# 力扣Hot100 **Repository Path**: CodingKeep/power-buckle-hot100 ## Basic Information - **Project Name**: 力扣Hot100 - **Description**: 🔥 LeetCode 热题 100 完全攻略，带你完全学会。 - **Primary Language**: Java - **License**: MIT - **Default Branch**: master - **Homepage**: None - **GVP Project**: No ## Statistics - **Stars**: 0 - **Forks**: 0 - **Created**: 2026-02-03 - **Last Updated**: 2026-03-09 ## Categories & Tags **Categories**: Uncategorized **Tags**: None ## README # 🔥 LeetCode 热题 100 完全攻略 > 本文档涵盖 LeetCode 热题 100 的所有题目，每道题都包含： > - 📝 题目描述 > - 💡 解题思路（为什么这样做） > - 🎯 关键点（踩坑点） > - 💻 代码实现（多种解法） > - ⏱️ 复杂度分析 --- ## 目录 1. [哈希](#一哈希) 2. [双指针](#二双指针) 3. [滑动窗口](#三滑动窗口) 4. [子串](#四子串) 5. [普通数组](#五普通数组) 6. [矩阵](#六矩阵) 7. [链表](#七链表) 8. [二叉树](#八二叉树) 9. [图论](#九图论) 10. [回溯](#十回溯) 11. [二分查找](#十一二分查找) 12. [栈](#十二栈) 13. [堆](#十三堆) 14. [贪心算法](#十四贪心算法) 15. [动态规划](#十五动态规划) 16. [多维动态规划](#十六多维动态规划) 17. [技巧](#十七技巧) --- ## 一、哈希 ### 1. 两数之和 ⭐ **LeetCode 1** **📝 题目描述** 给定一个整数数组 `nums` 和一个目标值 `target`，找出数组中和为目标值的两个数的索引。 **💡 解题思路** **思路演进：** 1. **暴力法**：两层循环，枚举所有两数组合 → O(n²) 2. **哈希优化**：边遍历边查找，用空间换时间 → O(n) **为什么用哈希表？** - 我们要找 `nums[i] + nums[j] = target` - 换个角度：对于每个 `nums[i]`，我们要找 `target - nums[i]` 是否存在 - 哈希表的查找是 O(1)，完美解决！ **关键洞察：** ``` 遍历到 nums[i] 时： 1. 计算 complement = target - nums[i] 2. 查询哈希表中是否有 complement 3. 如果有 → 找到答案！ 4. 如果没有 → 把 nums[i] 存入哈希表，供后续查找 ``` **🎯 关键点** - 先查后存：避免同一个元素使用两次 - 存的是 `{值: 索引}`，因为最后要返回索引 **💻 代码实现** ```java // 方法一：暴力法 O(n²) - 理解题意 public int[] twoSum(int[] nums, int target) { for (int i = 0; i < nums.length; i++) { for (int j = i + 1; j < nums.length; j++) { if (nums[i] + nums[j] == target) { return new int[]{i, j}; } } } return new int[]{}; } // 方法二：哈希表 O(n) - 最优解 public int[] twoSum(int[] nums, int target) { Map map = new HashMap<>(); // 值 -> 索引 for (int i = 0; i < nums.length; i++) { int complement = target - nums[i]; // 需要找的另一个数 // 先查：看之前遍历过的数中有没有 complement if (map.containsKey(complement)) { return new int[]{map.get(complement), i}; } // 后存：把当前数存入，供后续遍历查找 map.put(nums[i], i); } return new int[]{}; } ``` **⏱️ 复杂度分析** - 时间：O(n)，遍历一次 - 空间：O(n)，哈希表存储 --- ### 2. 字母异位词分组 ⭐⭐ **LeetCode 49** **📝 题目描述** 给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同但排列不同的字符串。 示例：`["eat","tea","tan","ate","nat","bat"]` → `[["bat"],["nat","tan"],["ate","eat","tea"]]` **💡 解题思路** **什么是字母异位词？** - 包含相同字母，只是顺序不同 - 如 "eat" 和 "tea"，都包含 e、a、t 各一个 **如何判断两个词是异位词？** 1. **排序法**：排序后相同 → "eat" 排序后是 "aet"，"tea" 排序后也是 "aet" 2. **计数法**：统计每个字母出现次数，次数相同则是异位词 **解题关键：** - 找一个"特征"来表示一组异位词 - 用这个特征作为哈希表的 Key ``` "eat" → 排序 → "aet" (作为Key) "tea" → 排序 → "aet" (相同Key，分到同一组) "ate" → 排序 → "aet" (相同Key，分到同一组) ``` **🎯 关键点** - 排序后的字符串作为分组的 Key - 字符数组转字符串：`new String(charArray)` **💻 代码实现** ```java // 方法一：排序法（推荐，简洁） public List> groupAnagrams(String[] strs) { Map> map = new HashMap<>(); for (String str : strs) { // 1. 将字符串转为字符数组并排序 char[] chars = str.toCharArray(); Arrays.sort(chars); String key = new String(chars); // "eat" → "aet" // 2. 以排序后的字符串为 Key 分组 map.computeIfAbsent(key, k -> new ArrayList<>()).add(str); } return new ArrayList<>(map.values()); } // 方法二：计数法（避免排序） public List> groupAnagrams(String[] strs) { Map> map = new HashMap<>(); for (String str : strs) { // 统计每个字母出现次数 int[] count = new int[26]; for (char c : str.toCharArray()) { count[c - 'a']++; } // 将计数数组转为字符串作为 Key // 如 "eat" → "1#0#0#0#1#...#1#0#..." (a=1, e=1, t=1) StringBuilder sb = new StringBuilder(); for (int i = 0; i < 26; i++) { sb.append(count[i]).append('#'); } String key = sb.toString(); map.computeIfAbsent(key, k -> new ArrayList<>()).add(str); } return new ArrayList<>(map.values()); } ``` **⏱️ 复杂度分析** - 排序法：时间 O(n × k log k)，k 是字符串最大长度 - 计数法：时间 O(n × k)，空间 O(n × k) --- ### 3. 最长连续序列 ⭐⭐ **LeetCode 128** **📝 题目描述** 给定一个未排序的整数数组，找出最长连续序列的长度。要求时间复杂度 O(n)。 示例：`[100, 4, 200, 1, 3, 2]` → 4（序列 [1,2,3,4]） **💡 解题思路** **为什么不能排序？** - 排序是 O(n log n)，题目要求 O(n) **核心思想：** 1. 把所有数放入 HashSet（去重 + O(1) 查找） 2. 对于每个数，检查它是否是序列的"起点" 3. 如果是起点，就往后数，统计序列长度 **如何判断是"起点"？** - 如果 `num - 1` 不在集合中，说明 `num` 是某个序列的起点 - 这样避免重复计数（不从序列中间开始数） ``` 数组: [100, 4, 200, 1, 3, 2] Set: {100, 4, 200, 1, 3, 2} 遍历: - 100: 99不在Set中 → 是起点 → 100,101? → 长度1 - 4: 3在Set中 → 不是起点，跳过 - 200: 199不在Set中 → 是起点 → 长度1 - 1: 0不在Set中 → 是起点 → 1,2,3,4,5? → 长度4 ✓ - 3: 2在Set中 → 不是起点，跳过 - 2: 1在Set中 → 不是起点，跳过 ``` **🎯 关键点** - 只从序列起点开始计数，避免重复 - 用 HashSet 而不是 HashMap，因为只需要判断存在性 **💻 代码实现** ```java public int longestConsecutive(int[] nums) { if (nums.length == 0) return 0; // 1. 所有数放入 Set Set set = new HashSet<>(); for (int num : nums) { set.add(num); } int maxLength = 0; // 2. 遍历每个数 for (int num : set) { // 注意：遍历 set 而不是 nums，避免重复元素 // 3. 只有当 num 是序列起点时才计数 if (!set.contains(num - 1)) { int currentNum = num; int currentLength = 1; // 4. 往后数，统计连续序列长度 while (set.contains(currentNum + 1)) { currentNum++; currentLength++; } maxLength = Math.max(maxLength, currentLength); } } return maxLength; } ``` **⏱️ 复杂度分析** - 时间：O(n)，虽然有嵌套循环，但每个数最多被访问两次 - 空间：O(n)，HashSet 存储 --- ## 二、双指针 ### 4. 移动零 ⭐ **LeetCode 283** **📝 题目描述** 给定一个数组，将所有的 0 移动到数组末尾，同时保持非零元素的相对顺序。必须原地操作。 示例：`[0,1,0,3,12]` → `[1,3,12,0,0]` **💡 解题思路** **双指针思想：** - `slow`：指向下一个非零元素应该放的位置 - `fast`：遍历数组，找非零元素 ``` 初始: [0, 1, 0, 3, 12] slow=0, fast=0 fast=0: nums[0]=0, 跳过 fast=1: nums[1]=1≠0, 交换 nums[0]和nums[1], slow++ [1, 0, 0, 3, 12], slow=1 fast=2: nums[2]=0, 跳过 fast=3: nums[3]=3≠0, 交换 nums[1]和nums[3], slow++ [1, 3, 0, 0, 12], slow=2 fast=4: nums[4]=12≠0, 交换 nums[2]和nums[4], slow++ [1, 3, 12, 0, 0], slow=3 ``` **🎯 关键点** - slow 左边都是处理好的非零元素 - fast 用来探索新的非零元素 **💻 代码实现** ```java // 方法一：交换法（推荐） public void moveZeroes(int[] nums) { int slow = 0; // 非零元素应该放的位置 for (int fast = 0; fast < nums.length; fast++) { if (nums[fast] != 0) { // 交换 int temp = nums[slow]; nums[slow] = nums[fast]; nums[fast] = temp; slow++; } } } // 方法二：覆盖法 public void moveZeroes(int[] nums) { int slow = 0; // 第一遍：把非零元素依次放到前面 for (int fast = 0; fast < nums.length; fast++) { if (nums[fast] != 0) { nums[slow++] = nums[fast]; } } // 第二遍：剩余位置填 0 while (slow < nums.length) { nums[slow++] = 0; } } ``` **⏱️ 复杂度分析** - 时间：O(n) - 空间：O(1) --- ### 5. 盛最多水的容器 ⭐⭐ **LeetCode 11** **📝 题目描述** 给定 n 个非负整数表示每个柱子的高度，找出两个柱子组成的容器能盛最多的水。 **💡 解题思路** **暴力法**：枚举所有组合 O(n²) **双指针优化：** - 水量 = `min(height[left], height[right]) × (right - left)` - 宽度：left 和 right 之间的距离 - 高度：取决于较矮的柱子（木桶效应） **为什么双指针有效？** ``` 初始：left=0, right=n-1（最宽） 移动策略：移动较矮的指针！ 为什么？假设 height[left] < height[right]： - 如果移动 right（较高的），宽度减小，高度不可能超过 height[left] → 面积只会变小或不变 - 如果移动 left（较矮的），宽度减小，但高度可能增大 → 面积有可能变大 所以：移动较矮的指针，才有机会找到更大的容器！ ``` **🎯 关键点** - 永远移动较矮的指针 - 每次移动都排除了不可能的情况 **💻 代码实现** ```java public int maxArea(int[] height) { int left = 0, right = height.length - 1; int maxWater = 0; while (left < right) { // 计算当前水量 int h = Math.min(height[left], height[right]); int w = right - left; maxWater = Math.max(maxWater, h * w); // 移动较矮的指针 if (height[left] < height[right]) { left++; } else { right--; } } return maxWater; } ``` **⏱️ 复杂度分析** - 时间：O(n) - 空间：O(1) --- ### 6. 三数之和 ⭐⭐ **LeetCode 15** **📝 题目描述** 给定一个数组，找出所有和为 0 的三元组，不能重复。 示例：`[-1,0,1,2,-1,-4]` → `[[-1,-1,2],[-1,0,1]]` **💡 解题思路** **核心思想：固定一个数，问题变成两数之和** ``` 排序后: [-4, -1, -1, 0, 1, 2] 固定 nums[i]，在 [i+1, n-1] 中找两数之和等于 -nums[i] 这就变成了"两数之和"问题，用双指针解决！ ``` **去重策略：** 1. 排序后，相同的数会相邻 2. 固定数去重：`if (i > 0 && nums[i] == nums[i-1]) continue` 3. 左指针去重：`while (left < right && nums[left] == nums[left-1]) left++` 4. 右指针去重：`while (left < right && nums[right] == nums[right+1]) right--` **🎯 关键点** - 先排序！ - 三处去重，缺一不可 - 固定数 > 0 可以提前结束（优化） **💻 代码实现** ```java public List> threeSum(int[] nums) { List> result = new ArrayList<>(); // 1. 排序 Arrays.sort(nums); // 2. 固定第一个数 for (int i = 0; i < nums.length - 2; i++) { // 优化：如果最小的数都大于0，不可能和为0 if (nums[i] > 0) break; // 去重：跳过重复的固定数 if (i > 0 && nums[i] == nums[i - 1]) continue; // 3. 双指针找另外两个数 int left = i + 1, right = nums.length - 1; int target = -nums[i]; // 需要找的和 while (left < right) { int sum = nums[left] + nums[right]; if (sum == target) { result.add(Arrays.asList(nums[i], nums[left], nums[right])); // 去重：跳过重复的左指针 while (left < right && nums[left] == nums[left + 1]) left++; // 去重：跳过重复的右指针 while (left < right && nums[right] == nums[right - 1]) right--; left++; right--; } else if (sum < target) { left++; } else { right--; } } } return result; } ``` **⏱️ 复杂度分析** - 时间：O(n²)，排序 O(n log n) + 双指针 O(n²) - 空间：O(1)，不考虑结果数组 --- ### 7. 接雨水 ⭐⭐⭐ **LeetCode 42** **📝 题目描述** 给定柱子高度数组，计算能接多少雨水。 **💡 解题思路** **核心公式：每个位置能接的水 = min(左边最高, 右边最高) - 当前高度** ``` 例如: [0,1,0,2,1,0,1,3,2,1,2,1] 位置2的水量: - 左边最高: max(0,1) = 1 - 右边最高: max(2,1,0,1,3,2,1,2,1) = 3 - 当前高度: 0 - 水量: min(1,3) - 0 = 1 ``` **方法一：预处理（好理解）** - 预先计算每个位置左边最大值和右边最大值 **方法二：双指针（空间优化）** - 用两个指针从两端向中间移动 - 维护左边最大值和右边最大值 **双指针的关键洞察：** ``` 如果 leftMax < rightMax： 当前位置的水量由 leftMax 决定（短板效应） 可以安全计算 left 位置的水量，然后 left++ 如果 leftMax >= rightMax： 当前位置的水量由 rightMax 决定 可以安全计算 right 位置的水量，然后 right-- ``` **🎯 关键点** - 理解"木桶效应"：水量取决于较矮的边 - 双指针：哪边矮就处理哪边 **💻 代码实现** ```java // 方法一：预处理数组（好理解） public int trap(int[] height) { int n = height.length; if (n == 0) return 0; // leftMax[i] = max(height[0..i]) int[] leftMax = new int[n]; leftMax[0] = height[0]; for (int i = 1; i < n; i++) { leftMax[i] = Math.max(leftMax[i - 1], height[i]); } // rightMax[i] = max(height[i..n-1]) int[] rightMax = new int[n]; rightMax[n - 1] = height[n - 1]; for (int i = n - 2; i >= 0; i--) { rightMax[i] = Math.max(rightMax[i + 1], height[i]); } // 计算每个位置的水量 int water = 0; for (int i = 0; i < n; i++) { water += Math.min(leftMax[i], rightMax[i]) - height[i]; } return water; } // 方法二：双指针（空间优化） public int trap(int[] height) { int left = 0, right = height.length - 1; int leftMax = 0, rightMax = 0; int water = 0; while (left < right) { // 更新左右最大值 leftMax = Math.max(leftMax, height[left]); rightMax = Math.max(rightMax, height[right]); // 哪边矮就处理哪边 if (leftMax < rightMax) { water += leftMax - height[left]; // 一定不会溢出 left++; } else { water += rightMax - height[right]; right--; } } return water; } ``` **⏱️ 复杂度分析** - 预处理：时间 O(n)，空间 O(n) - 双指针：时间 O(n)，空间 O(1) --- ## 三、滑动窗口 ### 8. 无重复字符的最长子串 ⭐⭐ **LeetCode 3** **📝 题目描述** 给定一个字符串，找出不含重复字符的最长子串的长度。 示例：`"abcabcbb"` → 3（"abc"） **💡 解题思路** **滑动窗口模板：** ``` 维护一个窗口 [left, right]，保证窗口内没有重复字符 1. right 向右扩展，加入新字符 2. 如果新字符导致重复，left 向右收缩，直到没有重复 3. 更新最大长度 ``` **如何判断重复？** - 用 Set 存储窗口内的字符 - 或用 Map 存储字符最后出现的位置（优化） ``` "abcabcbb" ^^^ → 窗口 "abc", 长度3 left=0, right=2 right=3, 加入'a'，'a'已存在 → left 移动到'a'之后，left=1 → 窗口 "bca", 长度3 继续...最大长度3 ``` **🎯 关键点** - 窗口内保持"无重复"的不变性 - 遇到重复时收缩左边界 **💻 代码实现** ```java // 方法一：HashSet（标准滑动窗口） public int lengthOfLongestSubstring(String s) { Set window = new HashSet<>(); int left = 0, maxLen = 0; for (int right = 0; right < s.length(); right++) { char c = s.charAt(right); // 如果字符已在窗口中，收缩左边界 while (window.contains(c)) { window.remove(s.charAt(left)); left++; } // 加入新字符 window.add(c); // 更新最大长度 maxLen = Math.max(maxLen, right - left + 1); } return maxLen; } // 方法二：HashMap（优化，直接跳转） public int lengthOfLongestSubstring(String s) { Map lastIndex = new HashMap<>(); // 字符 -> 最后出现位置 int left = 0, maxLen = 0; for (int right = 0; right < s.length(); right++) { char c = s.charAt(right); // 如果字符之前出现过，且在当前窗口内 if (lastIndex.containsKey(c) && lastIndex.get(c) >= left) { // 直接跳到重复字符的下一位 left = lastIndex.get(c) + 1; } lastIndex.put(c, right); maxLen = Math.max(maxLen, right - left + 1); } return maxLen; } ``` **⏱️ 复杂度分析** - 时间：O(n) - 空间：O(min(m, n))，m 是字符集大小 --- ### 9. 找到字符串中所有字母异位词 ⭐⭐ **LeetCode 438** **📝 题目描述** 给定两个字符串 s 和 p，找出 s 中所有 p 的字母异位词的起始索引。 示例：s = "cbaebabacd", p = "abc" → [0, 6] **💡 解题思路** **固定窗口大小的滑动窗口：** - 窗口大小固定为 p 的长度 - 比较窗口内字符频率和 p 的字符频率是否相同 ``` s = "cbaebabacd", p = "abc" p的频率: {a:1, b:1, c:1} 窗口滑动: [cba]ebabacd → {c:1,b:1,a:1} = p的频率 ✓ → 索引0 c[bae]babacd → {b:1,a:1,e:1} ≠ p的频率 cb[aeb]abacd → {a:1,e:1,b:1} ≠ p的频率 ... cbaeba[bac]d → {b:1,a:1,c:1} = p的频率 ✓ → 索引6 ``` **优化：用 valid 计数器** - 不用每次比较整个频率数组 - 维护"有多少种字符的频率已经满足" **🎯 关键点** - 窗口大小固定为 p.length() - 用字符频率数组比较 **💻 代码实现** ```java public List findAnagrams(String s, String p) { List result = new ArrayList<>(); if (s.length() < p.length()) return result; // p 的字符频率 int[] need = new int[26]; for (char c : p.toCharArray()) { need[c - 'a']++; } // 窗口的字符频率 int[] window = new int[26]; for (int i = 0; i < s.length(); i++) { // 右边界字符加入窗口 window[s.charAt(i) - 'a']++; // 窗口大小超过 p.length()，左边界移出 if (i >= p.length()) { window[s.charAt(i - p.length()) - 'a']--; } // 窗口大小等于 p.length() 时，比较频率 if (i >= p.length() - 1 && Arrays.equals(window, need)) { result.add(i - p.length() + 1); } } return result; } // 优化版：用 valid 计数 public List findAnagrams(String s, String p) { List result = new ArrayList<>(); int[] need = new int[26]; int[] window = new int[26]; int needCount = 0; // p 中有多少种不同字符 for (char c : p.toCharArray()) { if (need[c - 'a'] == 0) needCount++; need[c - 'a']++; } int valid = 0; // 当前满足的字符种类数 int left = 0; for (int right = 0; right < s.length(); right++) { char c = s.charAt(right); window[c - 'a']++; if (window[c - 'a'] == need[c - 'a']) valid++; // 窗口过大，收缩 if (right - left + 1 > p.length()) { char d = s.charAt(left); if (window[d - 'a'] == need[d - 'a']) valid--; window[d - 'a']--; left++; } // 满足条件 if (valid == needCount) { result.add(left); } } return result; } ``` **⏱️ 复杂度分析** - 时间：O(n) - 空间：O(1)，固定 26 个字母 --- ## 四、子串 ### 10. 和为 K 的子数组 ⭐⭐ **LeetCode 560** **📝 题目描述** 给定一个整数数组和一个整数 k，统计数组中和为 k 的连续子数组的个数。 示例：`[1,1,1]`, k=2 → 2（[1,1] 出现两次） **💡 解题思路** **暴力法**：枚举所有子数组 O(n²) **前缀和 + 哈希表优化：** ``` 前缀和: prefix[i] = nums[0] + nums[1] + ... + nums[i-1] 子数组 [i, j) 的和 = prefix[j] - prefix[i] 如果 prefix[j] - prefix[i] = k 那么 prefix[i] = prefix[j] - k 问题转化为：对于每个 prefix[j]，有多少个之前的 prefix[i] 等于 prefix[j] - k ``` **用哈希表记录：每个前缀和出现的次数** ``` 数组: [1, 1, 1], k = 2 前缀和: [0, 1, 2, 3] (prefix[0] = 0) j=1: prefix=1, 找 1-2=-1, count=0 j=2: prefix=2, 找 2-2=0, map中0出现1次, count=1 j=3: prefix=3, 找 3-2=1, map中1出现1次, count=2 答案: 2 ``` **🎯 关键点** - 前缀和数组要包含 prefix[0] = 0 - 边遍历边统计，避免重复计算 **💻 代码实现** ```java public int subarraySum(int[] nums, int k) { // map: 前缀和 -> 出现次数 Map prefixCount = new HashMap<>(); prefixCount.put(0, 1); // 前缀和为0出现1次（空前缀） int prefix = 0; // 当前前缀和 int count = 0; for (int num : nums) { prefix += num; // 查找之前有多少个前缀和等于 prefix - k count += prefixCount.getOrDefault(prefix - k, 0); // 记录当前前缀和 prefixCount.merge(prefix, 1, Integer::sum); } return count; } ``` **⏱️ 复杂度分析** - 时间：O(n) - 空间：O(n) --- ### 11. 滑动窗口最大值 ⭐⭐⭐ **LeetCode 239** **📝 题目描述** 给定一个数组和滑动窗口大小 k，返回滑动窗口中的最大值。 示例：`[1,3,-1,-3,5,3,6,7]`, k=3 → `[3,3,5,5,6,7]` **💡 解题思路** **单调队列：维护一个递减的双端队列** ``` 队列存储：索引（不是值），方便判断是否出窗口 规则： 1. 新元素入队前，移除所有比它小的元素（因为它们不可能成为最大值了） 2. 队首可能已经出窗口，需要检查移除 3. 队首始终是当前窗口的最大值 示例: [1,3,-1,-3,5,3,6,7], k=3 i=0: 1入队, 队列[0] i=1: 3>1, 移除1, 队列[1] i=2: -1<3, 入队, 队列[1,2], 窗口满 → max=3 i=3: -3<-1, 入队, 队列[1,2,3], 1出窗口移除, 队列[2,3] → max=3 i=4: 5>-3>-1, 移除所有, 队列[4] → max=5 ... ``` **🎯 关键点** - 队列存索引，不是值 - 保持队列单调递减 - 每个元素最多入队出队各一次，总体 O(n) **💻 代码实现** ```java public int[] maxSlidingWindow(int[] nums, int k) { if (nums.length == 0 || k == 0) return new int[0]; int n = nums.length; int[] result = new int[n - k + 1]; // 单调递减队列，存储索引 Deque deque = new ArrayDeque<>(); for (int i = 0; i < n; i++) { // 1. 移除出窗口的元素（从队首） while (!deque.isEmpty() && deque.peekFirst() <= i - k) { deque.pollFirst(); } // 2. 移除比当前元素小的元素（从队尾） while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) { deque.pollLast(); } // 3. 当前元素入队 deque.offerLast(i); // 4. 窗口形成后，记录最大值 if (i >= k - 1) { result[i - k + 1] = nums[deque.peekFirst()]; } } return result; } ``` **⏱️ 复杂度分析** - 时间：O(n)，每个元素最多入队出队各一次 - 空间：O(k)，队列最多存 k 个元素 --- ### 12. 最小覆盖子串 ⭐⭐⭐ **LeetCode 76** **📝 题目描述** 给定字符串 s 和 t，找出 s 中包含 t 所有字符的最小子串。 示例：s = "ADOBECODEBANC", t = "ABC" → "BANC" **💡 解题思路** **经典滑动窗口模板：** ``` 1. 扩展右边界，直到窗口包含 t 的所有字符 2. 收缩左边界，尝试找更小的窗口 3. 记录最小的满足条件的窗口 ``` **如何判断"包含所有字符"？** - need：t 中每个字符需要的数量 - window：当前窗口中每个字符的数量 - valid：当前有多少种字符的数量已满足 ``` s = "ADOBECODEBANC", t = "ABC" need = {A:1, B:1, C:1} 扩展: [A]DOBECODEBANC → window={A:1}, valid=1 [ADOBEC]ODEBANC → window={A:1,D:1,O:1,B:1,E:1,C:1}, valid=3 ✓ 收缩: A[DOBEC]ODEBANC → valid=2 ✗ 停止收缩 继续扩展... ... 最终找到 "BANC" ``` **🎯 关键点** - 扩展直到满足，收缩尝试优化 - valid == need.size() 表示包含所有字符 **💻 代码实现** ```java public String minWindow(String s, String t) { if (s.length() < t.length()) return ""; // t 中每个字符的需求 Map need = new HashMap<>(); for (char c : t.toCharArray()) { need.merge(c, 1, Integer::sum); } // 窗口中的字符计数 Map window = new HashMap<>(); int left = 0, valid = 0; int start = 0, minLen = Integer.MAX_VALUE; for (int right = 0; right < s.length(); right++) { char c = s.charAt(right); // 扩展：右边界字符加入窗口 if (need.containsKey(c)) { window.merge(c, 1, Integer::sum); if (window.get(c).equals(need.get(c))) { valid++; } } // 收缩：当窗口满足条件时 while (valid == need.size()) { // 更新最小窗口 if (right - left + 1 < minLen) { minLen = right - left + 1; start = left; } // 左边界字符移出窗口 char d = s.charAt(left); if (need.containsKey(d)) { if (window.get(d).equals(need.get(d))) { valid--; } window.merge(d, -1, Integer::sum); } left++; } } return minLen == Integer.MAX_VALUE ? "" : s.substring(start, start + minLen); } ``` **⏱️ 复杂度分析** - 时间：O(n + m)，n 是 s 长度，m 是 t 长度 - 空间：O(k)，k 是字符集大小 --- ## 五、普通数组 ### 13. 最大子数组和 ⭐⭐ **LeetCode 53** **📝 题目描述** 找出一个具有最大和的连续子数组，返回其最大和。 示例：`[-2,1,-3,4,-1,2,1,-5,4]` → 6（子数组 [4,-1,2,1]） **💡 解题思路** **动态规划思想：** ``` dp[i] = 以 nums[i] 结尾的最大子数组和 转移方程： dp[i] = max(dp[i-1] + nums[i], nums[i]) 解释： - 要么接上前面的子数组：dp[i-1] + nums[i] - 要么从 nums[i] 重新开始：nums[i] - 取较大者 ``` **空间优化：dp[i] 只依赖 dp[i-1]，用一个变量即可** ``` 数组: [-2, 1, -3, 4, -1, 2, 1, -5, 4] i=0: dp=-2, max=-2 i=1: dp=max(-2+1, 1)=1, max=1 i=2: dp=max(1-3, -3)=-2, max=1 i=3: dp=max(-2+4, 4)=4, max=4 i=4: dp=max(4-1, -1)=3, max=4 i=5: dp=max(3+2, 2)=5, max=5 i=6: dp=max(5+1, 1)=6, max=6 ✓ ... ``` **🎯 关键点** - 核心决策：是否要接上前面的 - 前面和为负数，不如重新开始 **💻 代码实现** ```java // 方法一：动态规划 public int maxSubArray(int[] nums) { int dp = nums[0]; // 以当前位置结尾的最大和 int maxSum = nums[0]; for (int i = 1; i < nums.length; i++) { // 要么接上前面，要么重新开始 dp = Math.max(dp + nums[i], nums[i]); maxSum = Math.max(maxSum, dp); } return maxSum; } // 更直观的写法 public int maxSubArray(int[] nums) { int currentSum = 0; // 当前连续和 int maxSum = Integer.MIN_VALUE; for (int num : nums) { // 如果 currentSum < 0，不如重新开始 if (currentSum < 0) { currentSum = 0; } currentSum += num; maxSum = Math.max(maxSum, currentSum); } return maxSum; } ``` **⏱️ 复杂度分析** - 时间：O(n) - 空间：O(1) --- ### 14. 合并区间 ⭐⭐ **LeetCode 56** **📝 题目描述** 合并所有重叠的区间。 示例：`[[1,3],[2,6],[8,10],[15,18]]` → `[[1,6],[8,10],[15,18]]` **💡 解题思路** **步骤：** 1. 按起点排序 2. 遍历，如果当前区间和上一个区间重叠，合并 3. 如果不重叠，加入结果 ``` 排序后: [[1,3],[2,6],[8,10],[15,18]] 遍历: result = [[1,3]] [2,6]: 2 <= 3, 重叠, 合并 → result = [[1,6]] [8,10]: 8 > 6, 不重叠 → result = [[1,6],[8,10]] [15,18]: 15 > 10, 不重叠 → result = [[1,6],[8,10],[15,18]] ``` **判断重叠：当前起点 <= 上一个终点** **🎯 关键点** - 排序是关键 - 合并时终点取较大值：`max(prev[1], curr[1])` **💻 代码实现** ```java public int[][] merge(int[][] intervals) { if (intervals.length <= 1) return intervals; // 1. 按起点排序 Arrays.sort(intervals, (a, b) -> a[0] - b[0]); List result = new ArrayList<>(); result.add(intervals[0]); // 2. 遍历合并 for (int i = 1; i < intervals.length; i++) { int[] last = result.get(result.size() - 1); int[] curr = intervals[i]; if (curr[0] <= last[1]) { // 重叠，合并（更新终点） last[1] = Math.max(last[1], curr[1]); } else { // 不重叠，加入结果 result.add(curr); } } return result.toArray(new int[result.size()][]); } ``` **⏱️ 复杂度分析** - 时间：O(n log n)，排序 - 空间：O(n)，结果数组 --- ### 15. 轮转数组 ⭐⭐ **LeetCode 189** **📝 题目描述** 将数组向右轮转 k 个位置。 示例：`[1,2,3,4,5,6,7]`, k=3 → `[5,6,7,1,2,3,4]` **💡 解题思路** **方法一：额外数组** - 新位置 = (原位置 + k) % n **方法二：三次翻转（原地，推荐）** ``` 原数组: [1, 2, 3, 4, 5, 6, 7], k=3 1. 整体翻转: [7, 6, 5, 4, 3, 2, 1] 2. 翻转前k个: [5, 6, 7, 4, 3, 2, 1] 3. 翻转后n-k个: [5, 6, 7, 1, 2, 3, 4] ✓ ``` **为什么三次翻转有效？** ``` 原数组可以看作两部分: [A][B] 目标: [B][A] 整体翻转: [A^R][B^R] (^R 表示翻转) 翻转前k个: [B][B^R] 变成 [B]... 不对 重新理解: [1,2,3,4 | 5,6,7] → [5,6,7 | 1,2,3,4] A B B A 整体翻转: [7,6,5 | 4,3,2,1] = [B^R | A^R] 翻转前3: [5,6,7 | 4,3,2,1] = [B | A^R] 翻转后4: [5,6,7 | 1,2,3,4] = [B | A] ✓ ``` **🎯 关键点** - k 可能大于 n，需要 k %= n - 三次翻转的顺序 **💻 代码实现** ```java // 方法一：三次翻转（原地） public void rotate(int[] nums, int k) { int n = nums.length; k %= n; // 处理 k > n 的情况 reverse(nums, 0, n - 1); // 整体翻转 reverse(nums, 0, k - 1); // 翻转前 k 个 reverse(nums, k, n - 1); // 翻转后 n-k 个 } private void reverse(int[] nums, int left, int right) { while (left < right) { int temp = nums[left]; nums[left] = nums[right]; nums[right] = temp; left++; right--; } } // 方法二：额外数组 public void rotate(int[] nums, int k) { int n = nums.length; int[] temp = new int[n]; for (int i = 0; i < n; i++) { temp[(i + k) % n] = nums[i]; } System.arraycopy(temp, 0, nums, 0, n); } ``` **⏱️ 复杂度分析** - 三次翻转：时间 O(n)，空间 O(1) - 额外数组：时间 O(n)，空间 O(n) --- ### 16. 除自身以外数组的乘积 ⭐⭐ **LeetCode 238** **📝 题目描述** 给定数组 nums，返回数组 answer，其中 answer[i] 等于 nums 中除 nums[i] 之外所有元素的乘积。不能使用除法，要求 O(n)。 示例：`[1,2,3,4]` → `[24,12,8,6]` **💡 解题思路** **不能用除法，那就用乘法：** ``` answer[i] = nums[i]左边所有数的乘积 × nums[i]右边所有数的乘积 = prefix[i] × suffix[i] ``` **两次遍历：** 1. 从左到右，计算左边乘积 2. 从右到左，乘上右边乘积 ``` nums = [1, 2, 3, 4] 从左到右（左边乘积）: answer = [1, 1, 2, 6] 1 1 1×1 1×2 从右到左（乘上右边乘积）: answer = [24, 12, 8, 6] 1×24 1×12 2×4 6×1 ``` **🎯 关键点** - 用 answer 数组存储中间结果，节省空间 - 第一遍算左积，第二遍乘右积 **💻 代码实现** ```java public int[] productExceptSelf(int[] nums) { int n = nums.length; int[] answer = new int[n]; // 第一遍：从左到右，计算每个位置左边的乘积 answer[0] = 1; for (int i = 1; i < n; i++) { answer[i] = answer[i - 1] * nums[i - 1]; } // 第二遍：从右到左，乘上每个位置右边的乘积 int rightProduct = 1; for (int i = n - 1; i >= 0; i--) { answer[i] *= rightProduct; rightProduct *= nums[i]; } return answer; } ``` **⏱️ 复杂度分析** - 时间：O(n) - 空间：O(1)，不算输出数组 --- ### 17. 缺失的第一个正数 ⭐⭐⭐ **LeetCode 41** **📝 题目描述** 给定一个未排序的整数数组，找出其中没有出现的最小的正整数。要求时间 O(n)，空间 O(1)。 示例：`[3,4,-1,1]` → 2 **💡 解题思路** **核心洞察：** - 答案一定在 [1, n+1] 范围内 - 如果数组包含 1 到 n，答案是 n+1 - 否则，答案是 [1, n] 中缺失的某个数 **原地哈希：把数组本身当作哈希表** - 规则：把数字 x 放到索引 x-1 的位置 - 即 nums[i] 应该等于 i+1 ``` [3, 4, -1, 1] 交换: i=0: nums[0]=3, 应该在索引2, 交换 → [-1, 4, 3, 1] i=0: nums[0]=-1, 不在范围内, 跳过 i=1: nums[1]=4, 应该在索引3, 交换 → [-1, 1, 3, 4] i=1: nums[1]=1, 应该在索引0, 交换 → [1, -1, 3, 4] i=1: nums[1]=-1, 跳过 i=2: nums[2]=3, 已在正确位置 i=3: nums[3]=4, 已在正确位置 检查: [1, -1, 3, 4] i=0: nums[0]=1 ✓ i=1: nums[1]=-1 ≠ 2 → 答案是 2 ``` **🎯 关键点** - 只处理 [1, n] 范围内的数 - 用 while 循环处理连续交换 - 避免死循环：nums[nums[i]-1] == nums[i] 时跳过 **💻 代码实现** ```java public int firstMissingPositive(int[] nums) { int n = nums.length; // 原地哈希：把 nums[i] 放到索引 nums[i]-1 的位置 for (int i = 0; i < n; i++) { // 只处理 [1, n] 范围内的数 while (nums[i] >= 1 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) { // 目标位置的值不对 // 交换 int targetIndex = nums[i] - 1; int temp = nums[targetIndex]; nums[targetIndex] = nums[i]; nums[i] = temp; } } // 找第一个 nums[i] != i+1 的位置 for (int i = 0; i < n; i++) { if (nums[i] != i + 1) { return i + 1; } } // 如果 1 到 n 都有，答案是 n+1 return n + 1; } ``` **⏱️ 复杂度分析** - 时间：O(n)，每个数最多被交换一次 - 空间：O(1) --- ## 六、矩阵 ### 18. 矩阵置零 ⭐⭐ **LeetCode 73** **📝 题目描述** 如果矩阵的某个元素为 0，则将其所在行和列的所有元素都置为 0。要求原地操作。 **💡 解题思路** **不能边遍历边置零（会影响后续判断）** **用第一行第一列作为标记：** ``` 1. 先记录第一行和第一列是否原本就有0 2. 用第一行和第一列标记哪些行/列需要置零 3. 根据标记置零（从[1,1]开始） 4. 最后处理第一行和第一列 ``` ``` 原矩阵: [1, 1, 1] [1, 0, 1] [1, 1, 1] 标记后（[1][1]有0，标记到[0][1]和[1][0]）: [1, 0, 1] ← 第0行的第1列标记为0 [0, 0, 1] ← 第1行的第0列标记为0 [1, 1, 1] 根据标记置零: [1, 0, 1] [0, 0, 0] ← 第1行全置零 [1, 0, 1] ← 第1列全置零 ``` **🎯 关键点** - 用第一行/列作为标记数组 - 需要额外记录第一行/列本身是否需要置零 **💻 代码实现** ```java public void setZeroes(int[][] matrix) { int m = matrix.length, n = matrix[0].length; boolean firstRowZero = false, firstColZero = false; // 1. 检查第一列是否有0 for (int i = 0; i < m; i++) { if (matrix[i][0] == 0) firstColZero = true; } // 2. 检查第一行是否有0 for (int j = 0; j < n; j++) { if (matrix[0][j] == 0) firstRowZero = true; } // 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. 根据标记置零（从[1,1]开始） 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 (firstColZero) { for (int i = 0; i < m; i++) matrix[i][0] = 0; } // 6. 处理第一行 if (firstRowZero) { for (int j = 0; j < n; j++) matrix[0][j] = 0; } } ``` **⏱️ 复杂度分析** - 时间：O(m × n) - 空间：O(1) --- ### 19. 螺旋矩阵 ⭐⭐ **LeetCode 54** **📝 题目描述** 给定一个矩阵，按照顺时针螺旋顺序，返回所有元素。 **💡 解题思路** **边界收缩法：** ``` 定义四个边界：top, bottom, left, right 顺序: 1. 从左到右遍历top行，然后top++ 2. 从上到下遍历right列，然后right-- 3. 从右到左遍历bottom行，然后bottom-- 4. 从下到上遍历left列，然后left++ 重复直到边界相遇 ``` ``` [1, 2, 3] [4, 5, 6] [7, 8, 9] 第一圈: 1,2,3 → 6,9 → 8,7 → 4 第二圈: 5 结果: [1,2,3,6,9,8,7,4,5] ``` **🎯 关键点** - 每走完一边就收缩对应边界 - 注意内层判断边界是否还有效 **💻 代码实现** ```java public List spiralOrder(int[][] matrix) { List result = new ArrayList<>(); if (matrix.length == 0) return result; int top = 0, bottom = matrix.length - 1; int left = 0, right = matrix[0].length - 1; while (top <= bottom && left <= right) { // 从左到右 for (int j = left; j <= right; j++) { result.add(matrix[top][j]); } top++; // 从上到下 for (int i = top; i <= bottom; i++) { result.add(matrix[i][right]); } right--; // 从右到左（检查边界） if (top <= bottom) { for (int j = right; j >= left; j--) { result.add(matrix[bottom][j]); } bottom--; } // 从下到上（检查边界） if (left <= right) { for (int i = bottom; i >= top; i--) { result.add(matrix[i][left]); } left++; } } return result; } ``` **⏱️ 复杂度分析** - 时间：O(m × n) - 空间：O(1) --- ### 20. 旋转图像 ⭐⭐ **LeetCode 48** **📝 题目描述** 将 n×n 矩阵顺时针旋转 90 度，要求原地操作。 **💡 解题思路** **方法：先转置，再水平翻转** ``` 原矩阵: [1, 2, 3] [4, 5, 6] [7, 8, 9] 转置（行列互换）: [1, 4, 7] [2, 5, 8] [3, 6, 9] 水平翻转（左右镜像）: [7, 4, 1] [8, 5, 2] [9, 6, 3] ``` **为什么这样有效？** ``` 原位置 (i, j) 转置后 (j, i) 水平翻转后 (j, n-1-i) 验证: (0,2) → (2,0) → (2,2) ✓ 原来的 3 → 转置到左下 → 翻转到右下 ``` **🎯 关键点** - 转置：交换 matrix[i][j] 和 matrix[j][i] - 只遍历上三角，避免重复交换 **💻 代码实现** ```java public void rotate(int[][] matrix) { int n = matrix.length; // 1. 转置（沿主对角线翻转） for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { // 只遍历上三角 int temp = matrix[i][j]; matrix[i][j] = matrix[j][i]; matrix[j][i] = temp; } } // 2. 水平翻转（每行左右翻转） for (int i = 0; i < n; i++) { for (int j = 0; j < n / 2; j++) { int temp = matrix[i][j]; matrix[i][j] = matrix[i][n - 1 - j]; matrix[i][n - 1 - j] = temp; } } } ``` **⏱️ 复杂度分析** - 时间：O(n²) - 空间：O(1) --- ### 21. 搜索二维矩阵 II ⭐⭐ **LeetCode 240** **📝 题目描述** 在一个 m×n 矩阵中搜索目标值，矩阵特点：每行从左到右升序，每列从上到下升序。 **💡 解题思路** **从右上角开始搜索：** ``` 为什么选右上角？ - 右上角元素：比它小的在左边，比它大的在下边 - 类似二叉搜索树！ 每次比较: - 如果等于 target：找到 - 如果大于 target：往左走（排除当前列） - 如果小于 target：往下走（排除当前行） ``` ``` 矩阵: [1, 4, 7, 11, 15] [2, 5, 8, 12, 19] [3, 6, 9, 16, 22] target = 5 从15开始: 15 > 5 → 左移 → 11 11 > 5 → 左移 → 7 7 > 5 → 左移 → 4 4 < 5 → 下移 → 5 ✓ ``` **🎯 关键点** - 也可以从左下角开始（对称的） - 每次排除一行或一列 **💻 代码实现** ```java public boolean searchMatrix(int[][] matrix, int target) { if (matrix.length == 0) return false; int m = matrix.length, n = matrix[0].length; int row = 0, 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) - 空间：O(1) --- ## 七、链表 ### 22. 相交链表 ⭐ **LeetCode 160** **📝 题目描述** 找出两个单链表相交的起始节点。 **💡 解题思路** **双指针妙解：** ``` 设链表A的长度 = a + c 设链表B的长度 = b + c 其中 c 是公共部分长度 指针pA: 走完A后走B → a + c + b 指针pB: 走完B后走A → b + c + a a + c + b = b + c + a 它们走相同的距离后会在交点相遇！ 如果不相交，c=0，最后都指向 null ``` ``` A: 1 → 2 → 3 ↘ 6 → 7 → null ↗ B: 4 → 5 pA: 1→2→3→6→7→null→4→5→6 (在6相遇) pB: 4→5→6→7→null→1→2→3→6 (在6相遇) ``` **🎯 关键点** - 走完自己的再走对方的 - 不相交时会同时到达 null **💻 代码实现** ```java public ListNode getIntersectionNode(ListNode headA, ListNode headB) { if (headA == null || headB == null) return null; ListNode pA = headA, pB = headB; // pA 走完 A 走 B，pB 走完 B 走 A while (pA != pB) { pA = (pA == null) ? headB : pA.next; pB = (pB == null) ? headA : pB.next; } return pA; // 相交点或 null } ``` **⏱️ 复杂度分析** - 时间：O(m + n) - 空间：O(1) --- ### 23. 反转链表 ⭐ **LeetCode 206** **📝 题目描述** 反转一个单链表。 **💡 解题思路** **迭代法：三指针** ``` prev curr next ↓ ↓ ↓ null 1 → 2 → 3 → null 步骤: 1. 保存 next = curr.next 2. 反转 curr.next = prev 3. 移动 prev = curr 4. 移动 curr = next ``` **递归法：** ``` reverseList(1→2→3) = reverseList(2→3) 然后把 1 接到末尾 = (3→2) 然后把 1 接到末尾 = 3→2→1 ``` **🎯 关键点** - 迭代：保存 next 再断链 - 递归：先递归反转后面，再把当前节点接到末尾 **💻 代码实现** ```java // 方法一：迭代 public ListNode reverseList(ListNode head) { ListNode prev = null; ListNode curr = head; while (curr != null) { ListNode next = curr.next; // 保存 curr.next = prev; // 反转 prev = curr; // 移动 prev curr = next; // 移动 curr } return prev; } // 方法二：递归 public ListNode reverseList(ListNode head) { // 基准：空链表或单节点 if (head == null || head.next == null) { return head; } // 递归反转后面的部分 ListNode newHead = reverseList(head.next); // 把当前节点接到后面 head.next.next = head; // 2→1 head.next = null; // 1→null return newHead; } ``` **⏱️ 复杂度分析** - 迭代：时间 O(n)，空间 O(1) - 递归：时间 O(n)，空间 O(n)（递归栈） --- ### 24. 回文链表 ⭐ **LeetCode 234** **📝 题目描述** 判断链表是否是回文链表，要求 O(n) 时间和 O(1) 空间。 **💡 解题思路** **步骤：** 1. 快慢指针找中点 2. 反转后半部分 3. 比较前半部分和后半部分 4. （可选）恢复链表 ``` 1 → 2 → 2 → 1 找中点: slow 停在第二个 2 反转后半: 1 → 2 → 2 ← 1 比较: 1==1, 2==2 ✓ ``` **🎯 关键点** - 快慢指针：快指针到末尾时，慢指针在中点 - 奇数长度时，中间节点不影响回文判断 **💻 代码实现** ```java 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 = reverseList(slow.next); // 3. 比较 ListNode p1 = head, 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 = reverseList(secondHalf); return result; } private ListNode reverseList(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) - 空间：O(1) --- ### 25. 环形链表 ⭐ **LeetCode 141** **📝 题目描述** 判断链表是否有环。 **💡 解题思路** **快慢指针（Floyd 判圈算法）：** ``` 快指针每次走2步，慢指针每次走1步 如果有环，快指针会"追上"慢指针 如果无环，快指针会先到达 null ``` **为什么一定会相遇？** ``` 假设进入环后，快指针在慢指针前面 k 步 每走一次，距离缩小 1 步（快走2，慢走1） k 次后距离为 0，相遇！ ``` **🎯 关键点** - 快指针检查 fast.next 和 fast.next.next **💻 代码实现** ```java public boolean hasCycle(ListNode head) { if (head == null || head.next == null) return false; ListNode slow = head, 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) - 空间：O(1) --- ### 26. 环形链表 II ⭐⭐ **LeetCode 142** **📝 题目描述** 如果链表有环，返回入环的第一个节点；否则返回 null。 **💡 解题思路** **数学推导：** ``` 设： - 头到入环点距离 = a - 入环点到相遇点距离 = b - 相遇点到入环点距离 = c - 环长 = b + c 快指针走的距离 = a + b + n(b+c) (n是圈数) 慢指针走的距离 = a + b 快指针是慢指针的2倍: 2(a + b) = a + b + n(b+c) a + b = n(b+c) a = n(b+c) - b = (n-1)(b+c) + c 结论： 从头节点走 a 步 = 从相遇点走 c + (n-1)圈 它们会在入环点相遇！ ``` **🎯 关键点** - 第一次相遇后，一个从头走，一个从相遇点走 - 再次相遇点就是入环点 **💻 代码实现** ```java public ListNode detectCycle(ListNode head) { if (head == null || head.next == null) return null; // 1. 快慢指针找相遇点 ListNode slow = head, fast = head; while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; if (slow == fast) { // 2. 找入环点 ListNode p1 = head, p2 = slow; while (p1 != p2) { p1 = p1.next; p2 = p2.next; } return p1; } } return null; } ``` **⏱️ 复杂度分析** - 时间：O(n) - 空间：O(1) --- ### 27. 合并两个有序链表 ⭐ **LeetCode 21** **📝 题目描述** 将两个升序链表合并为一个升序链表。 **💡 解题思路** **迭代：用 dummy 节点简化处理** ``` l1: 1 → 2 → 4 l2: 1 → 3 → 4 dummy → 1 → 1 → 2 → 3 → 4 → 4 ``` **🎯 关键点** - dummy 节点避免处理头节点特殊情况 - 最后接上剩余部分 **💻 代码实现** ```java // 迭代 public ListNode mergeTwoLists(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) ? l1 : l2; return dummy.next; } // 递归 public ListNode mergeTwoLists(ListNode l1, ListNode l2) { if (l1 == null) return l2; if (l2 == null) return l1; if (l1.val <= l2.val) { l1.next = mergeTwoLists(l1.next, l2); return l1; } else { l2.next = mergeTwoLists(l1, l2.next); return l2; } } ``` **⏱️ 复杂度分析** - 时间：O(m + n) - 空间：迭代 O(1)，递归 O(m + n) --- ### 28. 两数相加 ⭐⭐ **LeetCode 2** **📝 题目描述** 两个非空链表表示两个非负整数，数字逆序存储。将它们相加并以相同形式返回一个表示和的链表。 示例：`(2→4→3) + (5→6→4) = 7→0→8`（342 + 465 = 807） **💡 解题思路** **模拟加法过程：** ``` 2 → 4 → 3 + 5 → 6 → 4 ----------- 7 → 0 → 8 逐位相加，处理进位 ``` **🎯 关键点** - 用 carry 记录进位 - 两链表长度可能不同 - 最后可能还有进位 **💻 代码实现** ```java public ListNode addTwoNumbers(ListNode l1, ListNode l2) { ListNode dummy = new ListNode(0); ListNode curr = dummy; int carry = 0; while (l1 != null || l2 != null || carry != 0) { int sum = carry; if (l1 != null) { sum += l1.val; l1 = l1.next; } if (l2 != null) { sum += l2.val; l2 = l2.next; } carry = sum / 10; curr.next = new ListNode(sum % 10); curr = curr.next; } return dummy.next; } ``` **⏱️ 复杂度分析** - 时间：O(max(m, n)) - 空间：O(max(m, n)) --- ### 29. 删除链表的倒数第 N 个节点 ⭐⭐ **LeetCode 19** **📝 题目描述** 删除链表的倒数第 n 个节点。 示例：`1→2→3→4→5`, n=2 → `1→2→3→5` **💡 解题思路** **快慢指针：** ``` 让快指针先走 n 步 然后快慢指针同时走 当快指针到末尾时，慢指针正好在倒数第 n+1 个节点 ``` ``` dummy → 1 → 2 → 3 → 4 → 5, n=2 fast 先走 2 步: fast 在 2 slow 在 dummy 同时走: fast=3, slow=1 fast=4, slow=2 fast=5, slow=3 fast=null → slow 在 3，删除 slow.next(4) ``` **🎯 关键点** - 用 dummy 节点处理删除头节点的情况 - fast 先走 n+1 步（或者 slow 从 dummy 开始） **💻 代码实现** ```java public ListNode removeNthFromEnd(ListNode head, int n) { ListNode dummy = new ListNode(0, head); ListNode fast = dummy, slow = dummy; // fast 先走 n+1 步 for (int i = 0; i <= n; i++) { fast = fast.next; } // 同时走，直到 fast 到末尾 while (fast != null) { fast = fast.next; slow = slow.next; } // 删除 slow 的下一个节点 slow.next = slow.next.next; return dummy.next; } ``` **⏱️ 复杂度分析** - 时间：O(n) - 空间：O(1) --- ### 30. 两两交换链表中的节点 ⭐⭐ **LeetCode 24** **📝 题目描述** 两两交换链表中的相邻节点。 示例：`1→2→3→4` → `2→1→4→3` **💡 解题思路** **迭代：** ``` dummy → 1 → 2 → 3 → 4 prev=dummy, curr=1, next=2 交换后: dummy → 2 → 1 → 3 → 4 ↑prev指向2 1指向3 ``` **🎯 关键点** - 保存三个指针：prev, curr, next - 每次交换后，prev 移动到 curr（交换后在后面） **💻 代码实现** ```java // 迭代 public ListNode swapPairs(ListNode head) { ListNode dummy = new ListNode(0, head); ListNode prev = dummy; while (prev.next != null && prev.next.next != null) { ListNode first = prev.next; ListNode second = prev.next.next; // 交换 prev.next = second; first.next = second.next; second.next = first; // 移动 prev prev = first; } return dummy.next; } // 递归 public ListNode swapPairs(ListNode head) { if (head == null || head.next == null) return head; ListNode newHead = head.next; head.next = swapPairs(newHead.next); newHead.next = head; return newHead; } ``` **⏱️ 复杂度分析** - 时间：O(n) - 空间：迭代 O(1)，递归 O(n) --- ### 31. K 个一组翻转链表 ⭐⭐⭐ **LeetCode 25** **📝 题目描述** 每 k 个节点一组进行翻转，最后不足 k 个的不翻转。 示例：`1→2→3→4→5`, k=2 → `2→1→4→3→5` **💡 解题思路** **步骤：** 1. 检查是否有 k 个节点 2. 翻转这 k 个节点 3. 连接翻转后的部分 4. 递归/迭代处理剩余部分 **🎯 关键点** - 翻转时要记住头尾节点 - 连接前后部分 **💻 代码实现** ```java public ListNode reverseKGroup(ListNode head, int k) { // 检查是否有 k 个节点 ListNode check = head; for (int i = 0; i < k; i++) { if (check == null) return head; // 不足 k 个，不翻转 check = check.next; } // 翻转前 k 个节点 ListNode prev = null, curr = head; for (int i = 0; i < k; i++) { ListNode next = curr.next; curr.next = prev; prev = curr; curr = next; } // prev 是新头，head 是新尾 // curr 是下一组的头 head.next = reverseKGroup(curr, k); return prev; } ``` **⏱️ 复杂度分析** - 时间：O(n) - 空间：O(n/k)（递归栈） --- ### 32. 随机链表的复制 ⭐⭐ **LeetCode 138** **📝 题目描述** 复制带有随机指针的链表。每个节点有 next 和 random 两个指针。 **💡 解题思路** **方法一：哈希表** ``` 第一遍：创建所有新节点，用 Map 存储 原节点 → 新节点 的映射 第二遍：设置 next 和 random 指针 ``` **方法二：原地复制（空间 O(1)）** ``` 1. 在每个原节点后插入复制节点 A → A' → B → B' → C → C' 2. 设置 random 指针 A'.random = A.random.next 3. 拆分链表 ``` **🎯 关键点** - random 可能指向 null - 原地方法要恢复原链表（如果需要） **💻 代码实现** ```java // 方法一：哈希表 public Node copyRandomList(Node head) { if (head == null) return null; Map map = new HashMap<>(); // 第一遍：创建新节点 Node curr = head; while (curr != null) { map.put(curr, new Node(curr.val)); curr = curr.next; } // 第二遍：设置指针 curr = head; while (curr != null) { map.get(curr).next = map.get(curr.next); map.get(curr).random = map.get(curr.random); curr = curr.next; } return map.get(head); } // 方法二：原地复制 public Node copyRandomList(Node head) { if (head == null) return null; // 1. 在每个节点后插入复制节点 Node curr = head; while (curr != null) { Node copy = new Node(curr.val); copy.next = curr.next; curr.next = copy; curr = copy.next; } // 2. 设置 random 指针 curr = head; while (curr != null) { if (curr.random != null) { curr.next.random = curr.random.next; } curr = curr.next.next; } // 3. 拆分链表 Node newHead = head.next; curr = head; while (curr != null) { Node copy = curr.next; curr.next = copy.next; if (copy.next != null) { copy.next = copy.next.next; } curr = curr.next; } return newHead; } ``` **⏱️ 复杂度分析** - 哈希表：时间 O(n)，空间 O(n) - 原地：时间 O(n)，空间 O(1) --- ### 33. 排序链表 ⭐⭐ **LeetCode 148** **📝 题目描述** 对链表进行排序，要求 O(n log n) 时间，O(1) 空间。 **💡 解题思路** **归并排序（自底向上）：** ``` O(1) 空间的归并排序： 1. 先按步长 1 合并相邻的单节点 2. 再按步长 2 合并相邻的双节点对 3. 步长翻倍，直到大于等于链表长度 ``` **递归归并（空间 O(log n)）：** ``` 1. 快慢指针找中点 2. 递归排序左右两半 3. 合并两个有序链表 ``` **🎯 关键点** - 找中点时让 slow 停在中点前一个（便于断链） - 先断链再递归 **💻 代码实现** ```java // 递归归并（好理解，空间 O(log n)） public ListNode sortList(ListNode head) { if (head == null || head.next == null) return head; // 1. 快慢指针找中点 ListNode slow = head, fast = head.next; while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; } // 2. 断链 ListNode mid = slow.next; slow.next = null; // 3. 递归排序 ListNode left = sortList(head); ListNode right = sortList(mid); // 4. 合并 return merge(left, right); } 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) ? l1 : l2; return dummy.next; } ``` **⏱️ 复杂度分析** - 时间：O(n log n) - 空间：递归 O(log n)，迭代 O(1) --- ### 34. 合并 K 个升序链表 ⭐⭐⭐ **LeetCode 23** **📝 题目描述** 合并 k 个升序链表。 **💡 解题思路** **方法一：最小堆** ``` 把所有链表的头节点放入最小堆 每次取出最小的，加入结果，把它的下一个节点加入堆 ``` **方法二：分治合并** ``` 类似归并排序 两两合并，递归 ``` **🎯 关键点** - 堆中存储节点，按节点值排序 - 分治的时间复杂度更优 **💻 代码实现** ```java // 方法一：最小堆 public ListNode mergeKLists(ListNode[] lists) { if (lists == null || lists.length == 0) return null; PriorityQueue heap = new PriorityQueue<>( (a, b) -> a.val - b.val ); // 所有头节点入堆 for (ListNode head : lists) { if (head != null) heap.offer(head); } ListNode dummy = new ListNode(0); ListNode curr = dummy; while (!heap.isEmpty()) { ListNode min = heap.poll(); curr.next = min; curr = curr.next; if (min.next != null) { heap.offer(min.next); } } return dummy.next; } // 方法二：分治 public ListNode mergeKLists(ListNode[] lists) { if (lists == null || lists.length == 0) return null; return mergeRange(lists, 0, lists.length - 1); } private ListNode mergeRange(ListNode[] lists, int left, int right) { if (left == right) return lists[left]; int mid = left + (right - left) / 2; ListNode l1 = mergeRange(lists, left, mid); ListNode l2 = mergeRange(lists, mid + 1, right); return merge(l1, l2); } ``` **⏱️ 复杂度分析** - 最小堆：时间 O(n log k)，空间 O(k) - 分治：时间 O(n log k)，空间 O(log k) --- ### 35. LRU 缓存 ⭐⭐ **LeetCode 146** **📝 题目描述** 实现 LRU（最近最少使用）缓存，支持 get 和 put 操作，时间复杂度 O(1)。 **💡 解题思路** **哈希表 + 双向链表：** ``` 哈希表：O(1) 查找 双向链表：O(1) 插入删除，维护使用顺序 链表头 = 最近使用 链表尾 = 最久未使用 get: 存在 → 移到头部，返回值 不存在 → 返回 -1 put: 存在 → 更新值，移到头部 不存在 → 新建节点，加到头部 超出容量 → 删除尾部 ``` **🎯 关键点** - 双向链表用 dummy head 和 tail 简化操作 - Map 存储 key → Node **💻 代码实现** ```java public class LRUCache { class Node { int key, value; Node prev, next; Node() {} Node(int key, int value) { this.key = key; this.value = value; } } private int capacity; private Map map; private Node head, tail; // dummy nodes public LRUCache(int capacity) { this.capacity = capacity; this.map = new HashMap<>(); this.head = new Node(); this.tail = new Node(); head.next = tail; tail.prev = head; } public int get(int key) { Node node = map.get(key); if (node == null) return -1; moveToHead(node); return node.value; } public void put(int key, int value) { Node node = map.get(key); if (node != null) { node.value = value; moveToHead(node); } else { Node newNode = new Node(key, value); map.put(key, newNode); addToHead(newNode); 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 node = tail.prev; removeNode(node); return node; } } ``` **⏱️ 复杂度分析** - get/put 时间：O(1) - 空间：O(capacity) --- --- ## 八、二叉树 ### 36. 二叉树的中序遍历 ⭐ **LeetCode 94** **📝 题目描述** 给定二叉树的根节点，返回它的中序遍历。 **💡 解题思路** **中序遍历顺序：左 → 根 → 右** **三种方法：** 1. **递归**：最简单直观 2. **迭代**：用栈模拟递归 3. **Morris**：O(1) 空间，利用空指针 **迭代的关键：** ``` 一直往左走，把节点入栈 走到头后，出栈，访问，转向右子树 ``` **🎯 关键点** - 迭代：先一直往左入栈，出栈后转右 **💻 代码实现** ```java // 方法一：递归 public List inorderTraversal(TreeNode root) { List result = new ArrayList<>(); inorder(root, result); return result; } private void inorder(TreeNode node, List result) { if (node == null) return; inorder(node.left, result); // 左 result.add(node.val); // 根 inorder(node.right, result); // 右 } // 方法二：迭代（栈） public List inorderTraversal(TreeNode root) { List result = new ArrayList<>(); Stack stack = new Stack<>(); TreeNode curr = root; while (curr != null || !stack.isEmpty()) { // 一直往左走 while (curr != null) { stack.push(curr); curr = curr.left; } // 出栈，访问，转右 curr = stack.pop(); result.add(curr.val); curr = curr.right; } return result; } ``` --- ### 37. 二叉树的最大深度 ⭐ **LeetCode 104** **📝 题目描述** 给定一个二叉树，找出其最大深度。 **💡 解题思路** **递归（DFS）：** ``` maxDepth(root) = 1 + max(maxDepth(left), maxDepth(right)) ``` **BFS：层序遍历，数层数** **🎯 关键点** - 空节点深度为 0 - 递归自底向上计算 **💻 代码实现** ```java // DFS 递归 public int maxDepth(TreeNode root) { if (root == null) return 0; return 1 + Math.max(maxDepth(root.left), maxDepth(root.right)); } // BFS public int maxDepth(TreeNode root) { if (root == null) return 0; Queue 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++; } return depth; } ``` --- ### 38. 翻转二叉树 ⭐ **LeetCode 226** **📝 题目描述** 翻转一棵二叉树（镜像）。 **💡 解题思路** **递归：交换左右子树，然后递归翻转** ``` 4 4 / \ / \ 2 7 → 7 2 / \ / \ / \ / \ 1 3 6 9 9 6 3 1 ``` **🎯 关键点** - 先交换，再递归（或先递归再交换都可以） **💻 代码实现** ```java public TreeNode invertTree(TreeNode root) { if (root == null) return null; // 交换左右子树 TreeNode temp = root.left; root.left = root.right; root.right = temp; // 递归翻转 invertTree(root.left); invertTree(root.right); return root; } ``` --- ### 39. 对称二叉树 ⭐ **LeetCode 101** **📝 题目描述** 判断二叉树是否是镜像对称的。 **💡 解题思路** **递归比较：左子树和右子树是否镜像** ``` 镜像条件： 1. 两个节点值相同 2. 左的左 = 右的右 3. 左的右 = 右的左 ``` **🎯 关键点** - 比较的是"镜像位置"的节点 **💻 代码实现** ```java public boolean isSymmetric(TreeNode root) { if (root == null) return true; return isMirror(root.left, root.right); } private boolean isMirror(TreeNode left, TreeNode right) { if (left == null && right == null) return true; if (left == null || right == null) return false; return left.val == right.val && isMirror(left.left, right.right) // 外侧 && isMirror(left.right, right.left); // 内侧 } ``` --- ### 40. 二叉树的直径 ⭐ **LeetCode 543** **📝 题目描述** 求二叉树的直径（任意两节点之间的最长路径）。 **💡 解题思路** **关键洞察：** ``` 直径 = 经过某个节点的最长路径 = 该节点的左子树深度 + 右子树深度 遍历所有节点，取最大值 ``` **后序遍历：自底向上计算深度，同时更新最大直径** **🎯 关键点** - 深度是"边数"，不是节点数 - 用全局变量记录最大直径 **💻 代码实现** ```java private int maxDiameter = 0; public int diameterOfBinaryTree(TreeNode root) { depth(root); return maxDiameter; } // 返回以 node 为根的子树深度（边数） private int depth(TreeNode node) { if (node == null) return 0; int left = depth(node.left); int right = depth(node.right); // 更新最大直径（经过当前节点的路径） maxDiameter = Math.max(maxDiameter, left + right); // 返回深度 return 1 + Math.max(left, right); } ``` --- ### 41. 二叉树的层序遍历 ⭐⭐ **LeetCode 102** **📝 题目描述** 返回二叉树的层序遍历结果（按层分组）。 **💡 解题思路** **BFS + 按层记录：** ``` 每次处理一层： 1. 记录当前层的节点数 size 2. 处理 size 个节点，同时把下一层节点入队 ``` **🎯 关键点** - 用 `queue.size()` 确定当前层的节点数 **💻 代码实现** ```java public List> levelOrder(TreeNode root) { List> result = new ArrayList<>(); if (root == null) return result; Queue queue = new LinkedList<>(); queue.offer(root); while (!queue.isEmpty()) { int size = queue.size(); // 当前层节点数 List level = new ArrayList<>(); for (int i = 0; i < size; i++) { TreeNode node = queue.poll(); level.add(node.val); if (node.left != null) queue.offer(node.left); if (node.right != null) queue.offer(node.right); } result.add(level); } return result; } ``` --- ### 42. 将有序数组转换为BST ⭐ **LeetCode 108** **📝 题目描述** 将有序数组转换为高度平衡的二叉搜索树。 **💡 解题思路** **递归：取中点为根，保证平衡** ``` 数组: [-10, -3, 0, 5, 9] 中点 0 为根 左半部分 [-10, -3] 构建左子树 右半部分 [5, 9] 构建右子树 ``` **🎯 关键点** - 每次取中点作为根节点 - 递归处理左右部分 **💻 代码实现** ```java public TreeNode sortedArrayToBST(int[] nums) { return build(nums, 0, nums.length - 1); } private TreeNode build(int[] nums, int left, int right) { if (left > right) return null; int mid = left + (right - left) / 2; TreeNode root = new TreeNode(nums[mid]); root.left = build(nums, left, mid - 1); root.right = build(nums, mid + 1, right); return root; } ``` --- ### 43. 验证二叉搜索树 ⭐⭐ **LeetCode 98** **📝 题目描述** 判断二叉树是否是有效的二叉搜索树。 **💡 解题思路** **方法一：中序遍历升序** ``` BST 的中序遍历是严格升序的 ``` **方法二：递归传递范围** ``` 每个节点的值必须在 (min, max) 范围内 左子树的范围: (min, node.val) 右子树的范围: (node.val, max) ``` **🎯 关键点** - 注意是严格大于/小于，不是大于等于 - 用 Long 防止溢出 **💻 代码实现** ```java // 方法一：中序遍历 public boolean isValidBST(TreeNode root) { List inorder = new ArrayList<>(); inorderTraversal(root, inorder); for (int i = 1; i < inorder.size(); i++) { if (inorder.get(i) <= inorder.get(i - 1)) return false; } return true; } // 方法二：递归传范围（推荐） public boolean isValidBST(TreeNode root) { return validate(root, Long.MIN_VALUE, Long.MAX_VALUE); } private boolean validate(TreeNode node, long min, long max) { if (node == null) return true; if (node.val <= min || node.val >= max) return false; return validate(node.left, min, node.val) && validate(node.right, node.val, max); } ``` --- ### 44. 二叉搜索树中第K小的元素 ⭐⭐ **LeetCode 230** **📝 题目描述** 给定 BST 的根节点和整数 k，返回第 k 小的元素。 **💡 解题思路** **中序遍历计数：** ``` BST 中序遍历是升序的 遍历时计数，到第 k 个停止 ``` **🎯 关键点** - 提前终止：找到后不用继续遍历 **💻 代码实现** ```java private int count = 0; private int result = 0; 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; return; } inorder(node.right, k); } // 迭代版本 public int kthSmallest(TreeNode root, int k) { Stack stack = new Stack<>(); TreeNode curr = root; while (curr != null || !stack.isEmpty()) { while (curr != null) { stack.push(curr); curr = curr.left; } curr = stack.pop(); if (--k == 0) return curr.val; curr = curr.right; } return -1; } ``` --- ### 45. 二叉树的右视图 ⭐⭐ **LeetCode 199** **📝 题目描述** 返回从右侧看二叉树时能看到的节点值。 **💡 解题思路** **方法一：BFS，每层最后一个节点** **方法二：DFS，先访问右子树** ``` 先右后左的 DFS 每层第一个访问的就是右视图节点 ``` **🎯 关键点** - BFS：记录每层最后一个 - DFS：当层数等于结果数组长度时，说明是该层第一个 **💻 代码实现** ```java // BFS public List rightSideView(TreeNode root) { List result = new ArrayList<>(); if (root == null) return result; Queue 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; } // DFS（先右后左） public List rightSideView(TreeNode root) { List result = new ArrayList<>(); dfs(root, 0, result); return result; } private void dfs(TreeNode node, int depth, List result) { if (node == null) return; // 如果是该层第一个访问的节点 if (depth == result.size()) { result.add(node.val); } dfs(node.right, depth + 1, result); // 先右 dfs(node.left, depth + 1, result); // 后左 } ``` --- ### 46. 二叉树展开为链表 ⭐⭐ **LeetCode 114** **📝 题目描述** 将二叉树展开为单链表（前序遍历顺序），使用 right 指针连接。 **💡 解题思路** **方法一：前序遍历存储，再重建** **方法二：原地展开（逆前序：右→左→根）** ``` 从后往前处理，维护"上一个节点" 每次把当前节点的 right 指向上一个节点 ``` **方法三：迭代** ``` 对于每个节点： 1. 如果有左子树，找到左子树最右节点 2. 把右子树接到最右节点的 right 3. 把左子树移到 right ``` **🎯 关键点** - 展开顺序是前序遍历 - 原地操作需要从后往前处理 **💻 代码实现** ```java // 方法一：逆前序遍历（右→左→根） private TreeNode prev = null; public void flatten(TreeNode root) { if (root == null) return; flatten(root.right); flatten(root.left); root.right = prev; root.left = null; prev = root; } // 方法二：迭代 public void flatten(TreeNode root) { TreeNode curr = root; while (curr != null) { if (curr.left != null) { // 找左子树的最右节点 TreeNode rightmost = curr.left; while (rightmost.right != null) { rightmost = rightmost.right; } // 把右子树接到最右节点 rightmost.right = curr.right; // 把左子树移到右边 curr.right = curr.left; curr.left = null; } curr = curr.right; } } ``` --- ### 47. 从前序与中序遍历构造二叉树 ⭐⭐ **LeetCode 105** **📝 题目描述** 根据前序和中序遍历结果构造二叉树。 **💡 解题思路** ``` 前序: [根, 左子树, 右子树] 中序: [左子树, 根, 右子树] 1. 前序第一个是根 2. 在中序中找到根，分割左右子树 3. 递归构建 ``` ``` preorder = [3, 9, 20, 15, 7] inorder = [9, 3, 15, 20, 7] 根 = 3 中序中 3 的位置 = 1 左子树: preorder[1:2], inorder[0:1] 右子树: preorder[2:5], inorder[2:5] ``` **🎯 关键点** - 用 HashMap 加速在中序中查找根的位置 - 计算左子树长度来分割数组 **💻 代码实现** ```java private Map inorderMap; public TreeNode buildTree(int[] preorder, int[] inorder) { inorderMap = new HashMap<>(); for (int i = 0; i < inorder.length; i++) { inorderMap.put(inorder[i], i); } return build(preorder, 0, preorder.length - 1, 0); } private TreeNode build(int[] preorder, int preLeft, int preRight, int inLeft) { if (preLeft > preRight) return null; // 前序第一个是根 int rootVal = preorder[preLeft]; TreeNode root = new TreeNode(rootVal); // 在中序中找根的位置 int rootIndex = inorderMap.get(rootVal); // 左子树的长度 int leftSize = rootIndex - inLeft; // 递归构建 root.left = build(preorder, preLeft + 1, preLeft + leftSize, inLeft); root.right = build(preorder, preLeft + leftSize + 1, preRight, rootIndex + 1); return root; } ``` --- ### 48. 路径总和 III ⭐⭐ **LeetCode 437** **📝 题目描述** 求二叉树中路径和等于目标值的路径数量。路径不需要从根开始，不需要在叶子结束，但必须向下。 **💡 解题思路** **前缀和 + DFS：** ``` 类似数组的"和为K的子数组"问题 前缀和 = 从根到当前节点的路径和 如果存在前缀和 = 当前前缀和 - targetSum 说明中间这段路径的和等于 targetSum ``` **🎯 关键点** - 用 Map 记录前缀和出现的次数 - 回溯时要恢复 Map **💻 代码实现** ```java public int pathSum(TreeNode root, int targetSum) { Map prefixSum = new HashMap<>(); prefixSum.put(0L, 1); // 前缀和为0出现1次 return dfs(root, 0, targetSum, prefixSum); } private int dfs(TreeNode node, long currSum, int target, Map prefixSum) { if (node == null) return 0; currSum += node.val; // 查找是否存在前缀和 = currSum - target int count = prefixSum.getOrDefault(currSum - target, 0); // 记录当前前缀和 prefixSum.merge(currSum, 1, Integer::sum); // 递归左右子树 count += dfs(node.left, currSum, target, prefixSum); count += dfs(node.right, currSum, target, prefixSum); // 回溯，恢复 Map prefixSum.merge(currSum, -1, Integer::sum); return count; } ``` --- ### 49. 二叉树的最近公共祖先 ⭐⭐ **LeetCode 236** **📝 题目描述** 给定二叉树中的两个节点，找出它们的最近公共祖先。 **💡 解题思路** **递归：** ``` 1. 如果当前节点是 p 或 q，返回当前节点 2. 递归查找左右子树 3. 如果左右都找到了，当前节点就是 LCA 4. 如果只有一边找到，返回那一边的结果 ``` ``` 3 / \ 5 1 / \ 6 2 / \ 7 4 p=5, q=4 - 3的左子树找到5，右子树没找到 - 5自己就是p，5的右子树找到4 - 所以5是LCA ``` **🎯 关键点** - 递归定义：返回"子树中是否包含p或q" **💻 代码实现** ```java public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { // 基准情况 if (root == null || root == p || root == q) { return root; } // 在左右子树中查找 TreeNode left = lowestCommonAncestor(root.left, p, q); TreeNode right = lowestCommonAncestor(root.right, p, q); // 如果左右都找到了，当前节点是LCA if (left != null && right != null) { return root; } // 否则返回找到的那个 return left != null ? left : right; } ``` --- ### 50. 二叉树中的最大路径和 ⭐⭐⭐ **LeetCode 124** **📝 题目描述** 求二叉树中任意两个节点之间的最大路径和。路径可以不经过根节点。 **💡 解题思路** **后序遍历 + 全局变量：** ``` 对于每个节点，考虑经过它的最大路径： 路径和 = 左子树贡献 + 节点值 + 右子树贡献 子树贡献 = max(0, 子树最大路径和) （如果子树贡献为负，不如不要） 返回给父节点的贡献 = 节点值 + max(左贡献, 右贡献) （只能选一边，因为路径不能分叉） ``` **🎯 关键点** - 负数贡献取 0（不要那条路径） - 返回时只能选一边，更新答案时可以两边都选 **💻 代码实现** ```java private int maxSum = Integer.MIN_VALUE; public int maxPathSum(TreeNode root) { maxGain(root); return maxSum; } // 返回以 node 为端点的最大路径和 private int maxGain(TreeNode node) { if (node == null) return 0; // 左右子树的贡献（负数取0） int leftGain = Math.max(0, maxGain(node.left)); int rightGain = Math.max(0, maxGain(node.right)); // 经过当前节点的最大路径和 int pathSum = node.val + leftGain + rightGain; maxSum = Math.max(maxSum, pathSum); // 返回给父节点的贡献（只能选一边） return node.val + Math.max(leftGain, rightGain); } ``` --- ## 九、图论 ### 51. 岛屿数量 ⭐⭐ **LeetCode 200** **📝 题目描述** 给定一个由 '1'（陆地）和 '0'（水）组成的二维网格，计算岛屿数量。 **💡 解题思路** **DFS/BFS 遍历连通分量：** ``` 1. 遍历网格，找到 '1' 2. 从该位置开始 DFS/BFS，把相连的 '1' 都标记为已访问 3. 岛屿数量 +1 4. 继续遍历 ``` **🎯 关键点** - 访问后标记为 '0' 或用 visited 数组 - 四个方向遍历 **💻 代码实现** ```java public int numIslands(char[][] grid) { if (grid == null || grid.length == 0) return 0; int m = grid.length, 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') { dfs(grid, i, j); count++; } } } return count; } private void dfs(char[][] grid, int i, int j) { int m = grid.length, n = grid[0].length; // 边界检查 + 水检查 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); } ``` --- ### 52. 腐烂的橘子 ⭐⭐ **LeetCode 994** **📝 题目描述** 网格中有新鲜橘子和腐烂橘子，腐烂橘子每分钟会使相邻的新鲜橘子腐烂。求所有橘子腐烂的最少时间，如果不可能返回 -1。 **💡 解题思路** **多源 BFS：** ``` 1. 把所有腐烂橘子加入队列（多个起点） 2. BFS 扩散，每一轮代表一分钟 3. 统计最后是否还有新鲜橘子 ``` **🎯 关键点** - 多源 BFS：初始时所有腐烂橘子同时入队 - 记录新鲜橘子数量，每腐烂一个就减一 **💻 代码实现** ```java public int orangesRotting(int[][] grid) { int m = grid.length, n = grid[0].length; Queue queue = new LinkedList<>(); int fresh = 0; // 初始化：腐烂橘子入队，统计新鲜橘子数 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++; } } } if (fresh == 0) return 0; int[][] dirs = {{1,0}, {-1,0}, {0,1}, {0,-1}}; int minutes = 0; while (!queue.isEmpty()) { int size = queue.size(); boolean rotted = false; for (int i = 0; i < size; i++) { int[] pos = queue.poll(); for (int[] dir : dirs) { int ni = pos[0] + dir[0]; int nj = pos[1] + dir[1]; if (ni >= 0 && ni < m && nj >= 0 && nj < n && grid[ni][nj] == 1) { grid[ni][nj] = 2; queue.offer(new int[]{ni, nj}); fresh--; rotted = true; } } } if (rotted) minutes++; } return fresh == 0 ? minutes : -1; } ``` --- ### 53. 课程表 ⭐⭐ **LeetCode 207** **📝 题目描述** 判断是否能完成所有课程。课程有先修关系，如 [1, 0] 表示要学课程 1 必须先学课程 0。 **💡 解题思路** **拓扑排序（检测有向图是否有环）：** **方法一：BFS（Kahn 算法）** ``` 1. 统计每个节点的入度 2. 入度为 0 的节点入队 3. 取出节点，把它指向的节点入度 -1 4. 入度变 0 的节点入队 5. 最后检查是否所有节点都被处理 ``` **方法二：DFS 检测环** ``` 状态：0=未访问，1=正在访问，2=已完成 如果访问到"正在访问"的节点，说明有环 ``` **🎯 关键点** - 有环则无法完成所有课程 - 拓扑排序的实现 **💻 代码实现** ```java // BFS 拓扑排序 public boolean canFinish(int numCourses, int[][] prerequisites) { int[] indegree = new int[numCourses]; List> graph = new ArrayList<>(); for (int i = 0; i < numCourses; i++) { graph.add(new ArrayList<>()); } // 建图 + 统计入度 for (int[] pre : prerequisites) { graph.get(pre[1]).add(pre[0]); indegree[pre[0]]++; } // 入度为 0 的节点入队 Queue 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 next : graph.get(course)) { indegree[next]--; if (indegree[next] == 0) { queue.offer(next); } } } return count == numCourses; } ``` --- ### 54. 实现 Trie（前缀树）⭐⭐ **LeetCode 208** **📝 题目描述** 实现 Trie，支持 insert、search 和 startsWith 操作。 **💡 解题思路** **前缀树结构：** ``` 每个节点包含： - children[26]：指向子节点的指针数组 - isEnd：是否是某个单词的结尾 insert("apple"): root → a → p → p → l → e(isEnd=true) search("app"): 找到 p，但 isEnd=false，返回 false startsWith("app"): 找到 p，返回 true ``` **🎯 关键点** - 每个节点代表一个字符 - isEnd 标记单词结尾 **💻 代码实现** ```java class Trie { private Trie[] children; private boolean isEnd; public Trie() { children = new Trie[26]; isEnd = false; } public void insert(String word) { Trie node = this; for (char c : word.toCharArray()) { int index = c - 'a'; if (node.children[index] == null) { node.children[index] = new Trie(); } node = node.children[index]; } node.isEnd = true; } public boolean search(String word) { Trie node = searchPrefix(word); return node != null && node.isEnd; } public boolean startsWith(String prefix) { return searchPrefix(prefix) != null; } private Trie searchPrefix(String prefix) { Trie node = this; for (char c : prefix.toCharArray()) { int index = c - 'a'; if (node.children[index] == null) { return null; } node = node.children[index]; } return node; } } --- ## 十、回溯 ### 55. 全排列 ⭐⭐ **LeetCode 46** **📝 题目描述** 给定一个不含重复数字的数组，返回其所有可能的全排列。 **💡 解题思路** **回溯模板：** ``` 回溯三要素： 1. 路径：已经做出的选择 2. 选择列表：当前可以做的选择 3. 结束条件：到达决策树底层 框架： def backtrack(路径, 选择列表): if 满足结束条件: result.add(路径) return for 选择 in 选择列表: 做选择 backtrack(路径, 选择列表) 撤销选择 ``` **🎯 关键点** - 用 visited 数组标记已选择的元素 - 回溯时要撤销选择 **💻 代码实现** ```java public List> permute(int[] nums) { List> result = new ArrayList<>(); boolean[] visited = new boolean[nums.length]; backtrack(nums, new ArrayList<>(), visited, result); return result; } private void backtrack(int[] nums, List path, boolean[] visited, List> result) { // 结束条件 if (path.size() == nums.length) { result.add(new ArrayList<>(path)); return; } // 遍历选择列表 for (int i = 0; i < nums.length; i++) { if (visited[i]) continue; // 跳过已选择的 // 做选择 path.add(nums[i]); visited[i] = true; // 递归 backtrack(nums, path, visited, result); // 撤销选择 path.remove(path.size() - 1); visited[i] = false; } } ``` --- ### 56. 子集 ⭐⭐ **LeetCode 78** **📝 题目描述** 给定一个不含重复元素的整数数组，返回该数组所有可能的子集。 **💡 解题思路** **每个元素有两种选择：选 或 不选** ``` nums = [1,2,3] [] / \ [1] [] / \ / \ [1,2] [1] [2] [] ... ``` **另一种思路：按位置选择** ``` 从位置 start 开始，选择加入或不加入 ``` **🎯 关键点** - 每个节点都是一个子集，不只是叶子节点 - 用 start 控制选择范围，避免重复 **💻 代码实现** ```java public List> subsets(int[] nums) { List> result = new ArrayList<>(); backtrack(nums, 0, new ArrayList<>(), result); return result; } private void backtrack(int[] nums, int start, List path, List> result) { // 每个节点都是一个子集 result.add(new ArrayList<>(path)); // 从 start 开始选择 for (int i = start; i < nums.length; i++) { path.add(nums[i]); backtrack(nums, i + 1, path, result); path.remove(path.size() - 1); } } ``` --- ### 57. 电话号码的字母组合 ⭐⭐ **LeetCode 17** **📝 题目描述** 给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。 **💡 解题思路** **多路径回溯：** ``` 2 → "abc" 3 → "def" ... "23" 的组合: 先选 2 对应的字母(a/b/c) 再选 3 对应的字母(d/e/f) ``` **🎯 关键点** - 预处理数字到字母的映射 - 每个数字对应多个选择 **💻 代码实现** ```java private String[] mapping = { "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" }; public List letterCombinations(String digits) { List result = new ArrayList<>(); if (digits.isEmpty()) return result; backtrack(digits, 0, new StringBuilder(), result); return result; } private void backtrack(String digits, int index, StringBuilder path, List 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); } } ``` --- ### 58. 组合总和 ⭐⭐ **LeetCode 39** **📝 题目描述** 给定无重复元素的数组和目标数，找出所有和为目标数的组合。数字可以无限制重复使用。 **💡 解题思路** **回溯 + 可重复选择：** ``` 与子集的区别：同一个元素可以重复选择 所以递归时 start 不用 +1 ``` **剪枝优化：** ``` 排序后，如果当前数已经大于 remaining，后面的数更大，直接跳过 ``` **🎯 关键点** - 递归时传入当前索引 i（可重复选择） - 剪枝：排序 + 提前终止 **💻 代码实现** ```java public List> combinationSum(int[] candidates, int target) { List> result = new ArrayList<>(); Arrays.sort(candidates); // 排序，便于剪枝 backtrack(candidates, target, 0, new ArrayList<>(), result); return result; } private void backtrack(int[] candidates, int remaining, int start, List path, List> result) { if (remaining == 0) { result.add(new ArrayList<>(path)); return; } for (int i = start; i < candidates.length; i++) { // 剪枝：如果当前数已经大于 remaining，后面更大的数更不行 if (candidates[i] > remaining) break; path.add(candidates[i]); // 注意：传入 i 而不是 i+1，允许重复选择 backtrack(candidates, remaining - candidates[i], i, path, result); path.remove(path.size() - 1); } } ``` --- ### 59. 括号生成 ⭐⭐ **LeetCode 22** **📝 题目描述** 生成 n 对有效的括号组合。 **💡 解题思路** **回溯 + 剪枝条件：** ``` 有效括号的条件： 1. 左括号数量不能超过 n 2. 右括号数量不能超过左括号数量 在任意位置，已使用的右括号 <= 已使用的左括号 ``` **🎯 关键点** - 跟踪左右括号的使用数量 - 右括号数量不能超过左括号 **💻 代码实现** ```java public List generateParenthesis(int n) { List result = new ArrayList<>(); backtrack(n, 0, 0, new StringBuilder(), result); return result; } private void backtrack(int n, int left, int right, StringBuilder path, List result) { if (path.length() == 2 * n) { result.add(path.toString()); return; } // 可以加左括号 if (left < n) { path.append('('); backtrack(n, left + 1, right, path, result); path.deleteCharAt(path.length() - 1); } // 可以加右括号（右括号数量必须小于左括号） if (right < left) { path.append(')'); backtrack(n, left, right + 1, path, result); path.deleteCharAt(path.length() - 1); } } ``` --- ### 60. 单词搜索 ⭐⭐ **LeetCode 79** **📝 题目描述** 给定一个字符矩阵和一个单词，判断单词是否存在于矩阵中（相邻单元格连接）。 **💡 解题思路** **DFS + 回溯：** ``` 1. 遍历矩阵，找到第一个字符 2. 从该位置开始 DFS，匹配后续字符 3. 用 visited 标记已访问的位置 4. 如果不匹配，回溯 ``` **🎯 关键点** - 标记访问，防止重复使用同一个格子 - 回溯时恢复标记 **💻 代码实现** ```java public boolean exist(char[][] board, String word) { int m = board.length, n = board[0].length; 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 index) { // 匹配完成 if (index == word.length()) return true; // 边界检查 if (i < 0 || i >= board.length || j < 0 || j >= board[0].length) { return false; } // 字符不匹配 if (board[i][j] != word.charAt(index)) return false; // 标记已访问 char temp = board[i][j]; board[i][j] = '#'; // 四个方向搜索 boolean found = dfs(board, word, i + 1, j, index + 1) || dfs(board, word, i - 1, j, index + 1) || dfs(board, word, i, j + 1, index + 1) || dfs(board, word, i, j - 1, index + 1); // 回溯 board[i][j] = temp; return found; } ``` --- ### 61. 分割回文串 ⭐⭐ **LeetCode 131** **📝 题目描述** 将字符串分割成若干回文子串，返回所有可能的分割方案。 **💡 解题思路** **回溯：** ``` 从位置 0 开始，尝试每个可能的分割点 如果 [start, i] 是回文，则加入路径，递归处理剩余部分 ``` **🎯 关键点** - 只有当前子串是回文时才递归 - 可以用动态规划预处理回文判断 **💻 代码实现** ```java public List> partition(String s) { List> result = new ArrayList<>(); backtrack(s, 0, new ArrayList<>(), result); return result; } private void backtrack(String s, int start, List path, List> result) { if (start == s.length()) { result.add(new ArrayList<>(path)); return; } for (int end = start; end < s.length(); end++) { if (isPalindrome(s, start, end)) { path.add(s.substring(start, end + 1)); backtrack(s, end + 1, path, result); path.remove(path.size() - 1); } } } private boolean isPalindrome(String s, int left, int right) { while (left < right) { if (s.charAt(left++) != s.charAt(right--)) return false; } return true; } ``` --- ### 62. N 皇后 ⭐⭐⭐ **LeetCode 51** **📝 题目描述** 在 n×n 棋盘上放置 n 个皇后，使得它们不能互相攻击。 **💡 解题思路** **回溯 + 冲突检测：** ``` 皇后攻击范围：同行、同列、同对角线 按行放置，每行放一个皇后 用三个集合记录被占用的： - 列 - 主对角线（row - col 相同） - 副对角线（row + col 相同） ``` **🎯 关键点** - 按行遍历，所以不用检查行冲突 - 对角线用 row±col 的值来标识 **💻 代码实现** ```java public List> solveNQueens(int n) { List> result = new ArrayList<>(); int[] queens = new int[n]; // queens[i] = j 表示第 i 行皇后在第 j 列 Arrays.fill(queens, -1); Set cols = new HashSet<>(); // 被占用的列 Set diag1 = new HashSet<>(); // 主对角线 row-col Set diag2 = new HashSet<>(); // 副对角线 row+col backtrack(n, 0, queens, cols, diag1, diag2, result); return result; } private void backtrack(int n, int row, int[] queens, Set cols, Set diag1, Set diag2, List> result) { if (row == n) { result.add(generateBoard(queens, n)); return; } for (int col = 0; col < n; col++) { // 检查是否冲突 if (cols.contains(col) || diag1.contains(row - col) || diag2.contains(row + col)) { continue; } // 放置皇后 queens[row] = col; cols.add(col); diag1.add(row - col); diag2.add(row + col); backtrack(n, row + 1, queens, cols, diag1, diag2, result); // 回溯 queens[row] = -1; cols.remove(col); diag1.remove(row - col); diag2.remove(row + col); } } private List generateBoard(int[] queens, int n) { List board = new ArrayList<>(); for (int i = 0; i < n; i++) { char[] row = new char[n]; Arrays.fill(row, '.'); row[queens[i]] = 'Q'; board.add(new String(row)); } return board; } ``` --- ## 十一、二分查找 ### 63. 搜索插入位置 ⭐ **LeetCode 35** **📝 题目描述** 在排序数组中找到目标值的索引，如果不存在则返回应该插入的位置。 **💡 解题思路** **二分查找：找第一个 >= target 的位置** ``` 标准二分变体： 如果 nums[mid] >= target，答案在左边（包括 mid） 如果 nums[mid] < target，答案在右边 最终 left 就是第一个 >= target 的位置 ``` **🎯 关键点** - 循环条件：left <= right - 返回 left **💻 代码实现** ```java public int searchInsert(int[] nums, int target) { int left = 0, right = nums.length - 1; while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] >= target) { right = mid - 1; } else { left = mid + 1; } } return left; } ``` --- ### 64. 搜索二维矩阵 ⭐⭐ **LeetCode 74** **📝 题目描述** 在一个 m×n 矩阵中搜索目标值。每行从左到右升序，每行第一个数大于上一行最后一个数。 **💡 解题思路** **将矩阵看作一维数组：** ``` 矩阵可以看作一个升序数组 索引 i 对应矩阵位置 [i/n][i%n] ``` **🎯 关键点** - 一维索引转二维坐标 **💻 代码实现** ```java public boolean searchMatrix(int[][] matrix, int target) { int m = matrix.length, n = matrix[0].length; int left = 0, right = m * n - 1; while (left <= right) { int mid = left + (right - left) / 2; int val = matrix[mid / n][mid % n]; if (val == target) { return true; } else if (val < target) { left = mid + 1; } else { right = mid - 1; } } return false; } ``` --- ### 65. 在排序数组中查找元素的首末位置 ⭐⭐ **LeetCode 34** **📝 题目描述** 给定排序数组和目标值，找出目标值的开始位置和结束位置。 **💡 解题思路** **两次二分：** ``` 第一次：找第一个 >= target 的位置 第二次：找第一个 > target 的位置，减 1 ``` **🎯 关键点** - 两种二分变体：找左边界和右边界 **💻 代码实现** ```java public int[] searchRange(int[] nums, int target) { int left = findFirst(nums, target); if (left == nums.length || nums[left] != target) { return new int[]{-1, -1}; } int right = findFirst(nums, target + 1) - 1; return new int[]{left, right}; } // 找第一个 >= target 的位置 private int findFirst(int[] nums, int target) { int left = 0, right = nums.length; while (left < right) { int mid = left + (right - left) / 2; if (nums[mid] >= target) { right = mid; } else { left = mid + 1; } } return left; } ``` --- ### 66. 搜索旋转排序数组 ⭐⭐ **LeetCode 33** **📝 题目描述** 在旋转排序数组中搜索目标值。旋转：[4,5,6,7,0,1,2] **💡 解题思路** **二分 + 判断哪边有序：** ``` 旋转数组的特点： 至少有一半是有序的 1. 计算 mid 2. 判断 [left, mid] 或 [mid, right] 哪边是有序的 3. 如果 target 在有序的那边，继续在那边找 4. 否则在另一边找 ``` **🎯 关键点** - 通过比较 nums[left] 和 nums[mid] 判断哪边有序 - 根据 target 是否在有序区间决定搜索方向 **💻 代码实现** ```java public int search(int[] nums, int target) { int left = 0, 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[mid] && target <= nums[right]) { left = mid + 1; // 在右边找 } else { right = mid - 1; // 在左边找 } } } return -1; } ``` --- ### 67. 寻找旋转排序数组中的最小值 ⭐⭐ **LeetCode 153** **📝 题目描述** 找出旋转排序数组中的最小值。 **💡 解题思路** **二分：比较 mid 和 right** ``` 如果 nums[mid] > nums[right]： 最小值在右边（不包括 mid） 如果 nums[mid] < nums[right]： 最小值在左边（包括 mid） ``` **🎯 关键点** - 比较 mid 和 right 而不是 left - 最终 left == right 就是最小值 **💻 代码实现** ```java public int findMin(int[] nums) { int left = 0, right = nums.length - 1; while (left < right) { int mid = left + (right - left) / 2; if (nums[mid] > nums[right]) { // 最小值在右边 left = mid + 1; } else { // 最小值在左边（包括 mid） right = mid; } } return nums[left]; } ``` --- ### 68. 寻找两个正序数组的中位数 ⭐⭐⭐ **LeetCode 4** **📝 题目描述** 给定两个正序数组，找出这两个数组的中位数，要求时间复杂度 O(log(m+n))。 **💡 解题思路** **二分查找分割点：** ``` 将两个数组分割成左右两部分 left_part = nums1[0..i] + nums2[0..j] right_part = nums1[i..m] + nums2[j..n] 条件： 1. len(left_part) == len(right_part) → j = (m+n+1)/2 - i 2. max(left_part) <= min(right_part) 二分查找 i 的位置 ``` **🎯 关键点** - 在较短的数组上二分 - 处理边界情况 **💻 代码实现** ```java public double findMedianSortedArrays(int[] nums1, int[] nums2) { // 确保 nums1 是较短的数组 if (nums1.length > nums2.length) { return findMedianSortedArrays(nums2, nums1); } int m = nums1.length, n = nums2.length; int left = 0, right = m; while (left <= right) { int i = left + (right - left) / 2; int j = (m + n + 1) / 2 - i; int maxLeft1 = (i == 0) ? Integer.MIN_VALUE : nums1[i - 1]; int minRight1 = (i == m) ? Integer.MAX_VALUE : nums1[i]; int maxLeft2 = (j == 0) ? Integer.MIN_VALUE : nums2[j - 1]; int minRight2 = (j == n) ? Integer.MAX_VALUE : nums2[j]; if (maxLeft1 <= minRight2 && maxLeft2 <= minRight1) { // 找到了 if ((m + n) % 2 == 0) { return (Math.max(maxLeft1, maxLeft2) + Math.min(minRight1, minRight2)) / 2.0; } else { return Math.max(maxLeft1, maxLeft2); } } else if (maxLeft1 > minRight2) { right = i - 1; } else { left = i + 1; } } return 0; } ``` --- ## 十二、栈 ### 69. 有效的括号 ⭐ **LeetCode 20** **📝 题目描述** 判断字符串中的括号是否有效配对。 **💡 解题思路** **栈匹配：** ``` 左括号入栈 右括号出栈匹配 最后栈为空则有效 ``` **🎯 关键点** - 右括号时栈不能为空 - 必须匹配对应类型 **💻 代码实现** ```java public boolean isValid(String s) { Stack stack = new Stack<>(); Map map = Map.of(')', '(', ']', '[', '}', '{'); for (char c : s.toCharArray()) { if (map.containsValue(c)) { stack.push(c); } else { if (stack.isEmpty() || stack.pop() != map.get(c)) { return false; } } } return stack.isEmpty(); } ``` --- ### 70. 最小栈 ⭐⭐ **LeetCode 155** **📝 题目描述** 设计一个栈，支持 push、pop、top 和 O(1) 时间获取最小元素。 **💡 解题思路** **辅助栈：同步记录当前最小值** ``` 主栈: [3, 2, 5, 1] 辅助栈: [3, 2, 2, 1] 辅助栈栈顶始终是当前最小值 ``` **🎯 关键点** - 辅助栈和主栈同步 push/pop - 或者只在新最小值时 push **💻 代码实现** ```java class MinStack { private Stack stack; private Stack 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(); } } ``` --- ### 71. 字符串解码 ⭐⭐ **LeetCode 394** **📝 题目描述** 解码字符串，如 `3[a2[c]]` → `accaccacc` **💡 解题思路** **栈存储：** ``` 遇到数字：累积数字 遇到 '['：把当前数字和字符串入栈，重置 遇到 ']'：出栈，重复字符串 遇到字母：加到当前字符串 ``` **🎯 关键点** - 两个栈：一个存数字，一个存字符串 - 遇到 `[` 保存状态，遇到 `]` 恢复并重复 **💻 代码实现** ```java public String decodeString(String s) { Stack countStack = new Stack<>(); Stack strStack = new Stack<>(); StringBuilder current = new StringBuilder(); int num = 0; for (char c : s.toCharArray()) { if (Character.isDigit(c)) { num = num * 10 + (c - '0'); } else if (c == '[') { countStack.push(num); strStack.push(current); current = new StringBuilder(); num = 0; } else if (c == ']') { int count = countStack.pop(); StringBuilder prev = strStack.pop(); for (int i = 0; i < count; i++) { prev.append(current); } current = prev; } else { current.append(c); } } return current.toString(); } ``` --- ### 72. 每日温度 ⭐⭐ **LeetCode 739** **📝 题目描述** 给定温度数组，返回每天需要等多少天才能遇到更高的温度。 示例：`[73,74,75,71,69,72,76,73]` → `[1,1,4,2,1,1,0,0]` **💡 解题思路** **单调递减栈：** ``` 栈中存储索引 栈顶到栈底温度递减 遍历时： 如果当前温度 > 栈顶温度，说明找到了栈顶的"更高温度" 出栈，计算天数差 ``` **🎯 关键点** - 栈中存索引，方便计算天数差 - 单调递减：找右边第一个更大的 **💻 代码实现** ```java public int[] dailyTemperatures(int[] temperatures) { int n = temperatures.length; int[] result = new int[n]; Stack stack = new Stack<>(); // 存索引 for (int i = 0; i < n; i++) { // 当前温度 > 栈顶温度 while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) { int prev = stack.pop(); result[prev] = i - prev; } stack.push(i); } return result; } ``` --- ### 73. 柱状图中最大的矩形 ⭐⭐⭐ **LeetCode 84** **📝 题目描述** 给定柱状图的高度数组，找出其中最大的矩形面积。 **💡 解题思路** **单调栈：找每个柱子左右第一个更矮的柱子** ``` 对于每个柱子 h[i]： 最大矩形 = h[i] × (right[i] - left[i] - 1) left[i] = 左边第一个比 h[i] 矮的柱子位置 right[i] = 右边第一个比 h[i] 矮的柱子位置 ``` **🎯 关键点** - 单调递增栈 - 在数组两端加哨兵（高度为0）简化边界处理 **💻 代码实现** ```java public int largestRectangleArea(int[] heights) { int n = heights.length; int[] left = new int[n]; // 左边第一个更矮的索引 int[] right = new int[n]; // 右边第一个更矮的索引 Stack stack = new Stack<>(); // 从左到右，找左边界 for (int i = 0; i < n; i++) { while (!stack.isEmpty() && heights[stack.peek()] >= heights[i]) { stack.pop(); } left[i] = stack.isEmpty() ? -1 : stack.peek(); stack.push(i); } stack.clear(); // 从右到左，找右边界 for (int i = n - 1; i >= 0; i--) { while (!stack.isEmpty() && heights[stack.peek()] >= heights[i]) { stack.pop(); } right[i] = stack.isEmpty() ? n : stack.peek(); stack.push(i); } // 计算最大面积 int maxArea = 0; for (int i = 0; i < n; i++) { maxArea = Math.max(maxArea, heights[i] * (right[i] - left[i] - 1)); } return maxArea; } --- ## 十三、堆 ### 74. 数组中的第K个最大元素 ⭐⭐ **LeetCode 215** **📝 题目描述** 找出数组中第 K 大的元素。 **💡 解题思路** **方法一：小顶堆** ``` 维护一个大小为 K 的小顶堆 遍历数组，堆满后只保留最大的 K 个 堆顶就是第 K 大 ``` **方法二：快速选择 O(n)** ``` 快排思想：partition 后，pivot 左边都比它大 如果 pivot 位置 == K-1，找到了 如果 < K-1，在右边找 如果 > K-1，在左边找 ``` **🎯 关键点** - 小顶堆：保留最大的 K 个 - 快速选择：随机 pivot 避免最坏情况 **💻 代码实现** ```java // 方法一：小顶堆 O(n log k) public int findKthLargest(int[] nums, int k) { PriorityQueue heap = new PriorityQueue<>(); // 小顶堆 for (int num : nums) { heap.offer(num); if (heap.size() > k) { heap.poll(); // 移除最小的 } } return heap.peek(); } // 方法二：快速选择 O(n) public int findKthLargest(int[] nums, int k) { return quickSelect(nums, 0, nums.length - 1, k - 1); } private int quickSelect(int[] nums, int left, int right, int k) { if (left == right) return nums[left]; // 随机选择 pivot int pivotIndex = left + new Random().nextInt(right - left + 1); pivotIndex = partition(nums, left, right, pivotIndex); if (pivotIndex == k) { return nums[k]; } else if (pivotIndex < k) { return quickSelect(nums, pivotIndex + 1, right, k); } else { return quickSelect(nums, left, pivotIndex - 1, k); } } // 从大到小排列的 partition private int partition(int[] nums, int left, int right, int pivotIndex) { int pivot = nums[pivotIndex]; swap(nums, pivotIndex, right); int storeIndex = left; for (int i = left; i < right; i++) { if (nums[i] > pivot) { // 大的放左边 swap(nums, storeIndex++, i); } } swap(nums, storeIndex, right); return storeIndex; } ``` --- ### 75. 前 K 个高频元素 ⭐⭐ **LeetCode 347** **📝 题目描述** 给定整数数组和整数 k，返回其中出现频率前 k 高的元素。 **💡 解题思路** **方法一：小顶堆** ``` 1. 统计频率 2. 用大小为 K 的小顶堆（按频率） 3. 堆中保留频率最高的 K 个 ``` **方法二：桶排序 O(n)** ``` 1. 统计频率 2. 创建桶，桶的索引是频率 3. 从高频率桶向低频率桶取 K 个 ``` **🎯 关键点** - 先统计频率 - 桶排序更优 **💻 代码实现** ```java // 方法一：小顶堆 public int[] topKFrequent(int[] nums, int k) { Map freq = new HashMap<>(); for (int num : nums) { freq.merge(num, 1, Integer::sum); } PriorityQueue heap = new PriorityQueue<>((a, b) -> a[1] - b[1]); for (Map.Entry entry : freq.entrySet()) { heap.offer(new int[]{entry.getKey(), entry.getValue()}); 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) public int[] topKFrequent(int[] nums, int k) { Map freq = new HashMap<>(); for (int num : nums) { freq.merge(num, 1, Integer::sum); } // 桶的索引是频率 List[] buckets = new List[nums.length + 1]; for (Map.Entry entry : freq.entrySet()) { int f = entry.getValue(); if (buckets[f] == null) buckets[f] = new ArrayList<>(); buckets[f].add(entry.getKey()); } // 从高频率桶取 K 个 int[] result = new int[k]; int index = 0; for (int i = buckets.length - 1; i >= 0 && index < k; i--) { if (buckets[i] != null) { for (int num : buckets[i]) { result[index++] = num; if (index == k) break; } } } return result; } ``` --- ### 76. 数据流的中位数 ⭐⭐⭐ **LeetCode 295** **📝 题目描述** 设计一个数据结构，支持添加数据和获取当前数据的中位数。 **💡 解题思路** **大顶堆 + 小顶堆：** ``` 将数据分成两半： - 大顶堆存较小的一半（堆顶是较小一半的最大值） - 小顶堆存较大的一半（堆顶是较大一半的最小值） 保持平衡：两堆大小差不超过 1 中位数： - 总数为奇数：多的那个堆的堆顶 - 总数为偶数：两个堆顶的平均值 ``` **🎯 关键点** - 保持两堆大小平衡 - 新元素先入大顶堆，然后把大顶堆的最大值移到小顶堆 **💻 代码实现** ```java class MedianFinder { private PriorityQueue maxHeap; // 较小的一半 private PriorityQueue minHeap; // 较大的一半 public MedianFinder() { maxHeap = new PriorityQueue<>((a, b) -> b - a); // 大顶堆 minHeap = new PriorityQueue<>(); // 小顶堆 } public void addNum(int num) { // 先加入大顶堆 maxHeap.offer(num); // 把大顶堆的最大值移到小顶堆 minHeap.offer(maxHeap.poll()); // 平衡：保证大顶堆 >= 小顶堆 if (maxHeap.size() < minHeap.size()) { maxHeap.offer(minHeap.poll()); } } public double findMedian() { if (maxHeap.size() > minHeap.size()) { return maxHeap.peek(); } return (maxHeap.peek() + minHeap.peek()) / 2.0; } } ``` --- ## 十四、贪心算法 ### 77. 买卖股票的最佳时机 ⭐ **LeetCode 121** **📝 题目描述** 给定股票每天的价格，只能买卖一次，求最大利润。 **💡 解题思路** **贪心：记录最低价，计算每天卖出的利润** ``` 遍历时： 1. 更新历史最低价 2. 计算今天卖出的利润 3. 更新最大利润 ``` **🎯 关键点** - 只需要记录到今天为止的最低价 - 最大利润 = 当前价格 - 历史最低价 **💻 代码实现** ```java public int maxProfit(int[] prices) { int minPrice = Integer.MAX_VALUE; int maxProfit = 0; for (int price : prices) { minPrice = Math.min(minPrice, price); maxProfit = Math.max(maxProfit, price - minPrice); } return maxProfit; } ``` --- ### 78. 跳跃游戏 ⭐⭐ **LeetCode 55** **📝 题目描述** 给定非负整数数组，判断是否能从第一个位置跳到最后一个位置。 **💡 解题思路** **贪心：维护能到达的最远位置** ``` 遍历每个位置： 1. 如果当前位置超过了能到达的最远位置，返回 false 2. 更新能到达的最远位置 = max(maxReach, i + nums[i]) ``` **🎯 关键点** - 如果最远位置 >= 最后位置，可以到达 - 如果 i > maxReach，到不了当前位置 **💻 代码实现** ```java public boolean canJump(int[] nums) { int maxReach = 0; for (int i = 0; i < nums.length; i++) { if (i > maxReach) return false; // 到不了当前位置 maxReach = Math.max(maxReach, i + nums[i]); if (maxReach >= nums.length - 1) return true; } return true; } ``` --- ### 79. 跳跃游戏 II ⭐⭐ **LeetCode 45** **📝 题目描述** 用最少的跳跃次数到达最后位置。 **💡 解题思路** **BFS 思想 / 贪心：** ``` 把每一跳能到达的范围看作一层 每次跳跃都跳到能让下一跳到达最远的位置 ``` ``` [2, 3, 1, 1, 4] 第0跳能到: [1,2] 在[1,2]中，位置1能跳到4，选位置1 第1跳能到: [2,3,4] 到达终点 跳跃次数: 2 ``` **🎯 关键点** - end：当前跳跃能到的最远边界 - maxReach：下一跳能到的最远位置 - 到达 end 时，跳跃次数 +1，更新 end **💻 代码实现** ```java public int jump(int[] nums) { int jumps = 0; int end = 0; // 当前跳跃的边界 int maxReach = 0; // 能到达的最远位置 for (int i = 0; i < nums.length - 1; i++) { maxReach = Math.max(maxReach, i + nums[i]); if (i == end) { jumps++; end = maxReach; } } return jumps; } ``` --- ### 80. 划分字母区间 ⭐⭐ **LeetCode 763** **📝 题目描述** 把字符串划分为尽可能多的片段，同一字母只能出现在一个片段中。 **💡 解题思路** **贪心：** ``` 1. 记录每个字母最后出现的位置 2. 遍历时，维护当前片段必须延伸到的位置 end 3. end = max(end, 当前字母的最后位置) 4. 当 i == end 时，可以切分 ``` **🎯 关键点** - 当前片段必须包含所有已遍历字母的最后出现位置 - i == end 时，说明当前片段可以结束 **💻 代码实现** ```java public List partitionLabels(String s) { // 记录每个字母最后出现的位置 int[] lastIndex = new int[26]; for (int i = 0; i < s.length(); i++) { lastIndex[s.charAt(i) - 'a'] = i; } List result = new ArrayList<>(); int start = 0, end = 0; for (int i = 0; i < s.length(); i++) { end = Math.max(end, lastIndex[s.charAt(i) - 'a']); if (i == end) { result.add(end - start + 1); start = i + 1; } } return result; } ``` --- ## 十五、动态规划 ### 81. 爬楼梯 ⭐ **LeetCode 70** **📝 题目描述** 每次可以爬 1 或 2 个台阶，求爬到第 n 阶的方法数。 **💡 解题思路** **状态转移：** ``` dp[i] = 到达第 i 阶的方法数 dp[i] = dp[i-1] + dp[i-2] 从 i-1 爬 1 阶 + 从 i-2 爬 2 阶 ``` **就是斐波那契数列！** **🎯 关键点** - 空间优化：只需要前两个状态 **💻 代码实现** ```java public int climbStairs(int n) { if (n <= 2) return n; int prev2 = 1, prev1 = 2; for (int i = 3; i <= n; i++) { int curr = prev1 + prev2; prev2 = prev1; prev1 = curr; } return prev1; } ``` --- ### 82. 杨辉三角 ⭐ **LeetCode 118** **📝 题目描述** 生成杨辉三角的前 n 行。 **💡 解题思路** **每个元素 = 上一行的左上 + 正上** ``` dp[i][j] = dp[i-1][j-1] + dp[i-1][j] 每行首尾为 1 ``` **🎯 关键点** - 边界为 1 - 利用上一行生成当前行 **💻 代码实现** ```java public List> generate(int numRows) { List> result = new ArrayList<>(); for (int i = 0; i < numRows; i++) { List row = new ArrayList<>(); for (int j = 0; j <= i; j++) { if (j == 0 || j == i) { row.add(1); } else { row.add(result.get(i - 1).get(j - 1) + result.get(i - 1).get(j)); } } result.add(row); } return result; } ``` --- ### 83. 打家劫舍 ⭐⭐ **LeetCode 198** **📝 题目描述** 相邻房屋不能同时偷，求能偷到的最大金额。 **💡 解题思路** **状态转移：** ``` dp[i] = 到第 i 家为止的最大金额 两种选择： - 偷第 i 家：dp[i-2] + nums[i] - 不偷第 i 家：dp[i-1] dp[i] = max(dp[i-1], dp[i-2] + nums[i]) ``` **🎯 关键点** - 不是"必须偷"，是"能偷的最大值" - 空间优化：只需要前两个状态 **💻 代码实现** ```java public int rob(int[] nums) { if (nums.length == 1) return nums[0]; int prev2 = nums[0]; int prev1 = Math.max(nums[0], nums[1]); for (int i = 2; i < nums.length; i++) { int curr = Math.max(prev1, prev2 + nums[i]); prev2 = prev1; prev1 = curr; } return prev1; } ``` --- ### 84. 完全平方数 ⭐⭐ **LeetCode 279** **📝 题目描述** 找出若干个完全平方数，使其和等于 n，求最少个数。 **💡 解题思路** **完全背包：** ``` dp[i] = 和为 i 的最少完全平方数个数 dp[i] = min(dp[i - j*j] + 1)，其中 j*j <= i ``` **🎯 关键点** - 完全背包：每个完全平方数可以用多次 - 初始化：dp[0] = 0 **💻 代码实现** ```java public int numSquares(int n) { 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]; } ``` --- ### 85. 零钱兑换 ⭐⭐ **LeetCode 322** **📝 题目描述** 用最少数量的硬币凑出金额 amount，如果不能凑出返回 -1。 **💡 解题思路** **完全背包：** ``` dp[i] = 凑出金额 i 的最少硬币数 dp[i] = min(dp[i - coin] + 1)，对于所有 coin ``` **🎯 关键点** - 完全背包 - 初始化为 MAX_VALUE 表示无法凑出 **💻 代码实现** ```java public int coinChange(int[] coins, int amount) { 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 (coin <= i) { dp[i] = Math.min(dp[i], dp[i - coin] + 1); } } } return dp[amount] > amount ? -1 : dp[amount]; } ``` --- ### 86. 单词拆分 ⭐⭐ **LeetCode 139** **📝 题目描述** 判断字符串是否可以被拆分为字典中的单词。 **💡 解题思路** **动态规划：** ``` dp[i] = s[0:i] 是否可以被拆分 dp[i] = dp[j] && s[j:i] 在字典中 ``` **🎯 关键点** - 枚举分割点 j - 用 HashSet 加速字典查找 **💻 代码实现** ```java public boolean wordBreak(String s, List wordDict) { Set dict = 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] && dict.contains(s.substring(j, i))) { dp[i] = true; break; } } } return dp[n]; } ``` --- ### 87. 最长递增子序列 ⭐⭐ **LeetCode 300** **📝 题目描述** 找出数组中最长严格递增子序列的长度。 **💡 解题思路** **方法一：动态规划 O(n²)** ``` dp[i] = 以 nums[i] 结尾的最长递增子序列长度 dp[i] = max(dp[j] + 1)，其中 j < i 且 nums[j] < nums[i] ``` **方法二：贪心 + 二分 O(n log n)** ``` 维护一个数组 tails，tails[i] = 长度为 i+1 的递增子序列的最小末尾元素 遍历时： - 如果 num > tails 末尾，追加 - 否则二分查找替换第一个 >= num 的位置 ``` **🎯 关键点** - 二分法维护的是"潜力最大"的子序列 - tails 数组本身是有序的 **💻 代码实现** ```java // 方法一：DP O(n²) public int lengthOfLIS(int[] nums) { int n = nums.length; int[] dp = new int[n]; Arrays.fill(dp, 1); int maxLen = 1; for (int i = 1; i < n; i++) { for (int j = 0; j < i; j++) { if (nums[j] < nums[i]) { dp[i] = Math.max(dp[i], dp[j] + 1); } } maxLen = Math.max(maxLen, dp[i]); } return maxLen; } // 方法二：贪心 + 二分 O(n log n) public int lengthOfLIS(int[] nums) { List tails = new ArrayList<>(); for (int num : nums) { int pos = binarySearch(tails, num); if (pos == tails.size()) { tails.add(num); } else { tails.set(pos, num); } } return tails.size(); } // 找第一个 >= target 的位置 private int binarySearch(List tails, int target) { int left = 0, right = tails.size(); while (left < right) { int mid = left + (right - left) / 2; if (tails.get(mid) >= target) { right = mid; } else { left = mid + 1; } } return left; } ``` --- ### 88. 乘积最大子数组 ⭐⭐ **LeetCode 152** **📝 题目描述** 找出数组中乘积最大的连续子数组的乘积。 **💡 解题思路** **维护最大和最小（负负得正）：** ``` 负数可能让最小变最大！ dpMax[i] = 以 i 结尾的最大乘积 dpMin[i] = 以 i 结尾的最小乘积 如果 nums[i] < 0，交换 dpMax 和 dpMin dpMax[i] = max(nums[i], dpMax[i-1] * nums[i]) dpMin[i] = min(nums[i], dpMin[i-1] * nums[i]) ``` **🎯 关键点** - 负数翻转最大最小 - 空间优化：只需要前一个状态 **💻 代码实现** ```java public int maxProduct(int[] nums) { int maxProd = nums[0], minProd = nums[0], result = nums[0]; for (int i = 1; i < nums.length; i++) { // 如果是负数，交换最大最小 if (nums[i] < 0) { int temp = maxProd; maxProd = minProd; minProd = temp; } maxProd = Math.max(nums[i], maxProd * nums[i]); minProd = Math.min(nums[i], minProd * nums[i]); result = Math.max(result, maxProd); } return result; } ``` --- ### 89. 分割等和子集 ⭐⭐ **LeetCode 416** **📝 题目描述** 判断数组是否能分成两个元素和相等的子集。 **💡 解题思路** **0-1 背包：** ``` 等价于：能否选出一些数，使得和 = sum/2 dp[j] = 是否能凑出和为 j ``` **🎯 关键点** - sum 必须是偶数 - 0-1 背包：从后往前遍历 **💻 代码实现** ```java public boolean canPartition(int[] nums) { int sum = 0; for (int num : nums) sum += num; if (sum % 2 != 0) return false; int target = sum / 2; boolean[] dp = new boolean[target + 1]; dp[0] = true; for (int num : nums) { for (int j = target; j >= num; j--) { // 从后往前！ dp[j] = dp[j] || dp[j - num]; } } return dp[target]; } ``` --- ### 90. 最长有效括号 ⭐⭐⭐ **LeetCode 32** **📝 题目描述** 找出最长有效括号子串的长度。 **💡 解题思路** **方法一：动态规划** ``` dp[i] = 以 s[i] 结尾的最长有效括号长度 只有 s[i] == ')' 时才可能形成有效括号： - 如果 s[i-1] == '('：dp[i] = dp[i-2] + 2 - 如果 s[i-1] == ')' 且 s[i-dp[i-1]-1] == '('： dp[i] = dp[i-1] + 2 + dp[i-dp[i-1]-2] ``` **方法二：栈** ``` 栈中存储索引 初始放入 -1 作为"基准" 遇到 '(' 入栈 遇到 ')' 出栈，计算长度 ``` **🎯 关键点** - 动态规划：只看 ')' 结尾 - 栈：用索引计算长度 **💻 代码实现** ```java // 方法一：动态规划 public int longestValidParentheses(String s) { int n = s.length(); int[] dp = new int[n]; int maxLen = 0; for (int i = 1; i < n; i++) { if (s.charAt(i) == ')') { if (s.charAt(i - 1) == '(') { // () dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2; } else if (dp[i - 1] > 0) { // )) int j = i - dp[i - 1] - 1; if (j >= 0 && s.charAt(j) == '(') { dp[i] = dp[i - 1] + 2 + (j >= 1 ? dp[j - 1] : 0); } } maxLen = Math.max(maxLen, dp[i]); } } return maxLen; } // 方法二：栈 public int longestValidParentheses(String s) { Stack stack = new Stack<>(); stack.push(-1); // 基准 int maxLen = 0; for (int i = 0; i < s.length(); i++) { if (s.charAt(i) == '(') { stack.push(i); } else { stack.pop(); if (stack.isEmpty()) { stack.push(i); // 新的基准 } else { maxLen = Math.max(maxLen, i - stack.peek()); } } } return maxLen; } ``` --- ## 十六、多维动态规划 ### 91. 不同路径 ⭐⭐ **LeetCode 62** **📝 题目描述** 机器人从左上角到右下角有多少条不同的路径（只能向下或向右）。 **💡 解题思路** **状态转移：** ``` dp[i][j] = 到达 (i,j) 的路径数 dp[i][j] = dp[i-1][j] + dp[i][j-1] ``` **🎯 关键点** - 第一行和第一列都是 1 - 可以空间优化到一维 **💻 代码实现** ```java public int uniquePaths(int m, int n) { int[] dp = new int[n]; Arrays.fill(dp, 1); for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { dp[j] += dp[j - 1]; } } return dp[n - 1]; } ``` --- ### 92. 最小路径和 ⭐⭐ **LeetCode 64** **📝 题目描述** 找出从左上角到右下角的路径，使得路径上的数字总和最小。 **💡 解题思路** **状态转移：** ``` dp[i][j] = 到达 (i,j) 的最小路径和 dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j] ``` **🎯 关键点** - 边界初始化 - 可原地修改 grid **💻 代码实现** ```java public int minPathSum(int[][] grid) { int m = grid.length, n = grid[0].length; // 初始化第一行和第一列 for (int i = 1; i < m; i++) grid[i][0] += grid[i - 1][0]; for (int j = 1; j < n; j++) grid[0][j] += grid[0][j - 1]; for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { grid[i][j] += Math.min(grid[i - 1][j], grid[i][j - 1]); } } return grid[m - 1][n - 1]; } ``` --- ### 93. 最长回文子串 ⭐⭐ **LeetCode 5** **📝 题目描述** 找出字符串中最长的回文子串。 **💡 解题思路** **方法一：中心扩展 O(n²)** ``` 以每个位置为中心向两边扩展 考虑奇数长度和偶数长度 ``` **方法二：区间 DP** ``` dp[i][j] = s[i:j+1] 是否是回文 dp[i][j] = s[i]==s[j] && dp[i+1][j-1] ``` **🎯 关键点** - 中心扩展更简洁 - 区间 DP 要注意遍历顺序 **💻 代码实现** ```java // 中心扩展 public String longestPalindrome(String s) { if (s.length() < 2) return s; int start = 0, maxLen = 1; for (int i = 0; i < s.length(); i++) { int len1 = expand(s, i, i); // 奇数长度 int len2 = expand(s, i, i + 1); // 偶数长度 int len = Math.max(len1, len2); if (len > maxLen) { maxLen = len; start = i - (len - 1) / 2; } } return s.substring(start, start + maxLen); } private int expand(String s, int left, int right) { while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) { left--; right++; } return right - left - 1; } ``` --- ### 94. 最长公共子序列 ⭐⭐ **LeetCode 1143** **📝 题目描述** 找出两个字符串的最长公共子序列。 **💡 解题思路** **状态转移：** ``` dp[i][j] = text1[0:i] 和 text2[0:j] 的 LCS 长度 如果 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]) ``` **🎯 关键点** - 相等则从左上角 +1 - 不等则取左边或上边的较大值 **💻 代码实现** ```java public int longestCommonSubsequence(String text1, String text2) { int m = text1.length(), n = text2.length(); int[][] dp = new int[m + 1][n + 1]; for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; 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[m][n]; } ``` --- ### 95. 编辑距离 ⭐⭐⭐ **LeetCode 72** **📝 题目描述** 计算将 word1 转换成 word2 所需的最少操作数（插入、删除、替换）。 **💡 解题思路** **状态转移：** ``` dp[i][j] = word1[0:i] 转换成 word2[0:j] 的最少操作数 如果 word1[i-1] == word2[j-1]： dp[i][j] = dp[i-1][j-1] // 不需要操作 否则： dp[i][j] = min( dp[i-1][j] + 1, // 删除 word1[i-1] dp[i][j-1] + 1, // 插入 word2[j-1] dp[i-1][j-1] + 1 // 替换 ) ``` **🎯 关键点** - 初始化：空串到长度 n 的串需要 n 次操作 - 三种操作取最小 **💻 代码实现** ```java public int minDistance(String word1, String word2) { int m = word1.length(), n = word2.length(); int[][] dp = new int[m + 1][n + 1]; // 初始化 for (int i = 0; i <= m; i++) dp[i][0] = i; for (int j = 0; j <= n; j++) dp[0][j] = j; for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { if (word1.charAt(i - 1) == word2.charAt(j - 1)) { dp[i][j] = dp[i - 1][j - 1]; } else { dp[i][j] = 1 + Math.min( dp[i - 1][j - 1], // 替换 Math.min(dp[i - 1][j], dp[i][j - 1]) // 删除/插入 ); } } } return dp[m][n]; } ``` --- ## 十七、技巧 ### 96. 只出现一次的数字 ⭐ **LeetCode 136** **📝 题目描述** 数组中只有一个数出现一次，其他都出现两次，找出那个数。 **💡 解题思路** **异或的性质：** ``` a ^ a = 0 a ^ 0 = a 异或满足交换律和结合律 所有数异或，成对的消掉，剩下就是答案 ``` **🎯 关键点** - 异或是最优解 O(n) 时间 O(1) 空间 **💻 代码实现** ```java public int singleNumber(int[] nums) { int result = 0; for (int num : nums) { result ^= num; } return result; } ``` --- ### 97. 多数元素 ⭐ **LeetCode 169** **📝 题目描述** 找出数组中出现次数超过 n/2 的元素。 **💡 解题思路** **Boyer-Moore 投票算法：** ``` 维护候选人和计数 遇到相同的 +1，不同的 -1 计数为 0 时换候选人 多数元素最终一定是候选人 ``` **🎯 关键点** - 多数元素"票数"一定超过其他所有元素 **💻 代码实现** ```java public int majorityElement(int[] nums) { int candidate = nums[0]; int count = 0; for (int num : nums) { if (count == 0) { candidate = num; } count += (num == candidate) ? 1 : -1; } return candidate; } ``` --- ### 98. 颜色分类 ⭐⭐ **LeetCode 75** **📝 题目描述** 数组只包含 0、1、2，原地排序（荷兰国旗问题）。 **💡 解题思路** **三指针：** ``` p0：0 应该放的位置（左边界） p2：2 应该放的位置（右边界） curr：当前遍历位置 遇到 0：与 p0 交换，p0++，curr++ 遇到 1：curr++ 遇到 2：与 p2 交换，p2--（curr 不动，因为交换来的数还没检查） ``` **🎯 关键点** - 遇到 2 交换后 curr 不动 - 遍历到 p2 停止 **💻 代码实现** ```java public void sortColors(int[] nums) { int p0 = 0, curr = 0, p2 = nums.length - 1; while (curr <= p2) { if (nums[curr] == 0) { swap(nums, curr++, p0++); } else if (nums[curr] == 2) { swap(nums, curr, p2--); // curr 不动 } else { curr++; } } } private void swap(int[] nums, int i, int j) { int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; } ``` --- ### 99. 下一个排列 ⭐⭐ **LeetCode 31** **📝 题目描述** 找出数组的下一个字典序更大的排列。 **💡 解题思路** ``` 1. 从右往左找第一个 nums[i] < nums[i+1] 的位置 i 2. 从右往左找第一个 nums[j] > nums[i] 的位置 j 3. 交换 nums[i] 和 nums[j] 4. 反转 [i+1, end] 例如 [1,2,3] → [1,3,2] i=1 (nums[1]=2 < nums[2]=3) j=2 交换: [1,3,2] 反转[2,2]: [1,3,2] ``` **🎯 关键点** - 如果找不到 i，说明是最大排列，直接反转整个数组 **💻 代码实现** ```java public void nextPermutation(int[] nums) { int n = nums.length; int i = n - 2; // 1. 找第一个 nums[i] < nums[i+1] while (i >= 0 && nums[i] >= nums[i + 1]) { i--; } if (i >= 0) { // 2. 找第一个 nums[j] > nums[i] int j = n - 1; while (nums[j] <= nums[i]) { j--; } // 3. 交换 swap(nums, i, j); } // 4. 反转 [i+1, end] reverse(nums, i + 1, n - 1); } private void reverse(int[] nums, int left, int right) { while (left < right) { swap(nums, left++, right--); } } ``` --- ### 100. 寻找重复数 ⭐⭐ **LeetCode 287** **📝 题目描述** 数组包含 n+1 个整数，范围 [1, n]，找出唯一的重复数（不修改数组，O(1) 空间）。 **💡 解题思路** **Floyd 判圈算法（把值当指针）：** ``` 将数组看作链表： 索引 i → 值 nums[i] → 索引 nums[i] → ... 因为有重复数，所以一定有环！ 环的入口就是重复的数。 1. 快慢指针找相遇点 2. 一个从头，一个从相遇点，再次相遇就是入口 ``` **🎯 关键点** - 和环形链表 II 完全相同的原理 - 值作为"下一个位置" **💻 代码实现** ```java public int findDuplicate(int[] nums) { int slow = nums[0], 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; } --- ## 📚 学习建议 ### 刷题顺序建议 **第一周：基础数据结构** 1. 数组：双指针、滑动窗口 2. 链表：反转、合并、快慢指针 3. 栈：括号匹配、单调栈 **第二周：树和图** 1. 二叉树：遍历、递归思想 2. BST：中序遍历特性 3. 图：DFS、BFS、拓扑排序 **第三周：搜索和动态规划** 1. 回溯：排列、组合、子集 2. 二分查找：边界处理 3. 动态规划：背包、区间DP **第四周：综合强化** 1. 复习易错题 2. 限时练习 3. 总结套路模板 ### 每道题的学习方法 1. **先尝试 20 分钟**，想不出来看提示 2. **理解思路**后，自己写一遍 3. **总结模板**，归纳同类题 4. **隔天复习**，确保掌握 --- ## 📊 全部题目索引 | 序号 | 题号 | 题目 | 难度 | 分类 | |-----|------|------|------|------| | 1 | 1 | 两数之和 | ⭐ | 哈希 | | 2 | 49 | 字母异位词分组 | ⭐⭐ | 哈希 | | 3 | 128 | 最长连续序列 | ⭐⭐ | 哈希 | | 4 | 283 | 移动零 | ⭐ | 双指针 | | 5 | 11 | 盛最多水的容器 | ⭐⭐ | 双指针 | | 6 | 15 | 三数之和 | ⭐⭐ | 双指针 | | 7 | 42 | 接雨水 | ⭐⭐⭐ | 双指针 | | 8 | 3 | 无重复字符的最长子串 | ⭐⭐ | 滑动窗口 | | 9 | 438 | 找到字符串中所有字母异位词 | ⭐⭐ | 滑动窗口 | | 10 | 560 | 和为K的子数组 | ⭐⭐ | 子串 | | 11 | 239 | 滑动窗口最大值 | ⭐⭐⭐ | 子串 | | 12 | 76 | 最小覆盖子串 | ⭐⭐⭐ | 子串 | | 13 | 53 | 最大子数组和 | ⭐⭐ | 数组 | | 14 | 56 | 合并区间 | ⭐⭐ | 数组 | | 15 | 189 | 轮转数组 | ⭐⭐ | 数组 | | 16 | 238 | 除自身以外数组的乘积 | ⭐⭐ | 数组 | | 17 | 41 | 缺失的第一个正数 | ⭐⭐⭐ | 数组 | | 18 | 73 | 矩阵置零 | ⭐⭐ | 矩阵 | | 19 | 54 | 螺旋矩阵 | ⭐⭐ | 矩阵 | | 20 | 48 | 旋转图像 | ⭐⭐ | 矩阵 | | 21 | 240 | 搜索二维矩阵 II | ⭐⭐ | 矩阵 | | 22 | 160 | 相交链表 | ⭐ | 链表 | | 23 | 206 | 反转链表 | ⭐ | 链表 | | 24 | 234 | 回文链表 | ⭐ | 链表 | | 25 | 141 | 环形链表 | ⭐ | 链表 | | 26 | 142 | 环形链表 II | ⭐⭐ | 链表 | | 27 | 21 | 合并两个有序链表 | ⭐ | 链表 | | 28 | 2 | 两数相加 | ⭐⭐ | 链表 | | 29 | 19 | 删除链表的倒数第N个节点 | ⭐⭐ | 链表 | | 30 | 24 | 两两交换链表中的节点 | ⭐⭐ | 链表 | | 31 | 25 | K个一组翻转链表 | ⭐⭐⭐ | 链表 | | 32 | 138 | 随机链表的复制 | ⭐⭐ | 链表 | | 33 | 148 | 排序链表 | ⭐⭐ | 链表 | | 34 | 23 | 合并K个升序链表 | ⭐⭐⭐ | 链表 | | 35 | 146 | LRU缓存 | ⭐⭐ | 链表 | | 36 | 94 | 二叉树的中序遍历 | ⭐ | 二叉树 | | 37 | 104 | 二叉树的最大深度 | ⭐ | 二叉树 | | 38 | 226 | 翻转二叉树 | ⭐ | 二叉树 | | 39 | 101 | 对称二叉树 | ⭐ | 二叉树 | | 40 | 543 | 二叉树的直径 | ⭐ | 二叉树 | | 41 | 102 | 二叉树的层序遍历 | ⭐⭐ | 二叉树 | | 42 | 108 | 有序数组转BST | ⭐ | 二叉树 | | 43 | 98 | 验证二叉搜索树 | ⭐⭐ | 二叉树 | | 44 | 230 | BST第K小元素 | ⭐⭐ | 二叉树 | | 45 | 199 | 二叉树右视图 | ⭐⭐ | 二叉树 | | 46 | 114 | 二叉树展开为链表 | ⭐⭐ | 二叉树 | | 47 | 105 | 从前序中序构造树 | ⭐⭐ | 二叉树 | | 48 | 437 | 路径总和 III | ⭐⭐ | 二叉树 | | 49 | 236 | 最近公共祖先 | ⭐⭐ | 二叉树 | | 50 | 124 | 二叉树最大路径和 | ⭐⭐⭐ | 二叉树 | | 51 | 200 | 岛屿数量 | ⭐⭐ | 图论 | | 52 | 994 | 腐烂的橘子 | ⭐⭐ | 图论 | | 53 | 207 | 课程表 | ⭐⭐ | 图论 | | 54 | 208 | 实现Trie | ⭐⭐ | 图论 | | 55 | 46 | 全排列 | ⭐⭐ | 回溯 | | 56 | 78 | 子集 | ⭐⭐ | 回溯 | | 57 | 17 | 电话号码字母组合 | ⭐⭐ | 回溯 | | 58 | 39 | 组合总和 | ⭐⭐ | 回溯 | | 59 | 22 | 括号生成 | ⭐⭐ | 回溯 | | 60 | 79 | 单词搜索 | ⭐⭐ | 回溯 | | 61 | 131 | 分割回文串 | ⭐⭐ | 回溯 | | 62 | 51 | N皇后 | ⭐⭐⭐ | 回溯 | | 63 | 35 | 搜索插入位置 | ⭐ | 二分查找 | | 64 | 74 | 搜索二维矩阵 | ⭐⭐ | 二分查找 | | 65 | 34 | 排序数组查找首末位置 | ⭐⭐ | 二分查找 | | 66 | 33 | 搜索旋转排序数组 | ⭐⭐ | 二分查找 | | 67 | 153 | 旋转数组最小值 | ⭐⭐ | 二分查找 | | 68 | 4 | 两个有序数组中位数 | ⭐⭐⭐ | 二分查找 | | 69 | 20 | 有效的括号 | ⭐ | 栈 | | 70 | 155 | 最小栈 | ⭐⭐ | 栈 | | 71 | 394 | 字符串解码 | ⭐⭐ | 栈 | | 72 | 739 | 每日温度 | ⭐⭐ | 栈 | | 73 | 84 | 柱状图最大矩形 | ⭐⭐⭐ | 栈 | | 74 | 215 | 第K大元素 | ⭐⭐ | 堆 | | 75 | 347 | 前K高频元素 | ⭐⭐ | 堆 | | 76 | 295 | 数据流中位数 | ⭐⭐⭐ | 堆 | | 77 | 121 | 买卖股票最佳时机 | ⭐ | 贪心 | | 78 | 55 | 跳跃游戏 | ⭐⭐ | 贪心 | | 79 | 45 | 跳跃游戏 II | ⭐⭐ | 贪心 | | 80 | 763 | 划分字母区间 | ⭐⭐ | 贪心 | | 81 | 70 | 爬楼梯 | ⭐ | 动态规划 | | 82 | 118 | 杨辉三角 | ⭐ | 动态规划 | | 83 | 198 | 打家劫舍 | ⭐⭐ | 动态规划 | | 84 | 279 | 完全平方数 | ⭐⭐ | 动态规划 | | 85 | 322 | 零钱兑换 | ⭐⭐ | 动态规划 | | 86 | 139 | 单词拆分 | ⭐⭐ | 动态规划 | | 87 | 300 | 最长递增子序列 | ⭐⭐ | 动态规划 | | 88 | 152 | 最大乘积子数组 | ⭐⭐ | 动态规划 | | 89 | 416 | 分割等和子集 | ⭐⭐ | 动态规划 | | 90 | 32 | 最长有效括号 | ⭐⭐⭐ | 动态规划 | | 91 | 62 | 不同路径 | ⭐⭐ | 多维DP | | 92 | 64 | 最小路径和 | ⭐⭐ | 多维DP | | 93 | 5 | 最长回文子串 | ⭐⭐ | 多维DP | | 94 | 1143 | 最长公共子序列 | ⭐⭐ | 多维DP | | 95 | 72 | 编辑距离 | ⭐⭐⭐ | 多维DP | | 96 | 136 | 只出现一次的数字 | ⭐ | 技巧 | | 97 | 169 | 多数元素 | ⭐ | 技巧 | | 98 | 75 | 颜色分类 | ⭐⭐ | 技巧 | | 99 | 31 | 下一个排列 | ⭐⭐ | 技巧 | | 100 | 287 | 寻找重复数 | ⭐⭐ | 技巧 | --- ## 🎯 核心算法模板总结 ### 1. 二分查找模板 ```java // 标准二分：找 target int left = 0, right = n - 1; while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] == target) return mid; else if (nums[mid] < target) left = mid + 1; else right = mid - 1; } // 找左边界：第一个 >= target while (left < right) { int mid = left + (right - left) / 2; if (nums[mid] >= target) right = mid; else left = mid + 1; } ``` ### 2. 回溯模板 ```java void backtrack(路径, 选择列表) { if (满足结束条件) { 结果.add(路径); return; } for (选择 : 选择列表) { 做选择; backtrack(路径, 选择列表); 撤销选择; } } ``` ### 3. BFS 模板 ```java Queue queue = new LinkedList<>(); queue.offer(start); while (!queue.isEmpty()) { int size = queue.size(); for (int i = 0; i < size; i++) { Node node = queue.poll(); // 处理节点 for (Node next : node.neighbors) { queue.offer(next); } } // 层数 +1 } ``` ### 4. 动态规划框架 ```java // 1. 定义状态 dp[i] = ... // 2. 状态转移方程 dp[i] = f(dp[i-1], dp[i-2], ...) // 3. 初始化 dp[0] = ... // 4. 返回结果 return dp[n] ``` ### 5. 单调栈模板 ```java Stack stack = new Stack<>(); for (int i = 0; i < n; i++) { while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) { int idx = stack.pop(); // idx 的右边第一个更大元素是 i } stack.push(i); } ``` --- 📞 联系作者 Gitee: @10 📞 联系方式 📧 邮箱：3142277367@qq.com 💬 微信：Keep4212 > 💪 **加油！算法是练出来的，坚持就是胜利！** > > 📌 **建议**：打印这份文档，每道题刷完后打勾 ✅，坚持一个月必有成效！