综合演练

到最后一课,工具已经全部摆在台面上——binary search、DFS 与回溯、heap、动态规划、链表、HashMap、BST。而真实面试极少把题目的类别印在封面上。这节课是刻意为之的大杂烩:每一道题都把前面几课的两个或更多套路揉在一起,真正被操练的能力是分诊——读完题面,在写下第一行代码之前先说出它到底在考哪个工具。下面的题不是按故事分组,而是按它需要的技术分组,因为这个重组本身就是练习。

三种结构上的 Deep Copy

LC 138 Copy List with Random Pointer 是经典热身,因为它逼你把 deep 与 shallow 的区别摊开:shallow copy 解引用的是同一个 object,deep copy 在 heap 上重新分配一个全新对象,并重建每一根指针。麻烦在 random 指针,它可以指向任何地方——可能指向一个你还没复制的节点。

三种解法,巧劲递增:

• 两趟 HashMap——第一趟分配所有 copy 并记录 原节点 → copy;第二趟靠查表把 next 和 random 接上。O(n) 时间 O(n) 空间,天然正确。
• 一趟 HashMap——边走边接指针,遇到 random 目标还不存在时用 containsKey 按需先建出来。复杂度相同,只需一个循环。
• 穿插法,O(1) 额外空间——值得记住的巧招。把每个 copy 插在原节点后面,链表读作 A → A' → B → B' → …。于是一个节点的 copy 永远是 node.next,也就意味着 copy.random = node.random.next,一张 map 都不用。最后一趟拆链,把两条链表原地还原。

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

    // 1. 在每个原节点后穿插一个 copy:A -> A' -> B -> B' -> ...
    Node cur = head;
    while (cur != null) {
        Node copy = new Node(cur.val);
        copy.next = cur.next;
        cur.next  = copy;
        cur = copy.next;
    }
    // 2. 给 copy 接 random 指针(copy 就坐在 node.next)
    cur = head;
    while (cur != null) {
        if (cur.random != null) cur.next.random = cur.random.next;
        cur = cur.next.next;
    }
    // 3. 拆开两条交织的链表还原
    cur = head;
    Node copyHead = head.next;
    while (cur != null) {
        Node copy = cur.next;
        cur.next  = copy.next;
        copy.next = (copy.next != null) ? copy.next.next : null;
        cur = cur.next;
    }
    return copyHead;
}

同一副 deep copy 骨架可以推广:deep copy 一棵树就是带两个「next」指针的链表;deep copy 一张图(LC 133 Clone Graph)多了两个隐患——环,以及不连通分量。两者的解法都是一张以原节点引用为 key 的 HashMap:不重访已复制过的节点,每根 neighbor 指针在分配前先查 map。BFS 配 queue 或 DFS 配 recursion 都行;HashMap 才是把无限环游变成有限遍历的那个东西。

树:遍历之外的 BST 操作与结构手术

BST 其实就是穿着树外衣的 binary search——每次节点比较剪掉一棵子树,所以「找某个东西」的题只需要一条自顶向下的路径,不需要完整递归。

LC 270 Closest BST Value 把这点讲得很尖锐:递归 helper 能做,但既然只有一条 root 到 leaf 的路要走,一个 while (root != null) 的迭代下降、边走边记最接近值,反而更干净,O(h)。target < root.val 往左,否则往右。

LC 272 Closest K Values 抬高了门槛。暴力把 inorder 遍历当数组跑一个 top-k heap——O(k + (n−k) log k)。优雅解法用改写的 inorder 建两个栈:一个 predecessor 栈存 ≤ target 的值,一个 successor 栈存 > target 的值,各自惰性展开。然后就是 k-way merge——比较两个栈顶谁更近就 pop 谁,pop k 次。这套 predecessor/successor 机制,正是比 target 小的最大值和比 target 大的最小值需要的(LC 285 Inorder Successor in BST 是同一个下降);那里的经典陷阱是只有一个 root、没有左子、答案不存在的情况——closest 要用 Integer.MIN_VALUE 这样的哨兵初始化,而不是 root,否则会误返回 root。

