又到一年秋招季翻出电脑里存的网易2019秋招笔试编程题还是觉得这套题很适合拿来练手。题目本身不算特别难但题型很典型覆盖了字符串处理、数学推导、枚举优化、动态规划和简单模拟基本上是国内大厂笔试里最常出现的几种套路。这篇“合集一”我挑了五道有代表性的题目每道都会拆解题意、推导思路、给出完整代码再把我当时踩过的坑一起写出来。正在准备秋招春招的同学可以直接照着刷基础弱一点的也能从暴力解法开始慢慢理解。这套题最大的价值在于它不靠偏题怪题难为人而是考察你能否把一个实际问题抽象成算法模型再用代码实现出来。很多同学LeetCode刷了几百题一到笔试就懵往往就是卡在“读题转模型”这一步。所以这篇博文里我会重点讲清楚每道题是怎么从题干走到解法的而不是只贴一个答案。1. 网易2019秋招笔试这套题到底在考什么1.1 整体风格和题量分布网易的笔试编程题通常一次给2到4道时间大概90到120分钟有的场次还会混合选择题。难度梯度很明显前面一两道是签到题基本数据结构或简单模拟就能过中间是常规算法题常见的有动态规划、贪心、数学公式推导最后可能会有一道需要优化复杂度的题目用来拉开差距。这套2019秋招的题目就很有代表性简单题能让你快速进入状态中等题则需要动笔推一推规律而不是无脑循环。另外一个特点是题干描述比较长喜欢把问题包装成一个故事。比如“数对”那道题明明是一个数学计数问题却非要先说“牛牛从老师那里得到了一个正整数数对”。如果你读题不够快很容易被这些情节干扰。我当时的习惯是先看输入输出样例再回头读题干这样能更快抓住题目的真实要求。1.2 适合谁刷、怎么刷最有效如果你是正在准备校招的应届生这套题适合用来做笔试前的模拟训练。因为题目难度和类型都比较接近真实笔试不会让你在偏题上浪费时间。如果你想转行做开发或者刚学完数据结构这套题也可以作为从“会语法”到“会算法”的过渡练习。里面没有特别复杂的图论和高级数据结构核心依赖的是数组、字符串、数学思维和递归读起来门槛不高。刷的时候我建议别直接看答案。每道题先自己想10到15分钟哪怕只能写出暴力解法也比直接抄代码有价值。写完之后再看优化思路最后把代码重新默写一遍重点记下那些容易错的边界条件。这套题如果你能自己独立做出来3道以上笔试基本就不虚了如果只能做出1道那说明数学推导和枚举优化还需要再补一补。2. 五道高频真题拆解2.1 字符串碎片读题比写代码更重要题目描述大概是这样的一个由小写字母组成的字符串连续相同字符组成一个“碎片”比如字符串aaabbaaac碎片分别是aaa、bb、aaa、c长度分别为3、2、3、1那么所有碎片的平均长度就是(3231)/4 2.25。要求输出这个平均长度保留两位小数。其实这题的核心就一句话总字符数除以碎片数量。所有碎片长度加起来一定等于字符串长度所以不需要真的去记录每一段多长只需要统计有多少段。遍历一次字符串每次检测到当前字符和前一个字符不同碎片数就加一。首字符不用单独判断直接把计数器初始化为1从第二个字符开始遍历就行。这道题容易翻车的点有两个。一个是输出格式题目要求保留两位小数很多人写print(n / cnt)就交了结果格式错误另一个是忽略了空串输入虽然笔试环境一般不会给空串但用input().strip()处理一下更稳妥。整体复杂度O(n)属于必拿分的题。2.2 被3整除别枚举先推规律这道题给了一个很特殊的数列第1项是1第2项是12第3项是123第4项是1234也就是把从1到i的所有整数依次拼成一个数。然后给两个整数 l 和 r问第 l 项到第 r 项之间有多少个数能被3整除。如果你直接去生成第r项那肯定是不行的。因为项数稍微大一点这个数会膨胀得非常快基本没法用整型保存。正确的切入点是“能被3整除的数各位数字之和也能被3整除”。第i项的数位和是12...i i(i1)/2。我们只需要看这个数位和模3的周期。算一下i1时数位和为1模3余1i2时数位和为3模3余0i3时数位和为6模3余0i4时数位和为10模3余1。所以规律是1,0,0,1,0,0...也就是说只有当 i%31 时第i项不能被3整除其余情况都能被3整除。这样区间计数就很简单了。定义函数 f(x) 表示前x项中能被3整除的个数那么答案就是 f(r)-f(l-1)。前x项中每3个数里有2个满足条件所以f(x) x/3*2 余数部分如果余数为2还要额外加1。也可以用x - (x2)//3来算因为不能被3整除的数量是ceil(x/3)。注意l和r可能很大C要用long longPython则不用太担心溢出。2.3 数对由暴力到O(n)枚举优化这道题当年让不少人卡了很久。题目是给定 n 和 k问有多少个正整数对 (x, y) 满足1 x n、1 y n并且x % y k。n的范围大概是1e5级别直接双重循环肯定会超时。先处理一个特殊情况如果 k0那么任何余数都大于等于0答案是 n*n直接输出。这个特判不能漏不然循环条件会出问题。接下来想要满足x % y k除数 y 至少要大于 k否则余数最大也只有 y-1不可能达到k。所以 y 可以从 k1 枚举到 n。固定一个 y 之后x 从1到n它模 y 的余数一定是周期变化的。每 y 个连续整数构成一个完整周期余数从0到y-1。其中余数大于等于k的数量是 y-k。n 里面有 n//y 个完整周期所以完整周期贡献(y-k) * (n//y)。剩下的部分长度是n % y对应余数从1到n%y。我们要统计其中大于等于k的个数所以是max(0, n%y - k 1)。把这两部分加起来对每个y求和复杂度O(n)1e5的数据量完全能过。这道题的核心是“按余数周期分块”而不是一个数一个数去试。你如果理解了完整周期和剩余部分这两个概念后面做很多计数类题目都能用上。2.4 表达式求值区间DP或全排列都可以题目给了三个1到9的整数 a、b、c你可以在它们之间添加加号或乘号也可以任意加括号要求最后表达式的最大值。比如输入1 2 3最大是(12)*39而不是12*37。因为只有三个数最简单可靠的做法是把所有计算顺序都枚举一遍。你可以想象当前有一个数字序列每次从序列里选相邻的两个数用加法或乘法合并成一个新的数然后继续处理剩下的序列直到只剩一个数。这个过程天然就把加括号的情况全覆盖了。比如1 2 3可以先合并1和2得到3再乘3得到9也可以先合并2和3得到6再加1得到7最后取最大值9。写代码可以用递归也可以用区间DP。如果以后题目扩展成n个数用递归会变成指数级所以建议学习一下区间DP的写法。定义dp[i][j]表示区间 i 到 j 能得到的最大值枚举中间点把区间分成两半左边和右边分别做加法或乘法再合并。本题因为数字都是正数只需要记录最大值如果以后出现减法或除法还要同时记录最小值因为负负得正的情况需要通过最小值转换。这道题想提醒你的是不要只枚举有限的几种表达式模板比如abc、ab*c、a*bc、a*b*c这样很容易漏掉(ab)*c这种结构。只要把“任意相邻合并”这个动作想清楚括号带来的所有可能就都覆盖了。2.5 俄罗斯方块最容易被忽视的隐藏坑这道题看起来很简单但很多人会挂。题目背景是有一块 n 列的俄罗斯方块棋盘m 个方块依次从顶部下落每个方块是1x1每次落到指定的一列。所有方块落完后问能消掉多少行。换句话说棋盘每一列的高度就是该列收到的方块数。只有当所有列都有一个方块时才能凑齐一整行并消掉所以答案等于所有列高度的最小值。如果有一列从头到尾没有收到任何方块那么最小高度就是0答案也就是0。这个“取最小值”而不是“取最大值”是最大的坑。实现上只需维护一个长度为 n 的数组初始都是0。每读到一个列号就把对应位置加1。最后遍历1到n列找最小值。复杂度O(nm)。很多同学做完样例就以为自己是求最高列高度结果一提交发现全错问题就出在题意理解上。笔试里这种“简单但读题有坑”的题往往是区分度很高的题。3. 完整代码与边界处理方案3.1 核心代码实现Python版下面是我自己整理的这五道题的完整Python实现。注释里标了关键步骤和边界处理可以直接拿去本地跑一跑。字符串碎片s input().strip() n len(s) if n 0: print(0.00) exit() cnt 1 for i in range(1, n): if s[i] ! s[i-1]: cnt 1 print(%.2f % (n / cnt))被3整除def f(x): if x 0: return 0 return x - (x 2) // 3 l, r map(int, input().split()) print(f(r) - f(l - 1))数对n, k map(int, input().split()) if k 0: print(n * n) exit() ans 0 for y in range(k 1, n 1): full n // y rem n % y ans (y - k) * full ans max(0, rem - k 1) print(ans)表达式求值def solve(nums): if len(nums) 1: return nums[0] best 0 for i in range(len(nums) - 1): a, b nums[i], nums[i 1] for v in (a b, a * b): nxt nums[:i] [v] nums[i 2:] best max(best, solve(nxt)) return best a, b, c map(int, input().split()) print(solve([a, b, c]))俄罗斯方块data list(map(int, input().split())) n, m data[0], data[1] ops data[2:] height [0] * (n 1) for col in ops: height[col] 1 print(min(height[1:]))这五段代码里数对和被3整除最需要细心。数对的特判k0一旦漏掉样例可能都过不了被3整除则要注意边界函数f(0)的返回值必须是0否则l1时会出错。3.2 容易踩的边界坑和测试用例我整理了几个典型的测试用例你写完代码后可以先用这些验证题目输入输出说明字符串碎片aaabbaaac2.25常规样例验证输出格式字符串碎片a1.00单个字符碎片数为1被3整除1 106第2、3、5、6、8、9项可被3整除被3整除2 42区间是12和123两项都可整除数对3 14手动列举9个数对只有4个满足数对5 025k0时所有数对都满足表达式求值1 2 39最大是(12)*3表达式求值5 1 320最大是5*(13)俄罗斯方块4 6 1 2 2 3 3 30第4列没有方块答案0俄罗斯方块4 7 1 2 3 4 1 2 31每列都有方块最低列高度1看到没数对这道题k0如果不特判输出很可能不是n*n俄罗斯方块如果求成最大值第一个测试用例就会得到3和正确答案0对不上。这些“细节坑”比算法本身更容易让人丢分。4. 笔试现场的问题排查与技巧4.1 常见问题速查表我在模拟笔试和帮别人改代码时发现下面这些问题是出现频率最高的。整理成了一张速查表建议你刷题前扫一眼。出现的问题可能的原因解决办法输出格式不对浮点数没保留两位小数或者多了空格用print(%.2f % ans)或format被3整除超时去生成了第i项大数直接从数位和推导周期不要构造数字本身数对结果偏大没特判k0循环从y1开始k0直接输出n*n否则y从k1开始表达式求值漏情况只枚举固定模板用递归或区间DP实现任意相邻合并俄罗斯方块答案错误求成最大值或读入多行数据没处理答案取最小值用全量split读取所有数字数组越界列号下标从0开始用给数组长度设为n1直接用列号作为下标第二行和第三行是重灾区很多人以为“被3整除”需要高精度大数以为“数对”只能双重循环结果又超时又存不下。笔试的时候如果卡住了先回头想想是不是可以用数学规律优化不要死磕暴力。4.2 我的实战排错经验第一次刷这套题的时候“被3整除”我一开始写的是暴力从第l项到第r项每次构造一个字符串再判断各位数字之和是否模3为0。结果样例能过但一跑大数据就超时而且构造出来的数字长到连Python都觉得吃力。后来我意识到这道题的模型不是“大数整除”而是“数位和模3”马上换思路写了几行公式就过了。“数对”那道题我犯过两个错误。第一个是忘记k0的特判导致当k0时循环里出现y-k变成 y好像也能算出结果但边界很混乱样例都不好过。第二个错误是剩余部分的贡献写成了rem // k之类的错误公式。实际上剩余部分的余数是从1到rem连续分布的要统计其中≥k的个数应该是max(0, rem - k 1)。你自己画个数轴就明白了。表达式求值这道题我一开始用穷举八种表达式模板后面发现这样很容易漏情况。比如(ab)*c这种结构如果只考虑三个数字之间的两个运算符很难系统覆盖所有加括号方式。改成递归合并相邻数字后思路就清晰很多。这道题让我养成了一个习惯凡是遇到“添加符号、加括号求最值”的题优先想区间DP或递归枚举而不是手写所有组合。5. 题后复盘与扩展思考5.1 这套题暴露出的能力短板把这五道题放在一起看明显能感觉到网易考察的不只是“会不会背模板”而是你有没有把数学和算法结合起来的能力。字符串碎片和俄罗斯方块都是纯模拟考察细心程度被3整除和数对都是需要先推公式再实现的题表达式求值则考察你是否能把“枚举所有计算顺序”转换成代码。如果这些题中有两道以上让你没有思路说明基础可能还需要巩固。被3整除这种题本质上考的是整除性质的灵活运用数对这种题考的是对取模运算周期性的理解表达式求值考的是递归和动态规划的基本功。建议回头把这几个专题分别刷一刷比如把LeetCode上关于取模、区间DP的题目集中做一遍。5.2 后续还可以怎么扩展这套题其实每一道都可以继续往深处扩展。被3整除可以推广成“判断一个超长拼接数对任意模数的余数”核心思路依然是数位和或直接模拟除法数对可以用整除分块继续优化把O(n)降到O(sqrt(n))表达式求值如果加入减号和除号就需要同时维护最大值和最小值俄罗斯方块是一个典型的模拟入口扩展成完整游戏规则后还能练一练二维数组和状态维护。这些扩展点我后续会在“合集二”里继续写。我个人刷完这套题最大的体会是笔试编程题不是靠背题就能过的关键是把常见题型的思考路径吃透。先暴力解再优化再总结边界条件这个过程比最终AC那一刹那更值钱。你现在花时间搞明白的每个“为什么”到了真正的笔试现场都会变成肌肉记忆。