力扣 hot100 笔记

发表于 分类于 阅读次数： 本文字数： 46k 阅读时长 ≈ 2:46

leetcode hot100

太菜了，就先不写困难了

哈希

1. 两数之和

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。

你可以按任意顺序返回答案。

示例 1：

1
2
3
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：

1
2
输入：nums = [3,2,4], target = 6
输出：[1,2]

示例 3：

1
2
输入：nums = [3,3], target = 6
输出：[0,1]

提示：

  • 2 <= nums.length <= 104
  • -109 <= nums[i] <= 109
  • -109 <= target <= 109
  • 只会存在一个有效答案

**进阶：**你可以想出一个时间复杂度小于 O(n2) 的算法吗？

解题思路

  1. 遍历数组 nums
  2. 对于当前数字 x = nums[i]，计算它的配对数 diff = target - x
  3. 如果 diff 已经在哈希表中出现过，说明找到了答案，返回下标
  4. 否则，将 x 和它的下标 i 存入哈希表，方便后续查找
  5. 时间复杂度 O(n)，空间复杂度 O(n)

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        
        for (int i = 0; i < nums.length; i++) {
            int diff = target - nums[i];

            // 如果配对数出现过，直接返回答案
            if (map.containsKey(diff)) {
                return new int[] {map.get(diff), i};
            }

            // 否则存入当前值和下标
            map.put(nums[i], i);
        }

        return new int[0];
    }
}

复杂度分析

时间复杂度：O(n)，其中 n 是数组中的元素数量。对于每一个元素 x，我们可以 O(1) 地寻找 target - x。

空间复杂度：O(n)，其中 n 是数组中的元素数量。主要为哈希表的开销。

49. 字母异位词分组

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

示例 1:

输入: strs = [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”]

输出: [[“bat”],[“nat”,”tan”],[“ate”,”eat”,”tea”]]

解释：

  • 在 strs 中没有字符串可以通过重新排列来形成 "bat"。
  • 字符串 "nat" 和 "tan" 是字母异位词，因为它们可以重新排列以形成彼此。
  • 字符串 "ate" ，"eat" 和 "tea" 是字母异位词，因为它们可以重新排列以形成彼此。

示例 2:

输入: strs = [“”]

输出: [[“”]]

示例 3:

输入: strs = [“a”]

输出: [[“a”]]

提示：

  • 1 <= strs.length <= 104
  • 0 <= strs[i].length <= 100
  • strs[i] 仅包含小写字母

解题思路

  • 把字符串的字符排序后作为 key
  • 用 Map<String, List<String>> 存储
  • 时间复杂度：O(n * k log k)，k 为单词平均长度

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<>();
        
        for (String s : strs) {
            // 将字符串排序
            char[] chars = s.toCharArray();
            Arrays.sort(chars);
            String key = new String(chars);

            // 放入对应的分组
            map.computeIfAbsent(key, k -> new ArrayList<>()).add(s);
        }

        return new ArrayList<>(map.values());
    }
}

复杂度分析

时间复杂度：O(nk log k)，其中 n 是 strs 中的字符串的数量，k 是 strs 中的字符串的的最大长度。需要遍历 n 个字符串，对于每个字符串，需要 O(k log k) 的时间进行排序以及 O(1) 的时间更新哈希表，因此总时间复杂度是 O(nk log k)。

空间复杂度：O(nk)，其中 n 是 strs 中的字符串的数量，k 是 strs 中的字符串的的最大长度。需要用哈希表存储全部字符串。

128. 最长连续序列

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1：

1
2
3
输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。

示例 2：

1
2
输入：nums = [0,3,7,2,5,8,4,6,0,1]
输出：9

示例 3：

1
2
输入：nums = [1,0,1,2]
输出：3

提示：

  • 0 <= nums.length <= 105
  • -109 <= nums[i] <= 109

解题思路

  1. 把所有数字放进一个 HashSet，方便 O(1) 查询某个数字是否存在。

  2. 遍历每个数字 num：

    • 只从连续序列的起点开始往后数（即 num - 1 不在集合里时）

    • 不然会重复计算，比如序列 [1,2,3,4]，从 2 开始也能找到长度 3，但没必要

  3. 从起点 num 往后连续查找 num+1, num+2, ...，直到不连续为止，更新最大长度。

代码实现

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
class Solution {
    public int longestConsecutive(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }

        Set<Integer> set = new HashSet<>();
        for (int num : nums) {
            set.add(num);
        }

        int longest = 0;
        for (int num : set) {
            // 只从序列起点开始查
            if (!set.contains(num - 1)) {
                int currentNum = num;
                int length = 1;

                while (set.contains(currentNum + 1)) {
                    currentNum++;
                    length++;
                }

                longest = Math.max(longest, length);
            }
        }
        
        return longest;
    }
}

复杂度分析

  • 时间复杂度：O(n)，其中 n 为数组的长度。具体分析已在上面正文中给出。
  • 空间复杂度：O(n)。哈希表存储数组中所有的数需要 O(n) 的空间。

双指针

283. 移动零

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

请注意 ，必须在不复制数组的情况下原地对数组进行操作。

示例 1:

1
2
输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]

示例 2:

1
2
输入: nums = [0]
输出: [0]

提示:

  • 1 <= nums.length <= 104
  • -231 <= nums[i] <= 231 - 1

**进阶：**你能尽量减少完成的操作次数吗？

解题思路

  1. 双指针法：

    • slow：记录下一个非零元素应该放的位置

    • fast：遍历数组

  2. 遍历时：

    • 如果 nums[fast] != 0，就把 nums[fast] 放到 nums[slow]，slow++

  3. 遍历结束后，把从 slow 到末尾的元素全部置 0

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public void moveZeroes(int[] nums) {
        int slow = 0;  // 指向下一个非零元素的位置

        // 第一轮：把非零元素往前放
        for (int fast = 0; fast < nums.length; fast++) {
            if (nums[fast] != 0) {
                nums[slow] = nums[fast];
                slow++;
            }
        }

        // 第二轮：把剩下的位置填 0
        while (slow < nums.length) {
            nums[slow] = 0;
            slow++;
        }
    }
}

复杂度分析

  • 时间复杂度：O(n)，其中 n 为序列长度。每个位置至多被遍历两次。
  • 空间复杂度：O(1)。只需要常数的空间存放若干变量。

11. 盛最多水的容器

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

**说明：**你不能倾斜容器。

示例 1：

img

1
2
3
输入：[1,8,6,2,5,4,8,3,7]
输出：49 
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

示例 2：

1
2
输入：height = [1,1]
输出：1

提示：

  • n == height.length
  • 2 <= n <= 105
  • 0 <= height[i] <= 104

解题思路

  1. 左右指针分别从两端开始，计算当前容量
  2. 容量取决于较短的那条线，因为水不会溢出短板
  3. 移动短板指针，可能会找到更高的短板从而增大容量（移动长板无意义，因为高度受短板限制）

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int maxArea(int[] height) {
        int left = 0, right = height.length - 1;
        int maxArea = 0;

        while (left < right) {
            int h = Math.min(height[left], height[right]);
            int width = right - left;
            maxArea = Math.max(h * width, maxArea);

            // 移动短板
            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }
        
        return maxArea;
    }
}

复杂度分析

  • 时间复杂度：O(n)，双指针总计最多遍历整个数组一次。
  • 空间复杂度：O(1)，只需要额外的常数级别的空间。

15. 三数之和

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。

**注意：**答案中不可以包含重复的三元组。

示例 1：

1
2
3
4
5
6
7
8
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。

示例 2：

1
2
3
输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。

示例 3：

1
2
3
输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。

提示：

  • 3 <= nums.length <= 3000
  • -105 <= nums[i] <= 105

解题思路

  1. 排序数组（方便去重和使用双指针）。

  2. 遍历数组 i 作为第一个数 nums[i]。

  3. 对于每个 i，用双指针 (left, right) 找出后面两数之和为 -nums[i] 的组合。

  4. 去重：

    • i 重复时跳过

    • 找到一组解后，left 和 right 各自去掉重复的数，避免相同三元组重复加入结果。

代码实现

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
37
38
39
40
41
42
43
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums);  // 排序 O(n Log n)

        for (int i = 0; i < nums.length; i++) {
            // 跳过重复的第一个元素
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }

            int left = i + 1;
            int right = nums.length - 1;

            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];

                if (sum == 0) {
                    res.add(Arrays.asList(nums[i], nums[left], nums[right]));

                    // 跳过重复的 left
                    while (left < right && nums[left] == nums[left + 1]) {
                        left++;
                    }

                    // 跳过重复的 right
                    while (left < right && nums[right] == nums[right - 1]) {
                        right--;
                    }

                    left++;
                    right--;
                } else if (sum < 0) {
                    left++;  // 需要更大的和
                } else {
                    right--;  // 需要更小的和
                }
            }
        }

        return res;
    }
}

复杂度分析

时间复杂度：O(n^2)，其中 n 是数组 nums 的长度。

空间复杂度：O(log n)。我们忽略存储答案的空间，额外的排序的空间复杂度为 O(log n)。然而我们修改了输入的数组 nums，在实际情况下不一定允许，因此也可以看成使用了一个额外的数组存储了 nums 的副本并进行排序，空间复杂度为 O(n)。

滑动窗口

3. 无重复字符的最长子串

给定一个字符串 s ，请你找出其中不含有重复字符的 最长 子串 的长度。

示例 1:

1
2
3
输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:

1
2
3
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

1
2
3
4
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

提示：

  • 0 <= s.length <= 5 * 104
  • s 由英文字母、数字、符号和空格组成

解题思路

  1. 用两个指针 left 和 right 表示窗口的左右边界。
  2. 用一个 HashSet（或 Map）存储当前窗口内的字符。
  3. 向右扩展窗口（right++），如果出现重复字符，就移动 left 缩小窗口，直到没有重复为止。
  4. 在过程中不断更新最大长度 maxLen。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int lengthOfLongestSubstring(String s) {
        Set<Character> set = new HashSet<>();
        int maxLen = 0;
        int left = 0;

        for (int right = 0; right < s.length(); right++) {
            char c = s.charAt(right);

            // 如果重复，移动左指针
            while (set.contains(c)) {
                set.remove(s.charAt(left));
                left++;
            }

            // 加入新字符
            set.add(c);
            maxLen = Math.max(maxLen, right - left + 1);
        }

        return maxLen;
    }
}

复杂度分析

时间复杂度：O(N)，其中 N 是字符串的长度。左指针和右指针分别会遍历整个字符串一次。

空间复杂度：O(∣Σ∣)，其中 Σ 表示字符集（即字符串中可以出现的字符），∣Σ∣ 表示字符集的大小。在本题中没有明确说明字符集，因此可以默认为所有 ASCII 码在 [0,128) 内的字符，即 ∣Σ∣=128。我们需要用到哈希集合来存储出现过的字符，而字符最多有 ∣Σ∣ 个，因此空间复杂度为 O(∣Σ∣)。

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

给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

示例 1:

1
2
3
4
5
输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。

示例 2:

1
2
3
4
5
6
输入: s = "abab", p = "ab"
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。

提示:

  • 1 <= s.length, p.length <= 3 * 104
  • s 和 p 仅包含小写字母

解题思路

  1. 异位词判断：两个字符串的字符出现频率相同即可。
  2. 用两个长度为 26 的整型数组：
    • pCount 记录 p 中每个字符的频率。
    • sCount 记录当前窗口中每个字符的频率。
  3. 滑动窗口大小固定为 p.length()，在滑动过程中更新 sCount，并比较 sCount 与 pCount 是否相等。

代码实现

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
class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> res = new ArrayList<>();
        if (s.length() < p.length()) {
            return res;
        }

        int[] sCount = new int[26];
        int[] pCount = new int[26];
        int window = p.length();

        // 初始化 p 的字符频率
        for (char c : p.toCharArray()) {
            pCount[c - 'a']++;
        }
        
        for (int i = 0; i < s.length(); i++) {
            // 右边进入窗口
            sCount[s.charAt(i) - 'a']++;

            // 左边移出窗口
            if (i >= window) {
                sCount[s.charAt(i - window) - 'a']--;
            }

            // 比较两个频率数组
            if (Arrays.equals(sCount, pCount)) {
                res.add(i - window + 1);
            }
        }

        return res;
    }
}

复杂度分析

时间复杂度：O(m+(n−m)×Σ)，其中 n 为字符串 s 的长度，m 为字符串 p 的长度，Σ 为所有可能的字符数。我们需要 O(m) 来统计字符串 p 中每种字母的数量；需要 O(m) 来初始化滑动窗口；需要判断 n−m+1 个滑动窗口中每种字母的数量是否与字符串 p 中每种字母的数量相同，每次判断需要 O(Σ) 。因为 s 和 p 仅包含小写字母，所以 Σ=26。

空间复杂度：O(Σ)。用于存储字符串 p 和滑动窗口中每种字母的数量。

子串

560. 和为 K 的子数组

给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。

子数组是数组中元素的连续非空序列。

示例 1：

1
2
输入：nums = [1,1,1], k = 2
输出：2

示例 2：

1
2
输入：nums = [1,2,3], k = 3
输出：2

提示：

  • 1 <= nums.length <= 2 * 104
  • -1000 <= nums[i] <= 1000
  • -107 <= k <= 107

解题思路

核心公式：

1
prefixSum[j] - prefixSum[i] = k

其中：

  • prefixSum[j] 表示从数组开头到 j 的元素和
  • 如果 prefixSum[j] - k 在哈希表中出现过，说明存在以 j 结尾的子数组和为 k

步骤：

  1. 用 sum 记录当前前缀和
  2. 用 map 记录 某个前缀和出现的次数
  3. 遍历数组：
    • sum += nums[i]
    • 查看 map 中是否存在 sum - k
    • 如果存在，把出现次数加到答案中
    • 再把当前 sum 存入 map

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int subarraySum(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);  // 前缀和为 0 出现一次，表示从当前位置的和恰好为 k 的情况

        int sum = 0;
        int count = 0;

        for (int num : nums) {
            sum += num;

            // 查找是否有前缀和 = sum - k
            if (map.containsKey(sum - k)) {
                count += map.get(sum - k);
            }

            // 更新当前前缀和出现的次数
            map.put(sum, map.getOrDefault(sum, 0) + 1);
        }

        return count;
    }
}

复杂度分析

时间复杂度：O(n)，其中 n 为数组的长度。我们遍历数组的时间复杂度为 O(n)，中间利用哈希表查询删除的复杂度均为 O(1)，因此总时间复杂度为 O(n)。

空间复杂度：O(n)，其中 n 为数组的长度。哈希表在最坏情况下可能有 n 个不同的键值，因此需要 O(n) 的空间复杂度。

普通数组

53. 最大子数组和

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组是数组中的一个连续部分。

示例 1：

1
2
3
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

示例 2：

1
2
输入：nums = [1]
输出：1

示例 3：

1
2
输入：nums = [5,4,-1,7,8]
输出：23

提示：

  • 1 <= nums.length <= 105
  • -104 <= nums[i] <= 104

**进阶：**如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的 分治法 求解。

解题思路

我们要找的是一个 连续 子数组，和最大。
每个位置 i，我们要么：

  • 把当前元素 nums[i] 接在前面的子数组后面（如果前面和是正数，能帮它变大）
  • 从当前元素重新开始（如果前面的和是负数，还不如不要）

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int maxSubArray(int[] nums) {
        int currentSum = nums[0];
        int maxSum = nums[0];

        for (int i = 1; i < nums.length; i++) {
            // 要么加上 nums[i]，要么从 nums[i] 重新开始
            currentSum = Math.max(currentSum + nums[i], nums[i]);
            maxSum = Math.max(maxSum, currentSum);
        }

        return maxSum;
    }
}

复杂度分析

  • 时间复杂度：O(n)，其中 n 为 nums 数组的长度。我们只需要遍历一遍数组即可求得答案。
  • 空间复杂度：O(1)。我们只需要常数空间存放若干变量。

56. 合并区间

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

示例 1：

1
2
3
输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

示例 2：

1
2
3
输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。

示例 3：

1
2
3
输入：intervals = [[4,7],[1,4]]
输出：[[1,7]]
解释：区间 [1,4] 和 [4,7] 可被视为重叠区间。

提示：

  • 1 <= intervals.length <= 104
  • intervals[i].length == 2
  • 0 <= starti <= endi <= 104

解题思路

  1. 按区间的起点 start 升序排序，这样所有可能重叠的区间都会相邻出现。

  2. 用一个临时变量 current 表示正在合并的区间：

    • 如果新区间的起点 ≤ current 的终点，说明重叠，更新 current 的终点为两者终点的最大值；

    • 否则，没有重叠，把 current 加入结果，并开始合并下一个区间。

  3. 记得最后一个 current 也要放进结果中。

代码实现

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
class Solution {
    public int[][] merge(int[][] intervals) {
        if (intervals.length == 0) {
          return new int[0][0];
        }

        // 1. 按起点排序
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));

        List<int[]> merged = new ArrayList<>();

        // 2. 初始化第一个区间
        int[] current = intervals[0];

        for (int i = 1; i < intervals.length; i++) {
            // 如果重叠
            if (intervals[i][0] <= current[1]) {
                current[1] = Math.max(current[1], intervals[i][1]);
            } else {
                // 没有重叠，保存当前区间
                merged.add(current);
                current = intervals[i];
            }
        }

        // 3. 加入最后一个区间
        merged.add(current);

        return merged.toArray(new int[merged.size()][]);
    }
}

复杂度分析

时间复杂度：O(n log n)，其中 n 为区间的数量。除去排序的开销，我们只需要一次线性扫描，所以主要的时间开销是排序的 O(n log n)。

空间复杂度：O(log n)，其中 n 为区间的数量。这里计算的是存储答案之外，使用的额外空间。O(log n) 即为排序所需要的空间复杂度。

189. 轮转数组

给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

示例 1:

1
2
3
4
5
6
输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右轮转 1 步: [7,1,2,3,4,5,6]
向右轮转 2 步: [6,7,1,2,3,4,5]
向右轮转 3 步: [5,6,7,1,2,3,4]

示例 2:

1
2
3
4
5
输入：nums = [-1,-100,3,99], k = 2
输出：[3,99,-1,-100]
解释: 
向右轮转 1 步: [99,-1,-100,3]
向右轮转 2 步: [3,99,-1,-100]

提示：

  • 1 <= nums.length <= 105
  • -231 <= nums[i] <= 231 - 1
  • 0 <= k <= 105

进阶：

  • 尽可能想出更多的解决方案，至少有 三种 不同的方法可以解决这个问题。
  • 你可以使用空间复杂度为 O(1) 的 原地 算法解决这个问题吗？

解题思路

右旋转 k 步相当于：

  1. 先整体反转数组
  2. 再反转前 k 个元素
  3. 再反转剩余的 n - k 个元素

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public void rotate(int[] nums, int k) {
        int l = nums.length;
        k = k % l;  // 处理 k > n 的情况
        reverse(nums, 0, l - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, l - 1);
    }

    private void reverse(int[] nums, int left, int right) {
        if (nums.length < 2) {
            return;
        }

        while (left < right) {
            int temp = nums[left];
            nums[left] = nums[right];
            nums[right] = temp;
            left++;
            right--;
        }
    }
}

复杂度分析

  • 时间复杂度：O(n)，其中 n 为数组的长度。每个元素被翻转两次，一共 n 个元素，因此总时间复杂度为 O(2n)=O(n)。
  • 空间复杂度：O(1)。

238. 除自身以外数组的乘积

给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。

题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。

请 **不要使用除法，**且在 O(n) 时间复杂度内完成此题。

示例 1:

1
2
输入: nums = [1,2,3,4]
输出: [24,12,8,6]

示例 2:

1
2
输入: nums = [-1,1,0,-3,3]
输出: [0,0,9,0,0]

提示：

  • 2 <= nums.length <= 105
  • -30 <= nums[i] <= 30
  • 输入 保证 数组 answer[i] 在 32 位 整数范围内

**进阶：**你可以在 O(1) 的额外空间复杂度内完成这个题目吗？（ 出于对空间复杂度分析的目的，输出数组 不被视为 额外空间。）

解题思路

我们要求 answer[i] = nums[0] * nums[1] * ... * nums[i-1] * nums[i+1] * ... * nums[n-1]
也就是 当前位置的左边积 × 右边积。

  1. 先计算左积：
    • left[i] 表示 nums[0] ~ nums[i-1] 的乘积
    • 第 0 个位置没有左边元素，所以 left[0] = 1
  2. 再计算右积，并直接乘到结果数组上：
    • right 从末尾向前计算，不需要额外数组，用一个变量保存右积累乘值
    • 每一步 answer[i] = left[i] * right

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int[] productExceptSelf(int[] nums) {
        int[] answer = new int[nums.length];

        // 1. 计算左积
        answer[0] = 1;
        for (int i = 1; i < nums.length; i++) {
            answer[i] = answer[i - 1] * nums[i - 1];
        }

        // 2. 计算右积并乘在答案上
        int right = 1;  // 当前右边所有数的乘积
        for (int i = nums.length - 1; i >= 0; i--) {
            answer[i] = answer[i] * right;
            right *= nums[i];
        }

        return answer;
    }
}

复杂度分析

时间复杂度：O(n)，其中 n 指的是数组 nums 的大小。分析与方法一相同。
空间复杂度：O(1)，输出数组不算进空间复杂度中，因此我们只需要常数的空间存放变量。

矩阵

73. 矩阵置零

给定一个 *m* x *n* 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法**。**

示例 1：

img

1
2
输入：matrix = [[1,1,1],[1,0,1],[1,1,1]]
输出：[[1,0,1],[0,0,0],[1,0,1]]