插入与删除

LC 701 Insert into a BST 是简单那半:一直下降直到掉出树外,把新节点挂到那个空位(迭代循环,或递归里把 root.left/right 重新赋成返回的子树)。LC 450 Delete Node in a BST 是面试级的那半,而它的结构——递归下降、回溯时逐层重新赋子树——值得背下来。找到目标后有四种情况,收成三行:没有孩子或只有一个孩子,提升活着的那一侧;有两个孩子,把后继(右子树的最小值)复制到当前节点,再递归删掉那个后继。

public TreeNode deleteNode(TreeNode root, int key) {
    if (root == null) return null;

    if (key < root.val) {
        root.left = deleteNode(root.left, key);        // 递归,并重接子树
    } else if (key > root.val) {
        root.right = deleteNode(root.right, key);
    } else {                                          // 找到了
        if (root.left == null)  return root.right;      // 0/1 个孩子:提升另一侧
        if (root.right == null) return root.left;
        TreeNode min = findMin(root.right);         // 2 个孩子:把后继拉上来
        root.val = min.val;
        root.right = deleteNode(root.right, min.val);  // 再删掉那个后继
    }
    return root;
}

private TreeNode findMin(TreeNode node) {
    while (node.left != null) node = node.left;
    return node;
}

把链表翻转套用到树上

LC 156 Binary Tree Upside Down 是这组里的跨专题瑰宝:看着像树题,实则是把翻转链表套用在左脊上。给定一棵右节点永远是叶子兄弟的树,你沿左脊往下走,每一步让旧的左孩子把旧的右兄弟认作自己的左、把旧根认作自己的右——正是翻转链表里那套指针重接的舞步,同样有递归版和迭代版(pre / cur / next / tmp)。认出一道树题其实暗地里是链表题,就是全部的窍门。

区间 DP:在一条线上切与合

两道共享同一个递推形状的题——一个区间的答案由它在每个内部切点分裂出的子区间的答案拼起来。这是 matrix-chain-multiplication 家族,O(n³)。

切石头(Stone Cut):给定木棍上的切点,一刀的 cost 等于被切那段的长度,求最小总 cost。定义 dp[i][j] = 把切点 i 到 j 之间的段完全切完的最小 cost;转移先枚举每个内部切点 k:dp[i][j] = cost(i,j) + min over k ( dp[i][k] + dp[k][j] ),base case「没得切了」= 0。DP 之所以胜过朴素递归,靠的是共享的工作量——先切 1 再切 2 和先切 2 再切 1,留下的子段是一样的,记忆化抹掉这份重叠。

合并石子(Merge Stones,区间 DP 表亲,对应 LC 1000 Minimum Cost to Merge Stones)是镜像:反复合并相邻两堆,得分等于合并后的大小,求最小或最大总分。同样是 dp[i][j] 枚举内部切点 k,但「这次合并的 cost」是一段区间和,所以一个前缀和数组让它变 O(1):sum[j] − sum[i−1]。当石堆成环,标准操作是把数组翻倍(接一份 copy 到尾部),在翻倍后的长度上跑线性区间 DP——O((2n)³),但思路不变。要点:一见到「合并相邻、按大小付费」,就掏出区间 DP 加前缀和。

回溯精选集

一簇题目,全是同一副 DFS 骨架配不同剪枝。反复出现的设计问题是「每一层,我是选择要不要取第 i 个,还是选择下一个放谁?」——两种框法对同一个答案集会长出不同的树。

