★ FEATURED ARTICLE 复试OJ二刷复盘系列写到第3篇正好是我把第一轮“背过但没吃透”的题重新过完近一半的节点。先说结论二刷比第一次刷题难受多了因为你会反复看到某个一刷时“AC了”的题现在连完整的main函数都憋不出来。那种感觉比第一次见新题还要空虚。但也正是这种“旧题新卡”让我意识到一刷的通过率有多少水分也让二刷成了整个复试机试准备里最值钱的一段。这篇不打算罗列我又过了多少题而是想把二刷过程中真正改变我做题习惯的几个东西写下来定规矩、挑错题、看边界、抠输入输出细节以及最后怎么把错题变成考前能快速翻完的笔记。如果你也在准备某类复试OJ或者只是想把算法题从“背模板”提升到“真会做”这篇应该对你有用。1. 二刷前我先给自己定了三条规矩不然就是重复一刷1.1 规矩一不看旧AC代码靠“白纸回忆”起步一刷的时候我大量依赖搜索引擎和题解经常是看懂了甚至抄了一遍然后本地跑通就去OJ交。这种代码属于“顺着题解走的代码”不是“从题目自己推出来的代码”。二刷如果还点开自己的提交记录那等于把一刷的路径原封不动再走一遍收获只是多了一点熟练度。我给自己定的规矩是读完题之后先把屏幕切到编辑器白纸开始写不看任何旧代码。哪怕写得很烂哪怕写得比原来的版本长一倍也先写出来。写的过程才是真正把“题目的逻辑”和“代码的表达”重新接上的过程。有一道很简单的字符串题一刷我看题解十分钟就过了二刷让我在白纸上写我卡在“怎么处理最后一个单词”上想了很久。那一刻我才明白一刷的AC本质上只是把别人的思路誊写了一遍。白纸回忆这个动作虽然慢但它能把“背会的”和“真正会的”区分开。复试机试考的就是后者所以这条规矩我一条都没放松过。1.2 规矩二跑过样例不算完必须自问三个“为什么”以前一刷样例过了就急着提交提交AC了就觉得搞定。这次我强制自己在AC之后多一步自检这段代码为什么能在题目数据范围内通过我用的算法在时间上是不是最优如果不是是大意了还是不会如果把某个输入换成极端情况n0、全为同一个字符、链表只有一个节点代码会怎样这三个问题看起来基础但二刷时被它们问住的题恰恰是一刷时“背模板”背过的题。比如后面要讲的三类翻车题几乎每一个都是在这三个问题下现出原形的。尤其是第二个问题以前我从来不看题目给的数据范围也不估算复杂度反正样例能过就交。现在我会先问一句这个n最大能到多少我的循环嵌套扛不扛得住就这一句话已经帮我拦下好几次超时。1.3 规矩三宁可错得难看不许抄得顺手这里多说一句。很多人二刷维持不住一周就是因为一面是“不会做”的挫败感一面是“打开题解就能AC”的即时快感后者太诱人了。我后来发现一个妥协方案允许自己在卡了二十分钟后看提示但不允许直接看完整代码。最多看一眼算法关键词比如“双指针”“前缀和”“栈”然后把题解关掉继续写。这个方案的好处是既能保证二刷进度不被拖死又把“背题解”的空间压到最小。二刷的意义本来就是把“曾经靠提示做出来的题”变成“不靠提示也能安静写完的题”。我见过不少人二刷时依然开着一个题解页面在旁边那其实只是换了一种方式的一刷。2. 这次重做翻车最多的三类题每一题都是一面镜子2.1 字符串类一边循环走完还要记得补最后的收尾复试OJ几乎绕不开字符串题。我这次二刷碰到一道很基础的题给一段英文文本统计每个单词出现的次数不区分大小写忽略标点符号。看起来简单我一上来就出了三个问题用cin s读入结果遇到换行和连续空格直接把一行切得支离破碎判断“单词结束”时等循环走出去才处理最后一个单词结果漏了文本末尾没有跟随标点的那个单词把标点剔除和大小写转换写在同一个位置导致“Hello,”这种带尾部标点的词被统计成两个不同的key。正确做法是逐字符读入而不是按单词读入。遇到字母或数字就把字符转小写拼进当前的word遇到非字母数字就说明一个单词结束了此时如果word非空再计数然后清空word重新拼。这样“最后一个单词”只在循环结束后补一次即可。#include bits/stdc.h using namespace std; int main() { mapstring, int cnt; char ch; string word; while ((ch getchar()) ! EOF) { if (isalnum(ch)) { word tolower(ch); } else { if (!word.empty()) { cnt[word]; word.clear(); } } } if (!word.empty()) cnt[word]; for (auto kv : cnt) cout kv.first kv.second \n; return 0; }这个解法的时间是O(n)不算map内部复杂度比“先split再排序统计”写起来短而且边界天然被“非单词字符即分隔”这一判断覆盖了。最需要注意的是循环结束后那一次计数少了它文本最后一个单词就会从统计里消失。这种问题如果不二刷根本不会意识到一刷时为什么AC了——因为一刷的样例恰好没有“文本末尾直接结束”的情况。2.2 链表类虚拟头节点救了我大半条命二刷时我做了一道“合并两个有序链表”的题要求不能额外申请节点。一刷我记得自己用的是递归这次想练非递归结果一上来就出问题不用虚拟头节点就得先判断两个链表的头谁小谁当“结果链的头”然后还要维护一个尾指针。代码写出来不仅长而且“当前链没走完另一条链还有剩余”这个收尾逻辑我连续写错两次。虚拟头节点的核心价值是让“第一个节点”和“后续节点”的插入逻辑完全统一。你不需要单独讨论结果链是不是为空反正dummy永远在场。写起来也清爽很多struct ListNode { int val; ListNode *next; ListNode(int x) : val(x), next(nullptr) {} }; ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { ListNode dummy(0); ListNode* tail dummy; while (l1 l2) { if (l1-val l2-val) { tail-next l1; l1 l1-next; } else { tail-next l2; l2 l2-next; } tail tail-next; } tail-next l1 ? l1 : l2; return dummy.next; }写完复盘时我总结了一条凡是涉及“结果链的第一节点需要单独处理”的链表题无脑加一个虚拟头是性价比最高的做法。还有一个隐形好处是之后写删除节点、反转区间这类题dummy节点能一并避免很多空指针梦魇。链表题在OJ上出错很多时候不是思路不对而是空指针访问直接RE虚拟头能挡掉一大半。2.3 树的层序遍历变体队列里既要节点也要知道在哪一层有一道常见的“之字形层序遍历”题第一层从左到右第二层从右到左交替输出。我二刷时的第一个版本是用两个栈来回倒思路是“当前层从左到右入栈下一层从右到左入栈”结果顺序理了半天发现自己把左右孩子入栈的顺序是否反过来、以及要不要按层输出彻底搞混了。后来我给队列里每一层做了计数一次弹完一整层遇到需要反向的层就临时用索引倒着填vector代码简单多了vectorvectorint zigzag(TreeNode* root) { vectorvectorint ans; if (!root) return ans; queueTreeNode* q; q.push(root); bool leftToRight true; while (!q.empty()) { int sz q.size(); vectorint level(sz); for (int i 0; i sz; i) { TreeNode* cur q.front(); q.pop(); int idx leftToRight ? i : sz - 1 - i; level[idx] cur-val; if (cur-left) q.push(cur-left); if (cur-right) q.push(cur-right); } ans.push_back(level); leftToRight !leftToRight; } return ans; }这种“按层计数”的队列写法比用两个栈的思路好理解多了。它告诉我一个道理树这种结构里光知道节点还不够层号往往才是题目的隐藏要求。与其费劲在数据结构上变换不如在“每层大小”上做文章。这些坑不是第一次写就发现的都是二刷时用“不信一刷思路”的显微镜照出来的。3. OJ评测的红绿灯复杂度和边界二刷必须开始用眼睛判断3.1 复杂度为什么本地秒过评测机却超时复试OJ的题目后面通常会写数据范围比如n≤10^5但一刷的我根本不看这个数字。二刷时我专门开始练“一看数据范围就能说出目标复杂度”的能力。经验公式大概是n≤10^3时O(n^2)基本可以随便写n≤10^5到10^6时O(n log n)安全O(n^2)大概率超时n≤10^8时基本只有O(n)甚至O(log n)能活。为什么一般评测机限时1到2秒可以粗略认为每秒处理10^8左右次基础运算。1e5的平方是1e10次操作也就是一百亿次远超一秒能承受的量。所以当你写下一个双重循环扫一眼n的范围就该知道结果。二刷时我遇到一道n2e5的数组题第一版用双重循环求某个子区间和本地造了个小样例秒出一提交TLE。改成前缀和后一次扫完AC。这个对比比一百句“要注意复杂度”都更有说服力。3.2 边界0、1、最大这三个数字是评测机的三大最爱一刷最容易丢分的地方不是算法难而是边界。二刷我有意识地把每个题的边界条件列成清单当n0或输入为空时你的循环会不会跑空能不能直接返回预设值当链表只有一个节点时你的前驱、后继指针是否安全当所有数字都相等、所有字符都一样时你的“严格大于”“非严格大于”用对了吗当答案超过int范围时你有没有用long long当取模时出现了负数你有没有在最后补上mod我还做了一张“边界对照小表”贴在笔记里每次提交前都扫一眼输入场景最容易翻车的点二刷时的自查动作空输入、空串、n0循环体内访问首元素前先判空每次循环前确认下标可访问单节点、单字符对next和prev的引用先画链再写指针最大数据、最坏情况复杂度或溢出预估计算量并用long long重复值、逆序输入排序与“稳定”要求确定用什么比较符这张表看起来简单但二刷的每一道题我都会在提交前花两分钟过一遍。结果错题率直接降了一个档次。OJ不是“过了人类肉眼看到的样例”就算赢那些隐藏用例真正检查的往往就是你自己最不想测的那几个数值。3.3 不要怕被隐藏用例卡要把AC当成一种最低标准这里说点可能不太合群的话如果一个题你AC了但根本不知道数据范围是什么、也没想过极端输入那这个AC其实含水量很高。二刷时我不再把“AC了”当成“我会了”而是当成“至少样例没问题”。我会给自己加一分钟测试时间故意构造几组边界数据跑一下。比如字符串题我输入空串、纯标点串、超长单词链表题我输入空链表、单节点链表树题我输入空树、单边树。这些事情在正式复试的时候不是锦上添花而是必须的工序。因为机试的环境里你不会有太多机会去猜隐藏用例唯一能依赖的就是你在平时把这些用例“预演”过百遍之后形成的条件反射。4. 这轮刷题里最折磨我的细节全和编译器与输入输出有关4.1 输入函数混用是我翻车频率最高的一类错误复试OJ大多是标准输入输出。二刷前我一直觉得“输入输出不就是这样嘛”直到连续三题栽在“先读整数再读带空格的字符串”这个场景。问题出在scanf(%d, n)之后输入流里还停着一个换行符接下来如果直接gets()或getline(cin, s)它读到的就是一个空行而不是你真正想读的那行字符串。解决办法有两种int n; string line; cin n; getline(cin, line); // 吃掉换行通常是一个空行 getline(cin, line); // 真正读入目标行或者更稳的写法int n; scanf(%d, n); getchar(); // 吞掉换行 char buf[1000]; fgets(buf, sizeof(buf), stdin); // 读含空格整行这两种都行但关键在于每次混用不同读取方式之前心里要清楚输入流里此刻正在等待、正在残留的是什么。一刷时我不理解为什么代码在本地跑得好好的交上去WA得莫名其妙二刷才知道根本不是逻辑错了是回车键被我当成普通字符处理了。4.2 多组数据的读入从“不知道”到“条件反射”复试OJ不少题目会写“输入包含多组测试数据每组数据格式如下”。很多第一次接触OJ的人包括我一开始会傻傻地只处理一组输入或者无限循环读爆。现在的标准动作基本是int n; while (cin n) { // 等价于 while (scanf(%d, n) ! EOF) // 处理每一组 n }注意这种写法本身就是在“检测是否还有数据”读到文件结尾就自然结束。但有个细节很容易忽略如果每组数据包含字符串而且你用了cin s它按空白字符切分如果题目说“每组一行字符串”你要么用getline要么记得在读整数后手动先吞掉换行。除此之外多组数据之间可能有空行要不要跳过空行也要看着题目描述来。二刷阶段我给自己总结的口诀是先分清题目是“单组直接算”还是“多组读到结束”再决定循环的写法。这一步看错答得再对也是白搭。4.3 大数与取模别在int上翻车复试OJ里“结果对1000000007取模”几乎是标配。一刷时我直接int ans 1; 然后for循环里ans * x; 结果一旦x或ans稍大中间过程立刻溢出最后模出来的答案跟真实结果对不上。二刷后我的习惯是只要题面出现“取模”先把所有参与乘法、累加的变量定为long long并且每次更新后都取模比如const long long MOD 1000000007LL; long long res 1; for (int i 0; i n; i) { res res * a[i] % MOD; }另外做减法取模时比如(a - b) % MODC里结果可能是负数正确写法是(a - b MOD) % MOD。这个小细节我亲眼见过很多人在正式机试时丢分不是不懂取模是忘了负数的坑。4.4 编译警告不只是噪音本地编译器有时候会忽略一些警告直接跑出结果比如变量未初始化、隐式类型转换、数组越界前的可疑判断等。OJ评测用的环境更严格同一个代码本地能跑提交后可能变RE或WA。二刷时我把本地的编译参数加上了-Wall -Wextra每当警告里出现“可能未初始化”“比较有符号与无符号”这类提示我都会随手修掉而不是关掉警告继续提交。这个习惯救过我一次有一道题的二维数组我申请成了“int ma[1000][1000]”但内部循环误用了“ma[i][1000]”本地小数据完全没事-Wall明确报了越界索引提示才让我在提交前堵住这个坑。很多人觉得警告只是提示不报错就不用管但在OJ场景下警告往往是隐藏RE的前兆。5. 二刷复盘我用一题一表逼自己直面错误5.1 我的“一题三列”笔记格式二刷时我发现如果只记录“这题我过了”复盘毫无意义。真正有价值的是记录“我错在哪、为什么错、下次怎么避免”。所以每题我会开一个小表格三列错误点写清楚代码里哪一行、哪个判断、哪个循环出了问题越具体越好根因是没读懂题还是忘了复杂度还是边界没考虑还是某种语法细节二刷教训用一句能迁移到其他题的话写下来。比如“字符串统计题最后一个单词被漏掉”这一行我写的教训是“凡是以分隔符切分的字符串处理循环结束后必须再补一次收尾判断”。这类句子积累二三十条之后会发现自己对“输入扫描类题目”的敏感度一下子提高了。复试前不需要再看一遍题解只需要翻一遍这些教训就能把自己常踩的坑全部唤醒。5.2 错误归因别把所有错都推给“粗心”很多人复盘时爱写“下次细心点”这话等于没说。二刷时我重新对所有错题做了归因发现错误大概能分成五类读题理解错、边界条件漏、复杂度预估错、代码细节错数组名打错、变量覆盖、括号漏掉、思路本身就没有形成。归因之后我才能针对性地练。比如连续几个“边界条件漏”那就逼自己在提交前把所有0/1/极端数据先跑一遍连续几个“复杂度预估错”就逼自己每次读题后先把n的范围圈出来。复盘不是写日记是在做问题定位。只有把错误归到具体的“行为”上下一步的练习才有靶子。5.3 给题分档控制二刷节奏复试准备的时间很紧二刷不能每个题都无限磨。我给自己定的时间预算是简单题一看就有思路10分钟内写完并提交中等题需要想一下数据结构20分钟内能写出可运行版本难题看了题解也不一定马上懂30分钟内必须决定是继续死磕还是标记后绕过。实际执行中我很少真的卡到30分钟因为二刷的坑位是固定的一刷已经筛过一遍了。如果二刷仍有一道题卡住超过25分钟我会在表格里记录“卡在哪个点”先做后面的题第二天再回来重写一遍。这种“一题一表时间分档”的方法让我把二刷从“被动刷题”变成了“主动筛选薄弱点”。6. 复盘到第3篇我才想明白的三件小事6.1 题量是个数字掌握量才是底气二刷这段时间我最大的感受是一刷时我动不动“今天过了十题”二刷之后发现哪些题是“真掌握”哪些只是“见过”心里有了一杆秤。真正值得秒杀的是那种你能在十分钟内不假思索写出完整代码、还能说出每一步为什么这么写的题。如果你的目标是“复试OJ通过”那么一刷重广度二刷重精度。宁可二刷只精做三十道把套路理顺也不要再盲目追新题数量。把一个类型的题真正吃透比用五十个半生不熟的方法堆在心里要可靠得多。6.2 笔记是写给考前几天翻的不是写给现在的自己我之前记的笔记有一个通病当时看觉得很详细过两周再看发现“这写的是什么鬼”。二刷之后我把笔记改成了“面向未来的速查卡”模式一题两三行突出本次错误点和可复用的结论而不粘贴大段代码。这样考前只需要花一个晚上就能把几十个坑位过一遍。另外我还会给同类型的题打一个标签比如“字符串分割”“链表哑节点”“层序遍历按层计数”等到考前把它们集中在一起快刷比翻几十个分散页面高效得多。复试OJ的题目类型其实就那么几大类把标签归好等于给自己做了一张“考前地图”。6.3 二刷后期要主动模拟考场手感复试OJ通常有整体时间限制比如一小时内做三道题或者两小时做四道题。二刷如果只是单题练习很容易忽略“切换题目”带来的思维负担。我会在状态比较好的下午挑三个简单或中等的旧题设定好时间一口气写完再统一交。哪怕分数不理想这种训练的收益也很大它逼你练习“先挑软柿子捏”“该放弃就放弃”“不要在一道题上较劲到最后一秒”。这些考场策略单靠一道一道刷题是练不出来的。二刷到后期技术上的差距会越来越小真正的胜负手往往是时间分配和心理稳定。最后再说点实在的。二刷到第3篇我不再追求“AC率”这个虚荣指标了。每一道被我重写、被我标记、甚至被我放弃的题都像一面镜子把一刷的侥幸照得清清楚楚。如果你也在准备一场以机试为核心的复试建议你从今天开始停掉“打开题解—复制—提交”的循环老老实实地做一次二刷。别看旧代码别跳过边界用例别放过任何一次WA带来的反思。复试那天真正拼的不是谁见过更多题而是谁能在看穿题目之后安静地把代码写对。
阅读完成 · 觉得有帮助？
