七八月一到准备秋招的群里又开始热闹起来。每年都会有人问真题到底该刷哪一套我通常给的建议是把网易2017秋招编程题集合放在很靠前的位置。这套题年份虽然有点久但出题风格和难度曲线非常稳定几乎可以当成互联网公司笔试的标尺——字符串处理、模拟、数学推导、动态规划、搜索剪枝全都覆盖到了而且没有哪道题是故意刁难人属于“你认真准备就能做出来”的题。这篇博文就把这套题集合里有代表性的几道题拆开揉碎讲一遍包括每道题的解题思路、代码实现、以及我在实际刷题中踩过的坑。不管是正在秋招冲刺的同学还是想系统练手大厂真题的人都能从里面找到可直接复用的东西。1. 为什么我建议把2017这套题翻烂网易笔试的出题指纹先聊一个多数人不会注意的点网易笔试的出题风格很有“指纹”特征。它很少出那种拍脑袋的偏题怪题而是喜欢把常见考点包装进一个带角色、带场景的小故事里。比如“小易要买苹果”“小易从N号石板跳到M号石板”“考拉有一堆字符串”。场景是干扰项剥掉场景之后核心考点非常规整。我统计过这套题的常见构成基本落在下面几个方向题目类型代表题核心考点难度字符串去重下厨房set/hash去重、EOF读取简单贪心/枚举买苹果枚举8袋数量、边界校验简单数学推导计算糖果方程组求解、回代验证简单动态规划跳石板状态转移、约数枚举中字符串排序两种排序方法字典序与长度排序简单浮点输出字符串碎片字符串切分、输出格式简单搜索剪枝幸运的袋子回溯、排序剪枝中高这个分布很有代表性简单题占了多数但简单题不等于送分它考察的是你处理边界和输入输出的基本功中档题只有一两道专门用来拉开差距真正需要大量数学推导的难题反而很少出现在网易的笔试里。所以我的结论是这套题非常适合用来“校准”自己的笔试水平。如果你能在两小时内稳定做完前面六道并且一道题都不因为边界条件翻车那你的笔试基础已经比大部分候选人扎实了。下面的内容我就按这个思路逐题拆。2. 送分题也是分水岭下厨房与买苹果的“秒杀”细节2.1 下厨房多行不定长输入怎么读才稳原题的大意是小易要准备很多道菜每行输入一道菜需要的食材输入以EOF结束最后统计他一共需要多少种不同的食材。输入样例里每行是两个字符串菜名和食材名但行数不固定。很多人第一次见这种“不知道有多少行”的输入就慌了用getline一行一行读然后手动split结果不是首行多读了个换行就是最后一组数据没读进去。其实这类题有个非常稳的写法不要按行读直接按空白字符切。C的写法是这样#include iostream #include set #include string int main() { std::setstd::string table; std::string dish, material; // cin 会自动跳过所有换行和空格 while (std::cin dish material) { table.insert(material); } std::cout table.size() std::endl; return 0; }Python的写法更短import sys # 读取全部内容按空白符切割 data sys.stdin.read().split() # 每行两个单词菜名在下标0、2、4...食材名在下标1、3、5... materials set(data[1::2]) print(len(materials))这里有两个细节值得多说一句。第一为什么用cin dish material而不是getline因为cin 天然忽略所有空白字符包括换行和空格。输入是几行、每行几个词都不影响你按顺序拿到单词。只要题目里说“以EOF结束”while (cin ...)就是最不容易错的读取方式。除非题目要求你按“行”处理比如每行是一整条记录否则优先用。第二为什么用set而不用map因为题目只要“不同食材的个数”set天然去重size()直接给答案。有些同学习惯性用map计数代码长一截还容易在自增时写错。不是不能用但没必要。看到“不同”“去重”这类词第一反应就应该是set。这道题我当年第一次做的时候还犯过一个低级错误以为每行输入只有一个字符串写了个while (cin s)结果菜名和食材名全被当成食材放进set里了。所以读题时一定要先确认“每行包含几个字段”再决定读取逻辑。这个习惯比背模板重要得多。2.2 买苹果贪心枚举的边界校验买苹果这道题也很经典小易要买n个苹果苹果只按6个一袋和8个一袋卖问最少买几袋能够正好凑出n个如果凑不出来输出-1。最简单的思路是贪心8个一袋的越多总袋数越少。于是先尽量用8袋剩下的用6袋补补不上再往回减。这种思路能不能过能但必须把“往回减”的过程写对。更稳的写法是直接枚举8袋的数量#include iostream int main() { int n; std::cin n; int ans -1; // 8袋越多总袋数越少所以从能取的最大袋数往下枚举 for (int x n / 8; x 0; --x) { int rest n - x * 8; if (rest % 6 0) { ans x rest / 6; break; } } std::cout ans std::endl; return 0; }这里有个看似奇怪但实际有用的前置判断n如果是奇数直接输出-1。因为6和8都是偶数无论如何组合都只能凑出偶数所以奇数必然无解。这个判断虽然不影响最终结果但能让你在调试时更快排查问题也能避免在某些变种题里走弯路。再解释一下为什么枚举方向是“从n/8往下减”。如果从0开始往上加8袋的数量第一个找到可行解时8袋数量可能是少的总袋数却不一定最小。试想n488袋0个时用8个6袋共8袋8袋1个时剩余40不能被6整除8袋2个时剩余32也不能被6整除8袋3个时剩余24要4个6袋总袋数7。如果从0往上找会先找到8袋然后输出8但正确答案是7。反过来从最大8袋数往下找第一个可行解一定对应总袋数最小因为8袋替代两个6袋能减少一个袋数8袋越多总袋数越少。这个逻辑在代码里没直接写但枚举顺序本身就是贪心。这类“枚举所有可能性然后找最优”的题真正考验人的不是能不能枚举出来而是枚举起点和终点是否覆盖所有可能能否保证第一个找到的解就是最优边界条件比如n6、n6、n8是否单独考虑。把这三点想清楚简单题就不会在阴沟里翻船。3. 计算糖果看着像数学题其实是方程校验题如果下厨房和买苹果是手速题那计算糖果就是一道“披着数学外衣”的边界题。原题给出四个整数分别表示A-B、B-C、AB、BC要求还原出A、B、C如果解不存在或者不唯一输出No。第一次见这题的人往往会想得很复杂这不是三元一次方程组吗直接解不就行了问题在于出题人给的四个表达式不是恰好三个而是多了一个多出来的那个条件就是用来做“校验”的。如果你只取其中三个方程硬解然后不管第四个条件至少一半的测试用例会挂。3.1 从四个表达式还原三个未知数先把推导过程写清楚。设x1 A - Bx2 B - Cx3 A Bx4 B C由x1和x3可以算出A和BA (x1 x3) / 2B (x3 - x1) / 2由x2和x4可以算出B和CB (x2 x4) / 2C (x4 - x2) / 2注意这里得到了两个B的候选值它们必须相等。如果不等说明四个输入不是来自同一组A,B,C直接输出No。这是这道题最容易踩的坑很多解法只算一组A,B,C然后不再回代验证结果遇到畸形的输入照样输出一组看似合理的数。正确的做法是先算出一组解再把x1、x2、x3、x4全部代回去一个条件都不能少。3.2 回代验证与整除判断除了回代验证还要处理整数整除问题。题目里的A、B、C是整数那么x1x3必须是偶数x3-x1也必须是偶数x4-x2同理。否则直接无解。完整代码可以这样写#include iostream int main() { int x1, x2, x3, x4; std::cin x1 x2 x3 x4; // 三个除法都要求能整除 if ((x1 x3) % 2 ! 0 || (x3 - x1) % 2 ! 0 || (x4 - x2) % 2 ! 0) { std::cout No std::endl; return 0; } int A (x1 x3) / 2; int B (x3 - x1) / 2; int C (x4 - x2) / 2; // 回代验证四个条件以及B的两个候选值是否一致 if ((x2 x4) / 2 ! B || A - B ! x1 || B - C ! x2 || A B ! x3 || B C ! x4 || A 0 || B 0 || C 0) { std::cout No std::endl; return 0; } std::cout A B C std::endl; return 0; }这段代码里我特意保留了A 0 || B 0 || C 0这个判断。有些输入比如x1-100, x2-100, x3100, x4100数学上确实有整数解但题目如果规定A,B,C是正整数那就要排除。具体看原题对取值范围的描述但加上非负判断永远不会错。从这道题里可以提炼出一个通用的笔试经验凡是题目给了“多余条件”的求解题最后的验证环节一定不能省。计算糖果如此很多解方程、解矩阵的题也是如此。出题人给四个方程而不是三个本身就是故意留一个校验口。4. 跳石板一道把BFS卡死的动态规划启蒙题跳石板是这套题里最有含金量的一道也是我认为最值得反复刷的一道。原题大意小易站在编号为N的石板上要跳到编号为M的石板每次可以选择当前编号的一个真约数作为步长跳到当前编号 步长的位置。问最少跳几次能到M如果到不了输出-1。4.1 题意拆解步长是当前位置的真约数先说一个审题关键步长是“当前位置编号”的约数不是固定值也不是目标位置的约数。比如你站在4号石板4的约数有1、2、4但每次只能跳过1和自身所以只能选2跳到6号。站在6号石板6的真约数是2、3所以可以跳到8或9。“跳过1和自身”这个限制让题目有了意思站在一个质数位置时没有任何合法步长这条路就断了。这也是为什么要用动态规划而不是从后往前贪心。4.2 为什么BFS在这里不是最优解我第一次做这道题第一反应是BFS。从N出发每层枚举当前位置的约数把能跳到的新位置入队。听起来很自然但很快就会发现两个问题第一状态数很多。如果M可以到几万甚至十万BFS的队列会变得很大而且同一个位置可能被从多个路径到达需要额外的visited数组去重代码量一下就上来了。第二每次出队都要重新枚举约数假设某个位置的约数有几十个BFS总复杂度会相当难看。这不是说BFS不能写而是说BFS更适合“每一步选择有限且路径权重相同”的最短路径问题。跳石板的问题本质是“从N到M的最短步数”而且步长能跳到的位置是递增的这天然是DP的形态。4.3 DP状态转移与约数枚举优化先定义状态dp[i]表示从N跳到i的最少步数初始时dp[N]0其余为正无穷。状态转移遍历i从N到M如果dp[i]已经不是正无穷说明i可以被到达那么枚举i的所有真约数d更新dp[id] min(dp[id], dp[i] 1)同时保证id M。这里最需要优化的地方是枚举约数。如果对每个i都从2扫到i/2复杂度是O(M^2)M稍微大一点就会超时。常见优化是只扫到sqrt(i)#include iostream #include vector #include algorithm const int INF 0x3f3f3f3f; int main() { int N, M; std::cin N M; std::vectorint dp(M 1, INF); dp[N] 0; for (int i N; i M; i) { if (dp[i] INF) continue; // 枚举 i 的真约数不包含1和i本身 for (int d 2; d * d i; d) { if (i % d ! 0) continue; int jump1 d; int jump2 i / d; if (i jump1 M) { dp[i jump1] std::min(dp[i jump1], dp[i] 1); } // jump2 和 jump1 可能相同这里直接重复更新不影响正确性 if (jump2 ! i i jump2 M) { dp[i jump2] std::min(dp[i jump2], dp[i] 1); } } } std::cout (dp[M] INF ? -1 : dp[M]) std::endl; return 0; }这段代码里有个小细节枚举约数时从d2开始天然绕开了约数1。jump2是i/d因为d2所以jump2一定小于i不会出现原地跳自身的情况。我们用一个例子验证一下。N4M24dp[4]04的约数2跳到6dp[6]16的约数2、3跳到8和9dp[8]2dp[9]28的约数2、4跳到10和12dp[10]3dp[12]312的约数2、3、4、6跳到14、15、16、18dp[14]4dp[15]4dp[16]4dp[18]416的约数2、4、8其中8可以让16跳到24dp[24]5最终输出5和题目的答案是吻合的。这道题给我的最大启发是当你发现BFS需要维护一个很大的队列、而且每个节点的后继节点数量不固定时不妨想想能不能用DP。DP不是比BFS高级而是更适合处理“节点编号天然有序增长”的问题。这套题里跳石板是唯一一道中档题它卡住的从来不是不会写递归的人而是只会套BFS模板的人。5. 字符串题的隐藏考点两种排序方法与字符串碎片字符串题在这个集合里占比不小而且每道题都藏着一个容易忽略的“判定边界”。如果你以为字符串题就是调API那就太天真了。5.1 两种排序方法字典序判断的边界这道题给了n个字符串要求判断它们是否按字典序排列、是否按长度排列然后输出对应结果。先想清楚两个概念字典序不是简单的ASCII码排序。它是逐字符比较如果前面的字符都相同短的字符串排在长的前面。string的运算符默认就是按字典序比较所以这个判定可以直接用。长度排序就更好理解只比较size()。但有一个隐藏边界两个相邻字符串相等时算不算有序从题意看如果要求的是“非降序”那么相等算有序。我自己的经验是现在存疑先按“不算破坏顺序”处理因为绝大多数这类题不会把相等情况设成陷阱万一错了再调整。代码不难#include iostream #include vector #include string int main() { int n; std::cin n; std::vectorstd::string s(n); bool lex true; bool len true; for (int i 0; i n; i) { std::cin s[i]; if (i 0) { if (s[i] s[i - 1]) lex false; if (s[i].length() s[i - 1].length()) len false; } } if (lex len) std::cout both std::endl; else if (lex) std::cout lexicographically std::endl; else if (len) std::cout lengths std::endl; else std::cout none std::endl; return 0; }这里真正容易出问题的不是代码而是输出字符串。题目要求的输出是lexicographically不是lexicographic也不是Lexicographically。我见过有人算法完全正确结果输出时少写了一个ally整道题没分。这种细节在笔试里最可惜。另外不要用sort之后比较是否相等来判定有序。sort会改变原数组而且如果原数组长度很大排序的额外复杂度完全没有必要。线性扫描相邻元素就够了。5.2 字符串碎片平均长度的浮点输出字符串碎片的原题是给一个字符串它由若干“连续相同字符”的碎片组成比如aaabbaaac可以分成aaa、bb、aaa、c四段。求所有碎片的平均长度保留两位小数。解题核心就是数一数有多少个碎片。遍历一遍每当当前字符和上一个字符不同碎片数加一。平均长度就是总长度除以碎片数。#include iostream #include string #include cstdio int main() { std::string s; std::cin s; int cnt 1; for (size_t i 1; i s.size(); i) { if (s[i] ! s[i - 1]) cnt; } double avg (double)s.size() / cnt; printf(%.2f\n, avg); return 0; }这个代码短到几乎不需要解释但有两个坑值得提。第一cnt初始化为1需要前提字符串非空。笔试里一般都会保证字符串长度大于等于1但如果你在本地测试时手滑输入了空字符串cnt为1平均长度是0结果看起来有理实际是错的。稳健的写法是加一个if (s.empty())判断不过考虑到题目约束不写也没关系。第二输出格式。保留两位小数用printf(%.2f)最省心。如果用C的cout需要fixed setprecision(2)。很多人写cout avg结果输出一长串小数格式分直接没了。5.3 字符串题现场的检查清单字符串题看着简单但每次考试都有人翻车。我把常见的坑整理成一个清单输入是否可能包含空格如果包含空格cin s只读到第一个空格前需要用getline。空字符串是否会出现如果出现碎片数、字符串比较这些逻辑都要单独处理。相等字符串是否算有序取决于题目是否强调“非降序”。输出字符串是否拼写完全一致一个字母都不能差。浮点数保留几位用printf和setprecision之前确认格式。这个清单不是空话是我在真实笔试里一条条踩出来的。字符串题的代码量通常很少丢分基本都丢在这些不可见的边界条件上。6. 刷穿这套题后我留下的考场生存清单把这套题一行一行写下来之后我最大的感受是网易这类公司的笔试真正筛选的从来不是“会不会算法”而是“在有限时间内能不能写出不犯低级错误的代码”。所以我想最后分享几条自己总结的考场生存经验也是这套题教会我的东西。第一读题时先圈出三个关键词数据范围、输出格式、边界条件。下厨房的EOF、计算糖果的回代验证、两种排序方法的输出单词全是对着这三个关键词设置的陷阱。先把这三个东西圈出来再动笔写代码至少能避开一半的坑。第二输入输出模板要背到肌肉记忆。while (cin ...)处理不定长输入getline处理带空格的整行输入printf(%.2f)处理浮点格式ios::sync_with_stdio(false)和cin.tie(nullptr)在需要大量读入时加上。这些小模板平时不值一提考场上却能帮你省下大量调试时间。第三遇到“看似能贪心”的题先想枚举遇到“看似要搜索”的题先想DP。跳石板就是最典型的例子。贪心容易漏解搜索容易超时而枚举和DP往往在复杂度可控的前提下更加稳妥。这套题集合正是在帮你训练这种“算法直觉”。第四也是最重要的一条动手写代码之前先在草稿纸上用一个小例子把推导过程完整走一遍。计算糖果的方程组推导、跳石板的DP更新过程我都建议你亲手画一遍。很多时候你以为自己懂了实际上是在代码里才能发现推导漏洞。这套题的题量不大非常适合拿来当作“做题前先推导”的练习材料。我把这套题刷完之后又把跳石板和计算糖果单独重写了三遍每一次都能发现新的细节。这种“真题反复刷”的收益远高于漫无目的地刷几十道新题。如果你也想在秋招前把自己的笔试状态调整到最好我建议你先从这套题开始把每一道题都按“推导 - 编码 - 回代验证”的流程过一遍。刷完你会有一种很踏实的感觉原来大厂笔试考的东西并没有想象中那么玄乎。