cswork / 模板打开 500 路题单

500 路 · 35 站 · Java

代码模板手册：Java

每站一节：模式、复杂度、3 条要点、3 个易错点和 Java 模板。每份模板都编译运行过，并用测试数据核对了输出。打印时每组从新的一页开始；在打印对话框里选「存储为 PDF」就能存成文件。

cswork.org/topics

读写双指针原地压缩 · 时间 O(n) · 空间 O(1)

要点

  1. 写指针 w 左边是已经确定保留的结果；读指针只往前扫，两个指针都只走一遍。
  2. 判断能不能保留时和 nums[w-k] 比，也就是和「结果」比，而不是和上一个读到的原始元素比。
  3. 原地合并两个有序数组时从尾部往前写，就不会覆盖还没读到的数据。

易错点

  • 题目要的是新长度，判题只看前 k 个位置；返回数组本身或者去比较 k 之后的内容都会出错。
  • 边遍历边删除（Python 的 list.remove、Java 的 ArrayList.remove）是 O(n²)，还会跳过元素。
  • 排序比较器写成 a - b，值接近 ±2^31 时会溢出；用 Integer.compare 或直接比较大小。
class Solution {
    // Sorted nums: keep each value at most k times, in place. Returns the new length.
    int keepAtMost(int[] nums, int k) {
        int w = 0; // nums[0, w) is the kept prefix
        for (int x : nums)
            if (w < k || nums[w - k] != x) nums[w++] = x;
        return w;
    }
}

边扫边查的哈希表 · 时间 O(n) · 空间 O(n)

要点

  1. 先查补数、再存自己：一遍扫描就能找到「之前出现过」的配对，也不会把同一个元素用两次。
  2. 存什么取决于问什么：要位置就存下标，要个数就存次数，要最早出现的位置就只在第一次出现时存。
  3. 键可以组合出来：排序后的字符串、计数元组、(行, 值) 对，都能把「同一类」放进同一个桶。

易错点

  • 先插入再查询，target 恰好等于 2x 时会把同一个元素和自己配成一对。
  • C++ 的 map[key] 读一个不存在的键会插入默认值；只想判断存在时用 find 或 count。
  • Java 里两个 Integer 用 == 比较，超过 127 时可能不相等；用 equals 或先拆箱成 int。
class Solution {
    int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> seen = new HashMap<>(); // value -> index of an earlier element
        for (int i = 0; i < nums.length; i++) {
            Integer j = seen.get(target - nums[i]); // look up before inserting: no self-pairing
            if (j != null) return new int[] {j, i};
            seen.put(nums[i], i);
        }
        return new int[] {-1, -1};
    }
}

KMP 前缀函数匹配 · 时间 O(n + m) · 空间 O(m)

要点

  1. pi[i] 是 pat[0..i] 中「既是真前缀又是真后缀」的最长长度；失配时 j 退回 pi[j-1]，文本指针从不回头。
  2. 建 pi 表和在文本里匹配是同一段循环：建表就是模式串和自己匹配。
  3. 解析类题目用一个下标手动往前读数字、符号和括号，边界比 split 好处理。

易错点

  • 匹配成功后要令 j = pi[j-1] 继续，否则会漏掉重叠出现（"aaaa" 里的 "aa" 出现 3 次）。
  • 在循环里用 + 拼字符串是 O(n²)；Python 先收集到列表再 join，Java 用 StringBuilder。
  • Go 里 s[i] 是字节、len(s) 是字节数；处理中文等多字节字符要先转成 []rune。
class Solution {
    // Start index of every occurrence of a non-empty pat in text.
    List<Integer> findAll(String text, String pat) {
        int m = pat.length();
        int[] pi = new int[m]; // pi[i]: longest proper border of pat[0..i]
        for (int i = 1, j = 0; i < m; i++) {
            while (j > 0 && pat.charAt(i) != pat.charAt(j)) j = pi[j - 1];
            if (pat.charAt(i) == pat.charAt(j)) j++;
            pi[i] = j;
        }
        List<Integer> res = new ArrayList<>();
        for (int i = 0, j = 0; i < text.length(); i++) {
            while (j > 0 && text.charAt(i) != pat.charAt(j)) j = pi[j - 1];
            if (text.charAt(i) == pat.charAt(j)) j++;
            if (j == m) {
                res.add(i - m + 1);
                j = pi[j - 1]; // keep going: matches may overlap
            }
        }
        return res;
    }
}

可变长度滑动窗口 · 时间 O(n) · 空间 O(Σ)

要点

  1. 右端每步前进一格，左端只在窗口不合法时收缩；两个指针都只前进，总共 O(n)。
  2. 求最长窗口：收缩完再更新答案；求最短窗口：在「仍然合法」的收缩循环里更新答案。
  3. 有序数组上求两数之和、去重、反转用相向双指针；判环、找中点用快慢指针。

易错点

  • 收缩时忘了把移出窗口的元素计数减一，窗口状态就和实际内容对不上。
  • 数组里有负数时，「和超过 k 就收缩」不再单调，滑动窗口失效，要改用前缀和。
  • 「恰好 k 个」很难直接滑，用「至多 k 个」减去「至多 k-1 个」。
class Solution {
    // Length of the longest substring without repeated characters.
    int longestUnique(String s) {
        Map<Character, Integer> cnt = new HashMap<>(); // counts inside the window s[left..right]
        int left = 0, best = 0;
        for (int right = 0; right < s.length(); right++) {
            char c = s.charAt(right);
            cnt.merge(c, 1, Integer::sum);
            while (cnt.get(c) > 1) cnt.merge(s.charAt(left++), -1, Integer::sum); // shrink
            best = Math.max(best, right - left + 1);
        }
        return best;
    }
}

前缀和 + 哈希计数 · 时间 O(n) · 空间 O(n)

要点

  1. 区间和等于两个前缀和之差：sum(l..r) = pre[r+1] - pre[l]；前缀数组多开一位，pre[0] = 0。
  2. 统计「和为 k 的子数组」时，哈希表先放 {0: 1}，代表从下标 0 开始的子数组。
  3. 多次区间加值用差分数组：diff[l] += v，diff[r+1] -= v，最后求一遍前缀和；合并区间先按左端点排序。

