很长时间没这么痛快地刷完一套题了。这套 2017 春招笔试真题编程题集合，我断断续续刷了两轮，第一轮被字符串排序和动态规划教做人，第二轮才真正摸到门道。今天不打算把每道题原封不动贴一遍，而是想把题目背后共通的东西聊透：考点怎么拆、代码怎么写、现场怎么排错。无论你是准备实习春招，还是单纯想检验一下自己的算法基本功，这套题的覆盖面都足够典型，值得拿来当一面镜子照一照。

现在很多同学刷题喜欢按难度刷，从 Easy 到 Hard 一路刷过去，结果到了笔试现场发现时间根本不够用。为什么？因为在线笔试考的不只是“会不会这个算法”，还包括“在压力下能不能写对”。这套 2017 春招的题目恰好就在这个位置上：看起来每道题都不超纲，但能拿满分的没几个。我今天就从题型的角度先拆一遍，再挑几个高频考点做完整推演，最后把我实战中踩过的坑和排查方法整理成清单，希望你看完能少走一段弯路。

1. 先拆题：这套真题集合的考察面与刷题策略

1.1 从题型分布看笔试出题逻辑

我第一轮拿到这套题，第一个感觉是“怎么又有字符串又有 DP”。后来把题目归类整理了一下，发现它并不是随便拼凑的，而是有明显侧重点。下面这张表是我自己整理的题型分布，不一定和官方分类完全一致，但足够反映问题：

仔细观察你会发现，这套题几乎没有“偏难怪”的算法题，没有让你现场发明一个从没见过的数据结构。它考的全是基础算法里的经典模型，但每个模型都埋了一两个很容易忽视的细节。这其实就是大厂笔试的典型出题逻辑：题目要让大多数人在 20 分钟内能写出一个“能跑的版本”，但只有少数人能注意到边界条件、数据范围、输出格式这些隐性要求，从而拿到全部测试点。

从这个角度说，刷这套题不能只满足于“样例通过了”。样例通过只是起点，真正需要做的是把每个边界条件问一遍：如果数组为空怎么办？如果输入全是 0 怎么办？如果两个区间端点恰好重合算不算重叠？这些细节才是笔试拉开差距的地方。

1.2 刷题顺序怎么安排才不浪费时间

我第一轮刷的时候是按题号顺序硬啃，结果做到动态规划卡了很久，后面简单题反而没时间细看，心态也有点崩。第二轮我调整了顺序，效果好得多。我的建议是分三步走：

1. 先花十几分钟把所有题快速扫一遍，在题目旁边标上“思路清晰”“有思路但没把握”“完全没头绪”三个等级，不要急着动键盘。
2. 按类型分组刷：字符串处理 -> 贪心 -> 数据结构模拟 -> 动态规划。字符串和模拟题比较容易建立信心，贪心题能训练“先证明再写代码”的习惯，DP 需要整块时间专门啃。
3. 每刷完一类，不要立刻刷下一类，先回头把做过的题重新测一遍边界，再把代码整理成自己的模板。

为什么这么排列？因为笔试最忌讳“前面卡住后面崩盘”。字符串和模拟题通常代码量大但思维难度低，先用它们热身，能让你进入状态；贪心题难度适中，可以锻炼你在有限时间内判断方案正确性的能力；DP 是最耗脑子的，放在后面单独攻，就算思考时间长一点，也不至于影响前面题目的得分。

还有一个很多人忽略的点：刷题一定要模拟真实笔试环境。给自己定 100 分钟，打开一个本地 IDE，关掉聊天工具，全程只依赖代码和注释，不允许看题解。如果平时习惯了“看一眼思路就动手”，到笔试时你大概率会在同样一道题上多花一倍时间。模拟环境的作用就是让你提前体验那种紧张感，练出肌肉记忆。

2. 高频考点逐个拆解：字符串、动态规划与贪心

2.1 字符串拼接最大数：比较器与溢出陷阱

这套题里有一道很经典的字符串处理题：给一组非负整数，要求把它们按某种顺序拼接成一个最大的数。比如输入 3、30、34、5、9，输出应该是 9534330。这道题我第一次做的时候想得很简单：把所有数字转成字符串，按字典序从大到小排个序，直接拼接不就行了？