示例 2：

img

1
2
输入：matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]
输出：[[0,0,0,0],[0,4,5,0],[0,3,1,0]]

提示：

  • m == matrix.length
  • n == matrix[0].length
  • 1 <= m, n <= 200
  • -231 <= matrix[i][j] <= 231 - 1

进阶：

  • 一个直观的解决方案是使用 O(*m**n*) 的额外空间，但这并不是一个好的解决方案。
  • 一个简单的改进方案是使用 O(*m* + *n*) 的额外空间，但这仍然不是最好的解决方案。
  • 你能想出一个仅使用常量空间的解决方案吗？

解题思路

如果不用额外数组，我们就需要 复用原矩阵的一部分来存储“这一行或这一列需要清零”的信息：

  1. 先判断第一行和第一列是否本来就有 0
    • 因为第一行和第一列会被用来做标记，所以要提前单独记下来
  2. 用第一行、第一列做标记
    • 遍历除第一行、第一列之外的元素，如果 matrix[i][j] == 0
      • 标记 matrix[i][0] = 0（该行要清零）
      • 标记 matrix[0][j] = 0（该列要清零）
  3. 根据标记清零
    • 再次遍历（不包括第一行第一列），如果当前行或列的标记是 0，就把它清零
  4. 最后处理第一行、第一列
    • 如果第一行原来有 0，整行清零
    • 如果第一列原来有 0，整列清零

代码实现

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
class Solution {
    public void setZeroes(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        boolean firstRowZero = false;
        boolean firstColZero = false;

        // 1. 判断第一行是否有 0
        for (int j = 0; j < n; j++) {
            if (matrix[0][j] == 0) {
                firstRowZero = true;
                break;
            }
        }

        // 2. 判断第一列是否有 0
        for (int i = 0; i < m; i++) {
            if (matrix[i][0] == 0) {
                firstColZero = true;
                break;
            }
        }

        // 3. 用第一行和第一列做标记
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (matrix[i][j] == 0) {
                    matrix[i][0] = 0;
                    matrix[0][j] = 0;
                }
            }
        }

        // 4，根据标记清零（不动第一行和第一列）
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                    matrix[i][j] = 0;
                }
            }
        }

        // 5. 处理第一行
        if (firstRowZero) {
            for (int j = 0; j < n; j++) {
            matrix[0][j] = 0;
            }
        }
        
        // 6. 处理第一列
        if (firstColZero) {
            for (int i = 0; i < m; i++) {
                matrix[i][0] = 0;
            }
        }
    }
}

复杂度分析

  • 时间复杂度：O(mn)，其中 m 是矩阵的行数，n 是矩阵的列数。我们至多只需要遍历该矩阵两次。
  • 空间复杂度：O(1)。我们只需要常数空间存储若干变量。

54. 螺旋矩阵

给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。

示例 1：

img

1
2
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5]

示例 2：

img

1
2
输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
输出：[1,2,3,4,8,12,11,10,9,5,6,7]

提示：

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= m, n <= 10
  • -100 <= matrix[i][j] <= 100

解题思路

  1. 定义四个指针：
    • top：当前最上边界
    • bottom：当前最下边界
    • left：当前最左边界
    • right：当前最右边界
  2. 按照顺时针顺序循环：
    1. 从左到右遍历上边界 top，然后 top++
    2. 从上到下遍历右边界 right，然后 right--
    3. 从右到左遍历下边界 bottom，然后 bottom--
    4. 从下到上遍历左边界 left，然后 left++
  3. 每次遍历前都判断 top <= bottom && left <= right，避免重复访问。

代码实现

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
37
38
39
40
41
class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> res = new ArrayList<>();
        if (matrix == null || matrix.length == 0) {
            return res;
        }

        int top = 0, right = matrix[0].length - 1, bottom = matrix.length - 1, left = 0;
        while (top <= bottom && left <= right) {
            // 1. 上边界从左到右
            for (int j = left; j <= right; j++) {
                res.add(matrix[top][j]);
            }
            top++;

            // 2. 右边界从上到下
            for (int i = top; i <= bottom; i++) {
                res.add(matrix[i][right]);
            }
            right--;

            // 3. 下边界从右到左
            if (top <= bottom) {
                for (int j = right; j >= left; j--) {
                    res.add(matrix[bottom][j]);
                }
                bottom--;
            }

            // 4. 左边界从下到上
            if (left <= right) {
                for (int i = bottom; i >= top; i--) {
                    res.add(matrix[i][left]);
                }
                left++;
            }
        }

        return res;
    }
}

复杂度分析

时间复杂度：O(mn)，其中 m 和 n 分别是输入矩阵的行数和列数。矩阵中的每个元素都要被访问一次。

空间复杂度：O(1)。除了输出数组以外，空间复杂度是常数。

48. 旋转图像

给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。

你必须在原地旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。

示例 1：

img

1
2
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[[7,4,1],[8,5,2],[9,6,3]]

示例 2：

img

1
2
输入：matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]
输出：[[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]

提示：

  • n == matrix.length == matrix[i].length
  • 1 <= n <= 20
  • -1000 <= matrix[i][j] <= 1000

解题思路

顺时针旋转 90° = 先转置（transpose） + 每行反转（reverse row）

  1. 转置矩阵：
    • 把 matrix[i][j] 和 matrix[j][i] 交换（只交换上三角部分，避免交换两次）
    • 转置后行列互换
  2. 每行反转：
    • 每一行首尾交换，得到最终顺时针 90° 的效果

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public void rotate(int[][] matrix) {
        int l = matrix.length;

        // 1. 转置
        for (int i = 0; i < l; i++) {
            for (int j = i; j < l; j++) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = temp;
            }
        }

        // 2. 每行反转
        for (int i = 0; i < l; i++) {
            for (int j = 0; j < l / 2; j++) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[i][l - j - 1];
                matrix[i][l - j - 1] = temp;
            }
        }
    }
}

复杂度分析

时间复杂度：O(n^2)，其中 n 是 matrix 的边长。对于每一次翻转操作，我们都需要枚举矩阵中一半的元素。

空间复杂度：O(1)。为原地翻转得到的原地旋转。

240. 搜索二维矩阵 II

编写一个高效的算法来搜索 *m* x *n* 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：

  • 每行的元素从左到右升序排列。
  • 每列的元素从上到下升序排列。

示例 1：

img

1
2
输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
输出：true

示例 2：

img

1
2
输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20
输出：false

提示：

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= n, m <= 300
  • -109 <= matrix[i][j] <= 109
  • 每行的所有元素从左到右升序排列
  • 每列的所有元素从上到下升序排列
  • -109 <= target <= 109

解题思路

当前位置元素 matrix[row][col] 与 target 比较

  • 如果 matrix[row][col] == target → 找到了，返回 true
  • 如果 matrix[row][col] > target → 当前列都比 target 大，所以向 左 移动一列（col--）
  • 如果 matrix[row][col] < target → 当前行都比 target 小，所以向 下 移动一行（row++）

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length;
        int n = matrix[0].length;

        // 从右上角开始
        int row = 0;
        int col = n - 1;

        while (row < m && col >= 0) {
            if (matrix[row][col] == target) {
                return true;
            } else if (matrix[row][col] > target) {
                col--;  // 向左移动
            } else {
                row++;  // 向下移动
            }
        }

        return false;
    }
}

复杂度分析

时间复杂度：O(m+n)。在搜索的过程中，如果我们没有找到 target，那么我们要么将 y 减少 1，要么将 x 增加 1。由于 (x,y) 的初始值分别为 (0,n−1)，因此 y 最多能被减少 n 次，x 最多能被增加 m 次，总搜索次数为 m+n。在这之后，x 和 y 就会超出矩阵的边界。

空间复杂度：O(1)。

链表

160. 相交链表

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

图示两个链表在节点 c1 开始相交**：**

img

题目数据 保证 整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

自定义评测：

评测系统 的输入如下（你设计的程序 不适用 此输入）：

  • intersectVal - 相交的起始节点的值。如果不存在相交节点，这一值为 0
  • listA - 第一个链表
  • listB - 第二个链表
  • skipA - 在 listA 中（从头节点开始）跳到交叉节点的节点数
  • skipB - 在 listB 中（从头节点开始）跳到交叉节点的节点数

评测系统将根据这些输入创建链式数据结构，并将两个头节点 headA 和 headB 传递给你的程序。如果程序能够正确返回相交节点，那么你的解决方案将被 视作正确答案 。

示例 1：

img

1
2
3
4
5
6
输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at '8'
解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,6,1,8,4,5]。
在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
— 请注意相交节点的值不为 1，因为在链表 A 和链表 B 之中值为 1 的节点 (A 中第二个节点和 B 中第三个节点) 是不同的节点。换句话说，它们在内存中指向两个不同的位置，而链表 A 和链表 B 中值为 8 的节点 (A 中第三个节点，B 中第四个节点) 在内存中指向相同的位置。

示例 2：

img

1
2
3
4
5
输入：intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Intersected at '2'
解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [1,9,1,2,4]，链表 B 为 [3,2,4]。
在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。

示例 3：

img

1
2
3
4
5
输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：No intersection
解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。
由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
这两个链表不相交，因此返回 null 。

提示：

  • listA 中节点数目为 m
  • listB 中节点数目为 n
  • 1 <= m, n <= 3 * 104
  • 1 <= Node.val <= 105
  • 0 <= skipA <= m
  • 0 <= skipB <= n
  • 如果 listA 和 listB 没有交点，intersectVal 为 0
  • 如果 listA 和 listB 有交点，intersectVal == listA[skipA] == listB[skipB]

**进阶：**你能否设计一个时间复杂度 O(m + n) 、仅用 O(1) 内存的解决方案？

解题思路

  • 两个指针 pA 和 pB 分别从 headA 和 headB 出发
  • 当 pA 走到 A 链表的末尾，就跳到 B 链表的头继续走
  • 当 pB 走到 B 链表的末尾，就跳到 A 链表的头继续走
  • 如果两条链表相交，那么它们会在某个节点相遇（就是交点）
  • 如果不相交，两个指针最终都会走到 null，同时结束

这样做的原因：

  • 指针 pA 走过的路：A 链表长度 + B 链表长度
  • 指针 pB 走过的路：B 链表长度 + A 链表长度
  • 两者走的总长度相等，所以一定会在同一时刻到达交点或 null。

代码实现

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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }

        ListNode pA = headA;
        ListNode pB = headB;

        // 两指针走到同一个节点（可能是交点，也可能是 null）
        while (pA != pB) {
            pA = (pA == null) ? headB : pA.next;
            pB = (pB == null) ? headA : pB.next;
        }

        return pA;  // 要么是交点，要么是 null
    }
}

复杂度分析

时间复杂度：O(m+n)，其中 m 和 n 是分别是链表 headA 和 headB 的长度。两个指针同时遍历两个链表，每个指针遍历两个链表各一次。

空间复杂度：O(1)。

206. 反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例 1：

img

1
2
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

示例 2：

img

1
2
输入：head = [1,2]
输出：[2,1]

示例 3：

1
2
输入：head = []
输出：[]

提示：

  • 链表中节点的数目范围是 [0, 5000]
  • -5000 <= Node.val <= 5000

**进阶：**链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？

方法一：迭代

解题思路

用三个指针：prev（前驱节点）、curr（当前节点）、next（暂存下一个节点）。

每次把 curr.next 指向 prev，然后整体往前推进。

代码实现

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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
                ListNode prev = null;
        ListNode curr = head;

        while (curr != null) {
            ListNode next = curr.next;  // 暂存下一个节点
            curr.next = prev;           // 反转指针
            prev = curr;                // 前驱前进
            curr = next;                // 当前前进
        }

        return prev;  // prev 指向新头
    }
}

复杂度分析

  • 时间复杂度：O(n)，其中 n 是链表的长度。需要遍历链表一次。
  • 空间复杂度：O(1)。

方法二：递归

解题思路

从第二个节点开始递归反转后续链表，等反转完成后，将当前节点放到末尾。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public ListNode reverseList(ListNode head) {
        // 递归结束条件
        if (head == null || head.next == null) {
            return head;
        }

        ListNode newNode = reverseList(head.next);

        // 将当前节点放到后面
        head.next.next = head;
        head.next = null;

        return newNode;
    }
}

复杂度分析

时间复杂度：O(n)，其中 n 是链表的长度。需要对链表的每个节点进行反转操作。

空间复杂度：O(n)，其中 n 是链表的长度。空间复杂度主要取决于递归调用的栈空间，最多为 n 层。

234. 回文链表

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

示例 1：

img

1
2
输入：head = [1,2,2,1]
输出：true

示例 2：

img

1
2
输入：head = [1,2]
输出：false

提示：

  • 链表中节点数目在范围[1, 105] 内
  • 0 <= Node.val <= 9

**进阶：**你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

解题思路

  1. 找到链表中点（快慢指针）
    • 快指针一次走 2 步，慢指针一次走 1 步。
    • 当快指针走到结尾，慢指针正好到中间。
  2. 反转后半段链表
    • 从中点开始，把链表后半部分原地反转。
  3. 比较前半段和后半段
    • 两个指针从链表头部和反转后的后半段同时往后走，逐个比较值是否相等。
    • 比较完可选恢复链表（不要求可省略）。

代码实现

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) {
            return true;
        }
        
        // 1. 找中点（偶数时取左中点）
        ListNode slow = head, fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        // 2. 反转后半段
        ListNode secondHalf = reverse(slow.next);

        // 3. 比较两段
        ListNode p1 = head;
        ListNode p2 = secondHalf;
        boolean result = true;
        while (p2 != null) {  // 只需要遍历后半段
            if (p1.val != p2.val) {
                result = false;
                break;
            }

            p1 = p1.next;
            p2 = p2.next;
        }

        // 4. 恢复链表
        slow.next = reverse(secondHalf);

        return result;
    }

    // 反转链表（迭代法）
    private ListNode reverse(ListNode head) {
        ListNode prev = null, curr = head;
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }

        return prev;
    }
}

复杂度分析

  • 时间复杂度：O(n)，其中 n 指的是链表的大小。
  • 空间复杂度：O(1)。我们只会修改原本链表中节点的指向，而在堆栈上的堆栈帧不超过 O(1)。

141. 环形链表

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ，则返回 true 。 否则，返回 false 。

示例 1：

img

1
2
3
输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

img

1
2
3
输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

img

1
2
3
输入：head = [1], pos = -1
输出：false
解释：链表中没有环。

提示：

  • 链表中节点的数目范围是 [0, 104]
  • -105 <= Node.val <= 105
  • pos 为 -1 或者链表中的一个 有效索引 。

**进阶：**你能用 O(1)（即，常量）内存解决此问题吗？

解题思路

两个指针：

  • slow 每次走 1 步
  • fast 每次走 2 步

如果链表有环，那么 fast 最终会在环内追上 slow（就像跑道上跑步一样）。

如果链表无环，那么 fast 会先走到 null（链表尾）。

代码实现

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
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) {
            return false;
        }

        ListNode slow = head;
        ListNode fast = head;

        while (fast != null && fast.next != null) {
            slow = slow.next;       // 慢指针走一步
            fast = fast.next.next;  // 快指针走两步
            if (slow == fast) {     // 相遇 => 有环
                return true;
            }
        }

        return false;  // fast 走到 null => 无环
    }
}

复杂度分析

时间复杂度：O(N)，其中 N 是链表中的节点数。

当链表中不存在环时，快指针将先于慢指针到达链表尾部，链表中每个节点至多被访问两次。

当链表中存在环时，每一轮移动后，快慢指针的距离将减小一。而初始距离为环的长度，因此至多移动 N 轮。

空间复杂度：O(1)。我们只使用了两个指针的额外空间。

142. 环形链表 II

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改 链表。

示例 1：

img

1
2
3
输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

img

1
2
3
输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

img

1
2
3
输入：head = [1], pos = -1
输出：返回 null
解释：链表中没有环。

提示：

  • 链表中节点的数目范围在范围 [0, 104] 内
  • -105 <= Node.val <= 105
  • pos 的值为 -1 或者链表中的一个有效索引

**进阶：**你是否可以使用 O(1) 空间解决此题？

解题思路

  1. 第一步：用快慢指针判断链表是否有环（跟 hasCycle 一样）。
    • slow 每次走一步
    • fast 每次走两步
    • 如果 slow == fast，说明有环
    • 如果 fast 或 fast.next 为空，说明无环，直接返回 null
  2. 第二步：找到环的入口
    • 相遇后，让 一个指针从 head 出发，另一个指针从相遇点出发
    • 两个指针都 每次走一步
    • 它们再次相遇的点，就是 环的入口节点

为什么这样可行（数学推导）

设：

  • a = 链表头到环入口的距离
  • b = 环入口到相遇点的距离
  • c = 相遇点到环入口的距离（即环剩余的长度）

第一次相遇时：

  • slow 走了 a + b

  • fast 走了 a + b + n(b + c)（n 表示快指针多绕的圈数）

  • 因为快指针速度是慢指针的 2 倍：

    1
    2
    3
    4
    2(a + b) = a + b + n(b + c)
    a + b = n(b + c)
    a = n(b + c) - b
    a = (n - 1)(b + c) + c

    这说明：从头节点走 a 步，等价于从相遇点走 c 步（到达环入口）。

代码实现

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
37
38
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        if (head == null || head.next == null) {
          return null;
        }

        // 1. 判断是否有环
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                // 2. 寻找环入口
                ListNode ptr = head;
                while (ptr != slow) {
                    ptr = ptr.next;
                    slow = slow.next;
                }
            
                return ptr;
            }
        }

        return null;  // 无环
    }
}

复杂度分析

时间复杂度：O(N)，其中 N 为链表中节点的数目。在最初判断快慢指针是否相遇时，slow 指针走过的距离不会超过链表的总长度；随后寻找入环点时，走过的距离也不会超过链表的总长度。因此，总的执行时间为 O(N)+O(N)=O(N)。

空间复杂度：O(1)。我们只使用了 slow,fast,ptr 三个指针。

21. 合并两个有序链表

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例 1：

img

1
2
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

示例 2：

1
2
输入：l1 = [], l2 = []
输出：[]

示例 3：

1
2
输入：l1 = [], l2 = [0]
输出：[0]

提示：

  • 两个链表的节点数目范围是 [0, 50]
  • -100 <= Node.val <= 100
  • l1 和 l2 均按 非递减顺序 排列

解题思路

  1. 创建一个 dummy 节点（值随便，比如 0），并用 tail 指向它。
  2. 遍历 list1 和 list2：
    • 比较 list1.val 和 list2.val
    • 取较小的节点挂到 tail.next
    • 移动对应的链表指针
  3. 如果其中一个链表还没走完，把剩余部分直接接到 tail.next
  4. 返回 dummy.next（因为 dummy 是占位用的）

代码实现

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
37
38
39
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        // 虚拟头节点
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;

        // 当两个链表都不为空时
        while (list1 != null && list2 != null) {
            if (list1.val <= list2.val) {
                tail.next = list1;
                list1 = list1.next;
            } else {
                tail.next = list2;
                list2 = list2.next;
            }
            tail = tail.next;  // 移动尾指针
        }

        // 如果有一个链表没走完，直接接上
        if (list1 != null) {
            tail.next = list1;
        }
        if (list2 != null) {
            tail.next = list2;
        }

        return dummy.next;
    }
}

复杂度分析

时间复杂度：O(n+m)，其中 n 和 m 分别为两个链表的长度。因为每次循环迭代中，l1 和 l2 只有一个元素会被放进合并链表中， 因此 while 循环的次数不会超过两个链表的长度之和。所有其他操作的时间复杂度都是常数级别的，因此总的时间复杂度为 O(n+m)。

空间复杂度：O(1)。我们只需要常数的空间存放若干变量。

2. 两数相加

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例 1：

img

1
2
3
输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.

示例 2：

1
2
输入：l1 = [0], l2 = [0]
输出：[0]

示例 3：

1
2
输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出：[8,9,9,9,0,0,0,1]

提示：

  • 每个链表中的节点数在范围 [1, 100] 内
  • 0 <= Node.val <= 9
  • 题目数据保证列表表示的数字不含前导零

解题思路

  1. 创建虚拟头节点（dummy）简化链表操作，用 curr 指向当前处理位置。
  2. 初始化进位 carry = 0。
  3. 遍历 l1 和 l2：
    • 取当前节点的值（如果节点为 null，则值为 0）
    • 计算和 sum = x + y + carry
    • 计算当前位的值 sum % 10，作为新节点的值
    • 更新进位 carry = sum / 10
  4. 遍历结束后，如果 carry > 0，要在链表末尾加一个节点。
  5. 返回 dummy.next

代码实现

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
37
38
39
40
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode curr = dummy;
        int carry = 0;
        
        while (l1 != null || l2 != null) {
            int x = (l1 == null) ? 0 : l1.val;
            int y = (l2 == null) ? 0 : l2.val;

            int sum = x + y + carry;
            carry = sum / 10;
            curr.next = new ListNode(sum % 10);
            curr = curr.next;

            if (l1 != null) {
                l1 = l1.next;
            }
            if (l2 != null) {
                l2 = l2.next;
            }
        }

        if (carry > 0) {
            curr.next = new ListNode(carry);
        }

        return dummy.next;
    }
}

复杂度分析

时间复杂度：O(max(m,n))，其中 m 和 n 分别为两个链表的长度。我们要遍历两个链表的全部位置，而处理每个位置只需要 O(1) 的时间。

空间复杂度：O(1)。注意返回值不计入空间复杂度。

19. 删除链表的倒数第 N 个结点

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

示例 1：

img

1
2
输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]

示例 2：

1
2
输入：head = [1], n = 1
输出：[]

示例 3：

