网易秋招笔试编程题实战解析：字符串、滑动窗口与动态规划

每年秋招，网易的笔试一直是互联网大厂里比较有代表性的那一档。有人觉得它比BAT简单，有人连续两次挂在同一类题上，还有人考完才发现自己连样例都没读懂。我翻完2019秋季校园招聘编程题真题集合，把那些容易踩坑、容易丢分、复盘后才发现“原来这么考”的细节整理了一遍，算是一份针对网易笔试的实战攻略。

网易2019秋招编程题有一个非常明显的特点：题目都会套一层故事背景。主角无非是小易、石板、能量站、数组游戏，但脱掉外壳之后，考查的还是那几类经典算法——字符串处理、数组枚举、动态规划、图论搜索。真正的难点不是算法本身，而是你能不能快速把故事翻译成数学模型，然后选择正确的复杂度优化手段。

这篇文章不打算按“真题答案合集”的方式来写，而是挑了三类高频且具备代表性的题目，完整还原从审题、推导到代码实现和边界测试的过程。顺便把笔试环境里那些“非算法因素”的丢分点一并说清楚。无论你是第一次参加校招笔试，还是已经刷了不少题想查漏补缺，这篇应该都能给你一些实际帮助。

1. 网易2019秋招笔试的基调：题型结构与命题口味

先说整体感受。网易的校招笔试通常一场4道编程题，时间在120分钟上下，考试平台主要是牛客网。平台本身支持C/C++、Java、Python等主流语言，判题方式按测试点给分，部分通过也有分数。这个机制很关键，意味着你完全不需要每道题都AC，拿部分分也能进面试。

四道题有一个明显的难度阶梯。第一题一般是字符串或数组的简单模拟，考的是代码基本功，20分钟内应该解决。第二题开始需要一点算法思维，常见的是枚举优化、二分、贪心。第三题往往是动态规划或者数据结构优化，这一题基本决定了你能不能拿到这轮笔试的高分。第四题属于拉开差距的题，有时会涉及图论、状态压缩、数论等相对冷门的方向，大多数人的策略是拿部分分。

网易命题口味有四个高频标签：字符串、数组、动态规划、图论。字符串题喜欢玩“压缩”“展开”“反转”“匹配”；数组题偏爱“区间”“差值”“单调性”；动态规划题则常考“状态设计”和“优化”，不会出太裸的模板题；图论题一般不会超过最短路径和并查集的范畴。

这里顺便给一个我的备考优先序：先把滑动窗口、双指针、单调栈/队列做熟，再搞定LIS和背包类DP的优化写法，最后补一补并查集和最短路径模板。把这些吃透，网易笔试至少覆盖80%的考点。

网易的题还有一个隐藏特点：数据范围给得很直白，但不会在题目里提醒你“这个得用O(n log n)”。你需要自己从数据范围反推复杂度。看到n≤10^5，基本就告别O(n^2)了；看到K可以达到10^18，就要考虑long long和逆推。

2. 最容易丢分的不是算法，是输入输出与边界条件

很多同学刷LeetCode很顺，一到牛客网笔试就挂，问题往往出在输入输出上。LeetCode把函数签名和输入输出都封装好了，而牛客网是从标准输入自己读、自己解析。题目说“多组测试数据”，就有人只会处理一组；题目说“字符串可能包含空格”，就有人用cin直接读导致截断。这些不是算法问题，但丢分丢得非常冤枉。

先记住一个原则：把输入输出当成题目的一部分来做。拿到题先看输入格式，再设计算法。

字符串读入的坑我见得太多了。如果一行字符串里可能包含空格，要用getline。但getline之前如果还用cin读过一个整数，那一行的回车会被读进去，导致第一个字符串是空的。解决办法是在cin之后加一句cin.ignore()。这个细节在牛客笔试里碰到的概率极高。

数字范围也是一个隐蔽的丢分点。题目说“答案对10^9+7取模”，你写int运算，中间过程直接溢出。还有坐标、距离、累计长度这些变量，题目给了10^5规模，但累计值可能到10^10，不用long long就是错。这一条看起来简单，但每年都有人栽。

