面试经典 150 题 · Java 题解

力扣官方精选 150 题，按 21 个专题整理。每题：思路脉络 + Mermaid 图 + Java 代码 + 复杂度 + 易错点。

题型分布

专题	题数	核心思维
数组 / 字符串	24	双指针原地操作、区间合并、模拟
双指针	5	有序对撞、回文验证、有序两数
滑动窗口	4	定长/变长窗口 + 状态计数
矩阵	5	原地标记、螺旋遍历、坐标变换
哈希表	9	逆向映射、O(1) 查询、计数分组
区间	4	排序 + 合并/插入/贪心
栈	5	匹配消除、单调栈、表达式求值
链表	11	哨兵节点、快慢指针、指针操作
二叉树	17	递归三部曲、层序 BFS、构造
二叉搜索树	3	中序有序性、上下界
图	9	DFS/BFS 染色、拓扑排序、并查集
字典树	3	前缀检索、DFS 搜词
回溯	7	选→递→撤销
分治	4	找中点、递归两半、合并
Kadane 算法	2	最大子数组/环形子数组
二分查找	7	单调性 + 边界收缩
堆	4	Top-K、动态中位数
位运算	6	异或抵消、位统计、掩码
数学	6	数论、模拟、二分逼近
一维动态规划	5	状态 + 转移 + 滚动优化
多维动态规划	9	二维状态、区间 DP、股票系列