• LC 78 Subsets / LC 90 Subsets II——每个节点都是答案。干净的「下一个取谁」版本把每个候选加进去、从 i+1 递归;要在 Subsets II 里干掉重复,先排序再 if (i > start && nums[i] == nums[i-1]) continue;。另一种「取或不取」框法把答案放在叶子,在「不取」分支跳过一段相等值来去重;BFS/queue 版本也行,重复项落在连续块里,因为 queue 保序。
• LC 46 / LC 47 Permutations——原地 swap 模板:swap(index, i)、在 index+1 递归、再 swap 回来。有重复时要么排序后守 used[i-1],要么用每层的 seen 集合——while 配 i++ 的跳法会越界,所以用 continue。
• LC 20 / LC 22 括号——LC 20(合法性)是栈:压入期待的闭合符,任何不匹配或残留都失败。LC 22(生成 n 对)是带两个计数器的回溯:open < n 时加 (,close < open 时加 )。推广到 n 对 {} / [],或校验 XML/HTML 标签,都是同一套 open/close 记账,只是字母表更丰富。
• LC 322 / LC 518 Coin Change——DFS→DP 阶梯的招牌题,见下。
• LC 416 Partition Equal Subset Sum(「强盗分赃平分」)和 LC 51 / LC 52 N-Queens 补齐这组:subset-sum 是布尔背包;N-Queens 是带三个冲突集合(列、两条对角线)的 DFS——这引出一段小插曲:怎么快速查重。

public int coinChange(int[] coins, int amount) {
    int[] dp = new int[amount + 1];
    Arrays.fill(dp, amount + 1);   // 哨兵:不能用 MAX_VALUE,否则 dp[i-coin]+1 溢出
    dp[0] = 0;

    for (int i = 1; i <= amount; i++) {
        for (int coin : coins) {
            if (coin <= i) dp[i] = Math.min(dp[i], dp[i - coin] + 1);
        }
    }
    return dp[amount] == amount + 1 ? -1 : dp[amount];
}

这个进阶值得内化:朴素 DFS 对每个 amount 试每个 coin(指数级);在 amount 上记忆化剪掉重复(top-down);翻成 dp[i] = min(dp[i−coin] + 1) 就是自底向上。同一个递推,三种代价——面试官想看你爬这道阶梯。LC 518 Coin Change II(数组合方案数)重构了分支:一层一个币种、以「取几个」为分支,对比每个分支一个币种——两层循环的顺序决定了你数的是组合还是排列。

快速查重——回溯工具箱

回溯性能的一半在于你怎么回答「这个我用过了吗?」。从最省到最丰富的阶梯:小而固定的字母表用 boolean[k] 标志数组;想要 O(1) 成员判定又几乎不占空间时用位向量(一个 int,或几个 int 配 k/32 索引);任意值用 HashSet;需要计数或对象 key 时用 HashMap(也是 Trie 里的天然选择)。LC 318 Maximum Product of Word Lengths 是展示:把每个单词的字母编码成 26-bit mask,两个词无公共字母当且仅当 mask1 & mask2 == 0,把 O(k) 的逐字符比较变成一条机器指令;再按长度降序排、当拿不到更好乘积时剪枝,收尾。

隐式图上的 Heap + BFS

一类感觉像图搜索、却没有显式图的题——「节点」是你按需生成的 tuple,一个 min-heap 替你把顺序守住。配方永远是五步:定义 cost 函数、放入起点状态、扩展时压入邻居、poll 到第 k 个就停、用 seen 集合去重。

• f(x,y,z) = aˣ·bʸ·cᶻ 的第 k 小(ugly number 家族,参见 LC 264 / LC 313)——从 (0,0,0) 起,每次 poll 把 (x+1,y,z)、(x,y+1,z)、(x,y,z+1) 压进按 f 排序的 min-heap。空间无限,但到第 k 个就停。值会撞车,所以对指数 tuple 去重(把 tuple 编码或重写 equals)。时间 O(k · 4 log k),空间 O(k)。
• KD 空间里的 k 个最近点 / m 个有序数组里的 k 个最小和(LC 373 K Pairs with Smallest Sums)——同一个形状,cost 为 a[i]² + b[j]²(或坐标距离),扩展 (i+1,j)、(i,j+1)。同样要去重:两个不同的下标对可能落在同一个圆上。时间 O(k log k),空间 O(k)。
• LC 317 Shortest Distance from All Buildings / LC 296 Best Meeting Point——不从会合点向每栋楼 BFS,而是从每栋楼向外 BFS、把距离累加进一个网格——k 栋楼 O(k·n) 胜过 O(n²)。选对 BFS 起点就是全部洞察;当步数带权时,基于 PQ 的 Dijkstra(O(n log n))是升级版。