易错点

  • 忘了放 {0: 1}，会漏掉所有从下标 0 开始的子数组。
  • 前缀和很容易超过 32 位整数，C++ 用 long long，Java 用 long。
  • 先把当前前缀和存进表再查询，k = 0 时会把空子数组也算进去。
class Solution {
    // Number of non-empty subarrays whose sum is k (negatives allowed).
    int countSubarrays(int[] nums, int k) {
        Map<Long, Integer> seen = new HashMap<>(); // prefix sum -> occurrences
        seen.put(0L, 1); // the empty prefix
        long pre = 0;
        int ans = 0;
        for (int x : nums) {
            pre += x;
            ans += seen.getOrDefault(pre - k, 0); // sum(j..i) = pre_i - pre_j
            seen.merge(pre, 1, Integer::sum);
        }
        return ans;
    }
}

单调栈：下一个更大元素 · 时间 O(n) · 空间 O(n)

要点

  1. 栈里存下标而不是值：既能取到值，也能算距离（比如「还要等几天才升温」）。
  2. 每个元素只进栈、出栈各一次，所以虽然套了 while，总复杂度仍是 O(n)。
  3. 求前 k 大用大小为 k 的小根堆；滑动窗口最值用单调双端队列，队头过期就弹出。

易错点

  • 有重复值时 < 和 <= 结果不同，先想清楚要「严格更大」还是「大于等于」。
  • Python 的 heapq 只有小根堆，要大根堆就存相反数。
  • Java 的 Stack 类又慢又是同步的，栈和队列都用 ArrayDeque；比较器不要写成 a - b。
class Solution {
    // For each i, the first value to the right that is strictly greater, or -1.
    int[] nextGreater(int[] nums) {
        int[] ans = new int[nums.length];
        Arrays.fill(ans, -1);
        Deque<Integer> st = new ArrayDeque<>(); // indexes still waiting; values decrease to the top
        for (int i = 0; i < nums.length; i++) {
            while (!st.isEmpty() && nums[st.peek()] < nums[i]) ans[st.pop()] = nums[i];
            st.push(i);
        }
        return ans;
    }
}

按结束时间排序选区间 · 时间 O(n log n)

要点

  1. 总是选结束最早的区间，给后面留的空间最多。交换论证：任何最优解的第一个区间都能换成它而不变差。
  2. 最少删除数 = 总数 - 最多保留数；「最少几支箭」也是同一个循环，只是端点相接也算重叠。
  3. 写贪心之前先说清楚「为什么局部最优不吃亏」；说不清楚时，多半要换成动态规划。

易错点

  • 按开始时间排序再贪心，会被一个开始很早、持续很长的区间卡住。
  • 端点相接算不算重叠由题意决定：>= 和 > 只差一个字符，答案就不一样。
  • 比较器写成 a[1] - b[1]，端点接近 ±2^31 时会溢出。
class Solution {
    // Most intervals you can keep with no overlap; [a, b] and [b, c] may touch.
    int maxNonOverlapping(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[1], b[1]));
        int count = 0;
        long end = Long.MIN_VALUE;
        for (int[] iv : intervals)
            if (iv[0] >= end) { // fits after the last kept interval
                count++;
                end = iv[1];
            }
        return count;
    }
}

反转链表 + 快慢指针 · 时间 O(n) · 空间 O(1)

要点

  1. 改指针之前先存下 next。反转只有三步：存 next、指回前驱、整体前移。
  2. 头结点可能被删除或替换时，先建一个哑结点 dummy 指向 head，最后返回 dummy.next。
  3. 快指针一次两步、慢指针一次一步，用来找中点和判环；找倒数第 k 个结点则让前指针先走 k 步，再和后指针同速前进。

易错点

  • 先改了 head.next 再去取 next，后面的链表就丢了。
  • 访问 fast.next.next 之前要确认 fast 和 fast.next 都不为空。
  • 把链表拆成两段后忘了把前半段的尾部置空，合并或遍历时会成环。
class ListNode {
    int val;
    ListNode next;

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

class Solution {
    ListNode reverse(ListNode head) {
        ListNode prev = null;
        while (head != null) {
            ListNode nxt = head.next; // save it before rewiring
            head.next = prev;
            prev = head;
            head = nxt;
        }
        return prev;
    }

    // Middle node; the second of the two middles for even lengths.
    ListNode middle(ListNode head) {
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
}

按层 BFS · 时间 O(n) · 空间 O(最大层宽)

要点

  1. 每一轮先记下队列长度，正好处理这么多个结点，层与层就分开了。
  2. 写递归 DFS 前先想清楚「子树返回什么」：深度、是否平衡、结点数，都是把左右两边的结果合并。
  3. 前序、中序、后序的区别只在于「处理当前结点」放在两次递归的前面、中间还是后面。

易错点

  • 用一直在变化的队列长度当循环上界，会把下一层的结点也算进这一层。
  • Python 用 list.pop(0) 当队列是 O(n) 的，要用 collections.deque。
  • 树退化成链时递归深度能到 10^5，Python 会爆栈；改成迭代或调高 recursionlimit。
class TreeNode {
    int val;
    TreeNode left, right;

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class Solution {
    List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> levels = new ArrayList<>();
        Deque<TreeNode> q = new ArrayDeque<>();
        if (root != null) q.offer(root);
        while (!q.isEmpty()) {
            List<Integer> level = new ArrayList<>();
            for (int k = q.size(); k > 0; k--) { // exactly the nodes of this level
                TreeNode node = q.poll();
                level.add(node.val);
                if (node.left != null) q.offer(node.left);
                if (node.right != null) q.offer(node.right);
            }
            levels.add(level);
        }
        return levels;
    }
}

后序返回单边贡献，全局记录拐弯路径 · 时间 O(n) · 递归栈 O(h)

要点