[[#1. 数组 / 字符串]] · 24 题
[[#2. 双指针]] · 5 题
[[#3. 滑动窗口]] · 4 题
[[#4. 矩阵]] · 5 题
[[#5. 哈希表]] · 9 题
[[#6. 区间]] · 4 题
[[#7. 栈]] · 5 题
[[#8. 链表]] · 11 题
[[#9. 二叉树]] · 17 题
[[#10. 二叉搜索树]] · 3 题
[[#11. 图]] · 9 题
[[#12. 字典树]] · 3 题
[[#13. 回溯]] · 7 题
[[#14. 分治]] · 4 题
[[#15. Kadane 算法]] · 2 题
[[#16. 二分查找]] · 7 题
[[#17. 堆]] · 4 题
[[#18. 位运算]] · 6 题
[[#19. 数学]] · 6 题
[[#20. 一维动态规划]] · 5 题
[[#21. 多维动态规划]] · 9 题

1. 数组 / 字符串

数组和字符串题的核心是双指针原地操作——快慢指针做筛选、对撞指针做搜索、归并指针做合并。难点在边界处理和原地操作的指针顺序。

88. 合并两个有序数组

两个非递减整数数组 nums1（末尾留 m 后补 0）、nums2，合并到 nums1 使其有序。原地，O(m+n)。

思路脉络：朴素是合并后排序 O((m+n)log(m+n))，没利用"两个都有序"。两数组都从后往前，用三个指针 i=m-1, j=n-1, k=m+n-1，每次把大的放进 nums1[k]，从后往前填不会覆盖未处理的 nums1 元素。这就是逆向双指针——正向填会覆盖，反向填天然安全。

801

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int i = m - 1, j = n - 1, k = m + n - 1;
        while (i >= 0 && j >= 0) {
            nums1[k--] = nums1[i] > nums2[j] ? nums1[i--] : nums2[j--];
        }
        while (j >= 0) nums1[k--] = nums2[j--]; // nums1 剩余的不用动(已在位)
    }
}

[!info] 复杂度
时间 O(m+n)，空间 O(1)。

[!warning] 易错点
必须从后往前填。从前往后会覆盖 nums1 还没处理的元素。nums1 剩余不用拷（本来就在正确位置），只有 nums2 剩余要拷。

27. 移除元素

原地移除数组中值为 val 的元素，返回新长度。

思路脉络：快慢指针。slow 指向下一个保留元素该放的位置，fast 扫描全数组。遇 nums[fast] != val 就赋值给 nums[slow] 并 slow++，等于 val 就跳过。和热题 100 的移动零完全同构。

class Solution {
    public int removeElement(int[] nums, int val) {
        int slow = 0;
        for (int fast = 0; fast < nums.length; fast++) {
            if (nums[fast] != val) nums[slow++] = nums[fast];
        }
        return slow;
    }
}

[!info] 复杂度
时间 O(n)，空间 O(1)。

[!tip] 套路
快慢指针"原地筛选"：slow 永远指向下一个符合条件元素的落脚点。同款的还有删除有序数组重复项、移动零。

26. 删除有序数组中的重复项

有序数组原地去重，每个元素只留一个，返回新长度。

思路脉络：有序数组重复元素相邻。快慢指针：slow 指向最后一个不重复元素，fast 扫描。nums[fast] != nums[slow] 就 slow++ 并赋值。

class Solution {
    public int removeDuplicates(int[] nums) {
        if (nums.length == 0) return 0;
        int slow = 0;
        for (int fast = 1; fast < nums.length; fast++) {
            if (nums[fast] != nums[slow]) nums[++slow] = nums[fast];
        }
        return slow + 1;
    }
}

[!info] 复杂度
时间 O(n)，空间 O(1)。

[!warning] 易错点
slow 从 0 开始，返回 slow + 1（长度）。比较 nums[fast] != nums[slow]，不是 nums[fast] != nums[fast-1]——前者更简洁，因为 slow 永远是最后一个保留元素。

80. 删除有序数组中的重复项 II

有序数组，每个元素最多留两个，返回新长度。

思路脉络：和上一题的区别是允许重复两次。关键洞察：slow 位置要保留 nums[fast] 的条件是 slow < 2 || nums[fast] != nums[slow-2]。slow-2 是"如果保留这个，会不会变成第三个"。前两个位置直接保留，从第三个起要比对倒数第二个。

class Solution {
    public int removeDuplicates(int[] nums) {
        int slow = 0;
        for (int fast = 0; fast < nums.length; fast++) {
            if (slow < 2 || nums[fast] != nums[slow - 2]) nums[slow++] = nums[fast];
        }
        return slow;
    }
}

[!info] 复杂度
时间 O(n)，空间 O(1)。

[!warning] 易错点
判断条件 nums[fast] != nums[slow-2]（看倒数第二个），不是 nums[slow-1]。slow < 2 保证前两个位置直接放，不用比。这题推广到"最多留 k 个"就把 2 换成 k。

169. 多数元素

数组中出现超过 ⌊n/2⌋ 次的元素，保证存在。

思路脉络：摩尔投票。想象两军对战，同阵营 count+1、异阵营 count-1，归零换候选。多数派超半数，抵消所有少数派后仍有盈余。和热题 100 相同。

class Solution {
    public int majorityElement(int[] nums) {
        int cand = 0, cnt = 0;
        for (int n : nums) {
            if (cnt == 0) { cand = n; cnt = 1; }
            else if (n == cand) cnt++;
            else cnt--;
        }
        return cand;
    }
}

[!info] 复杂度
时间 O(n)，空间 O(1)。

[!warning] 易错点
摩尔投票只在"保证有多数元素"时直接返回候选。不保证时需二次遍历验证计数。

189. 轮转数组

数组右轮转 k 步，原地。

思路脉络：三次反转。整体反转 → 反转前 k 个 → 反转后 n-k 个，等价于右轮转 k。先 k %= n。和热题 100 相同。

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);
    }
    void reverse(int[] a, int l, int r) {
        while (l < r) { int t = a[l]; a[l] = a[r]; a[r] = t; l++; r--; }
    }
}

[!info] 复杂度
时间 O(n)，空间 O(1)。

[!warning] 易错点
忘 k %= n 会越界。k=0 时反转 0 个元素是空操作，安全。

122. 买卖股票的最佳时机 II

无限次买卖，求最大利润。

思路脉络：贪心。只要今天比昨天贵就累加差值。所有上升段的和就是最大利润。为什么对？因为"今天卖明天买"和"持有不卖"等价，拆开统计上升段更简单。

class Solution {
    public int maxProfit(int[] prices) {
        int ans = 0;
        for (int i = 1; i < prices.length; i++) {
            if (prices[i] > prices[i - 1]) ans += prices[i] - prices[i - 1];
        }
        return ans;
    }
}

[!info] 复杂度
时间 O(n)，空间 O(1)。

[!tip] 辨析
一次买卖(121)用"维护最小值"；无限次买卖(本题)用"累加所有上升段"；最多 k 次(188)才需 DP。难度递增。

274. H 指数

学者有 h 篇论文被引至少 h 次，求最大 h。

思路脉络：排序后从高引到低引遍历，h 是"至少有 h 篇被引 ≥ h 次"。排序后第 i 篇（从0起）引文 citations[i]，若 citations[i] >= n-i 则至少有 n-i 篇 ≥ 它，h 候选是 n-i。从后往前找第一个满足的，或正向遍历取 min(citations[i], n-i) 的最大值。

class Solution {
    public int hIndex(int[] citations) {
        Arrays.sort(citations);
        int h = 0, n = citations.length;
        for (int i = 0; i < n; i++) {
            h = Math.max(h, Math.min(citations[i], n - i));
        }
        return h;
    }
}

[!info] 复杂度
时间 O(n log n)，空间 O(1)。

[!tip] 进阶
计数排序可 O(n)：用 cnt[i] 记引文恰好 i 的篇数，超过 n 的计入 cnt[n]，从后往前累加。

380. O(1) 时间插入、删除和获取随机元素

设计 insert/remove/getRandom 全 O(1) 的数据结构。

思路脉络：ArrayList 支持下标随机访问 O(1) 但按值删 O(n)；HashSet 插删 O(1) 但无法随机访问。两者结合：List 存值、Map 存值→下标。删除时把待删元素和末尾元素交换再删末尾，O(1)。

class RandomizedSet {
    List<Integer> vals = new ArrayList<>();
    Map<Integer, Integer> idx = new HashMap<>();
    Random rand = new Random();

    public boolean insert(int val) {
        if (idx.containsKey(val)) return false;
        idx.put(val, vals.size());
        vals.add(val);
        return true;
    }
    public boolean remove(int val) {
        if (!idx.containsKey(val)) return false;
        int i = idx.get(val), last = vals.get(vals.size() - 1);
        vals.set(i, last); idx.put(last, i);   // 末尾填到待删位
        vals.remove(vals.size() - 1); idx.remove(val);
        return true;
    }
    public int getRandom() { return vals.get(rand.nextInt(vals.size())); }
}

[!info] 复杂度
三操作均 O(1)。

[!warning] 易错点
删除时必须先把 last 填到位置 i 再删末尾。若 i 本来就是末尾，交换逻辑也对（自己换自己），但 idx.remove(val) 要在 idx.put(last,i) 之后，否则 last==val 时会先把 key 删了。

134. 加油站

环形路上 n 个加油站，gas[i] 可加、cost[i] 耗，求能跑完一圈的起点下标，保证唯一。

思路脉络：总油量 >= 总耗量则一定有解（题目保证唯一）。关键是找起点：从 0 开始累计 gas-cost，一旦累和 < 0，说明 0..i 这段都不能作起点（油不够撑到 i），从 i+1 重新开始。最后看总剩油 >= 0 则返回记录的起点。

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int total = 0, tank = 0, start = 0;
        for (int i = 0; i < gas.length; i++) {
            int diff = gas[i] - cost[i];
            total += diff; tank += diff;
            if (tank < 0) { start = i + 1; tank = 0; } // 当前段作起点不行，重置
        }
        return total >= 0 ? start : -1;
    }
}

[!info] 复杂度
时间 O(n)，空间 O(1)。

[!warning] 易错点
"一旦 tank < 0 就从 i+1 重起"的正确性：若 0..i 段从任一 j 出发，走到 i 时累和必 < 0（因为从 0 出发累到 j 是正的，从 j 出发少带这部分正油，更早见底）。所以整段都淘汰。

135. 分发糖果

n 个孩子 rating 不同，相邻中 rating 高的糖果更多，求最少糖果总数。

思路脉络：每人至少 1 颗。两次遍历：从左扫保证比左邻 rating 高的多一颗；从右扫保证比右邻高的多一颗，取两次的 max。两次取 max 同时满足左右约束。

class Solution {
    public int candy(int[] ratings) {
        int n = ratings.length;
        int[] candies = new int[n];
        Arrays.fill(candies, 1);
        for (int i = 1; i < n; i++)           // 比左邻高则 +1
            if (ratings[i] > ratings[i - 1]) candies[i] = candies[i - 1] + 1;
        for (int i = n - 2; i >= 0; i--)      // 比右邻高则 max(+1)
            if (ratings[i] > ratings[i + 1]) candies[i] = Math.max(candies[i], candies[i + 1] + 1);
        int sum = 0;
        for (int c : candies) sum += c;
        return sum;
    }
}

[!info] 复杂度
时间 O(n)，空间 O(n)。

[!warning] 易错点
从右扫时必须取 max，不能直接 = candies[i+1]+1——否则会破坏从左扫建立的左约束。比如 [1,2,2,1]，从右扫到 index1 时若直接覆盖会丢掉左扫的值。

42. 接雨水

柱状图接雨水，求能接住的水量。

思路脉络：每列水量 = min(leftMax, rightMax) - height[i]。双指针 O(1) 空间：哪边矮处理哪边，瓶颈在矮侧 max。和热题 100 相同。

class Solution {
    public int trap(int[] height) {
        int l = 0, r = height.length - 1, leftMax = 0, rightMax = 0, ans = 0;
        while (l < r) {
            if (height[l] < height[r]) {
                if (height[l] >= leftMax) leftMax = height[l];
                else ans += leftMax - height[l];
                l++;
            } else {
                if (height[r] >= rightMax) rightMax = height[r];
                else ans += rightMax - height[r];
                r--;
            }
        }
        return ans;
    }
}

[!info] 复杂度
时间 O(n)，空间 O(1)。

[!tip] 关联
这题在热题 100 也选了。双指针 O(1) 空间是难点，DP 预处理两个数组是基础版。

13. 罗马数字转整数

罗马数字字符串转整数。

思路脉络：规则是小数在大数左边是减、右边是加。遍历时若当前 < 下一个就减当前，否则加当前。

class Solution {
    public int romanToInt(String s) {
        int[] v = new int[s.length()];
        for (int i = 0; i < s.length(); i++) v[i] = val(s.charAt(i));
        int ans = 0;
        for (int i = 0; i < v.length; i++) {
            if (i + 1 < v.length && v[i] < v[i + 1]) ans -= v[i];
            else ans += v[i];
        }
        return ans;
    }
    int val(char c) {
        return switch (c) {
            case 'I' -> 1; case 'V' -> 5; case 'X' -> 10; case 'L' -> 50;
            case 'C' -> 100; case 'D' -> 500; case 'M' -> 1000;
            default -> 0;
        };
    }
}

[!info] 复杂度
时间 O(n)，空间 O(n)。

[!warning] 易错点
只比相邻一个。IV=4、IX=9，但 IIX 不是合法写法（8 写 VIII）。判断 v[i] < v[i+1] 就减，不用管更远的。

12. 整数转罗马数字

整数转罗马数字，范围 1~3999。

思路脉络：罗马数字是"贪心"——从大到小枚举符号，能减就减。把 13 个值-符号对（含 900=CM、400=CD、4=IV 这种减法组合）按从大到小排列，每次减最大的可行值。

class Solution {
    public String intToRoman(int num) {
        int[] vals = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
        String[] syms = {"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < vals.length; i++) {
            while (num >= vals[i]) { sb.append(syms[i]); num -= vals[i]; }
        }
        return sb.toString();
    }
}

[!info] 复杂度
时间 O(1)（符号数固定），空间 O(1)。

[!tip] 套路
整数转"贪心符号"通用模板：值-符号对从大到小，能减就减。同样适合找零钱问题。

151. 反转字符串中的单词

the sky is blue → blue is sky the，单词间单空格，去首尾空格。

思路脉络：Java 直接 split("\\s+") 拆词，逆序拼。或原地双端：整体反转 → 每词反转 → 去多余空格。这里用 API 法最简洁。

class Solution {
    public String reverseWords(String s) {
        String[] words = s.trim().split("\\s+");
        StringBuilder sb = new StringBuilder();
        for (int i = words.length - 1; i >= 0; i--) {
            sb.append(words[i]);
            if (i > 0) sb.append(" ");
        }
        return sb.toString();
    }
}

[!info] 复杂度
时间 O(n)，空间 O(n)。

[!warning] 易错点
split("\\s+") 连续空格会产生空前缀（如 " a" 拆成 ["", "a"]），所以先 trim()。或用 split(" +") 配合 trim。

6. Z 字形变换

字符串按 Z 字形竖向排列，再逐行读取。

思路脉络：不必真画矩阵。用 StringBuilder[numRows] 模拟逐字符下填，到顶或底转向。方向变量 goingDown 控制指针上下移。

class Solution {
    public String convert(String s, int numRows) {
        if (numRows == 1) return s;
        StringBuilder[] rows = new StringBuilder[numRows];
        for (int i = 0; i < numRows; i++) rows[i] = new StringBuilder();
        int cur = 0, dir = 1;
        for (char c : s.toCharArray()) {
            rows[cur].append(c);
            if (cur == 0) dir = 1;
            else if (cur == numRows - 1) dir = -1;
            cur += dir;
        }
        StringBuilder ans = new StringBuilder();
        for (StringBuilder r : rows) ans.append(r);
        return ans.toString();
    }
}

[!info] 复杂度
时间 O(n)，空间 O(n)。

[!warning] 易错点
numRows == 1 时直接返回原串，否则 cur += dir 会越界（numRows-1 = 0，dir 一直在 1/-1 间跳但 cur 不动，但循环里 cur == 0 和 cur == numRows-1 同时成立会反复改 dir，实际 cur 始终 0，能跑但浪费。显式 return 更稳）。

28. 找出字符串中第一个匹配项的下标

实现 indexOf，返回 needle 在 haystack 中首次出现下标，没有返回 -1。

思路脉络：朴素匹配两层循环 O(nm)。KMP 能 O(n+m) 但实现长。面试若不要求 KMP，朴素法够用且不易错。这里给朴素法。

class Solution {
    public int strStr(String haystack, String needle) {
        int n = haystack.length(), m = needle.length();
        for (int i = 0; i <= n - m; i++) {
            int j = 0;
            for (; j < m && haystack.charAt(i + j) == needle.charAt(j); j++);
            if (j == m) return i;
        }
        return -1;
    }
}

[!info] 复杂度
时间 O(nm)（朴素），空间 O(1)。

[!tip] 进阶
KMP 用 next 数组预处理 needle 的"最长相同前后缀"，失配时跳过已匹配部分，O(n+m)。适合大文本匹配，面试会追。

68. 文本左右对齐

单词数组按每行 maxWidth 字符左右对齐排版，末行左对齐。

思路脉络：贪心每行尽可能多放词。先确定一行放几个词（总长 + 至少单空格 ≤ maxWidth），再分配空格：行内词间空格尽量均匀，多出的左优先；末行左对齐补尾空格。

class Solution {
    public List<String> fullJustify(String[] words, int maxWidth) {
        List<String> res = new ArrayList<>();
        int i = 0, n = words.length;
        while (i < n) {
            int lineLen = words[i].length(), j = i + 1;
            while (j < n && lineLen + 1 + words[j].length() <= maxWidth) {
                lineLen += 1 + words[j++].length();      // j 是下一行起点
            }
            int gap = j - i - 1;                          // 本行词间距数
            StringBuilder sb = new StringBuilder(words[i]);
            if (j == n || gap == 0) {                     // 末行 或 单词一行
                for (int k = i + 1; k < j; k++) sb.append(' ').append(words[k]);
                while (sb.length() < maxWidth) sb.append(' ');
            } else {
                int spaces = (maxWidth - lineLen + gap) / (gap); // 每个 gap 的基础空格
                int extra = (maxWidth - lineLen + gap) % gap;     // 多出的分给左边
                for (int k = i + 1; k < j; k++) {
                    int sp = spaces + (k - i <= extra ? 1 : 0);
                    sb.append(" ".repeat(sp)).append(words[k]);
                }
            }
            res.add(sb.toString());
            i = j;
        }
        return res;
    }
}

[!info] 复杂度
时间 O(总字符数)，空间 O(maxWidth)。

[!warning] 易错点
空格分配公式：lineLen 是"词长+gap个单空格"，所以 maxWidth - lineLen 是还需补的空格，分到 gap 个间距里，每个间距 spaces + 可能的 extra。lineLen + gap 是因为 lineLen 已含 gap 个单空格，再补的总空格 = maxWidth - (lineLen - gap) = maxWidth - lineLen + gap。

2. 双指针

双指针的核心是用两个指针协同，把两层循环压成一层。这里聚焦三类：回文对撞、子序列匹配、有序数组两数。

125. 验证回文串

字符串只看字母数字、忽略大小写，判断是否回文。

思路脉络：对撞指针，一左一右向中间走，跳过非字母数字，比较小写化后的字符。任一对不等就 false。

class Solution {
    public boolean isPalindrome(String s) {
        int l = 0, r = s.length() - 1;
        while (l < r) {
            while (l < r && !Character.isLetterOrDigit(s.charAt(l))) l++;
            while (l < r && !Character.isLetterOrDigit(s.charAt(r))) r--;
            if (Character.toLowerCase(s.charAt(l++)) != Character.toLowerCase(s.charAt(r--))) return false;
        }
        return true;
    }
}

[!info] 复杂度
时间 O(n)，空间 O(1)。

[!warning] 易错点

跳过非字母数字时也要带 l < r 条件，否则可能越界。l++/r-- 放在比较时一起做，别漏。

392. 判断子序列

s 是否是 t 的子序列（按顺序出现，可不连续）。

思路脉络：双指针各一个，i 走 s、j 走 t。s[i]==t[j] 则 i++，j 总是 ++。i 走到 s.length() 即是子序列。

class Solution {
    public boolean isSubsequence(String s, String t) {
        int i = 0;
        for (int j = 0; j < t.length() && i < s.length(); j++) {
            if (s.charAt(i) == t.charAt(j)) i++;
        }
        return i == s.length();
    }
}

[!info] 复杂度
时间 O(n+m)，空间 O(1)。

[!tip] 进阶

若 t 固定、s 有大量查询，预处理 t 为"每个位置之后各字母最早出现位置"的 next[i][26] 表，每个 s 查询 O(|s|)。

167. 两数之和 II - 输入有序数组

有序数组找和为 target 的两数下标（1起），恰好一个解。

思路脉络：有序 → 对撞双指针。l=0, r=n-1，和小于 target 则 l++（要变大），和大于则 r--（要变小）。不像无序要哈希。

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int l = 0, r = numbers.length - 1;
        while (l < r) {
            int sum = numbers[l] + numbers[r];
            if (sum == target) return new int[]{l + 1, r + 1};
            else if (sum < target) l++;
            else r--;
        }
        return new int[0];
    }
}

[!info] 复杂度
时间 O(n)，空间 O(1)。

[!warning] 易错点

题目要求下标从 1 起，返回 l+1, r+1。有序是关键——无序的两数之和用哈希，有序的用对撞双指针省掉哈希空间。

15. 三数之和

找所有和为 0 的不重复三元组。

思路脉络：排序 + 固定一个 + 对撞双指针。固定 i，在 i+1..n-1 用双指针找 nums[l]+nums[r] = -nums[i]。难点在去重：i/l/r 三处都要跳过相邻重复。和热题 100 相同。

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) l++;
                else if (sum > 0) r--;
                else {
                    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--;
                }
            }
        }
        return res;
    }
}

[!info] 复杂度
时间 O(n²)，空间 O(log n)（排序栈）。

[!warning] 易错点

去重用 nums[i] == nums[i-1]（与前一个比），保留第一个、跳后续重复。nums[i] == nums[i+1] 会漏掉 -1,-1,2 中第一个 -1。

3. 滑动窗口

滑动窗口维护一个满足约束的动态区间。变长窗口（r 扩到违反、l 缩到合法）求最长/最短，定长窗口整体平移。核心是用一个"状态量"替代每次重算。

209. 长度最小的子数组

正整数数组找和 ≥ target 的最短连续子数组长度。

思路脉络：正整数 → 窗口和单调。变长窗口：r 扩加入 sum，一旦 sum ≥ target 就缩 l（边缩边更新最短长度、减 sum）。正整数保证缩 l 和一定减，不会错过更优解。

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int l = 0, sum = 0, ans = Integer.MAX_VALUE;
        for (int r = 0; r < nums.length; r++) {
            sum += nums[r];
            while (sum >= target) {
                ans = Math.min(ans, r - l + 1);
                sum -= nums[l++];
            }
        }
        return ans == Integer.MAX_VALUE ? 0 : ans;
    }
}

[!info] 复杂度
时间 O(n)，空间 O(1)。

[!warning] 易错点

必须正整数——含负数时窗口和不再单调，这法失效，得用前缀和+单调队列。本题保证正整数。

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

找不含重复字符的最长子串长度。

思路脉络：哈希记字符最近下标，r 遇重复时 l 跳到 max(l, map[c]+1)（不能后退）。和热题 100 相同。

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;
    }
}

[!info] 复杂度
时间 O(n)，空间 O(字符集)。

[!warning] 易错点

Math.max 保证 l 只前进。abba 处理第二个 b 时 l 跳到 2，处理第二个 a 时 map.get('a')+1=1 不能让 l 退回。

30. 串联所有单词的子串

words 全部单词（同长）拼接的任意排列，在 s 中所有出现起点。

思路脉络：单词定长 w，把 s 按 w 切成"词序列"。窗口大小固定为 words.length，对每个起始偏移 0..w-1 各做一次定长滑动窗口 + 计数匹配。本质是"定长窗口 + 状态计数"。

class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> res = new ArrayList<>();
        int n = s.length(), m = words.length, w = words[0].length();
        Map<String, Integer> need = new HashMap<>();
        for (String wd : words) need.merge(wd, 1, Integer::sum);

        for (int off = 0; off < w; off++) {
            int l = off, count = 0;
            Map<String, Integer> win = new HashMap<>();
            for (int r = off; r + w <= n; r += w) {
                String word = s.substring(r, r + w);
                if (!need.containsKey(word)) { win.clear(); count = 0; l = r + w; continue; }
                win.merge(word, 1, Integer::sum);
                count++;
                while (win.get(word) > need.get(word)) {
                    String out = s.substring(l, l + w);
                    win.merge(out, -1, Integer::sum);
                    count--; l += w;
                }
                if (count == m) res.add(l);
            }
        }
        return res;
    }
}

[!info] 复杂度
时间 O(n·w)，空间 O(m·w)。

[!warning] 易错点

起始偏移 0..w-1 各做一遍，不能只从 0 开始——词边界不同会漏解。遇到不在词表的词要重置窗口（l 跳过它）。

76. 最小覆盖子串

s 中覆盖 t 所有字符的最短子串。

思路脉络：变长窗口。r 扩到"刚好覆盖 t"，l 缩到"刚好不覆盖"，临界点更新最短。valid 记录窗口里满足需求计数的字符种类数。和热题 100 相同。

class Solution {
    public String minWindow(String s, String t) {
        Map<Character, Integer> need = new HashMap<>();
        for (char c : t.toCharArray()) need.merge(c, 1, Integer::sum);
        Map<Character, Integer> win = new HashMap<>();
        int l = 0, valid = 0, needCnt = need.size(), start = 0, minLen = Integer.MAX_VALUE;
        for (int r = 0; r < s.length(); r++) {
            char c = s.charAt(r);
            if (need.containsKey(c)) {
                win.merge(c, 1, Integer::sum);
                if (win.get(c).equals(need.get(c))) valid++;
            }
            while (valid == needCnt) {
                if (r - l + 1 < minLen) { minLen = r - l + 1; start = l; }
                char d = s.charAt(l++);
                if (need.containsKey(d)) {
                    if (win.get(d).equals(need.get(d))) valid--;
                    win.merge(d, -1, Integer::sum);
                }
            }
        }
        return minLen == Integer.MAX_VALUE ? "" : s.substring(start, start + minLen);
    }
}

[!info] 复杂度
时间 O(n)，空间 O(字符集)。

[!warning] 易错点

valid 只在"刚好达到需求"时 ++、"刚好跌破"时 --。needCnt 用去重后的种类数 need.size()，不是 t.length()。

4. 矩阵

矩阵题集中在原地标记、边界模拟、坐标变换。关键是利用"下标本身承载信息"和"锚点选位简化判断"。

36. 有效的数独

9×9 数独部分填好，判断当前状态是否合法（每行/每列/每 3×3 宫不重复 1-9）。

思路脉络：一次遍历，用三个集合数组记录每行/每列/每宫已见数字。宫号 = (i/3)*3 + j/3。遇已见数字即非法。

class Solution {
    public boolean isValidSudoku(char[][] board) {
        boolean[][] row = new boolean[9][9], col = new boolean[9][9], box = new boolean[9][9];
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                char c = board[i][j];
                if (c == '.') continue;
                int d = c - '1', b = (i / 3) * 3 + j / 3;
                if (row[i][d] || col[j][d] || box[b][d]) return false;
                row[i][d] = col[j][d] = box[b][d] = true;
            }
        }
        return true;
    }
}

[!info] 复杂度
时间 O(1)（固定 81 格），空间 O(1)。

[!tip] 套路

"校验重复"通用：用 boolean 数组记已见。宫号公式 (i/3)*3 + j/3 把 3×3 子块映射到 0-8，记住。

73. 矩阵置零

若 matrix[i][j]==0 把它所在行列全置零，原地。

思路脉络：用第一行第一列自身记录"哪些行列要置零"，加两个布尔变量单独标记首行首列。先标记 → 清内部 → 最后清首行首列。和热题 100 相同。

class Solution {
    public void setZeroes(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        boolean firstRow = false, firstCol = false;
        for (int j = 0; j < n; j++) if (matrix[0][j] == 0) firstRow = true;
        for (int i = 0; i < m; i++) if (matrix[i][0] == 0) firstCol = 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 (firstRow) for (int j = 0; j < n; j++) matrix[0][j] = 0;
        if (firstCol) for (int i = 0; i < m; i++) matrix[i][0] = 0;
    }
}

[!info] 复杂度
时间 O(mn)，空间 O(1)。

[!warning] 易错点

必须最后清首行首列，否则先清了会用被污染的标记清内部。

289. 生命游戏

4 条规则演化细胞生死，原地更新矩阵（需同时更新所以不能边算边改）。

思路脉络：原地难点是"同时更新"——直接改 0/1 会污染后续判断。用复合状态：活→死记 -1、死→活记 2，统计活邻居时把 -1 也算活。最后扫一遍把 -1→0、2→1。

class Solution {
    public void gameOfLife(int[][] board) {
        int m = board.length, n = board[0].length;
        int[] dx = {-1,-1,-1,0,0,1,1,1}, dy = {-1,0,1,-1,1,-1,0,1};
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int live = 0;
                for (int k = 0; k < 8; k++) {
                    int x = i + dx[k], y = j + dy[k];
                    if (x >= 0 && x < m && y >= 0 && y < n && Math.abs(board[x][y]) == 1) live++;
                }
                if (board[i][j] == 1 && (live < 2 || live > 3)) board[i][j] = -1;
                else if (board[i][j] == 0 && live == 3) board[i][j] = 2;
            }
        }
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                board[i][j] = board[i][j] > 0 ? 1 : 0;
    }
}

[!info] 复杂度
时间 O(mn)，空间 O(1)。

[!tip] 套路

"同时更新"矩阵题通用技巧：用复合状态值（原值+新值编码），统计时 abs() 还原原值。比开额外数组省空间。

5. 哈希表

哈希的本质是建立逆向映射，把"查找"从 O(n) 降到 O(1)。这里聚焦三类：计数比较、模式映射、存在性查询。

205. 同构字符串

s 和 t 能否双射——s 的每个字符映射到 t 对应字符，且映射一一对应。

思路脉络：双射要求"同一字符映射恒定"且"无两个字符映射到同一目标"。两个 map 互查：s2t 记 s→t、t2s 记 t→s。遇不一致即 false。

class Solution {
    public boolean isIsomorphic(String s, String t) {
        Map<Character, Character> s2t = new HashMap<>(), t2s = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            char a = s.charAt(i), b = t.charAt(i);
            if (s2t.containsKey(a) && s2t.get(a) != b) return false;
            if (t2s.containsKey(b) && t2s.get(b) != a) return false;
            s2t.put(a, b); t2s.put(b, a);
        }
        return true;
    }
}

[!info] 复杂度
时间 O(n)，空间 O(字符集)。

[!warning] 易错点

必须两个 map 双向校验。单 map 只保证"s→t 恒定"，不保证"不同 s 不映射到同一 t"（如 ab→aa 单 map 会误判 true）。

290. 单词规律

pattern 字母和 s 单词之间是否满足双射规律。

思路脉络：和同构字符串同构——把"字母↔单词"看成双射。两个 map 互查，注意拆词。

class Solution {
    public boolean wordPattern(String pattern, String s) {
        String[] words = s.split(" ");
        if (words.length != pattern.length()) return false;
        Map<Character, String> p2w = new HashMap<>();
        Map<String, Character> w2p = new HashMap<>();
        for (int i = 0; i < pattern.length(); i++) {
            char c = pattern.charAt(i); String w = words[i];
            if (p2w.containsKey(c) && !p2w.get(c).equals(w)) return false;
            if (w2p.containsKey(w) && w2p.get(w) != c) return false;
            p2w.put(c, w); w2p.put(w, c);
        }
        return true;
    }
}

[!info] 复杂度
时间 O(n)，空间 O(n)。

[!warning] 易错点

长度不等先 return。字符串比较用 .equals()，字符可用 !=（基本类型）。w2p.get(w) != c 是 Character 拆箱成 char 比较，安全。

1. 两数之和

数组找和为 target 的两个元素下标。

思路脉络：边查边存。固定 num 要找的是 target-num，哈希 O(1) 查。先查再存避免用到自己。和热题 100 相同。

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

[!info] 复杂度
时间 O(n)，空间 O(n)。

[!warning] 易错点

先查再存，否则 [3,3] target=6 会误用自己下标。

202. 快乐数

反复把数替换成各位平方和，最终为 1 是快乐数，可能进入循环。

思路脉络：循环判定——用集合记出现过的数，遇重复说明进入循环非快乐数，遇 1 是快乐数。或者快慢指针（类似环形链表，但这里是数值链）。

class Solution {
    public boolean isHappy(int n) {
        Set<Integer> seen = new HashSet<>();
        while (n != 1 && !seen.contains(n)) {
            seen.add(n);
            n = next(n);
        }
        return n == 1;
    }
    int next(int n) {
        int sum = 0;
        while (n > 0) { int d = n % 10; sum += d * d; n /= 10; }
        return sum;
    }
}

[!info] 复杂度
时间 O(log n)，空间 O(log n)。

[!tip] 关联

快慢指针法 O(1) 空间：把"数→平方和"看成链表，循环即环，复用 [[#142. 环形链表 II]] 的快慢找环思路。

219. 存在重复元素 II

数组里是否存在 nums[i] == nums[j] 且 |i-j| <= k。

思路脉络：哈希记每个值最近下标。遇同值时比下标差，≤ k 即 true，否则更新最近下标（更近的下标更可能满足后续，旧的丢弃）。

class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        Map<Integer, Integer> idx = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            Integer prev = idx.put(nums[i], i);
            if (prev != null && i - prev <= k) return true;
        }
        return false;
    }
}

[!info] 复杂度
时间 O(n)，空间 O(n)。

[!tip] 套路

map.put 返回旧值，巧妙用它一次性完成"查旧值+更新"。比 containsKey + get 更简洁。

128. 最长连续序列

未排序数组找最长连续整数序列长度，要求 O(n)。

思路脉络：所有数放 set，只从"序列起点"（x-1 不在 set）向上扩展。x-1 在则跳过避免 O(n²)。和热题 100 相同。

class Solution {
    public int longestConsecutive(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int n : nums) set.add(n);
        int best = 0;
        for (int x : set) {
            if (set.contains(x - 1)) continue;
            int cur = x, len = 1;
            while (set.contains(cur + 1)) { cur++; len++; }
            best = Math.max(best, len);
        }
        return best;
    }
}

[!info] 复杂度
时间 O(n)，空间 O(n)。

[!warning] 易错点

漏 x-1 判断会退化 O(n²)。"只从起点扩展"是 O(n) 的灵魂。

6. 区间

区间题的核心是排序 + 一次遍历处理重叠。按起点排序后，重叠区间相邻，用一个"当前合并区间"吸收后续重叠即可。

228. 汇总区间

有序无重复整数数组，把连续段汇总成 a->b、单点列自身。

思路脉络：一次遍历，l 标记段起点，遇到 nums[i] != nums[i-1]+1（断开）就输出 [l, i-1] 段并重置 l=i。

class Solution {
    public List<String> summaryRanges(int[] nums) {
        List<String> res = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            int l = i;
            while (i + 1 < nums.length && nums[i + 1] == nums[i] + 1) i++;
            if (l == i) res.add(String.valueOf(nums[l]));
            else res.add(nums[l] + "->" + nums[i]);
        }
        return res;
    }
}

[!info] 复杂度
时间 O(n)，空间 O(1)。

[!warning] 易错点

单点（l==i）单独输出数字，连续段输出 a->b。while 推进 i，外层 for 的 i++ 会跳到下一段起点。

56. 合并区间

合并所有重叠区间。

思路脉络：按起点排序，遍历时若当前区间起点 ≤ 上一已合并区间终点则合并（终点取 max），否则新开。和热题 100 相同。

class Solution {
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
        List<int[]> res = new ArrayList<>();
        for (int[] iv : intervals) {
            if (!res.isEmpty() && iv[0] <= res.get(res.size() - 1)[1]) {
                res.get(res.size() - 1)[1] = Math.max(res.get(res.size() - 1)[1], iv[1]);
            } else res.add(iv);
        }
        return res.toArray(new int[0][]);
    }
}

[!info] 复杂度
时间 O(n log n)，空间 O(排序栈)。

[!warning] 易错点

合并时终点取 max，不能直接覆盖。[1,5] 与 [2,3] 覆盖成 [1,3] 就错了。

452. 用最少数量的箭引爆气球

一组气球用区间表示，一支箭从 x 射穿所有覆盖 x 的气球，求最少箭数。

思路脉络：按终点排序贪心。从左到右，每支箭射在"当前组的右边界最小值"，这样能射穿最多气球。遇到起点 > 当前右边界就需新箭。

class Solution {
    public int findMinArrowShots(int[][] points) {
        if (points.length == 0) return 0;
        Arrays.sort(points, (a, b) -> Integer.compare(a[1], b[1]));
        int arrows = 1, end = points[0][1];
        for (int[] p : points) {
            if (p[0] > end) { arrows++; end = p[1]; }
        }
        return arrows;
    }
}

[!info] 复杂度
时间 O(n log n)，空间 O(排序栈)。

[!warning] 易错点

按终点排序（不是起点），箭射在终点能覆盖最多。比较用 Integer.compare 防 a[1]-b[1] 溢出（坐标可能 INT_MIN）。p[0] > end 严格大于才算不重叠（边界相切 p[0]==end 仍能一支箭射穿）。

7. 栈

栈处理"最近相关性"问题：括号匹配、路径简化、表达式求值。后进先出天然适合"配对/嵌套/撤销"结构。

71. 简化路径

Unix 路径转规范绝对路径（去 ./..、合并多余斜杠）。

思路脉络：按 / 拆段，遇 . 或空跳过，遇 .. 弹栈（回上级），遇普通名压栈。最后用 / 拼接，补前导 /。

class Solution {
    public String simplifyPath(String path) {
        Deque<String> st = new ArrayDeque<>();
        for (String p : path.split("/")) {
            if (p.equals("..") && !st.isEmpty()) st.pop();
            else if (!p.equals(".") && !p.equals("..") && !p.isEmpty()) st.push(p);
        }
        StringBuilder sb = new StringBuilder();
        while (!st.isEmpty()) sb.insert(0, "/" + st.pop());
        return sb.length() == 0 ? "/" : sb.toString();
    }
}

[!info] 复杂度
时间 O(n)，空间 O(n)。

[!warning] 易错点

.. 在栈空时（根目录）无效，不能弹。结果空返回 /（根）。split("/") 会产生空段，要跳过。

150. 逆波兰表达式求值

后缀表达式（token 数组）求值，+ - * /。

思路脉络：遇数字入栈，遇运算符弹两个（注意顺序：先弹的是右操作数）计算后入栈。除法用 truncate toward zero（Java / 默认就是）。

class Solution {
    public int evalRPN(String[] tokens) {
        Deque<Integer> st = new ArrayDeque<>();
        for (String t : tokens) {
            if (t.equals("+") || t.equals("-") || t.equals("*") || t.equals("/")) {
                int b = st.pop(), a = st.pop();
                st.push(t.equals("+") ? a + b : t.equals("-") ? a - b
                     : t.equals("*") ? a * b : a / b);
            } else st.push(Integer.parseInt(t));
        }
        return st.pop();
    }
}

[!info] 复杂度
时间 O(n)，空间 O(n)。

[!warning] 易错点

操作数顺序：先弹的是右操作数 b、后弹的是左操作数 a，a - b、a / b 顺序反了结果错。Java a/b 对负数是向 0 取整，符合题意。

224. 基本计算器

中缀表达式含 + - ( ) 和空格，求值。

思路脉络：用栈处理括号和符号。核心是维护"当前符号 sign"——遇 + sign=1、- sign=-1，数字按 sign*数字 累加。遇 ( 把当前结果和 sign 入栈、重置；遇 ) 弹栈合并。

class Solution {
    public int calculate(String s) {
        Deque<Integer> st = new ArrayDeque<>();
        int res = 0, sign = 1, num = 0;
        for (char c : s.toCharArray()) {
            if (Character.isDigit(c)) num = num * 10 + (c - '0');
            else if (c == '+') { res += sign * num; num = 0; sign = 1; }
            else if (c == '-') { res += sign * num; num = 0; sign = -1; }
            else if (c == '(') { st.push(res); st.push(sign); res = 0; sign = 1; }
            else if (c == ')') { res += sign * num; num = 0; res *= st.pop(); res += st.pop(); }
        }
        return res + sign * num;
    }
}

[!info] 复杂度
时间 O(n)，空间 O(n)。

[!warning] 易错点

最后 return res + sign*num 处理末尾未结算的数字。遇 ( 入栈顺序是 res 先、sign 后，遇 ) 弹出是 sign 先（乘）、res 后（加）——LIFO。num 用完后归零。

8. 链表

链表题通用心法：哨兵节点 dummy 统一头被改的情况、快慢指针 找中点/倒数/环、画图改指针 不靠脑内想象。

2. 两数相加

两个链表逆序存两个非负整数（头是低位），返回和的链表。

思路脉络：模拟加法，从低位（头）逐位相加维护进位。循环条件带 carry != 0 防漏最高位进位。

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0), cur = 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;
            cur.next = new ListNode(sum % 10);
            cur = cur.next;
        }
        return dummy.next;
    }
}

[!info] 复杂度
时间 O(max(m,n))，空间 O(max(m,n))。

92. 反转链表 II

反转链表 [left, right] 区间（1起），其余不变。

思路脉络：先定位 pre（left 前驱）。用头插法反转 [left, right]：每次把 cur 插到 pre 后面，tail（原 left）不断被往后推。dummy 处理 left=1。

class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        ListNode dummy = new ListNode(0, head), pre = dummy;
        for (int i = 1; i < left; i++) pre = pre.next;
        ListNode tail = pre.next, cur = tail.next;
        for (int i = left; i < right; i++) {
            ListNode next = cur.next;
            cur.next = pre.next; pre.next = cur;
            tail.next = next; cur = next;
        }
        return dummy.next;
    }
}

[!info] 复杂度
时间 O(n)，空间 O(1)。

[!warning] 易错点

头插法：cur 插到 pre 后，tail（原 left）始终是这段的尾，tail.next = next 维持它与右侧连接。

82. 删除排序链表中的重复元素 II

有序链表，删掉所有有重复的节点（重复的全删，不只留一个）。

思路脉络：dummy + pre。遇 pre.next.val == pre.next.next.val 则记下该值，pre.next 跳过所有等于该值的节点。没有重复则推进 pre。

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode dummy = new ListNode(0, head), pre = dummy;
        while (pre.next != null && pre.next.next != null) {
            if (pre.next.val == pre.next.next.val) {
                int dup = pre.next.val;
                while (pre.next != null && pre.next.val == dup) pre.next = pre.next.next;
            } else pre = pre.next;
        }
        return dummy.next;
    }
}

[!info] 复杂度
时间 O(n)，空间 O(1)。

[!warning] 易错点

和"保留一个"不同：这里重复的全删。pre.next 直接跳过所有重复值节点，不保留任何一个。

61. 旋转链表

链表右轮转 k 步。

思路脉络：右轮转 k = 把末尾 k 个挪到前面。数长度 n，k %= n。新尾是倒数第 k+1 个（走 n-k-1 步定位），断开，旧尾接旧头。

class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if (head == null) return null;
        ListNode tail = head; int n = 1;
        while (tail.next != null) { tail = tail.next; n++; }
        k %= n; if (k == 0) return head;
        ListNode newTail = head;
        for (int i = 0; i < n - k - 1; i++) newTail = newTail.next;
        ListNode newHead = newTail.next;
        newTail.next = null; tail.next = head;
        return newHead;
    }
}

[!info] 复杂度
时间 O(n)，空间 O(1)。

[!warning] 易错点

k %= n 防超长。k == 0 直接返回。新尾是倒数第 k+1 个，走 n-k-1 步定位。

86. 分隔链表

链表按值 x 分区，小于 x 在前、大于等于在后，保持各段原相对顺序。

思路脉络：两个 dummy 链表分别收集小段和大段，最后小段尾接大段头。复用原节点空间 O(1)。

class Solution {
    public ListNode partition(ListNode head, int x) {
        ListNode small = new ListNode(0), big = new ListNode(0);
        ListNode s = small, b = big;
        for (ListNode p = head; p != null; p = p.next) {
            if (p.val < x) { s.next = p; s = s.next; }
            else { b.next = p; b = b.next; }
        }
        b.next = null; s.next = big.next;
        return small.next;
    }
}

[!info] 复杂度
时间 O(n)，空间 O(1)。

[!warning] 易错点

b.next = null 必须断开，否则大段末尾可能还连着原链表后续节点成环。

146. LRU 缓存

get/put 均 O(1) 的 LRU 缓存，容量满淘汰最久未使用。

思路脉络：哈希存 key→节点 + 双向链表维护访问序（头最近、尾最久）。节点存 key 供淘汰时删哈希。

class LRUCache {
    class Node { int key, val; Node prev, next; Node(int k, int v){key=k;val=v;} }
    Map<Integer, Node> map = new HashMap<>();
    int cap; Node head = new Node(0,0), tail = new Node(0,0);
    public LRUCache(int capacity) { cap = capacity; head.next = tail; tail.prev = head; }
    public int get(int key) {
        if (!map.containsKey(key)) return -1;
        Node n = map.get(key); moveToHead(n); return n.val;
    }
    public void put(int key, int value) {
        if (map.containsKey(key)) { Node n = map.get(key); n.val = value; moveToHead(n); }
        else {
            Node n = new Node(key, value); map.put(key, n); addToHead(n);
            if (map.size() > cap) { Node last = tail.prev; removeNode(last); map.remove(last.key); }
        }
    }
    void addToHead(Node n) { n.next = head.next; head.next.prev = n; head.next = n; n.prev = head; }
    void removeNode(Node n) { n.prev.next = n.next; n.next.prev = n.prev; }
    void moveToHead(Node n) { removeNode(n); addToHead(n); }
}

[!info] 复杂度
get/put 均 O(1)。

[!warning] 易错点

节点必须存 key：淘汰尾节点时需要用它删哈希项。dummy 头尾让"头是最近、尾是最久"语义稳定。

9. 二叉树

树题的灵魂是递归三部曲：边界条件、单层逻辑（假设子树已正确）、返回值传递。还有两类遍历：DFS 递归求路径/祖先、BFS 层序按层处理。

100. 相同的树

两棵树是否结构和值都相同。

思路脉络：两指针同步递归。都 null 返回 true；一空一非空 false；值不等 false；都非空则递归比左右子。

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) return true;
        if (p == null || q == null) return false;
        return p.val == q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
}

[!info] 复杂度
时间 O(n)，空间 O(h)。

[!warning] 易错点

先判"双 null"再判"单 null"，顺序反了会漏判。这是所有"两树对比"题的标准开头。

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

给前序和中序，构造原树。

思路脉络：前序第一个是根。中序里根位置分左右子树。哈希 O(1) 定位根。前序用全局 i 顺序取根，先建左子再建右子（前序天然"根左右"）。

class Solution {
    int[] preorder; int i = 0;
    Map<Integer, Integer> idx = new HashMap<>();
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.preorder = preorder;
        for (int j = 0; j < inorder.length; j++) idx.put(inorder[j], j);
        return build(0, inorder.length - 1);
    }
    TreeNode build(int l, int r) {
        if (l > r) return null;
        int val = preorder[i++], m = idx.get(val);
        TreeNode root = new TreeNode(val);
        root.left = build(l, m - 1); root.right = build(m + 1, r);
        return root;
    }
}

