前阵子整理云盘翻出一套2016年百度研发工程师在线编程题的存档。说实话刚看到年份时我愣了一下——互联网公司的笔试题目两年一小变、五年一大变2016年的题还能有多少参考价值但耐着性子把几道典型题重新做了一遍我发现一个挺扎心的事实那些题目里藏着的算法考点到现在依然是各大厂笔试的主力军。排序、栈、字符串、动态规划换了一层更花哨的包装内核还是那几个经典模型。所以这篇文章我想认真拆一拆这套题。我会按题型把这些在线编程题归类讲清楚每道题的思路推演过程、关键代码、边界条件和复杂度再加上这些年我实际刷题、带人备战笔试时踩过的坑。适合正在准备秋招春招的应届生也适合想系统补算法基础的开发者——哪怕你不参加笔试把这几类模型的思路吃透日常写代码也会顺手很多。1. 先搞清楚这套题到底在考什么1.1 为什么2016年的题还有参考价值很多人一听是几年前的题就直接划走觉得技术迭代这么快老题肯定过时了。但算法题恰恰是互联网公司笔试里最“保值”的部分。2016年考最长上升子序列2026年还在考只是数据范围从 n1000 变成了 n10^5要求从 O(n^2) 优化到 O(n log n)。考的不是你会不会背模板而是你在新约束下能不能反应过来该换什么做法。百度这类公司的在线编程题一向出得比较朴实不太喜欢故意刁难人的偏题怪题。题目包装往往很真实可能是一个搜索场景、一个数据统计场景但剥掉外壳之后就是经典的排序、栈、动态规划模型。正因为如此这套题特别适合用来做“算法基础体检”——每一道题都能精准检验你对某个基础模型的理解深度。顺便提一句百度每年还有“百度之星”这类程序设计竞赛有些校招笔试题目和竞赛题的风格是相通的。刷2016年的笔试题相当于提前熟悉一下这个出题体系的味道对目标明确想进这类公司的同学来说性价比很高。1.2 出题人的评估逻辑在线编程题和平时刷 LeetCode 有个很大的不同它是在限时、限内存、限环境的条件下完成的而且会通过隐藏测试用例来卡极端情况。所以想拿高分光是把样例跑通远远不够。出题人评估的维度通常有这么几个正确性核心逻辑是否对特殊输入空串、n0、负数、重复元素是否处理。效率算法复杂度是否在题目要求范围内会不会在大数据量下超时。代码规范变量命名、结构分层是否清晰面试官线下看代码时观感如何。工程习惯内存是否合理有没有不必要的拷贝有没有明显的浪费。那几年百度在线编程题的整体分布按我的复盘大概可以分成四类模拟与排序、数据结构与字符串、动态规划与递推还有一类是数学/位运算。频率我放一个表方便大家对照着查漏补缺题型典型考点出现频率模拟与排序结构体排序、多关键字排序、数组操作高数据结构与字符串栈、队列、滑动窗口、哈希高动态规划与递推LIS、背包、区间DP中高数学与位运算快速幂、公约数、二进制性质中2. 模拟与排序类最容易被忽视的送分题2.1 典型题目用户ID按权值排序先看一道非常典型的题输入若干条用户记录每条记录包含一个整数ID和一个整数权值。要求按权值从大到小排序权值相同的情况下按ID从小到大排序最后输出排序后的ID序列。题目描述看起来平平无奇但它在当年笔试里其实是一个“筛选器”。数据结构里 sort 谁都会调真正拉开差距的是两个细节一是能不能写出正确的多关键字比较函数二是在 n 达到 10^5 甚至 10^6 时能不能意识到性能风险。我给出的参考代码是这样#include bits/stdc.h using namespace std; struct Node { int id; int w; }; bool cmp(const Node a, const Node b) { if (a.w ! b.w) return a.w b.w; return a.id b.id; } int main() { int n; while (cin n) { vectorNode arr(n); for (int i 0; i n; i) { cin arr[i].id arr[i].w; } sort(arr.begin(), arr.end(), cmp); for (int i 0; i n; i) { cout arr[i].id (i n - 1 ? \n : ); } } return 0; }这段代码里有几个值得说的点。比较函数 cmp 的两个参数一定要用 const 引用否则 sort 排序过程中会反复拷贝整个 Node在大数据量下性能会明显下降。按权值降序、ID升序这个顺序不能反一旦写反就是全部样例失败。输出时行尾不要多余空格很多在线评测系统对行尾空格容忍但有些严格按字符串比对多余空格等于 Wrong Answer。2.2 做题时的边界处理与输入输出细节这种模拟排序题隐藏测试用例最爱出的就是极端情况n1 时输出是否正常n0 时能不能跳过输出所有记录权值都相等时是否退化成纯ID升序ID很大时 int 是否够用。我在复盘时试过几个常见的错误写法比如没有处理 n0 直接访问 arr[0]在本地跑没问题一提交就数组越界。另外在线编程题的输入输出约定和本地调试习惯往往不一样。当年百度用的在线评测系统输入通常是多组数据所以要用 while (cin n) 这种写法读到文件结束。很多人漏掉这个循环只处理了一组数据结果只能过第一个样例后面全挂。这个坑我在写 LeetCode 时没遇到过因为 LeetCode 是函数式输入但国内很多公司的笔试平台都是 ACM 风格大家一定要养成“多组输入”的条件反射。还有个小技巧输出用 cout 没问题但如果你在循环里频繁用 endl每输出一行都会刷新一次缓冲区数据量大时会拖慢速度。直接输出 \n 或者用 printf性能更稳。算法题里的常数优化往往就在这种不起眼的地方。3. 数据结构与字符串类考基本功的高频区3.1 括号匹配变种考栈但不直接考栈那几年的百度笔试题里栈相关的题特别爱以“变形”的方式出现。比如有一道变种给定一个只包含 ( 和 ) 的字符串找出其中最长的合法括号子串的长度。这题表面上是括号匹配但如果直接用栈做单纯的配对统计会漏掉很多情况。我第一次做这题时用了暴力枚举O(n^2) 的复杂度在小数据量下没问题但题目如果把字符串长度放到 10^5直接就超时了。正确的解法是用动态规划思路是这样dp[i] 表示以第 i 个字符结尾的最长合法括号子串长度。当 s[i] 是 ( 时dp[i] 0因为合法括号子串不可能以左括号结尾。当 s[i] 是 ) 且 s[i-1] 是 ( 时dp[i] dp[i-2] 2。当 s[i] 是 ) 且 s[i-1] 是 ) 时需要看 dp[i-1] 这个合法子串前一个字符是不是 (如果是就形成了一段更长的合法子串。最后一类是最容易写错的它要把三个部分加在一起当前匹配到的外层括号长度 2再加上外层括号内部原本包含的合法括号子串长度 dp[i-1]以及外层括号再往前一段的合法长度。代码实现#include bits/stdc.h using namespace std; int longestValidParentheses(string s) { int n s.size(); vectorint dp(n, 0); int ans 0; for (int i 1; i n; i) { if (s[i] )) { if (s[i - 1] () { dp[i] (i 2 ? dp[i - 2] : 0) 2; } else if (i - dp[i - 1] 0 s[i - dp[i - 1] - 1] () { dp[i] dp[i - 1] 2 (i - dp[i - 1] 2 ? dp[i - dp[i - 1] - 2] : 0); } ans max(ans, dp[i]); } } return ans; } int main() { string s; while (getline(cin, s)) { cout longestValidParentheses(s) endl; } return 0; }这题核心难点就是那个下标变换i - dp[i - 1] - 1。很多人第一眼看到会觉得莫名其妙的其实你画一个例子就清楚了。括号串 :()(()) 在 i5 这个位置dp[4]2内层()i - dp[i-1] - 1 5 - 2 - 1 2s[2] 是 (正好和 s[5] 的 ) 配对然后再往前的 dp[0] 是 0所以 dp[5]0224。多画几组例子这个转移方程就不难记了。3.2 最长无重复子串窗口思想的雏形字符串题里另一个高频考点是“最长无重复字符的子串”。2016年的时候这题叫法很朴素但内核就是后来 LeetCode 第3题的滑动窗口。题目给你一个字符串要求返回其中最长的、不包含重复字符的子串长度。我见过很多人直接暴力三层循环枚举起点、枚举终点、检查这一段有没有重复字符。这样写在小字符串上没问题但一旦长度到 10^5 级别复杂度是 O(n^3)基本宣告超时。正确做法是维护一个滑动窗口用哈希表记录窗口内每个字符最后一次出现的位置。#include bits/stdc.h using namespace std; int lengthOfLongestSubstring(string s) { vectorint last(256, -1); int left 0, ans 0; for (int right 0; right (int)s.size(); right) { char c s[right]; if (last[(int)c] left) { left last[(int)c] 1; } last[(int)c] right; ans max(ans, right - left 1); } return ans; } int main() { string s; while (getline(cin, s)) { cout lengthOfLongestSubstring(s) endl; } return 0; }这里有个细节为什么用 int[256] 而不是 unordered_map因为字符的 ASCII 范围是固定的用数组可以直接索引访问时间是 O(1)没有哈希冲突和扩容开销实测在大数据量下比 unordered_map 快不少。笔试环境对性能要求苛刻能用数组的地方就别偷懒用容器。滑动窗口的核心思想说起来很简单右指针不断右移扩张窗口如果遇到了重复字符就把左指针跳到重复字符上次出现位置的下一个保证窗口内始终无重复。窗口里的内容变了窗口长度随时更新。这个思路后面做“最小覆盖子串”、“字符串排列”之类的题都能复用属于基础中的基础。4. 动态规划与递推类区分度的分水岭4.1 最长上升子序列的贪心优化从O(n^2)到O(n log n)动态规划类题目基本是每套笔试题里的分水岭能不能拿高薪offer往往就看最后这一两道压轴题做得怎么样。百度这套题里有一道经典的最长上升子序列LIS但数据范围设计得很有意思如果用常规的 O(n^2) DP只能过一半测试点必须用贪心二分的优化版才能拿到满分。常规做法是 dp[i] 表示以第 i 个数结尾的最长上升子序列长度每到一个位置就往前扫一遍找到比当前数小的位置里 dp 值最大的那个加一。状态转移很简单但复杂度是 O(n^2)。优化版的思路非常巧妙。我们维护一个数组 tails其中 tails[i] 表示长度为 i1 的上升子序列的末尾元素的最小值。这个数组一定是严格递增的。每遍历一个新元素就用二分查找在 tails 里找第一个大于等于它的位置如果找到了就替换掉如果没找到就在末尾追加。最终 tails 的长度就是答案。#include bits/stdc.h using namespace std; int lengthOfLIS(vectorint nums) { vectorint tails; for (int num : nums) { auto it lower_bound(tails.begin(), tails.end(), num); if (it tails.end()) { tails.push_back(num); } else { *it num; } } return tails.size(); } int main() { int n; while (cin n) { vectorint nums(n); for (int i 0; i n; i) cin nums[i]; cout lengthOfLIS(nums) endl; } return 0; }为什么贪心成立原因是对于一个相同长度的上升子序列末尾元素越小后面能接上更多元素的可能性就越大。所以每个长度都保留末尾最小的那个就是局部最优选择而这一系列局部最优可以推导出全局最优。这个套路也叫耐心排序和纸牌游戏的规则很像理解了那个游戏这个优化就永远忘不掉。4.2 完全背包与最少硬币组合的状态设计另一道让我印象深刻的动态规划题是“找零钱最少硬币数”。给定若干种面值的硬币每种硬币数量无限问组成指定金额需要的最少硬币数不能组成时返回 -1。这就是典型的完全背包问题。这题的状态定义非常直观dp[i] 表示组成金额 i 需要的最少硬币数。初始化 dp[0]0其余都设成一个很大的数。然后遍历每枚硬币从硬币面值开始到目标金额更新 dp[j] min(dp[j], dp[j - coin] 1)。内层循环为什么必须正序这是完全背包和01背包最关键的区分点。01背包要求每个物品只能用一次所以内层要倒序遍历防止用同一个物品覆盖自己两次完全背包允许无限使用同一硬币正序遍历反而可以充分利用本轮更新过的状态实现“叠加使用”的效果。如果我把循环写成倒序那就是把无限背包变成了有限背包答案多半是错的。#include bits/stdc.h using namespace std; int coinChange(vectorint coins, int amount) { vectorint dp(amount 1, amount 1); dp[0] 0; for (int coin : coins) { for (int i coin; i amount; i) { dp[i] min(dp[i], dp[i - coin] 1); } } return dp[amount] amount 1 ? -1 : dp[amount]; } int main() { int n, m; while (cin n m) { vectorint coins(n); for (int i 0; i n; i) cin coins[i]; cout coinChange(coins, m) endl; } return 0; }这道题我在带人刷题时发现一个常见问题初始化数组时图省事用 memset(dp, 0x3f, sizeof(dp))或者用 INT_MAX。用 INT_MAX 会有一个隐患后面取 min 的时候如果再加 1可能直接溢出变成负数导致状态被污染。正确做法是初始化成 amount1因为它一定大于任何可行解的数量又不会在加法中溢出。这种细节在平时刷 LeetCode 不会被发现但在笔试的隐藏测试用例里就是送命题。5. 在线笔试的实战细节与调试策略5.1 环境与输入输出笔试里最容易扣分的隐形坑代码逻辑写对不等于能过我见过太多人倒在输入输出上。国内不少公司的笔试系统是 ACM 风格它不会给你一个函数接口而是要求你从标准输入读数据、往标准输出写结果。这意味着你写的 main 函数必须能正确处理多组输入、空行、末尾换行等等。我的习惯是上来先写一个读取模板固定住输入输出骨架再往里面填业务逻辑。多组数字行就用 while (cin n)多组带空格的字符串就用 while (getline(cin, line))如果一行里既有字符串又有数字就用 stringstream 拆分。先把这些模板练熟考试时就不会因为 IO 卡壳。还有一点局部变量别开太大。如果直接在函数里声明 int a[1000000]栈空间可能不够直接爆掉。数据量大时用 vector 或者 new 分配堆内存别挑战系统限制。递归同理深度太深容易栈溢出能用迭代就别递归。5.2 时间复杂度的自我评估方法在线编程题提交之后系统会告诉你超时还是答案错误。超时很多时候不是某一个测试点的问题而是你整个算法复杂度不达标。建议在动手写代码之前先看一眼数据范围做一次心算n 在 10^6 级别O(n log n) 可以过O(n^2) 大概率超时。n 在 10^4 级别O(n^2) 勉强能过O(n^3) 基本完蛋。n 在 500 以内才有资本写三重循环。我在复盘百度这套题时特意把每道题的数据范围都查了一遍。发现他们出题很克制不会故意放一个 10^9 的数据来卡你但常规的复杂度陷阱是存在的。如果你发现自己的算法里有个双层循环而 n 是 10^5那就要警惕了大概率需要优化成双指针、二分或者动态规划的滚动数组。另外做题时不要一上来就闷头写最复杂的解法。先把暴力解写出来跑通样例确保自己对题意的理解没有偏差然后再尝试优化。这个顺序能救你很多次——因为很多时候你觉得是超时问题实际上是题意理解错了暴力解至少能帮你确认方向。6. 常见问题与避坑经验实录6.1 高频错误速查表把复盘过程中遇到的错误整理成一张表方便大家对号入座问题类型典型表现原因解决办法输入输出错误只过第一个样例没处理多组输入用 while(cinn) 读到文件结束比较函数错误排序结果不稳定cmp 参数未用 const 引用或逻辑不完整都写成 const T包含相等分支数组越界本地正常提交报错访问 i-1、i1 前未判断边界循环从 1 开始或加边界保护动态规划初始化错误结果偏大偏小INF 设置成 INT_MAX 导致溢出初始化为 amount1 或 0x3f3f3f3f超时大数据点过不去算法复杂度不达标提前根据数据范围选算法输出格式错误提示 Presentation Error行尾空格或换行不一致按题目要求严格处理空白字符栈溢出递归深度大时崩溃系统栈空间有限改成循环或显式栈这张表里的错误我基本都踩过一遍。尤其是 INF 设置成 INT_MAX 那个早年刷背包题时被坑得很惨一度以为是自己状态转移写错了最后单步调试才发现是溢出问题。后来我统一习惯用 0x3f3f3f3f 这个魔数它大约等于 10^9足够大又不会在加法中溢出而且 memset 可以直接按字节填充非常方便。6.2 我踩过的坑和总结的刷题方法复盘这些题的时候我也想明白一个道理在线编程题考的不只是“会不会做”更是“在压力下能不能稳定发挥”。很多学弟学妹问我刷题要不要把所有题都刷完我的回答一直是不用。按题型归类、把每类题的核心模型吃透效果远好于毫无头绪地海量刷题。我的具体做法是每道经典题至少刷三遍。第一遍不看任何资料独立写出一个能过的版本第二遍做完之后去翻最优题解理解更高效的算法第三遍隔一周之后回来重新写强制自己不看之前代码。三遍下来这个知识点才真正长在你身上。最后一个小建议复盘时不要只盯着自己会的题。百度这套题里真正拉开差距的往往是那道动态规划压轴题。如果你能在 30 分钟内把 4.1 和 4.2 两道题的优化版都写出来并且把状态转移的边界条件说得清清楚楚那道题基本就稳了。算法的东西没有捷径但用正确的方法练习完全可以在有限时间内达到应试水平。