再说递归。某些题用DFS或分治会比较自然，但深度达到10^5甚至更高时，C++默认栈会爆。必要时改成显式栈的迭代写法，或者在牛客支持的情况下把递归深度限制调大。正常来说，笔试题目不怎么追求这种极端递归，但图论题BFS通常比DFS更稳，也更不容易栈溢出。

边界条件部分，我的习惯是写出代码后立刻造三组测试样例：最小输入（n=1或数组为空）、最大输入、带极端值的输入。比如第三题答案可能是0、可能是整个数组长度，这些情况的if分支有没有写全，一测就知道。这个习惯虽然朴实，但能救回不少本该拿到的分。

关于部分分策略也多说一句：如果一道题只想到了暴力解法，别犹豫，直接写暴力提交，先拿一部分测试点。牛客网按测试点给分，暴力能过30%~60%，白赚的分不要白不要。等暴力得分拿到手之后，再回头优化。

3. 真题精讲：字符串压缩展开中的第K个字符

这道题是典型的“第一题难度，但有第二题陷阱”的代表。题目背景大概是：压缩字符串形如“a3b2c4”，表示原字符串是“aaabbcccc”，即每个字符后面跟一个数字，表示这个字符连续重复了几次。现在给定一个整数K，求展开后的字符串中第K个字符是什么。

看起来很简单对不对？直接展开成完整字符串，然后按下标访问。但题目会给一个非常关键的限制：展开后的总长度可能超过10^18。这就意味着你没有办法真正把字符串展开到内存里。凡是能存得下的，都是大数据结构题；存不下的，才是考察思维的地方。

正确的思路是跳过展开过程，分段统计长度。遍历压缩串的每个字符，记住当前字符以及它重复的次数，然后把当前已展开的总长度累加上这个次数。当累计长度第一次大于等于K时，当前这个字符就是答案，直接返回。

为什么这样是对的？因为展开串本质上就是一段一段相同字符的拼接。你只需要知道每一段的长度，就能判断第K个字符落在哪一段里，根本不需要真的构造出这一段。

这里实现时有一个细节特别容易写错：数字可能是多位数。压缩串可能写成“a10b2”，意思是a重复10次，然后b重复2次，展开串长度是12。如果你只按单个字符解析数字，“10”就会解析成“1”和“0”，结果完全不对。正确写法是循环读取连续的数字字符，累乘10叠加。

样例验证一下：压缩串“a10b2”，展开串是“aaaaaaaaaabb”，共12个字符。K=11，前10个都是a，第11个是b。如果用我们分段统计的逻辑，扫描到a时累计长度+=10，此时累计长度10仍然小于K=11，继续扫描；扫描到b时累计长度+=2变成12，>=11，返回b。结果正确。

代码实现：

#include <bits/stdc++.h> using namespace std; char findKthChar(const string& s, long long K) { long long cnt = 0; for (int i = 0; i < (int)s.size(); i++) { char c = s[i++]; // 字符 long long num = 0; while (i < (int)s.size() && isdigit(s[i])) { num = num * 10 + (s[i] - '0'); i++; } i--; // 回退一位，for循环本身会++i if (cnt + num >= K) return c; cnt += num; } return '?'; } int main() { string s; long long K; cin >> s >> K; cout << findKthChar(s, K) << endl; return 0; }

这个代码里有几个容易出错的地方：

• i++之后，for循环末尾还会再i++一次，所以用i--回退，避免跳过一个数字字符。
• 判断条件是cnt + num >= K而不是> K。当K正好落在当前字符段的最后一个位置时，==也应该命中。
• num用long long接收，因为重复次数可能很大。
• cnt初始为0，代表已经展开的长度。先判断后累加，保证当前字符段被检查。

还有一种变形是问“第K个字符是哪个字符的重复次数”，那就在返回时同时带上段信息。核心思路完全一样。

这道题想通之后，字符串类的“按段统计”相关题基本都能用同一套思路，比如“压缩字符串中某个区间的数字和”“从压缩串里还原第l到r个字符”等。本质都是在处理大长度不可展开场景下的分段映射。

4. 真题精讲：差值不超过K的最长连续子数组

