2017年网易内推笔试编程题合集在校招圈子里基本算是“必刷清单”中的常客了。我印象里这套题反复出现过好几轮应届那年自己当真题练手后来帮学弟学妹讲题时又翻出来逐题拆过一遍再后来做模拟面试时还会拿其中某道题作为考察样例。放到今天看题目背景虽然还带着那几年校招的语境但涉及的算法模型一点都不过时动态规划、搜索、字符串处理、数学推导恰恰是互联网大厂笔试最常出现的四类题型。这篇文章我就把这套题里有代表性的几道题完整展开从题意理解、状态设计、代码实现到笔试现场的取舍策略一次性讲清楚。无论你是正在备战校招的应届生还是想找些经典题巩固算法基础的开发者这套题都值得认真过一遍。1. 这套题到底在考什么2017网易内推笔试的命题逻辑先别急着上手敲代码拿到题集的第一步是看懂出题人的布局。网易这套内推笔试题的整体风格非常稳定题量一般在4到6道之间时间给到90分钟到120分钟。难度梯度很清晰前一两道是简化版的字符串、模拟或数学题用来快速筛掉基础不扎实的候选人中间是搜索或动态规划用来区分有没有算法思维最后往往放一道综合题难度明显上升用来筛选能从容处理复杂状态的人。这种“由浅入深、逐步加压”的结构并不是网易独有的几乎所有大厂笔试都在用只是网易特别爱把题目包装成游戏、动漫、生活场景比如合唱团、地牢、下厨房本质却都是最基础的算法模型。1.1 题型分布动态规划、搜索、字符串、数学全覆盖从整体考察面来看这套题集覆盖得非常均衡。动态规划部分有经典的乘积最大问题也有排列补全类的复杂状态设计搜索部分出现了基于二维地图的最短路径问题表面是地图遍历实际考的是对BFS的理解字符串部分则包含集合去重、子序列判断这类高频基础操作数学题更是直接用上了求和公式和整数边界判断。这种覆盖面不是巧合而是校招笔试的标准配置在有限时间内一套题既要能考出基本功又要能试探思维上限必须在各模块之间找到平衡。我建议拿到题集后先做一次“题型标签”整理每道题不用完整做出来只判断它属于哪类模型然后按难度排序。这样做的好处是能快速识别自己的强弱项如果你看到一道题能立刻说出“这是BFS”“这是区间DP”“这是双指针”那笔试的时候就已经赢了一半。反过来如果连题目的算法类别都判断不出来那不管刷多少题都容易在同一个地方卡住。1.2 难度设计为什么把简单题放在前面很多人刷题有个坏习惯一上来就钻进难题里死磕结果时间全耗在一道题上。网易这套题的难度排序其实已经给了提示第一题通常简单到只要会用集合去重就能过第二题是字符串判断或基础数学第三题才开始上动态规划和搜索。出题人把简单题放在前面不只是为了送分更是在测试你的时间管理能力。我见过不少候选人前三十分钟就把两道简单题做完了留下充足时间啃难题最后轻松通过。也见过有人上来先把看起来最炫的压轴题研究了一通结果压轴题没做出来前面简单的题也来不及写完。笔试不是竞赛目标不是解出最难的那一道而是在有限时间内拿尽可能多的分。所以我的建议是先花五分钟扫一遍所有题目按“肯定能做出来、需要想一想、可能做不出来”分成三档从最简单的开始写把能拿的分全部拿稳再回头啃硬骨头。2. 动态规划题合唱团的完整推导与代码实现这套题集里最经典的一道非“合唱团”莫属。题目大概是这样有n个学生站成一排每个学生有一个能力值这个能力值可以是正数也可以是负数。现在要从这n个学生中选出k个学生组成一个合唱团要求任意两个相邻被选中学生的编号差不能超过d求选出的k个学生能力值乘积的最大值。这道题我每次讲校招题都会拿出来说因为它包含了动态规划里几个最容易踩坑的点负数乘积、多维状态、区间约束。很多人第一眼看到“选k个”“相邻编号差不超过d”会本能想到用组合数枚举但n的范围一旦到50以上枚举就完全不可行了。必须用动态规划来压缩状态。2.1 题意与输入输出先确认一下输入输出避免后面代码写偏。第一行输入n表示学生数量。第二行输入n个整数表示每个学生的能力值能力值范围可能包含负数。第三行输入两个整数k和dk表示需要选出的学生人数d表示相邻两个被选中学生的编号差上限。题目保证有解输出一个整数表示最大乘积。这里有个容易忽略的细节能力值有正有负。如果只维护最大值负数乘负数的情况会被漏掉。举例来说能力值是[-1, -1, 5]选两个人编号差上限足够大最优选择是-1和-1乘积为1比-1乘5等于-5要大得多。但如果只用一个dp数组记录最大值-1和-1的组合在状态转移时根本不会被考虑到因为你记录的是“以某个学生结尾的最大乘积”两个负数相乘的中间状态在局部看是极小的会被直接丢弃。2.2 状态定义与转移方程推导这道题的状态设计是典型的“以谁结尾”思路。定义dp_max[i][j]表示“前i个学生中选出j个并且第i个学生是最后一个被选中的情况下能得到的最大乘积”dp_min[i][j]表示相同条件下的最小乘积。初始状态很好写当选1个人时dp_max[i][1] dp_min[i][1] a[i]因为只有一个学生最大值和最小值都是这个学生的能力值。转移的时候要枚举上一个被选中的学生是谁。既然相邻两个被选中学生的编号差不能超过d那上一个被选中的学生p就必须满足 i - d p i。于是状态转移方程可以写成dp_max[i][j] max(dp_max[p][j-1] * a[i], dp_min[p][j-1] * a[i])p从max(1, i-d)遍历到i-1。dp_min[i][j] min(dp_max[p][j-1] * a[i], dp_min[p][j-1] * a[i])p同样从max(1, i-d)遍历到i-1。为什么要同时考虑dp_max和dp_min因为dp_max[p][j-1] * a[i]可能因为a[i]是负数而变成很小的值而dp_min[p][j-1] * a[i]反而可能变成很大的值。所以每次转移必须把两种可能的乘积都算一遍再从里面挑最大或最小。最终答案就是所有dp_max[i][k]里的最大值i从k到n。2.3 参考实现与复杂度分析用C实现的话代码不长但有几个细节必须注意。dp数组要初始化成足够小和足够大的值不能默认是0否则转移时会漏掉负数乘积的情况。数组下标最好从1开始这样计算编号差的时候更直观。我把核心代码贴出来#include iostream #include vector #include algorithm #include climits using namespace std; int main() { int n; cin n; vectorlong long a(n 1); for (int i 1; i n; i) cin a[i]; int k, d; cin k d; vectorvectorlong long dp_max(n 1, vectorlong long(k 1, LLONG_MIN / 2)); vectorvectorlong long dp_min(n 1, vectorlong long(k 1, LLONG_MAX / 2)); for (int i 1; i n; i) { dp_max[i][1] a[i]; dp_min[i][1] a[i]; } for (int i 1; i n; i) { for (int j 2; j k; j) { for (int p max(1, i - d); p i; p) { dp_max[i][j] max(dp_max[i][j], max(dp_max[p][j - 1] * a[i], dp_min[p][j - 1] * a[i])); dp_min[i][j] min(dp_min[i][j], min(dp_max[p][j - 1] * a[i], dp_min[p][j - 1] * a[i])); } } } long long ans LLONG_MIN; for (int i k; i n; i) { ans max(ans, dp_max[i][k]); } cout ans endl; return 0; }复杂度是O(n * k * d)。n一般不超过50k不超过10d不超过n这个复杂度完全可以接受。如果哪天遇到n到1000的情况就需要用单调队列优化了但笔试范围基本不会那么极端先掌握基础写法更重要。这道题我个人觉得最值得学的不是代码本身而是“同时维护最大和最小”这个思维模式。以后你遇到“乘积最大”“差值最小”这类带负数的动态规划题第一反应就应该是设计两个状态数组而不是纠结于某个局部最优是否会被丢掉。3. 搜索与图遍历地牢逃脱的BFS解法第二道我想重点讲的是“地牢逃脱”。题目背景大致是牛牛被困在一个n行m列的地牢里地牢用0和1表示0代表可以走1代表障碍物。牛牛有一个初始位置还有一组移动方式每种移动方式是一个坐标偏移比如(1, 0)表示向右走一步。牛牛每次可以选择任意一种移动方式但移动后的位置必须在地牢范围内且不是障碍物。题目问的是牛牛从起点出发最多需要多少步才能走到所有可以到达的格子如果存在某个可走格子永远也到不了那就输出-1。3.1 为什么这道题不能用DFS硬刚很多人看到“地图遍历”四个字第一反应就是DFS。但这道题有个很关键的点问的是“从起点到每个可到达格子的最少步数中的最大值”。DFS在解决“是否存在路径”时确实很方便但让它去求最短步数就非常别扭了。因为DFS本质上是沿一条路走到底再回头它第一次到达某个格子的深度并不一定是最短路径你需要遍历所有可能路径才能确定最小值复杂度会爆炸。BFS则天然适合这个问题。BFS逐层向外扩展第一次到达某个格子的层数就是该格子的最短步数。这是BFS最核心的性质也是这道题的命门。所以见到“最短步数”“最少操作次数”这类描述用BFS基本不会错。3.2 BFS实现步骤与边界处理实现步骤其实很固定。先定义dist二维数组初始化为-1表示还没访问过。起点的dist设为0然后入队。循环从队列中取出一个格子尝试每一种移动方式算出新的坐标如果新坐标在地图范围内、对应位置是0、且dist还是-1就更新dist为当前dist加1并把它入队。BFS结束后遍历整个地图检查所有值为0的位置是否dist都已经不是-1如果存在不可达的可走格子直接输出-1。否则取所有可达格子dist的最大值就是答案。边界处理有几个容易被坑的地方。第一起点的坐标是从0开始还是从1开始题目里通常会直接说明但现实中很多人不看就默认按0处理结果一出样例就错。第二移动方式可能是负数偏移比如(-1, 0)这意味着牛牛可以向上走不能因为看到负号就丢掉这种移动方式。第三输入地图时如果用的是字符串要注意字符0和1要转成数字再判断不能直接拿字符去比较。3.3 代码与复杂度参考代码用C写是这样的#include iostream #include vector #include queue #include algorithm using namespace std; int main() { int n, m; cin n m; vectorstring maze(n); for (int i 0; i n; i) cin maze[i]; int x0, y0; cin x0 y0; int k; cin k; vectorint dx(k), dy(k); for (int i 0; i k; i) cin dx[i] dy[i]; vectorvectorint dist(n, vectorint(m, -1)); queuepairint, int q; dist[x0][y0] 0; q.push({x0, y0}); while (!q.empty()) { auto cur q.front(); q.pop(); int x cur.first, y cur.second; for (int i 0; i k; i) { int nx x dx[i]; int ny y dy[i]; if (nx 0 || nx n || ny 0 || ny m) continue; if (maze[nx][ny] ! 0) continue; if (dist[nx][ny] ! -1) continue; dist[nx][ny] dist[x][y] 1; q.push({nx, ny}); } } int ans 0; for (int i 0; i n; i) { for (int j 0; j m; j) { if (maze[i][j] 0) { if (dist[i][j] -1) { cout -1 endl; return 0; } ans max(ans, dist[i][j]); } } } cout ans endl; return 0; }复杂度是O(n * m * k)也就是每个格子最多被访问一次每次访问尝试k种移动。这个复杂度在笔试范围内非常安全几乎不会超时。这道题给我的启发是搜索题不要急着写代码先把“要输出什么”搞清楚。如果题目问的是最少步数BFS如果问的是是否存在路径DFS也可以如果问的是方案数那就得用DFS加回溯或者动态规划了。模型选对代码只是时间问题。4. 简单题快速拿分下厨房、藏宝图、星际穿越这套题集里还有几道相对简单的题很多同学觉得“太水了不值得做”我反而觉得这些题才是最需要练习的。笔试时间那么紧能不能在最短时间内把送分题全拿到手往往决定了你能不能进入下一轮。简单题不是用来展示智商的是用来稳住心态的。4.1 下厨房用集合去重5分钟拿分“下厨房”这道题的题意很直白牛牛想做几道菜每道菜需要若干种材料现在把所有菜谱都给你问一共需要多少种不同的材料。输入是多行每行对应一道菜所需要的材料材料名用空格分隔要求输出材料种类的总数。核心解法就一句话把所有材料丢进一个set里最后输出set的size。C里可以直接用set 一行一行读取输入遇到EOF结束。读取的时候用stringstream把每行按空格拆开逐个插入set。这里有个值得说的经验笔试环境里经常出现多行输入直到EOF的情况很多人平时刷LeetCode习惯了固定输入格式一到这种需要自己处理EOF的题就懵。其实C里while(getline(cin, line))就能解决Python里用sys.stdin.read().split()更省事直接拿到所有单词列表转set。这道题虽然简单但它考察的核心能力是“能不能在紧张状态下快速处理输入格式”。我见过不少人因为少写一个头文件或者没处理换行符白白提交了好几次错误答案。所以平时练习时一定要刻意训练自己处理各种输入格式的速度。4.2 藏宝图双指针判断子序列“藏宝图”的模型也很典型给定两个字符串s和t判断t是不是s的子序列。所谓子序列就是指t中每个字符都能在s中找到且它们在s中出现的顺序与在t中的顺序一致但不需要连续。最直接的解法是双指针i指向sj指向t遍历s每当s[i]等于t[j]时j向后移动一位。如果最后j走到了t的末尾说明t的所有字符都在s中按顺序找到了返回true否则返回false。这道题难的地方不在于思路而在于特殊情况的处理。比如t是空字符串按照定义空字符串是任何字符串的子序列应该返回true。又比如t的长度大于s那一定返回false。还有字符大小写是否敏感如果题目没有说明默认是敏感的不要自己去额外处理。双指针的复杂度是O(len(s))一次遍历就解决了。这个思想在后续很多面试题里都会用到比如判断链表是否有环、合并两个有序数组、找两个数组的交集本质上都是维护两个指针按某种规则移动。4.3 星际穿越数学推导而非二分硬算“星际穿越”也是一道考察数学功底的题。题目大意类似牛牛的飞船飞行距离按秒递增第1秒飞1个单位第2秒飞2个单位第3秒飞3个单位依此类推。给定一个总燃料h问最多能飞多少秒而不超过h。这个问题等价于求最大的整数n使得1 2 ... n n(n 1) / 2 ≤ h。这道题很多人上来就写二分也没问题因为n的范围可能很大二分到float精度也可以接受。但更优雅的方式是用一元二次方程求解n(n 1) / 2 ≤ h即n^2 n - 2h ≤ 0解出n floor((sqrt(1 8h) - 1) / 2)。这里有个陷阱直接用浮点数sqrt和floor可能会因为精度问题在边界处出错。比如h正好是一个三角数计算出来的n可能比真实值少1。我的习惯是先用公式算出一个候选值然后检查候选值加1是否仍然满足条件如果满足就加1这样能有效规避浮点误差。更稳妥的做法是用整数二分因为二分只需要用long long做乘法和比较完全避开浮点数。这道题给我们的提示是数学题往往有比模拟更快的解法但必须注意整数边界。笔试里很多看似需要模拟到最后一步的题实际上都可以用数学公式直接算平时多积累这类模板考场上就能省下大量时间。5. 笔试现场的时间分配与常见问题排查代码能力训练到一定程度后真正拉开差距的往往是考场上的临场策略。网易这套题集特别适合用来模拟真实笔试因为它的题型和难度分布非常接近实战。我建议你把每次刷题都当成真正的笔试来对待定好90分钟倒计时只开一个编辑器尽量模拟在线评测环境做完再统一对答案。5.1 读题和样例分析的正确顺序很多人拿到题目第一眼看到样例就直接照着样例写这是很危险的习惯。正确的读题顺序应该是先读输入输出格式再读数据范围最后读样例。输入输出格式决定了你要处理的数据结构数据范围决定了算法复杂度底线样例只是用来验证你对题意的理解是否正确。我在刷这套题时每道题都会先把题目里的关键约束圈出来比如“d最大是多少”“乘积是否需要long long”“地图长宽范围”。这些约束看似不起眼实际上决定了你该用哪种写法。比如合唱团这道题如果能力值很大且k也大乘积就必须用long long否则会溢出成错误的答案。5.2 边界条件与数据范围容易被坑的地方笔试里最常见的错误不是算法不会而是边界条件没处理好。合唱团的负数乘积、地牢逃脱的障碍物和越界、星际穿越的浮点精度这些都是活生生的例子。我总结过一套“边界自查清单”每次提交前快速过一遍数组下标是否越界循环边界是否包含最后一个元素输入是否可能为空数字是否可能为负数计算结果是否可能溢出字符串是否需要处理大小写和空格。有一次我帮人调地牢逃脱的代码对方卡了很久最后发现是起点坐标没有做合法性检查样例里起点永远是合法的但实际测试数据里起点可能是障碍物BFS直接输出-1就错了。很多题目不会在样例里给出极端情况但后台测试数据一定会包含所以自查边界是提分最快的方式。5.3 调试技巧与本地测试用例设计在线笔试环境通常不支持一步步断点调试所以你必须在本地提前准备好测试能力。最简单的做法是在本地写代码时手动构造几组边界用例。合唱团想想全是负数、全是正数、正负混合、长度为1、k等于n、d等于1这些情况。地牢逃脱想想地图只有1行1列、起点被障碍包围、移动方式包含原地踏步或重复方式。宇宙穿越想想h等于0、h正好等于某个三角数、h巨大到接近long long上限。这些用例不需要多但覆盖要全。我习惯在写完代码后先用简单用例跑通再故意构造一两个极端用例去验证。能过了这些在线评测系统里的数据大概率也能过。要是还有问题就在代码里临时加输出语句把中间变量打出来分析是哪一步的数值不对比盯着代码干瞪眼有效得多。6. 从笔试到Offer这套题暴露的能力模型与准备建议刷完这套题如果你只记住了题目答案那收益其实很有限。真正该做的是透过题目去看网易这类大厂在筛选什么样的人。校招笔试不是奥数竞赛它考的不只是你会不会某道题更是你在限时压力下能不能快速定位问题、选择合适算法、写出干净代码以及有没有足够的边界意识。从这套题来看网易特别看重基础算法的灵活应用。合唱团考的虽然是最经典的动态规划但加了负数乘积和距离约束比直接背模板高了一个层次。地牢逃脱考的是BFS但很多人会惯性用DFS说明出题人不仅考察你会不会搜索还考察你能不能根据题意选择正确算法。所以刷题时别满足于“AC了就行”要追问一句为什么这个题用这个算法换一种行不行如果数据范围变大要怎么优化。后续准备的话我建议你把这套题当成“自测卷”而不是“题库”。做完一遍之后把所有题目按类型归类统计自己在哪类题上花的时间最多、错误率最高然后针对性补强。动态规划薄弱就集中刷背包、区间、状态压缩搜索薄弱就多练BFS和DFS的变种。另外强烈推荐在纸上手写状态转移方程不要一上来就敲代码这样能把思路理得更清楚面试时被追问思路也不会慌。这套题里还有一两道综合题比如排列补全类的题难度确实比前面几道高出一截我第一次做的时候也卡了很久。对于这种题我的态度是笔试时如果时间不够果断放弃或写个暴力拿部分分但日常练习时一定要啃下来因为这类题往往是面试官深挖的素材弄懂一道带来的提升比刷十道简单题还大。说到底网易这套2017年内推笔试题集真正值得学的是题目背后的思考方式如何从无序的信息中抽象出模型如何在常数时间内完成状态转移如何在边界条件下保证正确性。这些能力不会因为题目“过时”而贬值反而是你走得更远的底座。如果你正备战校招不妨从这套题开始每天两道认真总结一个月后再回头看一定会发现自己对算法题的理解完全不一样了。
2017网易内推笔试编程题解析：动态规划与BFS实战
2017年网易内推笔试编程题合集在校招圈子里基本算是“必刷清单”中的常客了。我印象里这套题反复出现过好几轮应届那年自己当真题练手后来帮学弟学妹讲题时又翻出来逐题拆过一遍再后来做模拟面试时还会拿其中某道题作为考察样例。放到今天看题目背景虽然还带着那几年校招的语境但涉及的算法模型一点都不过时动态规划、搜索、字符串处理、数学推导恰恰是互联网大厂笔试最常出现的四类题型。这篇文章我就把这套题里有代表性的几道题完整展开从题意理解、状态设计、代码实现到笔试现场的取舍策略一次性讲清楚。无论你是正在备战校招的应届生还是想找些经典题巩固算法基础的开发者这套题都值得认真过一遍。1. 这套题到底在考什么2017网易内推笔试的命题逻辑先别急着上手敲代码拿到题集的第一步是看懂出题人的布局。网易这套内推笔试题的整体风格非常稳定题量一般在4到6道之间时间给到90分钟到120分钟。难度梯度很清晰前一两道是简化版的字符串、模拟或数学题用来快速筛掉基础不扎实的候选人中间是搜索或动态规划用来区分有没有算法思维最后往往放一道综合题难度明显上升用来筛选能从容处理复杂状态的人。这种“由浅入深、逐步加压”的结构并不是网易独有的几乎所有大厂笔试都在用只是网易特别爱把题目包装成游戏、动漫、生活场景比如合唱团、地牢、下厨房本质却都是最基础的算法模型。1.1 题型分布动态规划、搜索、字符串、数学全覆盖从整体考察面来看这套题集覆盖得非常均衡。动态规划部分有经典的乘积最大问题也有排列补全类的复杂状态设计搜索部分出现了基于二维地图的最短路径问题表面是地图遍历实际考的是对BFS的理解字符串部分则包含集合去重、子序列判断这类高频基础操作数学题更是直接用上了求和公式和整数边界判断。这种覆盖面不是巧合而是校招笔试的标准配置在有限时间内一套题既要能考出基本功又要能试探思维上限必须在各模块之间找到平衡。我建议拿到题集后先做一次“题型标签”整理每道题不用完整做出来只判断它属于哪类模型然后按难度排序。这样做的好处是能快速识别自己的强弱项如果你看到一道题能立刻说出“这是BFS”“这是区间DP”“这是双指针”那笔试的时候就已经赢了一半。反过来如果连题目的算法类别都判断不出来那不管刷多少题都容易在同一个地方卡住。1.2 难度设计为什么把简单题放在前面很多人刷题有个坏习惯一上来就钻进难题里死磕结果时间全耗在一道题上。网易这套题的难度排序其实已经给了提示第一题通常简单到只要会用集合去重就能过第二题是字符串判断或基础数学第三题才开始上动态规划和搜索。出题人把简单题放在前面不只是为了送分更是在测试你的时间管理能力。我见过不少候选人前三十分钟就把两道简单题做完了留下充足时间啃难题最后轻松通过。也见过有人上来先把看起来最炫的压轴题研究了一通结果压轴题没做出来前面简单的题也来不及写完。笔试不是竞赛目标不是解出最难的那一道而是在有限时间内拿尽可能多的分。所以我的建议是先花五分钟扫一遍所有题目按“肯定能做出来、需要想一想、可能做不出来”分成三档从最简单的开始写把能拿的分全部拿稳再回头啃硬骨头。2. 动态规划题合唱团的完整推导与代码实现这套题集里最经典的一道非“合唱团”莫属。题目大概是这样有n个学生站成一排每个学生有一个能力值这个能力值可以是正数也可以是负数。现在要从这n个学生中选出k个学生组成一个合唱团要求任意两个相邻被选中学生的编号差不能超过d求选出的k个学生能力值乘积的最大值。这道题我每次讲校招题都会拿出来说因为它包含了动态规划里几个最容易踩坑的点负数乘积、多维状态、区间约束。很多人第一眼看到“选k个”“相邻编号差不超过d”会本能想到用组合数枚举但n的范围一旦到50以上枚举就完全不可行了。必须用动态规划来压缩状态。2.1 题意与输入输出先确认一下输入输出避免后面代码写偏。第一行输入n表示学生数量。第二行输入n个整数表示每个学生的能力值能力值范围可能包含负数。第三行输入两个整数k和dk表示需要选出的学生人数d表示相邻两个被选中学生的编号差上限。题目保证有解输出一个整数表示最大乘积。这里有个容易忽略的细节能力值有正有负。如果只维护最大值负数乘负数的情况会被漏掉。举例来说能力值是[-1, -1, 5]选两个人编号差上限足够大最优选择是-1和-1乘积为1比-1乘5等于-5要大得多。但如果只用一个dp数组记录最大值-1和-1的组合在状态转移时根本不会被考虑到因为你记录的是“以某个学生结尾的最大乘积”两个负数相乘的中间状态在局部看是极小的会被直接丢弃。2.2 状态定义与转移方程推导这道题的状态设计是典型的“以谁结尾”思路。定义dp_max[i][j]表示“前i个学生中选出j个并且第i个学生是最后一个被选中的情况下能得到的最大乘积”dp_min[i][j]表示相同条件下的最小乘积。初始状态很好写当选1个人时dp_max[i][1] dp_min[i][1] a[i]因为只有一个学生最大值和最小值都是这个学生的能力值。转移的时候要枚举上一个被选中的学生是谁。既然相邻两个被选中学生的编号差不能超过d那上一个被选中的学生p就必须满足 i - d p i。于是状态转移方程可以写成dp_max[i][j] max(dp_max[p][j-1] * a[i], dp_min[p][j-1] * a[i])p从max(1, i-d)遍历到i-1。dp_min[i][j] min(dp_max[p][j-1] * a[i], dp_min[p][j-1] * a[i])p同样从max(1, i-d)遍历到i-1。为什么要同时考虑dp_max和dp_min因为dp_max[p][j-1] * a[i]可能因为a[i]是负数而变成很小的值而dp_min[p][j-1] * a[i]反而可能变成很大的值。所以每次转移必须把两种可能的乘积都算一遍再从里面挑最大或最小。最终答案就是所有dp_max[i][k]里的最大值i从k到n。2.3 参考实现与复杂度分析用C实现的话代码不长但有几个细节必须注意。dp数组要初始化成足够小和足够大的值不能默认是0否则转移时会漏掉负数乘积的情况。数组下标最好从1开始这样计算编号差的时候更直观。我把核心代码贴出来#include iostream #include vector #include algorithm #include climits using namespace std; int main() { int n; cin n; vectorlong long a(n 1); for (int i 1; i n; i) cin a[i]; int k, d; cin k d; vectorvectorlong long dp_max(n 1, vectorlong long(k 1, LLONG_MIN / 2)); vectorvectorlong long dp_min(n 1, vectorlong long(k 1, LLONG_MAX / 2)); for (int i 1; i n; i) { dp_max[i][1] a[i]; dp_min[i][1] a[i]; } for (int i 1; i n; i) { for (int j 2; j k; j) { for (int p max(1, i - d); p i; p) { dp_max[i][j] max(dp_max[i][j], max(dp_max[p][j - 1] * a[i], dp_min[p][j - 1] * a[i])); dp_min[i][j] min(dp_min[i][j], min(dp_max[p][j - 1] * a[i], dp_min[p][j - 1] * a[i])); } } } long long ans LLONG_MIN; for (int i k; i n; i) { ans max(ans, dp_max[i][k]); } cout ans endl; return 0; }复杂度是O(n * k * d)。n一般不超过50k不超过10d不超过n这个复杂度完全可以接受。如果哪天遇到n到1000的情况就需要用单调队列优化了但笔试范围基本不会那么极端先掌握基础写法更重要。这道题我个人觉得最值得学的不是代码本身而是“同时维护最大和最小”这个思维模式。以后你遇到“乘积最大”“差值最小”这类带负数的动态规划题第一反应就应该是设计两个状态数组而不是纠结于某个局部最优是否会被丢掉。3. 搜索与图遍历地牢逃脱的BFS解法第二道我想重点讲的是“地牢逃脱”。题目背景大致是牛牛被困在一个n行m列的地牢里地牢用0和1表示0代表可以走1代表障碍物。牛牛有一个初始位置还有一组移动方式每种移动方式是一个坐标偏移比如(1, 0)表示向右走一步。牛牛每次可以选择任意一种移动方式但移动后的位置必须在地牢范围内且不是障碍物。题目问的是牛牛从起点出发最多需要多少步才能走到所有可以到达的格子如果存在某个可走格子永远也到不了那就输出-1。3.1 为什么这道题不能用DFS硬刚很多人看到“地图遍历”四个字第一反应就是DFS。但这道题有个很关键的点问的是“从起点到每个可到达格子的最少步数中的最大值”。DFS在解决“是否存在路径”时确实很方便但让它去求最短步数就非常别扭了。因为DFS本质上是沿一条路走到底再回头它第一次到达某个格子的深度并不一定是最短路径你需要遍历所有可能路径才能确定最小值复杂度会爆炸。BFS则天然适合这个问题。BFS逐层向外扩展第一次到达某个格子的层数就是该格子的最短步数。这是BFS最核心的性质也是这道题的命门。所以见到“最短步数”“最少操作次数”这类描述用BFS基本不会错。3.2 BFS实现步骤与边界处理实现步骤其实很固定。先定义dist二维数组初始化为-1表示还没访问过。起点的dist设为0然后入队。循环从队列中取出一个格子尝试每一种移动方式算出新的坐标如果新坐标在地图范围内、对应位置是0、且dist还是-1就更新dist为当前dist加1并把它入队。BFS结束后遍历整个地图检查所有值为0的位置是否dist都已经不是-1如果存在不可达的可走格子直接输出-1。否则取所有可达格子dist的最大值就是答案。边界处理有几个容易被坑的地方。第一起点的坐标是从0开始还是从1开始题目里通常会直接说明但现实中很多人不看就默认按0处理结果一出样例就错。第二移动方式可能是负数偏移比如(-1, 0)这意味着牛牛可以向上走不能因为看到负号就丢掉这种移动方式。第三输入地图时如果用的是字符串要注意字符0和1要转成数字再判断不能直接拿字符去比较。3.3 代码与复杂度参考代码用C写是这样的#include iostream #include vector #include queue #include algorithm using namespace std; int main() { int n, m; cin n m; vectorstring maze(n); for (int i 0; i n; i) cin maze[i]; int x0, y0; cin x0 y0; int k; cin k; vectorint dx(k), dy(k); for (int i 0; i k; i) cin dx[i] dy[i]; vectorvectorint dist(n, vectorint(m, -1)); queuepairint, int q; dist[x0][y0] 0; q.push({x0, y0}); while (!q.empty()) { auto cur q.front(); q.pop(); int x cur.first, y cur.second; for (int i 0; i k; i) { int nx x dx[i]; int ny y dy[i]; if (nx 0 || nx n || ny 0 || ny m) continue; if (maze[nx][ny] ! 0) continue; if (dist[nx][ny] ! -1) continue; dist[nx][ny] dist[x][y] 1; q.push({nx, ny}); } } int ans 0; for (int i 0; i n; i) { for (int j 0; j m; j) { if (maze[i][j] 0) { if (dist[i][j] -1) { cout -1 endl; return 0; } ans max(ans, dist[i][j]); } } } cout ans endl; return 0; }复杂度是O(n * m * k)也就是每个格子最多被访问一次每次访问尝试k种移动。这个复杂度在笔试范围内非常安全几乎不会超时。这道题给我的启发是搜索题不要急着写代码先把“要输出什么”搞清楚。如果题目问的是最少步数BFS如果问的是是否存在路径DFS也可以如果问的是方案数那就得用DFS加回溯或者动态规划了。模型选对代码只是时间问题。4. 简单题快速拿分下厨房、藏宝图、星际穿越这套题集里还有几道相对简单的题很多同学觉得“太水了不值得做”我反而觉得这些题才是最需要练习的。笔试时间那么紧能不能在最短时间内把送分题全拿到手往往决定了你能不能进入下一轮。简单题不是用来展示智商的是用来稳住心态的。4.1 下厨房用集合去重5分钟拿分“下厨房”这道题的题意很直白牛牛想做几道菜每道菜需要若干种材料现在把所有菜谱都给你问一共需要多少种不同的材料。输入是多行每行对应一道菜所需要的材料材料名用空格分隔要求输出材料种类的总数。核心解法就一句话把所有材料丢进一个set里最后输出set的size。C里可以直接用set 一行一行读取输入遇到EOF结束。读取的时候用stringstream把每行按空格拆开逐个插入set。这里有个值得说的经验笔试环境里经常出现多行输入直到EOF的情况很多人平时刷LeetCode习惯了固定输入格式一到这种需要自己处理EOF的题就懵。其实C里while(getline(cin, line))就能解决Python里用sys.stdin.read().split()更省事直接拿到所有单词列表转set。这道题虽然简单但它考察的核心能力是“能不能在紧张状态下快速处理输入格式”。我见过不少人因为少写一个头文件或者没处理换行符白白提交了好几次错误答案。所以平时练习时一定要刻意训练自己处理各种输入格式的速度。4.2 藏宝图双指针判断子序列“藏宝图”的模型也很典型给定两个字符串s和t判断t是不是s的子序列。所谓子序列就是指t中每个字符都能在s中找到且它们在s中出现的顺序与在t中的顺序一致但不需要连续。最直接的解法是双指针i指向sj指向t遍历s每当s[i]等于t[j]时j向后移动一位。如果最后j走到了t的末尾说明t的所有字符都在s中按顺序找到了返回true否则返回false。这道题难的地方不在于思路而在于特殊情况的处理。比如t是空字符串按照定义空字符串是任何字符串的子序列应该返回true。又比如t的长度大于s那一定返回false。还有字符大小写是否敏感如果题目没有说明默认是敏感的不要自己去额外处理。双指针的复杂度是O(len(s))一次遍历就解决了。这个思想在后续很多面试题里都会用到比如判断链表是否有环、合并两个有序数组、找两个数组的交集本质上都是维护两个指针按某种规则移动。4.3 星际穿越数学推导而非二分硬算“星际穿越”也是一道考察数学功底的题。题目大意类似牛牛的飞船飞行距离按秒递增第1秒飞1个单位第2秒飞2个单位第3秒飞3个单位依此类推。给定一个总燃料h问最多能飞多少秒而不超过h。这个问题等价于求最大的整数n使得1 2 ... n n(n 1) / 2 ≤ h。这道题很多人上来就写二分也没问题因为n的范围可能很大二分到float精度也可以接受。但更优雅的方式是用一元二次方程求解n(n 1) / 2 ≤ h即n^2 n - 2h ≤ 0解出n floor((sqrt(1 8h) - 1) / 2)。这里有个陷阱直接用浮点数sqrt和floor可能会因为精度问题在边界处出错。比如h正好是一个三角数计算出来的n可能比真实值少1。我的习惯是先用公式算出一个候选值然后检查候选值加1是否仍然满足条件如果满足就加1这样能有效规避浮点误差。更稳妥的做法是用整数二分因为二分只需要用long long做乘法和比较完全避开浮点数。这道题给我们的提示是数学题往往有比模拟更快的解法但必须注意整数边界。笔试里很多看似需要模拟到最后一步的题实际上都可以用数学公式直接算平时多积累这类模板考场上就能省下大量时间。5. 笔试现场的时间分配与常见问题排查代码能力训练到一定程度后真正拉开差距的往往是考场上的临场策略。网易这套题集特别适合用来模拟真实笔试因为它的题型和难度分布非常接近实战。我建议你把每次刷题都当成真正的笔试来对待定好90分钟倒计时只开一个编辑器尽量模拟在线评测环境做完再统一对答案。5.1 读题和样例分析的正确顺序很多人拿到题目第一眼看到样例就直接照着样例写这是很危险的习惯。正确的读题顺序应该是先读输入输出格式再读数据范围最后读样例。输入输出格式决定了你要处理的数据结构数据范围决定了算法复杂度底线样例只是用来验证你对题意的理解是否正确。我在刷这套题时每道题都会先把题目里的关键约束圈出来比如“d最大是多少”“乘积是否需要long long”“地图长宽范围”。这些约束看似不起眼实际上决定了你该用哪种写法。比如合唱团这道题如果能力值很大且k也大乘积就必须用long long否则会溢出成错误的答案。5.2 边界条件与数据范围容易被坑的地方笔试里最常见的错误不是算法不会而是边界条件没处理好。合唱团的负数乘积、地牢逃脱的障碍物和越界、星际穿越的浮点精度这些都是活生生的例子。我总结过一套“边界自查清单”每次提交前快速过一遍数组下标是否越界循环边界是否包含最后一个元素输入是否可能为空数字是否可能为负数计算结果是否可能溢出字符串是否需要处理大小写和空格。有一次我帮人调地牢逃脱的代码对方卡了很久最后发现是起点坐标没有做合法性检查样例里起点永远是合法的但实际测试数据里起点可能是障碍物BFS直接输出-1就错了。很多题目不会在样例里给出极端情况但后台测试数据一定会包含所以自查边界是提分最快的方式。5.3 调试技巧与本地测试用例设计在线笔试环境通常不支持一步步断点调试所以你必须在本地提前准备好测试能力。最简单的做法是在本地写代码时手动构造几组边界用例。合唱团想想全是负数、全是正数、正负混合、长度为1、k等于n、d等于1这些情况。地牢逃脱想想地图只有1行1列、起点被障碍包围、移动方式包含原地踏步或重复方式。宇宙穿越想想h等于0、h正好等于某个三角数、h巨大到接近long long上限。这些用例不需要多但覆盖要全。我习惯在写完代码后先用简单用例跑通再故意构造一两个极端用例去验证。能过了这些在线评测系统里的数据大概率也能过。要是还有问题就在代码里临时加输出语句把中间变量打出来分析是哪一步的数值不对比盯着代码干瞪眼有效得多。6. 从笔试到Offer这套题暴露的能力模型与准备建议刷完这套题如果你只记住了题目答案那收益其实很有限。真正该做的是透过题目去看网易这类大厂在筛选什么样的人。校招笔试不是奥数竞赛它考的不只是你会不会某道题更是你在限时压力下能不能快速定位问题、选择合适算法、写出干净代码以及有没有足够的边界意识。从这套题来看网易特别看重基础算法的灵活应用。合唱团考的虽然是最经典的动态规划但加了负数乘积和距离约束比直接背模板高了一个层次。地牢逃脱考的是BFS但很多人会惯性用DFS说明出题人不仅考察你会不会搜索还考察你能不能根据题意选择正确算法。所以刷题时别满足于“AC了就行”要追问一句为什么这个题用这个算法换一种行不行如果数据范围变大要怎么优化。后续准备的话我建议你把这套题当成“自测卷”而不是“题库”。做完一遍之后把所有题目按类型归类统计自己在哪类题上花的时间最多、错误率最高然后针对性补强。动态规划薄弱就集中刷背包、区间、状态压缩搜索薄弱就多练BFS和DFS的变种。另外强烈推荐在纸上手写状态转移方程不要一上来就敲代码这样能把思路理得更清楚面试时被追问思路也不会慌。这套题里还有一两道综合题比如排列补全类的题难度确实比前面几道高出一截我第一次做的时候也卡了很久。对于这种题我的态度是笔试时如果时间不够果断放弃或写个暴力拿部分分但日常练习时一定要啃下来因为这类题往往是面试官深挖的素材弄懂一道带来的提升比刷十道简单题还大。说到底网易这套2017年内推笔试题集真正值得学的是题目背后的思考方式如何从无序的信息中抽象出模型如何在常数时间内完成状态转移如何在边界条件下保证正确性。这些能力不会因为题目“过时”而贬值反而是你走得更远的底座。如果你正备战校招不妨从这套题开始每天两道认真总结一个月后再回头看一定会发现自己对算法题的理解完全不一样了。