1
2
输入：head = [1,2], n = 1
输出：[1]

提示：

  • 链表中结点的数目为 sz
  • 1 <= sz <= 30
  • 0 <= Node.val <= 100
  • 1 <= n <= sz

**进阶：**你能尝试使用一趟扫描实现吗？

解题思路

虚拟头节点：加一个 dummy，指向 head，避免删除头节点时的特殊处理。

快慢指针：让 fast 先走 n+1 步，这样 slow 停在待删除节点的前一个位置。同时移动 fast 和 slow，直到 fast 到达链表末尾。

删除节点：slow.next = slow.next.next

返回结果：返回 dummy.next（防止删除的是头节点）

代码实现

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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head);
        ListNode slow = dummy;
        ListNode fast = dummy;
        
        // 快指针先走 n + 1 步
        for (int i = 0; i <= n; i++) {
            fast = fast.next;
        }

        // 快慢指针同时移动
        while (fast != null) {
            slow = slow.next;
            fast = fast.next;
        }

        // 删除倒数第 n 个节点
        slow.next = slow.next.next;

        return dummy.next;
    }
}

复杂度分析

  • 时间复杂度：O(L)，其中 L 是链表的长度。
  • 空间复杂度：O(1)。

24. 两两交换链表中的节点

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

示例 1：

img

1
2
输入：head = [1,2,3,4]
输出：[2,1,4,3]

示例 2：

1
2
输入：head = []
输出：[]

示例 3：

1
2
输入：head = [1]
输出：[1]

提示：

  • 链表中节点的数目在范围 [0, 100] 内
  • 0 <= Node.val <= 100

解题思路

dummy 节点

  • 避免处理 head 是空或需要交换第一个节点的特殊情况。
  • 统一用 prev.next 来指向待交换的第一个节点。

prev 节点

  • 指向当前待交换节点的前驱。
  • 每次交换完成后，prev 移动到被交换后顺序靠后的节点（也就是 first）。

while 条件

  • prev.next != null && prev.next.next != null 保证有两个节点可以交换。

交换过程

  • first.next = second.next; → 先把第一个节点指向第二个节点之后的节点。
  • second.next = first; → 第二个节点指向第一个节点，实现反转。
  • prev.next = second; → 前驱节点指向新的头节点。

代码实现

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
37
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode swapPairs(ListNode head) {
        // 1. 创建一个 dummy 节点，指向 head
        ListNode dummy = new ListNode(0, head);

        // 2. 用 prev 来跟踪待交换节点的前驱
        ListNode prev = dummy;

        // 3. 当有两个节点可以交换时，循环
        while (prev.next != null && prev.next.next != null) {
            // 定位两个待交换节点
            ListNode first = prev.next;
            ListNode second = first.next;

            // 交换节点
            first.next = second.next;
            second.next = first;
            prev.next = second;

            // 移动 prev，准备下一轮交换
            prev = first;
        }

        // 4. 返回新的头节点
        return dummy.next;
    }
}

复杂度分析

  • 时间复杂度：O(n)，其中 n 是链表的节点数量。需要对每个节点进行更新指针的操作。
  • 空间复杂度：O(1)。

138. 随机链表的复制

给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。

构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。

例如，如果原链表中有 X 和 Y 两个节点，其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random --> y 。

返回复制链表的头节点。

用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：

  • val：一个表示 Node.val 的整数。
  • random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null 。

你的代码 只 接受原链表的头节点 head 作为传入参数。

示例 1：

img

1
2
输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]

示例 2：

img

1
2
输入：head = [[1,1],[2,1]]
输出：[[1,1],[2,1]]

示例 3：

img

1
2
输入：head = [[3,null],[3,0],[3,null]]
输出：[[3,null],[3,0],[3,null]]

提示：

  • 0 <= n <= 1000
  • -104 <= Node.val <= 104
  • Node.random 为 null 或指向链表中的节点。

解题思路

  1. 在每个原节点后面插入新节点

    • 原链表：A -> B -> C
    • 插入新节点：A -> A' -> B -> B' -> C -> C'
    • 新节点 A' 的 val = A.val，next 暂时指向原节点的 next。

  2. 复制 random 指针

    • 对于原节点 A：

      1
      2
      if (A.random != null)
          A.next.random = A.random.next;

    • 因为 A.next 是新节点，A.random.next 正好是新节点对应的 random 指向。

  3. 拆分链表

    • 将原链表和新链表拆开：
      • 原链表恢复：A -> B -> C
      • 新链表：A' -> B' -> C'

代码实现

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
/*
// Definition for a Node.
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
*/

class Solution {
    public Node copyRandomList(Node head) {
        if (head == null) {
            return null;
        }

        // 1. 在每个节点后插入新节点
        Node curr = head;
        while (curr != null) {
            Node newNode = new Node(curr.val);
            newNode.next = curr.next;
            curr.next = newNode;
            curr = newNode.next;
        }

        // 2. 复制 random 指针
        curr = head;
        while (curr != null) {
            if (curr.random != null) {
                curr.next.random = curr.random.next;
            }
            curr = curr.next.next;
        }

        // 3. 拆分链表
        Node dummy = new Node(0);
        Node copyCurr = dummy;
        curr = head;
        while (curr != null) {
            copyCurr.next = curr.next;
            copyCurr = copyCurr.next;

            curr.next = curr.next.next;  // 恢复原链表
            curr = curr.next;
        }

        return dummy.next;
    }
}

复杂度分析

时间复杂度：O(n)，其中 n 是链表的长度。我们只需要遍历该链表三次。

读者们也可以自行尝试在计算拷贝节点的随机指针的同时计算其后继指针，这样只需要遍历两次。
空间复杂度：O(1)。注意返回值不计入空间复杂度。

148. 排序链表

给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。

示例 1：

img

1
2
输入：head = [4,2,1,3]
输出：[1,2,3,4]

示例 2：

img

1
2
输入：head = [-1,5,3,4,0]
输出：[-1,0,3,4,5]

示例 3：

1
2
输入：head = []
输出：[]

提示：

  • 链表中节点的数目在范围 [0, 5 * 104] 内
  • -105 <= Node.val <= 105

**进阶：**你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？

解题思路

  1. 递归拆分链表

    • 用 快慢指针 找中点，将链表一分为二。
    • 快指针一次走两步，慢指针一次走一步，快指针到尾时，慢指针就是中点。

  2. 递归排序左右两部分

  3. 合并两个有序链表

    • 这个可以直接用 合并两个有序链表的题目 的方法。

代码实现

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode sortList(ListNode head) {
        // 递归结束条件
        if (head == null || head.next == null) {
            return head;
        }

        // 1. 快慢指针找中点
        ListNode slow = head, fast = head, prev = null;
        while (fast != null && fast.next != null) {
            prev = slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        prev.next = null;  // 断开链表

        // 2. 递归排序左右两部分
        ListNode l1 = sortList(head);
        ListNode l2 = sortList(slow);

        // 3. 合并两个有序链表
        return merge(l1, l2);
    }

    private ListNode merge(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode curr = dummy;

        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                curr.next = l1;
                l1 = l1.next;
            } else {
                curr.next = l2;
                l2 = l2.next;
            }
            curr = curr.next;
        }

        curr.next = (l1 == null) ? l2 : l1;

        return dummy.next;
    }
}

复杂度分析

  • 时间复杂度：O(n log n)，其中 n 是链表的长度。
  • 空间复杂度：O(log n)，其中 n 是链表的长度。空间复杂度主要取决于递归调用的栈空间。

146. LRU 缓存

请你设计并实现一个满足 LRU (最近最少使用) 缓存约束的数据结构。

实现 LRUCache 类：

  • LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
  • int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
  • void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。

函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
输入
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]

解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1);    // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2);    // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1);    // 返回 -1 (未找到)
lRUCache.get(3);    // 返回 3
lRUCache.get(4);    // 返回 4

提示：

  • 1 <= capacity <= 3000
  • 0 <= key <= 10000
  • 0 <= value <= 105
  • 最多调用 2 * 105 次 get 和 put

解题思路

这个 LRU 缓存题的核心是：

  • O(1) 查找 key → 哈希表（HashMap）
  • O(1) 移动节点到最近使用位置 & 删除最久未使用节点 → 双向链表（Doubly Linked List）

哈希表负责 定位节点，双向链表负责 维护使用顺序。
新数据或最近访问的数据放在链表头，最久未使用的在链表尾。

代码实现

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
class LRUCache {

    private class Node {
        int key, value;
        Node prev, next;

        Node(int k, int val) {
            key = k;;
            value = val;
        }
    }
    
    private Map<Integer, Node> map;
    private int capacity;
    private Node head, tail;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        map = new HashMap<>();
        // 伪头尾节点，方便处理边界
        head = new Node(0, 0);
        tail = new Node(0, 0);
        head.next = tail;
        tail.prev = head;        
    }
    
    public int get(int key) {
        if (!map.containsKey(key)) {
            return -1;
        }

        Node node = map.get(key);
        moveToHead(node);
        return node.value;
    }
    
    public void put(int key, int value) {
        if (map.containsKey(key)) {
            Node node = map.get(key);
            node.value = value;
            moveToHead(node);
        } else {
            Node node = new Node(key, value);
            map.put(key, node);
            addToHead(node);
            if (map.size() > capacity) {
                Node removed = removeTail();
                map.remove(removed.key);
            }
        }
    }

    // 辅助方法：把节点加到头部
    private void addToHead(Node node) {
        node.prev = head;
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
    }

    // 辅助方法：移除节点
    private void removeNode(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    // 辅助方法：把节点移动到头部
    private void moveToHead(Node node) {
        removeNode(node);
        addToHead(node);
    }

    // 辅助方法：移除尾部节点
    private Node removeTail() {
        Node res = tail.prev;
        removeNode(res);
        return res;
    }
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */

复杂度分析

  • 时间复杂度：对于 put 和 get 都是 O(1)。
  • 空间复杂度：O(capacity)，因为哈希表和双向链表最多存储 capacity+1 个元素。

二叉树

94. 二叉树的中序遍历

给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。

示例 1：

img

1
2
输入：root = [1,null,2,3]
输出：[1,3,2]

示例 2：

1
2
输入：root = []
输出：[]

示例 3：

1
2
输入：root = [1]
输出：[1]

提示：

  • 树中节点数目在范围 [0, 100] 内
  • -100 <= Node.val <= 100

进阶: 递归算法很简单，你可以通过迭代算法完成吗？

方法一：递归

解题思路

略

代码实现

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        // 方法一：递归法
        List<Integer> res = new ArrayList<>();
        inorder(root, res);
        return res;
    }

    private void inorder(TreeNode node, List<Integer> res) {
        if (node == null) {
            return;
        }

        inorder(node.left, res);    // 左
        res.add(node.val);          // 根
        inorder(node.right, res);   // 右
    }
}

复杂度分析

时间复杂度：O(n)，其中 n 为二叉树节点的个数。二叉树的遍历中每个节点会被访问一次且只会被访问一次。

空间复杂度：O(n)。空间复杂度取决于递归的栈深度，而栈深度在二叉树为一条链的情况下会达到 O(n) 的级别。

方法二：迭代

解题思路

略

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode curr = root;

        while (curr != null || !stack.isEmpty()) {
            // 不断往左子树走，并压栈
            while (curr != null) {
                stack.push(curr);
                curr = curr.left;
            }

            // 弹出栈顶，访问节点
            curr = stack.pop();
            res.add(curr.val);
            // 转向右子树
            curr = curr.right;
        }

        return res;
    }
}

复杂度分析

时间复杂度：O(n)，其中 n 为二叉树节点的个数。二叉树的遍历中每个节点会被访问一次且只会被访问一次。

空间复杂度：O(n)。空间复杂度取决于栈深度，而栈深度在二叉树为一条链的情况下会达到 O(n) 的级别。

104. 二叉树的最大深度

给定一个二叉树 root ，返回其最大深度。

二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。

示例 1：

img

1
2
输入：root = [3,9,20,null,null,15,7]
输出：3

示例 2：

1
2
输入：root = [1,null,2]
输出：2

提示：

  • 树中节点的数量在 [0, 104] 区间内。
  • -100 <= Node.val <= 100

方法一：深度优先搜索

解题思路

如果树为空，深度为 0；

否则最大深度 = 1 + max(左子树深度, 右子树深度)。

代码实现

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }

        int left = maxDepth(root.left);
        int right = maxDepth(root.right);

        return Math.max(left, right) + 1;
    }
}

复杂度分析

时间复杂度：O(n)，其中 n 为二叉树节点的个数。每个节点在递归中只被遍历一次。

空间复杂度：O(h)，其中 h 表示二叉树的高度。递归函数需要栈空间，而栈空间取决于递归的深度，因此空间复杂度等价于二叉树的高度。

方法二：广度优先搜索

解题思路

用队列做层序遍历，每遍历一层，深度 +1。

代码实现

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
class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int depth = 0;

        while (!queue.isEmpty()) {
            // 遍历当前层所有节点
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                if (node.left != null) {
                    queue.offer(node.left);
                }

                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            depth++;  // 一层结束，深度 + 1
        }

        return depth;
    }
}

复杂度分析

时间复杂度：O(n)，其中 n 为二叉树的节点个数。与方法一同样的分析，每个节点只会被访问一次。

空间复杂度：此方法空间的消耗取决于队列存储的元素数量，其在最坏情况下会达到 O(n)。

226. 翻转二叉树

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

示例 1：

img

1
2
输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]

示例 2：

img

1
2
输入：root = [2,1,3]
输出：[2,3,1]

示例 3：

1
2
输入：root = []
输出：[]

提示：

  • 树中节点数目范围在 [0, 100] 内
  • -100 <= Node.val <= 100

方法一：递归

解题思路

递归的思路是：对于每个节点，交换其左右子树，然后递归地交换其左右子树。基准条件是如果节点为空，直接返回。

代码实现

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
/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode() {}
*     TreeNode(int val) { this.val = val; }
*     TreeNode(int val, TreeNode left, TreeNode right) {
*         this.val = val;
*         this.left = left;
*         this.right = right;
*     }
* }
*/
class Solution {
    public TreeNode invertTree(TreeNode root) {
        // 如果节点为空，则直接返回 null
        if (root == null) {
            return null;
        }

        // 交换左右子树
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;

        // 递归翻转左右子树
        invertTree(root.left);
        invertTree(root.right);

        return root;
    }
}

复杂度分析

时间复杂度：O(n)，其中 n 为二叉树节点的数目。我们会遍历二叉树中的每一个节点，对每个节点而言，我们在常数时间内交换其两棵子树。

空间复杂度：O(n)。使用的空间由递归栈的深度决定，它等于当前节点在二叉树中的高度。在平均情况下，二叉树的高度与节点个数为对数关系，即 O(log n)。而在最坏情况下，树形成链状，空间复杂度为 O(n)。

方法二：迭代

解题思路

迭代方法可以通过广度优先搜索（BFS）或深度优先搜索（DFS）来实现。这里我们使用队列来模拟广度优先搜索（BFS），逐层交换左右子树。

代码实现

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
class Solution {
    public TreeNode invertTree(TreeNode root) {
        // 如果节点为空，则直接返回 null
        if (root == null) {
            return null;
        }

        // 使用队列来进行广度优先遍历
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
            
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                // 交换左右子树
                TreeNode curr = queue.poll();
                TreeNode temp = curr.left;
                curr.left = curr.right;
                curr.right = temp;

                // 将子节点加入队列
                if (curr.left != null) {
                    queue.offer(curr.left);
                }

                if (curr.right != null) {
                    queue.offer(curr.right);
                }
            }
        }

        return root;
    }
}

复杂度分析

时间复杂度：O(n)，同「方法一」。
空间复杂度：这里需要用一个队列来维护节点，每个节点最多进队一次，出队一次，队列中最多不会超过 n 个点，故渐进空间复杂度为 O(n)。

101. 对称二叉树

给你一个二叉树的根节点 root ， 检查它是否轴对称。

示例 1：

img

1
2
输入：root = [1,2,2,3,4,4,3]
输出：true

示例 2：

img

1
2
输入：root = [1,2,2,null,3,null,3]
输出：false

提示：

  • 树中节点数目在范围 [1, 1000] 内
  • -100 <= Node.val <= 100

**进阶：**你可以运用递归和迭代两种方法解决这个问题吗？

方法一：递归

解题思路

我们可以定义一个辅助函数来比较两个子树是否对称。这个辅助函数接收两个节点作为参数，判断这两个节点是否镜像对称。

代码实现

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
37
38
39
40
41
42
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isSymmetric(TreeNode root) {
        // 如果根节点为空，是对称的
        if (root == null) {
            return true;
        }

        // 递归检查左右子树是否对称
        return isMirror(root.left, root.right);
    }

    // 检查两个树是否镜像对称
    private boolean isMirror(TreeNode t1, TreeNode t2) {
        // 如果两个节点都为空，是对称的
        if (t1 == null && t2 == null) {
            return true;
        }
        
        // 如果只有一个为空，或者值不同，不是对称的
        if (t1 == null || t2 == null || t1.val != t2.val) {
            return false;
        }

        // 递归检查左右子树是否对称
        return isMirror(t1.left, t2.right) && isMirror(t1.right, t2.left);
    }
}

复杂度分析

时间复杂度：这里遍历了这棵树，渐进时间复杂度为 O(n)。
空间复杂度：这里的空间复杂度和递归使用的栈空间有关，这里递归层数不超过 n，故渐进空间复杂度为 O(n)。

方法二：迭代

解题思路

迭代方法可以通过使用队列来实现广度优先搜索（BFS）模拟递归过程。我们逐层遍历树，检查左右子树是否对称。

代码实现

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
class Solution {
    public boolean isSymmetric(TreeNode root) {
        // 如果根节点为空，是对称的
        if (root == null) {
            return true;
        }

        // 使用队列模拟广度优先搜索
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root.left);
        queue.offer(root.right);

        while (!queue.isEmpty()) {
            TreeNode t1 = queue.poll();
            TreeNode t2 = queue.poll();

            // 如果两个节点都为空，继续检查下一个节点
            if (t1 == null && t2 == null) {
                continue;
            }

            // 如果只有一个节点为空，或者值不相等，不是对称的
            if (t1 == null || t2 == null || t1.val != t2.val) {
                return false;
            }

            // 将子节点按对称顺序加入队列
            queue.offer(t1.left);
            queue.offer(t2.right);
            queue.offer(t1.right);
            queue.offer(t2.left);
        }

        return true;
    }
}

复杂度分析

时间复杂度：O(n)，同「方法一」。
空间复杂度：这里需要用一个队列来维护节点，每个节点最多进队一次，出队一次，队列中最多不会超过 n 个点，故渐进空间复杂度为 O(n)。

543. 二叉树的直径

给你一棵二叉树的根节点，返回该树的 直径 。

二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。

两节点之间路径的 长度 由它们之间边数表示。

示例 1：

img

1
2
3
输入：root = [1,2,3,4,5]
输出：3
解释：3 ，取路径 [4,2,1,3] 或 [5,2,1,3] 的长度。

示例 2：

1
2
输入：root = [1,2]
输出：1

提示：

  • 树中节点数目在范围 [1, 104] 内
  • -100 <= Node.val <= 100

解题思路

为了计算二叉树的直径，我们可以通过深度优先搜索（DFS）来实现。对于每个节点，直径可能是通过该节点的路径，即左子树的深度加上右子树的深度。这个值可能是当前节点的直径。然后我们递归计算左右子树的直径，最终返回树的最大直径。

代码实现

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
37
38
39
40
41
42
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    int diameter = 0;  // 记录树的最大直径

    public int diameterOfBinaryTree(TreeNode root) {
        depth(root);    

        return diameter;
    }

    // 计算树的深度并更新
    private int depth(TreeNode node) {
        // 如果节点为空，深度为 0
        if (node == null) {
            return 0;
        }

        // 递归左右子树的深度
        int leftDepth = depth(node.left);
        int rightDepth = depth(node.right);

        // 更新直径
        diameter = Math.max(diameter, leftDepth + rightDepth);

        // 返回该节点的深度
        return Math.max(leftDepth, rightDepth) + 1;
    }
}

复杂度分析

时间复杂度：O(n)，其中 n 为二叉树的节点数，即遍历一棵二叉树的时间复杂度，每个结点只被访问一次。

空间复杂度：O(h)，其中 h 为二叉树的高度。由于递归函数在递归过程中需要为每一层递归函数分配栈空间，所以这里需要额外的空间且该空间取决于递归的深度，而递归的深度显然为二叉树的高度，并且每次递归调用的函数里又只用了常数个变量，所以所需空间复杂度为 O(h) 。

102. 二叉树的层序遍历

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。

示例 1：

img

1
2
输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]

示例 2：

1
2
输入：root = [1]
输出：[[1]]

示例 3：

1
2
输入：root = []
输出：[]

提示：

  • 树中节点数目在范围 [0, 2000] 内
  • -1000 <= Node.val <= 1000

解题思路

  • 使用队列：队列是 BFS 的核心数据结构，它可以帮助我们按照层级访问节点。
  • 遍历过程：
    1. 初始时将根节点加入队列。
    2. 从队列中取出节点并访问。
    3. 如果当前节点有左子节点或右子节点，将它们加入队列。
    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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) {
            return result;
        }

        // 创建一个队列来进行 BFS
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            int size = queue.size();  // 当前层的节点数
            List<Integer> currentLevel = new ArrayList<>();

            for (int i = 0; i < size; i++) {
                TreeNode currentNode = queue.poll();
                currentLevel.add(currentNode.val);

                // 把当前节点的左右子树加入到队列
                if (currentNode.left != null) {
                    queue.add(currentNode.left);
                }

                if (currentNode.right != null) {
                    queue.add(currentNode.right);
                }
            }

            result.add(currentLevel);  // 将当前层的节点值加入到结果
        }

        return result;
    }
}

