最近在整理早年互联网大厂研发岗的笔试题目翻到一套 2016 年百度研发工程师笔试题的第四套。这套题和系列里的前几套不太一样前几套还有不少基础概念题、网络题和操作系统题这一套四道题几乎全是手写代码题考点非常集中字符串解析、堆与排序、二叉树递归、动态规划。放在 90 分钟的时限里要做到全对其实并不轻松。我专门找时间把四道题从头到尾重新做了一遍边做边记录发现里面很多细节非常值得展开聊——比如字符串模拟题的边界条件有多容易漏动态规划的状态定义怎么从暴力递归顺理成章地推出来这些都是能直接平移到其他大厂笔试题上的方法论。这篇就当作一次完整复盘把题目描述、考点定位、代码实现和现场易错点都整理出来给准备投研发岗的朋友做参考。1. 这套题想考察什么先拆开题目的出题逻辑1.1 题目清单与难度定位我反复做过这么多年笔试真题最大的感受是拿到题先别急着写代码先把整张卷子的结构和考点分布读明白后面时间分配才不慌。这套第四套的考点分布大概可以整理成下面这样题号考点分类题目简述难度出题频率1字符串模拟判断字符串是否可以表示数值中等经典题变体2堆/排序从实时数据流中取出前 K 大中等偏易海量数据高频3二叉树递归求二叉树中两个节点的最近公共祖先中等面试必刷4动态规划求字符串最小编辑距离中等偏难最长公共子序列的升级版从这张表能看出一个趋势百度这类大厂在 2016 年已经很看重候选人的代码基本功尤其是对边界条件的敏感度和对复杂度的判断能力。四道题覆盖了四个完全不同的算法分支但要用的底层能力是相通的就是“把一个问题抽象成已知模型”的能力。字符串模拟题考的是严谨TopK 考的是数据结构选型最近公共祖先考的是递归定义是否清晰编辑距离考的是状态转移是否扎实。1.2 90 分钟时间盒做题顺序比想象中重要这套题虽然有四道但每道题的难度并不均匀。按照我的实测合理的顺序应该是先做第 2 题 TopK再做第 3 题最近公共祖先然后回头写第 1 题字符串模拟最后死磕第 4 题编辑距离。理由很简单。TopK 几乎是最容易拿满分的题只要想到了堆代码量小、出错概率低花十几分钟把稳的分先拿到手心态会稳很多。二叉树最近公共祖先的递归框架也相对固定属于“背过模板就能很快写出来”的题。字符串模拟题虽然看起来简单但隐藏用例非常多很容易在一两个边界上翻车需要留足时间手工验证。编辑距离则是四道题里最吃时间的状态转移一旦想歪改起来会很痛苦放在后面能确保前面已经有足够多的完成为底气。合理的时间盒大概是第 2 题 15 分钟第 3 题 20 分钟第 1 题 20 分钟第 4 题 30 分钟最后留 5 分钟统一检查边界。如果某道题卡了三分钟一点思路都没有果断跳过笔试最怕的是在一道题上投入 40 分钟结果其他题全空了。2. 字符串模拟题判断数值的一堆隐藏边界2.1 题目描述与常见错误这道题的原题大意是实现一个函数判断给定字符串是否可以表示为一个数值。合法的例子包括100、5e2、-123、-1E-16、12e8非法的例子包括12e、1a3.14、1.2.3、-5、12e5.3。很多人第一反应是“这个简单用正则表达式”。但在笔试现场写一长串正则然后让它全对概率非常低。这个题的真正考点是你能不能把各种字符组合之间的约束关系理清楚本质上是一个简易状态机。我见过的高频错误大概有这么几类空字符串、全空格字符串居然被判定为合法直接错。没有处理首尾空格导致 1 这种输入直接返回非法。允许数字中间出现空格1 23被错误放行。小数点没有做次数限制1.2.3通过。e/E 的幂部分没有限制必须为整数1e2.5被放行。e/E 之前没有数字e9这种也放行。正负号位置判断错误12e-4这种居然也过了。这些问题本质上都不是“不会写代码”而是“没有在动手前把约束条件列全”。2.2 用逐字符扫描的思路处理约束把这个问题当成状态机来写是最稳的。扫描过程中只需要维护三个布尔状态hasDigit当前已经扫描到过数字。hasDot当前已经扫描到过小数点。hasE当前已经扫描到过 e/E。然后再加几条硬性规则比如小数点最多出现一次、e/E 最多出现一次、正负号只能出现在最前面或 e/E 的后面、e/E 之后必须跟数字。核心代码如下用的是 Cbool isNumber(string s) { int n s.size(); int i 0, j n - 1; // 去掉首尾空格注意如果全是空格i 会越过 j while (i n s[i] ) i; while (j 0 s[j] ) j--; if (i j) return false; bool hasDigit false; bool hasDot false; bool hasE false; for (int k i; k j; k) { char c s[k]; if (c 0 c 9) { hasDigit true; } else if (c || c -) { // 正负号只能出现在开头或者紧跟在 e/E 后面 if (k i !(s[k - 1] e || s[k - 1] E)) return false; // 正负号不能出现在末尾 if (k j) return false; } else if (c .) { // 小数点不能重复出现也不能出现在 e/E 之后 if (hasDot || hasE) return false; hasDot true; } else if (c e || c E) { // e/E 不能重复出现且前面必须有数字 if (hasE || !hasDigit) return false; hasE true; // e/E 后面必须跟着数字或正负号不能光秃秃地结束 if (k j) return false; if (!isdigit(s[k 1]) s[k 1] ! s[k 1] ! -) return false; } else { // 出现其他字符直接非法 return false; } } return hasDigit; }仔细看这段代码会发现我没有单独为“e/E 之后必须有数字”单独设置一个标志位而是用了几条彼此配合的规则。比如12e会因为在扫描到末尾时触发k j被拒绝12e会因为在e这一位触发k j被拒绝12e5.3会因为在.这一位触发hasE检查被拒绝。这样写的好处是逻辑集中每条规则职责单一。2.3 实测最容易翻车的几个用例我把自己的代码放到测试里跑发现有几个用例特别容易踩坑 去掉首尾空格后 i 会大于 j必须直接返回 false很多人在这里忘记判空。.5这个应该是合法的小数点前没有数字没问题但有数字在点后面。5.这个在部分题目定义中合法在部分定义中不合法。如果题目没有特别说明建议按合法处理因为小数点后的空位等价于数字 0。6e-5e 后面可以跟负号这是合法指数别把负号判成非法。-1E-16大写 E 和大写字母同样处理所以代码里判断了e和E两种。1.e2小数点后没数字但紧跟 e这个在多数定义里合法可以理解为1.0e2。所以你写完之后一定要在本地把这些用例都跑一遍不要只靠题目给的那几个示例。笔试不是写出来就行而是要能在隐藏用例面前活下来。3. 堆与排序思维数据流中的 TopK3.1 题目本质与方案选型第二道题是一道非常经典的动态求 TopK 问题设计一个数据结构能够不断接收新的整数并且随时能返回当前已接收数据中的前 K 大值。很多人一看到“前 K 大”就想排序排序确实能做但这里的“数据流”三个字很关键——数据是不断到达的你不能每次查询都把所有历史数据重新排序一遍。来简单对比一下主流方案方案新增一个数查询前 K 大适用场景全量重新排序O(1)O(n log n)数据量小、查询频率低维护一个有序数组最坏 O(n)O(K)查询极频繁但插入代价太大小顶堆O(log K)O(K log K)数据流、海量数据最优解这题的天然解法就是小顶堆。堆的大小固定为 K堆里保存的是当前见过的 K 个最大值。因为是小顶堆堆顶永远是这 K 个值里最小的那一个也就是当前整体数据中的“第 K 大”。每次来新数如果堆还没满就直接进堆如果堆满了就把新数和堆顶比较新数更大就替换堆顶并调整堆。3.2 小顶堆实现要点我用 C 的priority_queue写了一个简洁版本class TopKHolder { private: priority_queueint, vectorint, greaterint minHeap; int k; public: TopKHolder(int k_) : k(k_) {} void add(int value) { if (minHeap.size() k) { minHeap.push(value); return; } if (value minHeap.top()) { minHeap.pop(); minHeap.push(value); } } vectorint getTopK() { vectorint res; priority_queueint, vectorint, greaterint heapCopy minHeap; while (!heapCopy.empty()) { res.push_back(heapCopy.top()); heapCopy.pop(); } reverse(res.begin(), res.end()); // 从大到小输出 return res; } int getKthLargest() { return minHeap.size() k ? minHeap.top() : -1; } };这里面有两个细节值得单独提一下。第一个是 getTopK 时不能直接对原堆做 pop否则会破坏堆结构。我这里是拷贝了一个堆再取元素代价是 O(K log K)。如果笔试环境中内存很紧也可以改成把堆里的元素放到临时数组后排序效果等价。第二个是value minHeap.top()这个比较条件用了严格大于。对于重复数据这里有一个隐藏语义问题如果需求和 TopK 相同——即重复值也要被保留那么在value minHeap.top()时也应该做插入否则相同元素可能被丢弃。我在实际实现里选择了“严格大于”因为题目通常说的是“前 K 大而不去重”这个选择一旦定下行为就固定了不容易在后续需求里踩坑。3.3 这道题背后的延伸考点笔试里 TopK 通常只是一道引子后面常接一个更狠的问题如果数据量极大内存装不下怎么办这时候堆依然有用但需要配合分治。可以把数据切分成多份分别对每一份求 TopK然后对每个分文件的 TopK 再做一次归并。本质上还是堆但思路从“内存解法”变成了“外部排序解法”。另一个延伸是离线场景。如果所有数据已经一次性给到而且数据量不大快速选择算法Quick Select可以把求第 K 大的平均复杂度降到 O(n)比建堆更优。但注意快速选择只能拿到单次结果拿不到“持续更新”的前 K 个所以它只适合静态数据。这些延伸不需要在笔试里写出来但如果你在代码注释或面试官的追问里能说清楚会很加分。4. 二叉树递归的经典考验求最近公共祖先4.1 题目描述与解题误区这道题是 LeetCode 236 的原题给定一棵二叉树和两个目标节点 p、q找出这两个节点的最近公共祖先。所谓最近公共祖先就是离 p 和 q 都最近的、同时是 p 和 q 祖先的节点节点本身也可以算作自己的祖先。这道题最大的误区是把它想复杂了。有的人一看到二叉树就想着先分别找从根到 p 和从根到 q 的路径再比较公共部分这样当然能做但需要额外维护两个路径数组代码量一下就上去了。真正干净的思路是递归但递归函数返回什么必须定义清楚。在这道题的标准递归写法里函数返回值有三种可能如果当前子树里只找到了 p 或只找到了 q返回找到的那个节点。如果当前子树里同时找到了 p 和 q返回它们的最近公共祖先。如果都没有找到返回空。4.2 递归实现与推导过程核心代码很短TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { if (!root || root p || root q) return root; TreeNode* left lowestCommonAncestor(root-left, p, q); TreeNode* right lowestCommonAncestor(root-right, p, q); if (left right) return root; return left ? left : right; }很多人第一遍看这段代码会觉得有点懵不知道它为什么在left right时返回 root。我换个说法讲就通了左子树返回非空说明左子树里至少找到了 p 或 q 之一右子树返回非空说明右子树里也至少找到了 p 或 q 之一。注意这时候 p 和 q 分离在左右两侧它们不可能在 root 的子树中再有别的共同祖先所以 root 就是它们的最近公共祖先。如果左右两边只有一边返回非空说明两个目标节点都在同一边的子树里那么最近公共祖先也在那一边把那边返回的结果继续往上抛即可。代码最后还会出现一种情况根节点本身就是 p 或 q。比如 p 是某个祖先节点q 在 p 的子树里这时最近公共祖先显然就是 p所以代码在最开头直接判断root p || root q一旦命中就直接返回 root。4.3 三个高频变体这道题的变体在笔试和面试里出现的频率比原题还高。第一个变体是二叉搜索树。如果能利用二叉搜索树的性质就没必要递归搜两边。根据值的大小p 和 q 都小于 root 就向左走都大于 root 就向右走否则 root 就是答案复杂度能从 O(n) 降到 O(h)h 是树高。第二个变体是树节点带有 parent 指针。这种情况下可以把 p 到根部的路径和 q 到根部的路径看成两条链表问题退化成求两条链表的第一个公共节点用双指针或者哈希集合都能解。第三个变体是多次查询。如果一棵树被反复查询几十万次每次递归 O(n) 就太慢了。这时要考虑离线处理常见方案是用 Tarjan 算法做离线 LCA或者在欧拉序列上做 RMQ 到 ST 表。这个深度基本超出笔试范围但如果备考时间充裕值得了解它的存在。5. 动态规划编辑距离的完整推导5.1 题目描述与状态定义第四道题是最经典的编辑距离基本上所有字符串动态规划题里都绕不开它给定两个字符串 word1 和 word2你只能对 word1 做三种操作——插入一个字符、删除一个字符、替换一个字符问最少需要几步操作能让 word1 变成 word2。我见过很多人第一次做这道题的时候会试图模拟具体的操作过程从开头开始比较遇到不同就替换……但这样想很快会被各种特殊情况搞晕。正确的打开方式是把它定义成子问题设 dp[i][j] 表示 word1 的前 i 个字符转换成 word2 的前 j 个字符所需要的最小操作数。有了这个定义状态转移就好写了。考量 word1[i-1] 和 word2[j-1] 这两个字符如果它们相等那当前这一步不需要操作直接继承dp[i-1][j-1]。如果不相等有三种可能的操作删除 word1[i-1]前缀继续匹配对应dp[i-1][j] 1。在 word1 的 i 位置插入一个字符来匹配 word2[j-1]对应dp[i][j-1] 1。把 word1[i-1] 替换成 word2[j-1]对应dp[i-1][j-1] 1。把这三个值取最小值就是dp[i][j]。5.2 二维表格与手算例子转移方程的初始化也很自然dp[i][0] i表示把 word1 的前 i 个字符全部删掉dp[0][j] j表示在空串里插入 j 个字符补出 word2。我拿经典的horse到ros走一遍大家可以感受一下表格怎么填dp空ros空0123h1123o2212r3222s4332e5443这里的最终答案是 3。完整的一条操作路径是h 替换为 r - 删除 r 之前的 h - 把 e 替换成 s。这个例子也是 LeetCode 官方例子自己动手填一遍表格对理解状态转移特别有帮助。5.3 二维代码与空间优化笔试能写出二维版本就已经是及格了。下面是标准实现int minDistance(string word1, string word2) { int m word1.size(), n word2.size(); vectorvectorint dp(m 1, vectorint(n 1, 0)); for (int i 0; i m; i) dp[i][0] i; for (int j 0; j n; j) dp[0][j] j; for (int i 1; i m; i) { for (int j 1; j n; j) { if (word1[i - 1] word2[j - 1]) { dp[i][j] dp[i - 1][j - 1]; } else { dp[i][j] min({dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]}) 1; } } } return dp[m][n]; }这份代码时间复杂度 O(mn)空间复杂度 O(mn)。笔试环境里大多数情况是够用的。但如果你在面试里被问到“能不能把空间优化一下”那就得想到滚动数组。看一下状态转移式dp[i][j]只依赖上一行的dp[i-1][j]、当前行左一格的dp[i][j-1]、以及左上方格的dp[i-1][j-1]。后者是唯一需要额外留意的因为它既不在当前行的前一个位置也不在上一行的当前位置。所以在滚动数组的循环里必须用一个临时变量prev先保存左上方的值再把当前格子的旧值保留给下一轮的prev用。int minDistance(string word1, string word2) { int m word1.size(), n word2.size(); vectorint dp(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; for (int j 1; j n; j) { int temp dp[j]; // 保存旧值下一轮作为左上方的 prev if (word1[i - 1] word2[j - 1]) { dp[j] prev; } else { dp[j] min({dp[j], dp[j - 1], prev}) 1; } prev temp; } } return dp[n]; }空间复杂度直接降到了 O(n)。这种滚动数组的写法在动态规划类笔试题里几乎是通用技能最好做到不看代码也能随手写出来。6. 复盘这套题的现场表现与复习建议6.1 我在模拟作答时踩过的坑这套题我完整模拟了两遍第一遍的时间在 75 分钟左右第二遍压缩到 55 分钟但两遍都踩了一些很典型的坑说出来给大家避避雷。第一个坑是字符串数值题我第一次实现时没有单独处理“e/E 后面的指数部分为空”的情况导致12e这种明显非法的字符串被误判为合法。这个 bug 如果在笔试里出现基本上这一道题就拿不到高分了。后来我把规则改成了“e/E 后一位必须为数字或符号且符号不能在末尾”才把所有用例跑干净。这类题目光看题目给的示例远远不够我建议写了判断逻辑之后把、 、e、.、.、5e-3、3e2.5、 1 这几个用例全部过一遍能一次性写对的人真的不多。第二个坑在编辑距离的滚动数组。我一开始写滚动数组时忽略了对prev的保存导致dp[j]在计算时拿到的“左上角”已经是当前行被覆盖后的值结果全盘错误。这个问题在二维 DP 里不会出现但一旦优化成滚动数组就非常隐蔽。建议平时练习时两种写法都练笔试时心态紧张优先写二维版本稳定拿分时间充裕再改滚动数组。第三个坑在 TopK 的边界如果 K 等于 0堆的top()会直接崩溃因为这时的堆是空的。实际开发中肯定会先做参数校验但笔试里很多人只顾主体逻辑忘了这种边缘情况。我把k0当成不需要维护任何数据 2016百度研发笔试题复盘：字符串模拟、TopK、LCA、编辑距离一网打尽
最近在整理早年互联网大厂研发岗的笔试题目翻到一套 2016 年百度研发工程师笔试题的第四套。这套题和系列里的前几套不太一样前几套还有不少基础概念题、网络题和操作系统题这一套四道题几乎全是手写代码题考点非常集中字符串解析、堆与排序、二叉树递归、动态规划。放在 90 分钟的时限里要做到全对其实并不轻松。我专门找时间把四道题从头到尾重新做了一遍边做边记录发现里面很多细节非常值得展开聊——比如字符串模拟题的边界条件有多容易漏动态规划的状态定义怎么从暴力递归顺理成章地推出来这些都是能直接平移到其他大厂笔试题上的方法论。这篇就当作一次完整复盘把题目描述、考点定位、代码实现和现场易错点都整理出来给准备投研发岗的朋友做参考。1. 这套题想考察什么先拆开题目的出题逻辑1.1 题目清单与难度定位我反复做过这么多年笔试真题最大的感受是拿到题先别急着写代码先把整张卷子的结构和考点分布读明白后面时间分配才不慌。这套第四套的考点分布大概可以整理成下面这样题号考点分类题目简述难度出题频率1字符串模拟判断字符串是否可以表示数值中等经典题变体2堆/排序从实时数据流中取出前 K 大中等偏易海量数据高频3二叉树递归求二叉树中两个节点的最近公共祖先中等面试必刷4动态规划求字符串最小编辑距离中等偏难最长公共子序列的升级版从这张表能看出一个趋势百度这类大厂在 2016 年已经很看重候选人的代码基本功尤其是对边界条件的敏感度和对复杂度的判断能力。四道题覆盖了四个完全不同的算法分支但要用的底层能力是相通的就是“把一个问题抽象成已知模型”的能力。字符串模拟题考的是严谨TopK 考的是数据结构选型最近公共祖先考的是递归定义是否清晰编辑距离考的是状态转移是否扎实。1.2 90 分钟时间盒做题顺序比想象中重要这套题虽然有四道但每道题的难度并不均匀。按照我的实测合理的顺序应该是先做第 2 题 TopK再做第 3 题最近公共祖先然后回头写第 1 题字符串模拟最后死磕第 4 题编辑距离。理由很简单。TopK 几乎是最容易拿满分的题只要想到了堆代码量小、出错概率低花十几分钟把稳的分先拿到手心态会稳很多。二叉树最近公共祖先的递归框架也相对固定属于“背过模板就能很快写出来”的题。字符串模拟题虽然看起来简单但隐藏用例非常多很容易在一两个边界上翻车需要留足时间手工验证。编辑距离则是四道题里最吃时间的状态转移一旦想歪改起来会很痛苦放在后面能确保前面已经有足够多的完成为底气。合理的时间盒大概是第 2 题 15 分钟第 3 题 20 分钟第 1 题 20 分钟第 4 题 30 分钟最后留 5 分钟统一检查边界。如果某道题卡了三分钟一点思路都没有果断跳过笔试最怕的是在一道题上投入 40 分钟结果其他题全空了。2. 字符串模拟题判断数值的一堆隐藏边界2.1 题目描述与常见错误这道题的原题大意是实现一个函数判断给定字符串是否可以表示为一个数值。合法的例子包括100、5e2、-123、-1E-16、12e8非法的例子包括12e、1a3.14、1.2.3、-5、12e5.3。很多人第一反应是“这个简单用正则表达式”。但在笔试现场写一长串正则然后让它全对概率非常低。这个题的真正考点是你能不能把各种字符组合之间的约束关系理清楚本质上是一个简易状态机。我见过的高频错误大概有这么几类空字符串、全空格字符串居然被判定为合法直接错。没有处理首尾空格导致 1 这种输入直接返回非法。允许数字中间出现空格1 23被错误放行。小数点没有做次数限制1.2.3通过。e/E 的幂部分没有限制必须为整数1e2.5被放行。e/E 之前没有数字e9这种也放行。正负号位置判断错误12e-4这种居然也过了。这些问题本质上都不是“不会写代码”而是“没有在动手前把约束条件列全”。2.2 用逐字符扫描的思路处理约束把这个问题当成状态机来写是最稳的。扫描过程中只需要维护三个布尔状态hasDigit当前已经扫描到过数字。hasDot当前已经扫描到过小数点。hasE当前已经扫描到过 e/E。然后再加几条硬性规则比如小数点最多出现一次、e/E 最多出现一次、正负号只能出现在最前面或 e/E 的后面、e/E 之后必须跟数字。核心代码如下用的是 Cbool isNumber(string s) { int n s.size(); int i 0, j n - 1; // 去掉首尾空格注意如果全是空格i 会越过 j while (i n s[i] ) i; while (j 0 s[j] ) j--; if (i j) return false; bool hasDigit false; bool hasDot false; bool hasE false; for (int k i; k j; k) { char c s[k]; if (c 0 c 9) { hasDigit true; } else if (c || c -) { // 正负号只能出现在开头或者紧跟在 e/E 后面 if (k i !(s[k - 1] e || s[k - 1] E)) return false; // 正负号不能出现在末尾 if (k j) return false; } else if (c .) { // 小数点不能重复出现也不能出现在 e/E 之后 if (hasDot || hasE) return false; hasDot true; } else if (c e || c E) { // e/E 不能重复出现且前面必须有数字 if (hasE || !hasDigit) return false; hasE true; // e/E 后面必须跟着数字或正负号不能光秃秃地结束 if (k j) return false; if (!isdigit(s[k 1]) s[k 1] ! s[k 1] ! -) return false; } else { // 出现其他字符直接非法 return false; } } return hasDigit; }仔细看这段代码会发现我没有单独为“e/E 之后必须有数字”单独设置一个标志位而是用了几条彼此配合的规则。比如12e会因为在扫描到末尾时触发k j被拒绝12e会因为在e这一位触发k j被拒绝12e5.3会因为在.这一位触发hasE检查被拒绝。这样写的好处是逻辑集中每条规则职责单一。2.3 实测最容易翻车的几个用例我把自己的代码放到测试里跑发现有几个用例特别容易踩坑 去掉首尾空格后 i 会大于 j必须直接返回 false很多人在这里忘记判空。.5这个应该是合法的小数点前没有数字没问题但有数字在点后面。5.这个在部分题目定义中合法在部分定义中不合法。如果题目没有特别说明建议按合法处理因为小数点后的空位等价于数字 0。6e-5e 后面可以跟负号这是合法指数别把负号判成非法。-1E-16大写 E 和大写字母同样处理所以代码里判断了e和E两种。1.e2小数点后没数字但紧跟 e这个在多数定义里合法可以理解为1.0e2。所以你写完之后一定要在本地把这些用例都跑一遍不要只靠题目给的那几个示例。笔试不是写出来就行而是要能在隐藏用例面前活下来。3. 堆与排序思维数据流中的 TopK3.1 题目本质与方案选型第二道题是一道非常经典的动态求 TopK 问题设计一个数据结构能够不断接收新的整数并且随时能返回当前已接收数据中的前 K 大值。很多人一看到“前 K 大”就想排序排序确实能做但这里的“数据流”三个字很关键——数据是不断到达的你不能每次查询都把所有历史数据重新排序一遍。来简单对比一下主流方案方案新增一个数查询前 K 大适用场景全量重新排序O(1)O(n log n)数据量小、查询频率低维护一个有序数组最坏 O(n)O(K)查询极频繁但插入代价太大小顶堆O(log K)O(K log K)数据流、海量数据最优解这题的天然解法就是小顶堆。堆的大小固定为 K堆里保存的是当前见过的 K 个最大值。因为是小顶堆堆顶永远是这 K 个值里最小的那一个也就是当前整体数据中的“第 K 大”。每次来新数如果堆还没满就直接进堆如果堆满了就把新数和堆顶比较新数更大就替换堆顶并调整堆。3.2 小顶堆实现要点我用 C 的priority_queue写了一个简洁版本class TopKHolder { private: priority_queueint, vectorint, greaterint minHeap; int k; public: TopKHolder(int k_) : k(k_) {} void add(int value) { if (minHeap.size() k) { minHeap.push(value); return; } if (value minHeap.top()) { minHeap.pop(); minHeap.push(value); } } vectorint getTopK() { vectorint res; priority_queueint, vectorint, greaterint heapCopy minHeap; while (!heapCopy.empty()) { res.push_back(heapCopy.top()); heapCopy.pop(); } reverse(res.begin(), res.end()); // 从大到小输出 return res; } int getKthLargest() { return minHeap.size() k ? minHeap.top() : -1; } };这里面有两个细节值得单独提一下。第一个是 getTopK 时不能直接对原堆做 pop否则会破坏堆结构。我这里是拷贝了一个堆再取元素代价是 O(K log K)。如果笔试环境中内存很紧也可以改成把堆里的元素放到临时数组后排序效果等价。第二个是value minHeap.top()这个比较条件用了严格大于。对于重复数据这里有一个隐藏语义问题如果需求和 TopK 相同——即重复值也要被保留那么在value minHeap.top()时也应该做插入否则相同元素可能被丢弃。我在实际实现里选择了“严格大于”因为题目通常说的是“前 K 大而不去重”这个选择一旦定下行为就固定了不容易在后续需求里踩坑。3.3 这道题背后的延伸考点笔试里 TopK 通常只是一道引子后面常接一个更狠的问题如果数据量极大内存装不下怎么办这时候堆依然有用但需要配合分治。可以把数据切分成多份分别对每一份求 TopK然后对每个分文件的 TopK 再做一次归并。本质上还是堆但思路从“内存解法”变成了“外部排序解法”。另一个延伸是离线场景。如果所有数据已经一次性给到而且数据量不大快速选择算法Quick Select可以把求第 K 大的平均复杂度降到 O(n)比建堆更优。但注意快速选择只能拿到单次结果拿不到“持续更新”的前 K 个所以它只适合静态数据。这些延伸不需要在笔试里写出来但如果你在代码注释或面试官的追问里能说清楚会很加分。4. 二叉树递归的经典考验求最近公共祖先4.1 题目描述与解题误区这道题是 LeetCode 236 的原题给定一棵二叉树和两个目标节点 p、q找出这两个节点的最近公共祖先。所谓最近公共祖先就是离 p 和 q 都最近的、同时是 p 和 q 祖先的节点节点本身也可以算作自己的祖先。这道题最大的误区是把它想复杂了。有的人一看到二叉树就想着先分别找从根到 p 和从根到 q 的路径再比较公共部分这样当然能做但需要额外维护两个路径数组代码量一下就上去了。真正干净的思路是递归但递归函数返回什么必须定义清楚。在这道题的标准递归写法里函数返回值有三种可能如果当前子树里只找到了 p 或只找到了 q返回找到的那个节点。如果当前子树里同时找到了 p 和 q返回它们的最近公共祖先。如果都没有找到返回空。4.2 递归实现与推导过程核心代码很短TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { if (!root || root p || root q) return root; TreeNode* left lowestCommonAncestor(root-left, p, q); TreeNode* right lowestCommonAncestor(root-right, p, q); if (left right) return root; return left ? left : right; }很多人第一遍看这段代码会觉得有点懵不知道它为什么在left right时返回 root。我换个说法讲就通了左子树返回非空说明左子树里至少找到了 p 或 q 之一右子树返回非空说明右子树里也至少找到了 p 或 q 之一。注意这时候 p 和 q 分离在左右两侧它们不可能在 root 的子树中再有别的共同祖先所以 root 就是它们的最近公共祖先。如果左右两边只有一边返回非空说明两个目标节点都在同一边的子树里那么最近公共祖先也在那一边把那边返回的结果继续往上抛即可。代码最后还会出现一种情况根节点本身就是 p 或 q。比如 p 是某个祖先节点q 在 p 的子树里这时最近公共祖先显然就是 p所以代码在最开头直接判断root p || root q一旦命中就直接返回 root。4.3 三个高频变体这道题的变体在笔试和面试里出现的频率比原题还高。第一个变体是二叉搜索树。如果能利用二叉搜索树的性质就没必要递归搜两边。根据值的大小p 和 q 都小于 root 就向左走都大于 root 就向右走否则 root 就是答案复杂度能从 O(n) 降到 O(h)h 是树高。第二个变体是树节点带有 parent 指针。这种情况下可以把 p 到根部的路径和 q 到根部的路径看成两条链表问题退化成求两条链表的第一个公共节点用双指针或者哈希集合都能解。第三个变体是多次查询。如果一棵树被反复查询几十万次每次递归 O(n) 就太慢了。这时要考虑离线处理常见方案是用 Tarjan 算法做离线 LCA或者在欧拉序列上做 RMQ 到 ST 表。这个深度基本超出笔试范围但如果备考时间充裕值得了解它的存在。5. 动态规划编辑距离的完整推导5.1 题目描述与状态定义第四道题是最经典的编辑距离基本上所有字符串动态规划题里都绕不开它给定两个字符串 word1 和 word2你只能对 word1 做三种操作——插入一个字符、删除一个字符、替换一个字符问最少需要几步操作能让 word1 变成 word2。我见过很多人第一次做这道题的时候会试图模拟具体的操作过程从开头开始比较遇到不同就替换……但这样想很快会被各种特殊情况搞晕。正确的打开方式是把它定义成子问题设 dp[i][j] 表示 word1 的前 i 个字符转换成 word2 的前 j 个字符所需要的最小操作数。有了这个定义状态转移就好写了。考量 word1[i-1] 和 word2[j-1] 这两个字符如果它们相等那当前这一步不需要操作直接继承dp[i-1][j-1]。如果不相等有三种可能的操作删除 word1[i-1]前缀继续匹配对应dp[i-1][j] 1。在 word1 的 i 位置插入一个字符来匹配 word2[j-1]对应dp[i][j-1] 1。把 word1[i-1] 替换成 word2[j-1]对应dp[i-1][j-1] 1。把这三个值取最小值就是dp[i][j]。5.2 二维表格与手算例子转移方程的初始化也很自然dp[i][0] i表示把 word1 的前 i 个字符全部删掉dp[0][j] j表示在空串里插入 j 个字符补出 word2。我拿经典的horse到ros走一遍大家可以感受一下表格怎么填dp空ros空0123h1123o2212r3222s4332e5443这里的最终答案是 3。完整的一条操作路径是h 替换为 r - 删除 r 之前的 h - 把 e 替换成 s。这个例子也是 LeetCode 官方例子自己动手填一遍表格对理解状态转移特别有帮助。5.3 二维代码与空间优化笔试能写出二维版本就已经是及格了。下面是标准实现int minDistance(string word1, string word2) { int m word1.size(), n word2.size(); vectorvectorint dp(m 1, vectorint(n 1, 0)); for (int i 0; i m; i) dp[i][0] i; for (int j 0; j n; j) dp[0][j] j; for (int i 1; i m; i) { for (int j 1; j n; j) { if (word1[i - 1] word2[j - 1]) { dp[i][j] dp[i - 1][j - 1]; } else { dp[i][j] min({dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]}) 1; } } } return dp[m][n]; }这份代码时间复杂度 O(mn)空间复杂度 O(mn)。笔试环境里大多数情况是够用的。但如果你在面试里被问到“能不能把空间优化一下”那就得想到滚动数组。看一下状态转移式dp[i][j]只依赖上一行的dp[i-1][j]、当前行左一格的dp[i][j-1]、以及左上方格的dp[i-1][j-1]。后者是唯一需要额外留意的因为它既不在当前行的前一个位置也不在上一行的当前位置。所以在滚动数组的循环里必须用一个临时变量prev先保存左上方的值再把当前格子的旧值保留给下一轮的prev用。int minDistance(string word1, string word2) { int m word1.size(), n word2.size(); vectorint dp(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; for (int j 1; j n; j) { int temp dp[j]; // 保存旧值下一轮作为左上方的 prev if (word1[i - 1] word2[j - 1]) { dp[j] prev; } else { dp[j] min({dp[j], dp[j - 1], prev}) 1; } prev temp; } } return dp[n]; }空间复杂度直接降到了 O(n)。这种滚动数组的写法在动态规划类笔试题里几乎是通用技能最好做到不看代码也能随手写出来。6. 复盘这套题的现场表现与复习建议6.1 我在模拟作答时踩过的坑这套题我完整模拟了两遍第一遍的时间在 75 分钟左右第二遍压缩到 55 分钟但两遍都踩了一些很典型的坑说出来给大家避避雷。第一个坑是字符串数值题我第一次实现时没有单独处理“e/E 后面的指数部分为空”的情况导致12e这种明显非法的字符串被误判为合法。这个 bug 如果在笔试里出现基本上这一道题就拿不到高分了。后来我把规则改成了“e/E 后一位必须为数字或符号且符号不能在末尾”才把所有用例跑干净。这类题目光看题目给的示例远远不够我建议写了判断逻辑之后把、 、e、.、.、5e-3、3e2.5、 1 这几个用例全部过一遍能一次性写对的人真的不多。第二个坑在编辑距离的滚动数组。我一开始写滚动数组时忽略了对prev的保存导致dp[j]在计算时拿到的“左上角”已经是当前行被覆盖后的值结果全盘错误。这个问题在二维 DP 里不会出现但一旦优化成滚动数组就非常隐蔽。建议平时练习时两种写法都练笔试时心态紧张优先写二维版本稳定拿分时间充裕再改滚动数组。第三个坑在 TopK 的边界如果 K 等于 0堆的top()会直接崩溃因为这时的堆是空的。实际开发中肯定会先做参数校验但笔试里很多人只顾主体逻辑忘了这种边缘情况。我把k0当成不需要维护任何数据