来看一道更典型的网易风格题。题目大概意思是：给定一个长度为n的整数数组a和一个整数K，找到最长的连续子数组，使得这个子数组里的最大值和最小值的差不超过K，输出这个最长长度。数据范围n≤10^5，a[i]是32位整数。

如果对复杂度不敏感，第一反应是枚举所有子数组，O(n^2)检查每个子数组的最大最小差，总复杂度O(n^3)。在n=10^5时这简直不可行。即使优化成固定左端点、移动右端点时动态维护最大最小值，也只是把单次检查变O(1)，枚举子数组本身还是O(n^2)。依然会超时。

这道题的关键是观察到一个单调性：当左端点固定时，右端点向右移动，窗口内的最大值-最小值只会不变或变大，不会变小。也就是说，某个子数组合法，那么它内部的任意子数组也合法；某个子数组不合法，右端再扩大只会更不合法。这给了滑动窗口一个明确的收缩条件：每当最大减最小超过K，我们就让左端点向右移动，直到重新合法。

滑动窗口本身不难想，难点在于如何O(1)获取当前窗口的最大值和最小值。这里需要引入两个单调队列，一个维护窗口内最大值的候选序列，一个维护最小值的候选序列。

单调队列维护极值的原理可以这样理解：假设我们在一个队列里维护窗口内元素的下标，同时保证下标对应的元素值从队头到队尾是单调递减的。那么队头元素就是当前窗口的最大值。新元素入队前，从队尾弹出所有小于等于它的元素，因为它们已经不可能在后续充当最大值了——新元素下标更大且值更大，老元素在窗口左移时会更早失效，所以可以直接淘汰。

最小值队列同理，只是单调性相反，从队尾弹出所有大于等于新元素的元素。

用生活类比来解释：窗口就像一队人在排队打饭，你关心这队里最高的人是谁，以及他什么时候走。单调队列不是把所有人都记下来，而是只记“有机会成为最高的人”。如果你新来的比队尾那个高，那后面在你排队的时候就不会再看到队尾那位，直接把他踢掉就行。

这个算法整体是O(n)的，因为每个下标最多入队一次、出队一次，左右指针只前进不后退，时间复杂度线性，空间复杂度O(n)。在n=10^5时完全没有压力。

C++完整实现：

#include <bits/stdc++.h> using namespace std; int main() { int n, K; cin >> n >> K; vector<int> a(n); for (int i = 0; i < n; i++) cin >> a[i]; deque<int> qmax, qmin; // 存放下标 int left = 0, ans = 0; for (int right = 0; right < n; right++) { while (!qmax.empty() && a[qmax.back()] <= a[right]) qmax.pop_back(); qmax.push_back(right); while (!qmin.empty() && a[qmin.back()] >= a[right]) qmin.pop_back(); qmin.push_back(right); while (a[qmax.front()] - a[qmin.front()] > K) { left++; while (!qmax.empty() && qmax.front() < left) qmax.pop_front(); while (!qmin.empty() && qmin.front() < left) qmin.pop_front(); } ans = max(ans, right - left + 1); } cout << ans << endl; return 0; }

几个容易写错的地方，逐个说：

• 队列里存的是下标，不是值。因为窗口左移时要判断队头元素是否已经滑出窗口，只有下标才能做这个判断。
• 弹出队尾元素时，最大值队列用的是<=。意思是新元素等于队尾值时，弹出队尾。为什么要这样做？因为新元素下标更大，在窗口左移时更晚失效，用它替代老元素更有利于维持窗口长度。最小值队列同理用>=。
• 收缩左边界时要注意，单调队列的队头可能已经不在窗口内，所以要循环弹出所有下标小于left的队头。这一步漏掉的后果是窗口内最大值计算错误。
• 收缩条件是a[qmax.front()] - a[qmin.front()] > K，不要写成绝对值。因为最大值队列队头是当前窗口最大值，最小值队列队头是当前窗口最小值，差值一定非负。
• left右移之后，上一次得到的窗口信息被丢弃，但没问题，因为左边界单调右移，窗口是一个移动的区间，不会漏掉任何合法解。