数组上的单调栈与双指针

两道直方图经典,奖励同一种直觉——别重算一趟扫描已经知道的东西。

LC 84 Largest Rectangle in Histogram:暴力从每根柱子向左右扩,找它能保持最高多远——O(n²)。洞察是边界可以同时被发现:当柱子 A 比它左边的柱子 B 矮,A 就封死了 B 的右边界。预计算每根柱子的左侧最近更矮和右侧最近更矮,用 (right − left) × height 得 O(n);最利落的实现是一个单调递增栈,恰好在一根柱子的右边界被找到时把它弹出。

LC 42 Trapping Rain Water 是同一个「左 max 对右 max」思想推到极限。一根柱子上方的水是 min(leftMax, rightMax) − height。暴力每个下标重算两个 max(O(n²));预计算两个数组变 O(n) 时间 O(n) 空间;双指针精修把空间降到 O(1)——注意到哪个运行 max 更小,哪一侧就是真正的瓶颈,于是可以安全地敲定那个指针再往里挪。

public int trap(int[] height) {
    if (height == null || height.length <= 2) return 0;
    int left = 0, right = height.length - 1;
    int leftMax = 0, rightMax = 0, water = 0;

    while (left < right) {                       // 向中间靠拢;最高点存不住水
        leftMax  = Math.max(leftMax,  height[left]);
        rightMax = Math.max(rightMax, height[right]);
        if (leftMax < rightMax) {                  // 左侧是瓶颈
            water += leftMax - height[left];
            left++;
        } else {
            water += rightMax - height[right];
            right--;
        }
    }
    return water;
}

设计题:两个数据结构联姻

Cache 题是最纯的「两个结构、一份契约」练习——没有单一结构能把所有操作都做到 O(1),于是你把两个组合起来。

LC 146 LRU Cache:你需要 O(1) 的 get、O(1) 更新近用度、O(1) 淘汰最旧条目。单靠 HashMap 无法按近用度排序;单靠链表无法按 key 查找。把它俩联姻——map 里存进双向链表的节点引用,于是能 O(1) 把任意节点从中间摘出、重挂到尾部(最近使用),淘汰时从 head 弹出。这本质上就是手搓一个 LinkedHashMap。

class LRUCache {
    class Node { int key, val; Node prev, next; }

    private final Map<Integer, Node> map = new HashMap<>();
    private final Node head = new Node(), tail = new Node();
    private final int capacity;
    private int size = 0;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        head.next = tail; tail.prev = head;      // 哨兵节点夹住链表两端
    }

    public int get(int key) {
        Node node = map.get(key);
        if (node == null) return -1;
        moveToTail(node);                         // 被访问 -> 变最近使用
        return node.val;
    }

    public void put(int key, int value) {
        Node node = map.get(key);
        if (node != null) { node.val = value; moveToTail(node); return; }
        if (size == capacity) {                   // 淘汰 LRU:head 后面那个节点
            Node lru = head.next;
            remove(lru); map.remove(lru.key); size--;
        }
        Node fresh = new Node();
        fresh.key = key; fresh.val = value;
        addToTail(fresh); map.put(key, fresh); size++;
    }

    private void moveToTail(Node n) { remove(n); addToTail(n); }
    private void remove(Node n) { n.prev.next = n.next; n.next.prev = n.prev; }
    private void addToTail(Node n) {
        n.prev = tail.prev; tail.prev.next = n; tail.prev = n; n.next = tail;
    }
}