复杂度分析

时间复杂度：每个点进队出队各一次，故渐进时间复杂度为 O(n)。

空间复杂度：队列中元素的个数不超过 n 个，故渐进空间复杂度为 O(n)。

108. 将有序数组转换为二叉搜索树

给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 平衡 二叉搜索树。

示例 1：

img

1
2
3
输入：nums = [-10,-3,0,5,9]
输出：[0,-3,9,-10,null,5]
解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案：

示例 2：

img

1
2
3
输入：nums = [1,3]
输出：[3,1]
解释：[1,null,3] 和 [3,1] 都是高度平衡二叉搜索树。

提示：

  • 1 <= nums.length <= 104
  • -104 <= nums[i] <= 104
  • nums 按 严格递增 顺序排列

解题思路

  1. 选择中位数作为根节点：因为数组是升序排列的，选择中位数作为根节点可以确保树的左右两部分尽可能平衡。
    • 如果数组的长度是奇数，选择中间元素。
    • 如果数组的长度是偶数，选择中间偏左的元素（例如，索引为 (start + end) / 2）。
  2. 递归构建：通过递归地对数组的左半部分和右半部分重复上述操作，依次构建出整个树。
  3. 终止条件：当数组为空时，返回 null，表示树的子树为空。

代码实现

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
37
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        return buildTree(nums, 0, nums.length - 1);
    }

    private TreeNode buildTree(int[] nums, int start, int end) {
        // 递归的终止条件
        if (start > end) {
            return null;
        }

        // 选择中位数作为根节点
        int mid = (start + end) / 2;
        TreeNode node = new TreeNode(nums[mid]);
        
        // 递归构建左子树和右子树
        node.left = buildTree(nums, start, mid - 1);
        node.right = buildTree(nums, mid + 1, end);

        return node;
    }
}

复杂度分析

时间复杂度：O(n)，其中 n 是数组的长度。每个节点都会被访问一次，并且每次都进行常数时间的操作（选择中位数和递归调用）。

空间复杂度：O(log n)，这是递归调用栈的最大深度。在最坏情况下（数组的长度为 n），递归的深度为 log(n)。

98. 验证二叉搜索树

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

有效 二叉搜索树定义如下：

  • 节点的左子树只包含 严格小于 当前节点的数。
  • 节点的右子树只包含 严格大于 当前节点的数。
  • 所有左子树和右子树自身必须也是二叉搜索树。

示例 1：

img

1
2
输入：root = [2,1,3]
输出：true

示例 2：

img

1
2
3
输入：root = [5,1,4,null,null,3,6]
输出：false
解释：根节点的值是 5 ，但是右子节点的值是 4 。

提示：

  • 树中节点数目范围在[1, 104] 内
  • -231 <= Node.val <= 231 - 1

解题思路

我们可以通过递归来检查每个节点是否满足二叉搜索树的性质。为了避免重复检查，我们可以将每个节点的值限定在一个合法的区间内。递归过程中，我们可以利用以下规则：

  • 对于当前节点，左子树的所有节点值必须在 (min, root.val) 区间内，右子树的所有节点值必须在 (root.val, max) 区间内。
  • 对于每一个节点，都需要检查其左子树和右子树是否满足这些条件。

代码实现

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
37
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isValidBST(TreeNode root) {
        // 初始时，允许最小值为负无穷，最大值为正无穷
        return isValidBSTHelper(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    // 辅助递归函数，检查根节点在 [min, max] 范围内
    private boolean isValidBSTHelper(TreeNode node, long min, long max) {
        // 如果当前节点为空，返回 true
        if (node == null) {
            return true;
        }

        // 如果当前值不在 [min, max] 范围内，返回 false
        if (node.val <= min || node.val >= max) {
            return false;
        }

        // 递归检查左右子树
        return isValidBSTHelper(node.left, min, node.val) && isValidBSTHelper(node.right, node.val, max);
    }
}

复杂度分析

时间复杂度：O(n)，其中 n 是二叉树的节点数。每个节点都被访问一次，且每次访问的操作是常数时间的。

空间复杂度：O(h)，其中 h 是二叉树的高度。最坏情况下（树是链表形式），空间复杂度为 O(n)；最好的情况下（树是平衡的），空间复杂度为 O(log n)，这与递归的栈深度有关。

230. 二叉搜索树中第 K 小的元素

给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 小的元素（从 1 开始计数）。

示例 1：

img

1
2
输入：root = [3,1,4,null,2], k = 1
输出：1

示例 2：

img

1
2
输入：root = [5,3,6,2,4,null,null,1], k = 3
输出：3

提示：

  • 树中的节点数为 n 。
  • 1 <= k <= n <= 104
  • 0 <= Node.val <= 104

**进阶：**如果二叉搜索树经常被修改（插入/删除操作）并且你需要频繁地查找第 k 小的值，你将如何优化算法？

解题思路

  1. 中序遍历：中序遍历二叉搜索树会按升序访问节点。因此，我们可以通过中序遍历来依次访问节点，直到找到第 k 个节点。
  2. 递归或迭代实现：我们可以使用递归或迭代的方式来实现中序遍历。每遍历一个节点，就减小 k，当 k 减到 0 时，当前节点就是我们要找的第 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
37
38
39
40
41
42
43
44
45
46
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    int count = 0;  // 用于记录已经遍历的节点数
    int result = 0;  // 用于存储第 k 小的值

    public int kthSmallest(TreeNode root, int k) {
        // 开始中序遍历
        inOrder(root, k);

        return result;
    }

    private void inOrder(TreeNode node, int k) {
        // 递归遍历子树
        if (node == null) {
            return;
        }

        // 访问左子树
        inOrder(node.left, k);

        // 访问当前节点
        count++;
        if (count == k) {
            result = node.val;  // 记录第 k 小的值
            return;  // 提前返回，避免继续遍历
        }

        // 访问右子树
        inOrder(node.right, k);
    }
}

复杂度分析

时间复杂度：O(n)，其中 n 是树的节点数。最坏情况下，我们需要遍历所有节点，直到找到第 k 小的元素。

空间复杂度：O(h)，其中 h 是二叉树的高度。由于递归栈的深度等于树的高度，在最坏情况下（树为链状），空间复杂度为 O(n)。

199. 二叉树的右视图

给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

示例 1：

**输入：**root = [1,2,3,null,5,null,4]

输出：[1,3,4]

解释：

img

示例 2：

**输入：**root = [1,2,3,4,null,null,null,5]

输出：[1,3,4,5]

解释：

img

示例 3：

**输入：**root = [1,null,3]

输出：[1,3]

示例 4：

**输入：**root = []

输出：[]

提示:

  • 二叉树的节点个数的范围是 [0,100]
  • -100 <= Node.val <= 100

解题思路

  1. 层次遍历：从树的最上面一层开始，逐层遍历树。我们可以使用 BFS 来实现这一点。
  2. 每层的最后一个节点：对于每一层，我们将所有节点放入队列中，并逐个访问。每当我们遍历完当前层时，队列中的最后一个节点就是当前层从右侧看到的节点。

代码实现

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) {
            return result;
        }

        // 队列用于 BFS
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            int size = queue.size();

            // 遍历当前层的所有节点
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();

                // 如果是当前层的最后一个节点，加入结果
                if (i == size - 1) {
                    result.add(node.val);
                }

                // 将左右子树加入到队列
                if (node.left != null) {
                    queue.offer(node.left);
                }

                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
        }

        return result;
    }
}

复杂度分析

时间复杂度 : O(n)。 每个节点最多进队列一次，出队列一次，因此广度优先搜索的复杂度为线性。

空间复杂度 : O(n)。每个节点最多进队列一次，所以队列长度最大不不超过 n，所以这里的空间代价为 O(n)。

114. 二叉树展开为链表

给你二叉树的根结点 root ，请你将它展开为一个单链表：

  • 展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
  • 展开后的单链表应该与二叉树 先序遍历 顺序相同。

示例 1：

img

1
2
输入：root = [1,2,5,3,4,null,6]
输出：[1,null,2,null,3,null,4,null,5,null,6]

示例 2：

1
2
输入：root = []
输出：[]

示例 3：

1
2
输入：root = [0]
输出：[0]

提示：

  • 树中结点数在范围 [0, 2000] 内
  • -100 <= Node.val <= 100

**进阶：**你可以使用原地算法（O(1) 额外空间）展开这棵树吗？

解题思路

  1. 递归方法：可以采用递归的方式来进行展开。我们可以先遍历根节点，然后递归地展开左子树和右子树，最终将树的每个子树与其兄弟节点串联起来。
  2. 原地展开：我们可以在递归过程中直接修改 root 的 left 和 right 指针，而不使用额外的空间（如栈或队列）。

代码实现

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
37
38
39
40
41
42
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public void flatten(TreeNode root) {
        if (root == null) {
            return;
        }

        // 递归展开左右子树
        flatten(root.left);
        flatten(root.right);

        // 保存右子树，准备连接
        TreeNode tempRight = root.right;

        // 将左子树变为右子树
        root.right = root.left;
        root.left = null;

        // 找到新的右子树的最后一个节点
        TreeNode curr = root;
        while (curr.right != null) {
            curr = curr.right;
        }

        // 将原来的右子树连接到最后一个节点的右侧
        curr.right = tempRight;
    }
}

复杂度分析

时间复杂度：O(n)，其中 n 是树的节点数。每个节点都被访问一次。

空间复杂度：O(h)，其中 h 是树的高度。递归栈的空间复杂度取决于树的深度，在最坏情况下为 O(n)（当树是线性的）。

105. 从前序与中序遍历序列构造二叉树

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

示例 1:

img

1
2
输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]

示例 2:

1
2
输入: preorder = [-1], inorder = [-1]
输出: [-1]

提示:

  • 1 <= preorder.length <= 3000
  • inorder.length == preorder.length
  • -3000 <= preorder[i], inorder[i] <= 3000
  • preorder 和 inorder 均 无重复 元素
  • inorder 均出现在 preorder
  • preorder 保证 为二叉树的前序遍历序列
  • inorder 保证 为二叉树的中序遍历序列

解题思路

  1. 前序遍历的第一个元素就是树的根节点。

  2. 在中序遍历中找到根节点的位置，将中序遍历分为左右两部分：

    • 左边部分是左子树的节点。

    • 右边部分是右子树的节点。

  3. 递归地构建左子树和右子树。

  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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return buildTreeHelper(preorder, inorder, 0, preorder.length - 1, 0, inorder.length - 1);
    }

    private TreeNode buildTreeHelper(int[] preorder, int[] inorder, int preStart, int preEnd, int inStart, int inEnd) {
        // 递归出口
        if (preStart > preEnd || inStart > inEnd) {
            return null;
        }

        // 根节点是 preorder 的第一个元素
        int rootVal = preorder[preStart];
        TreeNode root = new TreeNode(rootVal);

        // 找到根节点在 inorder 的位置
        int rootIndex = -1;
        for (int i = inStart; i <= inEnd; i++) {
            if (inorder[i] == rootVal) {
                rootIndex = i;
                break;
            }
        }

        // 计算左子树的大小
        int leftSize = rootIndex - inStart;

        // 递归构建左右子树
        root.left = buildTreeHelper(preorder, inorder, preStart + 1, preStart + leftSize, inStart, rootIndex - 1);
        root.right = buildTreeHelper(preorder, inorder, preStart + leftSize + 1, preEnd, rootIndex + 1, inEnd);

        return root;
    }
}

复杂度分析

时间复杂度：O(n)，其中 n 是树中的节点个数。

空间复杂度：O(n)，除去返回的答案需要的 O(n) 空间之外，我们还需要使用 O(n) 的空间存储哈希映射，以及 O(h)（其中 h 是树的高度）的空间表示递归时栈空间。这里 h<n，所以总空间复杂度为 O(n)。

437. 路径总和 III

给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。

路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

示例 1：

img

1
2
3
输入：root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
输出：3
解释：和等于 8 的路径有 3 条，如图所示。

示例 2：

1
2
输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出：3

提示:

  • 二叉树的节点个数的范围是 [0,1000]
  • -109 <= Node.val <= 109
  • -1000 <= targetSum <= 1000

解题思路

  1. 从根节点开始，递归遍历二叉树，遍历到每个节点时，检查以该节点为起点的路径和。
  2. 在递归过程中，如果当前路径和等于 targetSum，则记录该路径。
  3. 对每个节点，递归地计算从该节点向下的路径和，同时递归左右子树。

代码实现

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int pathSum(TreeNode root, int targetSum) {
        // 递归遍历二叉树
        return helper(root, (long) targetSum);
    }

    // 对每一个节点，从该节点出发，统计路径和为 targetSum 的路径数
    private int helper(TreeNode node, long targetSum) {
        if (node == null) {
            return 0;
        }

        // 计算从当前节点出发的路径中，路径和为 targetSum 的个数
        return countPaths(node, targetSum) + helper(node.left, targetSum) + helper(node.right, targetSum);
    }

    // 计算从当前节点出发，路径和为 targetSum 的路径数
    private int countPaths(TreeNode node, long targetSum) {
        if (node == null) {
            return 0;
        }

        // 当前节点的路径和
        int count = 0;
        if ((long) node.val == targetSum) {
            count = 1;
        }

        // 递归计算左右子树
        count += countPaths(node.left, targetSum - node.val);
        count += countPaths(node.right, targetSum - node.val);

        return count;
    }
}

复杂度分析

时间复杂度：O(n^2)，其中 n 为该二叉树节点的个数。对于每一个节点，求以该节点为起点的路径数目时，则需要遍历以该节点为根节点的子树的所有节点，因此求该路径所花费的最大时间为 O(n)，我们会对每个节点都求一次以该节点为起点的路径数目，因此时间复杂度为 O(n^2)。

空间复杂度：O(n)，考虑到递归需要在栈上开辟空间。

236. 二叉树的最近公共祖先

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

示例 1：

img

1
2
3
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出：3
解释：节点 5 和节点 1 的最近公共祖先是节点 3 。

示例 2：

img

1
2
3
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出：5
解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。

示例 3：

1
2
输入：root = [1,2], p = 1, q = 2
输出：1

提示：

  • 树中节点数目在范围 [2, 105] 内。
  • -109 <= Node.val <= 109
  • 所有 Node.val 互不相同 。
  • p != q
  • p 和 q 均存在于给定的二叉树中。

解题思路

这个题是经典的「最近公共祖先 LCA」问题，可以用递归轻松解决。核心思想是：

  • 如果当前节点是 null，说明没找到，返回 null。
  • 如果当前节点是 p 或 q，那么这个节点本身就是答案的一部分，直接返回它。
  • 否则就分别递归左右子树：
    • 如果左右子树都能找到（返回非空），说明 p 和 q 分别在左右两边，那么当前节点就是最近公共祖先；
    • 如果只有一边找到，说明 p 和 q 都在这一边，直接返回这一边；
    • 如果都没找到，返回 null。

代码实现

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return null;
        }

        // 如果当前节点是 p 或 q，当前节点是公共祖先
        if (root == p || root == q) {
            return root;
        }

        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);

        if (left != null && right != null) {
            // p 和 q 分别在左右子树，当前节点是公共祖先
            return root;
        }

        // 如果只有一边非空，返回非空的那一边
        return left == null ? right : left;
    }
}

复杂度分析

时间复杂度：O(n)，其中 n 是二叉树的节点数。二叉树的所有节点有且只会被访问一次，因此时间复杂度为 O(n)。

空间复杂度：O(n) ，其中 n 是二叉树的节点数。递归调用的栈深度取决于二叉树的高度，二叉树最坏情况下为一条链，此时高度为 n，因此空间复杂度为 O(n)。

图论

200. 岛屿数量

给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

示例 1：

1
2
3
4
5
6
7
输入：grid = [
  ['1','1','1','1','0'],
  ['1','1','0','1','0'],
  ['1','1','0','0','0'],
  ['0','0','0','0','0']
]
输出：1

示例 2：

1
2
3
4
5
6
7
输入：grid = [
  ['1','1','0','0','0'],
  ['1','1','0','0','0'],
  ['0','0','1','0','0'],
  ['0','0','0','1','1']
]
输出：3

提示：

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 300
  • grid[i][j] 的值为 '0' 或 '1'

解题思路

  • 遍历整个二维数组；
  • 当遇到 '1'（陆地）时，就从这里开始 DFS 或 BFS 把整块岛屿淹没（把相邻的 '1' 都变成 '0'）；
  • 每次淹没完成，说明找到了一座岛屿，计数器 count++；
  • 遍历完成后，count 就是岛屿数量。

代码实现

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
37
38
39
40
41
class Solution {
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }

        int m = grid.length;
        int n = grid[0].length;
        int count = 0;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1') {
                    count++;
                    dfs(grid, i, j);  // 把这一整块岛屿淹没
                }
            }
        }

        return count;
    }

    private void dfs(char[][] grid, int i, int j) {
        int m = grid.length;
        int n = grid[0].length;

        // 越界 or 水，直接返回
        if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] == '0') {
            return;
        }

        // 标记为已访问（淹没）
        grid[i][j] = '0';

        // 递归访问上下左右
        dfs(grid, i + 1, j);
        dfs(grid, i - 1, j);
        dfs(grid, i, j + 1);
        dfs(grid, i, j - 1);
    }
}

复杂度分析

时间复杂度：O(m * n)，其中 m 和 n 分别为行数和列数。

空间复杂度：O(m * n)，在最坏情况下，整个网格均为陆地，深度优先搜索的深度达到 m * n。

994. 腐烂的橘子

在给定的 m x n 网格 grid 中，每个单元格可以有以下三个值之一：

  • 值 0 代表空单元格；
  • 值 1 代表新鲜橘子；
  • 值 2 代表腐烂的橘子。

每分钟，腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。

返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1 。

示例 1：

img

1
2
输入：grid = [[2,1,1],[1,1,0],[0,1,1]]
输出：4

示例 2：

1
2
3
输入：grid = [[2,1,1],[0,1,1],[1,0,1]]
输出：-1
解释：左下角的橘子（第 2 行， 第 0 列）永远不会腐烂，因为腐烂只会发生在 4 个方向上。

示例 3：

1
2
3
输入：grid = [[0,2]]
输出：0
解释：因为 0 分钟时已经没有新鲜橘子了，所以答案就是 0 。

提示：

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 10
  • grid[i][j] 仅为 0、1 或 2

解题思路

遍历整个 grid：

  • 把所有腐烂的橘子（值为 2）放进队列，作为 BFS 的起始点；
  • 统计新鲜橘子的数量。

从队列中一层一层地扩散（每一层扩散代表一分钟），将相邻的新鲜橘子变为腐烂，并入队。

BFS 结束后：

  • 如果没有剩下新鲜橘子，返回扩散的分钟数；
  • 如果还有新鲜橘子没被腐烂，返回 -1。

代码实现

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
37
38
39
40
41
42
43
44
45
46
47
48
49
class Solution {
    public int orangesRotting(int[][] grid) {
        Queue<int[]> queue = new LinkedList<>();
        int m = grid.length;
        int n = grid[0].length;
        int fresh = 0;

        // 1. 初始化，记录所有烂橘子的位置 & 统计新鲜橘子数量
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 2) {
                    queue.offer(new int[] {i, j});
                } else if (grid[i][j] == 1) {
                    fresh++;
                }
            }
        }

        // 如果一开始就没有新鲜橘子，直接返回 0
        if (fresh == 0) {
            return 0;
        }

        int minutes = -1;
        int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

        // 2. BFS 扩散
        while (!queue.isEmpty()) {
            int size = queue.size();
            minutes++;
            for (int k = 0; k < size; k++) {
                int[] curr = queue.poll();
                for (int[] d : dirs) {
                    int ni = curr[0] + d[0];
                    int nj = curr[1] + d[1];
                    
                    if (ni >= 0 && ni < m && nj >= 0 && nj < n && grid[ni][nj] == 1) {
                        grid[ni][nj] = 2;  // 新鲜橘子腐烂
                        fresh--;
                        queue.offer(new int[] {ni, nj});
                    }
                }
            }
        }

        // 3. 检查是否还有新鲜橘子
        return fresh == 0 ? minutes : -1;
    }
}

复杂度分析

时间复杂度：O(m * n)。即进行一次广度优先搜索的时间，其中 m,n 分别为 grid 的行数与列数。

空间复杂度：O(m * n)。需要额外的 dis 数组记录每个新鲜橘子被腐烂的最短时间，大小为 O(nm)，且广度优先搜索中队列里存放的状态最多不会超过 m * n 个，最多需要 O(m * n) 的空间，所以最后的空间复杂度为 O(m * n)。

207. 课程表

你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。

在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程 bi 。

  • 例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。

请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。

示例 1：

1
2
3
输入：numCourses = 2, prerequisites = [[1,0]]
输出：true
解释：总共有 2 门课程。学习课程 1 之前，你需要完成课程 0 。这是可能的。

示例 2：

1
2
3
输入：numCourses = 2, prerequisites = [[1,0],[0,1]]
输出：false
解释：总共有 2 门课程。学习课程 1 之前，你需要先完成课程 0 ；并且学习课程 0 之前，你还应先完成课程 1 。这是不可能的。

提示：

  • 1 <= numCourses <= 2000
  • 0 <= prerequisites.length <= 5000
  • prerequisites[i].length == 2
  • 0 <= ai, bi < numCourses
  • prerequisites[i] 中的所有课程对 互不相同

解题思路

BFS, Kahn 算法：

  • 用入度数组统计每门课程的依赖数；
  • 将入度为 0 的课程加入队列；
  • 每次出队一门课，就把它指向的课程的入度减一，如果某课程入度为 0，就入队；
  • 如果最终出队的课程数等于总课程数，则说明能完成。