这道题如果考察的是“子数组”而不是“子序列”，滑动窗口加单调队列就是最优解。部分变体还会要求输出最长子数组的起点和终点，思路同样，只是多记录两个变量。

5. 真题精讲：相邻差不超过K的最长子序列

再来一道动态规划加数据结构优化的题。题目大意：给定n个整数，可以删除其中任意多个数，要求剩下的序列中任意相邻两个数的差的绝对值都不超过K，问最少删除几个数。等价于求满足条件的最长合法子序列长度，答案就是n减去这个长度。

这道题的关键突破口是“子序列”而不是“子数组”。子序列不要求连续，所以不能直接用滑动窗口，得想状态转移。

设dp[i]表示以第i个数结尾的最长合法子序列长度。那么转移方程是：

dp[i] = 1 + max(dp[j])，其中 j < i 且 |a[i] - a[j]| <= K

也就是说，以a[i]结尾的合法子序列，可以在某个以a[j]结尾的合法子序列后面接上a[i]，前提是a[i]和a[j]的差不超过K。基础版本是O(n^2)枚举所有j，n=10^5时无法接受。

优化方向在哪里？观察转移条件：j < i是下标维度的限制，|a[i]-a[j]| <= K是值域维度的限制。如果我们不做二维枚举，而是把值域离散化，然后快速查找“值域在[a[i]-K, a[i]+K]范围里的最大dp值”，就可以把每次转移降到O(log n)。

这就需要一棵支持区间最大值查询、单点更新的线段树。树上的每个位置对应一个离散化之后的值域点，位置上的数值就是以这个值为结尾的最长合法子序列长度。

计算每个a[i]时，先查线段树区间[a[i]-K, a[i]+K]内的最大值，记为best，那么以a[i]结尾的最长合法子序列长度dp[i] = best + 1。然后把这个值更新到线段树中a[i]所在的离散化位置上。

为什么这题不能用树状数组？因为树状数组适合维护前缀最大值，而区间[a[i]-K, a[i]+K]是任意区间，最大值运算不可逆，没法通过两个前缀最大值相减得到区间最大值。所以老老实实用线段树。这也是一个区分“会用模板”和“理解模板”的好题目。

完整C++代码：

#include <bits/stdc++.h> using namespace std; struct SegTree { int n; vector<int> tree; SegTree(int n) : n(n), tree(4 * n + 4, 0) {} void update(int p, int l, int r, int pos, int val) { if (l == r) { tree[p] = max(tree[p], val); return; } int mid = (l + r) / 2; if (pos <= mid) update(p * 2, l, mid, pos, val); else update(p * 2 + 1, mid + 1, r, pos, val); tree[p] = max(tree[p * 2], tree[p * 2 + 1]); } int query(int p, int l, int r, int ql, int qr) { if (ql <= l && r <= qr) return tree[p]; int mid = (l + r) / 2, res = 0; if (ql <= mid) res = max(res, query(p * 2, l, mid, ql, qr)); if (qr > mid) res = max(res, query(p * 2 + 1, mid + 1, r, ql, qr)); return res; } }; int main() { int n, K; cin >> n >> K; vector<int> a(n); for (int i = 0; i < n; i++) cin >> a[i]; vector<int> vals = a; sort(vals.begin(), vals.end()); vals.erase(unique(vals.begin(), vals.end()), vals.end()); auto getId = [&](int x) { return lower_bound(vals.begin(), vals.end(), x) - vals.begin() + 1; }; SegTree seg(vals.size()); int ans = 0; for (int x : a) { int L = lower_bound(vals.begin(), vals.end(), x - K) - vals.begin() + 1; int R = upper_bound(vals.begin(), vals.end(), x + K) - vals.begin(); // 第一个 > x+K 的位置，1-based右端点正好是它 int best = 0; if (R >= L) best = seg.query(1, 1, vals.size(), L, R); int cur = best + 1; seg.update(1, 1, vals.size(), getId(x), cur); ans = max(ans, cur); } cout << n - ans << endl; return 0; }

几个实现细节需要特别留意：

