企业官网建设流程全解析

前阵子整理云盘，翻出一套2016年百度研发工程师在线编程题的存档。说实话，刚看到年份时我愣了一下——互联网公司的笔试题目两年一小变、五年一大变，2016年的题还能有多少参考价值？但耐着性子把几道典型题重新做了一遍，我发现一个挺扎心的事实：那些题目里藏着的算法考点，到现在依然是各大厂笔试的主力军。排序、栈、字符串、动态规划，换了一层更花哨的包装，内核还是那几个经典模型。

所以这篇文章我想认真拆一拆这套题。我会按题型把这些在线编程题归类，讲清楚每道题的思路推演过程、关键代码、边界条件和复杂度，再加上这些年我实际刷题、带人备战笔试时踩过的坑。适合正在准备秋招春招的应届生，也适合想系统补算法基础的开发者——哪怕你不参加笔试，把这几类模型的思路吃透，日常写代码也会顺手很多。

1. 先搞清楚：这套题到底在考什么

1.1 为什么2016年的题还有参考价值

很多人一听是几年前的题就直接划走，觉得技术迭代这么快，老题肯定过时了。但算法题恰恰是互联网公司笔试里最“保值”的部分。2016年考最长上升子序列，2026年还在考，只是数据范围从 n<=1000 变成了 n<=10^5，要求从 O(n^2) 优化到 O(n log n)。考的不是你会不会背模板，而是你在新约束下能不能反应过来该换什么做法。

百度这类公司的在线编程题，一向出得比较朴实，不太喜欢故意刁难人的偏题怪题。题目包装往往很真实，可能是一个搜索场景、一个数据统计场景，但剥掉外壳之后就是经典的排序、栈、动态规划模型。正因为如此，这套题特别适合用来做“算法基础体检”——每一道题都能精准检验你对某个基础模型的理解深度。

顺便提一句，百度每年还有“百度之星”这类程序设计竞赛，有些校招笔试题目和竞赛题的风格是相通的。刷2016年的笔试题，相当于提前熟悉一下这个出题体系的味道，对目标明确想进这类公司的同学来说，性价比很高。

1.2 出题人的评估逻辑

在线编程题和平时刷 LeetCode 有个很大的不同：它是在限时、限内存、限环境的条件下完成的，而且会通过隐藏测试用例来卡极端情况。所以想拿高分，光是把样例跑通远远不够。

出题人评估的维度通常有这么几个：

• 正确性：核心逻辑是否对，特殊输入（空串、n=0、负数、重复元素）是否处理。
• 效率：算法复杂度是否在题目要求范围内，会不会在大数据量下超时。
• 代码规范：变量命名、结构分层是否清晰，面试官线下看代码时观感如何。
• 工程习惯：内存是否合理，有没有不必要的拷贝，有没有明显的浪费。

那几年百度在线编程题的整体分布，按我的复盘大概可以分成四类：模拟与排序、数据结构与字符串、动态规划与递推，还有一类是数学/位运算。频率我放一个表，方便大家对照着查漏补缺：

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) { vector<Node> 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 做题时的边界处理与输入输出细节

这种模拟排序题，隐藏测试用例最爱出的就是极端情况：n=1 时输出是否正常，n=0 时能不能跳过输出，所有记录权值都相等时是否退化成纯ID升序，ID很大时 int 是否够用。我在复盘时试过几个常见的错误写法，比如没有处理 n=0 直接访问 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(); vector<int> 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。很多人第一眼看到会觉得莫名其妙的，其实你画一个例子就清楚了。括号串 ":()(())" 在 i=5 这个位置，dp[4]=2（内层"()"），i - dp[i-1] - 1 = 5 - 2 - 1 = 2，s[2] 是 '('，正好和 s[5] 的 ')' 配对，然后再往前的 dp[0] 是 0，所以 dp[5]=0+2+2=4。多画几组例子，这个转移方程就不难记了。

3.2 最长无重复子串：窗口思想的雏形

字符串题里另一个高频考点是“最长无重复字符的子串”。2016年的时候这题叫法很朴素，但内核就是后来 LeetCode 第3题的滑动窗口。题目给你一个字符串，要求返回其中最长的、不包含重复字符的子串长度。

我见过很多人直接暴力三层循环：枚举起点、枚举终点、检查这一段有没有重复字符。这样写在小字符串上没问题，但一旦长度到 10^5 级别，复杂度是 O(n^3)，基本宣告超时。正确做法是维护一个滑动窗口，用哈希表记录窗口内每个字符最后一次出现的位置。

#include <bits/stdc++.h> using namespace std; int lengthOfLongestSubstring(string s) { vector<int> 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] 表示长度为 i+1 的上升子序列的末尾元素的最小值。这个数组一定是严格递增的。每遍历一个新元素，就用二分查找在 tails 里找第一个大于等于它的位置，如果找到了就替换掉，如果没找到就在末尾追加。最终 tails 的长度就是答案。

#include <bits/stdc++.h> using namespace std; int lengthOfLIS(vector<int>& nums) { vector<int> 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) { vector<int> 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(vector<int>& coins, int amount) { vector<int> 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) { vector<int> 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，可能直接溢出变成负数，导致状态被污染。正确做法是初始化成 amount+1，因为它一定大于任何可行解的数量，又不会在加法中溢出。这种细节在平时刷 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 高频错误速查表

把复盘过程中遇到的错误整理成一张表，方便大家对号入座：

这张表里的错误，我基本都踩过一遍。尤其是 INF 设置成 INT_MAX 那个，早年刷背包题时被坑得很惨，一度以为是自己状态转移写错了，最后单步调试才发现是溢出问题。后来我统一习惯用 0x3f3f3f3f 这个魔数，它大约等于 10^9，足够大又不会在加法中溢出，而且 memset 可以直接按字节填充，非常方便。

6.2 我踩过的坑和总结的刷题方法

复盘这些题的时候我也想明白一个道理：在线编程题考的不只是“会不会做”，更是“在压力下能不能稳定发挥”。很多学弟学妹问我刷题要不要把所有题都刷完，我的回答一直是不用。按题型归类、把每类题的核心模型吃透，效果远好于毫无头绪地海量刷题。

我的具体做法是每道经典题至少刷三遍。第一遍不看任何资料，独立写出一个能过的版本；第二遍做完之后去翻最优题解，理解更高效的算法；第三遍隔一周之后回来重新写，强制自己不看之前代码。三遍下来，这个知识点才真正长在你身上。

最后一个小建议：复盘时不要只盯着自己会的题。百度这套题里真正拉开差距的，往往是那道动态规划压轴题。如果你能在 30 分钟内把 4.1 和 4.2 两道题的优化版都写出来，并且把状态转移的边界条件说得清清楚楚，那道题基本就稳了。算法的东西没有捷径，但用正确的方法练习，完全可以在有限时间内达到应试水平。