代码实现

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
37
38
39
class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        // 建图
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) {
            graph.add(new ArrayList<>());
        }
        
        int[] indegree = new int[numCourses];
        // prerequisites[i] = [a, b]，表示 b -> a
        for (int[] p : prerequisites) {
            graph.get(p[1]).add(p[0]);
            indegree[p[0]]++;
        }

        // 将入度为 0 的课程加入到队列
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (indegree[i] == 0) {
                queue.offer(i);
            }
        }

        int count = 0;  // 统计能学完的课程数
        while (!queue.isEmpty()) {
            int course = queue.poll();
            count++;

            for (int i : graph.get(course)) {
                indegree[i]--;
                if (indegree[i] == 0) {
                    queue.offer(i);
                }
            }
        }

        return count == numCourses;
    }
}

复杂度分析

时间复杂度: O(n+m)，其中 n 为课程数，m 为先修课程的要求数。这其实就是对图进行广度优先搜索的时间复杂度。

空间复杂度: O(n+m)。题目中是以列表形式给出的先修课程关系，为了对图进行广度优先搜索，我们需要存储成邻接表的形式，空间复杂度为 O(n+m)。在广度优先搜索的过程中，我们需要最多 O(n) 的队列空间（迭代）进行广度优先搜索。因此总空间复杂度为 O(n+m)。

208. 实现 Trie (前缀树)

Trie（发音类似 “try”）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补全和拼写检查。

请你实现 Trie 类：

  • Trie() 初始化前缀树对象。
  • void insert(String word) 向前缀树中插入字符串 word 。
  • boolean search(String word) 如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false 。
  • boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ，返回 true ；否则，返回 false 。

示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
输入
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
输出
[null, null, true, false, true, null, true]

解释
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple");   // 返回 True
trie.search("app");     // 返回 False
trie.startsWith("app"); // 返回 True
trie.insert("app");
trie.search("app");     // 返回 True

提示：

  • 1 <= word.length, prefix.length <= 2000
  • word 和 prefix 仅由小写英文字母组成
  • insert、search 和 startsWith 调用次数 总计 不超过 3 * 104 次

解题思路

每个节点要保存 26 个子节点指针（对应 a-z），也可以用 Map<Character, TrieNode>。

每个节点要有一个标志，表示“是否是某个完整单词的结尾”。

插入时逐字符往下建，搜索时逐字符往下走。

代码实现

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
class Trie {

    // 定义节点
    class TrieNode {
        TrieNode[] children;  // 存 26 个节点
        boolean isEnd;        // 标记是否为某个单词结尾

        TrieNode() {
            children = new TrieNode[26];
            isEnd = false;
        }
    }

    private TrieNode root;

    public Trie() {
        root = new TrieNode();  // 初始化根节点
    }
    
    public void insert(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            int i = c - 'a';  // 计算子节点索引
            if (node.children[i] == null) {
                node.children[i] = new TrieNode();
            }
            
            node = node.children[i];
        }

        node.isEnd = true;  // 单词结束位置打标
    }
    
    public boolean search(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            int i = c - 'a';
            if (node.children[i] == null) {
                return false;  // 没路了
            }

            node = node.children[i];
        }

        return node.isEnd;  // 必须到结尾且 isEnd = true
    }
    
    public boolean startsWith(String prefix) {
        TrieNode node = root;
        for (char c : prefix.toCharArray()) {
            int i = c - 'a';
            if (node.children[i] == null) {
                return false;
            }

            node = node.children[i];
        }

        return true;  // 只要路径存在即可
    }
}

/**
 * Your Trie object will be instantiated and called as such:
 * Trie obj = new Trie();
 * obj.insert(word);
 * boolean param_2 = obj.search(word);
 * boolean param_3 = obj.startsWith(prefix);
 */

复杂度分析

时间复杂度：初始化为 O(1)，其余操作为 O(∣S∣)，其中 ∣S∣ 是每次插入或查询的字符串的长度。

空间复杂度：O(∣T∣⋅Σ)，其中 ∣T∣ 为所有插入字符串的长度之和，Σ 为字符集的大小，本题 Σ=26。

回溯

46. 全排列

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

示例 1：

1
2
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

示例 2：

1
2
输入：nums = [0,1]
输出：[[0,1],[1,0]]

示例 3：

1
2
输入：nums = [1]
输出：[[1]]

提示：

  • 1 <= nums.length <= 6
  • -10 <= nums[i] <= 10
  • nums 中的所有整数 互不相同

解题思路

使用一个 List<Integer> 保存当前路径（即正在构造的排列）。

用一个 boolean[] used 数组标记 nums[i] 是否已经被选择。

如果路径长度等于 nums.length，就把它加入答案。

否则枚举所有数字，把没用过的数字加入，递归下去，再回溯（撤销选择）。

代码实现

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
class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        boolean[] used = new boolean[nums.length];
        backtrack(nums, new ArrayList<>(), used, result);
        return result;
    }

    private void backtrack(int[] nums, List<Integer> path, boolean[] used, List<List<Integer>> result) {
        if (path.size() == nums.length) {
            result.add(new ArrayList<>(path));  // 找到一个序列
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            if (used[i]) {
                continue;  // 已经用过，跳过
            }

            // 选择 nums[i]
            used[i] = true;
            path.add(nums[i]);

            backtrack(nums, path, used, result);

            // 撤销选择
            used[i] = false;
            path.remove(path.size() - 1);
        }
    }
}

复杂度分析

时间复杂度：O(n × n!)，其中 n 为序列的长度。

空间复杂度：O(n)，其中 n 为序列的长度。除答案数组以外，递归函数在递归过程中需要为每一层递归函数分配栈空间，所以这里需要额外的空间且该空间取决于递归的深度，这里可知递归调用深度为 O(n)。

78. 子集

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

示例 1：

1
2
输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

示例 2：

1
2
输入：nums = [0]
输出：[[],[0]]

提示：

  • 1 <= nums.length <= 10
  • -10 <= nums[i] <= 10
  • nums 中的所有元素 互不相同

解题思路

每个元素都有 选 或 不选 两种可能。

用回溯（DFS）保证不会生成重复子集。

一开始就把当前 path 加入结果，所以会自然包含 []（空集）。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack(nums, 0, new ArrayList<>(), result);
        return result;
    }

    private void backtrack(int[] nums, int start, List<Integer> path, List<List<Integer>> result) {
        result.add(new ArrayList<>(path));

        for (int i = start; i < nums.length; i++) {
            path.add(nums[i]);                     // 选择
            backtrack(nums, i + 1, path, result);  // 进入下一层
            path.remove(path.size() - 1);          // 撤销选择
        }
    }
}

复杂度分析

时间复杂度：O(n · 2^n)，其中 n 为数组长度。每个元素都有选或不选两种情况，因此一共会生成 2^n 个子集；而在构造每个子集时需要 O(n) 的时间进行拷贝。

空间复杂度：O(n)，递归调用过程中使用的栈空间与当前路径存储所需的空间，最多为 O(n)。输出结果本身不计入额外空间复杂度。

17. 电话号码的字母组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

img

示例 1：

1
2
输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

示例 2：

1
2
输入：digits = ""
输出：[]

示例 3：

1
2
输入：digits = "2"
输出：["a","b","c"]

提示：

  • 0 <= digits.length <= 4
  • digits[i] 是范围 ['2', '9'] 的一个数字。

解题思路

先用一个数组或 Map<Character, String> 建立映射

回溯递归

  • 从字符串的第 index 个数字开始，取出它对应的所有字母；
  • 把每个字母加入当前组合 path；
  • 然后递归处理下一个数字；
  • 当路径长度等于 digits.length 时，说明形成了一个完整的组合，加入结果。

如果输入 digits 为空字符串，直接返回空列表。

代码实现

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
37
38
39
class Solution {
    private static final String[] MAPPING = {
        "",     // 0
        "",     // 1
        "abc",  // 2
        "def",  // 3
        "ghi",  // 4
        "jkl",  // 5
        "mno",  // 6
        "pqrs", // 7
        "tuv",  // 8
        "wxyz"  // 9
    };

    public List<String> letterCombinations(String digits) {
        List<String> result = new ArrayList<>();
        if (digits == null || digits.length() == 0) {
            return result;
        }

        backtrack(digits, 0, new StringBuilder(), result);

        return result;
    }

    private void backtrack(String digits, int index, StringBuilder path, List<String> result) {
        if (index == digits.length()) {
            result.add(path.toString());
            return;
        }

        String letters = MAPPING[digits.charAt(index) - '0'];
        for (char c : letters.toCharArray()) {
            path.append(c);                             // 选择一个字母
            backtrack(digits, index + 1, path, result); // 递归处理下一个数字
            path.deleteCharAt(path.length() - 1);       // 撤销选择
        }
    }
}

复杂度分析

时间复杂度：O(3^m * 4^n)，其中 m 是输入中对应 3 个字母的数字个数（包括数字 2、3、4、5、6、8），n 是输入中对应 4 个字母的数字个数（包括数字 7、9），m+n 是输入数字的总个数。当输入包含 m 个对应 3 个字母的数字和 n 个对应 4 个字母的数字时，不同的字母组合一共有 3^m * 4^n 种，需要遍历每一种字母组合。

空间复杂度：O(m+n)，其中 m 是输入中对应 3 个字母的数字个数，n 是输入中对应 4 个字母的数字个数，m+n 是输入数字的总个数。除了返回值以外，空间复杂度主要取决于哈希表以及回溯过程中的递归调用层数，哈希表的大小与输入无关，可以看成常数，递归调用层数最大为 m+n。

39. 组合总和

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。

对于给定的输入，保证和为 target 的不同组合数少于 150 个。

示例 1：

1
2
3
4
5
6
输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。

示例 2：

1
2
输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]

示例 3：

1
2
输入: candidates = [2], target = 1
输出: []

提示：

  • 1 <= candidates.length <= 30
  • 2 <= candidates[i] <= 40
  • candidates 的所有元素 互不相同
  • 1 <= target <= 40

解题思路

用 回溯，在搜索过程中不断累加当前和 sum，直到：

  • 如果 sum == target → 收集结果。
  • 如果 sum > target → 直接返回（剪枝）。

用一个 start 参数控制搜索范围，保证组合里数字的顺序不会乱（避免重复解）。

  • 例如 [2,3] 和 [3,2] 其实是一样的，所以搜索的时候规定只能往后选。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack(candidates, target, 0, 0, new ArrayList<>(), result);
        
        return result;
    }

    private void backtrack(int[] candidates, int target, int start, int sum, List<Integer> path, List<List<Integer>> result) {
        if (sum == target) {
            result.add(new ArrayList<>(path));  // 找到组合
        }

        if (sum > target) {
            return;  // 剪枝：超过目标值，直接返回
        }

        for (int i = start; i < candidates.length; i++) {
            path.add(candidates[i]);  // 选择当前数 
            backtrack(candidates, target, i, sum + candidates[i], path, result);  // 递归时 i 不变，因为可以重复选择同一个数
            path.remove(path.size() - 1);  // 撤销选择
        }
    }
}

复杂度分析

时间复杂度：O(S)，其中 S 为所有可行解的长度之和。从分析给出的搜索树我们可以看出时间复杂度取决于搜索树所有叶子节点的深度之和，即所有可行解的长度之和。在这题中，我们很难给出一个比较紧的上界，我们知道 O(n * 2^n) 是一个比较松的上界，即在这份代码中，n 个位置每次考虑选或者不选，如果符合条件，就加入答案的时间代价。但是实际运行的时候，因为不可能所有的解都满足条件，递归的时候我们还会用 target−candidates[idx]≥0 进行剪枝，所以实际运行情况是远远小于这个上界的。

空间复杂度：O(target)。除答案数组外，空间复杂度取决于递归的栈深度，在最差情况下需要递归 O(target) 层。

22. 括号生成

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

示例 1：

1
2
输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]

示例 2：

1
2
输入：n = 1
输出：["()"]

提示：

  • 1 <= n <= 8

解题思路

有效括号的组合要求：

  • 左括号 ( 必须在右括号 ) 之前出现。
  • 不能有不匹配的右括号（即右括号不能超过左括号）。

递归过程：

  • 我们一开始有 n 对括号可以使用。
  • 递归时，我们尝试添加左括号 ( 和右括号 )，每次递归的时候需要确保：
    • 左括号数量不超过 n。
    • 右括号数量不超过左括号数量。

回溯的终止条件：

  • 当左括号和右括号的数量都达到了 n 时，说明当前组合是一个有效的括号组合。

代码实现

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
class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<>();
        backtrack(n, "", 0, 0, result);

        return result;
    }

    private void backtrack(int n, String current, int open, int close, List<String> result) {
        if (open == n && close == n) {
            result.add(current);
            return;
        }

        // 左括号在右括号之前，左括号数不超过 n
        if (open < n) {
            backtrack(n, current + "(", open + 1, close, result);
        }

        // 右括号数不超过左括号数
        if (close < open) {
            backtrack(n, current + ")", open, close + 1, result);
        }
    }
}

复杂度分析

时间复杂度：O(4^n / sqrt(n))，在回溯过程中，每个答案需要 O(n) 的时间复制到答案数组中。

空间复杂度：O(n)，除了答案数组之外，我们所需要的空间取决于递归栈的深度，每一层递归函数需要 O(1) 的空间，最多递归 2n 层，因此空间复杂度为 O(n)。

79. 单词搜索

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

示例 1：

img

1
2
输入：board = [['A','B','C','E'],['S','F','C','S'],['A','D','E','E']], word = "ABCCED"
输出：true

示例 2：

img

1
2
输入：board = [['A','B','C','E'],['S','F','C','S'],['A','D','E','E']], word = "SEE"
输出：true

示例 3：

img

1
2
输入：board = [['A','B','C','E'],['S','F','C','S'],['A','D','E','E']], word = "ABCB"
输出：false

提示：

  • m == board.length
  • n = board[i].length
  • 1 <= m, n <= 6
  • 1 <= word.length <= 15
  • board 和 word 仅由大小写英文字母组成

**进阶：**你可以使用搜索剪枝的技术来优化解决方案，使其在 board 更大的情况下可以更快解决问题？

解题思路

从每个单元格开始：遍历整个 board，从每个位置开始进行搜索。

深度优先搜索：每次移动到相邻的单元格，检查该位置的字符是否匹配目标字符，并继续递归搜索下一个字符。

回溯：如果当前路径无法找到目标单词，则回溯并尝试其他路径。

剪枝：每个单元格只能被使用一次，因此每次进入递归时，需要将当前位置标记为已访问，退出时恢复状态。

代码实现

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
37
38
39
40
41
42
43
44
45
class Solution {
    public boolean exist(char[][] board, String word) {
        int m = board.length;
        int n = board[0].length;

        if (board == null || m == 0 || n == 0 || word == null || word.length() == 0) {
            return false;
        }

        // 遍历每个位置作为起点
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (dfs(board, word, i, j, 0)) {
                    return true;
                }
            }
        }

        return false;
    }

    private boolean dfs(char[][] board, String word, int i, int j, int currLength) {
        // 如果当前长度等于 word 长度，说明已经匹配成功
        if (currLength == word.length()) {
            return true;
        }

        // 边界条件：越界 or 不等于目标字段
        if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || board[i][j] != word.charAt(currLength)) {
            return false;
        }

        // 保留当前字符，标记为已访问
        char temp = board[i][j];
        board[i][j] = '#';

        // 尝试从四个方向 dfs
        boolean isFound = dfs(board, word, i + 1, j, currLength + 1) || dfs(board, word, i - 1, j, currLength + 1) || dfs(board, word, i, j + 1, currLength + 1) || dfs(board, word, i, j - 1, currLength + 1);

        // 回溯
        board[i][j] = temp;

        return isFound;
    }
}

复杂度分析

时间复杂度：最坏情况下，我们要遍历每个单元格，进行一次深度优先搜索。递归的深度为单词 word 的长度，假设为 L，每个位置可以有 4 个方向，最坏情况下时间复杂度是 O(m * n * 4^L)，其中 m 和 n 分别是 board 的行数和列数。

空间复杂度：空间复杂度主要来自递归栈的深度，最坏情况下递归深度为 L，因此空间复杂度是 O(L)。

131. 分割回文串

给你一个字符串 s，请你将 s 分割成一些 子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。

示例 1：

1
2
输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]

示例 2：

1
2
输入：s = "a"
输出：[["a"]]

提示：

  • 1 <= s.length <= 16
  • s 仅由小写英文字母组成

解题思路

回溯：我们从字符串的开头开始，每次选择一个可能的切割点，将字符串分割成多个部分，递归处理剩下的部分。

回文检查：在每次选择分割点时，我们需要判断当前子串是否是回文。如果是回文，就继续进行分割，否则跳过这个分割点。

终止条件：当字符串完全被分割成回文子串时，记录当前的分割方案。回溯回去继续尝试其他分割。

回溯算法步骤：

  1. 从字符串的开头开始，尝试每一个可能的子串。
  2. 判断当前子串是否为回文。如果是回文，则继续递归地处理剩下的部分。
  3. 每当找到一种合法的分割方案，就将其加入结果集。
  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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class Solution {
    public List<List<String>> partition(String s) {
        List<List<String>> result = new ArrayList<>();
        List<String> currentPartition = new ArrayList<>();
        backtrack(s, 0, currentPartition, result);

        return result;
    }

    private void backtrack(String s, int start, List<String> currentPartition, List<List<String>> result) {
        // 如果已经遍历到字符串的末尾，记录当前分割方案
        if (start == s.length()) {
            result.add(new ArrayList<>(currentPartition));
            return;
        }

        // 从当前位置开始，尝试每个可能的子串
        for (int end = start + 1; end <= s.length(); end++) {
            String substring = s.substring(start, end);
            // 如果当前子串是回文，则继续递归
            if (isPalindrome(substring)) {
                currentPartition.add(substring);
                // 递归处理后续部分
                backtrack(s, end, currentPartition, result);
                // 回溯，移出最后一个子串
                currentPartition.remove(currentPartition.size() - 1);
            }
        }
    }

    // 判断一个字符串是否是回文
    private boolean isPalindrome(String s) {
        int left = 0;
        int right = s.length() - 1;
        while (left < right) {
            if (s.charAt(left) != s.charAt(right)) {
                return false;
            }

            left++;
            right--;
        }

        return true;
    }
}

复杂度分析

时间复杂度：对于每一个起始位置，我们可能会检查多个子串，因此总的时间复杂度是 O(2^n * n)，其中 2^n 是最坏情况下的回溯树的大小，n 是每次回文检查的时间。

空间复杂度：递归深度最多为 n，所以空间复杂度为 O(n)。

二分查找

35. 搜索插入位置

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。

示例 1:

1
2
输入: nums = [1,3,5,6], target = 5
输出: 2

示例 2:

1
2
输入: nums = [1,3,5,6], target = 2
输出: 1

示例 3:

1
2
输入: nums = [1,3,5,6], target = 7
输出: 4

提示:

  • 1 <= nums.length <= 104
  • -104 <= nums[i] <= 104
  • nums 为 无重复元素 的 升序 排列数组
  • -104 <= target <= 104

解题思路

初始化：我们需要设置两个指针：left 和 right，分别表示当前搜索范围的起始和结束位置。最开始时，left = 0，right = nums.length - 1。

查找目标：通过二分查找不断缩小搜索范围：

  • 计算中间位置 mid = left + (right - left) / 2。
  • 比较 nums[mid] 与 target：
    • 如果 nums[mid] == target，说明找到了目标值，直接返回 mid。
    • 如果 nums[mid] < target，说明目标值在右半部分，更新 left = mid + 1。
    • 如果 nums[mid] > target，说明目标值在左半部分，更新 right = mid - 1。

插入位置：如果在搜索过程中没有找到目标值，最终 left 就是目标值应该插入的位置。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int searchInsert(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;

        // 使用二分查找
        while (left <= right) {
            int mid = left + (right - left) / 2;  // 防止 overflow
            if (nums[mid] == target) {
                return mid;  // 找到目标值，返回索引
            } else if (nums[mid] < target) {
                left = mid + 1;  // 目标值在右半部分
            } else {
                right = mid - 1;  // 目标值在左半部分
            }
        }

        // 如果没有目标值，left 是目标值插入的位置
        return left;
    }
}

复杂度分析

  • 时间复杂度：O(log n)，其中 n 为数组的长度。二分查找所需的时间复杂度为 O(log n)。
  • 空间复杂度：O(1)。我们只需要常数空间存放若干变量。

74. 搜索二维矩阵

给你一个满足下述两条属性的 m x n 整数矩阵：

  • 每行中的整数从左到右按非严格递增顺序排列。
  • 每行的第一个整数大于前一行的最后一个整数。

给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false 。

示例 1：

img

1
2
输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
输出：true

示例 2：

img

1
2
输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
输出：false

提示：

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= m, n <= 100
  • -104 <= matrix[i][j], target <= 104

解题思路

由于矩阵满足特定的排列条件，我们可以使用一种 二分查找 的方法来优化搜索，达到 O(log(m * n)) 的时间复杂度。