  1. 递归函数返回「从当前结点往下走的最好单边路径」，因为要继续往上接的路径只能选一边。
  2. 在当前结点拐弯的路径（左 + 根 + 右）只用来更新全局答案，不返回给父结点。
  3. 根到叶的路径题用「进入时加、离开时减」维护当前路径；任意起点的路径和用前缀和 + 哈希表。

易错点

  • 全局答案初始化成 0，所有值都是负数的树会得到错误的 0。
  • 子树贡献为负时要截成 0（这一边不接），否则会把答案拖低。
  • 把拐弯路径也返回给父结点，等于让一条路径分叉，结果会偏大。
class TreeNode {
    int val;
    TreeNode left, right;

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class Solution {
    private int best;

    // Largest sum of any non-empty path between two nodes.
    int maxPathSum(TreeNode root) {
        best = Integer.MIN_VALUE;
        gain(root);
        return best;
    }

    private int gain(TreeNode node) { // best downward path sum that starts at node
        if (node == null) return 0;
        int left = Math.max(gain(node.left), 0), right = Math.max(gain(node.right), 0);
        best = Math.max(best, node.val + left + right); // the path that bends at node
        return node.val + Math.max(left, right); // only one side continues upward
    }
}

前序定根，中序分左右 · 时间 O(n) · 空间 O(n)

要点

  1. 前序的第一个值是根；在中序里找到它，左边是左子树，右边是右子树。
  2. 用哈希表存「值 → 中序下标」，每次切分 O(1)，整体 O(n)。
  3. 按「先左后右」递归时，前序指针顺序往后取就是下一个根，不用计算子数组长度；后序 + 中序则从后往前取、先右后左。

易错点

  • 值有重复时中序位置不唯一，这个方法就不成立了。
  • 每层递归都切片复制数组（Python 切片、Java copyOfRange），会退化成 O(n²)。
  • 后序 + 中序时如果仍然先建左子树，取到的根的顺序就错了。
class TreeNode {
    int val;
    TreeNode left, right;

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class Solution {
    private int[] preorder;
    private int next; // preorder yields roots in exactly the order we build them
    private final Map<Integer, Integer> pos = new HashMap<>(); // value -> inorder index

    // Rebuild a tree with distinct values from its preorder and inorder walks.
    TreeNode buildTree(int[] preorder, int[] inorder) {
        this.preorder = preorder;
        next = 0;
        pos.clear();
        for (int i = 0; i < inorder.length; i++) pos.put(inorder[i], i);
        return build(0, inorder.length);
    }

    private TreeNode build(int lo, int hi) { // the subtree whose inorder range is [lo, hi)
        if (lo == hi) return null;
        TreeNode root = new TreeNode(preorder[next++]);
        int mid = pos.get(root.val);
        root.left = build(lo, mid); // left before right, matching preorder
        root.right = build(mid + 1, hi);
        return root;
    }
}

迭代中序：按顺序走 BST · 时间 O(h + k) · 空间 O(h)

要点

  1. BST 的中序遍历是升序的：第 k 小、验证 BST、找前驱后继，都能转成中序问题。
  2. 验证 BST 要把上下界 (lo, hi) 往下传，每个结点都必须落在祖先给出的开区间里。
  3. 查找和插入只走一条路径，复杂度是 O(h)：平衡时 O(log n)，退化成链时 O(n)。

易错点

  • 只拿结点和它的左右孩子比较，发现不了「右子树深处有比根还小的值」。
  • 用 INT_MIN / INT_MAX 当边界，结点值恰好是极值时会误判；用 long 或空值表示「无界」。
  • 迭代中序里忘了转向 node.right，会重复弹出同一批结点或者提前结束。
class TreeNode {
    int val;
    TreeNode left, right;

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class Solution {
    // 1-indexed; assumes 1 <= k <= number of nodes.
    int kthSmallest(TreeNode root, int k) {
        Deque<TreeNode> st = new ArrayDeque<>();
        TreeNode node = root;
        while (true) {
            for (; node != null; node = node.left) st.push(node); // go as far left as possible
            node = st.pop(); // the next value in sorted order
            if (--k == 0) return node.val;
            node = node.right;
        }
    }
}

多源 BFS，一步扩一圈 · O(行数 × 列数)

要点

  1. 所有起点一开始就一起入队，相当于从一个虚拟的超级源点出发；BFS 的层数就是最短距离。
  2. 入队时就标记已访问，同一个格子不会被重复加入。
  3. 只问连通块（岛屿个数、面积）时 DFS、BFS 都可以；问最少步数必须用 BFS。

易错点

  • 出队时才标记，同一个格子会被多个邻居重复入队，大网格上会超时。
  • 一开始就没有新鲜橘子时答案是 0，既不是 -1，也不是层数。
  • 递归 DFS 在 1000×1000 的网格上会爆栈；大网格用 BFS 或显式栈。
class Solution {
    // 0 empty, 1 fresh, 2 rotten. Minutes until nothing is fresh, or -1.
    int minutesToRot(int[][] grid) {
        int rows = grid.length, cols = grid[0].length, fresh = 0, minutes = 0;
        Deque<int[]> q = new ArrayDeque<>();
        for (int r = 0; r < rows; r++)
            for (int c = 0; c < cols; c++) {
                if (grid[r][c] == 2) q.offer(new int[] {r, c});
                if (grid[r][c] == 1) fresh++;
            }
        int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        while (!q.isEmpty() && fresh > 0) {
            minutes++;
            for (int k = q.size(); k > 0; k--) { // every rotten cell spreads one step this minute
                int[] cell = q.poll();
                for (int[] d : dirs) {
                    int nr = cell[0] + d[0], nc = cell[1] + d[1];
                    if (nr < 0 || nr >= rows || nc < 0 || nc >= cols || grid[nr][nc] != 1) continue;
                    grid[nr][nc] = 2; // mark when enqueued, not when popped
                    fresh--;
                    q.offer(new int[] {nr, nc});
                }
            }
        }
        return fresh > 0 ? -1 : minutes;
    }
}

并查集：路径压缩 + 按大小合并 · 每次操作约 O(α(n))

要点