LC 460 LFU Cache 把难度提到按频率淘汰:维护一个 value map、一个 frequency map、一个「每个频率一桶 key」的桶(LinkedHashSet 保留插入顺序好打破平手),外加一个运行中的 min 频率好 O(1) 淘汰。笔记点名的微妙处:不像 LRU,访问时不能直接把条目丢掉——必须把它从桶 f 迁到桶 f+1,因为频率本身就是状态。

首个唯一字符——字符串 vs 数据流

找首个不重复字符(LC 387)在定长字符串上就是两趟频次统计——一个 HashMap<Character,Integer>,或一个 freq[128] 数组,甚至一个每字符两 bit 的位向量来编码「没出现 / 出现一次 / 出现多次」。数据流版本才是它变成设计题、并与 LRU 押韵的地方:维护一个「当前唯一候选」的双向链表加一张 HashMap;新字符到来时,要么追加,要么(若它已成重复)把它摘出并标记为「已见多次」使其永不再入。任意时刻链表头就是 O(1) 的答案。

字符串与序列 DP、数组技巧、数学

最后一簇混了 2D 字符串 DP、一个 DP 加二分的混血,以及三道各藏一个数学捷径的数组题。

Longest Common Substring / Subarray / Subsequence(LCS,LC 1143)是一个 2D DP,dp[i][j] 覆盖第一个串前 i 个和第二个串前 j 个字符。变体之间那一字之差就是全部:对连续子串,匹配时 dp[i][j] = dp[i-1][j-1] + 1,不匹配时重置为 0;对子序列,不匹配时取 max(dp[i-1][j], dp[i][j-1])。两者都能从 2D 压到 1D,因为每格只依赖上一行。

LC 300 Longest Increasing Subsequence 是 DP 遇上 binary search 的混血。O(n²) DP 设 dp[i] = max(dp[k]) + 1(k 是前面更小的元素);O(n log n) 升级维护一个 tails 数组(每个长度对应的最小可能结尾),对每个元素二分插入位置——一个由算法自己建、自己保持有序的数组。LC 354 Russian Doll Envelopes 是二维 LIS:按宽升序、宽相同时高降序排,再对高跑 LIS——排序就是全部窍门。

三道数组题收尾,各是一个「有数学捷径」的时刻:

• LC 41 First Missing Positive——O(n) 时间 O(1) 空间,把数组自身当 HashMap 用:把值 v 放到下标 v−1,再扫第一个值不对的下标。窍门是认出答案必落在 [1, n+1],于是越界值可以忽略。
• LC 149 Max Points on a Line——固定每个点,把其余点按斜率装进 HashMap,最大的桶获胜;O(n²)。数学上要小心斜率:存成 gcd 约分后的 (dy, dx) 对而不是浮点比值,躲开精度丢失,并把竖线和重合点各自单独计数。
• LC 169 Majority Element——排序白给 n/2 下标,HashMap 计数可提前退出,但 O(1) 空间的 Boyer-Moore voting 才是要掌握的那个,见下。

public int majorityElement(int[] nums) {
    int candidate = nums[0], count = 1;
    for (int i = 1; i < nums.length; i++) {
        if (count == 0) {                // 台上没人了 -> nums[i] 上位
            candidate = nums[i];
            count = 1;
        } else if (nums[i] == candidate) {
            count++;                     // 盟友
        } else {
            count--;                     // 对手抵消一票
        }
    }
    return candidate;                    // 只因多数严格 > n/2 才成立
}

voting 的直觉:让每个多数元素和一个不同元素两两抵消,双双出局;因为多数严格超过 n/2,它至少总有一票活下来。推到 LC 229 Majority Element II(出现超过 n/3,或一般的 1/k),就保留 k−1 个计数器而非一个——但保证变弱,必须加第二趟重新验证每个幸存者真的过阈值。低于 n/2 时 voting 无效,HashMap 计数才是诚实的工具。

刷题清单