结果不对。问题不是出在“转字符串”，而是出在“字典序从大到小”这个比较规则。举个例子：98 和 9，按字典序排列，98 会排在 9 前面，拼接结果是 989；但正确的最大拼接应该是 998，也就是 9 应该排在 98 前面。再比如 12 和 121，按数值大小比较，121 比 12 大，先排 121 得到 12112，但 12 和 121 拼接的最大结果是 12121，也就是 12 应该排在前面。

这说明什么？字符串拼接的顺序不能依靠单个字符串的大小，必须看两个字符串拼接后的相对顺序。正确的比较器应该是：如果 a 拼在 b 前面得到 ab，b 拼在 a 前面得到 ba，那么当 ab > ba 时，a 应该排在 b 前面。

用 C++ 写出来是这样的：

#include <bits/stdc++.h> using namespace std; bool cmp(const string& a, const string& b) { return a + b > b + a; } string largestNumber(vector<int>& nums) { vector<string> strs; for (int x : nums) { strs.push_back(to_string(x)); } sort(strs.begin(), strs.end(), cmp); if (strs[0] == "0") { return "0"; } string res; for (const string& s : strs) { res += s; } return res; }

这段代码里有几个细节特别值得说。第一，为什么不能直接把数字转成 int 或 long long 再比大小？因为如果输入的数字很多、位数很长，ab 和 ba 拼接后的数值很容易超过 64 位整数的范围。用字符串比较可以完全避开溢出问题，这是这道题埋得最深的坑。

第二，strs[0] == "0"这个判断不能省。如果输入是 0 和 0，按比较器排序后数组里全是 "0"，直接拼接会得到 "00"、甚至 "000"，但正确答案是 "0"。类似的，只要排序后第一个字符串是 "0"，说明整个数组的所有非负整数实际上都为 0，返回 "0" 才对。

第三，比较器需要满足严格弱序。我一开始写的是return a + b >= b + a;，加上了等号，结果 sort 排序时行为就不稳定，甚至可能引发逻辑错误。排序比较器的正确写法是用>，等于的情况应该返回 false。这个问题很难靠样例测出来，但数据一多就会暴露。建议你写完比较器后用 [98,9]、[12,121]、[0,0] 这三组数据分别自测。

2.2 编辑距离：状态定义和滚动数组优化

编辑距离这道题，我在第一轮花了将近四十分钟才写出来，而且一开始的版本内存超限了。题目描述很简单：两个字符串 word1 和 word2，每次操作可以插入一个字符、删除一个字符、替换一个字符，问把 word1 变成 word2 最少需要多少次操作。

我最初的想法是逐字符比较，完全绕不开“后面的字符可能会影响前面操作”这个问题。后来老老实实用 DP，才发现状态定义才是这题的关键。设dp[i][j]表示把 word1 的前 i 个字符变成 word2 的前 j 个字符所需要的最小操作数。这里 i 和 j 是“前缀长度”，不是下标。

为什么这个定义好用？因为字符串变化的过程可以拆成三个来源：

• 先删掉 word1 的第 i 个字符，然后处理剩下 i-1 个字符到 word2 前 j 个字符的转换，对应dp[i-1][j] + 1；
• 在 word1 前 i 个字符后面插入一个 word2 的第 j 个字符，先处理 i 个字符到 j-1 个字符，再插入一个，对应dp[i][j-1] + 1；
• 替换或匹配 word1 的第 i 个字符和 word2 的第 j 个字符，如果相等就不需要额外代价，否则替换一次，对应dp[i-1][j-1] + (相等 ? 0 : 1)。

代码写出来是这个样子：

int minDistance(string word1, string word2) { int m = word1.size(), n = word2.size(); vector<vector<int>> dp(m + 1, vector<int>(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) { dp[i][j] = min({ dp[i - 1][j] + 1, dp[i][j - 1] + 1, dp[i - 1][j - 1] + (word1[i - 1] == word2[j - 1] ? 0 : 1) }); } } return dp[m][n]; }

初始化是很容易出错的地方。dp[i][0] = i表示把一个长度为 i 的字符串变成空串，只能全部删除，所以需要 i 次操作；dp[0][j] = j表示把一个空串变成长度 j 的字符串，只能全部插入，所以需要 j 次操作。很多人会漏了第二行初始化，结果整个 DP 表第一列算对了，第一行却是 0，答案自然就错了。