  1. find 时做路径压缩，union 时把小树挂到大树下；两者一起用，单次操作几乎是常数时间。
  2. union 返回 false 说明两点本来就连通：无向图判环、找冗余连接都靠它。
  3. 连通块个数、块的大小这类信息只记在根上，合并时累加。

易错点

  • 用 parent[a] == parent[b] 判断连通是错的，必须比较 find(a) == find(b)。
  • 合并时写成 parent[a] = b，而不是把两个根连起来，会破坏树的结构。
  • 结点是字符串或坐标时，先映射成 0..n-1 的编号，或者用哈希表存 parent。
class DSU {
    private final int[] parent, size;
    int count; // number of components

    DSU(int n) {
        parent = new int[n];
        size = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            size[i] = 1;
        }
        count = n;
    }

    int find(int x) {
        while (parent[x] != x) x = parent[x] = parent[parent[x]]; // path halving
        return x;
    }

    boolean union(int a, int b) {
        a = find(a);
        b = find(b);
        if (a == b) return false; // already connected: this edge would close a cycle
        if (size[a] < size[b]) {
            int t = a;
            a = b;
            b = t;
        }
        parent[b] = a; // hang the smaller tree under the larger
        size[a] += size[b];
        count--;
        return true;
    }
}

Kahn 算法：入度为 0 的先出队 · O(V + E)

要点

  1. 入度为 0 的点没有未完成的前置依赖，可以先放；放下之后把它指向的点入度减一。
  2. 输出的点数少于 n，说明剩下的点都在环上：「能不能修完所有课」就是这样判断的。
  3. 要求字典序最小的拓扑序时，把队列换成小根堆。

易错点

  • 边的方向读反（「a 依赖 b」应该建 b → a），整个顺序就倒过来了。
  • 只把一开始入度为 0 的点入队，后面减到 0 的点忘了入队。
  • DFS 写拓扑排序时只有「访问过 / 没访问」两种状态是判不出环的，还需要「访问中」这第三种状态。
class Solution {
    // Edge {u, v} means u comes before v. Returns an empty list if there is a cycle.
    List<Integer> topoOrder(int n, int[][] edges) {
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) graph.add(new ArrayList<>());
        int[] indeg = new int[n];
        for (int[] e : edges) {
            graph.get(e[0]).add(e[1]);
            indeg[e[1]]++;
        }
        Deque<Integer> q = new ArrayDeque<>();
        for (int i = 0; i < n; i++) if (indeg[i] == 0) q.offer(i);
        List<Integer> order = new ArrayList<>();
        while (!q.isEmpty()) {
            int u = q.poll();
            order.add(u);
            for (int v : graph.get(u))
                if (--indeg[v] == 0) q.offer(v); // every prerequisite of v is placed
        }
        return order.size() == n ? order : new ArrayList<>();
    }
}

Dijkstra：堆 + 懒删除 · O((V + E) log V)

要点

  1. 每次从堆里取出当前距离最小的点，它的距离就确定了；前提是所有边权非负。
  2. 不做 decrease-key：直接把新距离压进堆，弹出时发现比 dist 大就跳过（懒删除）。
  3. 边权只有 0 和 1 时用双端队列 BFS；有负权用 Bellman-Ford；状态里带「已用次数」时，把 (点, 次数) 当成一个新结点。

易错点

  • 不跳过过期的堆元素，同一个点会被反复松弛，稠密图上会超时。
  • 距离累加超出 32 位整数；用 INT_MAX 当无穷大时，d + w 还会溢出成负数。
  • 有向图当成无向图建边（或者反过来），所有距离都会错。
class Solution {
    // Directed edges {u, v, w} with w >= 0. Unreachable nodes get -1.
    long[] dijkstra(int n, int[][] edges, int src) {
        List<List<int[]>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) graph.add(new ArrayList<>());
        for (int[] e : edges) graph.get(e[0]).add(new int[] {e[1], e[2]});
        long[] dist = new long[n];
        Arrays.fill(dist, Long.MAX_VALUE);
        PriorityQueue<long[]> pq = new PriorityQueue<>((a, b) -> Long.compare(a[0], b[0]));
        dist[src] = 0;
        pq.offer(new long[] {0, src});
        while (!pq.isEmpty()) {
            long[] top = pq.poll();
            long d = top[0];
            int u = (int) top[1];
            if (d > dist[u]) continue; // stale entry: u was settled with a shorter distance
            for (int[] e : graph.get(u))
                if (d + e[1] < dist[e[0]]) {
                    dist[e[0]] = d + e[1];
                    pq.offer(new long[] {dist[e[0]], e[0]});
                }
        }
        for (int i = 0; i < n; i++) if (dist[i] == Long.MAX_VALUE) dist[i] = -1;
        return dist;
    }
}

Kruskal：按边权排序 + 并查集 · O(E log E)

要点

  1. 按边权从小到大看每条边：能连起两个不同连通块就选，否则跳过（选了会成环）。
  2. 选够 n-1 条边就是一棵生成树；最后不够 n-1 条，说明图不连通。
  3. 点少边多的稠密图（比如坐标点两两相连）用 O(n²) 的 Prim，往往比给所有边排序更快。

易错点

  • 没检查是否连通，直接返回累加的边权。
  • 坐标点两两连边有 n²/2 条，内存和排序时间都可能超限。
  • 点的编号从 1 开始，并查集却只开了 n 个位置。
class Solution {
    private int[] parent;

    // Undirected edges {u, v, w}. Weight of a minimum spanning tree, or -1 if disconnected.
    long mstWeight(int n, int[][] edges) {
        Arrays.sort(edges, (a, b) -> Integer.compare(a[2], b[2]));
        parent = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;
        long total = 0;
        int used = 0;
        for (int[] e : edges) {
            int ru = find(e[0]), rv = find(e[1]);
            if (ru == rv) continue; // would close a cycle
            parent[ru] = rv;
            total += e[2];
            used++;
        }
        return used == n - 1 ? total : -1;
    }