• 离散化数组vals是去重排序后的所有可能取值。下标从1开始，方便线段树处理。
• L是第一个大于等于x-K的离散化位置，用lower_bound。
• R用upper_bound求第一个大于x+K的位置，因为是0-based索引，所以1-based右端点就是R，不需要减1。比如x+K=5，vals=[1,2,3,5,7]，upper_bound返回4（7的位置），那么小于等于5的下标是1~4，1-based右端点确实就是4。如果R < L，说明区间不存在，跳过查询。
• 线段树单点更新时，同一个值域位置可能被更新多次，要取最大值。因为同一个数值可以出现在数组的不同位置，dp值要保留最大的那个。
• 答案要求最少删除数，所以输出n-ans。这就是“最长合法子序列长度”和“最小删除数”的转化，题目喜欢在这个地方做一层变形，别搞反。

这道题背后其实是LIS（最长上升子序列）的加强版。普通的LIS限制是a[j] < a[i]，这里变成了差值绝对值不超过K，状态设计和查询方式就都跟着变了。网易喜欢在这个思路上做文章，把这题吃透，LIS的常见变体基本都不会慌。

6. 笔试实战复盘：时间分配、自测样例与查错路线

最后这章说说不涉及算法的决胜因素：时间分配和查错方法。很多同学笔试翻车，不是不会做，而是节奏崩了。一上来卡在第一题，死磕了40分钟，后面三道题全没时间看，那就真的很难救回来了。

我自己的时间分配策略是：拿到试卷先花2~3分钟把四道题全部扫一遍，瞬间标注三件事——题目类型、数据范围、大概思路。然后按照“会做且容易AC > 会做但代码长 > 暴力能拿部分分 > 完全没思路”的顺序来写代码。

推荐的大致节奏：

• 第1题：20分钟内解决，超过30分钟就果断放弃，先做后面的。
• 第2题：30分钟，如果思路不清晰，先写暴力拿部分分。
• 第3题：40分钟，通常是最能拉开差距的一题。
• 第4题：30分钟，能做则做，做不出就把暴力样例代码写上。

写代码前先在草稿或注释里列一下输入范围、边界情况，避免代码写一半发现方向错了。写完样例通过后，先别急着点提交，疯狂造几组测试用例：

• n=1或空数组
• K=0且数组大量相同元素
• 答案等于0或等于n的边界场景
• 包含负数、最大值、最小值
• 如果题目涉及取模，测试一个超过int范围的大数场景

我的习惯是写一个对拍脚本：用自己实现的暴力解法和优化解法同时跑随机小数据，对比输出是否一致。笔试时间紧张，写完整对拍脚本不现实，但至少可以手动造三五组小样例。这个步骤能拦住80%以上的低级错误。

查错路线也讲一下。如果代码运行结果不对，不要东猜西猜。按这个顺序排查：先看输入输出格式，再看数据范围有没有爆int，再看数组下标是否越界，再看单调队列或线段树这类结构的边界条件，最后看题目里的“相等”“不超过”“大于等于”这些词是否有理解偏差。这道题最大概率出问题的地方，往往是条件判断里的等号，以及离散化边界。把等号问题单独列出来检查，很多人能少丢十几分。

笔试结束后还有一件重要的事：复盘。我见过太多人考完就完事，下次笔试遇到同类型题目照样丢分。每次笔试完，趁思路还没凉透，把四道题重新做一遍，按“题目类型、解法核心、踩坑点”三个维度记到错题本里。过两周再刷一遍这四道题的同类变体，直到能不靠题解独立写出来为止。刷什么？不是刷原题，而是把原题背后的算法抽出来做变体训练。比如这道题考了单调队列，就找3~5道滑动窗口和单调队列的题；那道题考了线段树优化DP，就找LIS变体和区间最大值DP的变体。

最后分享一个我一直在用的小习惯：平时把常用模板整理成自己的代码片段库，包括快读、并查集、线段树、单调队列、拓扑排序、Dijkstra。笔试时先花五分钟把用得到的模板手动敲一遍，热热手，顺便检查环境。这样真到做题的时候，手不会生，代码结构也更稳定。这个习惯不一定会让你多解出一道难题，但能让你把会做的题稳稳拿住分数——校招笔试到最后比的往往不是谁聪明，而是谁不丢分。