秋招季又到了刷题的季节。如果你正在准备后端、算法岗的校招笔试网易2019秋招笔试编程题合集一这套题应该是绕不开的。不管你是不是把网易作为目标公司这套题都值得认真做一遍因为它的出题风格非常典型题面不长、场景包装很生活化、算法模型不偏门但特别爱考细节边界。可以说把这套题吃透相当于提前适应了大多数互联网大厂笔试的节奏。这份合集里收录的题目难度梯度拉得比较开前两道属于签到题级别后两道直接上强度。很多同学考完回来吐槽小易怎么又在搬砖牛牛怎么又在找工作但其实把这些包装剥掉以后核心考的都是非常经典的算法原型贪心排序、动态规划、区间维护、构造计数。这篇文章我打算按照先看全局、再拆考点、后讲代码、最后复盘踩坑的顺序把这套题彻底拆开揉碎。1. 网易2019秋招笔试的考场生态题量、时间与策略分配先说一个很多初次参加笔试的同学容易忽略的问题笔试不是让你把四道题全AC的而是让你在有限时间内拿尽可能多的分。网易这套题的典型配置是4道编程题考试时间在90到120分钟之间。按我自己的经验前两道简单题应该在20到25分钟内搞定第三道中等题留30分钟最后一道难题如果30分钟内没有明确思路就应该果断转向部分分策略而不是死磕。网易的命题有个很鲜明的特征场景叙事极其统一主角永远是小易或者牛牛。2019秋招这批题里你会看到小易开店、牛牛找活、小易数数字、牛牛排字典这些故事都是包装核心脱胎于《剑指Offer》和LeetCode中的经典题型但会故意加一层现实约束来增加区分度。比如牛牛找工作这道题本质上是一个性价比贪心问题但它不是直接给你一组数让你排序而是给你工作难度和报酬两个维度再给你若干个能力值去匹配——这就多了一层如何高效地对多组查询给出答案的考量。还有一个考场细节很多人都栽过网易笔试的输入格式喜欢用多行、多组数据混排。第一行是数组长度第二行是数组元素第三行又是另一个参数稍不留神就会把输入读错。我当年考的时候就因为在牛牛找工作那道题里把伙伴数量和工作数量的输入顺序搞反了白折腾了十几分钟。所以拿到题目第一件事不是看算法是先把输入输出格式圈出来用样例数据手动推一遍确认自己读对了。另外这套题对时间复杂度的容忍度很微妙。前两题用O(n^2)暴力完全能过但第三题开始O(n^2)基本就是超时预定必须优化到O(nlogn)或者O(n)。而第四题如果涉及组合数、字典序构造这类问题不光要会算法还要对数据范围敏感——该用long long的地方用int直接就是一个测试点都过不去。总体策略建议是正着做先易后难但绝不恋战。每道题先花两三分钟把题意和样例吃透再估计一下算法复杂度如果卡了15分钟没有实质进展立刻跳到下一题。最后留10分钟统一回头处理没做完的题——哪怕只能过样例、只能暴力解小数据也比白卷强得多。2. 从真题看网易命题组最钟爱的四类算法模型把这一套题放在一起对比你会发现网易出题虽然场景天天换但算法模型来来回回就是那么几个。这里我把出现频率最高的四类考点展开讲一下每一类都配上真题里的典型场景帮你建立看见包装就能识别原型的能力。2.1 性价比贪心与排序2019秋招里最典型的贪心题就是牛牛找工作。题目大意是牛牛找工作了每份工作有一个难度值Di和一份报酬Pi牛牛有一个能力值Ai只有当能力值大于等于工作难度时才能胜任这份工作。牛牛有若干个朋友每个朋友也有各自的能力值问每个朋友能拿到的最高报酬是多少。这个场景剥掉之后就是一个非常经典的多维匹配最值问题。核心思路是按难度从小到大排序所有工作然后顺序扫描维护到当前难度为止的最高报酬。为什么这么做是对的因为能力值越大可选的工作集合只会扩张不会收缩所以当前能选的最高报酬是单调不减的。每个朋友的能力值只需要在排序后的工作数组里二分找到最后一个难度不超过能力值的位置然后直接取该位置的前缀最大报酬。很多第一次做这道题的人会犯一个错误对每个朋友单独遍历一遍所有工作来找最大值复杂度是O(n*m)n和m稍微一大就超时。其实只要想到先排序再预处理前缀最大值复杂度立刻降到O((nm)log n)。这就是典型的空间换时间思路也是网易这类快消型笔试题最爱的考法——不考你知不知道贪心考你能不能把多组查询的重复计算消掉。类似的原型还有会议安排最多场次区间选点最少个数都是先排序再贪心的套路。如果你在考场上识别出我需要对多组查询反复做同一件事第一反应就应该是能不能预处理能不能排序后二分2.2 动态规划的小易式包装网易的DP题特别喜欢加一层游戏化设定。比如小易喜欢的单词这类题表面是在问一个字符串满不满足某种喜欢的条件实际上是一道自动机DP的状态转移题。再比如独立的小易小易要在一条街上走每次可以走1步或2步但某些位置有障碍不能踩问到达终点的方案数——这就是一个非常标准的线性DPdp[i] dp[i-1] dp[i-2]障碍位置直接置0。DP的难点从来不是状态转移方程的推导而是你能不能一眼看出这是个DP问题以及状态的维度怎么定。网易很喜欢用地图行走跳跃这样的场景来包装DP原因就是它们天然适合用位置或步数作为状态。遇到这类题我的习惯是先画一条数轴或者状态转移表把每一步的依赖关系写清楚再看有没有空间优化的余地。比如经典的小易喜欢的单词那道题实际上是一个字符串匹配变体状态是当前匹配到原串第几位和当前匹配到模式串第几位转移就是字符相等时的推进和失配时的回退本质上是KMP自动机上的DP。如果你没见过这类题第一次做很可能完全摸不着头脑但一旦见过下次再遇到小易XX的字符串题你会条件反射地往自动机DP上想。2.3 区间问题与数据结构的轻量运用网易有时候会把前缀和、差分数组、线段树这类数据结构揉进题目里。2019秋招里有一道小易的糖果题本质是区间加法和区间最大值查询。如果你只会暴力遍历数据一大就卡死但如果意识到多次区间操作可以用差分数组优化或者多次区间查询可以用线段树/树状数组维护题目难度就瞬间降级了。说实话网易的题目对线段树的考察不会特别深基本停留在你能写出单点更新区间查询的水平更多时候用前缀和、滑动窗口就能解决。比如有一道题是问连续子数组的和等于K的最长长度这就是典型的滑动窗口或前缀和哈希表优化。命题组在这里真正想考的是你对区间和这个概念的理解——能不能想到用前缀和把O(n^2)的区间枚举降成O(n)的两次前缀和之差。这一点想通了很多看似复杂的区间题都能迎刃而解。刷高频题的时候不要只看题解要刻意练习从题目描述中提取区间关系的能力。看到连续子数组区间覆盖这些词条件反射就应该想到前缀和、差分、双指针、滑动窗口这四个工具。2.4 思维构造与数论计数每年网易都会有一两道思维题2019秋招里的小易的字典就是代表。这种题最大的特点是你一眼看过去完全不知道用什么算法甚至会怀疑是不是题目出错了。它考的是你在面对非常规问题时能不能通过数学推导和构造找到规律。小易的字典的核心是给定n个a和m个z要求按字典序排列所有由这些字符组成的字符串然后输出第k个。看着字符串实际上是一个组合计数问题。字典序第k大的字符串每一位是a还是z取决于以当前位为a时后面还剩多少种排列而这个数量正好是组合数C(剩余位置数, 剩余z数)。所以本质上你要做的是从高位向低位逐位决定每决定一位就减去对应的组合数数量直到k减到零。这种题在考场上最考验心理素质。我的建议是先拿小数据量在草稿纸上手算出规律再想办法用组合数或递推形式把规律形式化。平时刷题时多积累这类构造计数的题目思路尤其是那种输出第k大/第k小的题目大概率是逐位构造计数剪枝的套路。3. 一道满分代码该怎么写从暴力递归到剪枝AC很多同学有个误区笔试答题只要思路对代码差不多就能过。但网易的评测系统非常严格边界条件、溢出、内存超限都会让你白丢分。这一节我就用牛牛找工作这道题完整走一遍从能跑通到满分AC的全过程顺便展示一下我在考场上的代码习惯。3.1 暴力版能做对但只能对一半#include iostream #include vector #include algorithm using namespace std; int main() { int n, m; cin n m; vectorpairint, int jobs(n); for (int i 0; i n; i) { cin jobs[i].first jobs[i].second; } vectorint abilities(m); for (int i 0; i m; i) { cin abilities[i]; } for (int i 0; i m; i) { int best 0; for (int j 0; j n; j) { if (abilities[i] jobs[j].first) { best max(best, jobs[j].second); } } cout best endl; } return 0; }这段代码的思路是直给的每个朋友都遍历所有工作找报酬最高的那个。时间复杂度O(n*m)当n和m都在10^4以上时基本就是超时。但它有一个好处——在数据量小的测试点上绝对正确。考场上如果实在想不出优化方案先交一版暴力能拿一部分分这比空着强得多。3.2 优化版排序前缀最大值二分优化的核心动机很简单每个朋友的查询都在重复做在所有工作中找难度不超过能力值的最大报酬而工作列表是固定的那为什么不提前处理好呢#include iostream #include vector #include algorithm using namespace std; int main() { int n, m; cin n m; vectorpairint, int jobs(n); for (int i 0; i n; i) { cin jobs[i].first jobs[i].second; } vectorint abilities(m); for (int i 0; i m; i) { cin abilities[i]; } // 按工作难度从小到大排序 sort(jobs.begin(), jobs.end()); // 预处理前缀最大报酬 vectorint maxPay(n); maxPay[0] jobs[0].second; for (int i 1; i n; i) { maxPay[i] max(maxPay[i-1], jobs[i].second); } for (int i 0; i m; i) { // 二分查找最后一个难度不超过能力值的工作 int l 0, r n - 1, pos -1; while (l r) { int mid (l r) / 2; if (jobs[mid].first abilities[i]) { pos mid; l mid 1; } else { r mid - 1; } } if (pos -1) { cout 0 endl; } else { cout maxPay[pos] endl; } } return 0; }这里有几个关键细节值得强调为什么排序后还要维护前缀最大值因为难度低不等于报酬高。有可能难度为3的工作报酬是100难度为5的工作报酬只有80。如果只按难度排序然后直接取难度不超过能力值的最后一个工作的报酬就错了。前缀最大值的意义在于它记录了到当前难度为止所有可选工作中的最高报酬。这样无论能力值落在哪个区间前缀最大值都能给出正确结果。为什么二分查找的返回值是最后一个难度不超过能力值的位置因为我们要找的是可选集合的右边界超过这个边界的工作难度太高做不了而这个边界之前的所有工作都可能被选择。用二分的标准模板注意等于号应该归入左边即让pos尽量靠右这样能保证取到所有可选工作里的最大值。优化后的时间复杂度是O(nlogn mlog n)空间复杂度O(n)。在笔试环境下这个复杂度可以轻松应对10^5级别的数据量。3.3 再进一步如果报酬也要按难度压缩怎么办有些变体题会把工作难度设计成不连续的大范围值比如难度范围到10^9但工作数量只有10^5。这时候排序二分的思路仍然成立但要注意离散化把所有出现过的难度值排序去重然后对每个能力值用lower_bound找到第一个大于等于它的难度位置再减一得到可选位置。这个技巧在牛牛找工作的升级版里很常见提前掌握能省不少考场时间。离散化版本我通常这样写#include iostream #include vector #include algorithm using namespace std; int main() { int n, m; cin n m; vectorpairint, int jobs(n); vectorint diff; for (int i 0; i n; i) { cin jobs[i].first jobs[i].second; diff.push_back(jobs[i].first); } vectorint abilities(m); for (int i 0; i m; i) { cin abilities[i]; } sort(jobs.begin(), jobs.end()); sort(diff.begin(), diff.end()); diff.erase(unique(diff.begin(), diff.end()), diff.end()); vectorint maxPay(diff.size()); int idx 0; for (int i 0; i n; i) { while (diff[idx] jobs[i].first) idx; maxPay[idx] max(maxPay[idx], jobs[i].second); } for (int i 1; i (int)diff.size(); i) { maxPay[i] max(maxPay[i], maxPay[i-1]); } for (int i 0; i m; i) { int pos upper_bound(diff.begin(), diff.end(), abilities[i]) - diff.begin() - 1; if (pos 0) { cout 0 endl; } else { cout maxPay[pos] endl; } } return 0; }这里用upper_bound找到第一个大于能力值的难度位置减一就是最后一个不超过能力值的难度。代码看起来复杂了一点但思路和上面的排序二分完全一致只是多加了一层离散化来压缩难度范围。4. 那些年在网易笔试里白给的边界条件刷题刷多了你会发现很多时候算法想对了代码也没写错但提交就是不过。网易的评测系统尤其爱在边界条件上做文章。这一节我把这套题里最值得注意的边界情况集中说一下全是我自己踩过的坑和帮别人调试时见过的真实案例。4.1 输入读取的顺序和格式网易的题输入格式经常是多行混排可能是先给工作数量n和伙伴数量m也可能是先给伙伴数量再给工作数量每一行的数据个数也不一样。我的建议是在写代码之前先用输入样例手动走一遍确认每个变量对应的是哪一行。尤其注意vector的resize和push_back不要混用——如果你先resize了再push_back数据会多出来一倍。另外有些题的输入数据量非常大用cin不关同步会导致超时。建议在main函数开头加上这两行ios::sync_with_stdio(false); cin.tie(0);这不算作弊只是让C的标准输入输出更快一些笔试环境完全允许。4.2 能力值小于所有工作难度的情况在牛牛找工作里如果某个朋友的能力值是1但所有工作的难度都大于1那这个人没有任何可选工作报酬应该是0。很多人在二分查找时没有处理pos-1的情况直接访问maxPay[pos]数组越界导致运行错误。注意上面的代码对这种情况做了特判。同样还有能力值大于所有工作难度的情况此时pos n-1maxPay[n-1]就是全局最大报酬不用特殊处理但你要确认自己的二分逻辑在全部可选时不会死循环。4.3 多个工作难度相同但报酬不同排序之后相同难度的工作会堆在一起。如果直接对每个位置计算前缀最大值同一个难度档位的多个工作报酬会被依次更新最后保留的是该难度下的最高报酬。这恰好是我们想要的。但如果某个难度档位的工作数量很多而你没有按难度聚合前缀最大值依然正确只是可能会有冗余计算——不影响正确性但会影响性能。我在实际写代码时会额外注意排序时pair默认先按first再按second排序所以相同难度的工作会按报酬从小到大排。前缀最大值递推式max(maxPay[i-1], jobs[i].second)天然会保留该难度的最大报酬所以不用额外处理。4.4 数据范围与溢出这是最隐蔽也最致命的坑。网易2019秋招的题目数据范围通常给到10^9级别比如报酬可以是1000000000朋友数量可以是100000。如果你用int存前缀最大值两个最大值相加就可能溢出导致答案变成负数。这类问题几乎每年都有人栽因为样例数据往往很小本地测试全过一提交就WA。我的习惯是只要题目数据范围里出现了10^9所有涉及累加、乘法、组合数的变量一律用long long。尤其是那些考组合数的题C(n, m)在n30时就已经超过int范围了如果你用int存组合数表算到一半就爆了。组合数问题的标准姿势是用long long加二维数组预计算比如long long C[1005][1005]; for (int i 0; i 1000; i) { C[i][0] C[i][i] 1; for (int j 1; j i; j) { C[i][j] C[i-1][j-1] C[i-1][j]; } }如果题目数据范围更大比如n到5000甚至更高二维数组就存不下了这时候需要用乘法逆元预处理阶乘来算组合数。网易2019秋招里那道字典构造题数据范围控制在100以内二维组合数表完全够用但如果你不知道这个预处理技巧在考场上现场手推组合数公式很容易越算越乱。4.5 字典序构造题的k超过总排列数场景小易的字典这类题有一个极易漏掉的点如果k比所有可能排列的总数还要大答案应该是-1。很多同学在逐位构造时只关心当前位的组合数够不够减却忘了先判断整体可不可能。你在代码开头要先算出总排列数C(nm, n)如果k大于这个数直接输出-1。这个判断不仅是一行代码的事它决定了你后续的构造过程会不会出现减到最后k还是正数的死循环。还有一点构造时每选择一位a就要从当前组合数中减去以a开头的排列数这里的排列数是指当前剩余位置中剩余z个数的组合数。写着写着很容易把n和m搞混我的做法是在草稿纸上先写清楚剩余n个a、m个z的状态然后每一步更新n或m再算组合数。这种题考场上心态越稳越不容易出错。5. 考场实战的时间分配与部分分求生指南笔试和平时刷题最大的区别是考场上有时间压力而且你不知道评测数据到底有多强。我见过太多平时LeetCode能轻松做出Hard的人笔试却翻车原因不是不会做而是不会考试。这一节分享一下我自己总结的考场实战策略。5.1 拿到题先做三件事第一读题看样例确认输入输出格式。程序员最怕的不是算法不会而是数据读错。如果样例能跑通但提交全错大概率是格式问题。第二估算数据范围确定目标复杂度。如果n在10^3以下O(n^2)随便写n在10^5级别基本必须O(nlogn)或O(n)n在10^6级别连O(nlogn)都要小心常数可能需要O(n)的线性算法。这一步想清楚后面写代码就不会盲目优化或者过度设计。第三确定每道题的优先级。我会用1分钟快速扫完四道题的题干把一眼知道怎么做的题标记为高优先级有点思路但需要细想的题标记为中优先级完全没有头绪的题标记为低优先级。然后按照高→中→低的顺序做。5.2 遇到卡壳题暴力分也是分网易的评测系统不会因为你的代码时间复杂度高就判零分很多测试点允许O(n^2)甚至更高的复杂度。所以当你一时想不出最优解时先写一个能过小数据、能过样例的暴力版本交上去至少能拿到一部分分数。然后再在剩余时间里慢慢优化。这里有一个经验之谈暴力版拿了分之后不要急着删掉重写。先把暴力版放在一边在纸上推导一下重复计算到底发生在哪里找到瓶颈后再针对性地优化。比如牛牛找工作的暴力版慢在每次查询都重新遍历工作那么优化方向就是预先把答案算好查询时直接取结果。这个思路可以在10分钟内把一道暴力题改造成满分题。5.3 一道题最多花多少时间我的原则是简单题不超过20分钟中等题不超过40分钟难题如果30分钟没有明确思路果断放弃。这个时间预算不是绝对的但至少能保证你不会在一道题上耗尽所有时间然后发现还有三道题没做。有个真实的教训我认识的一个同学在笔试时跟小易的字典这道题死磕了一个小时最后虽然做出来了但前面两道简单题只写了暴力版本有些测试点没过总成绩反而不如那些放弃难题、稳拿简单题的人。笔试不是竞赛拿满该拿的分比解出最难的题更重要。5.4 提交前最后的三查代码写完、样例通过别急着提交。花两分钟做最后的自查查输入输出格式变量顺序对不对换行符有没有是否有多余的输出查边界条件n1时会不会越界所有元素都相同时会不会死循环最大数据量会不会超时查数据类型有没有用int存long long的隐患数组开得够不够大这三查看起来简单但每一次都能拦住好几个本不该丢的测试点。尤其是数组开得够不够大这一点如果你开了一个长度为n的数组却访问了n1的位置评测系统会直接判运行时错误而本地运行因为内存布局的原因可能根本不会崩。血的教训。写在最后这套题到底值不值得反复刷经常有同学问我2019年的题现在刷还有意义吗我的回答是算法题的底层模型并不会因为年份变化而过时。贪心、DP、二分、前缀和、组合计数这些永远是大厂笔试的核心考点。网易2019秋招这套题的价值不在于题目本身有多难而在于它的出题风格和绝大多数互联网大厂高度一致——用生活化的场景包装经典算法用数据范围考察复杂度意识用边界条件筛选代码细节。我自己每年秋招前都会把这套题重新做一遍每次做都会发现新的问题有时候是代码风格不够稳健有时候是对某个算法的理解又深了一层。刷题的意义不只是为了应付笔试更是在帮自己建立一套稳定的解题思维框架。如果你正在准备秋招我建议你把这套题放进你的必刷清单。不要只做一遍就丢第一次按考场模式限时做第二次专门分析每道题的算法原型第三次只看题面在脑海里快速过思路。等你能够做到看见小易搬砖就知道考什么的时候这套题的价值就真正被你榨干了。