    private int find(int x) {
        while (parent[x] != x) x = parent[x] = parent[parent[x]];
        return x;
    }
}

选择、递归、撤销；同层跳过重复 · O(n · 2^n)

要点

  1. 模板只有三步：做选择、递归、撤销选择；path 是整个搜索共用的一份。
  2. 先排序，再用 i > start && nums[i] == nums[i-1] 跳过：同一层不重复选相同的值，更深的层可以。
  3. 组合从 start 往后选，避免 {1,2} 和 {2,1} 同时出现；排列每次从头选，用 used 数组标记。

易错点

  • 结果里直接存 path 的引用，回溯结束后所有结果都变成同一个空列表。
  • 把 i > start 写成 i > 0，更深层里合法的重复值也会被跳过。
  • 忘了先排序，相同的值不相邻，去重判断就失效了。
class Solution {
    private final List<List<Integer>> res = new ArrayList<>();
    private final List<Integer> path = new ArrayList<>();
    private int[] nums;

    List<List<Integer>> subsetsWithDup(int[] nums) {
        this.nums = nums.clone();
        Arrays.sort(this.nums); // equal values become neighbours
        res.clear();
        dfs(0);
        return res;
    }

    private void dfs(int start) {
        res.add(new ArrayList<>(path)); // copy: path keeps changing
        for (int i = start; i < nums.length; i++) {
            if (i > start && nums[i] == nums[i - 1]) continue; // already tried at this level
            path.add(nums[i]);
            dfs(i + 1);
            path.remove(path.size() - 1); // undo the choice
        }
    }
}

按切分点回溯 + 回文预处理 · O(n · 2^n)

要点

  1. 回溯的每一层决定「下一段切到哪里」，start 走到 n 就得到一种完整的切法。
  2. 先用 O(n²) 的区间 DP 算出每个子串是不是回文，回溯里的判断就是 O(1)。
  3. 复原 IP 地址、单词拆分也是同一个框架，只是「这一段是否合法」的判断不同。

易错点

  • 在回溯里每次都重新用双指针判断回文，重复计算会让常数大很多。
  • 只要求方案数或最少切几刀时，不要枚举，改用 DP。
  • 子串下标是左闭右开还是左闭右闭要统一；s[start:end+1] 和 substring(start, end+1) 很容易差一位。
class Solution {
    private final List<List<String>> res = new ArrayList<>();
    private final List<String> path = new ArrayList<>();
    private boolean[][] pal; // pal[i][j]: s[i..j] is a palindrome
    private String s;

    // Every way to cut s into palindromes.
    List<List<String>> partition(String s) {
        int n = s.length();
        this.s = s;
        pal = new boolean[n][n];
        for (int i = n - 1; i >= 0; i--)
            for (int j = i; j < n; j++)
                pal[i][j] = s.charAt(i) == s.charAt(j) && (j - i < 2 || pal[i + 1][j - 1]);
        res.clear();
        dfs(0);
        return res;
    }

    private void dfs(int start) {
        if (start == s.length()) {
            res.add(new ArrayList<>(path));
            return;
        }
        for (int end = start; end < s.length(); end++) // the next piece is s[start..end]
            if (pal[start][end]) {
                path.add(s.substring(start, end + 1));
                dfs(end + 1);
                path.remove(path.size() - 1);
            }
    }
}

N 皇后：按列和两条对角线剪枝 · 最坏 O(n!)

要点

  1. 每行只放一个皇后，搜索树只在列上分叉；列、主对角线 r-c、副对角线 r+c 各用一个数组标记。
  2. 剪枝越早越好：递归之前就判断冲突，而不是放满整个棋盘再检查。
  3. 数独、组合总和这类题先排序，在「剩下的值已经不可能满足」时用 break，比 continue 省得多。

易错点

  • 主对角线下标 r-c 会是负数，要加上 n-1 的偏移。
  • 回溯返回前忘了把标记改回去，后面的分支全被误剪。
  • 需要输出棋盘时，用可变的字符数组逐格修改，最后再转字符串，不要每一步都复制整盘。
class Solution {
    private boolean[] cols, diag, anti;
    private int n;

    // Number of ways to place n non-attacking queens on an n x n board.
    int totalQueens(int n) {
        this.n = n;
        cols = new boolean[n];
        diag = new boolean[2 * n - 1];
        anti = new boolean[2 * n - 1];
        return place(0);
    }

    private int place(int r) {
        if (r == n) return 1;
        int count = 0;
        for (int c = 0; c < n; c++) {
            int d = r - c + n - 1; // shift r - c into 0..2n-2
            if (cols[c] || diag[d] || anti[r + c]) continue; // attacked: prune this branch
            cols[c] = diag[d] = anti[r + c] = true;
            count += place(r + 1);
            cols[c] = diag[d] = anti[r + c] = false; // undo
        }
        return count;
    }
}

一维 DP + 滚动变量 · 时间 O(n) · 空间 O(1)

要点

  1. 先用一句话定义状态，比如 dp[i] = 只看前 i 个元素时的最优值；状态说清楚了，转移通常就出来了。
  2. 转移只看「最后一步做了什么」：第 i 个选还是不选，最后一跳是 1 步还是 2 步。
  3. dp[i] 只依赖前一两项时，用两个变量滚动，空间从 O(n) 降到 O(1)。

易错点

  • dp 和输入的下标错位：dp 多开一位时 dp[0] 表示「什么都没选」，答案在 dp[n]。
  • 滚动更新时先覆盖了 prev1 再拿它算新值，用到的已经是新数据了。
  • 方案数很快会超出 64 位；题目要求取模时，每一步都要取模。
class Solution {
    // Largest sum of elements with no two adjacent.
    long rob(int[] nums) {
        long prev2 = 0, prev1 = 0; // best totals up to i-2 and up to i-1
        for (int x : nums) {
            long cur = Math.max(prev1, prev2 + x); // skip x, or take it after i-2
            prev2 = prev1;
            prev1 = cur;
        }
        return prev1;
    }
}

网格 DP 压成一行 · 时间 O(行数 × 列数) · 空间 O(列数)

要点