我们可以将这个问题看作是在一个 一维有序数组 中查找目标值。具体的做法如下：

  1. 将二维矩阵看作一个一维的排序数组。例如，第 i 行第 j 列的元素可以通过 matrix[i][j] 来访问。在一维数组的角度上，可以用公式 index = i * n + j 来进行转换，其中 n 是每行的列数。
  2. 使用二分查找在矩阵中查找目标值。我们首先设定一个 left 指针指向数组的第一个元素，right 指针指向数组的最后一个元素。通过不断缩小搜索范围，直到找到目标值或者确定目标值不存在。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length;
        int n = matrix[0].length;
        int left = 0;
        int right = m * n - 1;

        // 使用二分查找
        while (left <= right) {
            int mid = left + (right - left) / 2;  // 防止 overflow
            // mid = i * n + j
            int midValue = matrix[mid / n][mid % n];
            if (midValue == target) {
                return true;  // 找到目标值
            } else if (midValue < target) {
                left = mid + 1;  // 目标值在右半部分
            } else {
                right = mid - 1;  // 目标值在左半部分
            }
        }

        return false;
    }
}

复杂度分析

  • 时间复杂度：O(log m * n)，其中 m 和 n 分别是矩阵的行数和列数。
  • 空间复杂度：O(1)。

34. 在排序数组中查找元素的第一个和最后一个位置

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

示例 1：

1
2
输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]

示例 2：

1
2
输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]

示例 3：

1
2
输入：nums = [], target = 0
输出：[-1,-1]

提示：

  • 0 <= nums.length <= 105
  • -109 <= nums[i] <= 109
  • nums 是一个非递减数组
  • -109 <= target <= 109

解题思路

二分查找：由于数组是有序的，我们可以使用二分查找来找到目标值的 开始位置 和 结束位置。首先，我们可以使用二分查找找到目标值的任意一个位置，然后从该位置向两边扩展，找到目标值的最左和最右位置。

步骤：

  • 首先，我们使用二分查找找到 target 的任意一个出现位置。
  • 然后，在找到的位置基础上，分别进行二分查找：
    • 向左查找，直到找到最左边的 target 位置。
    • 向右查找，直到找到最右边的 target 位置。
  • 如果数组中没有目标值 target，则返回 [-1, -1]。

代码实现

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
class Solution {
    public int[] searchRange(int[] nums, int target) {
        int[] result = new int[2];
        result[0] = findLeft(nums, target);  // 找到最左边的位置
        result[1] = findRight(nums, target);  // 找到最右边的位置

        return result;
    }

    // 二分查找找到最左边的位置
    private int findLeft(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        int leftIndex = -1;  // 默认找不到，返回 -1

        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                leftIndex = mid;
                right = mid - 1;  // 继续在左边寻找
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return leftIndex;
    }

    // 二分查找找到最右边的位置
    private int findRight(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        int rightIndex = -1;  // 默认找不到，返回 -1

        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                rightIndex = mid;
                left = mid + 1;  // 继续在右边寻找
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return rightIndex;
    }
}

复杂度分析

时间复杂度： O(log n) ，其中 n 为数组的长度。二分查找的时间复杂度为 O(log n)，一共会执行两次，因此总时间复杂度为 O(log n)。

空间复杂度：O(1) 。只需要常数空间存放若干变量。

33. 搜索旋转排序数组

整数数组 nums 按升序排列，数组中的值 互不相同 。

在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 向左旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 下标 3 上向左旋转后可能变为 [4,5,6,7,0,1,2] 。

给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

示例 1：

1
2
输入：nums = [4,5,6,7,0,1,2], target = 0
输出：4

示例 2：

1
2
输入：nums = [4,5,6,7,0,1,2], target = 3
输出：-1

示例 3：

1
2
输入：nums = [1], target = 0
输出：-1

提示：

  • 1 <= nums.length <= 5000
  • -104 <= nums[i] <= 104
  • nums 中的每个值都 独一无二
  • 题目数据保证 nums 在预先未知的某个下标上进行了旋转
  • -104 <= target <= 104

解题思路

首先，我们知道数组的两部分是有序的：一部分是从旋转点开始的升序部分，另一部分是从旋转点之前的部分。

在每次二分查找的过程中，我们需要判断当前的中间值 mid 与目标值 target 的关系，以及确定旋转点位置，然后确定在哪一部分继续查找。

代码实现

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
class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            
            // 如果找到目标，直接返回
            if (nums[mid] == target) {
                return mid;
            }

            if (nums[left] <= nums[mid]) {  // 左半部分有序
                if (target >= nums[left] && target < nums[mid]) {  // 目标在左半部分
                    right = mid - 1;
                } else {  // 目标在右半部分
                    left = mid + 1;
                }
            } else {  // 右半部分有序
                if (target <= nums[right] && target > nums[mid]) {  // 目标在右半部分
                    left = mid + 1;
                } else {  // 目标在左半部分
                    right = mid - 1;
                }
            }
        }

        return -1;
    }
}

复杂度分析

时间复杂度： O(log n)，其中 n 为 nums 数组的大小。整个算法时间复杂度即为二分查找的时间复杂度 O(log n)。

空间复杂度： O(1) 。我们只需要常数级别的空间存放变量。

153. 寻找旋转排序数组中的最小值

已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：

  • 若旋转 4 次，则可以得到 [4,5,6,7,0,1,2]
  • 若旋转 7 次，则可以得到 [0,1,2,4,5,6,7]

注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。

给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

示例 1：

1
2
3
输入：nums = [3,4,5,1,2]
输出：1
解释：原数组为 [1,2,3,4,5] ，旋转 3 次得到输入数组。

示例 2：

1
2
3
输入：nums = [4,5,6,7,0,1,2]
输出：0
解释：原数组为 [0,1,2,4,5,6,7] ，旋转 4 次得到输入数组。

示例 3：

1
2
3
输入：nums = [11,13,15,17]
输出：11
解释：原数组为 [11,13,15,17] ，旋转 4 次得到输入数组。

提示：

  • n == nums.length
  • 1 <= n <= 5000
  • -5000 <= nums[i] <= 5000
  • nums 中的所有整数 互不相同
  • nums 原来是一个升序排序的数组，并进行了 1 至 n 次旋转

解题思路

我们可以利用 二分查找 来缩小搜索范围。

每次比较中间元素 mid 和边界元素 nums[left] 以及 nums[right]，可以通过以下方式来决定移动哪一半：

  1. 如果 nums[mid] >= nums[left]，说明左半部分是升序的，最小值可能在右半部分。
  2. 如果 nums[mid] < nums[left]，说明右半部分是升序的，最小值可能在左半部分。

通过这种方式，我们可以在对数时间内找到最小元素。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int findMin(int[] nums) {
        int left = 0;
        int right = nums.length - 1;

        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > nums[right]) {  // 如果中间元素大于右边元素，说明最小值在右半部分
                left = mid + 1;
            } else {  // 如果中间元素小于右边元素，说明最小值在左半部分
                right = mid;
            }
        }

        // 当左指针和右指针重合时，left 即为最小元素的索引
        return nums[left];
    }
}

复杂度分析

时间复杂度：时间复杂度为 O(log n)，其中 n 是数组 nums 的长度。在二分查找的过程中，每一步会忽略一半的区间，因此时间复杂度为 O(log n)。

空间复杂度：O(1)。

栈

20. 有效的括号

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。
  3. 每个右括号都有一个对应的相同类型的左括号。

示例 1：

**输入：**s = “()”

**输出：**true

示例 2：

**输入：**s = “()[]{}”

**输出：**true

示例 3：

**输入：**s = “(]”

**输出：**false

示例 4：

**输入：**s = “([])”

**输出：**true

示例 5：

**输入：**s = “([)]”

**输出：**false

提示：

  • 1 <= s.length <= 104
  • s 仅由括号 '()[]{}' 组成

解题思路

栈的使用：我们遍历字符串中的每个字符：

  • 如果是左括号（(, {, [），则将其压入栈中。
  • 如果是右括号（), }, ]），则判断栈顶是否有对应的左括号。如果有，弹出栈顶的左括号；如果没有，则说明括号不匹配，返回 false。

最后检查：遍历结束后，如果栈为空，说明所有的括号都成功匹配并闭合，返回 true；否则，返回 false。

代码实现

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
class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();

        for (char c : s.toCharArray()) {
            if (c == '(' || c == '{' || c == '[') {  // 如果是左括号，压入栈
                stack.push(c);
            } else {  // 如果是右括号，弹出栈顶并匹配左括号
                if (stack.isEmpty()) {
                    return false;
                }

                char top = stack.pop();
                if (top == '(' && c != ')') {
                    return false;
                }

                if (top == '{' && c != '}') {
                    return false;
                }

                if (top == '[' && c != ']') {
                    return false;
                }
            }
        }

        return stack.isEmpty();
    }
}

复杂度分析

时间复杂度：O(n)，其中 n 是字符串 s 的长度。

空间复杂度：O(n+∣Σ∣)，其中 Σ 表示字符集，本题中字符串只包含 6 种括号，∣Σ∣=6。栈中的字符数量为 O(n)，而哈希表使用的空间为 O(∣Σ∣)，相加即可得到总空间复杂度。

155. 最小栈

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

实现 MinStack 类:

  • MinStack() 初始化堆栈对象。
  • void push(int val) 将元素val推入堆栈。
  • void pop() 删除堆栈顶部的元素。
  • int top() 获取堆栈顶部的元素。
  • int getMin() 获取堆栈中的最小元素。

示例 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
输入：
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

输出：
[null,null,null,null,-3,null,0,-2]

解释：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.getMin();   --> 返回 -2.

提示：

  • -231 <= val <= 231 - 1
  • pop、top 和 getMin 操作总是在 非空栈 上调用
  • push, pop, top, and getMin最多被调用 3 * 104 次

解题思路

主栈：存储栈中的所有元素。

辅助栈：每次 push 一个元素时，如果该元素小于当前最小值（或栈为空），就将它压入辅助栈。否则，将辅助栈当前的最小值再次压入辅助栈。这样，辅助栈的栈顶始终保存当前栈的最小值。

getMin 操作：只需要返回辅助栈的栈顶元素，因为它始终保存当前最小值。

pop 操作：在弹出主栈的元素时，辅助栈也要弹出对应的元素，保证辅助栈中的最小值与主栈同步。

代码实现

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
37
38
39
40
41
class MinStack {
    
    private Stack<Integer> stack;  // 主栈：用于存储所有元素
    private Stack<Integer> minStack;  // 辅助栈：用于存储当前最小值

    public MinStack() {
        stack = new Stack<>();
        minStack = new Stack<>();
    }
    
    public void push(int val) {
        stack.push(val);
        if (minStack.isEmpty() || val < minStack.peek()) {
            minStack.push(val);
        } else {
            minStack.push(minStack.peek());
        }
    }
    
    public void pop() {
        stack.pop();
        minStack.pop();
    }
    
    public int top() {
        return stack.peek();
    }
    
    public int getMin() {
        return minStack.peek();
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(val);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */

复杂度分析

时间复杂度：对于题目中的所有操作，时间复杂度均为 O(1)。因为栈的插入、删除与读取操作都是 O(1)，我们定义的每个操作最多调用栈操作两次。

空间复杂度：O(n)，其中 n 为总操作数。最坏情况下，我们会连续插入 n 个元素，此时两个栈占用的空间为 O(n)。

394. 字符串解码

给定一个经过编码的字符串，返回它解码后的字符串。

编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。

你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。

此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。

测试用例保证输出的长度不会超过 105。

示例 1：

1
2
输入：s = "3[a]2[bc]"
输出："aaabcbc"

示例 2：

1
2
输入：s = "3[a2[c]]"
输出："accaccacc"

示例 3：

1
2
输入：s = "2[abc]3[cd]ef"
输出："abcabccdcdcdef"

示例 4：

1
2
输入：s = "abc3[cd]xyz"
输出："abccdcdcdxyz"

提示：

  • 1 <= s.length <= 30
  • s 由小写英文字母、数字和方括号 '[]' 组成
  • s 保证是一个 有效 的输入。
  • s 中所有整数的取值范围为 [1, 300]

解题思路

遍历字符串：

  • 如果遇到数字（k），那么我们就要记录下来，因为它表示要重复的次数。
  • 如果遇到左括号（[），说明后面开始是需要重复的子字符串，我们将当前已构建的部分（包括数字 k）压入栈。
  • 如果遇到右括号（]），说明一个完整的子字符串已经结束，我们从栈中弹出最近的重复次数和之前的字符串部分，然后将当前字符串按照重复次数进行扩展。

关键步骤：

  • 使用栈保存数字 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
class Solution {
    public String decodeString(String s) {
        Stack<String> stack = new Stack<>();  // 存储字符串和数字
        String currentString = "";  // 存储当前处理的字符串
        int currentNum = 0;  // 存储重复的次数

        for (char c : s.toCharArray()) {
            if (Character.isDigit(c)) {  // 如果是数字，积累数字
                currentNum = currentNum * 10 + (c - '0');
            } else if (c == '[') {  // 如果是左括号，将重复次数和字符串入栈
                stack.push(Integer.toString(currentNum));
                stack.push(currentString);
                currentNum = 0;
                currentString = "";
            } else if (c == ']') {  // 如果是右括号，弹出栈中的信息
                String preString = stack.pop();
                int repeatTimes = Integer.parseInt(stack.pop());
                StringBuilder sb = new StringBuilder(preString);
                for (int i = 0; i < repeatTimes; i++) {
                    sb.append(currentString);
                }

                currentString = sb.toString();
            } else {  // 如果是字母，直接添加到当前处理的字符串
                currentString += c;
            }
        }

        return currentString;
    }
}

复杂度分析

时间复杂度：记解码后得出的字符串长度为 S，除了遍历一次原字符串 s，我们还需要将解码后的字符串中的每个字符都入栈，并最终拼接进答案中，故渐进时间复杂度为 O(S+∣s∣)，即 O(S)。
空间复杂度：记解码后得出的字符串长度为 S，这里用栈维护 TOKEN，栈的总大小最终与 S 相同，故渐进空间复杂度为 O(S)。

739. 每日温度

给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。

示例 1:

1
2
输入: temperatures = [73,74,75,71,69,72,76,73]
输出: [1,1,4,2,1,1,0,0]

示例 2:

1
2
输入: temperatures = [30,40,50,60]
输出: [1,1,1,0]

示例 3:

1
2
输入: temperatures = [30,60,90]
输出: [1,1,0]

提示：

  • 1 <= temperatures.length <= 105
  • 30 <= temperatures[i] <= 100

解题思路

我们遍历温度数组，对于每一天的温度：

  • 如果当前温度大于栈顶存储的温度（栈顶的温度对应的是较早的天数），则说明当前天的温度是一个更高的温度，栈顶的天数就找到了一个更高温度的天数。
  • 这时我们可以更新答案数组，并将栈顶元素弹出。

将当前温度的索引压入栈中，等待后续的更高温度来更新答案。

最终，当栈为空时，意味着没有更多更高温度，因此答案数组中相应位置的值是 0。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        Stack<Integer> stack = new Stack<>();
        int[] result = new int[temperatures.length];

        for (int i = 0; i < temperatures.length; i++) {
            while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
                int preIndex = stack.pop();
                result[preIndex] = i - preIndex;
            }

            stack.push(i);
        }

        return result;
    }
}

复杂度分析

时间复杂度：O(n)，其中 n 是温度列表的长度。正向遍历温度列表一遍，对于温度列表中的每个下标，最多有一次进栈和出栈的操作。

空间复杂度：O(n)，其中 n 是温度列表的长度。需要维护一个单调栈存储温度列表中的下标。

堆

215. 数组中的第K个最大元素

给定整数数组 nums 和整数 k，请返回数组中第 **k** 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1:

1
2
输入: [3,2,1,5,6,4], k = 2
输出: 5

示例 2:

1
2
输入: [3,2,3,1,2,4,5,5,6], k = 4
输出: 4

提示：

  • 1 <= k <= nums.length <= 105
  • -104 <= nums[i] <= 104

方法一：基于堆排序的选择方法

解题思路

遍历数组，把元素依次放入一个最小堆（PriorityQueue）。

如果堆的大小超过 k，就把堆顶（最小值）弹出。

遍历完成后，堆顶就是第 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
37
38
39
40
41
42
43
44
class Solution {
    public int findKthLargest(int[] nums, int k) {
        int heapSize = nums.length;
        // 从最后一个非叶子节点开始往前调整堆
        for (int i = heapSize / 2 - 1; i >= 0; i--) {
            maxHeapify(nums, heapSize, i);
        }

        // 依次将堆顶元素（最大值）交换到数组末尾
        for (int i = nums.length - 1; i >= nums.length - k + 1; i--) {
            swap(nums, i, 0);
            // 缩小堆的范围，重新调整堆
            heapSize--;
            maxHeapify(nums, heapSize, 0);
        }

        return nums[0];
    }

    private void maxHeapify(int[] nums, int heapSize, int i) {
        int largest = i;
        int left = i * 2 + 1;
        int right = i * 2 + 2;

        if (left < heapSize && nums[left] > nums[largest]) {
            largest = left;
        }

        if (right < heapSize && nums[right] > nums[largest]) {
            largest = right;
        }

        if (largest != i) {
            swap(nums, largest, i);
            maxHeapify(nums, heapSize, largest);
        }
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

复杂度分析

时间复杂度：O(n log n)，建堆的时间代价是 O(n)，删除的总代价是 O(k log n)，因为 k<n，故渐进时间复杂为 O(n+k log n)=O(n log n)。
空间复杂度：O(log n)，即递归使用栈空间的空间代价。

方法二：基于快速排序的选择方法

解题思路

快速选择算法是快速排序（Quicksort）的变种：

  • 快速排序是递归地对左右子数组排序；
  • 快速选择只需要递归到包含第 k 大元素的那一半数组即可。

我们先选一个 pivot（基准值），把数组划分成两部分：

  • 左边：比 pivot 小的数；
  • 右边：比 pivot 大的数。

根据 pivot 的位置 与目标位置 n - k（第 k 大对应的索引）进行比较：

  • 如果 pivotIndex == n - k，直接返回结果；
  • 如果 pivotIndex < n - k，递归右边；
  • 如果 pivotIndex > n - 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
37
38
39
40
class Solution {
    public int findKthLargest(int[] nums, int k) {
        return quickSelect(nums, 0, nums.length - 1, nums.length - k);
    }
    
    private int quickSelect(int[] nums, int left, int right, int targetIndex) {
        if (left == right) {
            return nums[targetIndex];
        }

        int pivot = nums[left];
        int i = left - 1;
        int j = right + 1;
        while (i < j) {
            do {
                i++;
            } while (nums[i] <   pivot);

            do {
                j--;
            } while (nums[j] > pivot);

            if (i < j) {
                swap(nums, i, j);
            }
        }

        if (targetIndex <= j) {
            return quickSelect(nums, left, j, targetIndex);
        } else {
            return quickSelect(nums, j + 1, right, targetIndex);
        }
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

复杂度分析

平均时间复杂度：O(n)

最坏时间复杂度：O(n^2)（当每次划分极端不平衡时）

空间复杂度：O(log n)（递归栈）

347. 前 K 个高频元素

给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

示例 1：

**输入：**nums = [1,1,1,2,2,3], k = 2

输出：[1,2]

示例 2：

**输入：**nums = [1], k = 1

输出：[1]

示例 3：

**输入：**nums = [1,2,1,2,1,2,3,1,3,2], k = 2

输出：[1,2]

提示：

  • 1 <= nums.length <= 105
  • k 的取值范围是 [1, 数组中不相同的元素的个数]
  • 题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的

**进阶：**你所设计算法的时间复杂度 必须 优于 O(n log n) ，其中 n 是数组大小。

解题思路

统计频率
用 HashMap<Integer, Integer> 统计每个元素出现的次数。

小顶堆存 K 个最高频率元素

  • 使用 优先队列 PriorityQueue（小顶堆），按频率从小到大排序。
  • 遍历 map，把元素放入堆中：
    • 如果堆大小超过 k，就弹出堆顶（频率最小的）。
  • 最终堆里保留的就是前 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
class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        // 统计频率
        Map<Integer, Integer> occurrences = new HashMap<>();
        for (int num : nums) {
            occurrences.put(num, occurrences.getOrDefault(num, 0) + 1);
        }

        // 使用小顶堆，按频率升序
        PriorityQueue<int[]> heap = new PriorityQueue<>(
            (a, b) -> a[1] - b[1]
        );

        for (Map.Entry<Integer, Integer> entry : occurrences.entrySet()) {
            heap.offer(new int[]{entry.getKey(), entry.getValue()});
            // 保证堆里最多只有 k 个元素
            if (heap.size() > k) {
                heap.poll();
            }
        }

        // 取结果
        int[] result = new int[k];
        for (int i = 0; i < k; i++) {
            result[i] = heap.poll()[0];
        }

        return result;
    }
}

复杂度分析

时间复杂度：O(n log k)，其中 n 为数组的长度。我们首先遍历原数组，并使用哈希表记录出现次数，每个元素需要 O(1) 的时间，共需 O(n) 的时间。随后，我们遍历「出现次数数组」，由于堆的大小至多为 k，因此每次堆操作需要 O(log k) 的时间，共需 O(n log k) 的时间。二者之和为 O(n log k)。
空间复杂度：O(n)。哈希表的大小为 O(n)，而堆的大小为 O(k)，共计为 O(n)。

贪心算法

121. 买卖股票的最佳时机

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

示例 1：

1
2
3
4
输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
     注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。

示例 2：

1
2
3
输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 没有交易完成, 所以最大利润为 0。

提示：

  • 1 <= prices.length <= 105
  • 0 <= prices[i] <= 104

解题思路

我们只需要找到：

  • 最便宜的一天买入（minPrice）
  • 之后某天卖出价格与它的差值最大

遍历 prices 数组时：

  1. 更新最小买入价 minPrice
  2. 计算当前天卖出的利润 prices[i] - minPrice
  3. 更新最大利润 maxProfit

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int maxProfit(int[] prices) {
        int minPrice = Integer.MAX_VALUE;   // 初始化最小买入价
        int maxProfit = 0;                  // 初始化最大利润

        for (int price : prices) {
            if (price < minPrice) {  // 更新最小买入价
                minPrice = price;
            } else if (price - minPrice > maxProfit) {  // 更新最大利润
                maxProfit = price - minPrice;
            }
        }

        return maxProfit;
    }
}

复杂度分析

