《LeetCode热题100》笔记题解思路技巧优化_Part

《LeetCode热题100》笔记&题解&思路&技巧&优化_Part_1

😍😍😍 相知
🙌🙌🙌 相识
😢😢😢 开始刷题
- 哈希
- - 🟢1. 两数之和
  - 🟡2. 字母异位词分组
  - 🟡3. 最长连续序列
- 双指针
- - 🟢4. 移动零
  - 🟡5. 盛最多水的容器
  - 🟡6. 三数之和
  - 🔴7. 接雨水（滞留）
- 滑动窗口
- - 🟡8. 无重复字符的最长子串（滞留）
  - 🟡9. 找到字符串中所有字母异位词（滞留）
- 子串
- - 🟡10. 和为K的子数组（滞留）
  - 🔴11. 滑动窗口最大值（滞留）
  - 🔴12. 最小覆盖子串（滞留）

在这里插入图片描述

😍😍😍 相知

刷题不要一上来就直接干，先看题，明白题说的什么意思，然后想一下用什么现成的算法和数据结构可以快速解决，如果还是无从下手，建议先去看视频，不要直接翻评论或官方代码实现，看完视频，自己在idea中模拟敲几遍代码，如果跑通了，先别急着上leetcode黏贴，而是再回顾一下要点，然后确定自己完全懂了后，在leetcode中手敲，注意是手敲下来！！！目前我就是采用的这种方法，虽然慢，但是可以维持一周忘不掉它，如果要想长期不忘，只能隔段时间就review一下了，就算是大牛，知道方法，长时间不碰，也不可能保证一次到位把代码敲完一遍过！！！

🙌🙌🙌 相识

刷LeetCode热题100的想法有几个原因：

流行度高：LeetCode是一个广受欢迎的在线刷题平台，拥有大量用户和活跃的讨论社区。因此，热门题目通常代表了大多数人认为重要的题目或者面试中常见的题目。
面试备战：LeetCode上的题目往往和面试题目有很大的重合度。刷LeetCode热题100可以帮助你熟悉常见的面试题型和解题思路，提高应对面试的能力。
广泛的覆盖：热题100覆盖了各种难度级别的题目，包括简单、中等和困难。通过解答这些题目，可以提高自己的算法和编程能力，并扩展自己的知识面。
反馈和讨论：由于热题100是根据用户的反馈和讨论度排名的，因此这些题目往往有大量的解题思路和讨论可以参考。你可以从其他人的解题过程中学习到很多知识和技巧。

😢😢😢 开始刷题

哈希

🟢1. 两数之和

题目跳转：https://leetcode.cn/problems/two-sum/?envType=study-plan-v2&envId=top-100-liked

哈希经典！第一题！！你要知道他的重要性！！

这里用了一个技巧，就是存哈希Key的时候存的是target - nums[i]，这样，我们找的时候就可以直接找Key，当然你直接存nums[i] ，hashmap.containsKey的时候找target - nums[i]就行。

在这里插入图片描述

class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer,Integer> hashmap = new HashMap<>();
        for(int i = 0;i<nums.length;i++){
            if(hashmap.containsKey(nums[i])){
                return new int [] {hashmap.get(nums[i]),i};
            }
            else
            {
                hashmap.put(target - nums[i],i);
            }
        }
        return new int [] {0,0};
    }
}

🟡2. 字母异位词分组

题目跳转：https://leetcode.cn/problems/group-anagrams/description/?envType=study-plan-v2&envId=top-100-liked

在这里插入图片描述

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        List<List<String>> l_list = new ArrayList<>();
        Map<String,List<String>> map = new HashMap<>();
        for(int i = 0;i<strs.length;i++)
        {
            char[] temp_char = strs[i].toCharArray();
            Arrays.sort(temp_char);
            String str_temp = new String(temp_char);

            if(map.containsKey(str_temp))
            {
                map.get(str_temp).add(strs[i]);
            }
            else
            {
                List<String> list = new ArrayList<>();
                list.add(strs[i]);
                map.put(str_temp,list);
            }
        }
        Set<String> keys = map.keySet();
        for(String k:keys)
        {
            l_list.add( map.get(k));
        }
        return l_list;
    }
}