  1. dp[r][c] 只依赖上方和左方，按行从左到右填，一行数组就够：更新前 dp[c] 是上方，dp[c-1] 是左方。
  2. 第一行、第一列只有一个来源，要么单独处理，要么用无穷大哨兵统一写法。
  3. 路径计数就把 min 换成加法；有障碍的格子直接置 0。

易错点

  • 哨兵用 INT_MAX 再加上格子值会溢出，要保证只在有限值上做加法。
  • 允许往四个方向走时没有填表顺序，DP 不成立，要用 BFS 或 Dijkstra。
  • 压成一行之后，如果转移还需要左上角的值，要在它被覆盖前先存到变量里。
class Solution {
    // Cheapest path from top-left to bottom-right moving only right or down.
    int minPathSum(int[][] grid) {
        int cols = grid[0].length;
        int[] dp = new int[cols]; // before row r is filled, dp[c] holds row r-1
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        for (int[] row : grid)
            for (int c = 0; c < cols; c++) {
                int best = c > 0 ? Math.min(dp[c], dp[c - 1]) : dp[c]; // from above or the left
                dp[c] = best + row[c]; // best is always finite here
            }
        return dp[cols - 1];
    }
}

0/1 背包倒序，完全背包正序 · O(n × target)

要点

  1. 0/1 背包倒序遍历容量，保证 dp[s-x] 还是「没用过 x」的旧值；完全背包正序遍历，允许同一件物品重复使用。
  2. 物品在外层、容量在内层，数的是组合（不计顺序）；容量在外层、物品在内层，数的是排列。
  3. 很多题要先转化成背包：「分成两个和相等的子集」= 能否凑出 sum/2；「目标和」= 凑出 (sum+target)/2。

易错点

  • 0/1 背包写成正序，同一件物品会被用很多次。
  • 计数问题 dp[0] = 1（什么都不选也是一种方案）；求最值问题 dp[0] = 0，其余初始化为无穷。
  • 转化成 (sum+target)/2 之前没检查奇偶性和正负，会得到错误的下标。
class Solution {
    // Ways to pick a subset (each item at most once) that sums to target.
    long countSubsets(int[] nums, int target) {
        long[] dp = new long[target + 1]; // dp[s]: ways to reach sum s
        dp[0] = 1;
        for (int x : nums)
            for (int s = target; s >= x; s--) dp[s] += dp[s - x]; // backwards: x used at most once
        return dp[target];
    }

    // Ways to make amount with unlimited coins, order ignored.
    long countCombinations(int[] coins, int amount) {
        long[] dp = new long[amount + 1];
        dp[0] = 1;
        for (int coin : coins) // coins outside: each multiset is counted once
            for (int s = coin; s <= amount; s++) dp[s] += dp[s - coin]; // forwards: reuse allowed
        return dp[amount];
    }
}

LIS：tails 数组 + 二分 · O(n log n)

要点

  1. tails[k] 是长度为 k+1 的递增子序列可能的最小结尾；它本身是递增的，所以可以二分。
  2. 严格递增用 lower_bound（第一个 ≥ x），非递减用 upper_bound（第一个 > x）。
  3. 二维的「信封嵌套」先按宽升序、宽相同时按高降序排序，再对高做 LIS。

易错点

  • tails 数组不是真实存在的最长子序列，只有长度是对的；要输出方案得另外记录前驱。
  • 严格和非严格用错了二分函数，重复元素多的用例会差 1 甚至更多。
  • 要求「最长子序列有几个」时，O(n log n) 写法不够，要回到 O(n²) 的 dp 加计数数组。
class Solution {
    // Length of the longest strictly increasing subsequence.
    int lisLength(int[] nums) {
        int[] tails = new int[nums.length]; // tails[k]: smallest tail of length k+1
        int len = 0;
        for (int x : nums) {
            int lo = 0, hi = len; // first index with tails[i] >= x (use > for non-decreasing)
            while (lo < hi) {
                int mid = (lo + hi) >>> 1;
                if (tails[mid] >= x) hi = mid;
                else lo = mid + 1;
            }
            tails[lo] = x;
            if (lo == len) len++;
        }
        return len;
    }
}

双串 DP：dp[i][j] 看两个前缀 · O(m × n)

要点

  1. dp[i][j] 定义在前缀上：a 的前 i 个字符和 b 的前 j 个字符；多开一行一列表示空串。
  2. 末尾字符相等就继承 dp[i-1][j-1]；不相等时，替换、删除、插入分别对应左上、上、左三个格子。
  3. 最长公共子序列、不同的子序列、通配符匹配都是这张表，只是转移不同。

易错点

  • dp 的下标是前缀长度，对应的字符是 a[i-1]；写成 a[i] 会错一位。
  • 忘了初始化第 0 行和第 0 列（变成空串需要删 i 次，从空串变来需要插 j 次）。
  • 压成一行时，左上角的值会被本行覆盖，需要额外一个变量保存。
class Solution {
    int editDistance(String a, String b) {
        int m = a.length(), n = b.length();
        // dp[i][j]: edits to turn a[0, i) into b[0, j); row 0 and column 0 are the empty prefixes
        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 (a.charAt(i - 1) == b.charAt(j - 1)) dp[i][j] = dp[i - 1][j - 1];
                else // replace, delete, insert
                    dp[i][j] = 1 + Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1]));
        return dp[m][n];
    }
}

区间 DP：左端点倒序枚举 · O(n²)

要点

  1. dp[i][j] 只依赖更短的区间 dp[i+1][*] 和 dp[*][j-1]，所以 i 倒序、j 正序填表。
  2. 两端字符相等就向内收缩并加 2，否则去掉一端，取两种情况的较大值。
  3. 只问回文子串（必须连续）时，中心扩展法 O(n²) 时间、O(1) 空间，更简单。

易错点

  • i 正序枚举时 dp[i+1][*] 还没有算出来，结果全错。
  • 子序列（可以不连续）和子串（必须连续）是两道题，转移不能混用。
  • 中心扩展要同时试奇数中心 (i, i) 和偶数中心 (i, i+1)。