[!info] 复杂度
时间 O(n)，空间 O(n)。

[!warning] 易错点

前序 i 全局递增，依赖"先建左子再建右子"的顺序，顺序反了 i 错位。

106. 从中序与后序遍历序列构造二叉树

给中序和后序，构造原树。

思路脉络：后序最后一个是根。中序定位根分左右。后序用全局 i 从后往前取根，先建右子再建左子（后序天然"左右根"，逆过来是"根右左"）。

class Solution {
    int[] postorder; int i;
    Map<Integer, Integer> idx = new HashMap<>();
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        this.postorder = postorder; this.i = postorder.length - 1;
        for (int j = 0; j < inorder.length; j++) idx.put(inorder[j], j);
        return build(0, inorder.length - 1);
    }
    TreeNode build(int l, int r) {
        if (l > r) return null;
        int val = postorder[i--], m = idx.get(val);
        TreeNode root = new TreeNode(val);
        root.right = build(m + 1, r); root.left = build(l, m - 1);   // 先右后左
        return root;
    }
}

[!info] 复杂度
时间 O(n)，空间 O(n)。

[!warning] 易错点

后序从后往前取根，必须先建右子再建左子（和 105 前序先左后右相反）。顺序反了 i 错位。

117. 填充每个节点的下一个右侧节点指针 II

