力扣热题2-盛最多水的容器


按照leetcode刷一遍:leetcode hot

7. 整数反转

题目给定,不允许存储64位整数,也就是边界条件要自行判断:

如果反转后整数超过 32 位的有符号整数的范围 [−2^31, 2^31 − 1] ,就返回 0。

class Solution {
    public int reverse(int x) {
        if(x==Integer.MIN_VALUE) return 0;
        int result = 0;
        int sign = x<0?-1:1;
        x = Math.abs(x);
        int LASTLIMIT = Integer.MAX_VALUE/10;
        int cur;
        while(x!=0) {
            //System.out.println(result);
            cur = x%10;
            if(result>LASTLIMIT) {
                return 0;
            } else if(result==LASTLIMIT&&((sign==1&&cur>=8)||(sign==-1&&cur>8))) {
                return 0;
            } else {
                result = result*10+cur;
                x/=10;
            }
            
        }
        return result*sign;
    }
}

在java里面的话,取余操作是先按照正数然后加上符号来做的,所以这里我的去符号操作可以省略。

8. 字符串转换整数 (atoi)

可以看看边界条件的限定方法。

class Solution {
    public int myAtoi(String s) {
        if(s==null) return 0;
        s = s.trim();
        if(s.length()==0) return 0;
        int idx = 0;
        int n = s.length();
        int result = 0;
        int sign = 1;
        if(s.charAt(0)=='-') {
            sign=-1;
            idx++;
        } else if(s.charAt(0)=='+') {
            idx++;
        } else if(s.charAt(0)<'0'||s.charAt(0)>'9') {
            return 0;
        }
        for(;idx<n;idx++) {
            if(s.charAt(idx)<'0'||s.charAt(idx)>'9') {
                return sign*result;
            }
            //直接在这里把最大值最小值也返回了
            if(result>Integer.MAX_VALUE/10||
                (result==Integer.MAX_VALUE/10&&((s.charAt(idx)>='7'&&sign==1)||(s.charAt(idx)>='8'&&sign==-1)))) {
                    return sign==1?Integer.MAX_VALUE:Integer.MIN_VALUE;
            }
            //这里不会出现最大值最小值
            result = result*10+(int)(s.charAt(idx)-'0');
        }
        return result*sign;
    }
}

10. 正则表达式匹配

写了很久才写出来。两点吧:

  • 在判断当前位时判断下一位是不是星号
  • 记忆化
class Solution {
    public boolean isMatch(String s, String p) {
        int[][] state = new int[s.length()][p.length()];
        //0:没有状态
        //1:true
        //-1:false
        return isMatch0(s,0,p,0,state);
    }
    private boolean isMatch0(String s,int s_start,String p,int p_start,int[][] state) {
        if(s.length()==s_start&&p.length()==p_start) {
            return true;
        } 
        if(s.length()==s_start) {
            if(p_start+1<p.length()&&p.charAt(p_start+1)=='*') {
                return isMatch0(s,s_start,p,p_start+2,state);
            } 
            return false;
        } 
        if(p.length()==p_start) {
            return false;
        }
        if(state[s_start][p_start]!=0) {
            return state[s_start][p_start]==1;
        }
        boolean star = false;
        boolean noStar = false;
        if(p_start+1<p.length()&&p.charAt(p_start+1)=='*') {
            star |= isMatch0(s,s_start,p,p_start+2,state); //跳过x*,不管等不等都可以跳过
            //等才能继续
            if(s.charAt(s_start)==p.charAt(p_start)||p.charAt(p_start)=='.') {
                star |= isMatch0(s,s_start+1,p,p_start,state); //s前进一位
            }
        } else {
            if(s.charAt(s_start)==p.charAt(p_start)||p.charAt(p_start)=='.') {
                noStar |= isMatch0(s,s_start+1,p,p_start+1,state);
            } 
        }
        state[s_start][p_start] = (star|noStar)?1:-1;
        return star|noStar;
    }
}

