每年秋招网易的笔试一直是互联网大厂里比较有代表性的那一档。有人觉得它比BAT简单有人连续两次挂在同一类题上还有人考完才发现自己连样例都没读懂。我翻完2019秋季校园招聘编程题真题集合把那些容易踩坑、容易丢分、复盘后才发现“原来这么考”的细节整理了一遍算是一份针对网易笔试的实战攻略。网易2019秋招编程题有一个非常明显的特点题目都会套一层故事背景。主角无非是小易、石板、能量站、数组游戏但脱掉外壳之后考查的还是那几类经典算法——字符串处理、数组枚举、动态规划、图论搜索。真正的难点不是算法本身而是你能不能快速把故事翻译成数学模型然后选择正确的复杂度优化手段。这篇文章不打算按“真题答案合集”的方式来写而是挑了三类高频且具备代表性的题目完整还原从审题、推导到代码实现和边界测试的过程。顺便把笔试环境里那些“非算法因素”的丢分点一并说清楚。无论你是第一次参加校招笔试还是已经刷了不少题想查漏补缺这篇应该都能给你一些实际帮助。1. 网易2019秋招笔试的基调题型结构与命题口味先说整体感受。网易的校招笔试通常一场4道编程题时间在120分钟上下考试平台主要是牛客网。平台本身支持C/C、Java、Python等主流语言判题方式按测试点给分部分通过也有分数。这个机制很关键意味着你完全不需要每道题都AC拿部分分也能进面试。四道题有一个明显的难度阶梯。第一题一般是字符串或数组的简单模拟考的是代码基本功20分钟内应该解决。第二题开始需要一点算法思维常见的是枚举优化、二分、贪心。第三题往往是动态规划或者数据结构优化这一题基本决定了你能不能拿到这轮笔试的高分。第四题属于拉开差距的题有时会涉及图论、状态压缩、数论等相对冷门的方向大多数人的策略是拿部分分。网易命题口味有四个高频标签字符串、数组、动态规划、图论。字符串题喜欢玩“压缩”“展开”“反转”“匹配”数组题偏爱“区间”“差值”“单调性”动态规划题则常考“状态设计”和“优化”不会出太裸的模板题图论题一般不会超过最短路径和并查集的范畴。这里顺便给一个我的备考优先序先把滑动窗口、双指针、单调栈/队列做熟再搞定LIS和背包类DP的优化写法最后补一补并查集和最短路径模板。把这些吃透网易笔试至少覆盖80%的考点。高频考点常见出题方式推荐练习方向字符串压缩展开、子串匹配、字符计数双指针、哈希、KMP数组区间最值、子数组条件计数单调队列、滑动窗口、前缀和动态规划最长合法序列、路径规划LIS、LCS、背包、状态压缩图论连通性、最短跳跃次数并查集、BFS、Dijkstra边界处理大数、空数组、极端K值多造边界用例自测网易的题还有一个隐藏特点数据范围给得很直白但不会在题目里提醒你“这个得用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^97取模”你写int运算中间过程直接溢出。还有坐标、距离、累计长度这些变量题目给了10^5规模但累计值可能到10^10不用long long就是错。这一条看起来简单但每年都有人栽。再说递归。某些题用DFS或分治会比较自然但深度达到10^5甚至更高时C默认栈会爆。必要时改成显式栈的迭代写法或者在牛客支持的情况下把递归深度限制调大。正常来说笔试题目不怎么追求这种极端递归但图论题BFS通常比DFS更稳也更不容易栈溢出。边界条件部分我的习惯是写出代码后立刻造三组测试样例最小输入n1或数组为空、最大输入、带极端值的输入。比如第三题答案可能是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个字符。K11前10个都是a第11个是b。如果用我们分段统计的逻辑扫描到a时累计长度10此时累计长度10仍然小于K11继续扫描扫描到b时累计长度2变成1211返回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^5a[i]是32位整数。如果对复杂度不敏感第一反应是枚举所有子数组O(n^2)检查每个子数组的最大最小差总复杂度O(n^3)。在n10^5时这简直不可行。即使优化成固定左端点、移动右端点时动态维护最大最小值也只是把单次检查变O(1)枚举子数组本身还是O(n^2)。依然会超时。这道题的关键是观察到一个单调性当左端点固定时右端点向右移动窗口内的最大值-最小值只会不变或变大不会变小。也就是说某个子数组合法那么它内部的任意子数组也合法某个子数组不合法右端再扩大只会更不合法。这给了滑动窗口一个明确的收缩条件每当最大减最小超过K我们就让左端点向右移动直到重新合法。滑动窗口本身不难想难点在于如何O(1)获取当前窗口的最大值和最小值。这里需要引入两个单调队列一个维护窗口内最大值的候选序列一个维护最小值的候选序列。单调队列维护极值的原理可以这样理解假设我们在一个队列里维护窗口内元素的下标同时保证下标对应的元素值从队头到队尾是单调递减的。那么队头元素就是当前窗口的最大值。新元素入队前从队尾弹出所有小于等于它的元素因为它们已经不可能在后续充当最大值了——新元素下标更大且值更大老元素在窗口左移时会更早失效所以可以直接淘汰。最小值队列同理只是单调性相反从队尾弹出所有大于等于新元素的元素。用生活类比来解释窗口就像一队人在排队打饭你关心这队里最高的人是谁以及他什么时候走。单调队列不是把所有人都记下来而是只记“有机会成为最高的人”。如果你新来的比队尾那个高那后面在你排队的时候就不会再看到队尾那位直接把他踢掉就行。这个算法整体是O(n)的因为每个下标最多入队一次、出队一次左右指针只前进不后退时间复杂度线性空间复杂度O(n)。在n10^5时完全没有压力。C完整实现#include bits/stdc.h using namespace std; int main() { int n, K; cin n K; vectorint a(n); for (int i 0; i n; i) cin a[i]; dequeint 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)枚举所有jn10^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; vectorint 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; vectorint a(n); for (int i 0; i n; i) cin a[i]; vectorint 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(); // 第一个 xK 的位置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求第一个大于xK的位置因为是0-based索引所以1-based右端点就是R不需要减1。比如xK5vals[1,2,3,5,7]upper_bound返回47的位置那么小于等于5的下标是1~41-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分钟能做则做做不出就把暴力样例代码写上。写代码前先在草稿或注释里列一下输入范围、边界情况避免代码写一半发现方向错了。写完样例通过后先别急着点提交疯狂造几组测试用例n1或空数组K0且数组大量相同元素答案等于0或等于n的边界场景包含负数、最大值、最小值如果题目涉及取模测试一个超过int范围的大数场景我的习惯是写一个对拍脚本用自己实现的暴力解法和优化解法同时跑随机小数据对比输出是否一致。笔试时间紧张写完整对拍脚本不现实但至少可以手动造三五组小样例。这个步骤能拦住80%以上的低级错误。查错路线也讲一下。如果代码运行结果不对不要东猜西猜。按这个顺序排查先看输入输出格式再看数据范围有没有爆int再看数组下标是否越界再看单调队列或线段树这类结构的边界条件最后看题目里的“相等”“不超过”“大于等于”这些词是否有理解偏差。这道题最大概率出问题的地方往往是条件判断里的等号以及离散化边界。把等号问题单独列出来检查很多人能少丢十几分。笔试结束后还有一件重要的事复盘。我见过太多人考完就完事下次笔试遇到同类型题目照样丢分。每次笔试完趁思路还没凉透把四道题重新做一遍按“题目类型、解法核心、踩坑点”三个维度记到错题本里。过两周再刷一遍这四道题的同类变体直到能不靠题解独立写出来为止。刷什么不是刷原题而是把原题背后的算法抽出来做变体训练。比如这道题考了单调队列就找3~5道滑动窗口和单调队列的题那道题考了线段树优化DP就找LIS变体和区间最大值DP的变体。最后分享一个我一直在用的小习惯平时把常用模板整理成自己的代码片段库包括快读、并查集、线段树、单调队列、拓扑排序、Dijkstra。笔试时先花五分钟把用得到的模板手动敲一遍热热手顺便检查环境。这样真到做题的时候手不会生代码结构也更稳定。这个习惯不一定会让你多解出一道难题但能让你把会做的题稳稳拿住分数——校招笔试到最后比的往往不是谁聪明而是谁不丢分。
网易秋招笔试编程题实战解析：字符串、滑动窗口与动态规划
每年秋招网易的笔试一直是互联网大厂里比较有代表性的那一档。有人觉得它比BAT简单有人连续两次挂在同一类题上还有人考完才发现自己连样例都没读懂。我翻完2019秋季校园招聘编程题真题集合把那些容易踩坑、容易丢分、复盘后才发现“原来这么考”的细节整理了一遍算是一份针对网易笔试的实战攻略。网易2019秋招编程题有一个非常明显的特点题目都会套一层故事背景。主角无非是小易、石板、能量站、数组游戏但脱掉外壳之后考查的还是那几类经典算法——字符串处理、数组枚举、动态规划、图论搜索。真正的难点不是算法本身而是你能不能快速把故事翻译成数学模型然后选择正确的复杂度优化手段。这篇文章不打算按“真题答案合集”的方式来写而是挑了三类高频且具备代表性的题目完整还原从审题、推导到代码实现和边界测试的过程。顺便把笔试环境里那些“非算法因素”的丢分点一并说清楚。无论你是第一次参加校招笔试还是已经刷了不少题想查漏补缺这篇应该都能给你一些实际帮助。1. 网易2019秋招笔试的基调题型结构与命题口味先说整体感受。网易的校招笔试通常一场4道编程题时间在120分钟上下考试平台主要是牛客网。平台本身支持C/C、Java、Python等主流语言判题方式按测试点给分部分通过也有分数。这个机制很关键意味着你完全不需要每道题都AC拿部分分也能进面试。四道题有一个明显的难度阶梯。第一题一般是字符串或数组的简单模拟考的是代码基本功20分钟内应该解决。第二题开始需要一点算法思维常见的是枚举优化、二分、贪心。第三题往往是动态规划或者数据结构优化这一题基本决定了你能不能拿到这轮笔试的高分。第四题属于拉开差距的题有时会涉及图论、状态压缩、数论等相对冷门的方向大多数人的策略是拿部分分。网易命题口味有四个高频标签字符串、数组、动态规划、图论。字符串题喜欢玩“压缩”“展开”“反转”“匹配”数组题偏爱“区间”“差值”“单调性”动态规划题则常考“状态设计”和“优化”不会出太裸的模板题图论题一般不会超过最短路径和并查集的范畴。这里顺便给一个我的备考优先序先把滑动窗口、双指针、单调栈/队列做熟再搞定LIS和背包类DP的优化写法最后补一补并查集和最短路径模板。把这些吃透网易笔试至少覆盖80%的考点。高频考点常见出题方式推荐练习方向字符串压缩展开、子串匹配、字符计数双指针、哈希、KMP数组区间最值、子数组条件计数单调队列、滑动窗口、前缀和动态规划最长合法序列、路径规划LIS、LCS、背包、状态压缩图论连通性、最短跳跃次数并查集、BFS、Dijkstra边界处理大数、空数组、极端K值多造边界用例自测网易的题还有一个隐藏特点数据范围给得很直白但不会在题目里提醒你“这个得用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^97取模”你写int运算中间过程直接溢出。还有坐标、距离、累计长度这些变量题目给了10^5规模但累计值可能到10^10不用long long就是错。这一条看起来简单但每年都有人栽。再说递归。某些题用DFS或分治会比较自然但深度达到10^5甚至更高时C默认栈会爆。必要时改成显式栈的迭代写法或者在牛客支持的情况下把递归深度限制调大。正常来说笔试题目不怎么追求这种极端递归但图论题BFS通常比DFS更稳也更不容易栈溢出。边界条件部分我的习惯是写出代码后立刻造三组测试样例最小输入n1或数组为空、最大输入、带极端值的输入。比如第三题答案可能是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个字符。K11前10个都是a第11个是b。如果用我们分段统计的逻辑扫描到a时累计长度10此时累计长度10仍然小于K11继续扫描扫描到b时累计长度2变成1211返回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^5a[i]是32位整数。如果对复杂度不敏感第一反应是枚举所有子数组O(n^2)检查每个子数组的最大最小差总复杂度O(n^3)。在n10^5时这简直不可行。即使优化成固定左端点、移动右端点时动态维护最大最小值也只是把单次检查变O(1)枚举子数组本身还是O(n^2)。依然会超时。这道题的关键是观察到一个单调性当左端点固定时右端点向右移动窗口内的最大值-最小值只会不变或变大不会变小。也就是说某个子数组合法那么它内部的任意子数组也合法某个子数组不合法右端再扩大只会更不合法。这给了滑动窗口一个明确的收缩条件每当最大减最小超过K我们就让左端点向右移动直到重新合法。滑动窗口本身不难想难点在于如何O(1)获取当前窗口的最大值和最小值。这里需要引入两个单调队列一个维护窗口内最大值的候选序列一个维护最小值的候选序列。单调队列维护极值的原理可以这样理解假设我们在一个队列里维护窗口内元素的下标同时保证下标对应的元素值从队头到队尾是单调递减的。那么队头元素就是当前窗口的最大值。新元素入队前从队尾弹出所有小于等于它的元素因为它们已经不可能在后续充当最大值了——新元素下标更大且值更大老元素在窗口左移时会更早失效所以可以直接淘汰。最小值队列同理只是单调性相反从队尾弹出所有大于等于新元素的元素。用生活类比来解释窗口就像一队人在排队打饭你关心这队里最高的人是谁以及他什么时候走。单调队列不是把所有人都记下来而是只记“有机会成为最高的人”。如果你新来的比队尾那个高那后面在你排队的时候就不会再看到队尾那位直接把他踢掉就行。这个算法整体是O(n)的因为每个下标最多入队一次、出队一次左右指针只前进不后退时间复杂度线性空间复杂度O(n)。在n10^5时完全没有压力。C完整实现#include bits/stdc.h using namespace std; int main() { int n, K; cin n K; vectorint a(n); for (int i 0; i n; i) cin a[i]; dequeint 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)枚举所有jn10^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; vectorint 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; vectorint a(n); for (int i 0; i n; i) cin a[i]; vectorint 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(); // 第一个 xK 的位置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求第一个大于xK的位置因为是0-based索引所以1-based右端点就是R不需要减1。比如xK5vals[1,2,3,5,7]upper_bound返回47的位置那么小于等于5的下标是1~41-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分钟能做则做做不出就把暴力样例代码写上。写代码前先在草稿或注释里列一下输入范围、边界情况避免代码写一半发现方向错了。写完样例通过后先别急着点提交疯狂造几组测试用例n1或空数组K0且数组大量相同元素答案等于0或等于n的边界场景包含负数、最大值、最小值如果题目涉及取模测试一个超过int范围的大数场景我的习惯是写一个对拍脚本用自己实现的暴力解法和优化解法同时跑随机小数据对比输出是否一致。笔试时间紧张写完整对拍脚本不现实但至少可以手动造三五组小样例。这个步骤能拦住80%以上的低级错误。查错路线也讲一下。如果代码运行结果不对不要东猜西猜。按这个顺序排查先看输入输出格式再看数据范围有没有爆int再看数组下标是否越界再看单调队列或线段树这类结构的边界条件最后看题目里的“相等”“不超过”“大于等于”这些词是否有理解偏差。这道题最大概率出问题的地方往往是条件判断里的等号以及离散化边界。把等号问题单独列出来检查很多人能少丢十几分。笔试结束后还有一件重要的事复盘。我见过太多人考完就完事下次笔试遇到同类型题目照样丢分。每次笔试完趁思路还没凉透把四道题重新做一遍按“题目类型、解法核心、踩坑点”三个维度记到错题本里。过两周再刷一遍这四道题的同类变体直到能不靠题解独立写出来为止。刷什么不是刷原题而是把原题背后的算法抽出来做变体训练。比如这道题考了单调队列就找3~5道滑动窗口和单调队列的题那道题考了线段树优化DP就找LIS变体和区间最大值DP的变体。最后分享一个我一直在用的小习惯平时把常用模板整理成自己的代码片段库包括快读、并查集、线段树、单调队列、拓扑排序、Dijkstra。笔试时先花五分钟把用得到的模板手动敲一遍热热手顺便检查环境。这样真到做题的时候手不会生代码结构也更稳定。这个习惯不一定会让你多解出一道难题但能让你把会做的题稳稳拿住分数——校招笔试到最后比的往往不是谁聪明而是谁不丢分。