每层节点用 next 串成链表，树非完美二叉（节点可能缺子）。

思路脉络：BFS 层序。每层开始记 size，逐个出队并把 next 指向队首（同层下一节点）。关键是 BFS 按层切分，同层内串 next。

class Solution {
    public Node connect(Node root) {
        if (root == null) return null;
        Queue<Node> q = new ArrayDeque<>(); q.offer(root);
        while (!q.isEmpty()) {
            int size = q.size();
            Node prev = null;
            for (int i = 0; i < size; i++) {
                Node n = q.poll();
                if (prev != null) prev.next = n;
                prev = n;
                if (n.left != null) q.offer(n.left);
                if (n.right != null) q.offer(n.right);
            }
        }
        return root;
    }
}

[!info] 复杂度
时间 O(n)，空间 O(n)。

[!tip] 进阶

O(1) 空间：利用上一层已串好的 next 链表遍历下一层，不用队列。但 BFS 法最直观，面试首选。

114. 二叉树展开为链表

按前序把树展开成右链（每节点只有右孩子）。

思路脉络：后序"右→左→中"配全局 prev。处理当前时左右子已展平，root.right = prev、root.left = null、prev = root。逆前序让链表从尾向头接。

class Solution {
    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;
    }
}

[!info] 复杂度
时间 O(n)，空间 O(h)。

[!warning] 易错点

必须先 flatten(right) 再 flatten(left)，模拟"前序的逆序"（右左中）。

112. 路径总和

判断是否有根到叶路径和等于 targetSum。

思路脉络：递归减值。到叶子时判剩余是否等于叶子值。空树直接 false（没有根到叶路径）。

class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) return false;
        if (root.left == null && root.right == null) return root.val == targetSum;
        return hasPathSum(root.left, targetSum - root.val) || hasPathSum(root.right, targetSum - root.val);
    }
}

[!info] 复杂度
时间 O(n)，空间 O(h)。

[!warning] 易错点

必须"根到叶"，叶子定义是左右都空。中间节点（只有一子）不算终止。空树返回 false。

129. 求根节点到叶节点数字之和

每条根到叶路径表示一个数字（如 1→2→3 = 123），求所有路径数字之和。

思路脉络：DFS 传"当前累计值" cur = cur*10 + node.val。到叶子时把 cur 加进总和。

class Solution {
    int sum = 0;
    public int sumNumbers(TreeNode root) {
        dfs(root, 0); return sum;
    }
    void dfs(TreeNode node, int cur) {
        if (node == null) return;
        cur = cur * 10 + node.val;
        if (node.left == null && node.right == null) sum += cur;
        dfs(node.left, cur); dfs(node.right, cur);
    }
}

[!info] 复杂度
时间 O(n)，空间 O(h)。

[!warning] 易错点

cur 是值传递，回溯天然（每层独立副本），不用显式撤销。叶子判断后才加 cur，中间节点不加。

124. 二叉树中的最大路径和

任意路径（可不经过根）的最大和。

思路脉络：gain(root) 返回从 root 向下单边最大和（负贡献截断为 0）。每节点处以它为最高点的路径和 = 左贡献 + 右贡献 + 自身，更新答案。返回给上层只能单边。和热题 100 相同。

class Solution {
    int ans = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) { gain(root); return ans; }
    int gain(TreeNode root) {
        if (root == null) return 0;
        int l = Math.max(0, gain(root.left)), r = Math.max(0, gain(root.right));
        ans = Math.max(ans, l + r + root.val);
        return Math.max(l, r) + root.val;
    }
}

[!info] 复杂度
时间 O(n)，空间 O(h)。

[!warning] 易错点

ans 用"两边和"（完整路径可分叉在当前），return 用"单边"（向上不能分叉）。负贡献 Math.max(0, ...) 截断。

173. 二叉搜索树迭代器

设计按升序遍历 BST 的迭代器，next/hasNext 均 O(1) 均摊。