🟡3. 最长连续序列

题目跳转：https://leetcode.cn/problems/longest-consecutive-sequence/?envType=study-plan-v2&envId=top-100-liked

首先去重加上可以find到具体值一直探究到一个最长连续序列的最小值，也就是没有比这个最小值还要小的值了，任何再网上进行遍历，一直累加到没有本身+1的值记录当前穿的长度。

在这里插入图片描述

class Solution {
    public int longestConsecutive(int[] nums) {
        Set<Integer> num_set = new HashSet<Integer>();
        for (int num : nums) {
            num_set.add(num);
        }

        int res = 0;

        for (int num : num_set) {
            // num 是一串连续数字的第一个
            if (!num_set.contains(num - 1)) {
                int curNum = num;
                int cnt = 1;

                while(num_set.contains(curNum + 1)) {
                    curNum++;
                    cnt++;
                }

                res = Math.max(cnt, res);
            }
        }
        return res;
    }
}

双指针

🟢4. 移动零

题目跳转：https://leetcode.cn/problems/move-zeroes/description/?envType=study-plan-v2&envId=top-100-liked

在这里插入图片描述

class Solution {
    public void moveZeroes(int[] nums) {
        if(nums.length==0)return;
        int slow = 0;
        for(int fast = 0;fast < nums.length;fast++){
            if(nums[fast]==0) continue;
            else{
                nums[slow] = nums[fast];
                slow++;
            }
        } 
        while(slow<nums.length){
            nums[slow++] = 0;
        }

    }
}

🟡5. 盛最多水的容器

题目跳转：https://leetcode.cn/problems/container-with-most-water/?envType=study-plan-v2&envId=top-100-liked

在这里插入图片描述
分析

我们先从题目中的示例开始，一步一步地解释双指针算法的过程。稍后再给出算法正确性的证明。

题目中的示例为：

[1, 8, 6, 2, 5, 4, 8, 3, 7]
 ^                       ^

在初始时，左右指针分别指向数组的左右两端，它们可以容纳的水量为 $\min(1, 7) * 8 = 8$

此时我们需要移动一个指针。移动哪一个呢？直觉告诉我们，应该移动对应数字较小的那个指针（即此时的左指针）。这是因为，由于容纳的水量是由

两个指针指向的数字中较小值∗指针之间的距离

决定的。如果我们移动数字较大的那个指针，那么前者「两个指针指向的数字中较小值」不会增加，后者「指针之间的距离」会减小，那么这个乘积会减小。因此，我们移动数字较大的那个指针是不合理的。因此，我们移动数字较小的那个指针。

有读者可能会产生疑问：我们可不可以同时移动两个指针？先别急，我们先假设总是移动数字较小的那个指针的思路是正确的，在走完流程之后，我们再去进行证明。

所以，我们将左指针向右移动：

[1, 8, 6, 2, 5, 4, 8, 3, 7]
    ^                    ^

此时可以容纳的水量为 $\min(8, 7) * 7 = 49$ 。由于右指针对应的数字较小，我们移动右指针：

[1, 8, 6, 2, 5, 4, 8, 3, 7]
    ^                 ^

此时可以容纳的水量为 $\min(8, 3) * 6 = 18$ 。由于右指针对应的数字较小，我们移动右指针：

[1, 8, 6, 2, 5, 4, 8, 3, 7]
    ^              ^

此时可以容纳的水量为 $\min(8, 8) * 5 = 40$ 。两指针对应的数字相同，我们可以任意移动一个，例如左指针：

[1, 8, 6, 2, 5, 4, 8, 3, 7]
       ^           ^