  • 时间复杂度：O(n)，只需要遍历一次。
  • 空间复杂度：O(1)，只使用了常数个变量。

55. 跳跃游戏

给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。

示例 1：

1
2
3
输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。

示例 2：

1
2
3
输入：nums = [3,2,1,0,4]
输出：false
解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。

提示：

  • 1 <= nums.length <= 104
  • 0 <= nums[i] <= 105

解题思路

我们维护一个变量 maxReach 表示 能到达的最远下标：

  1. 从头开始遍历数组。
  2. 如果当前位置 i 在 maxReach 之外，说明走不到这里 → 返回 false。
  3. 否则，更新 maxReach = max(maxReach, i + nums[i])。
  4. 遍历过程中如果 maxReach >= nums.length - 1，说明能到达最后一个位置 → 返回 true。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public boolean canJump(int[] nums) {
        int maxRearch = 0;
        int n = nums.length;

        for (int i = 0; i < n; i++) {
            // 如果当前位置不可到达，提前返回
            if (i > maxRearch) {
                return false;
            }

            // 更新能到达的最远位置
            maxRearch = Math.max(maxRearch, i + nums[i]);

            // 如果可以到达最后，提前返回
            if (maxRearch >= n - 1) {
                return true;
            }
        }

        return false;
    }
}

复杂度分析

  • 时间复杂度：O(n)，其中 n 为数组的大小。只需要访问 nums 数组一遍，共 n 个位置。
  • 空间复杂度：O(1)，不需要额外的空间开销。

45. 跳跃游戏 II

给定一个长度为 n 的 0 索引整数数组 nums。初始位置在下标 0。

每个元素 nums[i] 表示从索引 i 向后跳转的最大长度。换句话说，如果你在索引 i 处，你可以跳转到任意 (i + j) 处：

  • 0 <= j <= nums[i] 且
  • i + j < n

返回到达 n - 1 的最小跳跃次数。测试用例保证可以到达 n - 1。

示例 1:

1
2
3
4
输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
     从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。

示例 2:

1
2
输入: nums = [2,3,0,1,4]
输出: 2

提示:

  • 1 <= nums.length <= 104
  • 0 <= nums[i] <= 1000
  • 题目保证可以到达 n - 1

解题思路

我们要找的是最少跳跃次数。

  • 走到某个位置时，我们关心的是从当前位置最远能到哪里。
  • 当我们走完一个“跳跃范围”后，必须进行一次跳跃。
  • 所以我们用两个变量：
    • end：当前这一步能到的最远范围的边界。
    • farthest：在当前范围内能到的最远位置。
  • 每次遍历到 end 时，说明这一步的范围走完了，就需要进行一次跳跃，然后把 end 更新为 farthest。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int jump(int[] nums) {
        int steps = 0;      // 跳跃次数
        int end = 0;        // 当前范围的最远位置
        int farthest = 0;   // 在当前范围内能到达的最远位置

        for (int i = 0; i < nums.length - 1; i++) {
            farthest = Math.max(farthest, i + nums[i]);

            if (i == end) {  // 到达当前范围的最远位置，必须跳跃一次
                steps++;
                end = farthest;
            }
        }

        return steps;
    }
}

复杂度分析

  • 时间复杂度：O(n)，其中 n 是数组长度。
  • 空间复杂度：O(1)。

763. 划分字母区间

给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。例如，字符串 "ababcc" 能够被分为 ["abab", "cc"]，但类似 ["aba", "bcc"] 或 ["ab", "ab", "cc"] 的划分是非法的。

注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s 。

返回一个表示每个字符串片段的长度的列表。

示例 1：

1
2
3
4
5
6
输入：s = "ababcbacadefegdehijhklij"
输出：[9,7,8]
解释：
划分结果为 "ababcbaca"、"defegde"、"hijhklij" 。
每个字母最多出现在一个片段中。
像 "ababcbacadefegde", "hijhklij" 这样的划分是错误的，因为划分的片段数较少。

示例 2：

1
2
输入：s = "eccbbbbdec"
输出：[10]

提示：

  • 1 <= s.length <= 500
  • s 仅由小写英文字母组成

解题思路

我们要把字符串划分成尽可能多的片段，并保证每个字母只出现在一个片段中。

关键点：

  • 对于某个片段来说，如果片段中包含某个字母，就必须把这个字母最后一次出现的位置也包括进来。
  • 因此我们可以先扫描一遍字符串，记录每个字母的最后出现位置。
  • 然后从头遍历字符串，用一个变量 end 表示当前片段能到的最远位置。
    • 遍历时不断更新 end = max(end, last[s[i]])。
    • 当 i == end 时，说明一个片段结束，可以记录下来。

代码实现

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
class Solution {
    public List<Integer> partitionLabels(String s) {
        List<Integer> result = new ArrayList<>();
        int n = s.length();
        int[] last = new int[26];

        // 记录每个字母最后出现的位置
        for (int i = 0; i < n; i++) {
            last[s.charAt(i) - 'a'] = i;
        }

        // 分割区间
        int start = 0;
        int end = 0;
        for (int i = 0; i < n; i++) {
            end = Math.max(end, last[s.charAt(i) - 'a']);

            if (i == end) {
                result.add(end - start + 1);
                start = end + 1;
            }
        }

        return result;
    }
}

复杂度分析

时间复杂度：O(n)，其中 n 是字符串的长度。需要遍历字符串两次，第一次遍历时记录每个字母最后一次出现的下标位置，第二次遍历时进行字符串的划分。

空间复杂度：O(∣Σ∣)，其中 Σ 是字符串中的字符集。这道题中，字符串只包含小写字母，因此 ∣Σ∣=26。

动态规划

70. 爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

示例 1：

1
2
3
4
5
输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶

示例 2：

1
2
3
4
5
6
输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶

提示：

  • 1 <= n <= 45

解题思路

  • 如果要爬到第 n 阶，可以从：

    1. n-1 阶走 1 步；
    2. n-2 阶走 2 步。

  • 因此有递推关系式：

    f(n) = f(n − 1) + f(n − 2)

  • 初始条件：

    • f(1) = 1 （只有一种方式，1 阶）
    • f(2) = 2 （两种方式：1+1 或 2）

这其实就是 斐波那契数列，第 n 项即为答案。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int climbStairs(int n) {
        if (n <= 2) {
            return n;
        }

        int a = 1;
        int b = 2;
        for (int i = 3; i <= n; i++) {
            
            int c = b + a;  // f(i) = f(i - 1) + f(i - 2)
            a = b;          // f(i - 2 + 1) -> f(i - 1)
            b = c;          // f(i - 1 + 1) -> f(i - 1) + f(i - 2)
        }

        return b;           // f(n - 1) + f(n - 2)
    }
}

复杂度分析

时间复杂度：循环执行 n 次，每次花费常数的时间代价，故渐进时间复杂度为 O(n)。
空间复杂度：这里只用了常数个变量作为辅助空间，故渐进空间复杂度为 O(1)。

118. 杨辉三角

给定一个非负整数 *numRows，*生成「杨辉三角」的前 numRows 行。

在「杨辉三角」中，每个数是它左上方和右上方的数的和。

img

示例 1:

1
2
输入: numRows = 5
输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

示例 2:

1
2
输入: numRows = 1
输出: [[1]]

提示:

  • 1 <= numRows <= 30

解题思路

杨辉三角的性质：

  1. 每一行的首尾元素都是 1。

  2. 其他元素满足：row[j] = prev[j − 1] + prev[j]

    其中 prev 是上一行。

因此我们可以逐行生成。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> result = new ArrayList<>();

        for (int i = 0; i < numRows; i++) {
            List<Integer> row = new ArrayList<>();
            // 第 i 行有 i + 1 个元素
            for (int j = 0; j <= i; j++) {
                if (j == 0 || j == i) {
                    row.add(1);
                } else {
                    // row[j] = prev[j - 1] + prev[j]
                    row.add(result.get(i - 1).get(j - 1) + result.get(i - 1).get(j));
                }
            }

            result.add(row);
        }
        
        return result;
    }
}

复杂度分析

时间复杂度：O(numRows^2)，因为总共有 1 + 2 + … + numRows ≈ O(numRows^2) 个元素。

空间复杂度：O(numRows^2)，存储整个三角。

198. 打家劫舍

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

示例 1：

1
2
3
4
输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
     偷窃到的最高金额 = 1 + 3 = 4 。

示例 2：

1
2
3
4
输入：[2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
     偷窃到的最高金额 = 2 + 9 + 1 = 12 。

提示：

  • 1 <= nums.length <= 100
  • 0 <= nums[i] <= 400

解题思路

  • 如果我们在第 i 个房子：
    • 偷它：就不能偷 i-1，所以收益是 dp[i-2] + nums[i]
    • 不偷它：那收益是 dp[i-1]
  • 状态转移公式：dp[i] = max(dp[i], dp[i - 2] + nums[i])
  • 初始条件：
    • dp[0] = nums[0]
    • dp[1] = max(nums[0], nums[1])
  • 最终答案：dp[n-1]

优化：由于 dp[i] 只依赖 dp[i-1] 和 dp[i-2]，我们可以用两个变量滚动更新，空间降到 O(1)。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int rob(int[] nums) {
        // 转移方程：dp[i] = max(dp[i], dp[i - 2] + nums[i])
        
        int n = nums.length;
        if (n == 1) {
            return nums[0];
        }

        int prev2 = nums[0];  // dp[i - 2]
        int prev1 = Math.max(nums[0], nums[1]);  // dp[i - 1]
        for (int i = 2; i < n; i++) {
            int cur = Math.max(prev1, prev2 + nums[i]);
            prev2 = prev1;
            prev1 = cur;
        }

        return prev1;
    }
}

复杂度分析

时间复杂度：O(n)，其中 n 是数组长度。只需要对数组遍历一次。

空间复杂度：O(1)。使用滚动数组，可以只存储前两间房屋的最高总金额，而不需要存储整个数组的结果，因此空间复杂度是 O(1)。

279. 完全平方数

给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。

完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

示例 1：

1
2
3
输入：n = 12
输出：3 
解释：12 = 4 + 4 + 4

示例 2：

1
2
3
输入：n = 13
输出：2
解释：13 = 4 + 9

提示：

  • 1 <= n <= 104

解题思路

我们把 n 看作一个「背包容量」，完全平方数看作「物品」，每个物品可以无限使用，求最少物品数量。

  • 定义 dp[i]：表示和为 i 的最少完全平方数数量。
  • 转移方程：dp[i] = dp[i - j * j] + 1 (j * j <= i)
  • 初始化：
    • dp[0] = 0（和为 0 不需要数字）
    • 其他初始化为一个较大值

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int numSquares(int n) {
        // 转移方程：dp[i] = dp[i - j * j] + 1 (j * j <= i)
        
        int[] dp = new int[n + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j * j <= i; j++) {
                dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
            }
        }

        return dp[n];
    }
}

复杂度分析

时间复杂度：O(n * sqrt(n))，其中 n 为给定的正整数。状态转移方程的时间复杂度为 O(sqrt(n))，共需要计算 n 个状态，因此总时间复杂度为 O(n * sqrt(n))。

空间复杂度：O(n)。我们需要 O(n) 的空间保存状态。

322. 零钱兑换

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

示例 1：

1
2
3
输入：coins = [1, 2, 5], amount = 11
输出：3 
解释：11 = 5 + 5 + 1

示例 2：

1
2
输入：coins = [2], amount = 3
输出：-1

示例 3：

1
2
输入：coins = [1], amount = 0
输出：0

提示：

  • 1 <= coins.length <= 12
  • 1 <= coins[i] <= 231 - 1
  • 0 <= amount <= 104

解题思路

  • 定义 dp[i] 表示字符串 s[0..i-1] 是否可以由字典中的单词拼接而成。

  • 初始条件：dp[0] = true（空字符串可被拆分）。

  • 状态转移：
    对于每个位置 i，遍历所有 j < i：

    1
    如果 dp[j] == true 且 s[j..i-1] 在字典中出现，则 dp[i] = true

  • 最终答案：dp[n]，其中 n = s.length()。

为了加速判断子串是否在字典中，我们可以用 HashSet 存储 wordDict。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int coinChange(int[] coins, int amount) {
        // 转移方程：dp[i] = min(dp[i], dp[i - coin] + 1)
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, amount + 1);  // 最大不会超过 amount 个（全部使用 1 元）
        dp[0] = 0;
        
        for (int i = 1; i <= amount; i++) {
            for (int coin : coins) {
                if (i >= coin) {
                    dp[i] = Math.min(dp[i], dp[i - coin] + 1);
                }
            }
        }

        return dp[amount] != amount + 1 ? dp[amount] : -1;
    }
}

复杂度分析

时间复杂度：O(Sn)，其中 S 是金额，n 是面额数。我们一共需要计算 O(S) 个状态，S 为题目所给的总金额。对于每个状态，每次需要枚举 n 个面额来转移状态，所以一共需要 O(Sn) 的时间复杂度。
空间复杂度：O(S)。数组 dp 需要开长度为总金额 S 的空间。

139. 单词拆分

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。

**注意：**不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

示例 1：

1
2
3
输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。

示例 2：

1
2
3
4
输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。
     注意，你可以重复使用字典中的单词。

示例 3：

1
2
输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: false

提示：

  • 1 <= s.length <= 300
  • 1 <= wordDict.length <= 1000
  • 1 <= wordDict[i].length <= 20
  • s 和 wordDict[i] 仅由小写英文字母组成
  • wordDict 中的所有字符串 互不相同

解题思路

  • 定义 dp[i] 表示字符串 s[0..i-1] 是否可以由字典中的单词拼接而成。

  • 初始条件：dp[0] = true（空字符串可被拆分）。

  • 状态转移：
    对于每个位置 i，遍历所有 j < i：

    1
    如果 dp[j] == true 且 s[j..i-1] 在字典中出现，则 dp[i] = true

  • 最终答案：dp[n]，其中 n = s.length()。

为了加速判断子串是否在字典中，我们可以用 HashSet 存储 wordDict。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        // 转移方程：dp[i] = dp[j] && s[j...i-1]，dp[i] 表示 s[0...i-1] 是否能由字典拼接
        // 把 wordDict 存在 HashSet中，加速查找
        Set<String> wordSet = new HashSet<>(wordDict);
        int n = s.length();
        boolean[] dp = new boolean[n + 1];
        dp[0] = true;  // 初始条件
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j] && wordSet.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break;  // 找到一个即可终止
                }
            }
        }

        return dp[n];
    }
}

复杂度分析

时间复杂度：O(n^2) ，其中 n 为字符串 s 的长度。我们一共有 O(n) 个状态需要计算，每次计算需要枚举 O(n) 个分割点，哈希表判断一个字符串是否出现在给定的字符串列表需要 O(1) 的时间，因此总时间复杂度为 O(n^2)。

空间复杂度：O(n) ，其中 n 为字符串 s 的长度。我们需要 O(n) 的空间存放 dp 值以及哈希表亦需要 O(n) 的空间复杂度，因此总空间复杂度为 O(n)。

300. 最长递增子序列

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

示例 1：

1
2
3
输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

示例 2：

1
2
输入：nums = [0,1,0,3,2,3]
输出：4

示例 3：

1
2
输入：nums = [7,7,7,7,7,7,7]
输出：1

提示：

  • 1 <= nums.length <= 2500
  • -104 <= nums[i] <= 104

进阶：

  • 你能将算法的时间复杂度降低到 O(n log(n)) 吗?

方法一：动态规划

解题思路

定义 dp[i]：表示 以 nums[i] 结尾的最长递增子序列长度。

转移方程：

1
dp[i] = max(dp[j] + 1)  for all j < i and nums[j] < nums[i]

初始化：dp[i] = 1（每个数都能单独成为长度为 1 的子序列）。

答案就是 max(dp[i])。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int lengthOfLIS(int[] nums) {
        // 方法一：动态规划，时间复杂度 O(n^2)，空间复杂度 O(n)
        // 转移方程：dp[i] = max(dp[i], dp[j] + 1) for all j < i and nums[j] < nums[i]
        int n = nums.length;
        int[] dp = new int[ny];
        Arrays.fill(dp, 1);
        int maxLength = 1;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            maxLength = Math.max(maxLength, dp[i]);
        }
        
        return maxLength;
    }
}

复杂度分析

时间复杂度：O(n^2)，其中 n 为数组 nums 的长度。动态规划的状态数为 n，计算状态 dp[i] 时，需要 O(n) 的时间遍历 dp[0…i−1] 的所有状态，所以总时间复杂度为 O(n^2)。

空间复杂度：O(n)，需要额外使用长度为 n 的 dp 数组。

方法二：贪心 + 二分查找

解题思路

考虑一个简单的贪心，如果我们要使上升子序列尽可能的长，则我们需要让序列上升得尽可能慢，因此我们希望每次在上升子序列最后加上的那个数尽可能的小。

基于上面的贪心思路，我们维护一个数组 d[i] ，表示长度为 i 的最长上升子序列的末尾元素的最小值，用 len 记录目前最长上升子序列的长度，起始时 len 为 1，d[1]=nums[0]。

我们依次遍历数组 nums 中的每个元素，并更新数组 d 和 len 的值。如果 nums[i]>d[len] 则更新 len=len+1，否则在 d[1…len]中找满足 d[i−1]<nums[j]<d[i] 的下标 i，并更新 d[i]=nums[j]。

根据 d 数组的单调性，我们可以使用二分查找寻找下标 i，优化时间复杂度。

最后整个算法流程为：

设当前已求出的最长上升子序列的长度为 len（初始时为 1），从前往后遍历数组 nums，在遍历到 nums[i] 时：

如果 nums[i]>d[len] ，则直接加入到 d 数组末尾，并更新 len=len+1；

否则，在 d 数组中二分查找，找到第一个比 nums[i] 小的数 d[k] ，并更新 d[k+1]=nums[i]。

以输入序列 [0,8,4,12,2] 为例：

第一步插入 0，d=[0]；

第二步插入 8，d=[0,8]；

第三步插入 4，d=[0,4]；

第四步插入 12，d=[0,4,12]；

第五步插入 2，d=[0,2,12]。

最终得到最大递增子序列长度为 3。

代码实现

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
class Solution {
    public int lengthOfLIS(int[] nums) {
        // 方法二：贪心 + 二分，时间复杂度 O(n log n)，空间复杂度 O(n)
        int n = nums.length;
        if (n == 0) {
            return 0;
        }

        int len = 1;  // 初始时为 1
        int[] d = new int[n + 1];
        d[len] = nums[0];
        for (int i = 1; i < n; i++) {
            if (nums[i] > d[len]) {  // 如果 nums[i] > d[len] ，则直接加入到 d 数组末尾，并更新 len = len+1
                d[++len] = nums[i];
            } else {  // 否则，在 d 数组中二分查找，找到第一个比 nums[i] 小的数 d[k] ，并更新 d[k + 1] = nums[i]
                int left = 1;
                int right = len;
                int k = 0;  // 如果找不到说明所有的数都比 nums[i] 大，此时要更新 d[1]，所以这里将 k 设为 0
                while (left <= right) {
                    int mid = left + (right - left) / 2;
                    if (d[mid] < nums[i]) {
                        k = mid;
                        left = mid + 1;
                    } else {
                        right = mid - 1;
                    }
                }

                d[k + 1] = nums[i];
            }
        }

        return len;
    }
}

复杂度分析

时间复杂度：O(n log n)。数组 nums 的长度为 n，我们依次用数组中的元素去更新 d 数组，而更新 d 数组时需要进行 O(log n) 的二分搜索，所以总时间复杂度为 O(n log n)。

空间复杂度：O(n)，需要额外使用长度为 n 的 d 数组。

152. 乘积最大子数组

给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续 子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。

测试用例的答案是一个 32-位 整数。

示例 1:

1
2
3
输入: nums = [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。

示例 2:

1
2
3
输入: nums = [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。

提示:

  • 1 <= nums.length <= 2 * 104
  • -10 <= nums[i] <= 10
  • nums 的任何子数组的乘积都 保证 是一个 32-位 整数

解题思路

定义两个数组（或变量即可优化空间）：

  • maxF[i]：以 i 结尾的子数组的最大乘积
  • minF[i]：以 i 结尾的子数组的最小乘积

状态转移：

1
2
maxF[i] = max(nums[i], maxF[i-1] * nums[i], minF[i-1] * nums[i]);
minF[i] = min(nums[i], maxF[i-1] * nums[i], minF[i-1] * nums[i]);

因为 nums[i] 可能为负数，乘上 minF[i-1] 有可能变大。

答案就是所有 maxF[i] 中的最大值。

空间优化：我们只需要前一状态，所以用两个变量 maxVal 和 minVal 即可。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int maxProduct(int[] nums) {
        // maxF[i] = max(nums[i], maxF[i-1] * nums[i], minF[i-1] * nums[i]);
        // minF[i] = min(nums[i], maxF[i-1] * nums[i], minF[i-1] * nums[i]);

        int result = nums[0];
        int maxValue = nums[0];
        int minValue = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] < 0) {  // 如果当前数是负数，交换 maxValue 和 minValue
                int temp = maxValue;
                maxValue = minValue;
                minValue = temp;
            }

            maxValue = Math.max(nums[i], maxValue * nums[i]);
            minValue = Math.min(nums[i], minValue * nums[i]);
            result = Math.max(result, maxValue);
        }

        return result;
    }
}

复杂度分析

