言成言成啊 | Kit Chen's Blog

力扣100题

发布于2024-03-07 23:34:26，更新于2024-03-29 20:02:58，标签：java  转载随意，文章会持续修订，请注明来源地址：https://meethigher.top/blog

LeetCode 热题 100 - 学习计划 - 力扣（LeetCode）全球极客挚爱的技术成长平台

一、哈希

1.1 两数之和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> map = new LinkedHashMap<>();
    for (int i = 0; i < nums.length; i++) {
        int value = target - nums[i];
        if (map.containsKey(value)) {
            return new int[]{
                    map.get(value),
                    i
            };
        } else {
            map.put(nums[i], i);
        }
    }
    return new int[0];
}

1.2 字母异位词分组

核心做法：将字符串转为char数组然后排序，再将排序后char数组转为字符串。通过哈希判断即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public List<List<String>> groupAnagrams(String[] strs) {
    Map<String, List<String>> map = new HashMap<>();
    for (String str : strs) {
        char[] chars = str.toCharArray();
        Arrays.sort(chars);
        String key = Arrays.toString(chars);
        if (map.containsKey(key)) {
            map.get(key).add(str);
        } else {
            List<String> temp = new ArrayList<>();
            temp.add(str);
            map.put(key, temp);
        }
    }
    return new ArrayList<>(map.values());
}

1.3 最长连续新序列

这个其实没有用到哈希相关的知识，直接暴力for就是最好的解法！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public int longestConsecutive(int[] nums) {
    if (nums.length <= 1) {
        return nums.length;
    }
    Arrays.sort(nums);
    int max = 1, sum = 1;
    for (int i = 0; i < nums.length - 1; i++) {
        if (nums[i] == nums[i + 1]) {
            continue;
        }
        if (nums[i + 1] - nums[i] == 1) {
            if (++sum > max) {
                max = sum;
            }
        } else {
            sum = 1;
        }
    }
    return max;
}

二、指针

2.1 移动零

核心思路：设置index指针，将非0值与index值进行交换，之后index++。这里面有个妙处，就是值全不为0时。

1
2
3
4
5
6
7
8
9
10
public void moveZeroes(int[] nums) {
    int index = 0;
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] != 0) {
            int num = nums[index];
            nums[index++] = nums[i];
            nums[i] = num;
        }
    }
}

2.2 盛最多水的容器

核心思路：

若向内 移动短板 ，水槽的短板可能变大，因此下个水槽的面积 可能增大 。

若向内 移动长板 ，水槽的短板不变或变小，因此下个水槽的面积 一定变小 。

故应向内移动短板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int maxArea(int[] height) {
    int leftIndex = 0, rightIndex = height.length - 1, max = 0;
    for (int i = 0; i < height.length; i++) {
        int area = Math.min(height[leftIndex], height[rightIndex]) * (rightIndex - leftIndex);
        if (area > max) {
            max = area;
        }
        if (height[leftIndex] > height[rightIndex]) {
            rightIndex--;
        } else {
            leftIndex++;
        }
    }
    return max;
}

2.3 三数之和

要点：

  • nums[i]+nums[j]+nums[k]==0
  • i!=j!=k
  • 三元组的顺序不重要，但三元组结果集中数据不可重复
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
public List<List<Integer>> threeSum(int[] nums) {
    List<List<Integer>> list = new ArrayList<>();
    //按照从小到大排序
    Arrays.sort(nums);
    //[-4,-1,-1,0,1,2]
    for (int first = 0; first < nums.length; first++) {
        if (first > 0 && nums[first] == nums[first - 1]) {
            continue;
        }
        
        int target = -nums[first];
        
        //固定first，通过控制second与third双指针，确定两者和为target时的值
        int third = nums.length - 1;
        for (int second = first + 1; second < nums.length; second++) {
            if (second > first + 1 && nums[second] == nums[second - 1]) {
                continue;
            }
            //固定second，移动third指针
            while (third > second && nums[second] + nums[third] > target) {
                third--;
            }
            if (second >= third) {
                continue;
            }
            if (nums[second] + nums[third] == target) {
                List<Integer> temp = new ArrayList<>();
                temp.add(nums[first]);
                temp.add(nums[second]);
                temp.add(nums[third]);
                list.add(temp);
            }
        }
    }
    return list;
}