class Solution {
    int longestPalSubseq(String s) {
        int n = s.length();
        if (n == 0) return 0;
        int[][] dp = new int[n][n]; // dp[i][j]: answer for s[i..j]
        for (int i = n - 1; i >= 0; i--) { // i backwards so dp[i+1][*] is ready
            dp[i][i] = 1;
            for (int j = i + 1; j < n; j++)
                dp[i][j] = s.charAt(i) == s.charAt(j)
                        ? dp[i + 1][j - 1] + 2
                        : Math.max(dp[i + 1][j], dp[i][j - 1]);
        }
        return dp[0][n - 1];
    }
}

以 i 结尾的状态：同时记最大和最小 · 时间 O(n) · 空间 O(1)

要点

  1. 状态定义成「以 i 结尾」，连续子数组的转移就只有两种：接在前一段后面，或者从 i 重新开始。
  2. 乘法遇到负数时最大会变成最小，所以要同时维护最大和最小两个状态。
  3. 状态机 DP 就是给每个位置多设几个状态（持有 / 不持有、上一个选没选），把状态之间的每条转移都写出来。

易错点

  • 先更新了 hi 再用新的 hi 去算 lo，用到的是同一轮已经改过的值。
  • 答案初始化成 0，全是负数的数组就会出错。
  • 最大子数组和（Kadane）的转移是 cur = max(x, cur + x)，不要漏掉「重新开始」这一项。
class Solution {
    // Largest product of a non-empty contiguous subarray.
    long maxProduct(int[] nums) {
        long hi = nums[0], lo = nums[0], best = nums[0]; // max and min product ending here
        for (int i = 1; i < nums.length; i++) {
            long x = nums[i], a = hi * x, b = lo * x; // a negative x swaps max and min
            hi = Math.max(x, Math.max(a, b)); // restart, or extend
            lo = Math.min(x, Math.min(a, b));
            best = Math.max(best, hi);
        }
        return best;
    }
}

持有 / 冷却 / 空仓三状态 · 时间 O(n) · 空间 O(1)

要点

  1. 先写清楚每天结束时可能处于哪几种状态，再写「昨天的哪种状态 + 今天的什么动作」能到达它。
  2. 同一天的几个新值都要用前一天的旧值计算，所以要同时赋值或者先存临时变量。
  3. 最多 k 次交易就加一维 k；手续费在每次卖出（或买入）时扣一次；只交易一次就是「记录历史最低价」。

易错点

  • 持有状态初始化成 0，相当于第 0 天白送了一股。
  • 用负无穷做初值时，C++ / Java 里 hold + p 会溢出；取 MIN / 2 这样的值。
  • 有冷却期时，买入只能从「空仓」状态转过来，不能从「刚卖出」状态直接买。
class Solution {
    // Unlimited trades, but after selling you must wait one day before buying.
    long maxProfitCooldown(int[] prices) {
        long hold = Long.MIN_VALUE / 2, cool = 0, free = 0; // profit at day end in each state
        for (int p : prices) {
            long h = Math.max(hold, free - p); // keep holding, or buy today (only from free)
            long c = hold + p; // sell today
            long f = Math.max(free, cool); // rest
            hold = h;
            cool = c;
            free = f;
        }
        return Math.max(cool, free);
    }
}

按结束时间排序 + 二分找上一个兼容任务 · O(n log n)

要点

  1. 按结束时间排序后，dp[i] = 前 i 个任务的最优值；第 i 个任务要么不选，要么接在最后一个不冲突的任务后面。
  2. 「最后一个不冲突的任务」在结束时间数组里二分查找，整体 O(n log n)。
  3. 「把数组分成 k 段」这类题，状态通常是 dp[段数][结尾位置]，转移时枚举最后一段从哪里开始。

易错点

  • 首尾相接算不算冲突，决定了用 upper_bound 还是 lower_bound。
  • 按开始时间排序、每次贪心选利润最高的，在带权的版本里不成立。
  • 排序时只排了结束时间，开始时间和利润没有跟着一起动。
class Solution {
    // Best total profit of non-overlapping jobs; a job may start when another ends.
    long maxProfit(int[] start, int[] end, int[] profit) {
        int n = start.length;
        Integer[] order = new Integer[n];
        for (int i = 0; i < n; i++) order[i] = i;
        Arrays.sort(order, (a, b) -> Integer.compare(end[a], end[b]));
        long[] dp = new long[n + 1]; // dp[i]: best using the first i jobs by end time
        for (int i = 0; i < n; i++) {
            int job = order[i];
            int lo = 0, hi = i; // k = number of earlier jobs that end by start[job]
            while (lo < hi) {
                int mid = (lo + hi) >>> 1;
                if (end[order[mid]] > start[job]) hi = mid;
                else lo = mid + 1;
            }
            dp[i + 1] = Math.max(dp[i], dp[lo] + profit[job]); // skip it, or take it after them
        }
        return dp[n];
    }
}

树形 DP：每个结点返回（选，不选） · O(n)

要点

  1. 树形 DP 用后序遍历：先拿到左右子树的结果，再算当前结点，每个结点返回一个小元组。
  2. 按「当前结点选不选」拆状态，比在父结点里往下看两层更简单，也不会重复计算。
  3. 两人博弈题常用「当前先手比对手多拿多少」作为状态：dp[i][j] = max(nums[i] - dp[i+1][j], nums[j] - dp[i][j-1])。

易错点

  • 不返回元组，而是用「祖父 + 孙子」的写法又不做记忆化，会指数级重复计算。
  • 不选当前结点时，孩子也不一定要选，每个孩子都要取 max(选, 不选)。
  • 博弈题如果按「我的得分」建状态，往往还得再记对手的得分；用差值更省事。