时间复杂度：程序一次循环遍历了 nums，故渐进时间复杂度为 O(n)。

空间复杂度：优化后只使用常数个临时变量作为辅助空间，与 n 无关，故渐进空间复杂度为 O(1)。

416. 分割等和子集

给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

示例 1：

1
2
3
输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11] 。

示例 2：

1
2
3
输入：nums = [1,2,3,5]
输出：false
解释：数组不能分割成两个元素和相等的子集。

提示：

  • 1 <= nums.length <= 200
  • 1 <= nums[i] <= 100

解题思路

总和判断

  • 先算数组总和 sum。
  • 如果 sum 是奇数，直接返回 false（不可能拆成相等的两份）。
  • 目标就是找到一个子集，和为 target = sum / 2。

转化为 0-1 背包问题

  • 问题就变成：是否可以从 nums 中选一些数，使得和恰好等于 target。
  • 定义 dp[j]：表示是否可以恰好装满容量为 j 的背包。

状态转移
遍历每个 num：

1
dp[j] = dp[j] || dp[j - num]   (前提 j >= num)

注意要 逆序遍历 j，防止同一个 num 被重复使用。

初始化

  • dp[0] = true（不选任何数时，和为 0 是可行的）。

答案

  • 返回 dp[target]。

代码实现

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
class Solution {
    public boolean canPartition(int[] nums) {
        // 转移方程：dp[i] = dp[i] || dp[i - num] (i >= num)

        int sum = 0;
        for (int num : nums) {
            sum += num;
        }

        if (sum % 2 == 1) {
            return false;
        }
        sum /= 2;

        boolean[] dp = new boolean[sum + 1];
        dp[0] = true;
        for (int num : nums) {
            for (int i = sum; i >= num; i--) {
                dp[i] = dp[i] || dp[i - num];
            }
        }

        return dp[sum];
    }
}

复杂度分析

时间复杂度：O(n×target)，其中 n 是数组的长度，target 是整个数组的元素和的一半。需要计算出所有的状态，每个状态在进行转移时的时间复杂度为 O(1)。

空间复杂度：O(target)，其中 target 是整个数组的元素和的一半。空间复杂度取决于 dp 数组，在不进行空间优化的情况下，空间复杂度是 O(n×target)，在进行空间优化的情况下，空间复杂度可以降到 O(target)。

多维动态规划

62. 不同路径

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

示例 1：

img

1
2
输入：m = 3, n = 7
输出：28

示例 2：

1
2
3
4
5
6
7
输入：m = 3, n = 2
输出：3
解释：
从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右
3. 向下 -> 向右 -> 向下

示例 3：

1
2
输入：m = 7, n = 3
输出：28

示例 4：

1
2
输入：m = 3, n = 3
输出：6

提示：

  • 1 <= m, n <= 100
  • 题目数据保证答案小于等于 2 * 109

解题思路

状态定义

  • dp[i][j] 表示从起点 (0,0) 到达 (i,j) 的路径数。

状态转移方程

  • 机器人只能从 上方 (i-1,j) 或 左边 (i,j-1) 过来：

    1
    dp[i][j] = dp[i-1][j] + dp[i][j-1]

初始化

  • 第一行只能一直往右走，所以 dp[0][j] = 1。
  • 第一列只能一直往下走，所以 dp[i][0] = 1。

答案

  • 最终答案是 dp[m-1][n-1]。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int uniquePaths(int m, int n) {
        // 转移方程：dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
        int[][] dp = new int[m][n];
        
        for (int i = 0; i < m; i++) {
            dp[i][0] = 1;
        }

        for (int j = 0; j < n; j++) {
            dp[0][j] = 1;
        }

        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }

        return dp[m - 1][n - 1];
    }
}

复杂度分析

时间复杂度：O(mn)。

空间复杂度：O(min(m,n))，即为存储所有状态需要的空间。注意到 f(i,j) 仅与第 i 行和第 i−1 行的状态有关，因此我们可以使用滚动数组代替代码中的二维数组，使空间复杂度降低为 O(n)。此外，由于我们交换行列的值并不会对答案产生影响，因此我们总可以通过交换 m 和 n 使得 m≤n，这样空间复杂度降低至 O(min(m,n))。

64. 最小路径和

给定一个包含非负整数的 *m* x *n* 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

**说明：**每次只能向下或者向右移动一步。

示例 1：

img

1
2
3
输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。

示例 2：

1
2
输入：grid = [[1,2,3],[4,5,6]]
输出：12

提示：

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 200
  • 0 <= grid[i][j] <= 200

解题思路

当 i>0 且 j=0 时，dp[i][0]=dp[i−1][0]+grid[i][0]。

当 i=0 且 j>0 时，dp[0][j]=dp[0][j−1]+grid[0][j]。

当 i>0 且 j>0 时，dp[i][j]=min(dp[i−1][j],dp[i][j−1])+grid[i][j]

代码实现

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
class Solution {
    public int minPathSum(int[][] grid) {
        // 转移方程：dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]
        
        int m = grid.length;
        int n = grid[0].length;
        int[][] dp = new int[m][n];
        dp[0][0] = grid[0][0];

        for (int i = 1; i < m; i++) {
            dp[i][0] = dp[i - 1][0] + grid[i][0];
        }

        for (int j = 1; j < n; j++) {
            dp[0][j] = dp[0][j - 1] + grid[0][j];
        }

        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
            }
        }

        return dp[m - 1][n - 1];
    }
}

复杂度分析

时间复杂度：O(mn)，其中 m 和 n 分别是网格的行数和列数。需要对整个网格遍历一次，计算 dp 的每个元素的值。

空间复杂度：O(mn)，其中 m 和 n 分别是网格的行数和列数。创建一个二维数组 dp，和网格大小相同。
空间复杂度可以优化，例如每次只存储上一行的 dp 值，则可以将空间复杂度优化到 O(n)。

5. 最长回文子串

给你一个字符串 s，找到 s 中最长的 回文 子串。

示例 1：

1
2
3
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

示例 2：

1
2
输入：s = "cbbd"
输出："bb"

提示：

  • 1 <= s.length <= 1000
  • s 仅由数字和英文字母组成

解题思路

回文串有两种情况：

  1. 奇数长度回文：中心是一个字符
  2. 偶数长度回文：中心是两个字符

从每个位置向两边扩展，找到以该点（或该点和下一个点）为中心的最长回文子串。

记录最长的区间。

代码实现

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
37
38
39
40
41
42
43
44
45
46
47
class Solution {
    public String longestPalindrome(String s) {
        // 转移方程：dp[i][j] = dp[i + 1][j - 1] if (s.charAt(i) == s.charAt(j))

        int n = s.length();
        if (n < 2) {
            return s;
        }

        boolean[][] dp = new boolean[n][n];  // dp[i][j] 表示 s[i..j] 是否是回文串
        // 每个单字符都是回文串
        for (int i = 0; i < n; i++) {
            dp[i][i] = true;
        }

        int start = 0;  // 最长子串头部位置
        int maxLen = 1;  // 最长子串的长度
        // 枚举每个子串长度
        for (int len = 2; len <= n; len++) {
            for (int i = 0; i < n; i++) {
                int j = i + len - 1;  // 子串右端点
                
                if (j >= n) {
                    break;
                }

                if (s.charAt(i) == s.charAt(j)) {
                    if (len <= 3) {  // 2 个或 3 个字符，直接就是回文子串
                        dp[i][j] = true;
                    } else {
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                } else {
                    dp[i][j] = false;
                }

                // 更新最大长度
                if (dp[i][j] && len > maxLen) {
                    maxLen = len;
                    start = i;
                }
            }
        }

        return s.substring(start, start + maxLen);
    }
}

复杂度分析

时间复杂度：O(n^2)，其中 n 是字符串的长度。动态规划的状态总数为 O(n^2)，对于每个状态，我们需要转移的时间为 O(1)。

空间复杂度：O(n^2)，即存储动态规划状态需要的空间。

1143. 最长公共子序列

给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

  • 例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。

两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

示例 1：

1
2
3
输入：text1 = "abcde", text2 = "ace" 
输出：3  
解释：最长公共子序列是 "ace" ，它的长度为 3 。

示例 2：

1
2
3
输入：text1 = "abc", text2 = "abc"
输出：3
解释：最长公共子序列是 "abc" ，它的长度为 3 。

示例 3：

1
2
3
输入：text1 = "abc", text2 = "def"
输出：0
解释：两个字符串没有公共子序列，返回 0 。

提示：

  • 1 <= text1.length, text2.length <= 1000
  • text1 和 text2 仅由小写英文字符组成。

解题思路

定义状态：
dp[i][j] 表示 text1[0..i-1] 与 text2[0..j-1] 的最长公共子序列的长度。

状态转移：

  • 如果 text1[i-1] == text2[j-1]，则：dp[i][j] = dp[i-1][j-1] + 1
  • 否则：dp[i][j] = max(dp[i-1][j], dp[i][j-1])

初始化：
dp[0][*] = 0, dp[*][0] = 0，即空字符串和任何字符串的 LCS 长度是 0。

答案：
dp[m][n]，其中 m = text1.length, n = text2.length。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        // 转移方程：dp[i][j] = dp[i - 1][j - 1] + 1
        // dp[i][j] 表示 text1[0..i-1] 与 text2[0..j-1] 的最长公共子序列的长度

        int n1 = text1.length();
        int n2 = text2.length();
        int[][] dp = new int[n1 + 1][n2 + 1];

        for (int i = 1; i <= n1; i++) {
            for (int j = 1; j <= n2; j++) {
                if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }

        return dp[n1][n2];
    }
}

复杂度分析

时间复杂度：O(mn)，其中 m 和 n 分别是字符串 text1 和 text2 的长度。二维数组 dp 有 m+1 行和 n+1 列，需要对 dp 中的每个元素进行计算。

空间复杂度：O(mn)，其中 m 和 n 分别是字符串 text1 和 text2 的长度。创建了 m+1 行 n+1 列的二维数组 dp。

72. 编辑距离

给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。

你可以对一个单词进行如下三种操作：

  • 插入一个字符
  • 删除一个字符
  • 替换一个字符

示例 1：

1
2
3
4
5
6
输入：word1 = "horse", word2 = "ros"
输出：3
解释：
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')

示例 2：

1
2
3
4
5
6
7
8
输入：word1 = "intention", word2 = "execution"
输出：5
解释：
intention -> inention (删除 't')
inention -> enention (将 'i' 替换为 'e')
enention -> exention (将 'n' 替换为 'x')
exention -> exection (将 'n' 替换为 'c')
exection -> execution (插入 'u')

提示：

  • 0 <= word1.length, word2.length <= 500
  • word1 和 word2 由小写英文字母组成

解题思路

  • 定义 dp[i][j] 表示 将 word1[0..i-1] 转换为 word2[0..j-1] 的最少操作数。
  • 递推公式：
    1. 如果最后一个字符相同：
      dp[i][j] = dp[i-1][j-1]
    2. 如果最后一个字符不同，有三种选择，取三者最小值：
      • 插入：dp[i][j-1] + 1
      • 删除：dp[i-1][j] + 1
      • 替换：dp[i-1][j-1] + 1
  • 边界条件：
    • dp[0][j] = j （空字符串变成 word2[0..j-1] 需要插入 j 次）
    • dp[i][0] = i （word1[0..i-1] 变成空字符串需要删除 i 次）

代码实现

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
class Solution {
    public int minDistance(String word1, String word2) {
        // 最后一个字符相同：dp[i][j] = dp[i - 1][j - 1]
        // 最后一个字符不同：
        // 插入：dp[i][j - 1] + 1
        // 删除：dp[i - 1][j] + 1
        // 替换: dp[i - 1][j - 1]

        int n1 = word1.length();
        int n2 = word2.length();
        int[][] dp = new int[n1 + 1][n2 + 1];

        for (int i = 0; i <= n1; i++) {
            dp[i][0] = i;
        }

        for (int j = 0; j <= n2; j++) {
            dp[0][j] = j;
        }

        for (int i = 1; i <= n1; i++) {
            for (int j = 1; j <= n2; j++) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = Math.min(Math.min(dp[i -1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
                }
            }
        }

        return dp[n1][n2];
    }
}

复杂度分析

时间复杂度 ：O(mn)，其中 m 为 word1 的长度，n 为 word2 的长度。

空间复杂度 ：O(mn)，我们需要大小为 O(mn) 的 D 数组来记录状态值。

技巧

136. 只出现一次的数字

给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。

示例 1 ：

**输入：**nums = [2,2,1]

**输出：**1

示例 2 ：

**输入：**nums = [4,1,2,1,2]

**输出：**4

示例 3 ：

**输入：**nums = [1]

**输出：**1

提示：

  • 1 <= nums.length <= 3 * 104
  • -3 * 104 <= nums[i] <= 3 * 104
  • 除了某个元素只出现一次以外，其余每个元素均出现两次。

解题思路

最巧妙的方法就是 位运算 - 异或 XOR。

异或运算的性质：

  • a ^ a = 0 （一个数和自己异或等于 0）
  • a ^ 0 = a （一个数和 0 异或等于它本身）
  • 异或满足交换律和结合律。

所以：把所有数字依次异或，成对出现的数字都会变成 0，被抵消掉，只剩下那个唯一的数字。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int singleNumber(int[] nums) {
        // 异或运算 a ^ a = 0, a ^ 0 = a

        int result = 0;
        for (int num : nums) {
            result ^= num;
        }

        return result;
    }
}

复杂度分析

  • 时间复杂度：O(n)，其中 n 是数组长度。只需要对数组遍历一次。
  • 空间复杂度：O(1)。

169. 多数元素

给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例 1：

1
2
输入：nums = [3,2,3]
输出：3

示例 2：

1
2
输入：nums = [2,2,1,1,1,2,2]
输出：2

提示：

  • n == nums.length
  • 1 <= n <= 5 * 104
  • -109 <= nums[i] <= 109

**进阶：**尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。

解题思路

最优解法是 Boyer-Moore 投票算法。

多数元素的出现次数 > ⌊n/2⌋。

投票法：

  • 维护一个候选人 candidate 和一个计数器 count。
  • 遍历数组：
    • 如果 count == 0，设置当前数为候选人 candidate。
    • 如果当前数 == candidate，count++；否则 count–。
  • 遍历结束，candidate 就是多数元素

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int majorityElement(int[] nums) {
        int count = 0;  // 计数器
        int candidate = 0;  // 候选人
        
        // count 为 0 时，将当前数设置为 candidate
        // 遍历数组，如果当前数为 candidate，count++；否则 count--
        for (int num : nums) {
            if (count == 0) {
                candidate = num;
            }

            count += (candidate == num) ? 1 : -1;
        }

        return candidate;
    }
}

复杂度分析

时间复杂度：O(n)。Boyer-Moore 算法只对数组进行了一次遍历。

空间复杂度：O(1)。Boyer-Moore 算法只需要常数级别的额外空间。

75. 颜色分类

给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地 对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

必须在不使用库内置的 sort 函数的情况下解决这个问题。

**示例 1：**f

1
2
输入：nums = [2,0,2,1,1,0]
输出：[0,0,1,1,2,2]

示例 2：

1
2
输入：nums = [2,0,1]
输出：[0,1,2]

提示：

  • n == nums.length
  • 1 <= n <= 300
  • nums[i] 为 0、1 或 2

进阶：

  • 你能想出一个仅使用常数空间的一趟扫描算法吗？

解题思路

我们用三个指针来维护区间：

  • p0：下一个 0 应该放置的位置；
  • p2：下一个 2 应该放置的位置；
  • i：当前扫描的位置。

遍历 nums：

  • 如果 nums[i] == 0，说明它应该放到最前面：
    • 与 nums[p0] 交换，并移动 p0++ 和 i++。
  • 如果 nums[i] == 2，说明它应该放到最后面：
    • 与 nums[p2] 交换，并移动 p2--（注意此时不能 i++，因为交换过来的数还没处理）。
  • 如果 nums[i] == 1，就继续 i++。

代码实现

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
class Solution {
    public void sortColors(int[] nums) {
        int p0 = 0;  // 下一个 0 的位置
        int p2 = nums.length - 1;  // 下一个 2 的位置
        int i = 0;  // 当前位置

        while (i <= p2) {
            if (nums[i] == 0) {
                swap(nums, i, p0);
                p0++;
                i++;
            } else if (nums[i] == 2) {
                // 还不能移动 i，需要先处理交换过来的数
                swap(nums, i, p2);
                p2--;
            } else {
                i++;
            }
        }
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

复杂度分析

时间复杂度：O(n)，其中 n 是数组 nums 的长度。

空间复杂度：O(1)。

31. 下一个排列

整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。

  • 例如，arr = [1,2,3] ，以下这些都可以视作 arr 的排列：[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1] 。

整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列（即，其元素按升序排列）。

  • 例如，arr = [1,2,3] 的下一个排列是 [1,3,2] 。
  • 类似地，arr = [2,3,1] 的下一个排列是 [3,1,2] 。
  • 而 arr = [3,2,1] 的下一个排列是 [1,2,3] ，因为 [3,2,1] 不存在一个字典序更大的排列。

给你一个整数数组 nums ，找出 nums 的下一个排列。

必须原地修改，只允许使用额外常数空间。

示例 1：

1
2
输入：nums = [1,2,3]
输出：[1,3,2]

示例 2：

1
2
输入：nums = [3,2,1]
输出：[1,2,3]

示例 3：

1
2
输入：nums = [1,1,5]
输出：[1,5,1]

提示：

  • 1 <= nums.length <= 100
  • 0 <= nums[i] <= 100

解题思路

注意到下一个排列总是比当前排列要大，除非该排列已经是最大的排列。我们希望找到一种方法，能够找到一个大于当前序列的新序列，且变大的幅度尽可能小。

阶段 1：从后往前找到第一个下降点 i

  • 即满足 nums[i] < nums[i+1] 的最大下标 i。
  • 说明从 i+1 到末尾是一个非升序序列（最大排列）。
  • 如果找不到这样的 i，说明整个数组是非升序（最大排列），直接反转整个数组即可。

阶段 2：再从后往前找到第一个比 nums[i] 大的数 j

  • 因为 i+1..end 是非升序，找到的第一个比 nums[i] 大的数，一定是“刚刚比它大”的数。

阶段 3：交换 nums[i] 和 nums[j]

  • 这样确保 nums[0..i] 变大，并且尽可能小。

阶段 4：反转 nums[i+1..end]

  • 让尾部恢复成最小字典序。

代码实现

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
37
38
39
class Solution {
    public void nextPermutation(int[] nums) {
        int n = nums.length; 
        int i = n - 2;
        // 1. 找到第一个下降点
        while (i >= 0 && nums[i] >= nums[i + 1]) {
            i--;
        }

        if (i >= 0) {
            // 2. 从后往前找第一个比 nums[i] 大的数 
            int j = n - 1;
            while (j >= 0 && nums[i] >= nums[j]) {
                j--;
            }
            // 3. 交换
            swap(nums, i, j);
        }
        
        // 4. 反转 i+1...end
        reverse(nums, i + 1);
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    private void reverse(int[] nums, int start) {
        int left = start;
        int right = nums.length - 1;
        while (left < right) {
            swap(nums, left, right);
            left++;
            right--;
        }
    }
}

复杂度分析

时间复杂度：O(n)，其中 N 为给定序列的长度。我们至多只需要扫描两次序列，以及进行一次反转操作。

空间复杂度：O(1)，只需要常数的空间存放若干变量。

287. 寻找重复数

给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。

假设 nums 只有 一个重复的整数 ，返回 这个重复的数 。

你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间

示例 1：

1
2
输入：nums = [1,3,4,2,2]
输出：2

示例 2：

1
2
输入：nums = [3,1,3,4,2]
输出：3

示例 3 :

1
2
输入：nums = [3,3,3,3,3]
输出：3

提示：

  • 1 <= n <= 105
  • nums.length == n + 1
  • 1 <= nums[i] <= n
  • nums 中 只有一个整数 出现 两次或多次 ，其余整数均只出现 一次

进阶：

  • 如何证明 nums 中至少存在一个重复的数字?
  • 你可以设计一个线性级时间复杂度 O(n) 的解决方案吗？

解题思路

这其实是 Floyd 判圈算法（龟兔赛跑算法） 的应用。

把数组看成一个链表：

  • 索引是节点，nums[i] 是指针。
  • 由于有重复数，链表中一定会出现“环”。
  • 问题转化为：找出环的入口，就是重复的数字。

阶段 1：找环内的相遇点

  • 用快慢指针：
    • 慢指针 slow = nums[slow]
    • 快指针 fast = nums[nums[fast]]
  • 它们一定会在环中相遇。

阶段 2：找到环的入口（即重复数）

  • 一个指针从头开始 p1 = 0
  • 一个指针从相遇点开始 p2 = slow
  • 两个指针一起走，每次 p1 = nums[p1], p2 = nums[p2]
  • 相遇点就是重复数。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int findDuplicate(int[] nums) {
        int slow = nums[0];
        int fast = nums[0];

        // 找到相遇点
        do {
            slow = nums[slow];
            fast = nums[nums[fast]];
        } while (slow != fast);

        // 找到环入口
        slow = nums[0];
        while (slow != fast) {
            slow = nums[slow];
            fast = nums[fast];
        }

        return slow;
    }
}

复杂度分析

时间复杂度：O(n)。其中 n 为数组长度。算法分为两步：第一步利用快慢指针寻找相遇点，最坏情况下需要 O(n) 步；第二步从头开始再次移动指针寻找环的入口，同样最多 O(n) 步，因此整体复杂度为 O(n)。

空间复杂度：O(1)。只使用了若干指针变量（slow 和 fast），不依赖额外数据结构。