【面试经典150】day 10

目录

1.验证回文串

 2.判断子序列

 3.两数之和 II - 输入有序数组

4.盛最多水的容器

 5.三数之和

1.验证回文串

class Solution {
    public boolean isPalindrome(String s) {
        int i=0,j=s.length()-1;
        while(i<j){
            //跳过非数字/字母
            while(i<j&&!Character.isLetterOrDigit(s.charAt(i))) i++;
            while(i<j&&!Character.isLetterOrDigit(s.charAt(j))) j--;
            if(Character.toLowerCase(s.charAt(i))!=Character.toLowerCase(s.charAt(j))) return false;
            i++;j--;
        }
        return true;
    }
}

 2.判断子序列

class Solution {
    public boolean isSubsequence(String s, String t) {
        //判断s是否是t的子序列
        //s为空肯定是子序列
        if(s.length()==0) return true;
        for(int i=0,j=0;j<t.length();j++){
            if(s.charAt(i)==t.charAt(j)){
                //如果已经到s的末端
                if(++i==s.length()){
                    return true;
                }
            }
        }
        return false;
    }
}

 ps：

 3.两数之和 II - 输入有序数组

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int i=0,j=numbers.length-1;
        while(i<j){
            int s=numbers[i]+numbers[j];
            if(s<target){
                i++;
            }else if(s>target){
                j--;
            }else return new int [] {i+1,j+1};
        }
        return new int[0];
    }
}

class Solution {
    public int maxArea(int[] height) {
        //本质上直接向内收缩就可以了
        int num1=0,num2=height.length-1;
        int mx=0;
        while(num1<num2){
           mx=Math.max(mx,Math.min(height[num1],height[num2])*(num2-num1));
           if(height[num1]<height[num2]){
                num1++;
            }else{
                num2--;
            }
        }

        return mx;
    }
}

4.盛最多水的容器

class Solution {
    public int maxArea(int[] height) {
        //本质上直接向内收缩就可以了
        int num1=0,num2=height.length-1;
        int mx=0;
        while(num1<num2){
           mx=Math.max(mx,Math.min(height[num1],height[num2])*(num2-num1));
           if(height[num1]<height[num2]){
                num1++;
            }else{
                num2--;
            }
        }

        return mx;
    }
}

 5.三数之和

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> ret=new ArrayList<>();
        Arrays.sort(nums);
        int n=nums.length;
        //k,i,j 3个指针
        for(int k=0;k<n-2;k++){
            if(nums[k]>0){
                break;
            }
            //去除重复项
            if(k>0&&nums[k]==nums[k-1]){
                continue;
            }
            int i=k+1;
            int j=n-1;
            while(i<j){
                int s=nums[k]+nums[i]+nums[j];
                if(s<0){
                    //每次移动都去除重复
                    i++;
                    while(i<j&&nums[i]==nums[i-1]){
                        i++;
                    }
                }else if(s>0){
                    j--;
                    while(i<j&&nums[j]==nums[j+1]){
                        j--;
                    }
                }else{
                    //转为[a,b,c]格式
                    ret.add(Arrays.asList(nums[k],nums[i],nums[j]));
                    i++;
                    j--;
                    while(i<j&&nums[i]==nums[i-1]){
                        i++;
                    }
                    while(i<j&&nums[j]==nums[j+1]){
                        j--;
                    }
                }
            }
        }
        return ret;
    }
}