思路脉络：用栈模拟中序。构造时一路向左压栈。next 弹栈（当前最小）、把右子树一路向左压栈。均摊 O(1) 因为每节点入栈出栈各一次。

class BSTIterator {
    Deque<TreeNode> st = new ArrayDeque<>();
    public BSTIterator(TreeNode root) { pushLeft(root); }
    public int next() { TreeNode n = st.pop(); pushLeft(n.right); return n.val; }
    public boolean hasNext() { return !st.isEmpty(); }
    void pushLeft(TreeNode n) { while (n != null) { st.push(n); n = n.left; } }
}

[!info] 复杂度
next/hasNext 均摊 O(1)，空间 O(h)。

[!tip] 套路

"迭代中序"通用模板：栈 + pushLeft。惰性遍历，比一次性中序省空间（只存一条左链）。

222. 完全二叉树的节点个数

完全二叉树节点数，O(log²n)。

思路脉络：完全二叉树——若左右子树高度相同，左子是满的，节点数 = 2^h - 1 用公式；不同则递归数。满子树 O(1) 算，非满递归，整体 O(log²n)。

class Solution {
    public int countNodes(TreeNode root) {
        if (root == null) return 0;
        int lh = height(root.left), rh = height(root.right);
        if (lh == rh) return (1 << lh) + countNodes(root.right);   // 左满, 数左+递归右
        return (1 << rh) + countNodes(root.left);                   // 右满, 数右+递归左
    }
    int height(TreeNode n) { int h = 0; while (n != null) { h++; n = n.left; } return h; }
}

[!info] 复杂度
时间 O(log²n)，空间 O(log n)。

[!warning] 易错点

height 只走左链（完全二叉树性质：左链高度 = 该子树高度，除非最后一层）。lh == rh 说明左子树满（高度 lh），左子节点 = 2^lh - 1，加根 1 = 2^lh，再递归右。1 << lh 是 2^lh。

637. 二叉树的层平均值

每层节点值的平均值。

思路脉络：层序 BFS，每层累加求和再除以节点数。注意 double 防溢出。

class Solution {
    public List<Double> averageOfLevels(TreeNode root) {
        List<Double> res = new ArrayList<>();
        Queue<TreeNode> q = new ArrayDeque<>(); q.offer(root);
        while (!q.isEmpty()) {
            int size = q.size(); double sum = 0;
            for (int i = 0; i < size; i++) {
                TreeNode n = q.poll(); sum += n.val;
                if (n.left != null) q.offer(n.left);
                if (n.right != null) q.offer(n.right);
            }
            res.add(sum / size);
        }
        return res;
    }
}

[!info] 复杂度
时间 O(n)，空间 O(n)。

[!warning] 易错点

sum 用 double，否则大数相加溢出。sum / size 是 double 除法。

103. 二叉树的锯齿形层序遍历

层序，但奇数层从左到右、偶数层从右到左。

思路脉络：BFS 基础上加方向标志。偶数层（0起）正向收、奇数层用 add(0, val) 反向收（或最后 reverse）。

class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) return res;
        Queue<TreeNode> q = new ArrayDeque<>(); q.offer(root);
        boolean leftToRight = true;
        while (!q.isEmpty()) {
            int size = q.size(); LinkedList<Integer> level = new LinkedList<>();
            for (int i = 0; i < size; i++) {
                TreeNode n = q.poll();
                if (leftToRight) level.add(n.val); else level.addFirst(n.val);
                if (n.left != null) q.offer(n.left);
                if (n.right != null) q.offer(n.right);
            }
            res.add(level); leftToRight = !leftToRight;
        }
        return res;
    }
}

[!info] 复杂度
时间 O(n)，空间 O(n)。

[!tip] 套路

锯齿层序用 LinkedList.addFirst 在反向层插头，比"正向收集再 reverse"更简洁。BFS 层序模板是 [[#199. 二叉树的右视图]]、[[#102. 二叉树的层序遍历]]、[[#637. 二叉树的层平均值]] 的共同基底。

10. 二叉搜索树

BST 的核心性质：中序遍历是升序。这给三类题统一解法：最小差/第 K 小/验证合法性，都靠中序。

530. 二叉搜索树的最小绝对差

BST 任意两节点值最小绝对差。

思路脉络：BST 中序升序，最小差必在相邻中序节点间。中序遍历维护 prev，每步算 cur - prev 取最小。

class Solution {
    Integer prev = null; int ans = Integer.MAX_VALUE;
    public int getMinimumDifference(TreeNode root) {
        dfs(root); return ans;
    }
    void dfs(TreeNode n) {
        if (n == null) return;
        dfs(n.left);
        if (prev != null) ans = Math.min(ans, n.val - prev);
        prev = n.val;
        dfs(n.right);
    }
}

[!info] 复杂度
时间 O(n)，空间 O(h)。

[!tip] 套路

BST 中序后相邻即"最接近"，最小差必在中序相邻。prev 用 Integer 处理首节点无前驱。

98. 验证二叉搜索树

判断是否合法 BST。

思路脉络：递归传上下界 (lo, hi)，每节点须在 (lo, hi) 内，进左收紧上界、进右收紧下界。用 long 防整型极值越界。和热题 100 相同。

class Solution {
    public boolean isValidBST(TreeNode root) {
        return check(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }
    boolean check(TreeNode n, long lo, long hi) {
        if (n == null) return true;
        if (n.val <= lo || n.val >= hi) return false;
        return check(n.left, lo, n.val) && check(n.right, n.val, hi);
    }
}

[!info] 复杂度
时间 O(n)，空间 O(h)。

[!warning] 易错点

BST 要求"整棵左子树 < 根"，不是只比直接子节点。上下界法体现全局约束。long 处理 Integer.MIN_VALUE 节点。

11. 图

图的四把刀：DFS 染色（连通/感染）、BFS 层序（最短步数）、拓扑排序（依赖关系）、并查集（连通分量）。难点在建图（邻接表、隐式图）。

130. 被围绕的区域

矩阵 O/X，把被 X 围住的 O 翻成 X（与边界相连的 O 不翻）。

思路脉络：反向思考——从边界所有 O 出发 DFS/BFS 标记"不翻"，剩下的 O 都是被围的，翻成 X。

class Solution {
    public void solve(char[][] board) {
        int m = board.length, n = board[0].length;
        for (int i = 0; i < m; i++) {
            dfs(board, i, 0); dfs(board, i, n - 1);           // 左右边界
        }
        for (int j = 0; j < n; j++) {
            dfs(board, 0, j); dfs(board, m - 1, j);           // 上下边界
        }
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++) {
                if (board[i][j] == 'O') board[i][j] = 'X';    // 剩下的 O 是被围的
                else if (board[i][j] == 'A') board[i][j] = 'O'; // 标记的还原
            }
    }
    void dfs(char[][] b, int i, int j) {
        if (i < 0 || i >= b.length || j < 0 || j >= b[0].length || b[i][j] != 'O') return;
        b[i][j] = 'A';
        dfs(b, i+1, j); dfs(b, i-1, j); dfs(b, i, j+1); dfs(b, i, j-1);
    }
}

[!info] 复杂度
时间 O(mn)，空间 O(mn)。

[!tip] 套路

"与边界连通的保留"类问题：从边界反向标记，再处理内部。比"正向判断是否被围"简单得多。

399. 除法求值

给一组 a/b = k 等式，查询若干 c/d 的值。

思路脉络：把等式建成带权有向图——a→b 权 k、b→a 权 1/k。每次查询从 c 到 d 做 BFS/DFS，路径权乘积即答案；不可达返回 -1。

class Solution {
    public double[] calcEquation(List<List<String>> eq, double[] val, List<List<String>> q) {
        Map<String, Map<String, Double>> g = new HashMap<>();
        for (int i = 0; i < eq.size(); i++) {
            String a = eq.get(i).get(0), b = eq.get(i).get(1);
            g.computeIfAbsent(a, k -> new HashMap<>()).put(b, val[i]);
            g.computeIfAbsent(b, k -> new HashMap<>()).put(a, 1.0 / val[i]);
        }
        double[] res = new double[q.size()];
        for (int i = 0; i < q.size(); i++) {
            res[i] = bfs(g, q.get(i).get(0), q.get(i).get(1), new HashSet<>());
        }
        return res;
    }
    double bfs(Map<String, Map<String, Double>> g, String s, String t, Set<String> seen) {
        if (!g.containsKey(s) || !g.containsKey(t)) return -1.0;
        if (s.equals(t)) return 1.0;
        seen.add(s);
        for (Map.Entry<String, Double> e : g.get(s).entrySet()) {
            if (!seen.contains(e.getKey())) {
                double sub = bfs(g, e.getKey(), t, seen);
                if (sub != -1.0) return e.getValue() * sub;
            }
        }
        return -1.0;
    }
}

[!info] 复杂度
时间 O(查询数 × 节点数)，空间 O(等式数)。

[!tip] 套路

"变量间传递关系"建模成带权图，路径乘积即传递结果。并查集也能做（带权并查集），BFS 更直观。

210. 课程表 II

返回一种可行的修课顺序，不可行返回空。

思路脉络：和 207 完全相同，只是出队顺序就是拓扑序，收集进结果数组。最后判 cnt == n。

class Solution {
    public int[] findOrder(int n, int[][] pre) {
        List<List<Integer>> g = new ArrayList<>();
        int[] indeg = new int[n];
        for (int i = 0; i < n; i++) g.add(new ArrayList<>());
        for (int[] p : pre) { g.get(p[1]).add(p[0]); indeg[p[0]]++; }
        Queue<Integer> q = new ArrayDeque<>();
        for (int i = 0; i < n; i++) if (indeg[i] == 0) q.offer(i);
        int[] res = new int[n]; int idx = 0;
        while (!q.isEmpty()) { int c = q.poll(); res[idx++] = c; for (int nx : g.get(c)) if (--indeg[nx] == 0) q.offer(nx); }
        return idx == n ? res : new int[0];
    }
}

[!info] 复杂度
时间 O(V+E)，空间 O(V+E)。

[!warning] 易错点

边方向：[a,b] 表示"先 b 后 a"，所以 b→a（a 依赖 b）。建反了入度语义错。

909. 蛇梯棋

n×n 棋盘有蛇梯，求从 (1,1) 到终点的最少掷骰次数。

思路脉络：BFS 最短步数。每个位置 i 模拟掷 1-6，遇到蛇梯跳转（注意 Boustrophedon 编号——奇数行从左到右、偶数行从右到左，坐标映射是难点）。

class Solution {
    public int snakesAndLadders(int[][] board) {
        int n = board.length, target = n * n;
        int[] dist = new int[target + 1]; Arrays.fill(dist, -1); dist[1] = 0;
        Queue<Integer> q = new ArrayDeque<>(); q.offer(1);
        while (!q.isEmpty()) {
            int cur = q.poll();
            for (int move = 1; move <= 6 && cur + move <= target; move++) {
                int next = cur + move;
                int[] rc = pos(next, n);
                int r = rc[0], c = rc[1];
                if (board[r][c] != -1) next = board[r][c];
                if (dist[next] == -1) { dist[next] = dist[cur] + 1; q.offer(next); }
            }
        }
        return dist[target];
    }
    int[] pos(int num, int n) {
        int r = (num - 1) / n, c = (num - 1) % n;        // 从底起算的行列
        if (r % 2 == 1) c = n - 1 - c;                    // 偶数行(从底0起)反向
        return new int[]{n - 1 - r, c};                   // 转成从顶起的行
    }
}

[!info] 复杂度
时间 O(n²)，空间 O(n²)。

[!warning] 易错点

坐标映射 pos：从底起第 r 行，r 偶数正向、奇数反向；最终行号 = n-1-r。这块最容易写错，建议画图验证。

433. 最小基因变化

起始基因串到目标串，每次变一个字符且中间串须在银行库里，求最少步数。

思路脉络：BFS 最短路。每个状态生成所有"变一位"的邻居，邻居在银行库里且未访问则入队。首次到达目标即最少步数。

class Solution {
    public int minMutation(String start, String end, String[] bank) {
        Set<String> set = new HashSet<>(Arrays.asList(bank));
        if (!set.contains(end)) return -1;
        char[] genes = {'A','C','G','T'};
        Queue<String> q = new ArrayDeque<>(); q.offer(start);
        Set<String> seen = new HashSet<>(); seen.add(start);
        int steps = 0;
        while (!q.isEmpty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                String cur = q.poll();
                if (cur.equals(end)) return steps;
                char[] cs = cur.toCharArray();
                for (int j = 0; j < cs.length; j++) {
                    char old = cs[j];
                    for (char g : genes) {
                        cs[j] = g;
                        String nb = new String(cs);
                        if (set.contains(nb) && !seen.contains(nb)) { seen.add(nb); q.offer(nb); }
                    }
                    cs[j] = old;
                }
            }
            steps++;
        }
        return -1;
    }
}

[!info] 复杂度
时间 O(N × L × 4)（N 银行大小、L 串长），空间 O(N)。

[!tip] 套路

"变换一步可达"类问题用 BFS：枚举所有一步邻居（本题枚举每位 × 4 字符），邻居在合法集内则入队。和单词接龙同模板。

127. 单词接龙

beginWord 到 endWord，每次变一个字母且中间词在词典里，求最短转换序列长度。

思路脉络：和最小基因变化完全同模板——BFS，枚举每位 × 26 字母邻居，邻居在词典且未访问则入队。双向 BFS 可优化（从两端相向扩展，搜更窄的一侧），但单向 BFS 简洁。

class Solution {
    public int ladderLength(String begin, String end, List<String> wordList) {
        Set<String> dict = new HashSet<>(wordList);
        if (!dict.contains(end)) return 0;
        Queue<String> q = new ArrayDeque<>(); q.offer(begin);
        Set<String> seen = new HashSet<>(); seen.add(begin);
        int steps = 1;
        while (!q.isEmpty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                char[] cs = q.poll().toCharArray();
                for (int j = 0; j < cs.length; j++) {
                    char old = cs[j];
                    for (char c = 'a'; c <= 'z'; c++) {
                        cs[j] = c;
                        String nb = new String(cs);
                        if (nb.equals(end)) return steps + 1;
                        if (dict.contains(nb) && !seen.contains(nb)) { seen.add(nb); q.offer(nb); }
                    }
                    cs[j] = old;
                }
            }
            steps++;
        }
        return 0;
    }
}