(没想出来)11. 盛最多水的容器

没做出来。

image-20220130221440993

双指针法。

例如最开始如上图,实际上只能移动短的,也就是h=3的。因为如果移动h=7的,得到的新的盛水量肯定比当前小,因为左边h=3水都漏跑了。也就是排除了长边移动的所有情况。

class Solution {
    public int maxArea(int[] height) {
        int result = 0;
        int left = 0;
        int right = height.length-1;
        while(left<right) {
            result = Math.max(result,(right-left)*Math.min(height[left],height[right]));
            if(height[left]<height[right]) {
                left++;
            } else {
                right--;
            }
        }
        return result;
    }
}

13. 罗马数字转整数

这一题的问题就在于怎么写的简洁吧,我的还行。

class Solution {
    public int romanToInt(String s) {
        Map<Character,Integer> map = new HashMap<>();
        map.put('I',1);
        map.put('V',5);
        map.put('X',10);
        map.put('L',50);
        map.put('C',100);
        map.put('D',500);
        map.put('M',1000);
        int result = map.get(s.charAt(0));
        for(int idx = 1;idx<s.length();idx++) {
            char c = s.charAt(idx);
            if(map.get(c)>map.get(s.charAt(idx-1))) {
                result+=map.get(c)-2*map.get(s.charAt(idx-1));
            } else {
                result+=map.get(c);
            }
        }
        return result;
    }
}

14. 最长公共前缀

class Solution {
    public String longestCommonPrefix(String[] strs) {
        int idx = 0;
        String headStr = strs[0];
        while(true) {
            if(idx>=headStr.length()) {
                return strs[0].substring(0,idx);
            }
            for(int i=1;i<strs.length;i++) {
                String str = strs[i];
                if(idx>=str.length()||str.charAt(idx)!=headStr.charAt(idx)) {
                    return strs[0].substring(0,idx);
                }
            }
            idx++;
        }  
    }
}

(再看看)15. 三数之和

刚开始写出来的版本,效率比较低。

避免重复问题,就让三元组都必须是递增的形式,同时排序之后再相等的略过。

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> result = new ArrayList<>();
        Map<Integer,Integer> numMap = new HashMap<>();
        for(int n:nums) {
            numMap.put(n,numMap.getOrDefault(n,0)+1);
        }
        for(int i=0;i<nums.length;i++) {
            if(i>0&&nums[i]==nums[i-1]) continue;
            for(int j=i+1;j<nums.length;j++) {
                if(j>i+1&&nums[j]==nums[j-1]) continue;
                if(0-nums[i]-nums[j]<nums[j]) continue;
                int tmp = 0;
                if(0-nums[i]-nums[j]==nums[i]) tmp++;
                if(0-nums[i]-nums[j]==nums[j]) tmp++;
                if(numMap.getOrDefault(0-nums[i]-nums[j],0)>tmp) {
                    result.add(Arrays.asList(nums[i],nums[j],0-nums[i]-nums[j]));
                }
            }
        }
        return result;
    }
}

啊,没想起来,排完序就不用用map了,直接双指针。

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> result = new ArrayList<>();
        for(int i=0;i<=nums.length-3;i++) {
            if(i>0&&nums[i]==nums[i-1]) continue;
            int left = i+1;
            int right = nums.length-1;
            int target = 0-nums[i];
            while(left<right) {
                if(left>i+1&&nums[left]==nums[left-1]) {
                    left++;
                } else if(right<nums.length-1&&nums[right]==nums[right+1]) {
                    right--;
                } else if(nums[left]+nums[right]>target) {
                    right--;
                } else if(nums[left]+nums[right]==target) {
                    result.add(Arrays.asList(nums[i],nums[left],nums[right]));
                    left++;
                    right--;
                } else {
                    left++;
                }
            }
        }
        return result;
    }
}