2.4 接雨水

核心思路：计算每个单位积水值，然后求和。在获取每个单位积水值的时候，需要知道该单位左侧和右侧的最大值，方能知道能否积水。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public int trap(int[] height) {
    //获取左侧最大值
    int[] leftMax = new int[height.length];
    for (int i = 0; i < height.length; i++) {
        if (i == 0) {
            leftMax[i] = 0;
        } else {
            leftMax[i] = Math.max(height[i - 1], leftMax[i - 1]);
        }
    }
    //获取右侧最大值
    int[] rightMax = new int[height.length];
    for (int i = height.length - 1; i >= 0; i--) {
        if (i == height.length - 1) {
            rightMax[i] = 0;
        } else {
            rightMax[i] = Math.max(height[i + 1], rightMax[i + 1]);
        }
    }
    //求总的积水值
    int sum = 0;
    for (int i = 0; i < height.length; i++) {
        int area = Math.min(leftMax[i], rightMax[i]) - height[i];
        if (area > 0) {
            sum += area;
        }
    }
    return sum;
}

三、滑动窗口

3.1 无重复字符的最长子串

核心思路：设置一个容器，将所有不重复的字符存入。当发现新来的字符重复时，就把第一个该字符及其前面字符移除掉。最蠢的办法，就是设置一个List，然后对List进行截取。但该容器的本质是需要维护一个左右可滑动窗口，所以List只是容器的很麻烦的一种实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public int lengthOfLongestSubstring(String s) {
    if (s.length() <= 1) {
        return s.length();
    }
    int left = 0, max = 0;
    char[] chars = s.toCharArray();
    for (int right = 1; right < chars.length; right++) {
        int index = left;
        //当发现新来的字符重复时，就把第一个该字符及其前面字符移除掉(换言之，就是将左指针往前移)
        while (index < right) {
            if (chars[index] == chars[right]) {
                left = index + 1;
            }
            index++;
        }
        if ((right + 1 - left) > max) {
            max = right + 1 - left;
        }
    }
    return max;
}

3.2 找到字符串中所有字母异位词

核心思路：控制一个长度固定的滑动窗口，依次向前滑动，并将值排序后与排序后的p进行比较。这算是最简单直观的暴力解法了。排序在数据量大时，性能会特别低，其实也不需要关心p串中的字符顺序，只关心其中各字母出现的频次

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public List<Integer> findAnagrams(String s, String p) {
    if (p.length() > s.length()) {
        return new ArrayList<>();
    }
    //创建两个容器，用来存放各字母出现的频次
    List<Integer> list = new ArrayList<>();
    int[] pa = new int[26];
    int[] sa = new int[26];
    //初始化字符串p的字母频次，以及字符串s的初始滑动窗口的字母频次
    for (int i = 0; i < p.length(); i++) {
        pa[p.charAt(i) - 'a']++;
        sa[s.charAt(i) - 'a']++;
    }
    //移动滑动窗口，滑动窗口移动的次数为s.length-p.length+1
    for (int left = 0; left <= s.length() - p.length(); left++) {
        //a b c d e
        //移除滑动窗口第一个值，也就是下标为left-1。引入滑动后的下一个值，也就是下标为left-1+p.length。初始的滑动窗口不需要再次赋值了
        if (left != 0) {
            sa[s.charAt(left - 1) - 'a']--;
            sa[s.charAt(left - 1 + p.length()) - 'a']++;
        }
        //若两个数组相等，则记录起始索引
        if (Arrays.equals(pa, sa)) {
            list.add(left);
        }
    }
    return list;
}

四、子串

4.1 和为k的子数组