[!info] 复杂度
时间 O(N × L × 26)，空间 O(N)。

[!tip] 进阶

双向 BFS：从 begin 和 end 各自 BFS，每步扩节点少的一侧，相遇即最短。对大词典快很多，但实现稍复杂。

12. 字典树

Trie 把"前缀匹配"从 O(总词数 × 词长) 降到 O(前缀长)。共享前缀的词共用路径。难点在节点结构（children + isEnd）和带通配符的搜索。

211. 添加与搜索单词 - 数据结构设计

addWord + search，search 支持 . 通配任意字母。

思路脉络：Trie 基础上，搜索遇 . 时递归所有非空 children。search 改成递归（带位置 i）。

class WordDictionary {
    private WordDictionary[] children = new WordDictionary[26];
    private boolean isEnd;
    public void addWord(String word) {
        WordDictionary node = this;
        for (char c : word.toCharArray()) {
            int i = c - 'a';
            if (node.children[i] == null) node.children[i] = new WordDictionary();
            node = node.children[i];
        }
        node.isEnd = true;
    }
    public boolean search(String word) { return dfs(word, 0, this); }
    boolean dfs(String word, int i, WordDictionary node) {
        if (i == word.length()) return node.isEnd;
        char c = word.charAt(i);
        if (c == '.') {
            for (WordDictionary ch : node.children) if (ch != null && dfs(word, i + 1, ch)) return true;
            return false;
        }
        return node.children[c - 'a'] != null && dfs(word, i + 1, node.children[c - 'a']);
    }
}

[!info] 复杂度
addWord O(L)，search 最坏 O(26^L)（全通配）。

212. 单词搜索 II

字符网格里找所有词典里的词。

思路脉络：Trie + 回溯。把词典建 Trie，DFS 网格每个起点，沿 Trie 下走，遇 isEnd 收集，越界/字符不在 Trie/已访问则回溯。用 Trie 剪枝：只走 Trie 里有对应前缀的方向。

class Solution {
    class Trie { Trie[] ch = new Trie[26]; String word; }
    int[] dx = {-1,1,0,0}, dy = {0,0,-1,1};
    public List<String> findWords(char[][] board, String[] words) {
        Trie root = new Trie();
        for (String w : words) {
            Trie node = root;
            for (char c : w.toCharArray()) { int i = c - 'a'; if (node.ch[i] == null) node.ch[i] = new Trie(); node = node.ch[i]; }
            node.word = w;
        }
        List<String> res = new ArrayList<>();
        for (int i = 0; i < board.length; i++)
            for (int j = 0; j < board[0].length; j++)
                dfs(board, i, j, root, res);
        return res;
    }
    void dfs(char[][] b, int i, int j, Trie node, List<String> res) {
        char c = b[i][j];
        if (c == '#' || node.ch[c - 'a'] == null) return;
        node = node.ch[c - 'a'];
        if (node.word != null) { res.add(node.word); node.word = null; }  // 收集并去重
        b[i][j] = '#';
        for (int k = 0; k < 4; k++) {
            int x = i + dx[k], y = j + dy[k];
            if (x >= 0 && x < b.length && y >= 0 && y < b[0].length) dfs(b, x, y, node, res);
        }
        b[i][j] = c;
    }
}

[!info] 复杂度
时间 O(mn × 4^L)（L 最长词），空间 O(词典总字符)。

[!warning] 易错点

收集后置 node.word = null 防同一词重复收集。b[i][j]='#' 标记访问、回溯恢复，Trie 剪枝只走有前缀的方向。

13. 回溯

回溯是"带撤销的 DFS"。统一框架：做选择 → 递归 → 撤销选择。区分排列（用 used）/组合（用 start），收集在叶子或每个节点视题而定。

77. 组合

返回 1..n 中所有 k 个数的组合。

思路脉络：组合用 start 防重复（只往后选）。每层从 start 到 n，选了就递归 i+1，长度到 k 收集。

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> combine(int n, int k) {
        backtrack(n, k, 1, new ArrayList<>()); return res;
    }
    void backtrack(int n, int k, int start, List<Integer> path) {
        if (path.size() == k) { res.add(new ArrayList<>(path)); return; }
        for (int i = start; i <= n; i++) {
            path.add(i); backtrack(n, k, i + 1, path); path.remove(path.size() - 1);
        }
    }
}

[!info] 复杂度
时间 O(C(n,k))，空间 O(k)。

[!tip] 剪枝

i <= n - (k - path.size()) + 1：剩余位置不够凑满 k 个时停，省掉无效分支。

46. 全排列

无重复数组所有全排列。

思路脉络：排列用 used 标记，每层从头扫跳过已选。长度满收集。和热题 100 相同。

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> permute(int[] nums) {
        backtrack(nums, new ArrayList<>(), new boolean[nums.length]); return res;
    }
    void backtrack(int[] nums, List<Integer> path, boolean[] used) {
        if (path.size() == nums.length) { res.add(new ArrayList<>(path)); return; }
        for (int i = 0; i < nums.length; i++) {
            if (used[i]) continue;
            path.add(nums[i]); used[i] = true;
            backtrack(nums, path, used);
            path.remove(path.size() - 1); used[i] = false;
        }
    }
}

[!info] 复杂度
时间 O(n·n!)，空间 O(n)。

[!warning] 易错点

收集时 new ArrayList<>(path) 复制，不能直接 add(path)——path 是同一引用，回溯后被清空。

52. N 皇后 II

n×n 棋盘放 n 个皇后不互相攻击，返回摆法总数（不要求列出每种）。

思路脉络：逐行回溯，每行选一列。冲突检查只看上方（同行只一个、下方没放）：同列、主对角(row-col)、副对角(row+col)。用三个 Set 记已占列/对角，valid 降到 O(1)。

class Solution {
    int ans = 0;
    Set<Integer> col = new HashSet<>(), diag1 = new HashSet<>(), diag2 = new HashSet<>();
    public int totalNQueens(int n) { backtrack(n, 0); return ans; }
    void backtrack(int n, int row) {
        if (row == n) { ans++; return; }
        for (int c = 0; c < n; c++) {
            int d1 = row - c, d2 = row + c;
            if (col.contains(c) || diag1.contains(d1) || diag2.contains(d2)) continue;
            col.add(c); diag1.add(d1); diag2.add(d2);
            backtrack(n, row + 1);
            col.remove(c); diag1.remove(d1); diag2.remove(d2);
        }
    }
}

[!info] 复杂度
时间 O(n!)，空间 O(n)。

[!tip] 套路

对角线用 row-col、row+col 作 key 是经典。和 N 皇后 I 完全同模板，只是不收集棋盘只计数。

22. 括号生成

生成 n 对括号的所有合法组合。

思路脉络：跟踪 open/close 计数。open < n 可放左括号，close < open 可放右括号（右括号须匹配已放左括号）。和热题 100 相同。

class Solution {
    List<String> res = new ArrayList<>();
    public List<String> generateParenthesis(int n) {
        backtrack(new StringBuilder(), 0, 0, n); return res;
    }
    void backtrack(StringBuilder sb, int open, int close, int n) {
        if (sb.length() == 2 * n) { res.add(sb.toString()); return; }
        if (open < n) { sb.append('('); backtrack(sb, open + 1, close, n); sb.deleteCharAt(sb.length() - 1); }
        if (close < open) { sb.append(')'); backtrack(sb, open, close + 1, n); sb.deleteCharAt(sb.length() - 1); }
    }
}

[!info] 复杂度
时间 O(4^n/√n)（卡特兰数），空间 O(n)。

[!warning] 易错点

close < open 是合法性核心：右括号必须匹配一个已放的左括号。

79. 单词搜索

字符网格搜索单词，字母不可重复用。

思路脉络：每个格子作起点 DFS 四向扩展，进入先标记 # 防重复、退出恢复。回溯的"撤销"在网格题的体现。和热题 100 相同。

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, word, i, j, 0)) return true;
        return false;
    }
    boolean dfs(char[][] b, String w, int i, int j, int k) {
        if (k == w.length()) return true;
        if (i < 0 || i >= b.length || j < 0 || j >= b[0].length || b[i][j] != w.charAt(k)) return false;
        char t = b[i][j]; b[i][j] = '#';
        boolean f = dfs(b, w, i+1, j, k+1) || dfs(b, w, i-1, j, k+1) || dfs(b, w, i, j+1, k+1) || dfs(b, w, i, j-1, k+1);
        b[i][j] = t;
        return f;
    }
}

[!info] 复杂度
时间 O(mn·3^L)，空间 O(L)。

[!warning] 易错点

标记和恢复必须配对：char t 存原值，DFS 后还原。漏恢复会让其他起点的搜索踩到 # 误判。

14. 分治

分治：找中点 → 递归处理两半 → 合并。难点在"如何合并"和递归终止。

427. 建立四叉树

n×n 0/1 矩阵（n 是 2 的幂），构造四叉树。

思路脉络：递归。当前块全 0 或全 1 建叶节点；否则分四象限各递归。判断全同值直接遍历。

class Solution {
    public Node construct(int[][] grid) {
        return build(grid, 0, 0, grid.length);
    }
    Node build(int[][] g, int r, int c, int len) {
        if (same(g, r, c, len)) return new Node(g[r][c] == 1, true);
        Node node = new Node(true, false);
        int half = len / 2;
        node.topLeft = build(g, r, c, half);
        node.topRight = build(g, r, c + half, half);
        node.bottomLeft = build(g, r + half, c, half);
        node.bottomRight = build(g, r + half, c + half, half);
        return node;
    }
    boolean same(int[][] g, int r, int c, int len) {
        int v = g[r][c];
        for (int i = r; i < r + len; i++)
            for (int j = c; j < c + len; j++)
                if (g[i][j] != v) return false;
        return true;
    }
}

[!info] 复杂度
时间 O(n²)，空间 O(log n)。

[!warning] 易错点

象限顺序：左上、右上、左下、右下，坐标偏移别搞反。叶节点 val = g[r][c]==1、isLeaf=true。

23. 合并 K 个升序链表

合并 k 个升序链表。

思路脉络：小顶堆，k 个头入堆，每次弹最小接上、其 next 入堆。O(n log k)。

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) return null;
        PriorityQueue<ListNode> pq = new PriorityQueue<>((a, b) -> a.val - b.val);
        for (ListNode h : lists) if (h != null) pq.offer(h);
        ListNode dummy = new ListNode(0), cur = dummy;
        while (!pq.isEmpty()) { ListNode n = pq.poll(); cur.next = n; cur = cur.next; if (n.next != null) pq.offer(n.next); }
        return dummy.next;
    }
}

[!info] 复杂度
时间 O(n log k)，空间 O(k)。

[!tip] 另解

分治两两合并也是 O(n log k)，不依赖堆。把合并两个有序链表当子程序，两两配对合并到剩一个。

15. Kadane 算法

Kadane 求最大子数组和：dp[i] = max(nums[i], dp[i-1]+nums[i])，压缩成 pre 变量。环形版用"总和 − 最小子数组和"求跨边界的最大。

918. 环形子数组的最大和

子数组可跨首尾相连（环形），求最大和。

思路脉络：两种情况——最大子数组不跨边界（普通 Kadane）、跨边界（= 总和 − 最小子数组）。注意全负特例：若总和 − 最小子数组 = 0（最小子数组就是整个数组），这种情况不合法（子数组不能空），退化成普通最大。

class Solution {
    public int maxSubarraySumCircular(int[] nums) {
        int total = 0, curMax = 0, maxSum = nums[0], curMin = 0, minSum = nums[0];
        for (int n : nums) {
            total += n;
            curMax = Math.max(n, curMax + n); maxSum = Math.max(maxSum, curMax);
            curMin = Math.min(n, curMin + n); minSum = Math.min(minSum, curMin);
        }
        return maxSum > 0 ? Math.max(maxSum, total - minSum) : maxSum;
    }
}

[!info] 复杂度
时间 O(n)，空间 O(1)。

[!warning] 易错点

maxSum > 0 判断关键：若 maxSum <= 0 说明全负，total - minSum = 0（空子数组）不合法，只能返回普通最大 maxSum。否则取 max(普通最大, total - 最小子数组)。

16. 二分查找

二分的本质是在单调性上收缩边界。难点全在边界处理：精确值、左界、右界三种目标的循环条件和收缩方式不同。

[!tip] 左闭右闭三态
统一 [l,r] + while(l<=r)：精确值命中直接返回；左界命中也 r=m-1 往左压、记候选；右界命中 l=m+1 往右压。

74. 搜索二维矩阵

每行升序，行间首大于上行尾，找 target。

思路脉络：行间严格衔接等价一维升序——mid 映射到 matrix[mid/n][mid%n]，一次二分。

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length, n = matrix[0].length, l = 0, r = m * n - 1;
        while (l <= r) {
            int mid = (l + r) / 2, v = matrix[mid / n][mid % n];
            if (v == target) return true;
            else if (v < target) l = mid + 1; else r = mid - 1;
        }
        return false;
    }
}

