【二刷hot-100】day1

目录

1.两数之和

2.字母异位词分组

 3.字母异位词分组

 4.最长连续序列

 5.移动零

6.盛最多水的容器

7.三数之和 

 8.接雨水

1.两数之和

class Solution {
    public int[] twoSum(int[] nums, int target) {
         Map<Integer,Integer> map=new HashMap<>();
         for (int i=0;i<nums.length;i++){
            if(map.containsKey(target-nums[i])){
                return new int[] {map.get(target-nums[i]),i};
            }
            map.put(nums[i],i);
         } 
         throw new IllegalArgumentException("No two sum solution");
    }
}

2.字母异位词分组

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String,List<String>> m=new HashMap<>();
        for(String str:strs){
            char[] s=str.toCharArray();
            Arrays.sort(s);
            //s相同的字符串分到同一组
            m.computeIfAbsent(new String(s),k->new ArrayList<>()).add(str);
        }
        return new ArrayList<>(m.values());
    }
}

 3.字母异位词分组

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String,List<String>> m=new HashMap<>();
        for(String str:strs){
            char[] s=str.toCharArray();
            Arrays.sort(s);
            //s相同的字符串分到同一组
            m.computeIfAbsent(new String(s),k->new ArrayList<>()).add(str);
        }
        return new ArrayList<>(m.values());
    }
}

 4.最长连续序列

class Solution {
    public int longestConsecutive(int[] nums) {
        // 创建一个 HashSet 集合用于存储数组中的整数
        Set<Integer> num_set = new HashSet<Integer>();
        for (int num : nums) {
            // 将数组中的每个整数添加到集合中，去除重复元素
            num_set.add(num);
        }
        int longestStreak = 0;
        for (int num : num_set) {
            // 如果集合中不包含当前整数减一的值，说明当前整数可能是一个连续序列的起点
            if (!num_set.contains(num - 1)) {
                int currentNum = num;
                int currentStreak = 1;
                // 当集合中包含当前数字加一的值时，说明连续序列可以继续延伸
                while (num_set.contains(currentNum + 1)) {
                    currentNum += 1;
                    currentStreak += 1;
                }
                // 更新最长连续序列的长度
                longestStreak = Math.max(longestStreak, currentStreak);
            }
            //存在那这个数肯定不是开头，直接跳过。
        }
        return longestStreak;
    }
}

 5.移动零

class Solution {
    public void moveZeroes(int[] nums) {
        if(nums==null){
            return;
        }
        //i和j指针
        int j=0;
        for(int i=0;i<nums.length;i++){
            //!=0,左边    =0，右边
            if(nums[i]!=0){
                int tmp=nums[i];
                nums[i]=nums[j];
                nums[j++]=tmp;
            }
        }
    }
}

6.盛最多水的容器

class Solution {
    public int maxArea(int[] height) {
        int n=height.length;
        int num1=0;
        int num2=n-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+=1;
            }else{
                num2-=1;
            }
        }
        return mx;
    }
}

7.三数之和 

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
         List<List<Integer>>ret=new ArrayList<>();
         Arrays.sort(nums);
         int n=nums.length;
         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 sum=nums[k]+nums[i]+nums[j];
                if(sum<0){
                    i++;
                    while(i<j&&nums[i]==nums[i-1]){
                        i++;
                    }

                }else if(sum>0){
                    j--;
                    while(i<j&&nums[j]==nums[j+1]){
                        j--;
                    }
                }else{
                    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;
    }
}

 8.接雨水

class Solution {
    public int trap(int[] height) {
         int n=height.length;
         //height[0]到height[i]的最大值
         int [] preMax=new int[n];
         preMax[0]=height[0];
         for(int i=1;i<n;i++){
            preMax[i]=Math.max(preMax[i-1],height[i]);
         }
         //sufMax[i]表示height[i]到height[n-1]的最大值
         int [] sufMax=new int[n];
         sufMax[n-1]=height[n-1];
         for(int i=n-2;i>=0;i--){
            sufMax[i]=Math.max(sufMax[i+1],height[i]);
         }

         int ret=0;
         for(int i=0;i<n;i++){
            ret+=Math.min(preMax[i],sufMax[i])-height[i];
         }
         return ret;
    }
}

 ps:

略显轻松。