此时可以容纳的水量为 $\min(6, 8) * 4 = 24$ 。由于左指针对应的数字较小，我们移动左指针，并且可以发现，在这之后左指针对应的数字总是较小，因此我们会一直移动左指针，直到两个指针重合。在这期间，对应的可以容纳的水量为： $\min(2, 8) * 3 = 6$ ， $\min(5, 8) * 2 = 10$ ， $\min(4, 8) * 1 = 4$ 。

在我们移动指针的过程中，计算到的最多可以容纳的数量为 49，即为最终的答案。

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

🟡6. 三数之和

题目跳转：https://leetcode.cn/problems/3sum/?envType=study-plan-v2&envId=top-100-liked

在这里插入图片描述

拿这个nums数组来举例，首先将数组排序，然后有一层for循环，i从下标0的地方开始，同时定一个下标left 定义在i+1的位置上，定义下标right 在数组结尾的位置上。

依然还是在数组中找到 abc 使得a + b +c =0，我们这里相当于 a = nums[i]，b = nums[left]，c = nums[right]。

接下来如何移动left 和right呢，如果
$n u m s [i] + n u m s [l e f t] + n u m s [r i g h t] > 0$

就说明此时三数之和大了，因为数组是排序后了，所以right下标就应该向左移动，这样才能让三数之和小一些。

如果 $n u m s [i] + n u m s [l e f t] + n u m s [r i g h t] < 0$ 说明此时三数之和小了，left 就向右移动，才能让三数之和大一些，直到left与right相遇为止。

时间复杂度： $O(n^2)$ 。

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

            }
            right= nums.length-1;
            left++;
            while(right>left+1&&nums[left-1]==nums[left])
            {
                left++;
            }
            
        }
        return result;
    }
}

🔴7. 接雨水（滞留）

题目跳转：https://leetcode.cn/problems/trapping-rain-water/description/?envType=study-plan-v2&envId=top-100-liked

在这里插入图片描述

我真的服了学点忘点。。。。

在这里插入图片描述

class Solution {
    public int trap(int[] height) {
        if(height.length<=2)return 0;
        int sum = 0;
        Stack<Integer> stack = new Stack<>();
        stack.push(0);
        for(int i = 1;i<height.length;i++){
            if(!stack.isEmpty()&&height[stack.peek()]>=height[i]){
                stack.push(i);
            }
            else{
                while(!stack.isEmpty()&&height[stack.peek()]<height[i]){
                    int a = height[stack.peek()];
                    stack.pop();
                    if(!stack.isEmpty()){
                        int b = Math.min(height[stack.peek()],height[i]);
                        sum +=  (b-a)*(i-stack.peek()-1);
                    }
                    
                }
                stack.push(i);
            }
        }
        return sum;

    }
}

滑动窗口

🟡8. 无重复字符的最长子串（滞留）

题目跳转：https://leetcode.cn/problems/longest-substring-without-repeating-characters/description/?envType=study-plan-v2&envId=top-100-liked

class Solution {
    public int lengthOfLongestSubstring(String s) {
        if(s.length()<=1)return s.length();
        HashSet<Character> hashset = new HashSet<>();
        int left = 0;
        int right = 0;
        int max =  0; 
        char[] chararr = s.toCharArray();
        for(int i = 0;i<chararr.length;i++){
            if(hashset.contains(chararr[i])){
                for(int j  = left ;j<=right;j++){
                    if(chararr[j]!=chararr[i]){
                        hashset.remove(chararr[j]);
                        left++;
                    }
                    else{
                        hashset.remove(chararr[j]);
                        left ++;
                        hashset.add(chararr[i]);
                        right = i;
                        left = j+1;
                        max = Math.max(max,hashset.size());
                        break;
                    }
                }
            }
            else{
                hashset.add(chararr[i]);
                right = i;
                max = Math.max(max,hashset.size());
            }
        }
        max = Math.max(max,hashset.size());
        return max;

    }
}

🟡9. 找到字符串中所有字母异位词（滞留）