[!info] 复杂度
时间 O(log mn)，空间 O(1)。

[!tip] 辨析

注意和 [[#240. 搜索二维矩阵 II]] 区别：那题每行升、每列升但行间未必衔接，不能压成一维，得用右上角 O(m+n)。本题行间严格衔接，才能一维二分。

162. 寻找峰值

数组找任一峰值（大于相邻），nums[-1]=nums[n]=-∞，要求 O(log n)。

思路脉络：二分。nums[mid] < nums[mid+1] 说明右侧必有峰值（上坡必到峰），去右；否则左侧（含 mid）有峰值。相邻不等必有峰。

class Solution {
    public int findPeakElement(int[] nums) {
        int l = 0, r = nums.length - 1;
        while (l < r) {
            int m = (l + r) / 2;
            if (nums[m] < nums[m + 1]) l = m + 1; else r = m;
        }
        return l;
    }
}

[!info] 复杂度
时间 O(log n)，空间 O(1)。

[!warning] 易错点

nums[m] < nums[m+1] 去 l=m+1（右半必有峰），否则 r=m（m 自己可能是峰）。l<r 不是 l<=r，因为比较 m+1 要防越界。

33. 搜索旋转排序数组

升序数组旋转过，找 target，O(log n)。

思路脉络：对 mid 切一刀必有一半有序。nums[l]<=nums[m] 左半有序，看 target 在不在左半范围决定搜哪边；否则右半有序。

class Solution {
    public int search(int[] nums, int target) {
        int l = 0, r = nums.length - 1;
        while (l <= r) {
            int m = (l + r) / 2;
            if (nums[m] == target) return m;
            if (nums[l] <= nums[m]) {
                if (nums[l] <= target && target < nums[m]) r = m - 1; else l = m + 1;
            } else {
                if (nums[m] < target && target <= nums[r]) l = m + 1; else r = m - 1;
            }
        }
        return -1;
    }
}

[!info] 复杂度
时间 O(log n)，空间 O(1)。

[!warning] 易错点

判"左半有序"用 nums[l] <= nums[m]（含等号，处理 l==m）。范围判断用闭开区间 [nums[l], nums[m])。

4. 寻找两个正序数组的中位数

两个升序数组找中位数，O(log(m+n))。

思路脉络：中位数是"把合并数组平分的分界点"。二分较短数组的划分数 i，j = half - i，合法划分要 aL<=bR 且 bL<=aR。边界用 ±∞。

class Solution {
    public double findMedianSortedArrays(int[] a, int[] b) {
        if (a.length > b.length) return findMedianSortedArrays(b, a);
        int m = a.length, n = b.length, half = (m + n + 1) / 2, lo = 0, hi = m;
        while (lo <= hi) {
            int i = (lo + hi) / 2, j = half - i;
            int aL = i == 0 ? Integer.MIN_VALUE : a[i - 1];
            int aR = i == m ? Integer.MAX_VALUE : a[i];
            int bL = j == 0 ? Integer.MIN_VALUE : b[j - 1];
            int bR = j == n ? Integer.MAX_VALUE : b[j];
            if (aL <= bR && bL <= aR) {
                if ((m + n) % 2 == 1) return Math.max(aL, bL);
                return (Math.max(aL, bL) + Math.min(aR, bR)) / 2.0;
            } else if (aL > bR) hi = i - 1; else lo = i + 1;
        }
        return 0;
    }
}

[!info] 复杂度
时间 O(log(min(m,n)))，空间 O(1)。

[!warning] 易错点

必须在短数组上二分：否则 j = half - i 可能越界。开头 swap 保证 a 短。边界用 ±∞：i==0 时 aL 取 MIN_VALUE。

17. 堆

堆维护"半个有序集"，快速取最大/最小。两类：Top-K（大小 K 的堆，比堆顶差就丢）、动态中位数（大顶堆装小半 + 小顶堆装大半，平衡规模）。

502. IPO

k 个项目，各有资本 w[i] 和利润 p[i]，从初始资本 W 开始，每次选能做的（w[i] <= W）里利润最大的，求做完 k 个后的总资本。

思路脉络：贪心 + 两个堆。按资本升序排项目，用最大利润堆维护"当前能做的项目"。每次做利润最大的（堆顶），做完资本增加，把新解锁的项目入堆，做 k 次。

class Solution {
    public int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {
        int n = profits.length, i = 0;
        int[][] projects = new int[n][2];
        for (int j = 0; j < n; j++) projects[j] = new int[]{capital[j], profits[j]};
        Arrays.sort(projects, (a, b) -> a[0] - b[0]);
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        for (int cnt = 0; cnt < k; cnt++) {
            while (i < n && projects[i][0] <= w) maxHeap.offer(projects[i++][1]);
            if (maxHeap.isEmpty()) break;
            w += maxHeap.poll();
        }
        return w;
    }
}

[!info] 复杂度
时间 O(n log n + k log n)，空间 O(n)。

[!warning] 易错点

必须按资本升序排，才能用指针 i 一次性把"新解锁"的项目入堆（资本只增不减，入过堆的不用退）。堆里选利润最大——贪心选择。

373. 查找和最小的 K 对数字

两个升序数组 nums1/nums2，找和最小的 k 个数对 (u,v)。

思路脉络：最小堆。(0,0) 入堆，每次弹最小对 (i,j)，把 (i+1,j) 和 (i,j+1) 入堆。用 Set 防重复入堆。

class Solution {
    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        List<List<Integer>> res = new ArrayList<>();
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> nums1[a[0]] + nums2[a[1]] - nums1[b[0]] - nums2[b[1]]);
        Set<Long> seen = new HashSet<>();
        pq.offer(new int[]{0, 0}); seen.add(0L);
        while (!pq.isEmpty() && res.size() < k) {
            int[] p = pq.poll(); int i = p[0], j = p[1];
            res.add(Arrays.asList(nums1[i], nums2[j]));
            if (i + 1 < nums1.length && seen.add((long)(i+1) * 200 + j)) pq.offer(new int[]{i+1, j});
            if (j + 1 < nums2.length && seen.add((long)i * 200 + j + 1)) pq.offer(new int[]{i, j+1});
        }
        return res;
    }
}

[!info] 复杂度
时间 O(k log k)，空间 O(k)。

[!warning] 易错点

防重复是关键：seen 用 (i+1)*200+j 编码（200 因长度 ≤ 100，不冲突）。seen.add 返回 true 才入堆。

295. 数据流的中位数

数据流动态加数，随时取中位数。

思路脉络：两个堆——大顶堆 lo 装较小半、小顶堆 hi 装较大半，平衡规模差 ≤1。addNum：先入 lo，把 lo 最大推到 hi，若 lo 比 hi 少则回补。

class MedianFinder {
    PriorityQueue<Integer> lo = new PriorityQueue<>(Collections.reverseOrder());
    PriorityQueue<Integer> hi = new PriorityQueue<>();
    public void addNum(int num) {
        lo.offer(num); hi.offer(lo.poll());
        if (lo.size() < hi.size()) lo.offer(hi.poll());
    }
    public double findMedian() {
        return lo.size() > hi.size() ? lo.peek() : (lo.peek() + hi.peek()) / 2.0;
    }
}

[!info] 复杂度
addNum O(log n)，findMedian O(1)。

[!warning] 易错点

平衡方向：保证 lo.size >= hi.size，奇数中位数取 lo.peek。lo.poll() 给 hi 保证"小半最大 ≤ 大半最小"不变量。

18. 位运算

位运算处理底层 bit 操作：异或抵消、位统计、移位取位。关键是熟悉 & | ^ ~ << >> 的语义和常见套路（n & (n-1) 去最低 1、n ^ n = 0）。

67. 二进制求和

两个二进制字符串求和。

思路脉络：模拟加法，从低位（字符串末尾）向高位加，处理进位。比转 int 求和更稳（防大数溢出）。

class Solution {
    public String addBinary(String a, String b) {
        StringBuilder sb = new StringBuilder();
        int i = a.length() - 1, j = b.length() - 1, carry = 0;
        while (i >= 0 || j >= 0 || carry != 0) {
            int sum = carry;
            if (i >= 0) sum += a.charAt(i--) - '0';
            if (j >= 0) sum += b.charAt(j--) - '0';
            sb.append(sum % 2); carry = sum / 2;
        }
        return sb.reverse().toString();
    }
}

[!info] 复杂度
时间 O(max(m,n))，空间 O(max(m,n))。

190. 颠倒二进制位

32 位无符号整数的二进制位颠倒。

思路脉络：逐位处理。每次取 n 最低位，左移到结果的高位（res = (res<<1) | (n&1)），n 右移。32 次循环。

public class Solution {
    public int reverseBits(int n) {
        int res = 0;
        for (int i = 0; i < 32; i++) {
            res = (res << 1) | (n & 1);
            n >>>= 1;
        }
        return res;
    }
}

[!info] 复杂度
时间 O(1)（固定 32 位），空间 O(1)。

[!warning] 易错点

用 >>> 无符号右移，不是 >>（算术右移会填符号位）。

191. 位 1 的个数

32 位整数的 1 的个数。

思路脉络：n & (n-1) 消去最低位的 1，直到 n=0，操作次数即 1 的个数。比逐位检查快（只数 1）。

public class Solution {
    public int hammingWeight(int n) {
        int cnt = 0;
        while (n != 0) { n &= n - 1; cnt++; }
        return cnt;
    }
}

[!info] 复杂度
时间 O(1)，空间 O(1)。

[!tip] 套路

n & (n-1) 去最低 1：数 1、判 2 的幂（2 的幂只有一个 1，操作一次变 0）。

137. 只出现一次的数字 II

除一个数外每个出现三次，找那个。

思路脉络：位统计。对每一位，统计所有数该位的 1 个数，% 3 余数就是答案该位。32 位各算一次。

class Solution {
    public int singleNumber(int[] nums) {
        int ans = 0;
        for (int i = 0; i < 32; i++) {
            int cnt = 0;
            for (int n : nums) cnt += (n >> i) & 1;
            ans |= (cnt % 3) << i;
        }
        return ans;
    }
}

[!info] 复杂度
时间 O(32n)，空间 O(1)。

[!warning] 易错点

32 位逐位统计，|= 累加各位。% 3 因为其他数出现 3 次该位贡献 3 的倍数，被模掉。

201. 数字范围按位与

[m, n] 范围内所有整数按位与的结果。

思路脉络：按位与中只要某位在范围内出现过 0，该位必 0。只保留 m 和 n 的公共前缀，低位全 0。右移到相等再左移回来。

class Solution {
    public int rangeBitwiseAnd(int m, int n) {
        int shift = 0;
        while (m != n) { m >>= 1; n >>= 1; shift++; }
        return m << shift;
    }
}

[!info] 复杂度
时间 O(log n)，空间 O(1)。

[!warning] 易错点

公共前缀才保留——范围内 m 到 n 经历了后缀从全 0 到全 1，按位与后缀必 0。shift 记右移次数，最后左移还原。

19. 数学

数学题靠数论、模拟、二分逼近。注意溢出（用 long）和边界（0、负数）。

9. 回文数

整数是否回文，不转字符串。

思路脉络：反转后半数字，和前半比较。x % 10 取低位、x / 10 去低位，反转数 rev = rev*10 + 低位。当 rev >= x 时反转到一半。

class Solution {
    public boolean isPalindrome(int x) {
        if (x < 0 || (x % 10 == 0 && x != 0)) return false;
        int rev = 0;
        while (x > rev) { rev = rev * 10 + x % 10; x /= 10; }
        return x == rev || x == rev / 10;
    }
}

[!info] 复杂度
时间 O(log n)，空间 O(1)。

[!warning] 易错点

排除末尾 0 的非零数（10 不是回文）。奇数位反转多一位，x == rev/10 处理中间位。

172. 阶乘后的零

n! 末尾 0 的个数。

思路脉络：0 由因子 2×5 产生，2 充足，数 5 的个数。25/125 等含多个 5，累加 n/5 + n/25 + n/125 + ...。

class Solution {
    public int trailingZeroes(int n) {
        int ans = 0;
        while (n > 0) { n /= 5; ans += n; }
        return ans;
    }
}

[!info] 复杂度
时间 O(log n)，空间 O(1)。

[!warning] 易错点

25 贡献两个 5——n/5 算第一个、n/25 算第二个，循环累加全计入。不是直接 n/5。

69. x 的平方根

求 x 的整数平方根（向下取整）。

思路脉络：二分。mid*mid <= x 则候选并往右，否则往左。用 mid <= x/mid 代替 mid*mid 防溢出。

class Solution {
    public int mySqrt(int x) {
        int l = 1, r = x, ans = 0;
        while (l <= r) {
            int m = (l + r) / 2;
            if (m <= x / m) { ans = m; l = m + 1; } else r = m - 1;
        }
        return ans;
    }
}

[!info] 复杂度
时间 O(log x)，空间 O(1)。

[!warning] 易错点

m * m 会溢出，用 m <= x / m 等价判断（整数除法向下取整，安全）。

50. Pow(x, n)

求 x 的 n 次幂，O(log n)。

思路脉络：快速幂（二分）。偶数 x^n = (x^2)^(n/2)，奇数多乘 x。n 负取倒数。迭代。

class Solution {
    public double myPow(double x, int n) {
        long N = n;
        if (N < 0) { x = 1 / x; N = -N; }
        double ans = 1;
        while (N > 0) {
            if ((N & 1) == 1) ans *= x;
            x *= x; N >>= 1;
        }
        return ans;
    }
}

[!info] 复杂度
时间 O(log n)，空间 O(1)。

[!warning] 易错点

n 用 long 接收：Integer.MIN_VALUE 取反溢出。N & 1 判奇偶，N >>= 1 折半。

149. 直线上最多的点数