class TreeNode {
    int val;
    TreeNode left, right;

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class Solution {
    // Largest sum of node values with no parent-child pair both taken.
    long robTree(TreeNode root) {
        long[] r = dfs(root);
        return Math.max(r[0], r[1]);
    }

    private long[] dfs(TreeNode node) { // {best if node is taken, best if it is not}
        if (node == null) return new long[] {0, 0};
        long[] l = dfs(node.left), r = dfs(node.right);
        long take = node.val + l[1] + r[1]; // children must be skipped
        long skip = Math.max(l[0], l[1]) + Math.max(r[0], r[1]); // children are free to choose
        return new long[] {take, skip};
    }
}

惰性迭代器：hasNext 负责前进 · 每次调用均摊 O(1)

要点

  1. 把「跳过空行、走到下一个有效元素」放进 hasNext，next 只负责取值；这样连续调用多次 hasNext 也没有副作用。
  2. 只保存位置（行号、列号），不要在构造函数里把所有元素复制成一个大数组。
  3. 任意深度的嵌套列表用一个栈保存各层的位置；Python 里用生成器 yield from 最自然。

易错点

  • 中间或末尾有空行时，hasNext 只看下一行就会返回错误的 true。
  • next 里不先调用 hasNext，直接取值会越界。
  • 迭代过程中修改了原容器：Java 会抛 ConcurrentModificationException，其他语言则是悄悄出错。
// Iterates a list of lists in order, skipping empty rows.
class Flatten2D implements Iterator<Integer> {
    private final List<List<Integer>> rows;
    private int r = 0, c = 0;

    Flatten2D(List<List<Integer>> rows) {
        this.rows = rows;
    }

    @Override
    public boolean hasNext() {
        while (r < rows.size() && c == rows.get(r).size()) { // skip finished and empty rows
            r++;
            c = 0;
        }
        return r < rows.size();
    }

    @Override
    public Integer next() {
        if (!hasNext()) throw new NoSuchElementException();
        return rows.get(r).get(c++);
    }
}

LRU：哈希表 + 双向链表 · get 与 put 均为 O(1)

要点

  1. 哈希表负责 O(1) 找到结点，双向链表负责 O(1) 把结点移到头部、删除尾部。
  2. get 也算一次「使用」，要把结点移到最新的一端；put 一个已存在的键要更新值并移动，而不是再插一份。
  3. 面试要求手写链表时，用头尾两个哨兵结点，插入删除就不用判断空指针。

易错点

  • 淘汰尾结点时只删了链表、没删哈希表里的键（或者反过来）。
  • 先插入再淘汰还是先淘汰再插入要统一，并想清楚容量为 0 这种边界。
  • 链表结点里不存 key，淘汰时就不知道该删哈希表里的哪一项。
// LinkedHashMap in access order is a hash map over a doubly linked list.
class LRUCache extends LinkedHashMap<Integer, Integer> {
    private final int cap;

    LRUCache(int capacity) {
        super(16, 0.75f, true); // accessOrder = true: every get moves the entry to the end
        cap = capacity;
    }

    int get(int key) {
        return getOrDefault(key, -1);
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
        return size() > cap; // evict the least recently used after an insert
    }
}

字典树：结点存孩子和计数 · 每次操作 O(单词长度)

要点

  1. 每个结点代表一个前缀；插入和查询都是顺着字符往下走，耗时只和单词长度有关。
  2. 结点上存计数（有多少单词经过、有多少单词在此结束），前缀计数和删除都能 O(L) 完成。
  3. 序列化二叉树用前序遍历加空结点标记（如 "#"），反序列化时按同样的顺序递归读回来。

易错点

  • 把 search（完整单词）和 startsWith（前缀）混为一谈，忘了检查结束标记。
  • 固定 26 叉数组默认只有小写字母；有大写、数字或 Unicode 时，孩子改用哈希表存。
  • 序列化时值之间不加分隔符，多位数和负数就没法还原。
// Lowercase words.
class Trie {
    private final Trie[] next = new Trie[26];
    private int prefix, words; // words passing through / ending exactly here

    void insert(String word) {
        Trie node = this;
        for (char ch : word.toCharArray()) {
            int c = ch - 'a';
            if (node.next[c] == null) node.next[c] = new Trie();
            node = node.next[c];
            node.prefix++;
        }
        node.words++;
    }

    private Trie walk(String s) {
        Trie node = this;
        for (char ch : s.toCharArray()) {
            node = node.next[ch - 'a'];
            if (node == null) return null;
        }
        return node;
    }

    int countWord(String word) {
        Trie node = walk(word);
        return node == null ? 0 : node.words;
    }

    int countPrefix(String prefix) {
        Trie node = walk(prefix);
        return node == null ? 0 : node.prefix;
    }
}

位运算小工具与快速幂 · O(log n)

要点

  1. x & (x-1) 去掉最低位的 1，x & -x 取出最低位的 1；异或满足 a ^ a = 0，可以找出只出现一次的数。
  2. 快速幂把指数按二进制拆开：每轮把底数平方，指数这一位是 1 就乘进结果，O(log exp)。
  3. 不超过 20 个元素的集合可以用一个整数当掩码，for (s = mask; s; s = (s-1) & mask) 枚举它的所有非空子集。

易错点

  • 两个 10^9 量级的数相乘会超出 32 位，取模乘法之前先转成 long / long long。
  • Java 的 >> 会保留符号位，处理负数用无符号右移 >>>；Python 整数无限长，负数要先 & 0xFFFFFFFF。
  • C++ 里位运算优先级低于比较：x & 1 == 0 实际是 x & (1 == 0)，一定要加括号（Java 会直接编译报错）。
class Solution {
    // Set bits in x (Integer.bitCount does the same).
    int popcount(int x) {
        int count = 0;
        for (; x != 0; x &= x - 1) count++; // clear the lowest set bit
        return count;
    }

    // base^exp % mod by repeated squaring; mod < 2^31 keeps every product in a long.
    long powMod(long base, long exp, long mod) {
        long result = 1 % mod;
        for (base %= mod; exp > 0; exp >>= 1) {
            if ((exp & 1) == 1) result = result * base % mod;
            base = base * base % mod;
        }
        return result;
    }
}