题目跳转：https://leetcode.cn/problems/find-all-anagrams-in-a-string/description/?envType=study-plan-v2&envId=top-100-liked

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        //在长度为26的int数组target中存储字符串p中对应字符（a~z）出现的次数
        //如p="abc",则target为[1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
        //如p="bbdfeee",则target为[0,2,0,1,3,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
        int[] target = new int[26];
        for(int i = 0;i<p.length();i++){
            target[p.charAt(i)-'a']++;
        }
        int left = 0,right = 0;
        int[] window = new int [26];
        List<Integer> ans = new ArrayList<Integer>();
        while(right<s.length()){
            window[s.charAt(right) - 'a']++;
            if(right-left+1==p.length()){
                if(Arrays.equals(window,target)) ans.add(left);
                window[s.charAt(left) - 'a']--;
                left++;
            }
            right++;
        }
        return ans;

    }
}

子串

🟡10. 和为K的子数组（滞留）

题目跳转：https://leetcode.cn/problems/subarray-sum-equals-k/description/?envType=study-plan-v2&envId=top-100-liked

class Solution {
    public int subarraySum(int[] nums, int k) {
        if(nums.length<=0)return -1;
        int count = 0;
        int sum = 0;
        Map<Integer, Integer> hashmap = new HashMap<>();
        hashmap.put(0, 1);
         for(int i = 0;i < nums.length;i++){
            sum +=nums[i];
            if(hashmap.containsKey(sum-k)){
                count+=hashmap.get(sum-k);
            }
            if(hashmap.containsKey(sum)){
                hashmap.put(sum,hashmap.get(sum)+1);
            }
            else{
                hashmap.put(sum,1);
            }
        }
        return count;
    }
}

🔴11. 滑动窗口最大值（滞留）

题目跳转：https://leetcode.cn/problems/sliding-window-maximum/description/?envType=study-plan-v2&envId=top-100-liked

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if(nums.length<=0||k<=0)return new int [0];
        List<Integer> queue = new LinkedList<>();
        int [] arr = new int[nums.length-k+1];
        for( int i = 0;i<nums.length;i++){
            while(!queue.isEmpty()&&queue.getFirst()<i-k+1){
                queue.removeFirst();
            }
            while(!queue.isEmpty()&&nums[queue.getLast()]<nums[i]){
                queue.removeLast();
            }
            queue.add(i);
            if(i>=k-1)arr[i-k+1] = nums[queue.getFirst()];
        }
        return arr;
        
    }
}

🔴12. 最小覆盖子串（滞留）

题目跳转：https://leetcode.cn/problems/minimum-window-substring/description/?envType=study-plan-v2&envId=top-100-liked

class Solution {
    public String minWindow(String s, String t) {
        if(s.length() < t.length()) return "";

        HashMap<Character,Integer> hashmap = new HashMap<>();
        for(int i = 0;i < t.length();i++){
            char chartemp = t.charAt(i);
            hashmap.put(chartemp,hashmap.getOrDefault(chartemp,0)+1);
        }
        HashMap<Character,Integer> hashmap2 = new HashMap<>();
        int begin  = -1,minlen = -1;
        int count = 0;
        int left = 0;
        for(int right = 0;right<s.length();right++){
            char chartemp = s.charAt(right);
            hashmap2.put(chartemp,hashmap2.getOrDefault(chartemp,0)+1);
            if(hashmap2.get(chartemp)<=hashmap.getOrDefault(chartemp,0)){
                count++;
            }
            while(count>=t.length()){
                if(right-left+1<minlen||begin == -1){
                    begin = left;
                    minlen = right-left+1;
                }
                char temp = s.charAt(left);
                if(hashmap2.get(temp)<=hashmap.getOrDefault(temp,0)){
                    count--;
                }
                hashmap2.put(temp,hashmap2.get(temp)-1);
                left++;
            }
        }
        return begin ==-1?"":s.substring(begin,begin+minlen);


        
    }
}