如果你担心二维数组在笔试环境里内存爆炸，可以用滚动数组优化。因为每个dp[i][j]只依赖上一行和当前行，所以只需要一维数组加一个临时变量保存左上角的值。推荐把滚动数组版本也写熟：

int minDistanceRoll(string word1, string word2) { int m = word1.size(), n = word2.size(); vector<int> 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 tmp = dp[j]; dp[j] = min({ dp[j] + 1, dp[j - 1] + 1, prev + (word1[i - 1] == word2[j - 1] ? 0 : 1) }); prev = tmp; } } return dp[n]; }

这个版本的关键在prev变量。循环每次更新前，prev保存的是上一行的dp[j-1]，也就是二维版本里的dp[i-1][j-1]。如果先更新dp[j]再存prev，值就错了。我写过很多次滚动数组，踩坑心得是：先把tmp = dp[j]存下来，处理完dp[j]后再把tmp赋给prev，顺序不能反过来。

2.3 区间合并：贪心为什么有效

区间合并是这套题里看起来最简单、但也很能拉开分的题。题目说给一组区间，比如 [1,3] 和 [2,6] 有重叠，要合并成 [1,6]；如果下一个区间是 [8,10]，跟 [1,6] 不重叠，就原样保留。

我第一次做这道题时，下意识想用两层循环：每来一个新区间，就遍历一遍已经合并好的结果，看它和谁重叠。这样做不仅代码丑，还容易漏处理“合并后产生的新区间又和另一个区间重叠”的情况。后来我换成排序加单次扫描，一下就清晰了。

思路是这样：先把所有区间按左端点从小到大排序，然后维护当前正在合并的区间的左端点 L 和右端点 R。从头往后扫描，如果下一个区间的左端点不超过 R，说明和当前区间有重叠，用max(R, next.R)更新 R；如果左端点大于 R，说明当前合并区间已经到极限了，把它加入答案，然后让 L 和 R 指向下一个区间。

vector<vector<int>> merge(vector<vector<int>>& intervals) { if (intervals.empty()) { return {}; } sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b) { return a[0] < b[0]; }); vector<vector<int>> res; int L = intervals[0][0], R = intervals[0][1]; for (int i = 1; i < (int)intervals.size(); ++i) { if (intervals[i][0] <= R) { R = max(R, intervals[i][1]); } else { res.push_back({L, R}); L = intervals[i][0]; R = intervals[i][1]; } } res.push_back({L, R}); return res; }

为什么贪心在这里是正确的？因为排序之后，所有可能和当前区间重叠的区间都紧挨着排在一起，不会出现“间隔了一个不重叠区间又冒出一个重叠区间”的情况。所以一次扫描足够，不需要回头处理。理解这个“贪心正确性”很重要，否则面试官问你为什么不用两重循环，你自己也说不清。

有一个边界要特别小心：如果下一个区间的左端点恰好等于当前 R，这也算重叠。比如 [1,4] 和 [4,5]，题目要求合并成 [1,5]，所以判断条件必须是intervals[i][0] <= R，不是<。我见过不少人在这个小于号上栽跟头，样例里往往没有端点相等的情况，你能想到说明边界意识在线。

3. 从真题到代码：我的完整实现与踩坑记录

3.1 输入输出处理与代码模板

在线笔试和本地刷题最大的不同，就是输入输出格式非常死板。有些题目第一行给一个整数 n，然后第二行给 n 个字符串；有些题目不给 n，而是让你一直读，读到文件结束。这套真题集里两种格式都有，所以我建议你准备一套能应对两种情况的模板，减少临场思考成本。

我常用的 C++ 模板长这样：

#include <bits/stdc++.h> using namespace std; string solve(vector<int>& nums) { // 核心逻辑 } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; while (cin >> n) { vector<int> nums(n); for (int i = 0; i < n; ++i) { cin >> nums[i]; } cout << solve(nums) << '\n'; } return 0; }

