最近整理刷题仓库的时候把某度2017春招笔试真题编程题集合重新撸了一遍。这套题是我当年准备春招时反复练过的一个合集提交记录里的 ID 还留着Apare_xzc。现在回头看这套题最好的地方在于覆盖面非常典型排序、模拟、枚举、贪心、动态规划全都有难度也从一个简单到中等适合正处于笔试冲刺期的同学拿来当“体检题”。如果你准备参加校招或者找暑期实习又没太多时间刷海量题目我建议你花一到两周把这套题吃透效果比漫无目的刷几十道要实在得多。很多刚接触笔试的人会误以为春招真题都是难题实际并不是。这套题里真正需要绕几个弯的题目大概只有三分之一剩下的更像是“能不能写对边界条件”的考察。换句话说笔试除了考算法思维更多是考你有没有把一道题做完整、做严谨。这也是我写这篇复盘的原因把每一道值得展开的题掰开揉碎讲讲我当时是怎么想的中间踩过哪些坑以及最后稳定通过测试的写法。1. 这套题是什么写在刷题之前1.1 题目背景与适合人群某度2017春招笔试真题编程题集合本质上是一套面向应届生的在线笔试题目合集。它不像竞赛题那样烧脑也不像课后作业那样简单而是非常典型的“校招笔试题”每道题都有明确输入输出约束难度控制在大多数计算机专业学生能在一小时内完成两三道的水平。我当时刷它的目的很简单就是想验证自己准备得够不够结果发现第一遍做的时候好几道题都在小细节上翻车比如数组越界、浮点数精度、去重逻辑理解错。这套题适合三类人第一类是即将参加春招或暑期实习笔试的应届生用来查漏补缺第二类是刚开始刷题、想建立笔试节奏感的人可以先通过这套题感受真实笔试难度第三类是已经有一定刷题量但总在边界条件上丢分的人这套题里大量隐藏的“坑”非常适合用来训练严谨性。如果你已经是竞赛水平这套题可能偏简单但仍然可以快速过一遍就当热身。1.2 整体题型分布与难度画像整个集合里我印象比较深的题目大概有五六道知识点分布大致可以拆成下面这个表。注意这里不是官方题单是我根据自己的训练记录重新整理的原题顺序和具体题号可能和网上流传的版本有差异但不影响练习价值。题目代称核心知识点难度建议时间买帽子排序、去重、查找入门10分钟度度熊回家模拟、枚举、绝对值距离简单15分钟寻找三角形计算几何、枚举、叉积中等25分钟有趣的排序序列分析、贪心思想中等偏易20分钟不等式数列动态规划、组合计数中等偏难30分钟进制/字符串题进制转换、字符串处理简单10分钟这套题的难度曲线并不是完全递增的中间突然出现动态规划很容易让人心态波动。我第一遍做的时候习惯从第一题顺序做结果在“有趣的排序”那题卡了很久后来学乖了先整体扫一遍题目把容易拿分的题先做掉再集中啃难题。这个策略在真实笔试里非常有用建议你现在就养成习惯。1.3 我为什么选这套题来练说实话市面上编程题合集非常多但很多合集要么太偏竞赛要么就是简单到没营养。这套题吸引我的地方在于它“刚好卡在笔试水位线上”。所谓笔试水位线就是说题目能一眼看出解法但实现起来总有那么一两个细节在等着你。比如“买帽子”看似只是排序但如果把“第K便宜的价格”理解错去不去重就是完全不同的答案。这种题对思维严谨性的考察比难题更贴近真实笔试。另外这套题还有一个隐藏价值它涉及到的算法组合很标准。枚举、排序、贪心、DP、几何这些正好是技术岗笔试的高频模型。我把这套题刷熟之后再去打其他公司的模拟笔试明显感觉遇到类似题型时反应速度快了很多。所以对我来说它不只是应付某一场笔试更像是一套“算法基础体检套餐”。2. 题型拆解从暴力到最优2.1 买帽子排序题的两种理解先说说最简单的一道“买帽子”。题意大致是商场里有N顶帽子有些帽子价格相同现在想知道第K便宜的价格是多少元如果不存在就输出-1。这道题如果只看前半句很多人第一反应是排序后直接输出第K个元素比如sort完之后取a[k-1]。但这里有个关键陷阱“第K便宜的价格”到底要不要去重如果价格相同的帽子算同一个“价格档位”那要去重后再取第K个如果算不同帽子那直接按下标取。原题意更接近前者因为问的是“价格”不是“帽子”。我第一次做的时候没有去重样例能过但换一组测试数据就错了就是因为对“价格”这个关键词理解不到位。#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; vectorint a(n); for (int i 0; i n; i) cin a[i]; int k; cin k; sort(a.begin(), a.end()); a.erase(unique(a.begin(), a.end()), a.end()); if (k 0 || k (int)a.size()) cout -1 \n; else cout a[k - 1] \n; return 0; }这里的sort加unique是C里非常经典的去重组合。sort把相同元素聚在一起unique把相邻重复元素移到末尾并返回新结尾迭代器再用erase去掉尾巴。需要注意unique只去除“相邻重复”所以必须先排序。另外k可能小于等于0虽然题目通常保证k是正整数但笔试输入偶尔会玩文字游戏我习惯性把非法k也判掉能少一次WA就少一次。2.2 度度熊回家枚举删除点的数学推导“度度熊回家”这道题是典型的模拟题但如果你想清楚原理写起来会非常快。题意大致是一维数轴上有N个点按顺序排列成一个路径度度熊从第一个点出发沿顺序走到最后一个点现在可以选择删除中间某一个点问删除后从起点到终点的总路程最短是多少。最暴力的做法是枚举删除哪个点然后把剩下的相邻点距离全部加起来复杂度O(N^2)。N小的时候没问题但题目如果给到10^5量级就扛不住了。优化的核心是先算出不删除任何点时的总路程再计算删除某个点后“省掉”的距离。对于点i原本会走三段相关路程从i-1到i的距离|a[i] - a[i-1]|从i到i1的距离|a[i1] - a[i]|删除i后这两段会合并成直接从i-1到i1的距离|a[i1] - a[i-1]|注意这些距离本身可能不相等因为是数轴上的点。所以删除点i后总路程的变化量是 saved |a[i] - a[i-1]| |a[i1] - a[i]| - |a[i1] - a[i-1]|答案就是总路程total减去所有saved中的最大值。由于saved一定是非负的所以保留saved最大的删除方式就是最优方案。#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; vectorint a(n); for (int i 0; i n; i) cin a[i]; if (n 2) { cout 0 \n; return 0; } int total 0; for (int i 0; i 1 n; i) { total abs(a[i 1] - a[i]); } int maxSaved 0; for (int i 1; i 1 n; i) { int saved abs(a[i] - a[i - 1]) abs(a[i 1] - a[i]) - abs(a[i 1] - a[i - 1]); maxSaved max(maxSaved, saved); } cout total - maxSaved \n; return 0; }这段代码有一个容易忽略的坑当n等于1或2时根本没有“中间点”可以删除直接输出0。很多人在大样例上WA不是公式错而是没处理这种小数据边界。笔试里这种边界不起眼但往往就藏在第一组测试数据里。2.3 寻找三角形叉积与浮点精度“寻找三角形”是这套题里最早让我意识到“会数学和会编程是两回事”的题目。题目给了若干个三维空间中的点每个点有一个颜色值可能是R、G、B中的一种要求选出三个点组成三角形且三个点颜色要么完全相同要么两两不同然后求这些合法三角形里面积的最大值。解法非常直接三重循环枚举所有三元组先判断颜色条件再计算面积。枚举复杂度O(N^3)如果N在几十到几百量级完全可行。面积计算是这里的重点。三维空间三角形的面积可以用向量叉积的模长来求。假设三个点分别是A、B、C令向量u B - A向量v C - A则叉积的模长|u × v|等于以AB、AC为边的平行四边形面积三角形面积就是它的一半。叉积公式用行列式表示 u × v (u.y * v.z - u.z * v.y, u.z * v.x - u.x * v.z, u.x * v.y - u.y * v.x)模长就是三个分量平方和的平方根。代码实现时要小心坐标是整数但面积可能是浮点数。我建议先算出面积平方最后再开根号可以减少一部分精度问题。struct Point { char color; double x, y, z; }; double crossArea(const Point a, const Point b, const Point c) { double ux b.x - a.x, uy b.y - a.y, uz b.z - a.z; double vx c.x - a.x, vy c.y - a.y, vz c.z - a.z; double cx uy * vz - uz * vy; double cy uz * vx - ux * vz; double cz ux * vy - uy * vx; double square cx * cx cy * cy cz * cz; return sqrt(square) / 2.0; }颜色判断同样有坑。满足条件的情况只有两种三个颜色完全相同例如RRR或者三个颜色两两不同例如RGB。有同学会写“三色不同”时直接判断c1 ! c2 c2 ! c3结果漏了c1 c3这种情况比如RGR看起来是“不一样”但实际出现了两个R不合法。必须写成三条件同时满足 (c1 c2 c2 c3) || (c1 ! c2 c2 ! c3 c1 ! c3)这种逻辑判断本身不难难的是在写三重循环的时候保持清醒。我建议把颜色判断抽成单独的函数能少很多意外错误。2.4 有趣的排序先想清楚“哪些元素不用动”“有趣的排序”是这套题里很能考验理解能力的一道。题意大概是给定一个从1到N的排列你可以把任意一个元素移动到序列最前面或最后面问最少需要移动多少次才能让整个序列升序有序。如果你直接想“模拟移动”会掉进一个很大的坑因为移动顺序会影响结果很难模拟出最优解。换一个角度想如果最终序列要变成1,2,3,...,N那么序列中已经有一部分元素是“相对位置正确”的这部分元素可以完全不动只需要把其余元素逐个移到开头或结尾。因此问题变成原序列中最长有多少个值连续递增的元素它们的相对位置本来就是对的。这里的关键是“值连续递增且相对顺序不变”。比如序列3 1 2 4里面1 2 4在数组中的先后顺序正好是递增的且数值连续吗不是1、2、4中间少了3。真正连续的是1、2长度为2所以答案是4 - 2 2需要移动两个元素。实现思路记录每个值在数组中的下标比如pos[x]表示值x出现的位置。然后扫描值1到N判断pos[i]和pos[i1]的关系如果pos[i1] pos[i]说明i和i1在原序列中相对顺序正确可以连成一段连续递增序列否则就断开重新计数。#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; vectorint a(n 1), pos(n 1); for (int i 1; i n; i) { cin a[i]; pos[a[i]] i; } int len 1, best 1; for (int i 1; i n; i) { if (pos[i 1] pos[i]) { len; best max(best, len); } else { len 1; } } cout n - best \n; return 0; }第一次做这题时我尝试用最长上升子序列的长度作为“不用动的元素”结果WA了。因为LIS虽然保证相对顺序但不保证数值连续。而我们的最终序列是1到N的连续整数所以只有值连续递增的子段才能真正做到让未移动元素刚好占据最终序列中连续的一段。这个区别非常重要。3. 核心难点逐个击破3.1 不等式数列动态规划与组合意义这套题里最硬核的当属“不等式数列”。题意大致是长度为n的排列中有若干对相邻数字之间可能是小于号或大于号现在问恰好有k个小于号的排列一共有多少个结果对题目给定模数取模。直接枚举所有排列肯定不行n稍大就是灾难。当时我花了一段时间才理解动态规划的转移这里我把完整推导讲清楚因为它是整道题的核心。设dp[i][j]表示由数字1到i组成的所有排列中恰好有j个小于号的排列数量。初始状态dp[1][0] 1因为只有一个数字没有相邻关系更谈不上小于号。现在考虑从长度i-1的排列扩展到长度i的排列把数字i插入到原来i-1个数字形成的排列中。注意数字i是当前最大的数所以插入的位置不同小于号数量变化不同。如果插入到原来某个“小于号”的位置例如a b插入最大数i后变成a i b原来的1个小于号还是1个小于号数量不变。如果插入到原来某个“大于号”的位置例如a b变成a i b原来是0个小于号现在变成了1个数量增加1。除了插入到相邻符号位置还可以插入到最左端和最右端。最左端插入时最大数在第一个位置它和右边第一个数之间一定是大于号所以小于号数量不变。最右端插入时左边最后一个数和最大数之间一定是小于号所以小于号数量增加1。于是转移公式就清楚了。要得到dp[i][j]有两种来源从dp[i-1][j]转移原来已经有j个小于号插入到不增加小于号的位置。不增加小于号的位置有原来的j个小于号位置外加最左端1个共j1个位置。从dp[i-1][j-1]转移原来有j-1个小于号插入到增加小于号的位置。原排列中大于号数量为(i-2)-(j-1)i-j-1个再加最右端1个共i-j个位置。所以 dp[i][j] dp[i-1][j] * (j 1) dp[i-1][j-1] * (i - j)这里很容易记混第二个系数我自己也错过很多次。可以这样理解i-j表示“当前还缺多少个小于号”当目标从小到大时这个位置数量会逐渐减少。验证方式很简单对所有j求和结果应该是i!因为dp[i]的所有状态加起来就是全排列数量。用这个性质对拍检查能立刻发现转移写没写错。#include bits/stdc.h using namespace std; const int MOD 2017; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, k; cin n k; vectorvectorint dp(n 1, vectorint(n 1, 0)); dp[1][0] 1; for (int i 2; i n; i) { for (int j 0; j i; j) { long long cur 0; if (j i - 1) { cur 1LL * dp[i - 1][j] * (j 1) % MOD; } if (j 0) { cur 1LL * dp[i - 1][j - 1] * (i - j) % MOD; } dp[i][j] cur % MOD; } } cout dp[n][k] \n; return 0; }边界条件也要注意j的范围是0到i-1因为i个数字之间最多只有i-1对相邻关系不可能出现i个小于号。循环里加if判断就是为了防止越界。取模的时机尽量提前中间结果用long long暂存不然溢出会让你调半天。3.2 进制转换与字符串处理的小模板这套题里还有几道和进制、字符串相关的题难度不大但很能考察基础。比如十进制转任意进制用“除基取余”法处理时要特别注意进制大于10的情况可能需要用A、B等字母表示10以上的数字。还有可能遇到反向问题把一个表示任意进制数的字符串转换为十进制需要从高位往低位累加。这类题我建议准备一个通用模板笔试时直接套用string toBase(int num, int base) { if (num 0) return 0; string res ; bool neg false; if (num 0) { neg true; num -num; } while (num 0) { int digit num % base; res (digit 10) ? char(0 digit) : char(A digit - 10); num / base; } if (neg) res -; reverse(res.begin(), res.end()); return res; }注意负数和0这两个边界。很多人在进制题上丢分不是因为不会转换而是忘记处理num等于0的情况。如果你直接进while循环0会变成空字符串输出就错了。字符串处理题则要小心大小写、空格、前导零这些细节几乎每套笔试题都会出现。3.3 边界条件与输入输出陷阱刷这套题给我最大的教训是边界条件不是靠聪明而是靠经验积累。很多题你思路完全正确但WA在n1、空集合、重复元素、浮点数精度这些地方。我把自己在这套题里踩过的边界问题整理成了一份自查清单现在每次提交前都会过一遍数组长度为0或者1时代码是否还能正常运行如果结果可能为负数输出格式是否允许负号取模运算中减操作会不会产生负数需不需要加MOD再取模浮点数比较时是否用了eps是否因为误差导致答案偏了一点点输入是否可能包含多组数据题目有没有说读到EOF结束输出格式是否要求保留固定小数位题目说保留两位就不能输出3.1这种格式。这些看起来是细节但在真实笔试里一个边界问题可能让你丢掉整道题的分数。建议你在刷题时不只是让代码通过样例还要主动构造极端数据测试。4. 实操过程我的练习流程与代码模板4.1 准备环境与刷题节奏我刷这套题的时候用的是本地编辑环境加终端编译工具倒没什么特别。关键是我给自己定了节奏拿到一道题先读题三遍确认输入输出格式然后给自己10分钟想暴力解法如果暴力可行就先用暴力把答案跑出来再去思考优化。这样做的目的是保证至少有一版正确代码可以用来对拍。每道题我给自己30分钟超过30分钟还卡住就看题解思路但看完之后不是直接抄代码而是关掉题解自己重新写一遍。这个过程比刷十道简单题还有用。整套题我分了三天完成每天两到三道。第一天做简单题找状态第二天集中攻克中等题第三天专门做动态规划和几何题并且把所有AC代码重新整理了一遍。环境上我强烈建议开启编译警告比如g加上-Wall -Wextra。很多潜在问题比如变量未初始化、有符号数和无符号数比较编译器都会给警告。笔试时虽然可能不允许改编译选项但平时把这些习惯养好考场上犯错的概率就小很多。4.2 典型题的完整代码复盘这里我把“寻找三角形”的完整写法再放一次因为我当时在这道题上花费了不少时间而且最终AC的代码里有很多值得学习的地方。完整的结构包括读入点信息、三重循环枚举、颜色合法性判断、面积计算、更新最大值、控制输出精度。#include bits/stdc.h using namespace std; struct Point { char color; double x, y, z; }; bool validColor(char a, char b, char c) { if (a b b c) return true; if (a ! b b ! c a ! c) return true; return false; } double calcArea(const Point p1, const Point p2, const Point p3) { double ux p2.x - p1.x; double uy p2.y - p1.y; double uz p2.z - p1.z; double vx p3.x - p1.x; double vy p3.y - p1.y; double vz p3.z - p1.z; double cx uy * vz - uz * vy; double cy uz * vx - ux * vz; double cz ux * vy - uy * vx; return sqrt(cx * cx cy * cy cz * cz) / 2.0; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; vectorPoint pts(n); for (int i 0; i n; i) { cin pts[i].color pts[i].x pts[i].y pts[i].z; } double ans 0.0; for (int i 0; i n; i) { for (int j i 1; j n; j) { for (int k j 1; k n; k) { if (!validColor(pts[i].color, pts[j].color, pts[k].color)) continue; ans max(ans, calcArea(pts[i], pts[j], pts[k])); } } } cout fixed setprecision(5) ans \n; return 0; }三重循环枚举时用i、j、k递增的方式能保证同一个三角形只被计算一次。如果一开始用三层从0到n-1的全枚举不仅效率低而且可能出现同一个三角形因为顶点顺序不同被重复计算的情况。虽然最终面积一样但浪费了时间。4.3 对拍与测试脚本的实用技巧笔试刷题时最怕“样例过了但提交WA”这时候对拍是最高效的定位手段。所谓对拍就是写一个暴力解作为标准答案写一个优化解作为待测代码再写一个随机数据生成器批量跑随机数据比较两份输出。我常用Python写数据生成器然后在一个bash循环里反复对拍。以“度度熊回家”为例数据生成器可以随机生成数组长度和数值然后同时跑暴力程序和优化程序一旦输出不一致就停下来查看输入数据。for i in $(seq 1 500); do python3 gen.py input.txt ./brute input.txt output_brute.txt ./fast input.txt output_fast.txt if ! diff output_brute.txt output_fast.txt; then echo Case $i failed break fi done对拍时有个细节浮点数输出不要直接diff因为精度会导致两个程序输出细微不同。遇到浮点题我一般会在diff之前先用Python脚本解析两边输出比较它们差值的绝对值是否小于1e-6。这套流程看起来很原始但真的能节省大量反复提交试错的时间。5. 刷题中的常见问题与排查实录5.1 常见错误速查表刷完这套题后我把最容易出现的错误整理成了一张速查表现在每次笔试前都会扫一眼。常见的坑和排查方法如下错误现象可能原因排查方法样例通过但提交WA边界条件没处理构造n1、n2等最小数据答案总是差一点浮点数精度问题用double输出固定小数位数组越界循环边界写错检查所有i1、i-1访问输出格式错误没有处理多组输入看题是否要求循环读取结果偏大或偏小去重/排序逻辑理解错回到题意确认“第K个”概念动态规划结果不对状态转移系数写错用sum(dp)验证是否为全排列数这张表看起来简单但每一条都是我实际踩过的坑。尤其是“样例通过但提交WA”这个问题最让人心态爆炸。我的经验是不要急着猜隐藏数据先检查自己有没有处理n1等边界如果没有问题再去检查算法本身的逻辑。5.2 调试心得与或非逻辑的坑在“寻找三角形”这题上颜色判断的条件我写错过一次。当时我写的是if (a ! b b ! c)漏掉了a c的情况。样例里给出了一个RGB三角形我通过了但换到RGR这种组合时就错了因为a ! b成立b ! c也成立但a ! c不成立这种颜色组合有三个点但有两个R并不满足“要么全同要么全不同”。这个教训非常典型逻辑表达式不是“看起来差不多”就行必须逐项验证。后来我写这类条件判断都会先在草稿纸上列出所有可能组合再用真值表核对。看到一个if条件至少要能说出它排除了哪些情况保留哪些情况。不要嫌烦这种习惯能在笔试里救你很多次。另一个调试技巧是使用cerr输出中间变量。很多OJ对标准输出的格式很严格但如果用cerr输出调试信息不会影响最终输出。我在调试“不等式数列”的DP时就会在每次循环后cerr当前dp数组的一整行检查是不是符合全排列数总和的规律。发现问题后先看转移方程再看循环范围比盲目调参高效得多。5.3 为什么建议你也做一次完整复盘刷题不是把题目AC掉就结束了真正的提升在于复盘。我会在每道题AC之后隔几天重新用空白编辑器写一遍不参考之前的代码。如果能顺利写出来说明这个知识点真的掌握了如果卡住说明之前AC可能只是背下来了而不是理解了。这套题难度适中非常适合用来做这种“间隔复写”训练。我还习惯在题解里记录三件事第一这道题最简单的暴力写法是什么第二最优解为什么比暴力快复杂度差在哪里第三如果数据范围变大十倍这道题还能不能用当前解法。第三点对培养算法敏感度特别有好处它能让你从“会写题”变成“会选题”。6. 练习这套题后的几点体会如果让我用一句话总结这套题我会说它是一套“不偏不怪、处处有坑”的好题。它的每一道题单拿出来都不算难但组合在一起恰好把笔试中最容易失分的细节都覆盖了。我把这套题完整刷完再去做其他模拟笔试时明显感觉到自己读题更仔细了提交前检查边界条件变成了肌肉记忆。我个人的一个实操建议是刷这套题时别急着看题解。哪怕一道题卡了半小时也要保持独立思考。你可以借助调试工具、对拍程序、甚至手动用纸笔画状态转移但一定要先形成自己的思路。因为校招笔试里你面对的是全新题目没有人会给你提示平时怎么依赖题解考场上就会怎么吃亏。最后再分享一个我自己用得很顺手的方法每道题AC之后把代码按照“题意理解、解法推导、边界清单、代码实现”四段整理成笔记。这套题一共给了我几篇很完整的笔记。后来春招复习时我没有再去翻新的题库而是把这些笔记重新过了一遍效果反而比盲目刷新题好很多。如果你也正准备春招不妨试试这个方法把一套有价值的真题吃透比追求刷题数量更值得。