平面上一组点，找一条直线经过的点最多。

思路脉络：枚举每个点作基点，对其他点算斜率，哈希统计相同斜率个数。同斜率即在同一条过基点的线上。重复点单独计数。

class Solution {
    public int maxPoints(int[][] points) {
        int ans = 1, n = points.length;
        for (int i = 0; i < n; i++) {
            Map<String, Integer> slopes = new HashMap<>();
            int dup = 0, max = 0;
            for (int j = i + 1; j < n; j++) {
                int dx = points[j][0] - points[i][0], dy = points[j][1] - points[i][1];
                if (dx == 0 && dy == 0) { dup++; continue; }
                int g = gcd(dx, dy);
                String slope = (dx / g) + "/" + (dy / g);
                max = Math.max(max, slopes.merge(slope, 1, Integer::sum));
            }
            ans = Math.max(ans, max + dup + 1);
        }
        return ans;
    }
    int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
}

[!info] 复杂度
时间 O(n²)，空间 O(n)。

[!warning] 易错点

斜率用约分后的字符串作 key（dx/g + "/" + dy/g），不能用浮点（精度问题）。重复点单独计 dup，加基点 +1。

20. 一维动态规划

DP 三问：状态定义、转移方程、遍历顺序。一维 DP 压缩成两三个变量。关键是找"子问题如何推出当前"。

139. 单词拆分

字符串能否拆成字典里的若干词。

思路脉络：dp[i] = 前 i 个字符能否拆分。枚举 j，dp[j] 为真且 s[j..i) 在字典则 dp[i] = true。

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> dict = new HashSet<>(wordDict);
        boolean[] dp = new boolean[s.length() + 1];
        dp[0] = true;
        for (int i = 1; i <= s.length(); i++)
            for (int j = 0; j < i; j++)
                if (dp[j] && dict.contains(s.substring(j, i))) { dp[i] = true; break; }
        return dp[s.length()];
    }
}

[!info] 复杂度
时间 O(n² × 子串哈希)，空间 O(n)。

[!warning] 易错点

内层 break 找到一个就停。子串 substring(j, i) 是 [j, i) 左闭右开。

322. 零钱兑换

用若干面额硬币凑成 amount 的最少枚数。

思路脉络：完全背包。dp[i] = 凑成金额 i 的最少硬币数。dp[i] = min(dp[i-coin] + 1)。初始化 amount+1 代替 MAX_VALUE 防 +1 溢出。

class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, amount + 1); dp[0] = 0;
        for (int i = 1; i <= amount; i++)
            for (int c : coins)
                if (c <= i) dp[i] = Math.min(dp[i], dp[i - c] + 1);
        return dp[amount] > amount ? -1 : dp[amount];
    }
}

[!info] 复杂度
时间 O(amount × 种类数)，空间 O(amount)。

[!warning] 易错点

初始化用 amount+1 而非 MAX_VALUE：MAX+1 会溢出成负数。amount+1 是"全用 1 元最多 amount 枚"的上界，超过即不可达。

300. 最长递增子序列

找最长严格递增子序列长度。

思路脉络：二分 O(n log n)。维护 tails 数组，tails[k] = 长度为 k+1 的递增子序列的最小末尾。每来一个数二分找第一个 ≥ 它的位置替换。tails 长度即 LIS。

class Solution {
    public int lengthOfLIS(int[] nums) {
        int[] tails = new int[nums.length], len = 0;
        for (int num : nums) {
            int l = 0, r = len;
            while (l < r) { int m = (l + r) / 2; if (tails[m] < num) l = m + 1; else r = m; }
            tails[l] = num; if (l == len) len++;
        }
        return len;
    }
}

[!info] 复杂度
时间 O(n log n)，空间 O(n)。

[!warning] 易错点

tails 存的不是真实子序列，而是"各长度最小末尾"，替换保证后续更易接上更长。求具体序列要回溯，不能直接读 tails。

21. 多维动态规划

状态升到二维（行列/区间维度）。难点在状态含义和遍历顺序——依赖跨行跨列，要确保填表时依赖项已就绪。压缩成一维时注意左上角的覆盖问题。

120. 三角形最小路径和

三角形从顶到底相邻下走，最小路径和。

思路脉络：自底向上 DP。dp[i][j] = 从 (i,j) 到底的最小路径和。dp[i][j] = min(dp[i+1][j], dp[i+1][j+1]) + triangle[i][j]。底部等于自身。可原地修改。

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int n = triangle.size();
        int[] dp = triangle.get(n - 1).stream().mapToInt(Integer::intValue).toArray();  // 底部
        for (int i = n - 2; i >= 0; i--)
            for (int j = 0; j <= i; j++)
                dp[j] = Math.min(dp[j], dp[j + 1]) + triangle.get(i).get(j);
        return dp[0];
    }
}

[!info] 复杂度
时间 O(n²)，空间 O(n)。

[!warning] 易错点

自底向上比自顶向下简单（不用处理边界，底部直接是自身）。一维 dp 从底向上更新，dp[j] 和 dp[j+1] 是下一层的值。

63. 不同路径 II

网格有障碍，左上到右下只能右或下，几种走法。

思路脉络：dp[i][j] = 到 (i,j) 的走法。障碍处为 0，否则 dp[i][j] = dp[i-1][j] + dp[i][j-1]。首行首列特殊处理（有障碍则后续全 0）。

class Solution {
    public int uniquePathsWithObstacles(int[][] g) {
        int m = g.length, n = g[0].length;
        int[] dp = new int[n]; dp[0] = g[0][0] == 0 ? 1 : 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (g[i][j] == 1) { dp[j] = 0; continue; }
                if (j > 0) dp[j] += dp[j - 1];
            }
        }
        return dp[n - 1];
    }
}

[!info] 复杂度
时间 O(mn)，空间 O(n)。

[!warning] 易错点

一维压缩：dp[j] += dp[j-1]，dp[j] 是上一行（上）、dp[j-1] 是本行已更新（左）。障碍处 dp[j]=0 且 continue（不累加左）。

5. 最长回文子串

找最长回文子串。

思路脉络：中心扩展法。回文以中心对称，中心可单字符（奇）或间隙（偶）。每个中心向两侧扩展，记录最长。和热题 100 相同。

class Solution {
    public String longestPalindrome(String s) {
        int st = 0, max = 1;
        for (int i = 0; i < s.length(); i++) {
            int l1 = expand(s, i, i), l2 = expand(s, i, i + 1);
            int len = Math.max(l1, l2);
            if (len > max) { max = len; st = i - (len - 1) / 2; }
        }
        return s.substring(st, st + max);
    }
    int expand(String s, int l, int r) {
        while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) { l--; r++; }
        return r - l - 1;
    }
}

[!info] 复杂度
时间 O(n²)，空间 O(1)。

[!warning] 易错点

expand 返回 r - l - 1：退出时 l/r 已是不匹配位置，真实回文 (l+1, r-1)，长 r-1-(l+1)+1 = r-l-1。起点 i - (len-1)/2 对奇偶都成立。

97. 交错字符串

s3 是否由 s1 和 s2 交错组成（保持各自字符顺序）。

思路脉络：二维 DP。dp[i][j] = s1 前 i 个和 s2 前 j 个能否交错成 s3 前 i+j 个。dp[i][j] = (dp[i-1][j] && s1[i-1]==s3[i+j-1]) || (dp[i][j-1] && s2[j-1]==s3[i+j-1])。

class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        int m = s1.length(), n = s2.length();
        if (m + n != s3.length()) return false;
        boolean[] dp = new boolean[n + 1];
        dp[0] = true;
        for (int j = 1; j <= n; j++) dp[j] = dp[j - 1] && s2.charAt(j - 1) == s3.charAt(j - 1);
        for (int i = 1; i <= m; i++) {
            dp[0] = dp[0] && s1.charAt(i - 1) == s3.charAt(i - 1);
            for (int j = 1; j <= n; j++)
                dp[j] = (dp[j] && s1.charAt(i - 1) == s3.charAt(i + j - 1))
                     || (dp[j - 1] && s2.charAt(j - 1) == s3.charAt(i + j - 1));
        }
        return dp[n];
    }
}

[!info] 复杂度
时间 O(mn)，空间 O(n)。

[!warning] 易错点

长度不等先 return。一维压缩时 dp[0] 每行开头要单独更新（只依赖 s1）。dp[j]（上）和 dp[j-1]（左）分别对应 s1/s2 匹配。

72. 编辑距离

word1 变成 word2 的最少操作（增/删/改）次数。

思路脉络：dp[i][j] = w1 前 i 变 w2 前 j 的最少操作。字符相同 dp[i-1][j-1]；不同取删/增/改三方向 min+1。边界 dp[i][0]=i、dp[0][j]=j。和热题 100 相同。

class Solution {
    public int minDistance(String w1, String w2) {
        int m = w1.length(), n = w2.length();
        int[] dp = new int[n + 1];
        for (int j = 0; j <= n; j++) dp[j] = j;
        for (int i = 1; i <= m; i++) {
            int prev = dp[0]; dp[0] = i;                       // dp[i][0] = i
            for (int j = 1; j <= n; j++) {
                int tmp = dp[j];
                if (w1.charAt(i - 1) == w2.charAt(j - 1)) dp[j] = prev;
                else dp[j] = Math.min(Math.min(dp[j], dp[j - 1]), prev) + 1;
                prev = tmp;
            }
        }
        return dp[n];
    }
}

[!info] 复杂度
时间 O(mn)，空间 O(n)。

[!warning] 易错点

一维压缩时 dp[i-1][j-1]（左上角）会被 dp[j-1] 覆盖，用 prev 暂存上一轮的 dp[j-1]（即对角线值）。删/增/改分别对应 dp[j]/dp[j-1]/prev。

思路脉络：4 状态 DP。buy1/sell1 = 第 1 次买/卖后的最大收益，buy2/sell2 = 第 2 次。状态转移：buy1 = max(buy1, -price)、sell1 = max(sell1, buy1+price)、buy2 = max(buy2, sell1-price)、sell2 = max(sell2, buy2+price)。

class Solution {
    public int maxProfit(int[] prices) {
        int buy1 = Integer.MIN_VALUE, sell1 = 0, buy2 = Integer.MIN_VALUE, sell2 = 0;
        for (int p : prices) {
            buy1 = Math.max(buy1, -p);
            sell1 = Math.max(sell1, buy1 + p);
            buy2 = Math.max(buy2, sell1 - p);
            sell2 = Math.max(sell2, buy2 + p);
        }
        return sell2;
    }
}

[!info] 复杂度
时间 O(n)，空间 O(1)。

[!warning] 易错点

buy 初值 MIN_VALUE（表示还没买，取 max 后第一次会变成 -p）。buy2 依赖 sell1（第二次买要在第一次卖后），状态顺序不能乱。

188. 买卖股票的最佳时机 IV

最多 k 次买卖，求最大利润。

思路脉络：buy[j]/sell[j] = 第 j 次买/卖后最大收益。遍历每天，更新 1…k 次。buy[j] = max(buy[j], sell[j-1]-price)、sell[j] = max(sell[j], buy[j]+price)。k ≥ n/2 时退化成无限次（贪心）。

class Solution {
    public int maxProfit(int k, int[] prices) {
        int n = prices.length;
        if (k >= n / 2) return infinite(prices);
        int[] buy = new int[k + 1], sell = new int[k + 1];
        Arrays.fill(buy, Integer.MIN_VALUE);
        for (int p : prices)
            for (int j = 1; j <= k; j++) {
                buy[j] = Math.max(buy[j], sell[j - 1] - p);
                sell[j] = Math.max(sell[j], buy[j] + p);
            }
        return sell[k];
    }
    int infinite(int[] prices) {
        int ans = 0;
        for (int i = 1; i < prices.length; i++) if (prices[i] > prices[i - 1]) ans += prices[i] - prices[i - 1];
        return ans;
    }
}

[!info] 复杂度
时间 O(nk)，空间 O(k)。

[!warning] 易错点

k >= n/2 时退化为无限次买卖（每天最多一次买卖，k 超过这个上限没意义），用贪心累加所有上升段。buy[j] 依赖 sell[j-1]（第 j 次买要在第 j-1 次卖后）。

221. 最大正方形

0/1 矩阵里只含 1 的最大正方形面积。

思路脉络：dp[i][j] = 以 (i,j) 为右下角的最大全 1 正方形边长。dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1（当 matrix[i][j]=='1'）。三者 min + 1 保证能扩成正方形。

class Solution {
    public int maximalSquare(char[][] matrix) {
        int m = matrix.length, n = matrix[0].length, max = 0, prev = 0;
        int[] dp = new int[n + 1];
        for (int i = 1; i <= m; i++)
            for (int j = 1; j <= n; j++) {
                int tmp = dp[j];
                if (matrix[i - 1][j - 1] == '1') {
                    dp[j] = Math.min(Math.min(dp[j], dp[j - 1]), prev) + 1;
                    max = Math.max(max, dp[j]);
                } else dp[j] = 0;
                prev = tmp;
            }
        return max * max;
    }
}

[!info] 复杂度
时间 O(mn)，空间 O(n)。

[!warning] 易错点

一维压缩时 dp[i-1][j-1]（左上角）会被覆盖，用 prev 暂存。dp[j]（上）、dp[j-1]（左）、prev（左上）三者 min + 1。返回面积 max*max。

面试经典 150 题 · Java 题解

题型分布

目录

1. 数组 / 字符串

2. 双指针

3. 滑动窗口

4. 矩阵

5. 哈希表

6. 区间

7. 栈

8. 链表

9. 二叉树

10. 二叉搜索树

11. 图

12. 字典树

13. 回溯

14. 分治

15. Kadane 算法

16. 二分查找

17. 堆

18. 位运算