核心思路：

  • 暴力解法，T=O(n²)。每个元素依次和后面的元素累加，记录和为k的次数。时间复杂度为
  • 前缀和解法，T=O(n)。可以通过计算前缀和来解决该问题，有两种情况均满足条件，如下
    1. 两个位置的前缀和的差为k
    2. 某个位置的前缀和为k

前缀和的原理其实我还没弄明白，不知道为啥要这样写，虽然答案是对的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int subarraySum(int[] nums, int k) {
    int sum = 0, prefixSum = 0;
    //前缀和:该和出现的次数
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        prefixSum += nums[i];
        if (prefixSum == k) {
            sum++;
        }
        sum += map.getOrDefault(prefixSum - k, 0);
        map.put(prefixSum, map.getOrDefault(prefixSum, 0) + 1);
    }
    return sum;
}

4.2 滑动窗口最大值

核心思路

  • 暴力解法，T=O(n²)：超时
  • 优先队列解法，T=O(nlogn)：比暴力解法略优。优先队列支持通过自定义排序的方式，int compare(Integer o1, Integer o2)前-后=从小到大，后-前=从大到小。
  • 双向队列解法：本质思路与优先队列类似，只是借用了双向队列存储依次存储值下标，并保证在队列中的值都是随着下标增大单调递减的，这样取最大值只需要取第一个即可。

优先队列解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public int[] maxSlidingWindow(int[] nums, int k) {
    if (k > nums.length) {
        return new int[0];
    }
    PriorityQueue<int[]> priorityQueue = new PriorityQueue<>((o1, o2) -> {
        //使用优先队列存储。数组下标0存储值，数组下标1存储值对应的下标
        //若值相等，就按照索引由小到大排序。若值不等，就按照值从大到小排序
        return o2[0] != o1[0] ? o2[0] - o1[0] : o1[1] - o2[1];
    });
    //首先计算出滑动窗口需要移动的次数, 即nums.length-k+1
    int[] ints = new int[nums.length - k + 1];
    //先将第一组放入，并获取第一组的最大值
    for (int i = 0; i < k; i++) {
        priorityQueue.add(new int[]{nums[i], i});
    }
    ints[0] = priorityQueue.peek()[0];
    //从第二组开始计算
    for (int left = 1; left < ints.length; left++) {
        //将滑窗右侧的值加入
        priorityQueue.add(new int[]{nums[left + k - 1], left + k - 1});
        //若最大值的索引在左窗索引的左边，就进行移除
        while (priorityQueue.peek()[1] < left) {
            priorityQueue.poll();
        }
        ints[left] = priorityQueue.peek()[0];
    }
    return ints;
}

单调队列解法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public int[] maxSlidingWindow(int[] nums, int k) {
    if (k > nums.length) {
        return new int[0];
    }
    //首先计算出滑动窗口需要移动的次数, 即nums.length-k+1
    int[] ints = new int[nums.length - k + 1];
    //使用双向队列来记录数组下标
    Deque<Integer> deque = new LinkedList<>();
    //先计算第一组的最大值
    for (int i = 0; i < k; i++) {
        //该操作是为了保证单调递减的值才会存入到队列中，所以只要取第一个即可获取到最大值
        while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {
            deque.pollLast();
        }
        deque.addLast(i);
    }
    ints[0] = nums[deque.peekFirst()];
    //由第二组开始
    for (int left = 1; left < ints.length; left++) {
        //该操作是为了保证单调递减的值才会存入到队列中，所以只要取第一个即可获取到最大值
        while (!deque.isEmpty() && nums[left + k - 1] >= nums[deque.peekLast()]) {
            deque.pollLast();
        }
        deque.addLast(left + k - 1);
        //判断最大值的坐标是否在滑窗左边界以左，若是则移除
        while (deque.peekFirst() < left) {
            deque.pollFirst();
        }
        ints[left] = nums[deque.peekFirst()];
    }
    return ints;
}
发布：2024-03-07 23:34:26
修改：2024-03-29 20:02:58
链接：https://meethigher.top/blog/2024/leetcode-100/
标签：java 
付款码 打赏 分享
访客数calculating人
shift+ctrl+1可控制目录显示