每年的校招季，总有几套题会被反复拿出来讨论，网易2016研发工程师的编程题就是其中之一。我身边不少后来进了大厂的朋友，当年都把这份卷子当作练手标配。这轮题目的特点很鲜明：不玩偏题怪题，基础知识覆盖扎实，链表、字符串、动态规划、贪心都有涉及，难度梯度拉得比较开，从能快速AC的签到题到需要静下心来推状态转移方程的压轴题都有。无论你是准备春招秋招的在校生，还是想检验一下自己基础功底的从业者，这套题都值得认真做一遍。
我这次就把这套题里最具代表性的几类问题拆开揉碎了讲，从出题人的视角分析每道题在考什么，再给出可以直接落地的解法和代码。重点不是说答案，而是把“拿到一道题之后怎么思考”这条链路完整走一遍。
1. 整体设计思路与题目定位解析
1.1 2016年前后校招笔试的出题风格
聊这套题之前，得先还原一下当年的笔试环境。2016年的时候，线上笔试系统已经比较成熟了，网易的校招笔试基本都是在线做题，用自己电脑写代码然后提交。这种形式决定了出题上的几个倾向。
第一，题目不能太依赖本地调试环境，所以输入输出格式一般比较常规，不像现在有些公司用ACM赛制搞特别复杂的输入解析。第二，题目数量不会太多，大概4到6道编程题，给两小时左右，这样既覆盖了主要考点，又不至于让人完全写不完。第三，也是最重要的，题目里不会出现特别偏门的算法，重点还是放在基础数据结构和经典算法模型上。
网易2016这轮题基本就是这个思路的典型代表。我当时做完之后的感觉是：每道题你都知道它想考什么，但能不能在规定时间内写对，就是另一回事了。比如链表类的题，知道要逆序不难，难的是指针操作的边界处理；动态规划的题，能看出来是DP不难，难的是状态定义和转移方程的细节。
1.2 考点分布与难度梯度拆解
从考点分布来看，这套题覆盖的知识点大致可以分成四个层次：
- 基础数据结构操作：链表逆序、链表判环、字符串处理等，属于“必须拿分”的题目，一般放在前面
- 经典算法模型：动态规划、贪心策略，属于“区分度”题目，中等偏上难度
- 数学与逻辑思维：数学变形、规律推导，属于“拉分题”，考验思维的灵活性
- 代码实现能力：边界处理、复杂度优化，这个不单独成题，但每道题都在考
从实战角度看，前两类题目是重点，因为这些题目即便是在系统设计、架构面试里也可能以白板题的形式再次出现。举个例子，链表的逆序和判环，我在后来的技术面里就不止一次被要求手写。所以别觉得校招题就是刷完就扔，很多基本功是长期的。
2. 高频考点深度拆解：链表与字符串操作
2.1 链表逆序的两种写法和一个关键细节
链表逆序应该说是面试里最经典的题目之一，网易2016里就有一道和链表操作相关的题。这道题本身不难，但非常能看出一个候选人代码基本功扎不扎实，核心考察点是引用操作和边界条件。
迭代写法是最直观的。我们需要维护三个指针，前驱节点prev、当前节点cur、后继节点next。每次迭代做四件事：先保存cur的下一个节点，再把cur的next指向前驱，然后把prev移动到cur，最后把cur移动到之前保存的next。循环终止条件是cur为空，此时prev就是新的头节点。
struct ListNode { int val; ListNode *next; ListNode(int x) : val(x), next(nullptr) {} }; ListNode* reverseList(ListNode* head) { ListNode* prev = nullptr; ListNode* cur = head; while (cur) { ListNode* next = cur->next; cur->next = prev; prev = cur; cur = next; } return prev; }递归写法也值得掌握，尤其面试时有时候会要求你用递归实现一遍。递归的思路是把“反转整个链表”拆成“反转除去第一个节点后的子链表，再把原第一个节点接到子链表末尾”。注意递归的终止条件是当前节点为空或者当前节点的下一个节点为空，直接返回当前节点。
ListNode* reverseListRecursive(ListNode* head) { if (!head || !head->next) return head; ListNode* newHead = reverseListRecursive(head->next); head->next->next = head; head->next = nullptr; return newHead; }这里有一个关键的细节，也是我自己当年踩过的坑：递归写法里，head->next->next = head 这一步必须在 head->next = nullptr 之前。如果你的顺序写反了，先把head的next置空，后面的节点就找不到了，整个链表就断了。这个顺序问题在纸上推演的时候很容易忽略，最好自己在脑子里过一遍递归栈的展开过程。
2.2 链表判环的数学原理
另一类链表高频题是判断链表是否有环，网易2016里也有涉及。判断有环的标准解法是快慢指针，一个每次走一步，一个每次走两步。如果链表里有环，两个指针最终一定会相遇。
很多同学背了这个解法，但不知道为什么快慢指针一定能相遇。这里简单推一下：假设链表无环部分的长度是a，环的长度是b。当慢指针进入环的时候，快指针已经在环里了，设此时快指针距离慢指针还有k步（按环内顺时针方向）。因为快指针每次比慢指针多走一步，所以经过k步之后，快指针就会追上慢指针。也就是说，在最坏情况下，需要走的步数不会超过环的长度b，所以时间复杂度是O(a+b)，也就是O(n)。
快慢指针这个思路本身还可以延伸出不少变体，比如找到环的入口节点。做法是相遇之后，把一个指针移回链表头，两个指针每次都走一步，再次相遇的位置就是环的入口。这个结论的推导同样基于上面的数学关系，面试时可以顺手写出来，会是个不错的加分项。
2.3 字符串处理：循环移位与第一个只出现一次的字符
字符串相关的题目在2016网易研发工程师编程题里也占了不小的比重。这类题通常不考太复杂的算法，重点在于代码的简洁性和对常用技巧的掌握。
循环移位判断是一个非常典型的问题：给定两个字符串s1和s2，判断s2是否由s1循环移位得到。比如"abcde"循环移位可以得到"bcdea"、"cdeab"等。最巧妙的解法是把s1拼接成s1+s1，然后判断s2是不是这个新串的子串。这个结论背后的逻辑很简单：循环移位本质上是把一个字符串从某个位置切开，然后交换两段的前后顺序，而s1+s1这个串里包含了所有可能的切分结果。
另一个经典的字符串题是找第一个只出现一次的字符。直观做法是维护一个哈希表，第一遍遍历统计每个字符出现的次数，第二遍遍历找到第一个出现次数为1的字符。在C++里可以用unordered_map，但这道题有个更轻量的做法，因为字符范围有限（ASCII字符集256个），可以直接用一个大小为256的数组来计数，这样既避免了哈希表的开销，代码也更简洁。
char firstUniqChar(const string& s) { int count[256] = {0}; for (char c : s) count[(unsigned char)c]++; for (char c : s) { if (count[(unsigned char)c] == 1) return c; } return '\0'; }这里唯一需要注意的就是unsigned char的强转，因为char默认可能是有符号的，如果用负数下标访问数组会出问题。这个细节在实际笔试中可能会被测试用例打穿，我就吃过一次亏。
3. 进阶考点实战：动态规划与贪心策略
3.1 最长递增子序列的两种解法
动态规划是网易2016研发工程师编程题里区分度的主要来源，也是最值得花时间准备的部分。我先从最长递增子序列（LIS）说起，因为它的状态转移思路非常经典，而且有两种差距比较大的解法。
第一种是基础的O(n²)动态规划。定义dp[i]表示以第i个元素结尾的最长递增子序列长度。状态转移的时候，遍历i之前的所有元素j，如果nums[j] < nums[i]，就用dp[j] + 1去尝试更新dp[i]。
int lengthOfLIS(vector<int>& nums) { int n = nums.size(); vector<int> dp(n, 1); int ans = 1; for (int i = 1; i < n; i++) { for (int j = 0; j < i; j++) { if (nums[j] < nums[i]) { dp[i] = max(dp[i], dp[j] + 1); } } ans = max(ans, dp[i]); } return ans; }第二种是贪心加二分的O(n log n)解法。维护一个数组tails，tails[k]表示长度为k+1的递增子序列中，最小的末尾元素值。遍历原数组时，在tails里用二分查找找到第一个大于等于当前元素的位置，替换掉它；如果当前元素比tails所有元素都大，就追加到末尾。最终tails的长度就是LIS的长度。
这个解法的巧妙之处在于，tails数组本身不一定是真正的LIS序列，但它维护了“相同长度下的最小末尾元素”这个关键信息。这种贪心思路在面试里很受考官喜欢，因为它体现了对问题的深入理解。
3.2 网易经典DP题“合唱团”的完整推演
网易2016年前后笔试中出现过一道“合唱团”问题，这道题后来在各大论坛上被反复讨论，基本成了网易校招DP题的代名词。题目大意是有n个学生站成一排，每个学生有一个能力值，要求从这n个学生中选出k个学生，使得这k个学生的能力值乘积最大，同时要求相邻两个被选中的学生编号之差的绝对值不超过d。
这个题的难点在于乘积可能为负，而且能力值也可能是负数。如果只维护最大值，遇到两个负数相乘的情况就可能出错。所以需要同时维护最大值和最小值两个状态的转移。
具体来说，定义两个二维数组dpMax[i][j]和dpMin[i][j]，分别表示以第i个学生作为最后一个被选中的学生、已经选了j个学生时的最大乘积和最小乘积。状态转移时，从前一个被选中的学生p（满足i-p不超过d）转移过来：
dpMax[i][j] = max(dpMax[i][j], max(dpMax[p][j-1] * val[i], dpMin[p][j-1] * val[i])); dpMin[i][j] = min(dpMin[i][j], min(dpMax[p][j-1] * val[i], dpMin[p][j-1] * val[i]));初始条件是j=1时，dpMax[i][1]和dpMin[i][1]都等于val[i]。最终答案是所有dpMax[i][k]中的最大值。
这道题之所以经典，是因为它把DP中非常容易被忽略的“负负得正”情况做成了核心考点。我见过很多人在笔试时只维护了最大值，最后死活过不了隐藏样例。所以在这里给一个建议：只要题目涉及乘法、且数据范围允许负数，就要立刻想到同时维护最大最小值。
3.3 区间调度类贪心问题的两个视角
贪心策略在2016年的题目里也有体现，比较典型的是区间问题。区间调度类问题的核心是排序的基准选择，我以最经典的不重叠区间问题为例，展开讲讲。
给定一系列区间，问最多能选出多少个互不重叠的区间。常用的贪心策略是按区间右端点从小到大排序，然后依次选择右端点最小且与已选区间不冲突的区间。为什么按右端点排序而不是按左端点或者区间长度排序？因为右端点越小，给后续区间留出的空间就越大，这在直觉上是“最优的未来扩展性”。
反过来，如果是求“最少需要移除多少区间才能让剩余区间互不重叠”，它的答案就等于总区间数减去最多互不重叠区间数。这个转化思路在面试中也很常用。
这道题想明白之后，你会发现贪心算法其实是很多题目的“第一直觉”经过严谨验证后的结果。面试时如果你能把“为什么这样贪心是正确的”用反证法讲清楚，那比背一百道题的模板都有用。
4. 笔试现场的代码实现与调试心得
4.1 从读题到AC的标准工作流
备考阶段刷题是一回事，真正上了笔试考场又是另一回事。我总结了一套自己用起来比较顺的做题流程，分享出来可以参考。
拿到题目之后，第一步不是马上写代码，而是先花两到三分钟静下心来读题，把输入输出格式、数据范围、边界条件这几个关键信息圈出来。尤其是数据范围，它直接决定了你的算法需要什么复杂度。举个例子，如果n的范围是10^5，O(n²)大概率超时，这时候就得想O(n log n)甚至O(n)的解法；如果n只有1000，那暴力枚举很多时候就够了。
第二步是先在草稿纸上或者脑子里过一遍用例。手工构造一个最简单的输入，把预期输出写出来，再构造一个包含边界条件的输入，比如空数组、只有一个元素、全是负数、最大值，然后跟着自己的思路跑一遍，看看输出是否符合预期。这个步骤能挡掉至少三成的低级错误。
第三步才是写代码。写的过程中注意三个点：循环边界、下标偏移、空指针判断。我的习惯是先写主体逻辑，最后再统一补边界条件的处理，这样思路不容易被打断。写完代码之后，一定不要急着提交，先用自己构造的测试用例在本地跑一遍，确认输出正确了再提交。
4.2 手写代码时最容易翻车的三个细节
我在帮别人review代码以及复盘自己笔试时，发现有几个细节是反复翻车的高发区，这里单独拎出来说一下。
第一个是整型溢出。很多题目的中间结果会超过int的范围，尤其是在做乘法或累加的时候。2016年的题目里，能力值的乘积就可能非常大。解决方案是只要涉及相乘或者求和，就优先考虑用long long，甚至在某些情况下用unsigned long long。虽然多写几个字节不费事，但能省掉很多不必要的排查时间。
第二个是动态规划数组的初始化。不同的初始化值直接决定了状态转移是否正确。比如求最小值的时候初始化为一个大数，求最大值的时候初始化为一个负数，这些都是老生常谈，但真的很容易写错。我的习惯是初始化时从题目数据范围倒推，而不是随手写一个INT_MAX或者INT_MIN了事。
第三个是二分查找的边界写法。二分查找看似简单，但死循环和越界是高频问题。我自己比较习惯的写法是闭区间写法，循环条件用left <= right，更新时用left = mid + 1和right = mid - 1，这样能避免很多边界上的坑。
4.3 推荐使用的代码模板
准备笔试的时候，可以提前准备几个常用算法的代码模板，到了考场直接默写，能节省不少时间。我常用的模板包括二分查找、链表操作、二叉树遍历、回溯框架这几个大类。
这里给一个我常用的二分查找框架，对绝大多数变体都适用：
int binarySearch(vector<int>& nums, int target) { int left = 0, right = nums.size() - 1; while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] == target) return mid; else if (nums[mid] < target) left = mid + 1; else right = mid - 1; } return -1; }mid的计算推荐用left + (right - left) / 2，而不是(left + right) / 2，这样可以防止left和right都很大时的整型溢出。虽然现代编译器里int溢出在竞赛环境下未必会暴露，但在生产代码里这是一个好习惯。
5. 高频问题与备考实战建议
5.1 常见错误速查表
我把平时刷题和笔试中遇到的典型问题整理成一个速查表，每一条都是亲手踩过的坑，不是从书上抄来的理论。
| 问题类型 | 典型表现 | 排查思路 |
|---|---|---|
| 数组越界 | 本地运行崩溃，线上报Runtime Error | 检查循环变量边界，尤其是i+1、i-1、j+1这类下标偏移 |
| 死循环 | 程序一直不退出，超时 | 检查while循环中指针/索引是否一定会更新，考虑快慢指针相遇条件 |
| 输出格式 | Wrong Answer | 检查是否多输出了空格、换行，是否漏了#Case 1这类前缀 |
| 类型溢出 | 结果异常，大数据量时出错 | 把所有涉及乘法的中间量改成long long |
| 逻辑遗漏 | 只能过部分样例 | 思考负数、零、空输入、单元素输入是否都覆盖了 |
| 指针丢失 | 链表操作结果错误 | 画图模拟指针变化，尤其注意临时节点的保存 |
这张表其实不只是针对网易2016这套题，其他任何笔试都适用。每次做完题复盘的时候，把自己犯错的原因归类到对应行，刷几套题之后你就会发现自己有一两个固定的“弱点模式”，针对性地去练比盲目刷题有效得多。
5.2 从一套题延伸出的备考知识树
网易2016这套题其实是一棵很好的知识树主干，以它为起点可以延伸出大量的关联考点。链表逆序可以延伸出K个一组反转链表、回文链表判断；链表判环可以延伸出寻找环入口、求环长度；LIS可以延伸出最长公共子序列、最长回文子序列；合唱团这道DP题可以延伸出状态压缩DP、树形DP。
我建议备考时不要只盯着题解看，而是每做完一道题就做一次横向扩展：这道题的数据结构还能支持什么操作？这道题的DP状态定义还能迁移到哪些问题上？这样坚持两周，覆盖面会明显上一个台阶。
提示：刷题的时候给自己定个规矩，每道题搞懂之后花三分钟在笔记本上写一句话总结。别小看这个动作，它能在你复习的时候省下很多时间。
5.3 笔试时的时间分配建议
网易这种校招笔试一般两小时左右、4到6道题。我的建议是不要把时间平均分配，而是先把所有题目快速看一遍，把题目按难度和熟悉度分成三档：马上能写的、有点思路但需要推一推的、完全没思路的。
第一档题直接写，争取拿满分。第二档题给自己设置一个时间上限，比如30分钟，如果到时间了还是一点头绪都没有，先跳过，去做后面的题积累分数。第三档题留在最后，就算只能写个暴力解法，也要把代码框填满，因为很多时候暴力解法能帮你拿到部分测试用例的分数。
压轴题如果已经明确是DP，而且你状态定义也推得差不多了，建议先写主逻辑，把核心转移方程实现出来，再回头补初始化和边界。因为阅卷系统通常是按测试用例给分的，主逻辑写对就能覆盖不少用例。
写在最后
网易2016研发工程师编程题这套题对我的意义，不只是一次笔试的练兵，更像是一面镜子。它让我看清了自己在数据结构和算法上的薄弱环节，也让我意识到，面试考查的其实不是“你背了多少题”，而是“你在面对一个没见过的问题时，能不能冷静地拆解、建模、实现、验证”。我自己在实际操作中的体会是，刷题不追求数量，追求的是每道题都能讲到“为什么”的层面。哪怕一天只吃透一道题，坚持三个月，效果一定比一天刷十道题然后转头就忘好得多。
最后再分享一个小技巧：做这套题的时候，可以给自己模拟一下真实的笔试环境，开一个计时器，关闭编译器自动补全，甚至把手机关机放到另一个房间。这种略带紧张感的练习，比漫无目的地刷题更能锻炼临场状态。如果你能把这套题的每个考点都吃透，我相信你面对大多数公司的研发岗笔试，都能多一分底气。
