春招笔试刷编程题这件事我太有感触了。网易这套2017春招笔试真题编程题集合虽然过去好几年了但直到今天都是我认为最适合拿来练手的校招题库之一。原因很简单这套题的难度梯度设置得特别真实从送分题到压轴题都有涵盖了动态规划、贪心、字符串处理、数学推导这些笔试高频考点而且题目本身的质量非常高没有偏题怪题非常适合用来评估自己到底有没有准备好校招笔试。不管你是正在备战春招的应届生还是打算跳槽的职场人这套题都值得认真过一遍。我当年把这套题刷了两遍第一遍刷的时候大概有一半的题需要看别人的思路才能写出来第二遍的时候已经能独立在限定时间内完成大部分题目了。这个过程给我的提升是实打实的——不仅是对算法知识的查漏补缺更是对笔试节奏、代码风格、边界条件处理这些软实力的系统训练。这篇文章我就把这套题拆开揉碎了讲说说每道题背后的考点、解题思路、代码实现以及我在实际操作中踩过的坑和总结出来的经验。1. 先搞清楚这套题到底考什么1.1 为什么是2017年的题现在还有参考价值吗先说结论有价值而且价值不低。很多人觉得笔试题目每年都在变刷几年前的题没意义。但实际上面试官考察的核心能力是稳定的——算法思维、代码实现能力、边界情况处理、复杂度分析这些基本功不会因为年份变化而改变。网易的笔试题目风格向来是重思维、轻套路它不会考你背过的模板题而是喜欢把经典的算法模型藏在新的场景里这恰恰是现在大多数公司笔试的出题趋势。我当时在牛客网上做这套题的时候感受到最明显的一点是这套题的难度分布非常接近真实校招笔试的体验。前两三道属于热身级别的送分题中间几道需要一定的思考最后一道或两道是真正拉差距的题目。这种梯度设计特别适合用来做笔试模拟你可以严格按照考试时间来做一遍看看自己卡在哪一档就知道当前水平大概在什么位置了。1.2 这套题覆盖的知识点全景图整套题涉及的核心知识点我梳理了一下大致有这些动态规划包括0-1背包的变种、区间DP、线性DP是绝对的重点贪心算法考察如何找到正确的贪心策略并证明其正确性搜索包括DFS、回溯、状态空间枚举数学推导部分题目需要先做数学化简再设计算法字符串处理涉及字符计数、ASCII码映射、模拟操作数据结构基础数组、哈希表、堆的基本使用很多人刷题容易陷入一个误区——只看题解、不总结考点。但考点的归纳整理恰恰是刷题最重要的产出。我刷完这套题之后专门花了半天时间把每道题对应的考点、解题模型、可以延伸变形的方向写成了笔记这个笔记在我后续准备其他公司笔试的时候帮了大忙。2. 从送分到压轴难度梯度的典型拆解2.1 热身级题目奇怪的信与调整队形这套题的前两道属于手速题——思路很简单代码也不长主要考察你能不能快速读懂题目并写出正确的代码不要在这种题上浪费太多时间。奇怪的信这道题的核心是处理一个整数各位数字的重复累加折叠直到变成一个一位数。这个题看起来简单但其实有一个数学上的小彩蛋对9取模。一个数对9取模的结果和它各位数字之和的对9取模结果是一致的。所以你其实不需要真的循环折叠直接用数学性质就能O(1)解决。当然直接模拟循环也不算错只是代码会更啰嗦一些。我当时的做法是直接模拟因为这道题放在第一题的位置就是让你热身的写模拟代码的时间成本也很低没必要炫技。调整队形这道题考察的是贪心策略。问题是有一排学生男生女生分别编号要求通过交换相邻两个人使得所有男生和所有女生各自站在一起求最少交换次数。这里的关键结论是最终状态只有两种可能——男生全部在左边或女生全部在左边。你只需要分别计算变成这两种状态需要的交换次数取最小值就可以了。这个题容易出错的地方在于交换相邻两个人的操作次数怎么计算——实际上就是看每个需要移动的人在当前状态中的相对位置和目标位置之间的偏移量累加。这两道题我给的建议是考试时遇到这种级别的题要在10分钟内搞定包括读题、写代码、跑样例、提交。如果你连这种题都要想很久说明刷题量还不够需要先把基础算法再过一遍。2.2 核心题双核CPU处理任务这道题可以说是整套题的分水岭——能独立做出来的人说明动态规划的基本功是过关的。题目的场景是有两个CPU每个CPU同一时刻只能处理一个任务给定若干个任务的处理时间求所有任务完成的最短时间。这个题第一眼看过去像个调度问题容易往贪心方向想——按时间从大到小排序然后往当前空闲的CPU上分配。但这个贪心策略并不是最优的。正确的解法是把问题转化为0-1背包所有任务总时间的一半作为背包容量每个任务的时间当作物品的重量和价值目标是让装入背包的任务总时间尽可能接近总时间的一半。这样分给一个CPU的任务尽可能接近一半另一个CPU就是剩下的一半总完成时间就是两者中的较大值而较大值的最小化就是让较小值尽量大。我当时第一次做这道题时就掉进了贪心的坑里想了很久都没想明白为什么WA。后来看题解才意识到这是典型的正难则反——直接求最短完成时间不好求转化成求容量为总时间一半的背包最多能装多少就简单了。这个转化思路在笔试中非常常见很多看似是调度、分区的问题本质都是背包问题。2.3 压轴题魔力手环与工作安排魔力手环这道题是整套题里我印象最深的一道。题目大意是有一个包含n个数字的手环每次操作后第i个位置变成原来第i个位置和第i1个位置循环的数字之和并对某个数取模。操作需要进行k次n和k的范围很大k可能达到10^9级别。这道题的核心考点是矩阵快速幂。每次操作本质上是一个线性变换——把当前状态向量乘以一个n×n的矩阵得到新的状态向量。连续操作k次就相当于把初始向量乘以这个矩阵的k次方。而矩阵快速幂可以在O(n³log k)的时间复杂度内完成计算n最大是50log k大约是30总的运算量是可以接受的。但这里有一个很大的坑n为偶数时矩阵的k次方可能会退化成某种规律形式可以进一步优化但如果你没发现这个规律直接用标准矩阵快速幂也能过。我当时就是直接写的标准矩阵快速幂因为n50、log k30的复杂度在考试时间限制内完全没问题。后面看别人题解时发现还有更巧妙的数学优化但对于应试来说能过就是王道优化是锦上添花的事情。工作安排这道题是DFS和状态枚举的典型应用。题目是给n项工作每项工作有开始时间、结束时间和报酬要求选择若干项工作使得报酬最大化且选定工作的时间不能有重叠。n的范围不大可以用DFS枚举所有可能的组合也可以用DP按照结束时间排序后做线性DP。这道题的价值在于它考察了决策枚举的思想和后面很多公司的笔试题思路一致。3. 硬核真题四道典型题目的完整解题过程3.1 双核CPU从问题转化到代码实现先说结论这道题 0-1背包 正难则反。问题转化之后代码其实非常短。题目核心描述是两个CPU每个同一时刻只能处理一个任务有n个任务每个任务有一个处理时间time[i]求所有任务都处理完成所需的最短时间。def solution(times): total sum(times) capacity total // 2 # dp[j] 表示容量为j时能装下的最大任务总时间 dp [0] * (capacity 1) for t in times: # 0-1背包一维数组倒序遍历 for j in range(capacity, t - 1, -1): dp[j] max(dp[j], dp[j - t] t) # 一个CPU处理dp[capacity]的时间另一个处理total - dp[capacity]的时间 return total - dp[capacity]这段代码的核心逻辑就是把任务分给两个CPU让它们的处理时间尽可能均衡。dp[capacity]表示在不超过总时间一半的前提下一个CPU最多能承担的处理时间。另一个CPU处理的时间就是total - dp[capacity]因为任务没法再细分了。返回的是两者中的较大值其实因为dp[capacity] ≤ total/2所以total - dp[capacity] ≥ dp[capacity]直接返回那个较大的就行。这里面最容易出错的一个细节是如果总时间是一个奇数比如7那么capacity 3dp[3]最多是3返回7 - 3 4这确实是正确答案——两个CPU的时间分别为3和4总完成时间就是4。3.2 奇怪的信数学化简的妙处这道题虽然简单但我特别想拿出来说因为它展示了一个很好的思维习惯在写模拟代码之前先想一想有没有数学性质可以用。题目要求是把一个整数的各位数字反复相加直到结果是一个一位数。比如987 → 98724 → 246所以结果是6。直接的模拟写法是def solve(x): while x 10: s 0 while x 0: s x % 10 x // 10 x s return x这个代码没问题但如果你知道数字根digital root的性质可以直接写def solve(x): if x 0: return 0 return 9 if x % 9 0 else x % 9这个性质的核心是任何整数和它各位数字之和在模9意义下同余。因为10^k ≡ 1 (mod 9)所以一个数字的模9值等于它每一位数字之和的模9值。反复折叠也不会改变这个同余关系。最终结果如果是9的倍数数字根就是9否则就是它对9取余的结果。我不是说你一定要用数学做法——模拟写法的代码也完全可以过。但我想强调的是养成动手之前先想想有没有更优解法的习惯在考场上能帮你省下大量时间尤其是当这种题出现在比较靠前的位置时更快的解法意味着你能把省下的时间留给后面的难题。3.3 魔力手环矩阵快速幂的完整实现这道题是整套题里最有算法竞赛感觉的一道。题目要求做k次变换每次变换都是线性操作new[i] (old[i] old[(i1) % n]) % mod。我们先构造转移矩阵M。M的第i行第j列表示第j个位置对第i个位置新值的贡献系数。因为new[i] old[i] old[i1]所以M[i][i] 1M[i][(i1) % n] 1其余为0。注意这个矩阵是n×n的乘以一个n×1的列向量得到的就是变换后的状态。初始状态向量是原始数组执行k次变换就相当于计算 M^k × initial_vector。用矩阵快速幂可以在O(n³ log k)时间内完成。def mat_mul(A, B, mod): n len(A) C [[0] * n for _ in range(n)] for i in range(n): for k in range(n): if A[i][k] 0: continue for j in range(n): C[i][j] (C[i][j] A[i][k] * B[k][j]) % mod return C def mat_pow(M, power, mod): n len(M) # 单位矩阵 res [[1 if i j else 0 for j in range(n)] for i in range(n)] while power 0: if power 1: res mat_mul(res, M, mod) M mat_mul(M, M, mod) power 1 return res def solve(n, k, arr, mod): M [[0] * n for _ in range(n)] for i in range(n): M[i][i] 1 M[i][(i 1) % n] 1 M_pow mat_pow(M, k, mod) result [0] * n for i in range(n): s 0 for j in range(n): s (s M_pow[i][j] * arr[j]) % mod result[i] s return result这里有几个实际操作上容易踩的坑我一个个说第一矩阵乘法的循环顺序。标准的O(n³)矩阵乘法有三个循环为了提高缓存命中率通常把k循环放在中间层这样C[i][j]的累加过程会连续访问B的某一列。但这里因为我们要正确实现数学上的矩阵乘法循环顺序只要保证逻辑正确即可性能优化不是首要考虑n最大50怎么写都不会超时。第二取模操作。如果中间结果不加modn50、数据范围大的时候矩阵元素会变得非常大Python的int虽然不会溢出但大数运算的速度会拖慢程序。所以每步都模一下保证数字不会太大。第三单位矩阵初始化。很多人在写快速幂的时候容易忘记把初始结果设为乘法单位元——在矩阵乘法中就是单位矩阵。写错了的话结果会完全不对而且这种错误很隐蔽不容易通过小样例发现。3.4 工作安排DFS解决选择类问题工作安排这道题给了n项工作每项工作有开始时间s[i]、结束时间e[i]、价值v[i]要求选择若干项不冲突的工作使总价值最大n的范围在20以内。n20这个范围其实很微妙——意味着你可以用2^n的暴力枚举也可以用DFS加剪枝或者用DP排序后做。我当时的做法是DFS因为n很小状态空间完全可以穷举。DFS的思路是按结束时间排序后对于每一项工作都有选和不选两种决策。选的话需要保证它的开始时间大于等于当前已选最后一项工作的结束时间不选的话直接跳到下一项。由于搜索树是2^n的规模n20时大约100万种状态跑起来没有任何压力。def max_value(jobs): # jobs: [(start, end, value), ...] jobs.sort(keylambda x: x[1]) # 按结束时间排序 n len(jobs) memo [-1] * n # 返回从第i个工作开始含能获得的最大价值前提是当前空闲时间允许选择第i个 # 更标准的做法是使用DP这里展示DFS思路的变形如果是按时间线DP则另说 def dfs(i, current_time): if i n: return 0 # 不选第i个 best dfs(i 1, current_time) # 选第i个前提不冲突 if jobs[i][0] current_time: best max(best, v dfs(i 1, jobs[i][1])) return best return dfs(0, 0)不过坦白说DFS虽然能过但并不是这道题的最优解。等n变大之后DFS的指数级复杂度就扛不住了。更好的做法是动态规划按结束时间排序dp[i]表示前i项工作中能获得的最大价值转移的时候用二分查找找到结束时间不大于第i项工作开始时间的最后一项工作下标然后做状态转移。这样复杂度是O(n log n)是最优的解法。这个题给我最大的启发是笔试中遇到n不大的题目不要一上来就写暴力。可以先估算一下暴力枚举的复杂度——n20的话2^n大约是100万次操作确实可过但n30的话2^30就不行了。先分析数据范围再决定用哪种解法这是一个很关键的应试习惯。4. 刷题方法论怎么把一套题的价值榨干4.1 做题顺序和限时训练很多人刷题有一个不好的习惯——不限时慢慢琢磨。这在校招笔试中是要吃亏的。真实的笔试环境是整个过程大概90到120分钟题目数量在7到10道之间每一道题都有限定的提交时间窗口。如果你平时不训练限时做题的节奏到了考场上很容易出现前面花太多时间、后面题目来不及看的情况。我自己比较推荐的做法是把这套题当成一次完整的模拟考试设定90分钟的倒计时到点就停笔。不管做了几道题都要停下来复盘。复盘时总结三个问题哪些题在10分钟内做出来了哪些题想了很久才做出来哪些题完全没有思路这三个问题的答案就是你当前算法能力的真实画像。比如我当时做完这套题之后发现自己想了很久才做出来的题目集中在动态规划和带技巧的数学题上于是接下来的两周里我集中刷了大概50道不同难度的DP题把常见的DP模型背包、LIS、LCS、区间DP、状压DP都过了一遍。这种以题带练的方式比漫无目的地每天刷几道随机题要高效得多。4.2 一题多解从能过到会分析刷题的时候我还特别提倡一个习惯每道题AC之后再想一想有没有别的解法。不是为了追求花哨而是为了培养分析问题的能力。拿双核CPU来说标准解法是0-1背包。但你有没有想过如果任务数量特别大、时间特别长背包解法还可行吗这时候可能需要换思路比如用bitset优化或者用贪心近似但笔试一般不要求近似解。这种如果数据范围变化了解法要怎样调整的思考正是面试中面试官喜欢追问的问题。另外工作安排这道题我也做了两个版本一个是DFS的版本一个是二分DP的版本。两个版本代码风格完全不同一个体现的是暴力思维一个体现的是最优性思维。能在笔试规定时间内写出DFS版本说明基础功扎实但能在时间富余的情况下优化到DP版本说明你对这个问题的理解更深入这是一道题发挥出更高价值的地方。4.3 错题本比刷题量更重要的复习资源我强烈建议你建一个错题本把每次做错的题、卡壳的题、看了题解才明白的题统一整理到一个文档里。这个错题本不需要写完整的题目描述只需要记录题目核心考点、我当时卡在哪一步、正确的解题思路、和这道题类似的题有哪几道。举例来说我在整理双核CPU这道错题时写下的记录是考点是0-1背包转化我的错误是试图用贪心正确思路是正难则反类似的题有将数组分成两个和最接近的子集送外卖的最短时间等。这样在复习的时候我只需要看错题本就能在很短的时间里把高频考点和常见陷阱过一遍。这套方法我在后面准备其他公司的笔试时一直用效果非常显著。5. 笔试现场最容易踩的坑血泪经验总结5.1 输入输出的格式陷阱校招笔试最常见的一个翻车点就是输入输出格式。网易这套题用的是牛客网的评测环境输入是标准输入输出是标准输出。但每道题的输入格式都不一样有的第一行是n第二行是n个数有的每一行是一组测试数据可能有多个case。我见过太多人因为输出格式多了一个空格、少了一个换行、或者多余打印了一行调试信息导致WAWrong Answer。这里我分享几个实操中的细节第一无论如何不要在提交前省略自测环节。把题目样例输入复制下来跑一遍对照样例输出。如果样例都过不了说明题没读懂如果样例过了但是提交WA多半是边界条件或格式问题。第二如果题目要求输出之间用空格分隔最后一项后面不要多空格。有的评测系统对行末空格也敏感。最简单的方法是先把结果收集到一个list里然后用 .join(map(str, result))来输出就不会有行末多空格的问题。第三多个case的题目注意while循环读取输入的方式。在Python里你可以用while True: try: line input() except EOFError: break来处理不要因为不知道输入何时结束而卡住。5.2 边界条件空输入、单个元素、极端值边界条件是笔试中区分高手的隐形指标。很多人的代码在常规数据上没问题一碰到边界数据就崩。做题时我习惯在写完代码后自己脑内或者实际跑几个极端用例数组长度为1的情况所有元素相等的情况元素已经是升序或降序的情况数值极值0、最大值、负数如果允许空输入拿双核CPU那道题来说如果n1、总时间是一个很大的数比如1000000000背包容量是500000000dp数组的大小就是500000001在Python里这可能会比较占用内存。虽然这题数据范围要求保证内存够用但写代码时要有意识地避免无意义的巨大数组。另外如果所有任务时间加起来不是偶数一定要确认整除后的取整方向不会导致答案错误。5.3 时间和内存超限的判断限时训练的价值在这里就体现出来了。在笔试现场如果提交后提示TLETime Limit Exceeded你的第一反应不应该是死磕当前算法而是重新估算复杂度。这里的经验法则是如果n ≤ 20可以上2^n级别的算法如果n ≤ 5000O(n²)通常是可接受的如果n ≤ 10^5大概需要O(n log n)或O(n)的算法如果n ≤ 10^9那肯定不能用扫描整个范围的算法必须用数学推导或快速幂/对数级别算法魔力手环那道题就是典型的O(n³ log k)解法如果你真的傻乎乎地去模拟k次变换k达到10^9级别时必定TLE。这种题考的就是你能不能识别出线性变换 大量重复操作这个模式进而想到矩阵快速幂。5.4 多语言选择的经验网易这套题支持的语言包括C/C、Java、Python等。我的建议是用你最熟悉、写起来最快、最不容易出错的编程语言。不要因为听说C在竞赛中性能更好就临时切换语言笔试的紧张环境下熟悉感比理论上的性能优势重要得多。如果你主用Python需要注意的一点是Python在纯计算密集型问题上确实比C慢但网易这套题的数据范围基本上是让Python能过的只要你没有写出高复杂度的糟糕算法。我当时用Python2.7做的牛客网当时默认的Python版本现在一般用Python3注意一下input()和sys.stdin.readline()的性能差异就行——需要读大量数据时sys.stdin.readline()更快。6. 刷完这套题之后接下来怎么继续进阶刷完这套题你可以凭自己的表现来判断下一步计划。如果热身级题目做得还行但核心题卡住我建议下一步的强化方向是动态规划和贪心这是笔试中最常考的两大类算法。你可以找一些专题练习比如LeetCode上的动态规划标签或者牛客网上的名企真题板块把同一类型的题目集中刷一遍边刷边总结规律。如果核心题做得比较顺畅压轴题还有一些吃力那说明你的算法思维已经比较扎实了需要加强的是对高难度题目的敏感度。这时候可以扩展学习一下线段树、树状数组、并查集、状态压缩、图论里的最短路等进阶内容。这些知识不一定每次笔试都会考但一旦考到待遇和分数差距就会拉开。另外我想说刷题数量不是唯一指标。我见过刷了300道题但笔试成绩一般的人也见过只刷了80道题但几乎每次笔试都能通过的人。差别就在于是否真的把每道题的思路想透了、把同类型的题目归纳好了。一套好的真题集如果你能真正做到做完、改完、复盘完、整理完它的价值不亚于漫无目的地刷五套题。回到网易这套2017春招真题最后再分享一个我个人的小技巧刷完之后试着把每道题讲给别人听。找一个朋友或者自己对着镜子从头到尾讲一遍这道题的思路就像在面试时向面试官解释你的解法一样。如果你能把自己讲到别人听懂那你对这道题的理解就真的到位了。这个过程也会帮你提前演练面试中的讲题环节一举两得。根据我个人踩过不少坑之后的体会准备笔试最好的状态不是我刷了很多题而是我看到题能判断出它考察哪种模型、该用什么样的算法框架。网易这套真题就是一个特别好的训练场希望你能在里面把这道判断力练出来。 网易2017春招笔试真题解析：从动态规划到矩阵快速幂
春招笔试刷编程题这件事我太有感触了。网易这套2017春招笔试真题编程题集合虽然过去好几年了但直到今天都是我认为最适合拿来练手的校招题库之一。原因很简单这套题的难度梯度设置得特别真实从送分题到压轴题都有涵盖了动态规划、贪心、字符串处理、数学推导这些笔试高频考点而且题目本身的质量非常高没有偏题怪题非常适合用来评估自己到底有没有准备好校招笔试。不管你是正在备战春招的应届生还是打算跳槽的职场人这套题都值得认真过一遍。我当年把这套题刷了两遍第一遍刷的时候大概有一半的题需要看别人的思路才能写出来第二遍的时候已经能独立在限定时间内完成大部分题目了。这个过程给我的提升是实打实的——不仅是对算法知识的查漏补缺更是对笔试节奏、代码风格、边界条件处理这些软实力的系统训练。这篇文章我就把这套题拆开揉碎了讲说说每道题背后的考点、解题思路、代码实现以及我在实际操作中踩过的坑和总结出来的经验。1. 先搞清楚这套题到底考什么1.1 为什么是2017年的题现在还有参考价值吗先说结论有价值而且价值不低。很多人觉得笔试题目每年都在变刷几年前的题没意义。但实际上面试官考察的核心能力是稳定的——算法思维、代码实现能力、边界情况处理、复杂度分析这些基本功不会因为年份变化而改变。网易的笔试题目风格向来是重思维、轻套路它不会考你背过的模板题而是喜欢把经典的算法模型藏在新的场景里这恰恰是现在大多数公司笔试的出题趋势。我当时在牛客网上做这套题的时候感受到最明显的一点是这套题的难度分布非常接近真实校招笔试的体验。前两三道属于热身级别的送分题中间几道需要一定的思考最后一道或两道是真正拉差距的题目。这种梯度设计特别适合用来做笔试模拟你可以严格按照考试时间来做一遍看看自己卡在哪一档就知道当前水平大概在什么位置了。1.2 这套题覆盖的知识点全景图整套题涉及的核心知识点我梳理了一下大致有这些动态规划包括0-1背包的变种、区间DP、线性DP是绝对的重点贪心算法考察如何找到正确的贪心策略并证明其正确性搜索包括DFS、回溯、状态空间枚举数学推导部分题目需要先做数学化简再设计算法字符串处理涉及字符计数、ASCII码映射、模拟操作数据结构基础数组、哈希表、堆的基本使用很多人刷题容易陷入一个误区——只看题解、不总结考点。但考点的归纳整理恰恰是刷题最重要的产出。我刷完这套题之后专门花了半天时间把每道题对应的考点、解题模型、可以延伸变形的方向写成了笔记这个笔记在我后续准备其他公司笔试的时候帮了大忙。2. 从送分到压轴难度梯度的典型拆解2.1 热身级题目奇怪的信与调整队形这套题的前两道属于手速题——思路很简单代码也不长主要考察你能不能快速读懂题目并写出正确的代码不要在这种题上浪费太多时间。奇怪的信这道题的核心是处理一个整数各位数字的重复累加折叠直到变成一个一位数。这个题看起来简单但其实有一个数学上的小彩蛋对9取模。一个数对9取模的结果和它各位数字之和的对9取模结果是一致的。所以你其实不需要真的循环折叠直接用数学性质就能O(1)解决。当然直接模拟循环也不算错只是代码会更啰嗦一些。我当时的做法是直接模拟因为这道题放在第一题的位置就是让你热身的写模拟代码的时间成本也很低没必要炫技。调整队形这道题考察的是贪心策略。问题是有一排学生男生女生分别编号要求通过交换相邻两个人使得所有男生和所有女生各自站在一起求最少交换次数。这里的关键结论是最终状态只有两种可能——男生全部在左边或女生全部在左边。你只需要分别计算变成这两种状态需要的交换次数取最小值就可以了。这个题容易出错的地方在于交换相邻两个人的操作次数怎么计算——实际上就是看每个需要移动的人在当前状态中的相对位置和目标位置之间的偏移量累加。这两道题我给的建议是考试时遇到这种级别的题要在10分钟内搞定包括读题、写代码、跑样例、提交。如果你连这种题都要想很久说明刷题量还不够需要先把基础算法再过一遍。2.2 核心题双核CPU处理任务这道题可以说是整套题的分水岭——能独立做出来的人说明动态规划的基本功是过关的。题目的场景是有两个CPU每个CPU同一时刻只能处理一个任务给定若干个任务的处理时间求所有任务完成的最短时间。这个题第一眼看过去像个调度问题容易往贪心方向想——按时间从大到小排序然后往当前空闲的CPU上分配。但这个贪心策略并不是最优的。正确的解法是把问题转化为0-1背包所有任务总时间的一半作为背包容量每个任务的时间当作物品的重量和价值目标是让装入背包的任务总时间尽可能接近总时间的一半。这样分给一个CPU的任务尽可能接近一半另一个CPU就是剩下的一半总完成时间就是两者中的较大值而较大值的最小化就是让较小值尽量大。我当时第一次做这道题时就掉进了贪心的坑里想了很久都没想明白为什么WA。后来看题解才意识到这是典型的正难则反——直接求最短完成时间不好求转化成求容量为总时间一半的背包最多能装多少就简单了。这个转化思路在笔试中非常常见很多看似是调度、分区的问题本质都是背包问题。2.3 压轴题魔力手环与工作安排魔力手环这道题是整套题里我印象最深的一道。题目大意是有一个包含n个数字的手环每次操作后第i个位置变成原来第i个位置和第i1个位置循环的数字之和并对某个数取模。操作需要进行k次n和k的范围很大k可能达到10^9级别。这道题的核心考点是矩阵快速幂。每次操作本质上是一个线性变换——把当前状态向量乘以一个n×n的矩阵得到新的状态向量。连续操作k次就相当于把初始向量乘以这个矩阵的k次方。而矩阵快速幂可以在O(n³log k)的时间复杂度内完成计算n最大是50log k大约是30总的运算量是可以接受的。但这里有一个很大的坑n为偶数时矩阵的k次方可能会退化成某种规律形式可以进一步优化但如果你没发现这个规律直接用标准矩阵快速幂也能过。我当时就是直接写的标准矩阵快速幂因为n50、log k30的复杂度在考试时间限制内完全没问题。后面看别人题解时发现还有更巧妙的数学优化但对于应试来说能过就是王道优化是锦上添花的事情。工作安排这道题是DFS和状态枚举的典型应用。题目是给n项工作每项工作有开始时间、结束时间和报酬要求选择若干项工作使得报酬最大化且选定工作的时间不能有重叠。n的范围不大可以用DFS枚举所有可能的组合也可以用DP按照结束时间排序后做线性DP。这道题的价值在于它考察了决策枚举的思想和后面很多公司的笔试题思路一致。3. 硬核真题四道典型题目的完整解题过程3.1 双核CPU从问题转化到代码实现先说结论这道题 0-1背包 正难则反。问题转化之后代码其实非常短。题目核心描述是两个CPU每个同一时刻只能处理一个任务有n个任务每个任务有一个处理时间time[i]求所有任务都处理完成所需的最短时间。def solution(times): total sum(times) capacity total // 2 # dp[j] 表示容量为j时能装下的最大任务总时间 dp [0] * (capacity 1) for t in times: # 0-1背包一维数组倒序遍历 for j in range(capacity, t - 1, -1): dp[j] max(dp[j], dp[j - t] t) # 一个CPU处理dp[capacity]的时间另一个处理total - dp[capacity]的时间 return total - dp[capacity]这段代码的核心逻辑就是把任务分给两个CPU让它们的处理时间尽可能均衡。dp[capacity]表示在不超过总时间一半的前提下一个CPU最多能承担的处理时间。另一个CPU处理的时间就是total - dp[capacity]因为任务没法再细分了。返回的是两者中的较大值其实因为dp[capacity] ≤ total/2所以total - dp[capacity] ≥ dp[capacity]直接返回那个较大的就行。这里面最容易出错的一个细节是如果总时间是一个奇数比如7那么capacity 3dp[3]最多是3返回7 - 3 4这确实是正确答案——两个CPU的时间分别为3和4总完成时间就是4。3.2 奇怪的信数学化简的妙处这道题虽然简单但我特别想拿出来说因为它展示了一个很好的思维习惯在写模拟代码之前先想一想有没有数学性质可以用。题目要求是把一个整数的各位数字反复相加直到结果是一个一位数。比如987 → 98724 → 246所以结果是6。直接的模拟写法是def solve(x): while x 10: s 0 while x 0: s x % 10 x // 10 x s return x这个代码没问题但如果你知道数字根digital root的性质可以直接写def solve(x): if x 0: return 0 return 9 if x % 9 0 else x % 9这个性质的核心是任何整数和它各位数字之和在模9意义下同余。因为10^k ≡ 1 (mod 9)所以一个数字的模9值等于它每一位数字之和的模9值。反复折叠也不会改变这个同余关系。最终结果如果是9的倍数数字根就是9否则就是它对9取余的结果。我不是说你一定要用数学做法——模拟写法的代码也完全可以过。但我想强调的是养成动手之前先想想有没有更优解法的习惯在考场上能帮你省下大量时间尤其是当这种题出现在比较靠前的位置时更快的解法意味着你能把省下的时间留给后面的难题。3.3 魔力手环矩阵快速幂的完整实现这道题是整套题里最有算法竞赛感觉的一道。题目要求做k次变换每次变换都是线性操作new[i] (old[i] old[(i1) % n]) % mod。我们先构造转移矩阵M。M的第i行第j列表示第j个位置对第i个位置新值的贡献系数。因为new[i] old[i] old[i1]所以M[i][i] 1M[i][(i1) % n] 1其余为0。注意这个矩阵是n×n的乘以一个n×1的列向量得到的就是变换后的状态。初始状态向量是原始数组执行k次变换就相当于计算 M^k × initial_vector。用矩阵快速幂可以在O(n³ log k)时间内完成。def mat_mul(A, B, mod): n len(A) C [[0] * n for _ in range(n)] for i in range(n): for k in range(n): if A[i][k] 0: continue for j in range(n): C[i][j] (C[i][j] A[i][k] * B[k][j]) % mod return C def mat_pow(M, power, mod): n len(M) # 单位矩阵 res [[1 if i j else 0 for j in range(n)] for i in range(n)] while power 0: if power 1: res mat_mul(res, M, mod) M mat_mul(M, M, mod) power 1 return res def solve(n, k, arr, mod): M [[0] * n for _ in range(n)] for i in range(n): M[i][i] 1 M[i][(i 1) % n] 1 M_pow mat_pow(M, k, mod) result [0] * n for i in range(n): s 0 for j in range(n): s (s M_pow[i][j] * arr[j]) % mod result[i] s return result这里有几个实际操作上容易踩的坑我一个个说第一矩阵乘法的循环顺序。标准的O(n³)矩阵乘法有三个循环为了提高缓存命中率通常把k循环放在中间层这样C[i][j]的累加过程会连续访问B的某一列。但这里因为我们要正确实现数学上的矩阵乘法循环顺序只要保证逻辑正确即可性能优化不是首要考虑n最大50怎么写都不会超时。第二取模操作。如果中间结果不加modn50、数据范围大的时候矩阵元素会变得非常大Python的int虽然不会溢出但大数运算的速度会拖慢程序。所以每步都模一下保证数字不会太大。第三单位矩阵初始化。很多人在写快速幂的时候容易忘记把初始结果设为乘法单位元——在矩阵乘法中就是单位矩阵。写错了的话结果会完全不对而且这种错误很隐蔽不容易通过小样例发现。3.4 工作安排DFS解决选择类问题工作安排这道题给了n项工作每项工作有开始时间s[i]、结束时间e[i]、价值v[i]要求选择若干项不冲突的工作使总价值最大n的范围在20以内。n20这个范围其实很微妙——意味着你可以用2^n的暴力枚举也可以用DFS加剪枝或者用DP排序后做。我当时的做法是DFS因为n很小状态空间完全可以穷举。DFS的思路是按结束时间排序后对于每一项工作都有选和不选两种决策。选的话需要保证它的开始时间大于等于当前已选最后一项工作的结束时间不选的话直接跳到下一项。由于搜索树是2^n的规模n20时大约100万种状态跑起来没有任何压力。def max_value(jobs): # jobs: [(start, end, value), ...] jobs.sort(keylambda x: x[1]) # 按结束时间排序 n len(jobs) memo [-1] * n # 返回从第i个工作开始含能获得的最大价值前提是当前空闲时间允许选择第i个 # 更标准的做法是使用DP这里展示DFS思路的变形如果是按时间线DP则另说 def dfs(i, current_time): if i n: return 0 # 不选第i个 best dfs(i 1, current_time) # 选第i个前提不冲突 if jobs[i][0] current_time: best max(best, v dfs(i 1, jobs[i][1])) return best return dfs(0, 0)不过坦白说DFS虽然能过但并不是这道题的最优解。等n变大之后DFS的指数级复杂度就扛不住了。更好的做法是动态规划按结束时间排序dp[i]表示前i项工作中能获得的最大价值转移的时候用二分查找找到结束时间不大于第i项工作开始时间的最后一项工作下标然后做状态转移。这样复杂度是O(n log n)是最优的解法。这个题给我最大的启发是笔试中遇到n不大的题目不要一上来就写暴力。可以先估算一下暴力枚举的复杂度——n20的话2^n大约是100万次操作确实可过但n30的话2^30就不行了。先分析数据范围再决定用哪种解法这是一个很关键的应试习惯。4. 刷题方法论怎么把一套题的价值榨干4.1 做题顺序和限时训练很多人刷题有一个不好的习惯——不限时慢慢琢磨。这在校招笔试中是要吃亏的。真实的笔试环境是整个过程大概90到120分钟题目数量在7到10道之间每一道题都有限定的提交时间窗口。如果你平时不训练限时做题的节奏到了考场上很容易出现前面花太多时间、后面题目来不及看的情况。我自己比较推荐的做法是把这套题当成一次完整的模拟考试设定90分钟的倒计时到点就停笔。不管做了几道题都要停下来复盘。复盘时总结三个问题哪些题在10分钟内做出来了哪些题想了很久才做出来哪些题完全没有思路这三个问题的答案就是你当前算法能力的真实画像。比如我当时做完这套题之后发现自己想了很久才做出来的题目集中在动态规划和带技巧的数学题上于是接下来的两周里我集中刷了大概50道不同难度的DP题把常见的DP模型背包、LIS、LCS、区间DP、状压DP都过了一遍。这种以题带练的方式比漫无目的地每天刷几道随机题要高效得多。4.2 一题多解从能过到会分析刷题的时候我还特别提倡一个习惯每道题AC之后再想一想有没有别的解法。不是为了追求花哨而是为了培养分析问题的能力。拿双核CPU来说标准解法是0-1背包。但你有没有想过如果任务数量特别大、时间特别长背包解法还可行吗这时候可能需要换思路比如用bitset优化或者用贪心近似但笔试一般不要求近似解。这种如果数据范围变化了解法要怎样调整的思考正是面试中面试官喜欢追问的问题。另外工作安排这道题我也做了两个版本一个是DFS的版本一个是二分DP的版本。两个版本代码风格完全不同一个体现的是暴力思维一个体现的是最优性思维。能在笔试规定时间内写出DFS版本说明基础功扎实但能在时间富余的情况下优化到DP版本说明你对这个问题的理解更深入这是一道题发挥出更高价值的地方。4.3 错题本比刷题量更重要的复习资源我强烈建议你建一个错题本把每次做错的题、卡壳的题、看了题解才明白的题统一整理到一个文档里。这个错题本不需要写完整的题目描述只需要记录题目核心考点、我当时卡在哪一步、正确的解题思路、和这道题类似的题有哪几道。举例来说我在整理双核CPU这道错题时写下的记录是考点是0-1背包转化我的错误是试图用贪心正确思路是正难则反类似的题有将数组分成两个和最接近的子集送外卖的最短时间等。这样在复习的时候我只需要看错题本就能在很短的时间里把高频考点和常见陷阱过一遍。这套方法我在后面准备其他公司的笔试时一直用效果非常显著。5. 笔试现场最容易踩的坑血泪经验总结5.1 输入输出的格式陷阱校招笔试最常见的一个翻车点就是输入输出格式。网易这套题用的是牛客网的评测环境输入是标准输入输出是标准输出。但每道题的输入格式都不一样有的第一行是n第二行是n个数有的每一行是一组测试数据可能有多个case。我见过太多人因为输出格式多了一个空格、少了一个换行、或者多余打印了一行调试信息导致WAWrong Answer。这里我分享几个实操中的细节第一无论如何不要在提交前省略自测环节。把题目样例输入复制下来跑一遍对照样例输出。如果样例都过不了说明题没读懂如果样例过了但是提交WA多半是边界条件或格式问题。第二如果题目要求输出之间用空格分隔最后一项后面不要多空格。有的评测系统对行末空格也敏感。最简单的方法是先把结果收集到一个list里然后用 .join(map(str, result))来输出就不会有行末多空格的问题。第三多个case的题目注意while循环读取输入的方式。在Python里你可以用while True: try: line input() except EOFError: break来处理不要因为不知道输入何时结束而卡住。5.2 边界条件空输入、单个元素、极端值边界条件是笔试中区分高手的隐形指标。很多人的代码在常规数据上没问题一碰到边界数据就崩。做题时我习惯在写完代码后自己脑内或者实际跑几个极端用例数组长度为1的情况所有元素相等的情况元素已经是升序或降序的情况数值极值0、最大值、负数如果允许空输入拿双核CPU那道题来说如果n1、总时间是一个很大的数比如1000000000背包容量是500000000dp数组的大小就是500000001在Python里这可能会比较占用内存。虽然这题数据范围要求保证内存够用但写代码时要有意识地避免无意义的巨大数组。另外如果所有任务时间加起来不是偶数一定要确认整除后的取整方向不会导致答案错误。5.3 时间和内存超限的判断限时训练的价值在这里就体现出来了。在笔试现场如果提交后提示TLETime Limit Exceeded你的第一反应不应该是死磕当前算法而是重新估算复杂度。这里的经验法则是如果n ≤ 20可以上2^n级别的算法如果n ≤ 5000O(n²)通常是可接受的如果n ≤ 10^5大概需要O(n log n)或O(n)的算法如果n ≤ 10^9那肯定不能用扫描整个范围的算法必须用数学推导或快速幂/对数级别算法魔力手环那道题就是典型的O(n³ log k)解法如果你真的傻乎乎地去模拟k次变换k达到10^9级别时必定TLE。这种题考的就是你能不能识别出线性变换 大量重复操作这个模式进而想到矩阵快速幂。5.4 多语言选择的经验网易这套题支持的语言包括C/C、Java、Python等。我的建议是用你最熟悉、写起来最快、最不容易出错的编程语言。不要因为听说C在竞赛中性能更好就临时切换语言笔试的紧张环境下熟悉感比理论上的性能优势重要得多。如果你主用Python需要注意的一点是Python在纯计算密集型问题上确实比C慢但网易这套题的数据范围基本上是让Python能过的只要你没有写出高复杂度的糟糕算法。我当时用Python2.7做的牛客网当时默认的Python版本现在一般用Python3注意一下input()和sys.stdin.readline()的性能差异就行——需要读大量数据时sys.stdin.readline()更快。6. 刷完这套题之后接下来怎么继续进阶刷完这套题你可以凭自己的表现来判断下一步计划。如果热身级题目做得还行但核心题卡住我建议下一步的强化方向是动态规划和贪心这是笔试中最常考的两大类算法。你可以找一些专题练习比如LeetCode上的动态规划标签或者牛客网上的名企真题板块把同一类型的题目集中刷一遍边刷边总结规律。如果核心题做得比较顺畅压轴题还有一些吃力那说明你的算法思维已经比较扎实了需要加强的是对高难度题目的敏感度。这时候可以扩展学习一下线段树、树状数组、并查集、状态压缩、图论里的最短路等进阶内容。这些知识不一定每次笔试都会考但一旦考到待遇和分数差距就会拉开。另外我想说刷题数量不是唯一指标。我见过刷了300道题但笔试成绩一般的人也见过只刷了80道题但几乎每次笔试都能通过的人。差别就在于是否真的把每道题的思路想透了、把同类型的题目归纳好了。一套好的真题集如果你能真正做到做完、改完、复盘完、整理完它的价值不亚于漫无目的地刷五套题。回到网易这套2017春招真题最后再分享一个我个人的小技巧刷完之后试着把每道题讲给别人听。找一个朋友或者自己对着镜子从头到尾讲一遍这道题的思路就像在面试时向面试官解释你的解法一样。如果你能把自己讲到别人听懂那你对这道题的理解就真的到位了。这个过程也会帮你提前演练面试中的讲题环节一举两得。根据我个人踩过不少坑之后的体会准备笔试最好的状态不是我刷了很多题而是我看到题能判断出它考察哪种模型、该用什么样的算法框架。网易这套真题就是一个特别好的训练场希望你能在里面把这道判断力练出来。