秋招季一到算法笔试就成了很多同学最头疼的一关。我当年准备校招的时候把网易近几年能搜到的笔试真题都刷了一遍其中“网易2018校园招聘编程题真题集合”这套题虽然名字听起来像古董但它的题型结构和网易后来的笔试思路基本一脉相承性价比很高。这篇文章我就把这套题的考点拆开聊聊顺便把几个高频题型的思路和代码整理出来给准备校招笔试的同学做个参考。这套题涵盖了字符串处理、贪心、搜索、动态规划、快速幂这些笔试常客难度梯度也拉得比较开从送分题到压轴题都有。不管你是刚开始刷题的大三学生还是秋招前想突击一把的应届生按这个思路过一遍都能摸清网易笔试的出题路子。1. 网易18校招编程题一份被低估的算法练习册1.1 这份真题集到底是什么网易2018校园招聘笔试技术类岗位的在线笔试环节基本都有一组编程题牛客网上把这些题整理成了“网易2018校园招聘编程题真题集合”一共二十来道。题目描述通常都很“网易”主角不是小易就是牛牛场景大概是排队、背包、手环、跳格子这类生活化设定但外壳底下考的东西非常实在。别觉得2018年的题就过时了。算法笔试考的核心东西这十年来几乎没有变过依旧是枚举、排序、贪心、动态规划、搜索、快速幂这几板斧。网易这套题最难得的是它的题目质量高且没有太多偏题怪题每道题都能找到对应的常规算法模型非常适合作为校招笔试的训练材料。1.2 网易笔试的命题风格为什么到现在还值得刷网易的编程题风格我总结下来有三个特点。第一故事包装重但题目本质不绕。题面一长串“小易有一个数列”“牛牛有一个背包”真正要你做的事往往一两句话就能说清。这种风格对阅读能力是个考验很多同学在真实笔试时不是不会做而是被题面绕晕了找不准输入的边界和输出的要求。第二数据范围卡得很有讲究。简单题的数据范围让你暴力能过中等题暴力会超时但优化一下能过压轴题必须上正经算法。这是很典型的互联网公司笔试题型设计思路用数据范围逼你选对算法。第三覆盖的知识点非常集中。网易不考后缀自动机、不考Link-Cut-Tree这种进阶数据结构就考你在大学算法课上学过、又被各大公司反复拿来面试的那些基础算法。正因为如此这套题非常适合用来打校招笔试的地基。我当时刷这套题的时候大概花了一周。先把简单题全部独立做出来再对着中等题卡壳最后硬啃压轴题。刷完之后明显感觉再去做其他公司的笔试题至少不会出现“看到题不知道用什么算法”的尴尬。2. 热身题拆解彩色的砖块与字符串碎片2.1 彩色的砖块会读题比会写代码更重要先看一道很多人第一步就栽了的题“彩色的砖块”。题目大意是小易有一些彩色的砖块每个砖块由一个大写字母表示颜色每种颜色的砖块数量至多为2块。现在要把这些砖块排成一行要求任意两个相邻砖块颜色都不同问一共有多少种不同的排列方式。如果忽略“每种颜色的砖块数量至多为2块”这个隐藏条件这题会把你带进组合数学的坑里算半天都算不出来。但只要看到这个条件解法就非常直接统计字符串里一共有多少种不同的颜色。只有1种颜色只能排出一种排列答案是1。正好2种颜色因为每种颜色最多2块两块同色的砖只要隔开就能满足相邻不同排列方式固定为两种答案是2。超过2种颜色无论怎么排至少有一种颜色的砖块会相邻答案是0。为什么超过2种就一定不行因为每种颜色最多出现2次3种颜色一共最多6块砖但要保证相邻不同最多只能支撑两种颜色来回交替。你可以想象成给两个槽位轮着放颜色第三种颜色一旦出现必然要跟同色砖块相邻。代码量很小核心逻辑就是一句话数一数不同字符的个数。#include bits/stdc.h using namespace std; int main() { string s; cin s; setchar st; for (char c : s) st.insert(c); if (st.size() 1) cout 1 endl; else if (st.size() 2) cout 2 endl; else cout 0 endl; return 0; }这道题给我的启发是笔试的第一题往往不是考你算法而是考你读题。题面里那句“每种颜色的砖块数量至多为2块”就藏在描述中间不看仔细直接做你会以为它是一个复杂的排列组合问题白白浪费时间。2.2 字符串碎片一段一统计的经典模拟第二道热身题叫“字符串碎片”。一个由小写字母组成的字符串连续的相同字母会被视为一个“碎片”。比如aaabbaaac就可以拆成aaa、bb、aaa、c这四个碎片。题目要求输出所有碎片长度的平均值保留两位小数。这道题考察的是最基本的字符串遍历能力。你要做的就是从头到尾扫一遍字符串每遇到一个和前一个字符不同的位置就说明开启了一个新碎片。碎片总数等于“相邻不同字符的次数 1”。长度平均值就是字符串总长度除以碎片总数。#include bits/stdc.h using namespace std; int main() { string s; cin s; int seg 1; for (int i 1; i (int)s.size(); i) { if (s[i] ! s[i - 1]) seg; } printf(%.2f\n, (double)s.size() / seg); return 0; }这里有一个容易出错的细节字符串长度为1时碎片数应该是1不能初始化为0否则平均值算出来会被除以0。另一个要注意的是输出格式题目明确要求保留两位小数printf(%.2f)是最稳妥的方式用cout直接输出浮点数可能因为默认精度问题挂掉。这类“看起来特别简单”的题在真实笔试中反而是失分重灾区。因为简单很多人不写完测试数据就提交结果边界情况一爆一个准。我在刷这套题的时候养成一个习惯任何题哪怕再简单也要用最小的数据跑一遍比如长度为1的字符串、全部字符都一样的情况确认输出符合预期再提交。3. 贪心与思维题疯狂队列和数字游戏3.1 疯狂队列排序后两端交错放置热身题之后题目的难度开始上来了。“疯狂队列”是网易这道题里很有代表性的一道考的是贪心加构造不少同学在真实笔试时卡在这一题。题目是这么个意思小易老师有n个学生每个学生有一个疯狂值排成一个队列之后整个队列的疯狂值等于相邻两个学生疯狂值之差的绝对值之和。现在要你重新排列这些学生让整个队列的疯狂值最大。第一反应可能是直接暴力枚举所有排列但n稍微一大n!种排列直接把你按在地上摩擦。这题的贪心思路其实很经典想让相邻差值之和最大就要让大数和小数尽可能多地相邻。把最大的数放在中间然后用“当前最大数”和“当前最小数”交替往队列两端填充这样每个新加入的数总能碰到一个跟它差异很大的邻居。具体的构造方法是先把数组排序让相邻数值尽量挨在一起这是为了后续取数方便。接着用一个双端队列deque维护已经排好的部分。初始把最大值放进去然后按顺序交替做两件事放一个当前的最小值到其中一端再放一个当前的最大值到另一端。每次放置的时候选择能让新增相邻差值更大的那一端。参考实现思路大概长这样sort(a.begin(), a.end()); dequeint dq; dq.push_back(a[n - 1]); int left 0, right n - 2; bool putSmall true; while (left right) { if (putSmall) { dq.push_front(a[left]); left; } else { dq.push_back(a[right]); right--; } putSmall !putSmall; } // 最后计算 dq 中相邻元素绝对差之和要注意的是这个双端队列的填充顺序在不同题解里有一些细节差异因为存在“最后剩下一个数放左还是放右”的边界问题。我的经验是笔试时不要死记代码模板而是记住“大的放中间大的小的轮流往两边放”这个核心策略然后根据具体数据手动推演一遍再写代码。这类构造题手动模拟两个小用例能帮你避开不少边界坑。3.2 数字游戏用“连续覆盖区间”一次遍历“数字游戏”这道题我第一次做的时候觉得它像个脑筋急转弯后来才发现它其实是一道非常漂亮的贪心题。题目说的是小易给你n个正整数每个数最多使用一次问你最小的、不能由这些数中若干个相加得到的正整数是多少。比如给你1, 2, 4能组成的数是0, 1, 2, 3, 4, 5, 6, 7所以最小不能组成的是8。但如果是1, 2, 5能组成的数里没有4答案就是4。暴力的做法当然是把所有子集的和都算出来再从小到大找缺失的数。但n一大2的n次方个子集根本枚举不完。这题的正解是一种非常典型的贪心维护法。把数组从小到大排序。维护一个变量res表示当前已经能组成从1到res的所有整数。初始时res等于0。遍历排序后的每个数a[i]如果a[i] res 1说明把这个数加入之后能组成的连续区间可以直接从[0, res]扩展到[0, res a[i]]所以res a[i]。如果a[i] res 1说明res 1这个数再怎么加后面的数也没办法组出来了因为后面的数都比a[i]大而a[i]都已经比res 1大了答案就是res 1。为什么这个贪心是对的你可以这样理解当前手里有一堆数能拼出0到res之间所有的整数。这时来了一个新的数x。只要x res 1那么[x, x res]这一段区间和原来的[0, res]是首尾相接甚至重叠的拼起来就是一个更大的连续区间。反过来如果x res 1那么res 1这个数字就成了永远补不上的洞它必然是答案。#include bits/stdc.h using namespace std; int main() { int n; cin n; vectorlong long a(n); for (int i 0; i n; i) cin a[i]; sort(a.begin(), a.end()); long long res 0; for (int i 0; i n; i) { if (a[i] res 1) break; res a[i]; } cout res 1 endl; return 0; }这里我特意用了long long因为多个数累加之后可能超过int的范围笔试里因为这个原因挂掉的人不在少数。这道题的核心思想“连续覆盖区间”在很多题目里都能复用比如判断一堆硬币能凑出哪些金额本质都是同一个模型。4. 中等题牛牛的背包问题与DFS/折半枚举4.1 背包问题为什么不能直接DP“牛牛的背包问题”是这套题里我第一次见到时有点发怵的一道题。题面是牛牛有n个零食每个零食有一个体积现在有一个容量为w的背包问你一共有多少种装法空背包也算一种装法。n最大可以到30w可以到2的31次方量级。看到“背包”两个字很多人的第一反应是动态规划。但仔细看数据范围这个背包容量w巨大没法开dp[w]这么大的数组。而且这题要求的是“方案总数”不是“最大价值”状态转移也不太好写。如果你熟悉经典的0-1背包你会发现常规DP在这里完全不适用。n等于30最终答案最多是2的30次方种方案这个数本身还在long long范围内但w太大导致DP数组根本开不出来。所以这道题考察的是另一条路搜索。但要命的是30个物品直接暴力枚举2的30次方种选法大约是10亿次操作在笔试那种环境下绝对会超时。所以必须做优化。4.2 折半枚举把2^30拆成两个2^15折半枚举meet in the middle是处理这种“n不太大但2的n次方恰好卡在超时边缘”的经典套路。思路很简单把30个零食分成两组每组15个分别枚举出所有可能的组合体积。15个物品的组合数是2的15次方也就是32768个非常小。枚举完两组之后把其中一组排序然后遍历另一组的每个体积二分查找有多少个能放进去。#include bits/stdc.h using namespace std; int n; long long W; vectorlong long w; void dfs(int idx, int end, long long sum, vectorlong long v) { if (idx end) { v.push_back(sum); return; } dfs(idx 1, end, sum, v); if (sum w[idx] W) dfs(idx 1, end, sum w[idx], v); } int main() { cin n W; w.resize(n); for (int i 0; i n; i) cin w[i]; vectorlong long left, right; dfs(0, n / 2 - 1, 0, left); dfs(n / 2, n - 1, 0, right); sort(right.begin(), right.end()); long long ans 0; for (long long x : left) { ans upper_bound(right.begin(), right.end(), W - x) - right.begin(); } cout ans endl; return 0; }这样一拆单个递归最多只有32768个叶子节点后半段排序加二分查找的复杂度也非常低完全可以在笔试时间内跑完。这道题给我一个很重要的教训看到n等于20到30这个范围不要急着写DFS暴力搜索而是优先想一想折半枚举。2的20次方大约是100万勉强能跑2的30次方是10亿基本必挂。一旦n超过25直接裸DFS就可能超时折半枚举几乎是标准答案。这里还有一个搜索细节递归枚举的时候只要当前累加和已经超过背包容量w就直接剪枝不继续往下走。这个剪枝在数据比较均匀的时候能砍掉大量无效分支。如果零食体积有很多很小的数剪枝效果不明显折半枚举的复杂度优势就体现出来了。5. 压轴题魔力手环与矩阵快速幂套路5.1 从题意到线性变换这套题里真正有分量的压轴题我觉得是“魔力手环”。题目大意是有一个长度为n的数列每一次操作会把每个位置变成自己与下一个位置的和最后一个位置和第一个位置相加。把一个长度为3的数列[1, 2, 3]操作一次会变成[12, 23, 31] [3, 5, 4]。现在给你初始数列和一个操作次数kk可以大到10的9次方问操作k次之后的数列长什么样。看到k高达10的9次方直觉就告诉你不能真的一步一步模拟。这类“重复进行同一种线性操作”的问题标准的处理手法是找规律或用矩阵快速幂。先看操作本身。每个新位置的值都是旧数列中两个位置的线性组合。这意味着整个操作可以用一个矩阵乘法来表示new old * M其中M是一个n阶矩阵。对长度为n的数列第i行第i列和第i行第(i1)%n列是1其余是0。这样操作k次就等价于乘k次M也就是计算初始向量 * M^k。快速幂把k次乘法压缩到log(k)次10的9次方也就30多次矩阵乘法。但这里有个现实问题n最大可以到5050乘50的矩阵乘法是2500次乘法再乘上log(k)级别的运算次数朴素写法在复杂度上勉强能接受但常数不小。实际笔试时如果你看到n特别大还有更优的做法由于M是一个循环矩阵可以只用第一行来表示整个矩阵矩阵乘法也就能优化成O(n^2)的卷积形式。不过这个优化的代码量比较大考场上时间有限我通常建议先写朴素矩阵快速幂拿分数据过了就过过不了再优化。5.2 什么时候该上矩阵快速幂很多人对矩阵快速幂有畏难情绪觉得矩阵乘法这么抽象考场上肯定写不出来。但说实话一个通用的矩阵快速幂模板并没有那么难背下来之后遇到“k次变换”类问题能立刻套上。给一个比较通用的矩阵乘法参考模板这里不针对魔力手环做特殊优化struct Mat { int n; vectorvectorlong long a; Mat(int n) : n(n), a(n, vectorlong long(n)) {} Mat operator*(const Mat o) const { Mat res(n); for (int i 0; i n; i) { for (int k 0; k n; k) { if (a[i][k] 0) continue; for (int j 0; j n; j) { res.a[i][j] a[i][k] * o.a[k][j]; } } } return res; } };要注意的是实际题目如果要求结果取模需要在乘法里加上取模操作。如果题目数据量大到long long都可能溢出甚至要考虑大数处理。魔力手环这道题当年在牛客上有个很邪门的坑因为中间结果增长特别快不取模的话直接爆long long。所以写这类题之前一定要仔细看题面里有没有“对某个数取模”的说明。判断一道题该不该用矩阵快速幂我一般看两个信号第一操作次数k特别大大到模拟明显不现实第二每次操作是“线性变换”也就是新状态的每个值都是旧状态的值的加权和。这两个条件同时满足基本就可以往矩阵快速幂的方向想了。比如斐波那契数列的O(log n)求法本质也是这个套路。6. 笔试现场的节奏控制与避坑清单6.1 拿到题后的标准动作刷完这套网易真题我最大的收获不是会做这几道题而是形成了一套笔试的固定节奏。很多同学笔试翻车不是因为题目难而是因为节奏乱前面的题磨太久后面的题没时间看。我自己的习惯是开考之后先花两分钟把所有编程题都扫一遍按难度和心理预期排个序。先把最有把握的题做掉确保送分题一分不丢再做那种思路清晰但代码量大的题最后留时间啃压轴题。中等题卡壳超过二十分钟直接标记跳过千万别跟一道题死磕。笔试是限时游戏时间本身就是最贵的资源。看到数据范围脑子里要立刻反应出大概的算法方向。这是刷题刷出来的直觉数据范围可接受的算法复杂度常见算法方向n 10O(n!) 或 O(2^n * n)全排列、状态压缩n 20O(2^n)状态压缩枚举、DFSn 30O(2^(n/2) * n)折半枚举、剪枝搜索n 1000O(n^2)双重循环DP、Floydn 100000O(n log n)排序、二分、线段树k 10^9O(log k)快速幂、矩阵快速幂、倍增这个表不是万能的但能帮你快速锁定一个大概范围避免写出一个注定超时的暴力算法。6.2 常见错误与排查速查表我在刷这套题和后来参加各种笔试时反复踩过一些坑整理成一张速查表每次提交前对照检查一遍能省下不少罚时。现象原因解决办法本地跑的好好的提交全错没有处理多组输入或题目要求循环读入用while (cin n)包裹主逻辑答案变成负数或莫名其妙的大数int溢出涉及累加、乘法、DP状态值一律用 long long数组越界下标从1开始时忘记把数组开大多开一个或两个位置初始化好边界输出格式不对浮点数保留位数不对或多了空格严格按照题面要求用 printf 精确控制超时暴力枚举复杂度过高对照数据范围换算法必要时折半枚举或快速幂边界数据挂掉没考虑长度为0/1、全相等、n1等边界每次提交前跑最小数据和极端数据还有一个很实用的小技巧在本地调试时故意构造一些“恶心”的输入比如n取最大值、所有数都相等、所有数都很大看看程序会不会超时或者溢出。这套网易题里很多题目的坑都藏在边界条件里比如字符串碎片的长度为1、数字游戏里所有数都满足条件、背包问题里n1。把这些边界都测一遍提交的把握会大很多。刷题这件事没有捷径但一定有方法。网易2018这套真题题目数量不算多但每一道都值得反复咀嚼。我当时刷完一遍之后又把做错的题隔了两周重新做了一遍对比两次的思路差异进步非常明显。如果你现在正在准备校招笔试与其漫无目的地刷一堆重复题型不如先拿这套题试试水把里面的套路吃透再往外扩展。