LeetCode top 100题
目录
| # | 分类 | 题目数 | 题号 |
|---|---|---|---|
| 1 | 哈希 | 3 | 1、49、128 |
| 2 | 双指针 | 4 | 283、11、15、42 |
| 3 | 滑动窗口 | 2 | 3、438 |
| 4 | 子串 | 3 | 560、239、76 |
| 5 | 普通数组 | 5 | 53、56、189、238、41 |
| 6 | 矩阵 | 4 | 73、54、48、240 |
| 7 | 链表 | 14 | 160、206、234、141、142、21、2、19、24、25、138、148、23、146 |
| 8 | 二叉树 | 15 | 94、104、226、101、543、102、108、98、230、199、114、105、437、236、124 |
| 9 | 图论 | 4 | 200、994、207、208 |
| 10 | 回溯 | 8 | 46、78、17、39、22、79、131、51 |
| 11 | 二分查找 | 6 | 35、74、34、33、153、4 |
| 12 | 栈 | 5 | 20、155、394、739、84 |
| 13 | 堆 | 3 | 215、347、295 |
| 14 | 贪心算法 | 4 | 121、55、45、763 |
| 15 | 动态规划 | 10 | 70、118、198、279、322、139、300、152、416、32 |
| 16 | 多维动态规划 | 5 | 62、64、5、1143、72 |
| 17 | 技巧 | 5 | 136、169、75、31、287 |
附录：节点类定义
// 链表节点
class ListNode {
int val;
ListNode next;
ListNode() {}
ListNode(int val) { this.val = val; }
ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
// 二叉树节点
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {}
TreeNode(int val) { this.val = val; }
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
一、哈希（3 题）
1. 两数之和（简单）
题目要求：给定一个整数数组 nums 和一个目标值 target，在数组中找出和为 target 的两个数，并返回它们的下标。可以假设每个输入恰好只有一个解，且同一个元素不能使用两次。nums 长度至少为 2，数值范围为 int。 示例：输入 nums = [2,7,11,15]，target = 9 → 输出 [0,1]（nums[0]+nums[1] == 9）。 示例：输入 nums = [3,2,4]，target = 6 → 输出 [1,2]。
思路：暴力两层循环是 O(n²)，换个角度——遍历到 nums[i] 时，我们要找的"补数" target - nums[i] 在不在之前出现过？用哈希表把"已见过的数 → 下标"存下来，每来一个新数 O(1) 查补数是否存在，存在就直接返回两个下标，否则把当前数塞进表。这是"空间换时间"的经典套路。 时间复杂度 O(n)，空间复杂度 O(n)。
代码：
import java.util.*;
class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int complement = target - nums[i];
if (map.containsKey(complement)) {
return new int[]{map.get(complement), i};
}
map.put(nums[i], i);
}
return new int[0];
}
}
49. 字母异位词分组（中等）
题目要求：给定一个字符串数组 strs，把其中互为字母异位词（字母相同、顺序不同）的字符串分到同一组，返回分组结果（顺序任意）。所有输入均为小写字母组成的非空字符串，strs 长度至少为 1。 示例：输入 strs = [“eat”,“tea”,“tan”,“ate”,“nat”,“bat”] → 输出 [[“bat”],[“nat”,“tan”],[“ate”,“eat”,“tea”]]。 示例：输入 strs = [""] → 输出 [[""]]。
思路：异位词就是字母相同、顺序不同的串，关键是给它们找一个"统一的指纹"。最直观的做法是把每个串排序——排序后的字符串一定相同，用它当 key，原串塞进对应 List。也可以用 26 个字母计数数组当 key，但排序写法代码量更小、可读性更好。 时间复杂度 O(n · k log k)，n 是字符串个数、k 是最长串长度；空间复杂度 O(n · k)。
代码：
import java.util.*;
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
Map<String, List<String>> map = new HashMap<>();
for (String s : strs) {
char[] arr = s.toCharArray();
Arrays.sort(arr);
String key = new String(arr);
map.computeIfAbsent(key, k -> new ArrayList<>()).add(s);
}
return new ArrayList<>(map.values());
}
}
128. 最长连续序列（中等）
题目要求：给定一个未排序的整数数组 nums，找出其中数字连续的最长序列的长度。要求时间复杂度 O(n)。nums 长度可为 0（此时返回 0），数值范围为 int，可能有重复元素。 示例：输入 nums = [100,4,200,1,3,2] → 输出 4（最长连续序列是 [1,2,3,4]）。 示例：输入 nums = [0,3,7,2,5,8,4,6,0,1] → 输出 9。
思路：要求 O(n)，排序就废了。把所有数塞进 HashSet，然后遍历——如果 n-1 不在集合里，说明 n 是一段连续序列的起点，从 n 开始一路数 n+1、n+2……直到断了，记录长度。为什么要"从起点开始数"？因为如果不这么判断，每个数都会把自己前后整段重数一遍，退化成 O(n²)。用"只从左边界出发"这一条规则，每个数最多被访问两次。 时间复杂度 O(n)，空间复杂度 O(n)。
代码：
import java.util.*;
class Solution {
public int longestConsecutive(int[] nums) {
Set<Integer> set = new HashSet<>();
for (int n : nums) set.add(n);
int max = 0;
for (int n : set) {
if (!set.contains(n - 1)) {
int cur = n;
int len = 1;
while (set.contains(cur + 1)) {
cur++;
len++;
}
max = Math.max(max, len);
}
}
return max;
}
}
二、双指针（4 题）
283. 移动零（简单）
题目要求：给定数组 nums，将所有 0 移动到数组末尾，同时保持所有非零元素的相对顺序不变。必须原地修改数组，不能复制数组。nums 长度可为 0。 示例：输入 nums = [0,1,0,3,12] → 输出 [1,3,12,0,0]。 示例：输入 nums = [0] → 输出 [0]。
思路：原地把所有 0 挪到末尾，不能开额外数组。用快慢两个指针：慢指针 j 指向"下一个非零元素该放的位置"，快指针 i 扫一遍数组，遇到非零就和 nums[j] 交换，j 后移。这样扫完一遍，非零元素相对顺序不变，尾部自然全是 0。一次遍历搞定，不用先填非零再补零。 时间复杂度 O(n)，空间复杂度 O(1)。
代码：
class Solution {
public void moveZeroes(int[] nums) {
int j = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] != 0) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
j++;
}
}
}
}
11. 盛最多水的容器（中等）
题目要求：给定长度为 n 的整数数组 height，每个元素代表一条垂直线的高度。选两条线与 x 轴构成一个容器，求能盛最多水的容量（面积 = 两线间距 × 较矮线高度）。n 至少为 2，高度为正整数。 示例：输入 height = [1,8,6,2,5,4,8,3,7] → 输出 49（下标 1 和 8，min(8,7)×7 = 49）。 示例：输入 height = [1,1] → 输出 1。
思路：暴力枚举左右边是 O(n²)。双指针从两端开始：容量 = 较短边 × 间距。每次移动哪一边？移动长的那边——短边没变，间距还小了，容量只会更差。所以必须移动较短的那一边，才有可能找到更高的边把容量撑大。每一步都排除了一个"不可能更优"的状态，O(n) 扫完。 时间复杂度 O(n)，空间复杂度 O(1)。
代码：
class Solution {
public int maxArea(int[] height) {
int l = 0, r = height.length - 1;
int ans = 0;
while (l < r) {
int h = Math.min(height[l], height[r]);
ans = Math.max(ans, h * (r - l));
if (height[l] < height[r]) {
l++;
} else {
r--;
}
}
return ans;
}
}
15. 三数之和（中等）
题目要求：给定整数数组 nums，找出所有和为 0 的三元组 [a,b,c]，要求三元组不重复（不能出现相同组合）。nums 长度至少为 3，可能有重复元素，结果顺序任意。 示例：输入 nums = [-1,0,1,2,-1,-4] → 输出 [[-1,-1,2],[-1,0,1]]。 示例：输入 nums = [0,1,1] → 输出 []。
思路：把 a + b + c = 0 转化为"固定一个 a，在剩余区间里用双指针找 b + c = -a"。先排序，外层枚举 a，内层 l = i+1、r = n-1 往中间夹：和太小 l 右移，和太大 r 左移，找到一组就记录。关键是去重——a 重复、l 和 r 重复都要跳过，不然结果里会有重复三元组。排序是 O(n log n)，外层 O(n) × 内层 O(n) = O(n²)，整体被 O(n²) 主导。 时间复杂度 O(n²)，空间复杂度 O(log n)（排序栈开销）。
代码：
import java.util.*;
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
Arrays.sort(nums);
for (int i = 0; i < nums.length - 2; i++) {
if (nums[i] > 0) break;
if (i > 0 && nums[i] == nums[i - 1]) continue;
int l = i + 1, r = nums.length - 1;
while (l < r) {
int sum = nums[i] + nums[l] + nums[r];
if (sum == 0) {
res.add(Arrays.asList(nums[i], nums[l], nums[r]));
while (l < r && nums[l] == nums[l + 1]) l++;
while (l < r && nums[r] == nums[r - 1]) r--;
l++;
r--;
} else if (sum < 0) {
l++;
} else {
r--;
}
}
}
return res;
}
}
42. 接雨水（困难）
题目要求：给定 n 个非负整数表示柱状图中每根柱子的高度，柱子宽度为 1，求下雨后这些柱子能接住多少单位的雨水。 示例：输入 height = [0,1,0,2,1,0,1,3,2,1,2,1] → 输出 6。 示例：输入 height = [4,2,0,3,2,5] → 输出 9。
思路：每根柱子能接多少水，取决于它左边最高柱和右边最高柱里"较矮的那根"减去自身高度。朴素做法是每个位置都往左往右扫一遍，O(n²)；用 DP 预存 leftMax/rightMax 数组是 O(n)/O(n)。再进一步优化到 O(1) 空间——双指针法：l、r 从两端往中间走，维护 lmax 和 rmax。因为如果 lmax < rmax，那 l 位置的瓶颈一定是 lmax（右边更高的 rmax 已经存在），所以 l 位置的水量可以直接算；反之算 r。这一步巧妙在于"只需要知道对侧更高的那堵墙存在"，不需要知道它具体在哪。这是 O(n) 时间、O(1) 空间的最优解，单调栈法虽然也是 O(n) 但空间 O(n) 且不如这个直观。 时间复杂度 O(n)，空间复杂度 O(1)。
代码：
class Solution {
public int trap(int[] height) {
int l = 0, r = height.length - 1;
int lmax = 0, rmax = 0, ans = 0;
while (l < r) {
if (height[l] < height[r]) {
if (height[l] >= lmax) {
lmax = height[l];
} else {
ans += lmax - height[l];
}
l++;
} else {
if (height[r] >= rmax) {
rmax = height[r];
} else {
ans += rmax - height[r];
}
r--;
}
}
return ans;
}
}
三、滑动窗口（2 题）
3. 无重复字符的最长子串（中等）
题目要求：给定一个字符串 s，找出其中不含有重复字符的最长子串的长度。s 由英文字母、数字、符号和空格组成，长度可为 0（此时返回 0）。 示例：输入 s = “abcabcbb” → 输出 3（最长子串 “abc”）。 示例：输入 s = “bbbbb” → 输出 1。
思路：典型滑动窗口——维护一个窗口 [l, r]，保证里面所有字符不重复。r 不断右移加入新字符，如果这个字符在窗口里出现过（用哈希表记录"字符 → 最近一次出现的下标"），就把 l 直接跳到"上次出现位置 + 1"，一步到位而不是一格一格挪。每加一个字符就更新窗口最大长度。 时间复杂度 O(n)，空间复杂度 O(|Σ|)（字符集大小）。
代码：
import java.util.*;
class Solution {
public int lengthOfLongestSubstring(String s) {
Map<Character, Integer> map = new HashMap<>();
int l = 0, ans = 0;
for (int r = 0; r < s.length(); r++) {
char c = s.charAt(r);
if (map.containsKey(c)) {
l = Math.max(l, map.get(c) + 1);
}
map.put(c, r);
ans = Math.max(ans, r - l + 1);
}
return ans;
}
}
438. 找到字符串中所有字母异位词（中等）
题目要求：给定字符串 s 和非空字符串 p，找出 s 中所有是 p 的字母异位词的子串，返回这些子串的起始下标（顺序任意）。s、p 均只含小写字母，若 s 长度小于 p 则返回空数组。 示例：输入 s = “cbaebabacd”，p = “abc” → 输出 [0,6]。 示例：输入 s = “abab”，p = “ab” → 输出 [0,1,2]。
思路：固定长度的滑动窗口。窗口大小等于 p 的长度，用两个长度 26 的计数数组——need 记 p 中每个字母出现几次，win 记当前窗口里每个字母出现几次。r 每右移一格就把新字符计入 win，窗口滑出左边界时把旧字符减去，两个数组相等就说明当前窗口是 p 的异位词。数组直接用 Arrays.equals 比较，简洁高效。 时间复杂度 O(n)，n 是 s 的长度；空间复杂度 O(1)（两个定长数组）。
代码：
import java.util.*;
class Solution {
public List<Integer> findAnagrams(String s, String p) {
List<Integer> res = new ArrayList<>();
if (s.length() < p.length()) return res;
int[] need = new int[26];
for (char c : p.toCharArray()) need[c - 'a']++;
int[] win = new int[26];
int k = p.length();
for (int i = 0; i < s.length(); i++) {
win[s.charAt(i) - 'a']++;
if (i >= k) win[s.charAt(i - k) - 'a']--;
if (i >= k - 1 && Arrays.equals(need, win)) {
res.add(i - k + 1);
}
}
return res;
}
}
四、子串（3 题）
560. 和为 K 的子数组（中等）
题目要求：给定一个整数数组 nums 和一个整数 k，统计其中和为 k 的"连续子数组"的个数。子数组至少包含一个元素，nums 长度至少为 1，数值可为负数。 示例：输入 nums = [1,1,1]，k = 2 → 输出 2（[1,1] 出现两次）。 示例：输入 nums = [1,2,3]，k = 3 → 输出 2（[1,2] 和 [3]）。
思路：子数组是连续段，前缀和是天然工具。定义 prefix[i] = nums[0..i] 的和，那么子数组 j+1..i 的和 = prefix[i] - prefix[j]。我们要找的就是"prefix[i] - prefix[j] = k"，即"对于当前 prefix[i]，前面有多少个 prefix[j] 等于 prefix[i] - k"。用哈希表存"前缀和 → 出现次数"，边遍历边查、边累加答案。注意要先 put(0, 1)，不然会漏掉"从下标 0 开始"的那段。 时间复杂度 O(n)，空间复杂度 O(n)。
代码：
import java.util.*;
class Solution {
public int subarraySum(int[] nums, int k) {
Map<Integer, Integer> map = new HashMap<>();
map.put(0, 1);
int sum = 0, ans = 0;
for (int n : nums) {
sum += n;
ans += map.getOrDefault(sum - k, 0);
map.put(sum, map.getOrDefault(sum, 0) + 1);
}
return ans;
}
}
239. 滑动窗口最大值（困难）
题目要求：给定整数数组 nums 和大小为 k 的滑动窗口，窗口从数组最左端滑到最右端，每次只能看到 k 个数，返回每个窗口位置的最大值。nums 长度至少为 k，k 至少为 1。 示例：输入 nums = [1,3,-1,-3,5,3,6,7]，k = 3 → 输出 [3,3,5,5,6,7]。 示例：输入 nums = [1]，k = 1 → 输出 [1]。
思路：窗口每右移一格，要在 O(1) 均摊时间内拿到最大值。暴力扫窗口是 O(nk)，用堆是 O(n log k)。最优是单调双端队列：队列里存下标，保证对应的值单调递减——队首永远是当前窗口的最大值。每来一个新元素 nums[i]，把队列尾部所有比它小的元素全部弹掉（它们再也没机会当最大值了），再把 i 入队；同时队首如果滑出窗口左边界就弹出。这样每个元素最多入队、出队各一次，均摊 O(1)。这是单调队列的经典题。 时间复杂度 O(n)，空间复杂度 O(k)（队列最多存窗口大小）。
代码：
import java.util.*;
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int n = nums.length;
int[] res = new int[n - k + 1];
Deque<Integer> dq = new ArrayDeque<>();
for (int i = 0; i < n; i++) {
while (!dq.isEmpty() && dq.peekFirst() < i - k + 1) dq.pollFirst();
while (!dq.isEmpty() && nums[dq.peekLast()] <= nums[i]) dq.pollLast();
dq.offerLast(i);
if (i >= k - 1) res[i - k + 1] = nums[dq.peekFirst()];
}
return res;
}
}
76. 最小覆盖子串（困难）
题目要求：给定字符串 s 和字符串 t，找出 s 中包含 t 所有字符（含重复次数）的最短子串；若不存在则返回空字符串。t 中可能有重复字符，这些重复字符在结果子串中也必须至少出现对应次数。s、t 由大小写英文字母组成。 示例：输入 s = “ADOBECODEBANC”，t = “ABC” → 输出 “BANC”。 示例：输入 s = “a”，t = “aa” → 输出 “"。
思路：滑动窗口的进阶版。维护窗口 [l, r] 和一个 need 表（t 中每个字符需要出现几次）。r 右移扩大窗口，每当窗口里"已满足要求的字符种类数"cnt 达到 need 的大小时，就说明窗口已经覆盖了 t，然后尝试左移 l 缩小窗口——每缩一次都记录一次最短长度，直到窗口不再覆盖 t 为止。这套"右扩找满足、左缩找最优"是滑动窗口求最小覆盖子串的标准模板，时间 O(n)。 时间复杂度 O(|s| + |t|)，空间复杂度 O(|Σ|)。
代码：
import java.util.*;
class Solution {
public String minWindow(String s, String t) {
Map<Character, Integer> need = new HashMap<>();
for (char c : t.toCharArray()) {
need.put(c, need.getOrDefault(c, 0) + 1);
}
Map<Character, Integer> win = new HashMap<>();
int l = 0, cnt = 0;
int minLen = Integer.MAX_VALUE, start = 0;
for (int r = 0; r < s.length(); r++) {
char c = s.charAt(r);
if (need.containsKey(c)) {
win.put(c, win.getOrDefault(c, 0) + 1);
if (win.get(c).intValue() == need.get(c).intValue()) cnt++;
}
while (cnt == need.size()) {
if (r - l + 1 < minLen) {
minLen = r - l + 1;
start = l;
}
char d = s.charAt(l);
if (need.containsKey(d)) {
if (win.get(d).intValue() == need.get(d).intValue()) cnt--;
win.put(d, win.get(d) - 1);
}
l++;
}
}
return minLen == Integer.MAX_VALUE ? "" : s.substring(start, start + minLen);
}
}
五、普通数组（5 题）
53. 最大子数组和（中等）
题目要求：给你一个整数数组 nums，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。数组长度 1～10^5，元素取值在 [-10^4, 10^4] 之间。 输入 nums = [-2,1,-3,4,-1,2,1,-5,4] → 输出 6（连续子数组 [4,-1,2,1] 的和最大，为 6）。
思路：动态规划经典题，Kadane 算法。核心一步：遍历到每个位置时问自己"以当前元素结尾的最大子数组和是多少”——要么接上前面的子数组（cur + nums[i]），要么从当前元素重新开始（nums[i]），取较大者。全程用一个变量维护当前和，同时更新全局最大值，不需要 DP 数组。
时间复杂度 O(n)，空间复杂度 O(1)。
class Solution {
public int maxSubArray(int[] nums) {
int maxSum = nums[0], cur = nums[0];
for (int i = 1; i < nums.length; i++) {
cur = Math.max(nums[i], cur + nums[i]);
maxSum = Math.max(maxSum, cur);
}
return maxSum;
}
}
56. 合并区间（中等）
题目要求：以数组 intervals 表示若干个区间，其中 intervals[i] = [start_i, end_i]。请你合并所有重叠的区间，返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。 输入 intervals = [[1,3],[2,6],[8,10],[15,18]] → 输出 [[1,6],[8,10],[15,18]]（区间 [1,3] 和 [2,6] 重叠，合并为 [1,6]）。
思路：先按区间左端点排序，然后线性扫描。维护结果列表最后一个区间，遇到下一个区间：如果它的左端点 <= 上一个区间右端点，说明重叠，把右端点更新为两者的较大值；否则直接追加。排序后一次扫描就能合并所有重叠区间。 时间复杂度 O(n log n)，空间复杂度 O(n)（存储结果）。
import java.util.*;
class Solution {
public int[][] merge(int[][] intervals) {
Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
List<int[]> res = new ArrayList<>();
for (int[] interval : intervals) {
if (res.isEmpty() || interval[0] > res.get(res.size() - 1)[1]) {
res.add(interval);
} else {
res.get(res.size() - 1)[1] = Math.max(res.get(res.size() - 1)[1], interval[1]);
}
}
return res.toArray(new int[res.size()][]);
}
}
189. 轮转数组（中等）
题目要求：给定一个整数数组 nums，将数组元素向右轮转 k 个位置（k 是非负数），要求使用空间复杂度 O(1) 的原地算法解决。 输入 nums = [1,2,3,4,5,6,7]，k = 3 → 输出 [5,6,7,1,2,3,4]。
思路：要求 O(1) 空间时用"三次翻转"法。先整体翻转，再把前 k%n 个元素翻转回来，最后把剩余元素翻转回来。举例 [1,2,3,4,5,6,7] k=3：整体翻转成 [7,6,5,4,3,2,1]，前 3 个翻成 [5,6,7,...]，后 4 个翻成 [...,1,2,3,4]，得到 [5,6,7,1,2,3,4]。注意 k 要先对 n 取模。
时间复杂度 O(n)，空间复杂度 O(1)。
class Solution {
public void rotate(int[] nums, int k) {
int n = nums.length;
k %= n;
reverse(nums, 0, n - 1);
reverse(nums, 0, k - 1);
reverse(nums, k, n - 1);
}
private void reverse(int[] nums, int left, int right) {
while (left < right) {
int tmp = nums[left];
nums[left] = nums[right];
nums[right] = tmp;
left++;
right--;
}
}
}
238. 除自身以外数组的乘积（中等）
题目要求：给定整数数组 nums，返回数组 answer，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。要求不能使用除法，且在 O(n) 时间内完成。题目数据保证数组中除 nums[i] 外任意元素的乘积都能用 32 位整数表示。 输入 nums = [1,2,3,4] → 输出 [24,12,8,6]。
思路：题目禁止用除法，那自然想到"前缀乘积 × 后缀乘积"。先从左到右遍历，ans[i] 存 i 左边所有数的乘积；再从右到左遍历，用一个变量 right 维护 i 右边所有数的乘积，乘到 ans[i] 上。两次遍历即完成，不需要额外数组。
时间复杂度 O(n)，空间复杂度 O(1)（输出数组不计入额外空间）。
class Solution {
public int[] productExceptSelf(int[] nums) {
int n = nums.length;
int[] ans = new int[n];
ans[0] = 1;
for (int i = 1; i < n; i++) {
ans[i] = ans[i - 1] * nums[i - 1];
}
int right = 1;
for (int i = n - 1; i >= 0; i--) {
ans[i] *= right;
right *= nums[i];
}
return ans;
}
}
41. 缺失的第一个正数（困难）
题目要求：给定一个未排序的整数数组 nums，找出其中没有出现的最小的正整数。要求实现时间复杂度 O(n) 且只使用常数级别的额外空间。 输入 nums = [1,2,0] → 输出 3；输入 nums = [3,4,-1,1] → 输出 2；输入 nums = [7,8,9,11,12] → 输出 1。
思路：原地哈希（桶思想）。要求 O(n) 时间 O(1) 空间，那就把数组本身当哈希表：目标是让数值 v 放到索引 v-1 的位置。从头到尾遍历，只要 nums[i] 在 [1, n] 范围内且不在自己该在的位置，就交换过去。最后再扫一遍，第一个 nums[i] != i+1 的位置就是答案；都齐了则答案是 n+1。
时间复杂度 O(n)，空间复杂度 O(1)。
class Solution {
public int firstMissingPositive(int[] nums) {
int n = nums.length;
for (int i = 0; i < n; i++) {
while (nums[i] >= 1 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
int tmp = nums[nums[i] - 1];
nums[nums[i] - 1] = nums[i];
nums[i] = tmp;
}
}
for (int i = 0; i < n; i++) {
if (nums[i] != i + 1) return i + 1;
}
return n + 1;
}
}
六、矩阵（4 题）
73. 矩阵置零（中等）
题目要求：给定一个 m × n 的矩阵，如果一个元素为 0，则将其所在行和列的所有元素都设为 0。要求使用原地算法，并尽量优化空间复杂度。 输入 matrix = [[1,1,1],[1,0,1],[1,1,1]] → 输出 [[1,0,1],[0,0,0],[1,0,1]]。
思路：要用 O(1) 空间，就用矩阵第一行和第一列当"标记位"。先扫描整个矩阵，遇到 0 就把对应的第一行、第一列位置标为 0；然后再根据这些标记把对应行列置零。注意：第一行和第一列本身是否有 0 要单独用两个布尔变量记录，否则会把整个矩阵都误置零。 时间复杂度 O(mn)，空间复杂度 O(1)。
class Solution {
public void setZeroes(int[][] matrix) {
int m = matrix.length, n = matrix[0].length;
boolean firstRowZero = false, firstColZero = false;
for (int j = 0; j < n; j++) {
if (matrix[0][j] == 0) firstRowZero = true;
}
for (int i = 0; i < m; i++) {
if (matrix[i][0] == 0) firstColZero = true;
}
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;
}
}
}
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;
}
}
}
if (firstRowZero) {
for (int j = 0; j < n; j++) matrix[0][j] = 0;
}
if (firstColZero) {
for (int i = 0; i < m; i++) matrix[i][0] = 0;
}
}
}
54. 螺旋矩阵（中等）
题目要求：给定一个 m 行 n 列的矩阵 matrix，请按照顺时针螺旋顺序，返回矩阵中的所有元素。 输入 matrix = [[1,2,3],[4,5,6],[7,8,9]] → 输出 [1,2,3,6,9,8,7,4,5]；输入 matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]] → 输出 [1,2,3,4,8,12,11,10,9,5,6,7]。
思路：模拟四条边界。维护 top、bottom、left、right 四个边界，按"从左到右 → 从上到下 → 从右到左 → 从下到上"的顺序遍历，每走完一条边就收缩对应边界。关键细节：从右到左和从下到上之前要检查边界是否还合法，防止单行或单列时重复遍历。 时间复杂度 O(mn)，空间复杂度 O(1)（输出数组不计）。
import java.util.*;
class Solution {
public List<Integer> spiralOrder(int[][] matrix) {
List<Integer> res = new ArrayList<>();
int m = matrix.length, n = matrix[0].length;
int top = 0, bottom = m - 1, left = 0, right = n - 1;
while (left <= right && top <= bottom) {
for (int j = left; j <= right; j++) res.add(matrix[top][j]);
top++;
for (int i = top; i <= bottom; i++) res.add(matrix[i][right]);
right--;
if (top <= bottom) {
for (int j = right; j >= left; j--) res.add(matrix[bottom][j]);
bottom--;
}
if (left <= right) {
for (int i = bottom; i >= top; i--) res.add(matrix[i][left]);
left++;
}
}
return res;
}
}
48. 旋转图像（中等）
题目要求：给定一个 n × n 的二维矩阵 matrix 表示一个图像，将矩阵顺时针旋转 90 度。必须在原地修改输入矩阵，不能使用另一个矩阵来旋转。 输入 matrix = [[1,2,3],[4,5,6],[7,8,9]] → 输出 [[7,4,1],[8,5,2],[9,6,3]]。
思路：要求原地顺时针旋转 90 度，经典两步走：先转置（matrix[i][j] 与 matrix[j][i] 交换，只遍历上三角），再把每一行左右翻转一下。转置把行列互换，行翻转把左右顺序倒过来，合起来就是顺时针 90 度。
时间复杂度 O(n²)，空间复杂度 O(1)。
class Solution {
public void rotate(int[][] matrix) {
int n = matrix.length;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
int tmp = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = tmp;
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n / 2; j++) {
int tmp = matrix[i][j];
matrix[i][j] = matrix[i][n - 1 - j];
matrix[i][n - 1 - j] = tmp;
}
}
}
}
240. 搜索二维矩阵 II（中等）
题目要求：编写一个高效算法，在 m × n 矩阵中搜索目标值 target。该矩阵每行的元素从左到右升序排列，每列的元素从上到下升序排列。 输入 matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]]，target = 5 → 输出 true；target = 20 → 输出 false。
思路：矩阵每行从左到右递增、每列从上到下递增，所以从右上角开始"Z 字形"搜索：当前值比 target 大，说明这一列往下只会更大，左移；当前值比 target 小，说明这一行往左只会更小，下移。每次排除一行或一列，效率很高。 时间复杂度 O(m+n)，空间复杂度 O(1)。
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
int m = matrix.length, n = matrix[0].length;
int i = 0, j = n - 1;
while (i < m && j >= 0) {
if (matrix[i][j] == target) return true;
else if (matrix[i][j] > target) j--;
else i++;
}
return false;
}
}
七、链表（14 题）
160. 相交链表（简单）
题目要求：给定两个单链表的头节点 headA 和 headB，请找出并返回两个链表相交的起始节点；若不相交返回 null。题目保证整体无环，且不能修改原链表。节点总数范围在 0～3×10⁴，要求尽量用 O(1) 空间。输入 intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5] → 输出值为 8 的那个相交节点。输入 listA = [2,6,4], listB = [1,5] → 输出 null。
思路：双指针走"自己的路 + 对方的路"是经典套路。两个指针分别从 headA、headB 出发，每次走一步；走到 null 后就改从另一条链表头继续走。这样两个指针走过的总长度都是 lenA + lenB，如果两链表相交，它们一定会在交点处相遇；如果不相交，会同时走到 null。本质是消除两条链表长度差，让两个指针对齐到同一个起跑点。空间 O(1)，不用哈希表。
时间复杂度 O(m+n)，空间复杂度 O(1)。
代码：
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode a = headA, b = headB;
while (a != b) {
a = (a == null) ? headB : a.next;
b = (b == null) ? headA : b.next;
}
return a;
}
}
206. 反转链表（简单）
题目要求：给定单链表的头节点 head，请反转链表并返回新的头节点。节点数范围 0～5000，节点值 -5000～5000。要求就地反转（不能新建整条链表）。输入 head = [1,2,3,4,5] → 输出 [5,4,3,2,1]。输入 head = [] → 输出 null。
思路：迭代法用三个指针 prev / curr / next 边遍历边翻转。核心一步：先把 curr.next 暂存到 next（不然断链找不回去），再让 curr.next = prev，然后整体后移。递归法则是先把后面的节点都反转好，再把当前节点接到后面。迭代法直观且面试常写，选它。dummy 节点不需要，直接在原链上改指针即可。
时间复杂度 O(n)，空间复杂度 O(1)。
代码：
public class Solution {
public 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;
}
}
234. 回文链表（简单）
题目要求：给定单链表头节点 head，判断链表是否为回文序列，是则返回 true，否则返回 false。节点数范围 1～10⁵，节点值 0～9。进阶要求 O(n) 时间且 O(1) 空间。输入 head = [1,2,2,1] → 输出 true。输入 head = [1,2] → 输出 false。
思路：要求 O(1) 空间，就不能用栈。套路是"快慢指针找中点 + 反转后半段 + 逐段比较"。快慢指针走一遍，slow 停在中点（偶数时长的后半段起点）；把后半段反转后，从 head 和反转后中点各自往后比，全部相等才是回文。最后可以把链表再反转回去（题目不强制，但好习惯）。找中点用 fast != null && fast.next != null 的写法，保证 slow 停在偶数长度时是后半段开头，便于反转。
时间复杂度 O(n)，空间复杂度 O(1)。
代码：
public class Solution {
public boolean isPalindrome(ListNode head) {
if (head == null || head.next == null) return true;
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
ListNode prev = null, curr = slow;
while (curr != null) {
ListNode next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
ListNode p1 = head, p2 = prev;
while (p2 != null) {
if (p1.val != p2.val) return false;
p1 = p1.next;
p2 = p2.next;
}
return true;
}
}
141. 环形链表（简单）
题目要求：给定单链表头节点 head，判断链表中是否存在环（某节点能通过 next 再次回到自己），存在返回 true，否则返回 false。节点数范围 0～10⁴。pos 用于表示尾节点连接到的索引（-1 表示无环），做题时不需要传 pos。输入 head = [3,2,0,-4], pos = 1 → 输出 true。输入 head = [1,2], pos = 0 → 输出 true。输入 head = [1], pos = -1 → 输出 false。
思路：快慢指针经典题。慢指针每次走一步，快指针每次走两步；如果有环，快指针一定会在环里追上慢指针（相对速度一步/次，必相遇）。如果快指针走到 null 则无环。不需要额外空间，比哈希表省内存。边界处理：head 为 null 直接返回 false。
时间复杂度 O(n)，空间复杂度 O(1)。
代码：
public class Solution {
public boolean hasCycle(ListNode head) {
if (head == 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;
}
}
142. 环形链表 II（中等）
题目要求：给定单链表头节点 head，返回链表开始入环的第一个节点；若无环返回 null。不允许修改链表。节点数范围 0～10⁴。输入 head = [3,2,0,-4], pos = 1 → 输出值为 2 的节点（环入口）。输入 head = [1,2], pos = 0 → 输出值为 1 的节点。输入 head = [1], pos = -1 → 输出 null。
思路：在 141 的基础上找环入口。快慢指针相遇后，把其中一个指针放回 head，两个指针每次都走一步，再次相遇的点就是环入口。数学原理：设 head 到入口距离 a，入口到相遇点 b，环长 c；快慢相遇时 2(a+b) = a+b + kc，化简得 a = kc - b，所以从 head 走 a 步 = 从相遇点走 (kc-b) 步，正好在入口相遇。套路要记结论，不必每次推。
时间复杂度 O(n)，空间复杂度 O(1)。
代码：
public class Solution {
public ListNode detectCycle(ListNode head) {
if (head == null) return null;
ListNode slow = head, fast = head;
boolean hasCycle = false;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) { hasCycle = true; break; }
}
if (!hasCycle) return null;
ListNode p = head;
while (p != slow) {
p = p.next;
slow = slow.next;
}
return p;
}
}
21. 合并两个有序链表（简单）
题目要求：给定两个已按升序排列的链表头 list1 和 list2，将它们合并成一个升序链表并返回新头。节点数范围 0～50，节点值 -100～100，两个链表均按非降序排列。输入 list1 = [1,2,4], list2 = [1,3,4] → 输出 [1,1,2,3,4,4]。输入 list1 = [], list2 = [] → 输出 null。
思路：dummy 哑结点的典型应用。新建一个 dummy 作为新链表头，用一个 tail 指针向后接节点；两个链表各自一个指针，谁小接谁，走一步。其中一条走完后，把另一条剩下的整体接上即可。用 dummy 是因为新链表头会变化（不是原链表头），用哑节点可以统一处理，不用单独写 if。
时间复杂度 O(m+n)，空间复杂度 O(1)。
代码：
public class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
ListNode dummy = new ListNode(0);
ListNode tail = dummy;
while (list1 != null && list2 != null) {
if (list1.val <= list2.val) {
tail.next = list1;
list1 = list1.next;
} else {
tail.next = list2;
list2 = list2.next;
}
tail = tail.next;
}
tail.next = (list1 != null) ? list1 : list2;
return dummy.next;
}
}
2. 两数相加（中等）
题目要求：给定两个非空链表 l1、l2，分别表示两个非负整数，每一位数字按逆序存储（即低位在表头）。请将两数相加并以同样逆序链表形式返回。节点数范围 1～100，节点值 0～9，除了数字 0 本身不含前导零。输入 l1 = [2,4,3], l2 = [5,6,4] → 输出 [7,0,8]（对应 342 + 465 = 807）。输入 l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9] → 输出 [8,9,9,9,0,0,0,1]。
思路：dummy 哑结点 + 进位变量。两个链表本来就是低位在前，正好按加法从低位开始逐位算：每轮取两个节点的值（null 当 0），加进 carry，写一个新节点。carry 要带上 carry / 10 进入下一轮。两链表都走完后，若 carry 还剩 1，要再补一个节点。dummy 节点同样是为了统一头节点处理。
时间复杂度 O(max(m,n))，空间复杂度 O(max(m,n))。
代码：
public class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0);
ListNode tail = dummy;
int carry = 0;
while (l1 != null || l2 != null || carry != 0) {
int x = (l1 != null) ? l1.val : 0;
int y = (l2 != null) ? l2.val : 0;
int sum = x + y + carry;
carry = sum / 10;
tail.next = new ListNode(sum % 10);
tail = tail.next;
if (l1 != null) l1 = l1.next;
if (l2 != null) l2 = l2.next;
}
return dummy.next;
}
}
19. 删除链表的倒数第 N 个结点（中等）
题目要求：给定链表头节点 head 和整数 n（保证有效），删除链表中倒数第 n 个节点，并返回删除后的新头节点。节点数范围 1～30，1 ≤ n ≤ 链表长度。输入 head = [1,2,3,4,5], n = 2 → 输出 [1,2,3,5]（删掉了倒数第 2 个节点 4）。输入 head = [1], n = 1 → 输出 null。
思路：dummy 哑结点 + 快慢指针。先让 fast 从 dummy 出发走 N+1 步，再让 slow 和 fast 一起走；fast 走到 null 时，slow 正好停在"要删节点的前一个"。为什么用 dummy？因为有可能删除的是头节点（倒数第 length 个），不用哑节点得特殊处理。fast 先走 N+1 步而不是 N 步，是为了让 slow 落在待删节点的前驱上，方便直接 slow.next = slow.next.next。
时间复杂度 O(n)，空间复杂度 O(1)。
代码：
public class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode fast = dummy, slow = dummy;
for (int i = 0; i <= n; i++) fast = fast.next;
while (fast != null) {
fast = fast.next;
slow = slow.next;
}
slow.next = slow.next.next;
return dummy.next;
}
}
24. 两两交换链表中的节点（中等）
题目要求：给定链表头节点 head，两两交换相邻的节点（不能只交换节点里的 val，必须真正改指针），返回交换后链表的头节点。节点数范围 0～100，0 ≤ 节点值 ≤ 100。输入 head = [1,2,3,4] → 输出 [2,1,4,3]。输入 head = [1,2,3] → 输出 [2,1,3]。
思路：dummy 哑结点 + 三指针改指针。设前驱 pre、待交换的 a、b，操作顺序很关键：先把 pre.next 指向 b，再把 a.next 指向 b.next，最后把 b.next 指向 a；然后 pre 跳到 a（即下一对的前驱）。指针顺序错了就会断链。dummy 同样是为了处理头节点会变的问题。每轮处理一对，最后剩 0 或 1 个节点时自然结束。
时间复杂度 O(n)，空间复杂度 O(1)。
代码：
public class Solution {
public ListNode swapPairs(ListNode head) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode pre = dummy;
while (pre.next != null && pre.next.next != null) {
ListNode a = pre.next;
ListNode b = a.next;
a.next = b.next;
b.next = a;
pre.next = b;
pre = a;
}
return dummy.next;
}
}
25. K 个一组翻转链表（困难）
题目要求：给定链表头节点 head 和正整数 k，每 k 个节点为一组进行反转，不足 k 个的剩余节点保持原序，返回反转后的链表头。节点数范围 1～5000，0 ≤ 节点值 ≤ 1000，1 ≤ k ≤ 节点数。要求只能改指针、不能改节点值。输入 head = [1,2,3,4,5], k = 2 → 输出 [2,1,4,3,5]。输入 head = [1,2,3,4,5], k = 3 → 输出 [3,2,1,4,5]。
思路：把 24 题的"两两交换"推广到 K 个。核心是三个动作：① 数出 K 个节点，不够 K 个直接返回；② 把这一段原地反转（用 206 的三指针法）；③ 把反转后的段接回原链表（前驱段尾部接上反转后的新头，反转后的尾部接上下一段）。关键是每轮要记住"段前驱 pre"和"段尾 tail"，因为反转后段尾变成了原段头。指针操作多，建议用 prev/curr/next 三指针局部反转，再用 pre 和 tail 串起来。
时间复杂度 O(n)，空间复杂度 O(1)。
代码：
public class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode pre = dummy;
while (pre != null) {
ListNode tail = pre;
for (int i = 0; i < k; i++) {
tail = tail.next;
if (tail == null) return dummy.next;
}
ListNode next = tail.next;
ListNode a = pre.next, b = a.next;
for (int i = 1; i < k; i++) {
ListNode tmp = b.next;
b.next = a;
a = b;
b = tmp;
}
ListNode newTail = pre.next;
newTail.next = next;
pre.next = a;
pre = newTail;
}
return dummy.next;
}
}
138. 随机链表的复制（中等）
题目要求：定义一种节点：val 为整数，next 指向下一个节点，random 指向链表中任意节点或 null。给定这种链表的头节点 head，请返回它的深拷贝（克隆）——新链表中每个节点都必须是新创建的节点，next、random 关系要和原链表完全对应，不能直接引用原节点。节点数范围 0～1000，-10⁴ ≤ 节点值 ≤ 10⁴。输入 head = [[7,null],[13,0],[11,4],[10,2],[1,0]] → 输出一条内容完全相同的新链表（所有节点均为新对象）。输入 head = [[1,1],[2,1]] → 输出深拷贝新链表。
思路：哈希表存映射。难点在于 random 指针可能指向还没创建的节点。两遍法：第一遍遍历原链表，把每个节点 new 出一个副本，用 Map<原节点, 副本节点> 存起来；第二遍再遍历，从 map 里取出副本，把它的 next 和 random 都指向"原节点 next/random 对应的副本节点"。用 map 做中介，避免直接在新链上找 random。空间 O(n) 是必须的（要存 n 个映射）。
时间复杂度 O(n)，空间复杂度 O(n)。
代码：
import java.util.*;
public class Solution {
public Node copyRandomList(Node head) {
if (head == null) return null;
Map<Node, Node> 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);
}
}
148. 排序链表（中等）
题目要求：给定链表头节点 head，请将链表按升序排列并返回排序后的头节点。节点数范围 0～5×10⁴，节点值 -10⁵～10⁵。进阶要求 O(n log n) 时间、O(1) 空间（只改指针）。输入 head = [4,2,1,3] → 输出 [1,2,3,4]。输入 head = [-1,5,3,4,0] → 输出 [-1,0,3,4,5]。
思路：要求 O(n log n) 且 O(1) 空间，链表上首选归并排序。分三步：① 快慢指针找中点，把链表从中断开（注意要用 fast.next != null && fast.next.next != null，让 slow 停在中点前驱，方便断链）；② 递归排序左右两段；③ 用 21 题的双指针合并两个有序链表。归并排序在数组上要 O(n) 额外空间，但链表只改指针，O(1) 额外空间即可（递归栈不算）。
时间复杂度 O(n log n)，空间复杂度 O(log n)（递归栈）。
代码：
public class Solution {
public ListNode sortList(ListNode head) {
if (head == null || head.next == null) return head;
ListNode slow = head, fast = head;
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
ListNode mid = slow.next;
slow.next = null;
ListNode left = sortList(head);
ListNode right = sortList(mid);
return merge(left, right);
}
private ListNode merge(ListNode a, ListNode b) {
ListNode dummy = new ListNode(0);
ListNode tail = dummy;
while (a != null && b != null) {
if (a.val <= b.val) {
tail.next = a;
a = a.next;
} else {
tail.next = b;
b = b.next;
}
tail = tail.next;
}
tail.next = (a != null) ? a : b;
return dummy.next;
}
}
23. 合并 K 个升序链表（困难）
题目要求：给定一个链表数组 lists，其中每个链表都已按升序排列。请将所有链表合并成一个升序链表并返回其头节点。链表总数范围 0～10⁴，所有链表总节点数范围 0～10⁴，节点值 -10⁴～10⁴。输入 lists = [[1,4,5],[1,3,4],[2,6]] → 输出 [1,1,2,3,4,4,5,6]。输入 lists = [] → 输出 null。
思路：最小堆（优先队列）是最直观的做法。把 K 个链表的头节点全部放进小根堆，每次从堆里 poll 出最小节点接到结果尾部，再把这个节点的 next 放进堆里。堆大小始终不超过 K，每次 push/poll 是 O(log K)。用优先队列比两两合并（O(kn)）和分治合并都好写。注意比较器要按 val 升序，且要处理 null。
时间复杂度 O(N log K)，N 是总节点数，K 是链表数，空间复杂度 O(K)。
代码：
import java.util.*;
public class Solution {
public ListNode mergeKLists(ListNode[] lists) {
PriorityQueue<ListNode> pq = new PriorityQueue<>((a, b) -> a.val - b.val);
for (ListNode node : lists) {
if (node != null) pq.offer(node);
}
ListNode dummy = new ListNode(0);
ListNode tail = dummy;
while (!pq.isEmpty()) {
ListNode min = pq.poll();
tail.next = min;
tail = min;
if (min.next != null) pq.offer(min.next);
}
return dummy.next;
}
}
146. LRU 缓存（中等）
题目要求：实现 LRUCache 类：构造函数接收容量 capacity；get(key) 读取 key 对应的值，不存在返回 -1，且读取后该 key 变为最近使用；put(key, value) 写入或更新 key，当缓存超过 capacity 时淘汰最久未使用的 key。要求 get 和 put 都是 O(1) 时间。示例：LRUCache c = new LRUCache(2)；c.put(1,1); c.put(2,2); c.get(1) → 返回 1；c.put(3,3) → 淘汰 key=2；c.get(2) → 返回 -1；c.put(4,4) → 淘汰 key=1；c.get(1) → -1，c.get(3) → 3，c.get(4) → 4。
思路：LRU 要"O(1) 查 + O(1) 删最久未用 + O(1) 把新访问的移到最前"，数据结构是"哈希表 + 双向链表"。哈希表存 key→节点，让 get 直接定位；双向链表按访问顺序串，头部是最近使用，尾部是最久未用。Java 里直接用 LinkedHashMap 最省事——它本身就是哈希表+双向链表，重写 removeEldestEntry 就能在超容量时自动淘汰最老的 entry。面试时讲清楚 LinkedHashMap 底层就是这俩结构即可。
时间复杂度 O(1)，空间复杂度 O(capacity)。
代码：
import java.util.*;
public class LRUCache {
private final int capacity;
private final LinkedHashMap<Integer, Integer> map;
public LRUCache(int capacity) {
this.capacity = capacity;
this.map = new LinkedHashMap<>(capacity, 0.75f, true);
}
public int get(int key) {
return map.getOrDefault(key, -1);
}
public void put(int key, int value) {
map.put(key, value);
if (map.size() > capacity) {
Iterator<Integer> it = map.keySet().iterator();
it.next();
it.remove();
}
}
}
八、二叉树（15 题）
二叉树题先想递归：把"对整棵树做的事"想成"对根做一步 + 递归处理左右子树"，90% 的题就有骨架了。遇到"按层"就上 BFS 队列，遇到 BST 就抓住"中序遍历有序"这个性质。
94. 二叉树的中序遍历（简单）
题目要求：给定二叉树的根节点 root，返回它的中序遍历结果（按"左子树 → 根节点 → 右子树"顺序收集所有节点值）。节点数范围为 [0, 100]，节点值为 [-100, 100]。
示例：输入 root = [1,null,2,3] → 输出 [1,3,2]；输入 root = [] → 输出 []。
思路：中序就是"左 → 根 → 右"。最直观的写法是递归：先递归走左子树，再把当前结点值加进结果，最后递归走右子树。递归写法面试最常用，也最容易写对。如果要写迭代版，用一个栈一路向左压到底，弹出时访问结点，再转到它的右子树即可。这里给递归版。时间复杂度 O(n)，空间复杂度 O(h)（h 为树高，递归栈）。
代码：
import java.util.*;
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
dfs(root, res);
return res;
}
private void dfs(TreeNode node, List<Integer> res) {
if (node == null) return;
dfs(node.left, res);
res.add(node.val);
dfs(node.right, res);
}
}
104. 二叉树的最大深度（简单）
题目要求：给定二叉树的根节点 root，找出其最大深度。最大深度是指从根节点到最远叶子节点的最长路径上的节点数。节点数范围为 [0, 10^4]。
示例：输入 root = [3,9,20,null,null,15,7] → 输出 3（路径 3→20→15 共 3 层）；输入 root = [1,null,2] → 输出 2。
思路：求整棵树的最大深度，等于"左子树最大深度和右子树最大深度的较大值 + 1"。这是最经典的递归定义——base case 是空结点返回 0。递归出口清晰，一行递归体就能写完。时间复杂度 O(n)，每个结点访问一次；空间复杂度 O(h)，最坏链状 O(n)。
代码：
import java.util.*;
class Solution {
public int maxDepth(TreeNode root) {
if (root == null) return 0;
return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}
}
226. 翻转二叉树（简单）
题目要求：给定一棵二叉树的根节点 root，翻转这棵二叉树（每个节点的左右子树互换位置），并返回其根节点。节点数范围为 [0, 100]。
示例：输入 root = [4,2,7,1,3,6,9] → 输出 [4,7,2,9,6,3,1]；输入 root = [] → 输出 []。
思路：翻转就是交换每个结点的左右孩子，递归地对每个结点做同一件事。先递归翻转左子树、再递归翻转右子树，然后把当前结点的 left 和 right 互换位置。处理顺序不影响结果，只要每个结点都被走到一次。时间复杂度 O(n)，空间复杂度 O(h)。
代码：
import java.util.*;
class Solution {
public TreeNode invertTree(TreeNode root) {
if (root == null) return null;
TreeNode left = invertTree(root.left);
TreeNode right = invertTree(root.right);
root.left = right;
root.right = left;
return root;
}
}
101. 对称二叉树（简单）
题目要求：给定一棵二叉树的根节点 root，检查它是否是自身的镜像（即左右子树围绕中心对称）。节点数范围为 [1, 1000]。
示例：输入 root = [1,2,2,3,4,4,3] → 输出 true；输入 root = [1,2,2,null,3,null,3] → 输出 false。
思路：判断一棵树是否对称，等价于判断它的左子树和右子树是否"互为镜像"。写一个辅助函数 isMirror(a, b)：a 和 b 的值相等，且 a 的左子树与 b 的右子树镜像、a 的右子树与 b 的左子树镜像。两棵子树成对递归下去，空结点也要正确判等。时间复杂度 O(n)，空间复杂度 O(h)。
代码：
import java.util.*;
class Solution {
public boolean isSymmetric(TreeNode root) {
if (root == null) return true;
return isMirror(root.left, root.right);
}
private boolean isMirror(TreeNode a, TreeNode b) {
if (a == null && b == null) return true;
if (a == null || b == null) return false;
return a.val == b.val
&& isMirror(a.left, b.right)
&& isMirror(a.right, b.left);
}
}
543. 二叉树的直径（简单）
题目要求：给定一棵二叉树的根节点 root，返回任意两个节点之间最长路径的长度（路径上的边数）。这条路径可能不经过根节点。树中节点数范围为 [1, 10^4]。
示例：输入 root = [1,2,3,4,5] → 输出 3（路径 4→2→1→3 或 5→2→1→3，共 3 条边）；输入 root = [1,2] → 输出 1。
思路：直径是"任意两个结点之间最长路径的边数"。关键认知：任意一条路径，都有一个最高点（最近公共祖先），它等于"左子树向下的深度 + 右子树向下的深度"。所以我们在后序递归里，对每个结点都算一次 左深度 + 右深度，用一个全局变量记下最大值；而递归返回给上层的是"单边深度"（即 max(左, 右) + 1），因为上层只能选一边延伸。路径的贡献和单边贡献是两回事，这是这题的核心。时间复杂度 O(n)，空间复杂度 O(h)。
代码：
import java.util.*;
class Solution {
private int ans = 0;
public int diameterOfBinaryTree(TreeNode root) {
depth(root);
return ans;
}
private int depth(TreeNode node) {
if (node == null) return 0;
int left = depth(node.left);
int right = depth(node.right);
ans = Math.max(ans, left + right); // 经过当前结点的最长路径边数
return Math.max(left, right) + 1; // 返回单边深度给上层
}
}
102. 二叉树的层序遍历（中等）
题目要求：给定二叉树的根节点 root，按层序遍历（从上到下逐层、同层从左到右）返回节点值，结果是一个二维列表，每层对应一个子列表。节点数范围为 [0, 2000]。
示例：输入 root = [3,9,20,null,null,15,7] → 输出 [[3],[9,20],[15,7]]；输入 root = [] → 输出 []。
思路：按层遍历就是 BFS。用一个队列，每一层开始时先记下当前队列大小 size，这就是本层结点数，然后一次性把这 size 个结点全部出队、收集值、把它们的孩子入队。这样一层一层地切，就能自然地把每层的结果分开。时间复杂度 O(n)，空间复杂度 O(n)（队列最多装一层结点）。
代码：
import java.util.*;
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if (root == null) return res;
Queue<TreeNode> q = new LinkedList<>();
q.offer(root);
while (!q.isEmpty()) {
int size = q.size();
List<Integer> level = new ArrayList<>();
for (int i = 0; i < size; i++) {
TreeNode node = q.poll();
level.add(node.val);
if (node.left != null) q.offer(node.left);
if (node.right != null) q.offer(node.right);
}
res.add(level);
}
return res;
}
}
108. 将有序数组转换为二叉搜索树（简单）
题目要求：给一个已按升序排列的整数数组 nums，将其转换为一棵高度平衡的二叉搜索树（每个节点左右两个子树的高度差不超过 1）。数组长度范围为 [1, 10^4]，元素互不相同。
示例：输入 nums = [-10,-3,0,5,9] → 输出 [0,-3,9,-10,null,5]（或等价平衡 BST）；输入 nums = [1,3] → 输出 [3,1]。
思路：BST 的中序遍历是升序的，题目给的就是一个升序数组。要让它"高度平衡"，最自然的做法是取数组中点作为根，这样左右两边元素个数尽量相等，再递归地把左半段建成左子树、右半段建成右子树。分治的思路，每次选中点即可。时间复杂度 O(n)，空间复杂度 O(h)（递归栈，平衡树即 O(log n)）。
代码：
import java.util.*;
class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
return build(nums, 0, nums.length - 1);
}
private TreeNode build(int[] nums, int l, int r) {
if (l > r) return null;
int mid = l + (r - l) / 2;
TreeNode root = new TreeNode(nums[mid]);
root.left = build(nums, l, mid - 1);
root.right = build(nums, mid + 1, r);
return root;
}
}
98. 验证二叉搜索树（中等）
题目要求：给定一个二叉树的根节点 root，判断它是否是一棵有效的二叉搜索树（BST）。有效 BST 要求：左子树所有节点值小于根值、右子树所有节点值大于根值，且左右子树本身也都是 BST。节点数范围为 [1, 10^4]。
示例：输入 root = [2,1,3] → 输出 true；输入 root = [5,1,4,null,null,3,6] → 输出 false（根是 5，但右子树里出现了 3）。
思路：BST 的定义是"整棵树"满足左 < 根 < 右，而不是只看当前结点和它左右孩子的大小关系。两种写法：① 利用中序遍历递增——中序走一遍，检查当前值是否严格大于上一个值；② 递归传区间——每个结点都有一个合法范围 (lower, upper)，左子树把 upper 收紧成当前值，右子树把 lower 收紧成当前值。这里给"中序遍历递增"写法，最直观。时间复杂度 O(n)，空间复杂度 O(h)。
代码：
import java.util.*;
class Solution {
private long prev = Long.MIN_VALUE;
public boolean isValidBST(TreeNode root) {
prev = Long.MIN_VALUE;
return inorder(root);
}
private boolean inorder(TreeNode node) {
if (node == null) return true;
if (!inorder(node.left)) return false;
if (node.val <= prev) return false;
prev = node.val;
return inorder(node.right);
}
}
230. 二叉搜索树中第 K 小的元素（中等）
题目要求：给定二叉搜索树的根节点 root 和一个整数 k，返回树中第 k 小的元素（从 1 开始计数）。可假设 k 总是合法的（1 ≤ k ≤ 树中节点数）。树中节点数至少为 1。
示例：输入 root = [3,1,4,null,2], k = 1 → 输出 1；输入 root = [5,3,6,2,4,null,null,1], k = 3 → 输出 3。
思路：BST 的中序遍历是升序的，所以"第 K 小"就是中序遍历走到第 K 个结点。做一个递归中序，用一个计数器从 1 开始数，数到 K 时把当前结点的值存下来即可。可以一旦找到就提前返回。时间复杂度 O(h + k)（最坏 O(n)），空间复杂度 O(h)。
代码：
import java.util.*;
class Solution {
private int count = 0;
private int result = 0;
public int kthSmallest(TreeNode root, int k) {
count = 0;
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);
}
}
199. 二叉树的右视图（中等）
题目要求：给定二叉树的根节点 root，想象自己站在树的右侧，返回从右侧从上到下能看到的节点值（即每一层最右边的那个节点）。节点数范围为 [0, 100]。
示例：输入 root = [1,2,3,null,5,null,4] → 输出 [1,3,4]；输入 root = [1,null,3] → 输出 [1,3]。
思路：右视图就是"从右边看，每一层能看到的最右边那个结点"。层序遍历时，每一层的最后一个结点就是这一层的右视图元素，所以做法和 102 一样：BFS 按层切，每层出队完后，把该层最后一个结点的值加进结果即可。时间复杂度 O(n)，空间复杂度 O(n)。
代码：
import java.util.*;
class Solution {
public List<Integer> rightSideView(TreeNode root) {
List<Integer> res = new ArrayList<>();
if (root == null) return res;
Queue<TreeNode> q = new LinkedList<>();
q.offer(root);
while (!q.isEmpty()) {
int size = q.size();
for (int i = 0; i < size; i++) {
TreeNode node = q.poll();
if (i == size - 1) res.add(node.val); // 每层最后一个
if (node.left != null) q.offer(node.left);
if (node.right != null) q.offer(node.right);
}
}
return res;
}
}
114. 二叉树展开为链表（中等）
题目要求：给定二叉树的根节点 root，将其原地展开为一个按前序遍历顺序排列的"右孩子链表"（每个节点的左指针为 null，右指针指向下一个节点）。不能使用辅助节点数组。节点数范围为 [0, 2000]。
示例：输入 root = [1,2,5,3,4,null,6] → 输出展开后形如 [1,null,2,null,3,null,4,null,5,null,6]；输入 root = [] → 输出 []。
思路：要求原地把二叉树按前序顺序拉成一条右孩子链。一个巧妙的做法是"后序遍历 + 就地接"：递归把左子树展开成链表、右子树展开成链表，然后把"展开后的左链表"接到根的右孩子位置，把"展开后的右链表"接到左链表末尾。这样自底向上，每一步都维护好链表结构，最后根的 left 置空即可。时间复杂度 O(n)，空间复杂度 O(h)。
代码：
import java.util.*;
class Solution {
public void flatten(TreeNode root) {
if (root == null) return;
flatten(root.left);
flatten(root.right);
// 暂存右子树
TreeNode right = root.right;
// 把左子树接到右边
root.right = root.left;
root.left = null;
// 走到当前新右链的末尾，接上原来的右子树
TreeNode cur = root;
while (cur.right != null) cur = cur.right;
cur.right = right;
}
}
105. 从前序与中序遍历序列构造二叉树（中等）
题目要求：给定一棵二叉树的前序遍历结果 preorder 和中序遍历结果 inorder，据此构造并返回这棵二叉树。假设树中没有重复元素。两个数组长度相同，范围为 [1, 3000]。
示例：输入 preorder = [3,9,20,15,7], inorder = [9,3,15,20,7] → 输出 [3,9,20,null,null,15,7]；输入 preorder = [-1], inorder = [-1] → 输出 [-1]。
思路：经典分治。前序的第一个元素一定是根；在中序里找到这个根，它左边的元素构成左子树的中序、右边构成右子树的中序；再根据左右子树的长度，把前序数组也切成对应两段，递归建左右子树即可。用一个哈希表把"值 → 中序下标"存起来，查找根的位置就是 O(1)。时间复杂度 O(n)，空间复杂度 O(n)（哈希表 + 递归栈）。
代码：
import java.util.*;
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
Map<Integer, Integer> inMap = new HashMap<>();
for (int i = 0; i < inorder.length; i++) {
inMap.put(inorder[i], i);
}
return build(preorder, 0, 0, inorder.length - 1, inMap);
}
private TreeNode build(int[] preorder, int preStart, int inL, int inR,
Map<Integer, Integer> inMap) {
if (inL > inR) return null;
int rootVal = preorder[preStart];
TreeNode root = new TreeNode(rootVal);
int inIdx = inMap.get(rootVal);
int leftSize = inIdx - inL;
root.left = build(preorder, preStart + 1, inL, inIdx - 1, inMap);
root.right = build(preorder, preStart + 1 + leftSize, inIdx + 1, inR, inMap);
return root;
}
}
437. 路径总和 III（中等）
题目要求：给定二叉树根节点 root 和一个整数 targetSum，求路径上节点值之和等于 targetSum 的路径总数。路径方向必须向下（从父节点到子节点），但不需要从根开始、也不需要到叶子结束，只要是一条向下的连续路径即可。节点数范围为 [0, 1000]，节点值范围为 [-10^9, 10^9]。
示例：输入 root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8 → 输出 3；输入 root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22 → 输出 3。
思路：路径不一定要从根开始，也不一定要到叶子结束，所以要枚举所有可能的起点。做法是两层递归：① pathSum(root, targetSum) 对每个结点都当作一次"路径起点"，算从该结点出发向下累加能凑出 targetSum 的路径数；② 再对左右子树递归地做同样的事，把"以每个结点为起点"的方案数累加起来。这样覆盖所有起点。时间复杂度 O(n²)（退化链时），空间复杂度 O(h)。
代码：
import java.util.*;
class Solution {
public int pathSum(TreeNode root, int targetSum) {
if (root == null) return 0;
return countFrom(root, targetSum)
+ pathSum(root.left, targetSum)
+ pathSum(root.right, targetSum);
}
private int countFrom(TreeNode node, long sum) {
if (node == null) return 0;
int cnt = 0;
if (node.val == sum) cnt++;
cnt += countFrom(node.left, sum - node.val);
cnt += countFrom(node.right, sum - node.val);
return cnt;
}
}
236. 二叉树的最近公共祖先（中等）
题目要求：给定一棵二叉树的根节点 root，以及树中的两个节点 p 和 q，找到它们的最近公共祖先（LCA）。最近公共祖先是指"同时以 p 和 q 作为后代的最低层节点"（允许节点本身是自己的后代）。树中节点数范围为 [2, 10^5]，p、q 一定在树中且不相等。
示例：输入 root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 → 输出 3；输入 root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4 → 输出 5（因为 LCA 允许是节点自身）。
思路：在一棵树上找 p、q 的最近公共祖先，用递归分治。定义 lowestCommonAncestor(root, p, q) 返回"以 root 为根的子树里，p、q 的最近公共祖先（如果找到）"。逻辑：① 如果 root 是 null、或者 root 就是 p、或者 root 就是 q，直接返回 root；② 分别去左子树和右子树里找；③ 如果左边没找到，说明 p、q 都在右边，返回右边的结果；右边同理；④ 如果左右都找到了，说明 p、q 分别在 root 两侧，root 就是答案。时间复杂度 O(n)，空间复杂度 O(h)。
代码：
import java.util.*;
class Solution {
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);
if (left == null) return right;
if (right == null) return left;
return root;
}
}
124. 二叉树中的最大路径和（困难）
题目要求：给定一棵二叉树的根节点 root，返回其最大路径和。路径被定义为任意一条从树中某节点出发、沿着父节点—子节点连接到达任意节点的序列，路径上至少有一个节点，且不一定经过根。节点值范围为 [-1000, 1000]，节点数范围为 [1, 3 * 10^4]。
示例：输入 root = [1,2,3] → 输出 6（路径 2→1→3 求和为 6）；输入 root = [-10,9,20,null,null,15,7] → 输出 42（路径 15→20→7 求和为 42）。
思路：和 543 直径是同一个套路。任意一条路径都有一个最高点（最近公共祖先），它的"经过该结点的路径和" = 左子树单边贡献 + 当前结点值 + 右子树单边贡献，其中单边贡献如果是负数就不如不选（取 0）。我们在递归里用一个全局变量记录这个最大值；而递归返回给上层的是"单边贡献" = 当前结点值 + max(左单边, 右单边, 0)，因为上层只能从一边延伸，不能两边都走。路径和与单边贡献严格区分，这是这题的核心，也是最容易错的地方。时间复杂度 O(n)，空间复杂度 O(h)。
代码：
import java.util.*;
class Solution {
private int maxSum = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
maxSum = Integer.MIN_VALUE;
gain(root);
return maxSum;
}
private int gain(TreeNode node) {
if (node == null) return 0;
// 单边贡献，负数则取 0
int left = Math.max(0, gain(node.left));
int right = Math.max(0, gain(node.right));
// 经过当前结点作为最高点的路径和
int cur = node.val + left + right;
maxSum = Math.max(maxSum, cur);
// 返回给上层：只能选一边延伸
return node.val + Math.max(left, right);
}
}
九、图论（4 题）
200. 岛屿数量（中等）
题目要求：给你一个由 '1'（陆地）和 '0'（水）组成的二维网格，求其中岛屿的数量。岛屿被水包围，且只能通过水平或垂直方向相邻的陆地连接；对角线相连不算。网格尺寸 m、n 范围 1～300。
示例：输入 grid = [[‘1’,‘1’,‘1’,‘1’,‘0’],[‘1’,‘1’,‘0’,‘1’,‘0’],[‘1’,‘1’,‘0’,‘0’,‘0’],[‘0’,‘0’,‘0’,‘0’,‘0’]] → 输出 1。
示例：输入 grid = [[‘1’,‘1’,‘0’,‘0’,‘0’],[‘1’,‘1’,‘0’,‘0’,‘0’],[‘0’,‘0’,‘1’,‘0’,‘0’],[‘0’,‘0’,‘0’,‘1’,‘1’]] → 输出 3。
思路：把网格看成一张图，每个 '1' 是一个结点，上下左右相邻的 '1' 互相连通。经典套路是「DFS / BFS 染色」——遍历每个格子，只要碰到一块未访问的陆地，答案就 +1，然后从这块陆地出发，用 DFS（或 BFS）把与之连通的所有陆地全部"淹掉"（直接改成 '0' 或打访问标记），这样后续遍历不会重复计数。核心一步：双循环扫网格，遇到 '1' 就启动一次 DFS 并把当前岛屿计数 +1。DFS 内递归访问四个方向，越界或不是陆地就返回。
时间复杂度 O(m×n)，空间复杂度 O(m×n)（最坏全是陆地，DFS 递归栈深度为 m×n）。
代码：
class Solution {
public int numIslands(char[][] grid) {
if (grid == null || grid.length == 0) return 0;
int m = grid.length, n = grid[0].length, ans = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == '1') {
ans++;
dfs(grid, i, j);
}
}
}
return ans;
}
private void dfs(char[][] g, int i, int j) {
int m = g.length, n = g[0].length;
if (i < 0 || i >= m || j < 0 || j >= n || g[i][j] != '1') return;
g[i][j] = '0';
dfs(g, i + 1, j);
dfs(g, i - 1, j);
dfs(g, i, j + 1);
dfs(g, i, j - 1);
}
}
994. 腐烂的橘子（中等）
题目要求：m×n 网格中每个格子是 0（空）、1（新鲜橘子）或 2（腐烂橘子）。每分钟，腐烂橘子上下左右相邻的新鲜橘子会被感染腐烂。求直到再也没有新鲜橘子为止所经过的分钟数；如果永远有新鲜橘子无法被感染，返回 -1。网格尺寸 1～10。 示例：输入 grid = [[2,1,1],[1,1,0],[0,1,1]] → 输出 4。 示例：输入 grid = [[2,1,1],[0,1,1],[1,0,1]] → 输出 -1。
思路：腐烂是"按层扩散"的过程，天然对应 BFS（多源 BFS）。先把所有初始腐烂橘子入队，统计新鲜橘子总数；然后一层层向外扩展，每扩散一轮分钟数 +1，把被污染的新鲜橘子数减一。BFS 结束后，如果还有新鲜橘子剩着，说明有橘子永远碰不到，返回 -1；否则返回扩散的轮数。核心一步：多源同时入队，按层（按 queue size）遍历，时间就是层数。注意边界：一开始就没有新鲜橘子时答案为 0。
时间复杂度 O(m×n)，空间复杂度 O(m×n)。
代码：
import java.util.*;
class Solution {
public int orangesRotting(int[][] grid) {
int m = grid.length, n = grid[0].length;
Queue<int[]> q = new LinkedList<>();
int fresh = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 2) q.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 (!q.isEmpty() && fresh > 0) {
int size = q.size();
for (int k = 0; k < size; k++) {
int[] p = q.poll();
for (int[] d : dirs) {
int x = p[0] + d[0], y = p[1] + d[1];
if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1) {
grid[x][y] = 2;
fresh--;
q.offer(new int[]{x, y});
}
}
}
minutes++;
}
return fresh == 0 ? minutes : -1;
}
}
207. 课程表（中等）
题目要求：总共有 numCourses 门课，记为 0 到 numCourses-1。prerequisites 是先修关系数组，其中每个元素 [a, b] 表示必须先修 b 才能修 a。判断是否可能完成所有课程，即是否存在合法的选课顺序；存在返回 true，否则返回 false。课程数范围 1～2000，先修关系数范围 0～5000。
示例：输入 numCourses = 2, prerequisites = [[1,0]] → 输出 true。
示例：输入 numCourses = 2, prerequisites = [[1,0],[0,1]] → 输出 false。
思路：先修关系 [a, b] 表示学 a 之前必须学 b，等价于有向边 b → a。问题本质是「判断有向图是否有环」——能完成所有课，当且仅当这张图是 DAG（有向无环图）。常用拓扑排序（Kahn 算法）：统计每个结点入度，把入度为 0 的结点入队，不断从队列取出并把它指向的结点入度减一，若减到 0 就入队。最后看「已处理的结点数」是否等于课程总数，等于则无环，否则存在环。核心一步：用邻接表建图 + 入度数组，BFS 一层层剥掉入度为 0 的点。
时间复杂度 O(V+E)，空间复杂度 O(V+E)。
代码：
import java.util.*;
class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < numCourses; i++) adj.add(new ArrayList<>());
int[] indeg = new int[numCourses];
for (int[] pre : prerequisites) {
adj.get(pre[1]).add(pre[0]);
indeg[pre[0]]++;
}
Queue<Integer> q = new LinkedList<>();
for (int i = 0; i < numCourses; i++) {
if (indeg[i] == 0) q.offer(i);
}
int done = 0;
while (!q.isEmpty()) {
int c = q.poll();
done++;
for (int nxt : adj.get(c)) {
indeg[nxt]--;
if (indeg[nxt] == 0) q.offer(nxt);
}
}
return done == numCourses;
}
}
208. 实现 Trie（前缀树）（中等）
题目要求：实现一个 Trie（前缀树）类，支持三个操作：Trie() 初始化对象；insert(String word) 把单词 word 插入树中；search(String word) 判断 word 是否在已插入的单词集合中（完全匹配）；startsWith(String prefix) 判断是否存在任何已插入的单词以 prefix 作为前缀。word 和 prefix 仅由小写英文字母组成，长度 1～2000。
示例：调用顺序 Trie trie = new Trie(); trie.insert("apple"); trie.search("apple"); // true；trie.search("app"); // false；trie.startsWith("app"); // true；trie.insert("app"); trie.search("app"); // true。
思路：Trie（前缀树）是一棵多叉树，每个结点代表一个字符，从根到某结点的路径拼起来就是一个前缀。结构上每个结点持有一个长度 26 的子结点数组（Trie[26]）和一个 isEnd 布尔标记，表示「从根到这里是否是一个完整单词」。插入：逐字符沿树往下走，不存在就新建结点；最后把末尾结点的 isEnd 置 true。查询同理：能走到末尾且 isEnd 为 true 才算命中；startsWith 只要求能走到末尾，不管 isEnd。核心一步：用数组 Trie[26] 替代 Map，查询/插入都是 O(L)，L 为单词长度。
时间复杂度：insert/search/startsWith 均为 O(L)，L 为字符串长度；空间复杂度 O(字符总数×26)。
代码：
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 (int i = 0; i < word.length(); i++) {
int idx = word.charAt(i) - 'a';
if (node.children[idx] == null) node.children[idx] = new Trie();
node = node.children[idx];
}
node.isEnd = true;
}
public boolean search(String word) {
Trie node = find(word);
return node != null && node.isEnd;
}
public boolean startsWith(String prefix) {
return find(prefix) != null;
}
private Trie find(String s) {
Trie node = this;
for (int i = 0; i < s.length(); i++) {
int idx = s.charAt(i) - 'a';
if (node.children[idx] == null) return null;
node = node.children[idx];
}
return node;
}
}
十、回溯（8 题）
46. 全排列（中等）
题目要求：给定一个不含重复数字的数组 nums，返回其所有可能的全排列，可以按任意顺序输出。nums 长度范围 1～6，数组元素范围 -10～10，且互不相同。 示例：输入 nums = [1,2,3] → 输出 [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]。 示例：输入 nums = [0,1] → 输出 [[0,1],[1,0]]。
思路：回溯模板题。求 1~n 的全排列，就是对每个位置尝试所有尚未使用的数字。标准三步：① 选择（把当前数加入路径，并标记已用）；② 递归（进入下一层）；③ 撤销（从路径弹出、取消标记）。当路径长度等于 n 时，得到一个完整排列，拷贝加入结果集。核心一步：用一个 used 布尔数组记录哪些数已经在路径里，避免同一层重复选同一个数；结果集里要 new ArrayList<>(path) 拷贝，不能直接加引用。
时间复杂度 O(n×n!)，空间复杂度 O(n)（递归栈 + used 数组）。
代码：
import java.util.*;
class Solution {
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> ans = new ArrayList<>();
boolean[] used = new boolean[nums.length];
backtrack(nums, used, new ArrayList<>(), ans);
return ans;
}
private void backtrack(int[] nums, boolean[] used, List<Integer> path, List<List<Integer>> ans) {
if (path.size() == nums.length) {
ans.add(new ArrayList<>(path));
return;
}
for (int i = 0; i < nums.length; i++) {
if (used[i]) continue;
used[i] = true;
path.add(nums[i]);
backtrack(nums, used, path, ans);
path.remove(path.size() - 1);
used[i] = false;
}
}
}
78. 子集（中等）
题目要求：给你一个整数数组 nums，数组中的元素互不相同，返回该数组所有可能的子集（幂集）。解集不能包含重复的子集，可以按任意顺序输出。nums 长度范围 1～10。 示例：输入 nums = [1,2,3] → 输出 [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]。 示例：输入 nums = [0] → 输出 [[],[0]]。
思路：回溯模板题。子集就是对每个元素做"选 / 不选"两种决策，所有决策路径拼起来就是 2^n 个子集。写法上：按数组顺序逐个考虑元素，在每一层递归入口都先把当前路径加入结果集（因为每一条从根出发的路径本身就是一个子集，不是只有叶子才收）；然后从当前 start 位置开始，选择 nums[i] 进入下一层，再撤销。核心一步：用 start 控制遍历起点，保证同一组合里元素只递增出现，避免 {1,2} 和 {2,1} 被当成两个不同子集。
时间复杂度 O(n×2^n)，空间复杂度 O(n)。
代码：
import java.util.*;
class Solution {
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> ans = new ArrayList<>();
backtrack(nums, 0, new ArrayList<>(), ans);
return ans;
}
private void backtrack(int[] nums, int start, List<Integer> path, List<List<Integer>> ans) {
ans.add(new ArrayList<>(path));
for (int i = start; i < nums.length; i++) {
path.add(nums[i]);
backtrack(nums, i + 1, path, ans);
path.remove(path.size() - 1);
}
}
}
17. 电话号码的字母组合（中等）
题目要求：给定一个仅包含数字 2～9 的字符串，返回它能表示的所有字母组合（按任意顺序）。数字到字母的映射如下：2→abc、3→def、4→ghi、5→jkl、6→mno、7→pqrs、8→tuv、9→wxyz。输入字符串长度 0～4，若为空则返回空列表。 示例：输入 digits = “23” → 输出 [“ad”,“ae”,“af”,“bd”,“be”,“bf”,“cd”,“ce”,“cf”]。 示例：输入 digits = "" → 输出 []。
思路：每个数字对应一组字母，求所有组合，本质是「多步决策的笛卡尔积」，用回溯逐位选择即可。先建一张数字 → 字母串的映射表（可用数组下标 2~9）。递归时按当前处理到第几位 pos 走：若 pos == digits.length，得到一个组合，加入结果；否则枚举该数字对应字母串里的每个字符，append、递归到 pos+1、再 delete。核心一步：用 StringBuilder 拼接，回溯时 deleteCharAt(len-1) 撤销，比 add/remove 整数更高效。空串输入要返回空列表。
时间复杂度 O(3^m × 4^n)，m 是对应 3 个字母的数字个数，n 是对应 4 个字母（7、9）的数字个数；空间复杂度 O(m+n)。
代码：
import java.util.*;
class Solution {
private static final String[] MAP = {
"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"
};
public List<String> letterCombinations(String digits) {
List<String> ans = new ArrayList<>();
if (digits == null || digits.length() == 0) return ans;
backtrack(digits, 0, new StringBuilder(), ans);
return ans;
}
private void backtrack(String digits, int pos, StringBuilder sb, List<String> ans) {
if (pos == digits.length()) {
ans.add(sb.toString());
return;
}
String letters = MAP[digits.charAt(pos) - '0'];
for (int i = 0; i < letters.length(); i++) {
sb.append(letters.charAt(i));
backtrack(digits, pos + 1, sb, ans);
sb.deleteCharAt(sb.length() - 1);
}
}
}
39. 组合总和（中等）
题目要求：给你一个无重复元素的整数数组 candidates 和一个目标整数 target，找出 candidates 中可以使数字和为 target 的所有不同组合，candidates 中的数字可以无限制重复被选取。两个组合若相同（元素多重集合相同）视为同一个。数组长度 1～30，元素 2～40，target 1～40。 示例：输入 candidates = [2,3,6,7], target = 7 → 输出 [[2,2,3],[7]]。 示例：输入 candidates = [2,3,5], target = 8 → 输出 [[2,2,2,2],[2,3,3],[3,5]]。
思路：回溯 + 剪枝。数组里的数可以重复使用，求加起来等于 target 的所有组合。决策树：按顺序考虑 candidates 里的数，每个数可以"选若干次"。递归函数里传入 start（从哪个下标开始尝试）和 remain（剩余目标值）。对每个 candidates[i]：① 如果 candidates[i] > remain 直接跳过（剪枝——因为已排序，后面更大，也都不用看）；② 加入路径、递归时 start 仍传 i（允许重复选当前数）、remain 减 candidates[i]；③ 撤销。核心一步：先把数组排序，然后在 candidates[i] > remain 处 break，这是关键剪枝点；题目保证元素唯一，不需要去重。
时间复杂度：上界 O(目标值 / 最小元素 × 组合数)，空间复杂度 O(target)。
代码：
import java.util.*;
class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> ans = new ArrayList<>();
Arrays.sort(candidates);
backtrack(candidates, 0, target, new ArrayList<>(), ans);
return ans;
}
private void backtrack(int[] arr, int start, int remain, List<Integer> path, List<List<Integer>> ans) {
if (remain == 0) {
ans.add(new ArrayList<>(path));
return;
}
for (int i = start; i < arr.length; i++) {
if (arr[i] > remain) break;
path.add(arr[i]);
backtrack(arr, i, remain - arr[i], path, ans);
path.remove(path.size() - 1);
}
}
}
22. 括号生成（中等）
题目要求：数字 n 表示生成括号的对数，设计一个函数，能够生成所有可能的、并且有效的（左右括号正确匹配的）括号组合。n 范围 1～8。 示例：输入 n = 3 → 输出 ["((()))","(()())","(())()","()(())","()()()"]。 示例：输入 n = 1 → 输出 ["()"]。
思路：经典回溯题。合法括号序列的关键约束是「任意前缀中左括号数 ≥ 右括号数」，且最终左右括号数都等于 n。回溯时维护两个计数器 open（已用左括号数）和 close（已用右括号数）：① 只要 open < n，就可以放一个 (；② 只要 close < open，就可以放一个 )。当 open == n && close == n 时得到一个合法序列，拷贝加入结果。核心一步：用 close < open 这个条件剪去所有非法分支——这是把"合法性"翻译成"可放右括号"的判断。
时间复杂度 O(4^n / √n)（卡特兰数级别），空间复杂度 O(n)。
代码：
import java.util.*;
class Solution {
public List<String> generateParenthesis(int n) {
List<String> ans = new ArrayList<>();
backtrack(n, 0, 0, new StringBuilder(), ans);
return ans;
}
private void backtrack(int n, int open, int close, StringBuilder sb, List<String> ans) {
if (open == n && close == n) {
ans.add(sb.toString());
return;
}
if (open < n) {
sb.append('(');
backtrack(n, open + 1, close, sb, ans);
sb.deleteCharAt(sb.length() - 1);
}
if (close < open) {
sb.append(')');
backtrack(n, open, close + 1, sb, ans);
sb.deleteCharAt(sb.length() - 1);
}
}
}
79. 单词搜索（中等）
题目要求：给定一个 m×n 二维字符网格 board 和一个字符串单词 word，若 word 存在于网格中则返回 true，否则返回 false。单词必须由相邻格子（水平或垂直相邻）的字母按顺序构成，同一格子不能被重复使用。网格尺寸 m、n 范围 1～6，word 长度范围 1～15。 示例：输入 board = [[‘A’,‘B’,‘C’,‘E’],[‘S’,‘F’,‘C’,‘S’],[‘A’,‘D’,‘E’,‘E’]], word = “ABCCED” → 输出 true。 示例：输入 board = [[‘A’,‘B’,‘C’,‘E’],[‘S’,‘F’,‘C’,‘S’],[‘A’,‘D’,‘E’,‘E’]], word = “SEE” → 输出 true；word = “ABCB” → 输出 false。
思路：在网格里找一条路径拼出目标单词，本质是「带访问标记的 DFS 回溯」。从每个格子出发，只要它等于 word[0]，就启动 DFS：先把当前格子标记为已访问（避免重复走，直接把 board 改成 '#'），再向四个方向递归匹配 word[pos+1]，递归回来撤销标记（恢复原字符）。核心一步：递归出口——pos == word.length()-1 时已匹配完，直接返回 true；越界、字符不匹配、已访问都立刻返回 false。注意因为要撤销，修改前要先把原字符存下来。
时间复杂度 O(m×n×3^L)，L 为单词长度（每步最多三个方向可走），空间复杂度 O(L)。
代码：
class Solution {
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, i, j, word, 0)) return true;
}
}
return false;
}
private boolean dfs(char[][] b, int i, int j, String word, int pos) {
if (pos == word.length()) return true;
int m = b.length, n = b[0].length;
if (i < 0 || i >= m || j < 0 || j >= n) return false;
if (b[i][j] != word.charAt(pos)) return false;
char tmp = b[i][j];
b[i][j] = '#';
boolean ok = dfs(b, i + 1, j, word, pos + 1)
|| dfs(b, i - 1, j, word, pos + 1)
|| dfs(b, i, j + 1, word, pos + 1)
|| dfs(b, i, j - 1, word, pos + 1);
b[i][j] = tmp;
return ok;
}
}
131. 分割回文串（中等）
题目要求：给你一个字符串 s，要求把 s 分割成若干子串，使得每个子串都是回文串。返回所有可能的分割方案。子串是原字符串的连续切片。s 长度范围 1～16，仅由小写英文字母组成。 示例：输入 s = “aab” → 输出 [[“a”,“a”,“b”],[“aa”,“b”]]。 示例：输入 s = “a” → 输出 [[“a”]]。
思路：回溯枚举所有切分方式，每切一刀都判断当前段是不是回文。决策树：在位置 start 开始，枚举 end 从 start 到 n-1，如果 s[start..end] 是回文，就把它加入路径，递归从 end+1 继续切；撤销。当 start == n 时，得到一个完整切分，加入结果。核心一步：「回文判断」可以用双指针逐个字符比对（O(L)），本题数据量小直接写就行；也可以提前 DP 预处理 isPalindrome[i][j] 数组，把每次判断降到 O(1)。
时间复杂度 O(n × 2^n)，空间复杂度 O(n)（递归栈 + 路径）。
代码：
import java.util.*;
class Solution {
public List<List<String>> partition(String s) {
List<List<String>> ans = new ArrayList<>();
backtrack(s, 0, new ArrayList<>(), ans);
return ans;
}
private void backtrack(String s, int start, List<String> path, List<List<String>> ans) {
if (start == s.length()) {
ans.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, ans);
path.remove(path.size() - 1);
}
}
}
private boolean isPalindrome(String s, int l, int r) {
while (l < r) {
if (s.charAt(l++) != s.charAt(r--)) return false;
}
return true;
}
}
51. N 皇后（困难）
题目要求：n 皇后问题，在 n×n 的棋盘上放置 n 个皇后，使得任意两个皇后不能互相攻击（即不能在同一行、同一列、同一条斜线上）。返回所有不同的解决方案，每个方案用一个 n×n 字符矩阵表示，'Q' 表示皇后，'.' 表示空位。n 范围 1～9。
示例：输入 n = 4 → 输出 [[".Q..","…Q",“Q…”,"..Q."],["..Q.",“Q…”,"…Q",".Q.."]]（共 2 种方案）。
示例：输入 n = 1 → 输出 [[“Q”]]。
思路：经典回溯题。N 皇后要求：每行放一个皇后，且任意两个皇后不能在同一列、同一主对角线（行-列 相等）、同一副对角线（行+列 相等）。按行递归——第 row 行尝试每一列 col，检查 (row, col) 是否和已放置的皇后冲突：① col 列是否已占用；② 主对角线 row-col（可用偏移 n 映射到 0~2n-2）是否占用；③ 副对角线 row+col 是否占用。三个集合都为空才落子，然后标记占用、递归下一行、撤销标记。核心一步：用三个 boolean 数组或 Set 分别记录列、主对角线、副对角线的占用情况，检查冲突 O(1)。当 row == n 时，把棋盘构造出来加入结果。
时间复杂度 O(n!)，空间复杂度 O(n)。
代码：
import java.util.*;
class Solution {
public List<List<String>> solveNQueens(int n) {
List<List<String>> ans = new ArrayList<>();
char[][] board = new char[n][n];
for (int i = 0; i < n; i++) Arrays.fill(board[i], '.');
boolean[] colUsed = new boolean[n];
boolean[] diag1 = new boolean[2 * n - 1]; // row - col + n - 1
boolean[] diag2 = new boolean[2 * n - 1]; // row + col
backtrack(n, 0, board, colUsed, diag1, diag2, ans);
return ans;
}
private void backtrack(int n, int row, char[][] board, boolean[] colUsed,
boolean[] diag1, boolean[] diag2, List<List<String>> ans) {
if (row == n) {
List<String> list = new ArrayList<>();
for (char[] r : board) list.add(new String(r));
ans.add(list);
return;
}
for (int col = 0; col < n; col++) {
int d1 = row - col + n - 1;
int d2 = row + col;
if (colUsed[col] || diag1[d1] || diag2[d2]) continue;
board[row][col] = 'Q';
colUsed[col] = true;
diag1[d1] = true;
diag2[d2] = true;
backtrack(n, row + 1, board, colUsed, diag1, diag2, ans);
board[row][col] = '.';
colUsed[col] = false;
diag1[d1] = false;
diag2[d2] = false;
}
}
}
十一、二分查找（6 题）
35. 搜索插入位置（简单）
题目要求：给定一个严格递增的整数数组 nums 和一个目标值 target，若 target 存在则返回它的下标；若不存在，返回它按顺序插入后应在的位置。数组非空，元素为整数。 输入 nums = [1,3,5,6]，target = 5 → 输出 2 输入 nums = [1,3,5,6]，target = 2 → 输出 1
思路：数组有序且要找"目标应该插在哪"，本质就是二分模板里"找第一个 >= target 的位置"。用左闭右闭写法 [l, r]，当 nums[mid] < target 时去右半找，否则去左半；循环结束时 l 就是答案——因为所有 < target 的都被推到了 l 左边，找不到时 l 正好落在第一个该插入的位置。经典二分模板题。
时间复杂度 O(log n)，空间复杂度 O(1)。
代码：
class Solution {
public int searchInsert(int[] nums, int target) {
int l = 0, r = nums.length - 1;
while (l <= r) {
int mid = l + (r - l) / 2;
if (nums[mid] < target) {
l = mid + 1;
} else {
r = mid - 1;
}
}
return l;
}
}
74. 搜索二维矩阵（中等）
题目要求：给定一个 m×n 矩阵，其每一行从左到右递增、且每行第一个数都大于上一行最后一个数（整体有序），判断 target 是否存在于矩阵中，存在返回 true，否则 false。 输入 matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]]，target = 3 → 输出 true 输入 matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]]，target = 13 → 输出 false
思路：矩阵的每一行从上到下、从左到右整体严格递增，可以把它"拍平"成一个长度为 m*n 的一维有序数组来二分。关键只是坐标换算：一维下标 mid 对应到矩阵就是 行 = mid / n，列 = mid % n。之后完全是 35 题那套二分模板。
时间复杂度 O(log(mn))，空间复杂度 O(1)。
代码：
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
int m = matrix.length, n = matrix[0].length;
int l = 0, r = m * n - 1;
while (l <= r) {
int mid = l + (r - l) / 2;
int val = matrix[mid / n][mid % n];
if (val == target) return true;
if (val < target) l = mid + 1;
else r = mid - 1;
}
return false;
}
}
34. 在排序数组中查找元素的第一个和最后一个位置（中等）
题目要求：给定一个可能有重复元素的升序数组 nums，找出 target 第一次和最后一次出现的下标，返回长度为 2 的数组；若 target 不存在则返回 [-1,-1]。要求 O(log n) 复杂度。 输入 nums = [5,7,7,8,8,10]，target = 8 → 输出 [3,4] 输入 nums = [5,7,7,8,8,10]，target = 6 → 输出 [-1,-1]
思路：有序数组找"出现区间"，就是两次二分：第一次找第一个 >= target 的位置（左边界），第二次找第一个 > target 的位置再减一（右边界）。两次都用同一套"找满足条件最左位置"的模板，区别只在比较时等号归哪边。先找到左端点后判断是否越界、值是否真的等于 target，否则说明 target 不存在，直接返回 [-1,-1]。
时间复杂度 O(log n)，空间复杂度 O(1)。
代码：
class Solution {
public int[] searchRange(int[] nums, int target) {
int left = lowerBound(nums, target);
if (left == nums.length || nums[left] != target) {
return new int[]{-1, -1};
}
int right = lowerBound(nums, target + 1) - 1;
return new int[]{left, right};
}
private int lowerBound(int[] nums, int target) {
int l = 0, r = nums.length - 1;
while (l <= r) {
int mid = l + (r - l) / 2;
if (nums[mid] < target) l = mid + 1;
else r = mid - 1;
}
return l;
}
}
33. 搜索旋转排序数组（中等）
题目要求：给定一个原本升序、但在某个未知下标处旋转过的数组 nums（元素互不相同），以及 target，若 target 存在返回其下标，否则返回 -1。要求 O(log n)。 输入 nums = [4,5,6,7,0,1,2]，target = 0 → 输出 4 输入 nums = [4,5,6,7,0,1,2]，target = 3 → 输出 -1
思路：数组被旋转过但仍"局部有序"，二分的关键在于每次先判断 [l, mid] 和 [mid, r] 哪一段是有序的，再看 target 落在哪一段里，从而决定收缩哪一边。常见写法：若 nums[l] <= nums[mid] 说明左半有序，且 target 落在 [nums[l], nums[mid]) 内就搜左半、否则搜右半；否则右半有序，同理判断。不要死记"哪边大"，记住"先锁定有序段，再判断 target 是否在该段内"。
时间复杂度 O(log n)，空间复杂度 O(1)。
代码：
class Solution {
public int search(int[] nums, int target) {
int l = 0, r = nums.length - 1;
while (l <= r) {
int mid = l + (r - l) / 2;
if (nums[mid] == target) return mid;
if (nums[l] <= nums[mid]) {
if (nums[l] <= target && target < nums[mid]) {
r = mid - 1;
} else {
l = mid + 1;
}
} else {
if (nums[mid] < target && target <= nums[r]) {
l = mid + 1;
} else {
r = mid - 1;
}
}
}
return -1;
}
}
153. 寻找旋转排序数组中的最小值（中等）
题目要求：给定一个原本升序、在某处旋转过的数组 nums（元素互不相同），找出并返回其中最小的元素。 输入 nums = [3,4,5,1,2] → 输出 1 输入 nums = [4,5,6,7,0,1,2] → 输出 0
思路：旋转数组里最小值是唯一的"断崖点"。二分比较 nums[mid] 和 nums[r]：如果 nums[mid] > nums[r]，说明最小值在 mid 右边（右半无序），令 l = mid + 1；否则说明 mid 落在递增段、最小值在 mid 及其左边，令 r = mid。注意这里右边用 r = mid 而不是 mid - 1，因为 mid 本身可能就是最小值，避免漏点。
时间复杂度 O(log n)，空间复杂度 O(1)。
代码：
class Solution {
public int findMin(int[] nums) {
int l = 0, r = nums.length - 1;
while (l < r) {
int mid = l + (r - l) / 2;
if (nums[mid] > nums[r]) {
l = mid + 1;
} else {
r = mid;
}
}
return nums[l];
}
}
4. 寻找两个正序数组的中位数（困难）
题目要求：给定两个分别升序排列的数组 nums1 和 nums2，找出这两个数组合并后的中位数。要求时间复杂度 O(log(m+n))。 输入 nums1 = [1,3]，nums2 = [2] → 输出 2.0 输入 nums1 = [1,2]，nums2 = [3,4] → 输出 2.5
思路：要 O(log(min(m,n))) 就得用"找第 k 小"的二分思路，而不是归并。先把问题转化为"找第 k 小"，对较短的数组做二分切分：每次比较两个数组各自前 k/2 个元素的末尾 A[i] 和 B[j]，较小的那一侧前 k/2 个一定不可能是第 k 小，直接整段淘汰、k 相应减少。边界处理：某数组越界时直接淘汰另一数组。中位数就是"第 (m+n+1)/2 小"和"第 (m+n+2)/2 小"的平均（奇偶通用）。为了让代码好读，这里给出基于较短数组切分的标准写法。
时间复杂度 O(log(min(m,n)))，空间复杂度 O(1)。
代码：
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
if (nums1.length > nums2.length) {
int[] t = nums1; nums1 = nums2; nums2 = t;
}
int m = nums1.length, n = nums2.length;
int totalLeft = (m + n + 1) / 2;
int l = 0, r = m;
while (l <= r) {
int i = (l + r) / 2;
int j = totalLeft - i;
if (i < m && j > 0 && nums2[j - 1] > nums1[i]) {
l = i + 1;
} else if (i > 0 && j < n && nums1[i - 1] > nums2[j]) {
r = i - 1;
} else {
int maxLeft;
if (i == 0) maxLeft = nums2[j - 1];
else if (j == 0) maxLeft = nums1[i - 1];
else maxLeft = Math.max(nums1[i - 1], nums2[j - 1]);
if ((m + n) % 2 == 1) return maxLeft;
int minRight;
if (i == m) minRight = nums2[j];
else if (j == n) minRight = nums1[i];
else minRight = Math.min(nums1[i], nums2[j]);
return (maxLeft + minRight) / 2.0;
}
}
return 0.0;
}
}
十二、栈（5 题）
20. 有效的括号（简单）
题目要求：给定一个只包含 ‘(’ ‘)’ ‘{’ ‘}’ ‘[’ ‘]’ 的字符串 s，判断括号是否有效：左括号必须用相同类型的右括号闭合，且必须以正确顺序闭合。空串视为有效。 输入 s = “()” → 输出 true 输入 s = “()[]{}” → 输出 true 输入 s = “(]” → 输出 false
思路：括号匹配是栈的最经典应用。遇到左括号就把对应的右括号压栈；遇到右括号时检查栈顶是否正好是它——是则弹栈，否则立刻非法。遍历结束时栈必须为空。用 Map 维护"左括号->应匹配的右括号"，把判断集中到一处，避免一堆 if。 时间复杂度 O(n)，空间复杂度 O(n)。
代码：
import java.util.*;
class Solution {
public boolean isValid(String s) {
Deque<Character> stack = new ArrayDeque<>();
Map<Character, Character> map = new HashMap<>();
map.put('(', ')');
map.put('[', ']');
map.put('{', '}');
for (char c : s.toCharArray()) {
if (map.containsKey(c)) {
stack.push(map.get(c));
} else {
if (stack.isEmpty() || stack.pop() != c) return false;
}
}
return stack.isEmpty();
}
}
155. 最小栈（中等）
题目要求：设计一个栈，支持 push、pop、top，以及能在 O(1) 时间内获取栈中最小元素的 getMin。所有操作都在常数时间完成。 调用示例：MinStack minStack = new MinStack(); push(-2)；push(0)；push(-3)；getMin() → 返回 -3；pop()；top() → 返回 0；getMin() → 返回 -2。
思路：普通栈能 push/pop/top，但还要随时拿到最小值。核心是"辅助栈"思想：主栈正常存元素，另开一个栈 minStack，每次 push 时把"当前最小值"同步压入——push x 时压入 min(x, minStack 顶)。这样两个栈永远保持同高，pop 时一起弹，栈顶就是此刻的最小值，O(1) 拿到。
时间复杂度 O(1)（各操作），空间复杂度 O(n)。
代码：
import java.util.*;
class MinStack {
private Deque<Integer> stack;
private Deque<Integer> minStack;
public MinStack() {
stack = new ArrayDeque<>();
minStack = new ArrayDeque<>();
}
public void push(int val) {
stack.push(val);
if (minStack.isEmpty()) {
minStack.push(val);
} else {
minStack.push(Math.min(val, minStack.peek()));
}
}
public void pop() {
stack.pop();
minStack.pop();
}
public int top() {
return stack.peek();
}
public int getMin() {
return minStack.peek();
}
}
394. 字符串解码（中等）
题目要求：给定一个编码字符串，格式为 k[encoded_string]，表示方括号内的子串重复 k 次，编码可嵌套。返回解码后的字符串。k 为正整数。 输入 s = “3[a]2[bc]” → 输出 “aaabcbc” 输入 s = “3[a2[c]]” → 输出 “accaccacc”
思路：带嵌套的括号（如 3[a2[c]]）天然适合栈。用两个栈分别存"重复次数"和"进入嵌套前的已拼字符串"。遇到数字就累乘出 k；遇到 [ 时把当前 k 和当前串压栈，重置；遇到 ] 时弹栈：把"当前串"重复 k 次，拼接到"弹出的旧串"后面。普通字符直接追加到当前串。栈的作用就是记住每层括号之前的状态。
时间复杂度 O(n)（n 为展开后长度量级），空间复杂度 O(n)。
代码：
import java.util.*;
class Solution {
public String decodeString(String s) {
Deque<Integer> countStack = new ArrayDeque<>();
Deque<StringBuilder> strStack = new ArrayDeque<>();
StringBuilder cur = new StringBuilder();
int k = 0;
for (char c : s.toCharArray()) {
if (Character.isDigit(c)) {
k = k * 10 + (c - '0');
} else if (c == '[') {
countStack.push(k);
strStack.push(cur);
cur = new StringBuilder();
k = 0;
} else if (c == ']') {
StringBuilder prev = strStack.pop();
int times = countStack.pop();
for (int i = 0; i < times; i++) prev.append(cur);
cur = prev;
} else {
cur.append(c);
}
}
return cur.toString();
}
}
739. 每日温度（中等）
题目要求：给定一个每日气温数组 temperatures，对每一天算出需要等多少天才能遇到更高的温度；若之后都不会更高则填 0。返回对应长度的数组。 输入 temperatures = [73,74,75,71,69,72,76,73] → 输出 [1,1,4,2,1,1,0,0] 输入 temperatures = [30,40,50,60] → 输出 [1,1,1,0]
思路：“找右边第一个比当前大的元素距离多少"是单调栈的标准套路。维护一个存"下标"的栈，栈内对应温度单调递减。遍历到新温度时，只要它比栈顶下标对应的温度大，就说明找到了栈顶的"下一个更高温”，两者下标差就是答案，弹栈；然后把当前下标压栈。一遍扫描即可，无需对每个位置再往后找。单调栈经典题。 时间复杂度 O(n)，空间复杂度 O(n)。
代码：
import java.util.*;
class Solution {
public int[] dailyTemperatures(int[] temperatures) {
int n = temperatures.length;
int[] ans = new int[n];
Deque<Integer> stack = new ArrayDeque<>();
for (int i = 0; i < n; i++) {
while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
int prev = stack.pop();
ans[prev] = i - prev;
}
stack.push(i);
}
return ans;
}
}
84. 柱状图中最大的矩形（困难）
题目要求：给定 n 根柱子的高度数组 heights（宽度均为 1），求在直方图中能勾勒出的最大矩形面积。 输入 heights = [2,1,5,6,2,3] → 输出 10 输入 heights = [2,4] → 输出 4
思路：对每个柱子，它作为"最矮的那根"能撑开的最大矩形 = 它的高度 ×（左边第一个比它矮的位置到右边第一个比它矮的位置之间的宽度）。这又是单调栈：找左右两边第一个更矮的边界。用单调递增栈，遇到更矮的柱子时，栈顶就是"刚确定右边界的柱子"，它的左边界就是新的栈顶。为省掉首尾边界判断，在数组头尾各补一个高度 0 的"哨兵柱"，让所有真实柱子都能被正常弹栈结算。 时间复杂度 O(n)，空间复杂度 O(n)。
代码：
import java.util.*;
class Solution {
public int largestRectangleArea(int[] heights) {
int n = heights.length;
int[] h = new int[n + 2];
System.arraycopy(heights, 0, h, 1, n);
Deque<Integer> stack = new ArrayDeque<>();
int max = 0;
for (int i = 0; i < h.length; i++) {
while (!stack.isEmpty() && h[i] < h[stack.peek()]) {
int idx = stack.pop();
int left = stack.peek();
int width = i - left - 1;
max = Math.max(max, h[idx] * width);
}
stack.push(i);
}
return max;
}
}
十三、堆（3 题）
215. 数组中的第 K 个最大元素（中等）
题目要求：给定一个整数数组 nums 和整数 k，返回数组中第 k 个最大的元素（指按降序排列后的第 k 个，不是第 k 个不同元素）。 输入 nums = [3,2,1,5,6,4]，k = 2 → 输出 5 输入 nums = [3,2,3,1,2,4,5,5,6]，k = 4 → 输出 4
思路：求第 K 大，最直观是用一个大小为 K 的小顶堆：遍历数组，把元素塞进堆，堆超 K 就弹出最小的。遍历完后堆里就是最大的 K 个数，堆顶就是第 K 大。相比对全数组排序，堆只维护 K 个元素，复杂度更优；这也是"Top-K"问题的通用模板。 时间复杂度 O(n log K)，空间复杂度 O(K)。
代码：
import java.util.*;
class Solution {
public int findKthLargest(int[] nums, int k) {
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
for (int x : nums) {
minHeap.offer(x);
if (minHeap.size() > k) {
minHeap.poll();
}
}
return minHeap.peek();
}
}
347. 前 K 个高频元素（中等）
题目要求：给定一个整数数组 nums 和整数 k，返回出现频率最高的前 k 个元素，顺序任意。答案唯一。 输入 nums = [1,1,1,2,2,3]，k = 2 → 输出 [1,2] 输入 nums = [1]，k = 1 → 输出 [1]
思路：分两步。第一步先用 HashMap 统计每个数的出现频次；第二步对"频次"做 Top-K——用一个大小为 K 的小顶堆，堆里存 (数, 频次)，按频次排序，遍历完堆里就是频次最高的 K 个。本质是 215 题的套娃，只是比较对象从"数值"换成了"频次"。 时间复杂度 O(n log K)，空间复杂度 O(n)。
代码：
import java.util.*;
class Solution {
public int[] topKFrequent(int[] nums, int k) {
Map<Integer, Integer> freq = new HashMap<>();
for (int x : nums) freq.merge(x, 1, Integer::sum);
PriorityQueue<Map.Entry<Integer, Integer>> heap = new PriorityQueue<>(
(a, b) -> a.getValue() - b.getValue());
for (Map.Entry<Integer, Integer> e : freq.entrySet()) {
heap.offer(e);
if (heap.size() > k) heap.poll();
}
int[] ans = new int[k];
for (int i = 0; i < k; i++) ans[i] = heap.poll().getKey();
return ans;
}
}
295. 数据流的中位数（困难）
题目要求：设计一个数据结构，支持两种操作：addNum(num) 从数据流中添加一个整数；findMedian() 返回当前所有元素的中位数（偶数个元素时为中间两数的平均）。 调用示例：MedianFinder mf = new MedianFinder(); addNum(1)；addNum(2)；findMedian() → 返回 1.5；addNum(3)；findMedian() → 返回 2.0。
思路：数据流要随时取中位数，经典做法是"双堆"：一个大顶堆 left 存较小的一半（堆顶是左半最大），一个小顶堆 right 存较大的一半（堆顶是右半最小）。维持两条不变量：① left.size() == right.size() 或 left 比 right 多 1；② left 所有元素 <= right 所有元素。新来的数先放 left（比 left 顶大就先放 right 再调整），再做平衡。取中位数时：两堆等大就是两堆顶平均，不等就是 left 堆顶。
时间复杂度 addNum O(log n)，findMedian O(1)，空间复杂度 O(n)。
代码：
import java.util.*;
class MedianFinder {
private PriorityQueue<Integer> left; // 大顶堆
private PriorityQueue<Integer> right; // 小顶堆
public MedianFinder() {
left = new PriorityQueue<>((a, b) -> b - a);
right = new PriorityQueue<>();
}
public void addNum(int num) {
if (left.isEmpty() || num <= left.peek()) {
left.offer(num);
} else {
right.offer(num);
}
if (left.size() > right.size() + 1) {
right.offer(left.poll());
} else if (right.size() > left.size()) {
left.offer(right.poll());
}
}
public double findMedian() {
if (left.size() > right.size()) return left.peek();
return (left.peek() + right.peek()) / 2.0;
}
}
十四、贪心算法（4 题）
121. 买卖股票的最佳时机（简单）
题目要求：给定一个数组 prices，prices[i] 是某只股票第 i 天的价格。你只能选择某一天买入、在之后某一天卖出，计算所能获得的最大利润；如果无法获得利润，返回 0。数组长度至少为 1。 输入 prices = [7,1,5,3,6,4] → 输出 5（第 2 天买入价 1，第 5 天卖出价 6）。
思路：核心贪心是——在第 i 天卖出时，要让利润最大，买入点必须是 i 之前所有天里价格最低的那一天。所以我们只需遍历一次，一边维护"历史最低价 minPrice"，一边计算"当天价 − 历史最低价"的利润并更新全局最大利润即可。不需要记录买入点，只需要记录历史最低值。时间复杂度 O(n)，空间复杂度 O(1)。
代码：
class Solution {
public int maxProfit(int[] prices) {
int minPrice = Integer.MAX_VALUE;
int maxProfit = 0;
for (int p : prices) {
if (p < minPrice) {
minPrice = p;
} else if (p - minPrice > maxProfit) {
maxProfit = p - minPrice;
}
}
return maxProfit;
}
}
55. 跳跃游戏（中等）
题目要求：给定非负整数数组 nums，每个元素代表从该位置最多可向前跳跃的步数。你最初位于数组第一个下标，判断是否能到达最后一个下标。 输入 nums = [2,3,1,1,4] → 输出 true；输入 nums = [3,2,1,0,4] → 输出 false。
思路：贪心维护"当前能到达的最远位置 maxReach"。遍历数组，对于每个位置 i，如果 i 已经超过了 maxReach，说明跳不到这里，直接返回 false；否则更新 maxReach = max(maxReach, i + nums[i])。如果遍历过程中 maxReach 已经覆盖到最后一个下标，就提前返回 true。贪心正确性在于：如果能跳到 i，那么 i 之前所有位置也都能跳到，取最远可达范围自然最优。时间复杂度 O(n)，空间复杂度 O(1)。
代码：
class Solution {
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;
}
}
45. 跳跃游戏 II（中等）
题目要求：给定非负整数数组 nums，每个元素代表从该位置最多可向前跳跃的步数。你最初位于数组第一个下标，目标是到达最后一个下标，求最少跳跃次数。题目保证一定可以到达。 输入 nums = [2,3,1,1,4] → 输出 2（2→3→4，跳 2 次）。
思路：这题要算最少跳几步，贪心策略是"按层跳跃"。维护当前跳跃的边界 end、下一步能到的最远位置 farthest，以及步数 jumps。遍历到 i 时更新 farthest；当 i 到达当前边界 end 时，说明这一步必须跳了，jumps++，把 end 更新为 farthest。这样每一步都选"能跳到最远"的位置，步数自然最少。时间复杂度 O(n)，空间复杂度 O(1)。
代码：
class Solution {
public int jump(int[] nums) {
int end = 0, farthest = 0, jumps = 0;
for (int i = 0; i < nums.length - 1; i++) {
farthest = Math.max(farthest, i + nums[i]);
if (i == end) {
jumps++;
end = farthest;
}
}
return jumps;
}
}
763. 划分字母区间（中等）
题目要求：给定一个字符串 s（仅小写字母），把它划分为尽可能多的片段，要求同一字母最多出现在一个片段中。返回每个片段的长度（按顺序）。 输入 s = “ababcbacadefegdehijhklij” → 输出 [9,7,8]。
思路：贪心思路——每个字母最后一次出现的位置，就是它所在区间的右端点。先遍历一遍记录每个字符的最远出现位置 last[c]。再遍历一遍，维护当前区间的右端点 right = max(right, last[s[i]])；当 i 走到 right 时，说明从区间起点到 right 之间所有字符的最后出现位置都不会超过 right，此时可以切一刀，记录区间长度。时间复杂度 O(n)，空间复杂度 O(1)（固定 26 个字母）。
代码：
import java.util.*;
class Solution {
public List<Integer> partitionLabels(String s) {
int[] last = new int[26];
for (int i = 0; i < s.length(); i++) {
last[s.charAt(i) - 'a'] = i;
}
List<Integer> ans = new ArrayList<>();
int start = 0, right = 0;
for (int i = 0; i < s.length(); i++) {
right = Math.max(right, last[s.charAt(i) - 'a']);
if (i == right) {
ans.add(right - start + 1);
start = i + 1;
}
}
return ans;
}
}
十五、动态规划（10 题）
70. 爬楼梯（简单）
题目要求：假设你要爬 n 阶楼梯，每次可以爬 1 或 2 阶。问有多少种不同方法可以爬到楼顶？n 为正整数。 输入 n = 2 → 输出 2；输入 n = 3 → 输出 3。
思路：经典 DP 入门题。状态定义 dp[i] = 爬到第 i 阶有多少种方法。转移方程：到第 i 阶要么从 i−1 跨一步、要么从 i−2 跨两步，所以 dp[i] = dp[i−1] + dp[i−2]，本质就是斐波那契数列。初始值 dp[1]=1、dp[2]=2（也可 dp[0]=1、dp[1]=1）。空间上只需前两个状态，用滚动变量即可。时间复杂度 O(n)，空间复杂度 O(1)。
代码：
class Solution {
public int climbStairs(int n) {
if (n <= 2) return n;
int prev2 = 1, prev1 = 2;
for (int i = 3; i <= n; i++) {
int cur = prev1 + prev2;
prev2 = prev1;
prev1 = cur;
}
return prev1;
}
}
118. 杨辉三角（简单）
题目要求：给定非负整数 numRows，生成杨辉三角的前 numRows 行。杨辉三角中每个数是它左上方和右上方数之和，每行首尾均为 1。 输入 numRows = 5 → 输出 [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]。
思路：DP 思路——第 i 行的第 j 个数等于上一行第 j−1 和第 j 个数之和。状态就是三角形本身，每行首尾固定为 1，中间元素直接由上一行算出。按行逐层构造即可。时间复杂度 O(n²)，空间复杂度 O(n²)（返回结果本身）。
代码：
import java.util.*;
class Solution {
public List<List<Integer>> generate(int numRows) {
List<List<Integer>> ans = new ArrayList<>();
for (int i = 0; i < numRows; i++) {
List<Integer> row = new ArrayList<>();
for (int j = 0; j <= i; j++) {
if (j == 0 || j == i) {
row.add(1);
} else {
row.add(ans.get(i - 1).get(j - 1) + ans.get(i - 1).get(j));
}
}
ans.add(row);
}
return ans;
}
}
198. 打家劫舍（中等）
题目要求：给定一个非负整数数组 nums，代表沿街每个房屋存放的金额。相邻房屋在同一晚被闯入会触发警报，求不触发警报的情况下一夜能偷到的最高总金额。 输入 nums = [1,2,3,1] → 输出 4；输入 nums = [2,7,9,3,1] → 输出 12。
思路：状态定义 dp[i] = 考虑前 i 间房时能偷到的最大金额。转移方程：对第 i 间房，有两种选择——偷（则 i−1 不能偷，金额 = dp[i−2] + nums[i]）或不偷（金额 = dp[i−1]），取较大者：dp[i] = max(dp[i−1], dp[i−2] + nums[i])。初始值 dp[0] = nums[0]，dp[1] = max(nums[0], nums[1])。只需前两个状态，滚动变量即可。时间复杂度 O(n)，空间复杂度 O(1)。
代码：
class Solution {
public int rob(int[] nums) {
int n = nums.length;
if (n == 1) return nums[0];
int prev2 = nums[0];
int prev1 = Math.max(nums[0], nums[1]);
for (int i = 2; i < n; i++) {
int cur = Math.max(prev1, prev2 + nums[i]);
prev2 = prev1;
prev1 = cur;
}
return prev1;
}
}
279. 完全平方数（中等）
题目要求：给定正整数 n，求最少需要多少个完全平方数（如 1、4、9、16…），使它们的和等于 n。 输入 n = 12 → 输出 3（4+4+4）；输入 n = 13 → 输出 2（4+9）。
思路：完全背包型 DP。状态定义 dp[i] = 组成数字 i 所需的最少完全平方数个数。转移方程：对每个 i，枚举所有不超过 i 的完全平方数 j²，dp[i] = min(dp[i − j²] + 1)。初始值 dp[0] = 0，其余初始为无穷大（可用 i 的最大值，因为最坏情况 i 个 1）。时间复杂度 O(n√n)，空间复杂度 O(n)。
代码：
class Solution {
public int numSquares(int n) {
int[] dp = new int[n + 1];
for (int i = 1; i <= n; i++) {
dp[i] = i; // 最坏：i 个 1
for (int j = 1; j * j <= i; j++) {
dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
}
}
return dp[n];
}
}
322. 零钱兑换（中等）
题目要求：给定不同面额的硬币 coins 和总金额 amount，求凑成总金额所需的最少硬币个数；如果没有任何一种组合能凑出，返回 -1。每种硬币数量无限。 输入 coins = [1,2,5], amount = 11 → 输出 3（5+5+1）；输入 coins = [2], amount = 3 → 输出 -1。
思路：也是完全背包 DP。状态定义 dp[i] = 凑成金额 i 所需的最少硬币数。转移方程：对每个 i，枚举所有硬币 coin，如果 coin ≤ i，则 dp[i] = min(dp[i], dp[i − coin] + 1)。初始值 dp[0] = 0，其余初始为一个不可达的标记值（如 amount+1），最后 dp[amount] 若仍为该值则返回 −1。时间复杂度 O(amount × n)，空间复杂度 O(amount)。
代码：
import java.util.*;
class Solution {
public int coinChange(int[] coins, int amount) {
int max = amount + 1;
int[] dp = new int[amount + 1];
Arrays.fill(dp, max);
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];
}
}
139. 单词拆分（中等）
题目要求：给定字符串 s 和单词字典 wordDict，判断 s 是否可以被拆分成一个或多个字典中出现的单词（拆分时字典单词可重复使用，且字典中单词无重复）。 输入 s = “leetcode”, wordDict = [“leet”,“code”] → 输出 true。
思路：状态定义 dp[i] = 字符串前 i 个字符（s[0..i−1]）能否被拆分成字典中的单词。转移方程：对每个 i，枚举 j < i，如果 dp[j] == true 且 s[j..i−1] 在字典中，则 dp[i] = true。初始值 dp[0] = true（空串）。用 HashSet 存字典加速查找。时间复杂度 O(n²)，空间复杂度 O(n)。
代码：
import java.util.*;
class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
Set<String> 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];
}
}
300. 最长递增子序列（中等）
题目要求：给定整数数组 nums，找到其中最长严格递增子序列的长度。子序列不要求连续，但要求保持相对顺序。 输入 nums = [10,9,2,5,3,7,101,18] → 输出 4（最长递增子序列为 [2,3,7,101]）。
思路：这里给 O(n²) DP 写法，最直观好懂。状态定义 dp[i] = 以 nums[i] 结尾的最长递增子序列长度。转移方程：对每个 i，枚举 j < i，若 nums[j] < nums[i]，则 dp[i] = max(dp[i], dp[j] + 1)。初始值每个 dp[i] = 1（自身）。答案为所有 dp[i] 的最大值。另有 O(n log n) 二分优化写法（维护 tails 数组），但 DP 写法更易理解。时间复杂度 O(n²)，空间复杂度 O(n)。
代码：
import java.util.*;
class Solution {
public int lengthOfLIS(int[] nums) {
int n = nums.length;
int[] dp = new int[n];
Arrays.fill(dp, 1);
int ans = 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);
}
}
ans = Math.max(ans, dp[i]);
}
return ans;
}
}
152. 乘积最大子数组（中等）
题目要求：给定整数数组 nums，找出乘积最大的非空连续子数组，返回该子数组的乘积。数组中可能包含正数、负数和 0。 输入 nums = [2,3,-2,4] → 输出 6（子数组 [2,3]）；输入 nums = [-2,0,-1] → 输出 0。
思路：乘积问题和求和不同——负数乘以负数会变正，所以光记录最大值不够，还要同时记录最小值。状态定义：maxDp[i] = 以 i 结尾的最大乘积，minDp[i] = 以 i 结尾的最小乘积。转移方程：maxDp[i] = max(nums[i], maxDp[i−1]×nums[i], minDp[i−1]×nums[i])，minDp[i] 同理取最小。初始值 maxDp[0] = minDp[0] = nums[0]。全程用变量滚动即可。时间复杂度 O(n)，空间复杂度 O(1)。
代码：
class Solution {
public int maxProduct(int[] nums) {
int maxProd = nums[0], minProd = nums[0], ans = nums[0];
for (int i = 1; i < nums.length; i++) {
int n = nums[i];
int mx = maxProd, mn = minProd;
maxProd = Math.max(n, Math.max(mx * n, mn * n));
minProd = Math.min(n, Math.min(mx * n, mn * n));
ans = Math.max(ans, maxProd);
}
return ans;
}
}
416. 分割等和子集（中等）
题目要求：给定一个只包含正整数的非空数组 nums，判断是否可以将数组分割成两个子集，使得两个子集的元素和相等。 输入 nums = [1,5,11,5] → 输出 true（可分割为 [1,5,5] 和 [11]）；输入 nums = [1,2,3,5] → 输出 false。
思路：本质是 0/1 背包——能否从数组中选若干个数，使它们的和等于总和的一半 target。先算总和，若为奇数直接返回 false。状态定义 dp[j] = 容量为 j 的背包能否恰好装满。转移方程（逆序遍历避免重复使用同一元素）：dp[j] = dp[j] || dp[j − nums[i]]。初始值 dp[0] = true。时间复杂度 O(n × target)，空间复杂度 O(target)。
代码：
import java.util.*;
class Solution {
public boolean canPartition(int[] nums) {
int sum = 0;
for (int n : nums) sum += n;
if (sum % 2 != 0) return false;
int target = sum / 2;
boolean[] dp = new boolean[target + 1];
dp[0] = true;
for (int n : nums) {
for (int j = target; j >= n; j--) {
dp[j] = dp[j] || dp[j - n];
}
}
return dp[target];
}
}
32. 最长有效括号（困难）
题目要求：给定一个只包含 ‘(’ 和 ‘)’ 的字符串 s，找出最长的、连续的有效（格式正确）括号子串的长度。 输入 s = “(()” → 输出 2；输入 s = “)()())” → 输出 4（最长有效子串为 “()()"）。
思路：用栈解法，直观好懂。栈底始终保持"最后一个未匹配右括号的下标”。初始压入 −1 作为哨兵。遍历字符串：遇到左括号，压入下标；遇到右括号，弹出栈顶——若弹出后栈空，说明这个右括号无法匹配，把它的下标压入作为新的哨兵；若栈不空，则当前有效长度 = i − 栈顶下标。全程维护最大值。时间复杂度 O(n)，空间复杂度 O(n)。
代码：
import java.util.*;
class Solution {
public int longestValidParentheses(String s) {
Deque<Integer> stack = new ArrayDeque<>();
stack.push(-1);
int ans = 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 {
ans = Math.max(ans, i - stack.peek());
}
}
}
return ans;
}
}
十六、多维动态规划（5 题）
62. 不同路径（中等）
题目要求：给定一个 m 行 n 列的网格，机器人从左上角出发，每次只能向下或向右走一步，求到达右下角共有多少条不同的路径。1 <= m, n <= 100，题目数据保证答案在 32 位整数范围内。
输入 m = 3，n = 7 → 输出 28。
输入 m = 3，n = 2 → 输出 3。
思路：经典二维 DP 入门题。定义 dp[i][j] 为"从起点走到第 i 行第 j 列格子的路径数"。因为每步只能向右或向下，所以到达 (i,j) 的前一步要么是它上方 (i-1,j)，要么是它左方 (i,j-1)，于是转移方程就是 dp[i][j] = dp[i-1][j] + dp[i][j-1]。初始值：第一行只能一路向右走、第一列只能一路向下走，所以 dp[0][0..n-1] 和 dp[0..m-1][0] 都恒为 1。答案就是右下角 dp[m-1][n-1]。空间上每行只依赖上一行和当前行左边，可以滚动成一维数组，但这里给出最直观的二维版本便于理解。
时间复杂度 O(m×n)，空间复杂度 O(m×n)。
代码：
import java.util.*;
class Solution {
public int uniquePaths(int m, int n) {
int[][] dp = new int[m][n];
for (int i = 0; i < m; i++) dp[i][0] = 1;
for (int j = 0; j < n; j++) dp[0][j] = 1;
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
return dp[m - 1][n - 1];
}
}
64. 最小路径和（中等）
题目要求：给定一个 m×n 的非负整数网格，每次只能向下或向右走一步，求从左上角走到右下角的路径上所有数字之和的最小值。1 <= m, n <= 200，网格元素为 0 <= grid[i][j] <= 200 的非负整数。
输入 grid = [[1,3,1],[1,5,1],[4,2,1]] → 输出 7。
输入 grid = [[1,2,3],[4,5,6]] → 输出 12。
思路：和 62 题是同一副骨架，只是把"路径数相加"换成了"最小代价累加"。定义 dp[i][j] 为"从起点走到 (i,j) 时累计的最小路径和"。转移：到达 (i,j) 只能从上方或左方过来，取两者较小者再加上当前格子的数，即 dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]。边界：dp[0][0] = grid[0][0]；第一行只能一路向右累加，第一列只能一路向下累加，没有第二个方向可选。注意要按行优先、从左到右遍历，这样用到的 dp[i-1][j] 和 dp[i][j-1] 都已经算好。同样可以滚动成一维数组，这里给清晰的二维版。
时间复杂度 O(m×n)，空间复杂度 O(m×n)。
代码：
import java.util.*;
class Solution {
public int minPathSum(int[][] grid) {
int m = grid.length, n = grid[0].length;
int[][] dp = new int[m][n];
dp[0][0] = grid[0][0];
for (int i = 1; i < m; i++) dp[i][0] = dp[i - 1][0] + grid[i][0];
for (int j = 1; j < n; j++) dp[0][j] = dp[0][j - 1] + grid[0][j];
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
}
}
return dp[m - 1][n - 1];
}
}
5. 最长回文子串（中等）
题目要求：给定一个字符串 s，找出其中最长的回文子串（子串要求连续），返回该子串。1 <= s.length <= 1000，s 仅由数字和英文字母组成。
输入 s = “babad” → 输出 “bab”（“aba” 也是合法答案）。
输入 s = “cbbd” → 输出 “bb”。
思路：求"一个子串是不是回文"天然可以用 DP：定义 dp[i][j] 表示子串 s[i..j]（含两端）是否是回文。转移方程：当 s[i] == s[j] 时，s[i..j] 是否回文取决于去掉两端后剩下的 s[i+1..j-1] 是否回文，即 dp[i][j] = dp[i+1][j-1]。关键边界：长度为 1 的子串 i==j 一定是回文；长度为 2 的子串 j == i+1 时只要两个字符相等就是回文（这时 i+1 > j-1，要单独处理）。由于 dp[i][j] 依赖左下角的 dp[i+1][j-1]，所以要按子串长度从小到大、或按 i 从大到小遍历。记录过程中遇到的最长回文起点和长度即可。
时间复杂度 O(n²)，空间复杂度 O(n²)。
代码：
import java.util.*;
class Solution {
public String longestPalindrome(String s) {
int n = s.length();
boolean[][] dp = new boolean[n][n];
int start = 0, maxLen = 1;
for (int i = 0; i < n; i++) dp[i][i] = true;
for (int len = 2; len <= n; len++) {
for (int i = 0; i <= n - len; i++) {
int j = i + len - 1;
if (s.charAt(i) != s.charAt(j)) {
dp[i][j] = false;
} else {
dp[i][j] = (len == 2) || dp[i + 1][j - 1];
}
if (dp[i][j] && len > maxLen) {
start = i;
maxLen = len;
}
}
}
return s.substring(start, start + maxLen);
}
}
1143. 最长公共子序列（中等）
题目要求：给定两个字符串 text1 和 text2，求它们的最长公共子序列的长度。子序列不要求连续，但要保持相对顺序；若不存在公共子序列则返回 0。1 <= text1.length, text2.length <= 1000，两个字符串都仅由小写英文字母组成。
输入 text1 = “abcde”，text2 = “ace” → 输出 3。
输入 text1 = “abc”，text2 = “def” → 输出 0。
思路：经典二维 DP，和编辑距离同构。两个字符串的子序列问题，状态一律取"前缀"：定义 dp[i][j] 为 text1 的前 i 个字符与 text2 的前 j 个字符的最长公共子序列长度。为了让下标统一，下面把 dp 开成 (m+1)×(n+1)，第 0 行第 0 列表示其中一个串为空，LCS 必然为 0。转移看两个串的末字符：若 text1[i-1] == text2[j-1]，这个字符可以接到前面的 LCS 后面，即 dp[i][j] = dp[i-1][j-1] + 1；若不等，则这个字符至少有一个用不上，取"丢掉 text1 末位"或"丢掉 text2 末位"的较大者，即 dp[i][j] = max(dp[i-1][j], dp[i][j-1])。最后答案就是 dp[m][n]。空间可滚动为一行数组，这里给满表版本最直观。
时间复杂度 O(m×n)，空间复杂度 O(m×n)。
代码：
import java.util.*;
class Solution {
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];
}
}
72. 编辑距离（中等）
题目要求：给定两个字符串 word1 和 word2，求将 word1 转换成 word2 所使用的最少操作次数。共有三种操作：插入一个字符、删除一个字符、替换一个字符。0 <= word1.length, word2.length <= 500，两个字符串都由小写英文字母组成。
输入 word1 = “horse”，word2 = “ros” → 输出 3。
输入 word1 = “intention”，word2 = “execution” → 输出 5。
思路：二维 DP 的模板题，必须把转移方程讲透。定义 dp[i][j] 为"把 word1 的前 i 个字符变成 word2 的前 j 个字符"所需的最少操作次数，同样开成 (m+1)×(n+1)。为什么是三种操作？站在末字符 word1[i-1] 和 word2[j-1] 的角度倒推上一步：
- 增：在
word1末尾插入一个字符，使它匹配word2[j-1]。那插入前word1的前i个字符只需变成word2的前j-1个，代价是dp[i][j-1] + 1。 - 删：把
word1末尾字符word1[i-1]删掉，剩下的前i-1个字符要变成完整的word2前j个，代价是dp[i-1][j] + 1。 - 改：把
word1[i-1]改成word2[j-1]。若二者已经相等，不用改，直接继承dp[i-1][j-1]；若不等，改一下，代价是dp[i-1][j-1] + 1。
三者取最小就是 dp[i][j]。边界：dp[0][j] = j（空串变成 word2 前 j 个字符只能逐个插入），dp[i][0] = i（word1 前 i 个字符变空串只能逐个删除）。答案为 dp[m][n]。
时间复杂度 O(m×n)，空间复杂度 O(m×n)。
代码：
import java.util.*;
class Solution {
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(
Math.min(dp[i - 1][j], dp[i][j - 1]),
dp[i - 1][j - 1]);
}
}
}
return dp[m][n];
}
}
十七、技巧（5 题）
136. 只出现一次的数字（简单）
题目要求：给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。要求算法具有线性时间复杂度，且不使用额外空间。 输入 nums = [2,2,1] → 输出 1；输入 nums = [4,1,2,1,2] → 输出 4。
思路：异或的两个性质——x^x=0、x^0=x，而且异或满足交换律。把数组所有数异或起来，成对出现的都抵消成 0，剩下的就是那个单独出现的数。一行循环搞定，不需要额外空间。
时间复杂度 O(n)，空间复杂度 O(1)。
class Solution {
public int singleNumber(int[] nums) {
int res = 0;
for (int num : nums) res ^= num;
return res;
}
}
169. 多数元素（简单）
题目要求：给定一个大小为 n 的数组 nums，返回其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。可以假设数组是非空的，并且给定的数组总是存在多数元素。 输入 nums = [3,2,3] → 输出 3；输入 nums = [2,2,1,1,1,2,2] → 输出 2。
思路：摩尔投票法。核心思想是"抵消"——遇到一个数就给它投一票，票为 0 就换候选人；遇到相同数票数+1，不同数-1。由于多数元素出现次数超过 n/2，它最后一定是幸存者。 时间复杂度 O(n)，空间复杂度 O(1)。
class Solution {
public int majorityElement(int[] nums) {
int candidate = nums[0], count = 1;
for (int i = 1; i < nums.length; i++) {
if (count == 0) candidate = nums[i];
count += (nums[i] == candidate) ? 1 : -1;
}
return candidate;
}
}
75. 颜色分类（中等）
题目要求：给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。我们使用整数 0、1 和 2 分别表示红色、白色和蓝色。必须不使用库内置的 sort 函数。 输入 nums = [2,0,2,1,1,0] → 输出 [0,0,1,1,2,2]。
思路：荷兰国旗问题，三指针一次遍历。left 指向 0 的右边界，right 指向 2 的左边界，cur 扫描：遇到 0 就和 left 交换并右移；遇到 2 就和 right 交换并左移（注意交换后 cur 不能前进，因为从 right 换过来的可能是 0 或 2，需要再判断一次）；遇到 1 直接跳过。 时间复杂度 O(n)，空间复杂度 O(1)。
class Solution {
public void sortColors(int[] nums) {
int left = 0, right = nums.length - 1, cur = 0;
while (cur <= right) {
if (nums[cur] == 0) {
int tmp = nums[left];
nums[left] = nums[cur];
nums[cur] = tmp;
left++;
cur++;
} else if (nums[cur] == 2) {
int tmp = nums[right];
nums[right] = nums[cur];
nums[cur] = tmp;
right--;
} else {
cur++;
}
}
}
}
31. 下一个排列（中等）
题目要求：给定一个整数数组 nums，找出 nums 的下一个排列（即字典序中下一个更大的排列）。如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。必须原地修改，只允许使用额外常数空间。 输入 nums = [1,2,3] → 输出 [1,3,2]；输入 nums = [3,2,1] → 输出 [1,2,3]；输入 nums = [1,1,5] → 输出 [1,5,1]。
思路：经典三步法。① 从右往左找第一个下降的位置 i（nums[i] < nums[i+1]），说明 i 及之前的前缀还能变大；② 从右往左找第一个比 nums[i] 大的位置 j，交换 i 和 j；③ 把 i 之后的后缀整个翻转（因为交换后后缀仍是降序，翻转后变成最小排列）。如果步骤①找不到 i，说明已是最大排列，直接整体翻转回最小。
时间复杂度 O(n)，空间复杂度 O(1)。
class Solution {
public void nextPermutation(int[] nums) {
int n = nums.length;
int i = n - 2;
while (i >= 0 && nums[i] >= nums[i + 1]) i--;
if (i >= 0) {
int j = n - 1;
while (j >= 0 && nums[j] <= nums[i]) j--;
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
int left = i + 1, right = n - 1;
while (left < right) {
int tmp = nums[left];
nums[left] = nums[right];
nums[right] = tmp;
left++;
right--;
}
}
}
287. 寻找重复数（中等）
题目要求：给定一个包含 n + 1 个整数的数组 nums，其数字都在 [1, n] 范围内。假设 nums 只有一个重复的整数，找出这个重复的数。要求不能修改数组（假定数组只读），且只用 O(1) 的额外空间。 输入 nums = [1,3,4,2,2] → 输出 2；输入 nums = [3,1,3,4,2] → 输出 3。
思路：数组值在 [1, n] 范围内且只有一个重复数，可以把它看成链表——索引 i 指向 nums[i]。由于有重复值，必然形成环，用 Floyd 判圈（快慢指针）找入口即可。快指针每次走两步，慢指针走一步，相遇后把慢指针放回起点，两个指针同步走，再次相遇的点就是重复数。鸽巢原理保证必然有环。
时间复杂度 O(n)，空间复杂度 O(1)。
class Solution {
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;
}
}