ios::sync_with_stdio(false)和cin.tie(nullptr)这两行不能忘。它们能让 cin/cout 的运行速度明显提升，尤其是在输入量很大的时候。我自己实测过，同样一组数据，不加速可能比加速慢 20% 到 50%。笔试环境里每个题目的时间限制通常只有一两秒，这种小细节很关键。

还有一点，有些题目格式是“第一行是 n，后面接下来 n 行每行一个输入”，有些则是“输入包含多组测试数据”。遇到多组数据时，用while (cin >> n)就可以自动读到文件结束，比for循环固定次数更稳妥。如果你判断不出到底有几组，优先用 while 读，这是我踩过不少坑后总结出来的经验。

3.2 字符串拼接题的完整实现与运行验证

把前面那套字符串拼接的核心逻辑补上输入输出，就是一道可以完整提交的程序。我写代码时习惯把核心逻辑单独抽成函数，这样调试起来方便，也能避免 main 函数里堆太多临时变量导致心智负担。

#include <bits/stdc++.h> using namespace std; static bool cmp(const string& a, const string& b) { return a + b > b + a; } string largestNumber(vector<int>& nums) { vector<string> strs; for (int x : nums) { strs.push_back(to_string(x)); } sort(strs.begin(), strs.end(), cmp); if (strs[0] == "0") { return "0"; } string res; for (const string& s : strs) { res += s; } return res; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; while (cin >> n) { vector<int> nums(n); for (int i = 0; i < n; ++i) { cin >> nums[i]; } cout << largestNumber(nums) << '\n'; } return 0; }

写完这段代码之后，我习惯立刻跑三组用例。第一组是标准样例：3、30、34、5、9，期望输出 9534330；第二组是反直觉用例：98、9，期望输出 998；第三组是全零用例：0、0、0，期望输出 0。这三组跑完，比较器、全零处理、拼接这三块基本都能覆盖到。

我在第一轮犯的一个特别蠢的错误是，把所有数字转成字符串之后，用了默认的字典序降序排序，结果遇到 98 和 9 这种用例直接错了。当时我没有立刻怀疑比较器，反而以为是字符串拼接顺序写错了，查了半天。后来养成的习惯是：凡是排序相关的题，先检查比较器是否满足传递性，再检查边界数据。

3.3 编辑距离的 DP 表手算过程

动态规划题最容易出错的不是转移方程，而是初始化。光靠想很难发现自己的问题，所以我建议你在纸上或者注释里把 DP 表手算一遍。以 word1="horse"、word2="ros" 为例：

先初始化的第一行表示从空串变到 "r"、"ro"、"ros"，代价分别是 1、2、3；第一列表示把 "h"、"ho"、"hor" 变成空串，代价是 1、2、3、4。然后按行从上到下填表：

手算到第二行，你就会发现 “h” 变 “r” 的最小代价是 1，因为把 h 替换成 r 就行；第二行第三列 “h” 变 “ro” 的代价是 2，可以 h 替换成 r，再插入 o。这个过程不复杂，但能帮你确认状态转移的每个分支都覆盖到了，尤其是dp[i-1][j-1]那个斜向上的值没有被漏掉。

在笔试现场，我建议你先花两分钟在草稿纸上画一个 4x4 的小表，跑一遍相等和不相等的两个字符变化，确认状态转移没有写反，再铺开写完整代码。这样做的成本很低，但能避免提交后才发现初始化错误。

3.4 区间合并的边界用例验证

区间合并的代码不长，但边界用例特别多。我整理了一份自测清单，每次写完代码都用它过一遍：

输入：[[1,3],[2,6],[8,10],[15,18]] 期望输出：[[1,6],[8,10],[15,18]] 输入：[[1,4],[4,5]] 期望输出：[[1,5]] 输入：[[1,4],[2,3]] 期望输出：[[1,4]] 输入：[] 期望输出：[] 输入：[[5,5],[5,5]] 期望输出：[[5,5]]

第一组是常规用例，验证基本合并逻辑；第二组验证左端点等于右端点时仍算重叠；第三组验证一个区间完全被另一个区间包含时，右端点取 max；第四组验证空数组不会崩溃；第五组验证左右端点相同这种极窄区间也能正常处理。

我曾经在第二组用例上翻过车，因为我把合并条件写成了intervals[i][0] < R，严格小于，结果 [1,4] 和 [4,5] 没有被合并。后来我特意把这类“端点相接”的用例加进自测清单，之后再没犯过同样的错误。建议你也维护一份自己的用例清单，每次写排序、区间相关的题都拿出来跑一遍。

4. 笔试实战中的常见问题与排查技巧实录

4.1 本地跑得好好的，一提交就错是怎么回事

这是我被问得最多的问题。代码在本机怎么测都对，样例也过了，一交上去就是 Wrong Answer，甚至 Runtime Error。根据我刷这套真题集合的经验，问题往往出在以下几个地方：

第一个是输入数据范围。笔试题目里经常隐藏大数，比如字符串拼接题里每个数的位数可能很长，动态规划题的字符串长度可能达到几千。如果你没有注意到数据范围，用 int 保存中间结果，很容易溢出。建议读题时养成标注数据范围的习惯，看到10^9、10^5这种量级，第一时间用 long long，而不是等提交失败再排查。

第二个是边界条件。最常见的边界是空数组、单元素数组、所有元素相同、最大长度这种极端值。如果你只是在标准样例上验证，这些边界全都会被漏掉。我的做法是给每个核心函数都准备一个边界用例，不需要很多，但空、单元素、全零这三类一定要有。

第三个是输出格式。在线笔试系统通常要求输出精确匹配，多一个空格、少一个换行都可能判错。比如多组输出时最后一行是否要换行，每行的数字之间用空格还是逗号，这些都要从题目描述里确认。实在不确定的话，参考样例输出的格式，严格照抄。

第四个是全局变量复用的坑。如果你写了多组数据循环，每次循环开始前没有把全局容器清空，上一组的数据就会残留到下一组，导致结果错误。推荐做法是把核心逻辑封装成函数，所有临时变量都放在函数内部，每次调用都是全新的一份，不要靠全局变量传数据。

4.2 时间不够怎么办：取舍与调试策略

一套笔试编程题通常有 3 到 5 道题，时间 100 分钟到 120 分钟。这个时间节奏意味着，你不可能每道题都做到满分。我的策略是“先拿基本分，再拼优化分”。

具体来说，拿到题目后我会先花 5 分钟把所有题都扫一遍，对每道题的难度做一个快速判断。自己最有把握的题，比如字符串排序、区间合并这类，马上动手，目标是拿到所有测试点；中等难度的题，先写出基础解法，保证正确性，如果时间还有富余再优化；一时没思路的题，绝对不恋战，先跳过，最后回头用暴力解至少拿一部分分数。

调试策略上，我强烈建议你在写代码之前就把关键变量的预期值写在注释里。比如写编辑距离时，我会注释“dp[2][3] 表示 word1 前两个字符到 word2 前三个字符的最小代价”，这样一旦输出不对，可以单步追踪到这个具体位置，而不是对着整张 DP 表发愣。实测下来，这个方法比盲目加日志高效很多。

另外，不要小看暴力解的价值。有些题要求最优解，但暴力解能过 30% 到 50% 的测试点。在时间有限的情况下，一个跑得慢但逻辑正确的程序，比一个没写完的程序得分高得多。先拿到这部分分数，再逐步优化。

4.3 一套能直接用的检查清单

刷完这套真题集合之后，我把最容易出错的点整理成了一张检查清单，笔试前快速过一遍能显著降低翻车率：

这个清单不是一次就能形成的，我是刷完第二轮、总结了所有 Wrong Answer 之后才整理出来的。你现在看到可能觉得条目有点多，但每一条背后都是我真实踩过的坑。笔试前把清单在脑子里快速过一遍，很多时候要比多刷两道题更管用。

最后说点个人体会。我刷完这套题之后，最大的收获不是背下了几道解法，而是学会了一件事：拿到题目先不急着写代码，先把边界情况在脑子里过一遍。像字符串拼接那道题，如果你想当然地用数值比较，样例能过，提交才原形毕露。笔试拼的从来不只是会不会算法，而是能不能在有限时间内写出不出错的代码。这套题集合非常适合用来检验这一点。如果你最近也在准备实习面试，建议按我上面说的顺序刷，刷完再回头看看哪些地方容易翻车，一定比盲目刷题有收获得多。