“东华复试OJ每日3题打卡”这个系列走到第13~15题复盘刚好是备考节奏从“适应期”切换到“稳定期”的分水岭。东华大学计算机相关专业复试是有上机环节的而且用的是传统OJ评测模式——自己写完整程序处理标准输入输出跑多个测试点不是LeetCode那种填函数的玩法。这种模式决定了很现实的一点平时刷题偷的懒考场上都会变成罚时。所以从第10题开始我给自己的要求从“把题做出来”升级成了“把题吃透”每道题至少准备两种思路卡住的地方全部记进复盘笔记。这三天我刻意挑了三种“看起来不难、写起来全是坑”的题型第13题括号匹配第14题约瑟夫环第15题有序链表合并。三个题分别对应栈、模拟/递推、链表指针正好是复试机试出镜率最高的三个方向。如果你也在准备东华复试或者准备其他学校的计算机考研机试这份复盘可以直接对照着过一遍顺便看看自己在哪些地方容易栽跟头。1. 复盘前的整体思路为什么这三天选了这三道题1.1 “每日三题”的节奏怎么定很多人备考机试容易走两个极端要么疯狂刷题一天十道做完就忘要么慢慢悠悠一天一道到考前才发现还有一半题型没见过。我试下来最适合自己的是“每日三题”这个量——一题纯基础热手一题主流考点巩固一题稍微拔高逼自己思考。三个题加起来大概两小时剩下时间全部用来写复盘笔记比盲目多刷几道更值。至于选题不能全凭心情。东华复试OJ的题风偏基础很少出偏题怪题但数据范围给的比较“老实”不像比赛题那样动不动1e5起步。所以我把选题标准定为优先覆盖栈、队列、链表、排序、递归、简单动态规划这几个高频方向每天三题尽量不重复类别。第13到15题刚好轮到了括号匹配、约瑟夫环和链表合并属于复试上机题单里的老熟人。1.2 东华OJ和杭电、郑轻这些平台到底差在哪刷题平台上手之后你会发现OJ和OJ之间的“脾气”差别挺大的。杭电OJ、郑轻OJ、杭师大OJ这些老牌ACM练习平台题面传统输入输出要求严格多组输入到EOF是家常便饭东方博宜OJ这类偏教学性质的平台题面会更温和适合大一新生打基础而东华复试OJ的风格更接近前者。这里有一个很多人忽略的点不同OJ的评测机制和处理习惯会影响你的代码习惯。比如杭电OJ上养成while(scanf(%d,n)!EOF)的手感到了东华OJ碰到“先给T组数据”的题就会条件反射地写错循环结构。所以备考时不能只刷一个平台至少要用两三个平台交叉练一方面见多识广另一方面也能提前适应复试时可能遇到的输入输出格式差异。我平时除了东华OJ还会去杭电OJ和郑轻OJ找同类题互相印证。1.3 我给自己定的几条复盘规矩复盘不是把代码贴一遍就算完我给自己定了几条硬规矩这15题下来收益很明显第一所有题先独立写一遍写不出来再看题解看完题解必须自己关掉参考重新默写一遍否则不算掌握。第二每道题必须设计至少三组“刁钻用例”比如空输入、单个元素、极限规模用来测试边界条件。第三记录每次Wrong Answer的真实原因是思路错、边界错还是格式错整理成自己的错误类型清单。第四一题至少会两种写法。比如能用数组模拟的想一想能不能用链表能用递推的想一想能不能模拟。这样考场上就算一种思路卡壳还有备用方案。这几条看起来费时间但复试上机拼的就是基础稳定性把错误模式提前暴露出来比考场上第一次见到要划算得多。2. 第13题复盘括号匹配不只会用栈就行2.1 题目与考点第13题是典型的括号匹配题。题面大致是输入一个只包含小括号、中括号、大括号的字符串判断这个字符串里的括号是否合法匹配。合法要求有两层一是左右括号数量对应二是嵌套顺序正确就是俗称的“不能交叉”。很多刷过LeetCode的人觉得这题太简单了但复试OJ上这题的通过率其实不算高。原因很简单LeetCode是函数式提交编译器帮你处理了输入输出而复试OJ需要你自己写完整程序、处理多组输入、自己判断字符串结束。难度不在算法而在把一个小算法用标准IO方式完整实现出来不出一丁点错。2.2 为什么这个题非用栈不可括号匹配天然适合用栈因为它的结构是“后出现的左括号要先匹配”。这句听起来抽象打个比方括号嵌套就像往包里塞东西最后塞进去的要最先拿出来这叫后进先出。栈正好就是这个特性。有人会问难道不能用三个计数器分别数三种括号的数量只要配平就合法吗这个思路能过一部分用例但遇到交叉括号就崩了。比如[(])左括号总数和右括号总数分别是2和2数字上是配平的可顺序是错的——中括号还没闭合小括号就插进来了。计数器根本看不出顺序问题只有栈能在每次遇到右括号时立刻去检查最近一个未匹配的左括号是不是同类型。想明白这一点这题的核心思路就算真掌握了。2.3 完整代码与逐步解析我上机用的是C的string加STL栈代码如下#include bits/stdc.h using namespace std; int main() { string s; while (cin s) { stackchar st; bool ok true; for (char c : s) { if (c ( || c [ || c {) { st.push(c); } else { if (st.empty()) { ok false; break; } if ((c ) st.top() ! () || (c ] st.top() ! [) || (c } st.top() ! {)) { ok false; break; } st.pop(); } } if (!st.empty()) ok false; cout (ok ? valid : invalid) endl; } return 0; }几个关键点说一下。遇到左括号就压栈遇到右括号先判断栈是否为空——这一步很多人会忘如果栈是空的还去取st.top()直接Runtime Error。然后检查栈顶类型是否匹配注意这里我利用了短路运算st.empty()为true时后面的st.top()不会执行所以把空栈判断和类型判断写在一起也是安全的。最后全部字符串扫完之后还要再检查一次栈是不是空的防止出现(()这种左括号多余的情况。2.4 括号匹配最容易踩的四个坑第一多组输入的循环没写好。有的题目明确说“输入多行直到EOF”有的说“第一行是数据组数T”。两种情况写法完全不同考试时先看题面描述再动手不要默认成一种模式。第二不小心用计数器代替栈。刚才说的交叉括号就是致命反例平时刷题可能碰不到到了复试考场上样例一变就现出原形。第三输入里如果包含空格cin s会按空白字符断开导致字符串被截断。如果题目明说字符串可能包含空格就要改用getline(cin, s)。括号匹配题一般不会有空格但养成先读题面的习惯很重要。第四输出格式问题。有的OJ要求输出YES/NO有的要求valid/invalid还有的要求true/false。样例只是参考真正决定代码对错的是题目描述里的输出要求严格照做别自己想当然。3. 第14题复盘约瑟夫环的三种解法考场选哪种3.1 题目是什么考的是哪个点约瑟夫环是复试OJ里的常青树。题面经典到不能再经典n个人围成一圈从1号开始报数报到m的人出列然后从下一个人重新报数问最后剩下的是几号。变体还会要求输出整个出列顺序。这个题的考点其实很综合循环结构、数组下标操作、链表操作、递推思维全都能串到一起。更妙的是不同问法对应不同最优解法如果你只会一种写法很容易在现场被卡住——所以这题值得把三种方案都过一遍。3.2 解法一数组模拟写起来最直白最直观的思路是开一个数组存活的人记为1出列的人记为0。每次从当前位置开始找下一个存活的人数到第m个就标记为0直到只剩一个人。数组模拟的代码不难写但复杂度是O(nm)——外层循环要执行n次每次都要“数”m个人。n和m都很小的时候没问题一旦n到几千、m到几千运行时间就开始肉眼可见地增长。我刷题时试过用这个解法提交小数据全过把数据范围调大后直接TLE。所以数组模拟只适合作为理解题意的工具不适合作为考场唯一方案。3.3 解法二链表模拟输出出列顺序很顺手如果题目要求输出完整出列序列链表模拟比数组模拟更自然。C里直接用list就能写不必自己实现链表循环结构。我用list写过一版#include bits/stdc.h using namespace std; int main() { int n, m; while (scanf(%d%d, n, m) ! EOF) { if (n 0 || m 0) { printf(\n); continue; } listint people; for (int i 1; i n; i) people.push_back(i); auto it people.begin(); while (!people.empty()) { for (int k 1; k m; k) { it; if (it people.end()) it people.begin(); } printf(%d , *it); it people.erase(it); if (it people.end()) it people.begin(); } printf(\n); } return 0; }这里有个细节值得强调list的erase会返回被删除元素的下一个迭代器所以it people.erase(it)是安全写法。如果先删除再用旧的it迭代器已经失效行为未定义这是C初学者最常踩的坑。循环一圈的写法是判断it people.end()就回绕到begin()这个判断必须放在每次移动之后位置不能错。整体复杂度虽然还是O(nm)但链表移动指针比数组扫描要快一些而且删人就是真删代码逻辑和题意贴合得很紧。3.4 解法三数学递推只要最终编号就选它如果题目只问最后剩下几号不需要输出出列序列那就完全没必要模拟直接用递推公式一行算出答案。这里简单展开一下推导过程。把人员编号定为0到n-1。第一个人出列后剩下n-1个人重新编号原本出列者的下一位变成新一轮的0号。设f(i)表示i个人玩这个游戏最终存活者的编号从0开始那么出列者的位置是(m-1) % i下一轮从出列者的下一位开始重新编号。通过这个映射关系可以推出f(i) (f(i-1) m) % i初始条件f(1) 0。#include bits/stdc.h using namespace std; int main() { int n, m; while (scanf(%d%d, n, m) ! EOF) { if (n 0 || m 0) { printf(0\n); continue; } int ans 0; for (int i 2; i n; i) { ans (ans m) % i; } printf(%d\n, ans 1); // 题目编号从1开始所以加1 } return 0; }这个解法的复杂度是O(n)几乎感觉不到耗时。我当时在本地把n开到100万m随便取了一个大数跑完一瞬间出结果对比之下数组模拟早就卡死了。数学解法看起来只是一行取模但它背后那套“重新编号”的思想对后面理解动态规划的状态转移也有帮助值得彻底吃透。3.5 约瑟夫环在复试现场的隐藏陷阱第一个陷阱是编号起点。递推公式从0开始编号题目从1开始编号输出时忘记加1答案就会差一位。这个错误现场极难肉眼发现因为小数据样例里可能碰巧能过换一组数据就错。第二个陷阱是m的取值。有些变体题说“报到m”但m可能是0、1甚至大于当前人数。m为0时没有意义程序直接死循环m为1时就是依次出列输出顺序等于原顺序。写代码前先把这些极端值想清楚。第三个陷阱是出列顺序和最终编号的取舍。如果题目要输出整个出列序列数学递推就不能直接用了老老实实写链表模拟如果只问最终编号用模拟就是浪费考场时间。先看问什么再选做法。4. 第15题复盘有序链表合并考的是指针基本功4.1 题目描述与考察意图第15题是经典的有序链表合并两个升序链表合并成一个新的升序链表并返回头指针。这个题在LeetCode上算简单题但在复试OJ里完全不是一回事——OJ题不会给你现成的链表结构和函数接口你需要自己定义结构体、自己构建链表、自己处理输入输出最后还要保证合并逻辑正确。这个题为什么复试爱考因为它考察的是最容易被忽略的指针基本功。结构体指针的赋值、空指针的判断、头节点的处理任何一个细节出错都很难调试。而这些东西靠死记硬背是学不会的必须亲手写、亲手踩坑。4.2 迭代法借助哑结点把逻辑变短迭代合并的思路是用两个指针分别遍历两条链表谁的值小就先接谁然后移动对应指针。这里最关键的技巧是使用哑结点。#include bits/stdc.h using namespace std; struct Node { int val; Node* next; Node(int x) : val(x), next(nullptr) {} }; Node* createList(int a[], int n) { Node* head new Node(0); // 临时头结点 Node* tail head; for (int i 0; i n; i) { tail-next new Node(a[i]); tail tail-next; } return head-next; } Node* mergeTwoLists(Node* l1, Node* l2) { Node dummy(0); // 哑结点栈上对象 Node* tail dummy; while (l1 ! nullptr l2 ! nullptr) { if (l1-val l2-val) { tail-next l1; l1 l1-next; } else { tail-next l2; l2 l2-next; } tail tail-next; } tail-next (l1 ! nullptr) ? l1 : l2; return dummy.next; } int main() { int n, m; while (scanf(%d%d, n, m) ! EOF) { int* a new int[n]; int* b new int[m]; for (int i 0; i n; i) scanf(%d, a[i]); for (int i 0; i m; i) scanf(%d, b[i]); Node* l1 createList(a, n); Node* l2 createList(b, m); Node* res mergeTwoLists(l1, l2); while (res ! nullptr) { printf(%d , res-val); res res-next; } printf(\n); delete[] a; delete[] b; } return 0; }哑结点的好处是什么呢如果不设哑结点合并后需要单独判断结果头指针到底是l1还是l2代码会多出好几个if分支。用哑结点之后所有节点都统一挂在tail-next后面最后直接返回dummy.next逻辑一下子干净了。这个技巧在链表题里出现频率极高比如删除节点、反转链表、拆分链表基本都能用上。4.3 递归法代码短但别忽略栈深度递归写法更短很多面试标准答案也是递归。代码如下Node* mergeTwoListsRecur(Node* l1, Node* l2) { if (l1 nullptr) return l2; if (l2 nullptr) return l1; if (l1-val l2-val) { l1-next mergeTwoListsRecur(l1-next, l2); return l1; } else { l2-next mergeTwoListsRecur(l1, l2-next); return l2; } }递归思路非常直观每次都把较小的节点摘出来再接上剩余部分的合并结果。但复试上机我一般不推荐优先写递归原因有两个一是递归调用会占用栈空间链表一长栈开销就上去了二是递归代码出错后调试比迭代麻烦你很难在脑子里跟完整个调用链。所以我的建议是平时练习两种都要会写考场上优先用迭代递归留给面试环节展示思路。4.4 这道题在OJ和面试里的常见延伸很多人在OJ上写链表题输入部分比合并本身还容易出错。比如输入格式是“先给n再给n个数然后给m再给m个数”读入时必须先读n再循环读n个值如果题目给的链表节点本身有序但可能有重复值合并时用还是会影响稳定性和结果正确性一般用保证相等元素的相对顺序。另外我的createList里用了一个临时头结点来简化尾插法这也是一个小技巧不然每次插节点都要特判链表是否为空。还有一个容易被追问的点是内存释放。OJ上程序退出后系统会回收所有内存所以赶时间不释放也能过但如果复试有面试环节面试官问“这段代码有没有内存泄漏”你得能答上来——创建的Node节点没有被delete工程上应当写一个freeList函数逐个释放。平时练习时养成释放的习惯面试会从容很多。顺带说一句复试面试里如果聊到C智能指针可以这样衔接传统OJ链表题为了直接考指针操作通常要求手写Node结构体并用裸指针而实际工程中链表的节点所有权可以交给unique_ptr管理能大幅减少野指针和内存泄漏。能说出这一层说明你不是只会刷题而是真的理解内存管理的差异。5. 三题横向对比与上机避坑实录5.1 三道题横向对比表刷完三题之后把它们放在一起看复习效率会更高。题号核心考点推荐方法时间复杂度最容易丢分的位置第13题 括号匹配栈、字符串边界栈一次遍历O(len)空栈取栈顶、交叉括号误判第14题 约瑟夫环模拟、递推、循环结构链表模拟或数学递推O(nm) 或 O(n)编号0/1混淆、m极端值第15题 链表合并链表指针、哑结点迭代合并O(nm)空链表、尾部拼接丢节点这份表格给我自己的提示是三题分别对应“数据结构使用”“算法建模选择”“指针操作细节”恰好是复试机试三个层面的能力。括号匹配考察会不会用现成数据结构约瑟夫环考察能不能根据题目要求选择合适算法链表合并考察能不能把基础操作写到无懈可击。备考时最好按这三个层面分别训练而不是只盯着题目本身。5.2 上机提交最常见的几类报错与排查方法复试上机提交代码时看到红色结果第一反应不是重新乱改而是先看错误类型。我把常见的报错整理成了速查表报错类型常见原因排查方法WA答案错误思路错、边界错、编号起点错手工跑空输入、单元素、重复值、最大值用例PE格式错误多了或少了空格、换行检查每个输出字符尤其不能行尾多空格RE运行错误数组越界、空栈取顶、野指针在可疑位置加边界判断递归写法检查终止条件TLE超时算法复杂度过高、死循环估算数据范围O(nm)解法在n大时立刻换思路MLE超内存数组开得太大、递归栈过深精简数组维度合并排序等操作避免额外大数组我统计了一下自己前15题的错误记录占比最高的是WA而WA里大半来自边界条件没考虑全。比如约瑟夫环的编号加1、链表合并时空链表判断、多组输入的数据重置都是老生常谈但极易踩中的点。所以每次WA我要求自己必须写出“错在哪一组数据上”而不是笼统地说“代码错了”。5.3 我的几招备考细节最后分享几个实操细节都是这15题反复验证过有效的。第一写代码之前先写测试用例。哪怕只是草稿纸上列几条比如空输入、只有一个字符、两个链表长度差很大写完代码立刻拿这些用例跑一遍比闷头提交省时间得多。第二把输入输出模板固化下来。多组输入到EOF用while(scanf(...)!EOF)先给数据组数用scanf(%d,T); while(T--)单组输入直接读完做。这三种模板闭着眼睛都要能写出来现场再想就晚了。第三提交前检查行尾空格。很多OJ对行尾空格是判PE的输出时让“最后一个元素单独处理不要统一加空格”或者干脆用printf(%d%c, val, icnt-1 ? \n : )这种写法。第四遇到TLE先算复杂度。数据量是1e5还写O(n^2)不是代码优化能解决的必须换算法数据量很小还超时的才考虑是不是死循环。另外想说一点关于“刷题参考答案”的态度。网上确实能搜到很多OJ平台的答案包括东方博宜、郑轻OJ这些平台的题目解析参考思路没问题但复试上机考察的是你在现场独立写代码的能力只背答案等于没练。我自己的习惯是先独立写卡壳时翻思路解析看完后关掉参考重写一遍。这个“重写”的环节才是最值钱的部分。最后再分享一点个人体会刷完这15题我心里最明显的变化不是多会了几道题而是终于开始“把自己当成评测机器”了。每次代码写到最后我都会下意识地追问这里会不会越界这里如果是空串怎么办这里如果多组输入数据没重置会不会出错这些追问看起来浪费时间但恰恰是复试上机最需要的稳定感。考场上没有调试器、没有搜索引擎唯一可靠的就是平时练出来的条件反射。这个打卡系列我还会继续往下做。后面大概率会遇到排序规则的复杂输出、树的遍历、简单图论、动态规划入门这些专题等攒够了新的素材我会再按专题做一轮复盘。如果你也在刷东华复试OJ欢迎拿自己的思路来对比互相查漏补缺。备考本来就是一场持久战每天向前推进一点点坚持到考前量变自然会变成质变。
东华复试OJ每日三题：括号匹配、约瑟夫环、链表合并复盘
“东华复试OJ每日3题打卡”这个系列走到第13~15题复盘刚好是备考节奏从“适应期”切换到“稳定期”的分水岭。东华大学计算机相关专业复试是有上机环节的而且用的是传统OJ评测模式——自己写完整程序处理标准输入输出跑多个测试点不是LeetCode那种填函数的玩法。这种模式决定了很现实的一点平时刷题偷的懒考场上都会变成罚时。所以从第10题开始我给自己的要求从“把题做出来”升级成了“把题吃透”每道题至少准备两种思路卡住的地方全部记进复盘笔记。这三天我刻意挑了三种“看起来不难、写起来全是坑”的题型第13题括号匹配第14题约瑟夫环第15题有序链表合并。三个题分别对应栈、模拟/递推、链表指针正好是复试机试出镜率最高的三个方向。如果你也在准备东华复试或者准备其他学校的计算机考研机试这份复盘可以直接对照着过一遍顺便看看自己在哪些地方容易栽跟头。1. 复盘前的整体思路为什么这三天选了这三道题1.1 “每日三题”的节奏怎么定很多人备考机试容易走两个极端要么疯狂刷题一天十道做完就忘要么慢慢悠悠一天一道到考前才发现还有一半题型没见过。我试下来最适合自己的是“每日三题”这个量——一题纯基础热手一题主流考点巩固一题稍微拔高逼自己思考。三个题加起来大概两小时剩下时间全部用来写复盘笔记比盲目多刷几道更值。至于选题不能全凭心情。东华复试OJ的题风偏基础很少出偏题怪题但数据范围给的比较“老实”不像比赛题那样动不动1e5起步。所以我把选题标准定为优先覆盖栈、队列、链表、排序、递归、简单动态规划这几个高频方向每天三题尽量不重复类别。第13到15题刚好轮到了括号匹配、约瑟夫环和链表合并属于复试上机题单里的老熟人。1.2 东华OJ和杭电、郑轻这些平台到底差在哪刷题平台上手之后你会发现OJ和OJ之间的“脾气”差别挺大的。杭电OJ、郑轻OJ、杭师大OJ这些老牌ACM练习平台题面传统输入输出要求严格多组输入到EOF是家常便饭东方博宜OJ这类偏教学性质的平台题面会更温和适合大一新生打基础而东华复试OJ的风格更接近前者。这里有一个很多人忽略的点不同OJ的评测机制和处理习惯会影响你的代码习惯。比如杭电OJ上养成while(scanf(%d,n)!EOF)的手感到了东华OJ碰到“先给T组数据”的题就会条件反射地写错循环结构。所以备考时不能只刷一个平台至少要用两三个平台交叉练一方面见多识广另一方面也能提前适应复试时可能遇到的输入输出格式差异。我平时除了东华OJ还会去杭电OJ和郑轻OJ找同类题互相印证。1.3 我给自己定的几条复盘规矩复盘不是把代码贴一遍就算完我给自己定了几条硬规矩这15题下来收益很明显第一所有题先独立写一遍写不出来再看题解看完题解必须自己关掉参考重新默写一遍否则不算掌握。第二每道题必须设计至少三组“刁钻用例”比如空输入、单个元素、极限规模用来测试边界条件。第三记录每次Wrong Answer的真实原因是思路错、边界错还是格式错整理成自己的错误类型清单。第四一题至少会两种写法。比如能用数组模拟的想一想能不能用链表能用递推的想一想能不能模拟。这样考场上就算一种思路卡壳还有备用方案。这几条看起来费时间但复试上机拼的就是基础稳定性把错误模式提前暴露出来比考场上第一次见到要划算得多。2. 第13题复盘括号匹配不只会用栈就行2.1 题目与考点第13题是典型的括号匹配题。题面大致是输入一个只包含小括号、中括号、大括号的字符串判断这个字符串里的括号是否合法匹配。合法要求有两层一是左右括号数量对应二是嵌套顺序正确就是俗称的“不能交叉”。很多刷过LeetCode的人觉得这题太简单了但复试OJ上这题的通过率其实不算高。原因很简单LeetCode是函数式提交编译器帮你处理了输入输出而复试OJ需要你自己写完整程序、处理多组输入、自己判断字符串结束。难度不在算法而在把一个小算法用标准IO方式完整实现出来不出一丁点错。2.2 为什么这个题非用栈不可括号匹配天然适合用栈因为它的结构是“后出现的左括号要先匹配”。这句听起来抽象打个比方括号嵌套就像往包里塞东西最后塞进去的要最先拿出来这叫后进先出。栈正好就是这个特性。有人会问难道不能用三个计数器分别数三种括号的数量只要配平就合法吗这个思路能过一部分用例但遇到交叉括号就崩了。比如[(])左括号总数和右括号总数分别是2和2数字上是配平的可顺序是错的——中括号还没闭合小括号就插进来了。计数器根本看不出顺序问题只有栈能在每次遇到右括号时立刻去检查最近一个未匹配的左括号是不是同类型。想明白这一点这题的核心思路就算真掌握了。2.3 完整代码与逐步解析我上机用的是C的string加STL栈代码如下#include bits/stdc.h using namespace std; int main() { string s; while (cin s) { stackchar st; bool ok true; for (char c : s) { if (c ( || c [ || c {) { st.push(c); } else { if (st.empty()) { ok false; break; } if ((c ) st.top() ! () || (c ] st.top() ! [) || (c } st.top() ! {)) { ok false; break; } st.pop(); } } if (!st.empty()) ok false; cout (ok ? valid : invalid) endl; } return 0; }几个关键点说一下。遇到左括号就压栈遇到右括号先判断栈是否为空——这一步很多人会忘如果栈是空的还去取st.top()直接Runtime Error。然后检查栈顶类型是否匹配注意这里我利用了短路运算st.empty()为true时后面的st.top()不会执行所以把空栈判断和类型判断写在一起也是安全的。最后全部字符串扫完之后还要再检查一次栈是不是空的防止出现(()这种左括号多余的情况。2.4 括号匹配最容易踩的四个坑第一多组输入的循环没写好。有的题目明确说“输入多行直到EOF”有的说“第一行是数据组数T”。两种情况写法完全不同考试时先看题面描述再动手不要默认成一种模式。第二不小心用计数器代替栈。刚才说的交叉括号就是致命反例平时刷题可能碰不到到了复试考场上样例一变就现出原形。第三输入里如果包含空格cin s会按空白字符断开导致字符串被截断。如果题目明说字符串可能包含空格就要改用getline(cin, s)。括号匹配题一般不会有空格但养成先读题面的习惯很重要。第四输出格式问题。有的OJ要求输出YES/NO有的要求valid/invalid还有的要求true/false。样例只是参考真正决定代码对错的是题目描述里的输出要求严格照做别自己想当然。3. 第14题复盘约瑟夫环的三种解法考场选哪种3.1 题目是什么考的是哪个点约瑟夫环是复试OJ里的常青树。题面经典到不能再经典n个人围成一圈从1号开始报数报到m的人出列然后从下一个人重新报数问最后剩下的是几号。变体还会要求输出整个出列顺序。这个题的考点其实很综合循环结构、数组下标操作、链表操作、递推思维全都能串到一起。更妙的是不同问法对应不同最优解法如果你只会一种写法很容易在现场被卡住——所以这题值得把三种方案都过一遍。3.2 解法一数组模拟写起来最直白最直观的思路是开一个数组存活的人记为1出列的人记为0。每次从当前位置开始找下一个存活的人数到第m个就标记为0直到只剩一个人。数组模拟的代码不难写但复杂度是O(nm)——外层循环要执行n次每次都要“数”m个人。n和m都很小的时候没问题一旦n到几千、m到几千运行时间就开始肉眼可见地增长。我刷题时试过用这个解法提交小数据全过把数据范围调大后直接TLE。所以数组模拟只适合作为理解题意的工具不适合作为考场唯一方案。3.3 解法二链表模拟输出出列顺序很顺手如果题目要求输出完整出列序列链表模拟比数组模拟更自然。C里直接用list就能写不必自己实现链表循环结构。我用list写过一版#include bits/stdc.h using namespace std; int main() { int n, m; while (scanf(%d%d, n, m) ! EOF) { if (n 0 || m 0) { printf(\n); continue; } listint people; for (int i 1; i n; i) people.push_back(i); auto it people.begin(); while (!people.empty()) { for (int k 1; k m; k) { it; if (it people.end()) it people.begin(); } printf(%d , *it); it people.erase(it); if (it people.end()) it people.begin(); } printf(\n); } return 0; }这里有个细节值得强调list的erase会返回被删除元素的下一个迭代器所以it people.erase(it)是安全写法。如果先删除再用旧的it迭代器已经失效行为未定义这是C初学者最常踩的坑。循环一圈的写法是判断it people.end()就回绕到begin()这个判断必须放在每次移动之后位置不能错。整体复杂度虽然还是O(nm)但链表移动指针比数组扫描要快一些而且删人就是真删代码逻辑和题意贴合得很紧。3.4 解法三数学递推只要最终编号就选它如果题目只问最后剩下几号不需要输出出列序列那就完全没必要模拟直接用递推公式一行算出答案。这里简单展开一下推导过程。把人员编号定为0到n-1。第一个人出列后剩下n-1个人重新编号原本出列者的下一位变成新一轮的0号。设f(i)表示i个人玩这个游戏最终存活者的编号从0开始那么出列者的位置是(m-1) % i下一轮从出列者的下一位开始重新编号。通过这个映射关系可以推出f(i) (f(i-1) m) % i初始条件f(1) 0。#include bits/stdc.h using namespace std; int main() { int n, m; while (scanf(%d%d, n, m) ! EOF) { if (n 0 || m 0) { printf(0\n); continue; } int ans 0; for (int i 2; i n; i) { ans (ans m) % i; } printf(%d\n, ans 1); // 题目编号从1开始所以加1 } return 0; }这个解法的复杂度是O(n)几乎感觉不到耗时。我当时在本地把n开到100万m随便取了一个大数跑完一瞬间出结果对比之下数组模拟早就卡死了。数学解法看起来只是一行取模但它背后那套“重新编号”的思想对后面理解动态规划的状态转移也有帮助值得彻底吃透。3.5 约瑟夫环在复试现场的隐藏陷阱第一个陷阱是编号起点。递推公式从0开始编号题目从1开始编号输出时忘记加1答案就会差一位。这个错误现场极难肉眼发现因为小数据样例里可能碰巧能过换一组数据就错。第二个陷阱是m的取值。有些变体题说“报到m”但m可能是0、1甚至大于当前人数。m为0时没有意义程序直接死循环m为1时就是依次出列输出顺序等于原顺序。写代码前先把这些极端值想清楚。第三个陷阱是出列顺序和最终编号的取舍。如果题目要输出整个出列序列数学递推就不能直接用了老老实实写链表模拟如果只问最终编号用模拟就是浪费考场时间。先看问什么再选做法。4. 第15题复盘有序链表合并考的是指针基本功4.1 题目描述与考察意图第15题是经典的有序链表合并两个升序链表合并成一个新的升序链表并返回头指针。这个题在LeetCode上算简单题但在复试OJ里完全不是一回事——OJ题不会给你现成的链表结构和函数接口你需要自己定义结构体、自己构建链表、自己处理输入输出最后还要保证合并逻辑正确。这个题为什么复试爱考因为它考察的是最容易被忽略的指针基本功。结构体指针的赋值、空指针的判断、头节点的处理任何一个细节出错都很难调试。而这些东西靠死记硬背是学不会的必须亲手写、亲手踩坑。4.2 迭代法借助哑结点把逻辑变短迭代合并的思路是用两个指针分别遍历两条链表谁的值小就先接谁然后移动对应指针。这里最关键的技巧是使用哑结点。#include bits/stdc.h using namespace std; struct Node { int val; Node* next; Node(int x) : val(x), next(nullptr) {} }; Node* createList(int a[], int n) { Node* head new Node(0); // 临时头结点 Node* tail head; for (int i 0; i n; i) { tail-next new Node(a[i]); tail tail-next; } return head-next; } Node* mergeTwoLists(Node* l1, Node* l2) { Node dummy(0); // 哑结点栈上对象 Node* tail dummy; while (l1 ! nullptr l2 ! nullptr) { if (l1-val l2-val) { tail-next l1; l1 l1-next; } else { tail-next l2; l2 l2-next; } tail tail-next; } tail-next (l1 ! nullptr) ? l1 : l2; return dummy.next; } int main() { int n, m; while (scanf(%d%d, n, m) ! EOF) { int* a new int[n]; int* b new int[m]; for (int i 0; i n; i) scanf(%d, a[i]); for (int i 0; i m; i) scanf(%d, b[i]); Node* l1 createList(a, n); Node* l2 createList(b, m); Node* res mergeTwoLists(l1, l2); while (res ! nullptr) { printf(%d , res-val); res res-next; } printf(\n); delete[] a; delete[] b; } return 0; }哑结点的好处是什么呢如果不设哑结点合并后需要单独判断结果头指针到底是l1还是l2代码会多出好几个if分支。用哑结点之后所有节点都统一挂在tail-next后面最后直接返回dummy.next逻辑一下子干净了。这个技巧在链表题里出现频率极高比如删除节点、反转链表、拆分链表基本都能用上。4.3 递归法代码短但别忽略栈深度递归写法更短很多面试标准答案也是递归。代码如下Node* mergeTwoListsRecur(Node* l1, Node* l2) { if (l1 nullptr) return l2; if (l2 nullptr) return l1; if (l1-val l2-val) { l1-next mergeTwoListsRecur(l1-next, l2); return l1; } else { l2-next mergeTwoListsRecur(l1, l2-next); return l2; } }递归思路非常直观每次都把较小的节点摘出来再接上剩余部分的合并结果。但复试上机我一般不推荐优先写递归原因有两个一是递归调用会占用栈空间链表一长栈开销就上去了二是递归代码出错后调试比迭代麻烦你很难在脑子里跟完整个调用链。所以我的建议是平时练习两种都要会写考场上优先用迭代递归留给面试环节展示思路。4.4 这道题在OJ和面试里的常见延伸很多人在OJ上写链表题输入部分比合并本身还容易出错。比如输入格式是“先给n再给n个数然后给m再给m个数”读入时必须先读n再循环读n个值如果题目给的链表节点本身有序但可能有重复值合并时用还是会影响稳定性和结果正确性一般用保证相等元素的相对顺序。另外我的createList里用了一个临时头结点来简化尾插法这也是一个小技巧不然每次插节点都要特判链表是否为空。还有一个容易被追问的点是内存释放。OJ上程序退出后系统会回收所有内存所以赶时间不释放也能过但如果复试有面试环节面试官问“这段代码有没有内存泄漏”你得能答上来——创建的Node节点没有被delete工程上应当写一个freeList函数逐个释放。平时练习时养成释放的习惯面试会从容很多。顺带说一句复试面试里如果聊到C智能指针可以这样衔接传统OJ链表题为了直接考指针操作通常要求手写Node结构体并用裸指针而实际工程中链表的节点所有权可以交给unique_ptr管理能大幅减少野指针和内存泄漏。能说出这一层说明你不是只会刷题而是真的理解内存管理的差异。5. 三题横向对比与上机避坑实录5.1 三道题横向对比表刷完三题之后把它们放在一起看复习效率会更高。题号核心考点推荐方法时间复杂度最容易丢分的位置第13题 括号匹配栈、字符串边界栈一次遍历O(len)空栈取栈顶、交叉括号误判第14题 约瑟夫环模拟、递推、循环结构链表模拟或数学递推O(nm) 或 O(n)编号0/1混淆、m极端值第15题 链表合并链表指针、哑结点迭代合并O(nm)空链表、尾部拼接丢节点这份表格给我自己的提示是三题分别对应“数据结构使用”“算法建模选择”“指针操作细节”恰好是复试机试三个层面的能力。括号匹配考察会不会用现成数据结构约瑟夫环考察能不能根据题目要求选择合适算法链表合并考察能不能把基础操作写到无懈可击。备考时最好按这三个层面分别训练而不是只盯着题目本身。5.2 上机提交最常见的几类报错与排查方法复试上机提交代码时看到红色结果第一反应不是重新乱改而是先看错误类型。我把常见的报错整理成了速查表报错类型常见原因排查方法WA答案错误思路错、边界错、编号起点错手工跑空输入、单元素、重复值、最大值用例PE格式错误多了或少了空格、换行检查每个输出字符尤其不能行尾多空格RE运行错误数组越界、空栈取顶、野指针在可疑位置加边界判断递归写法检查终止条件TLE超时算法复杂度过高、死循环估算数据范围O(nm)解法在n大时立刻换思路MLE超内存数组开得太大、递归栈过深精简数组维度合并排序等操作避免额外大数组我统计了一下自己前15题的错误记录占比最高的是WA而WA里大半来自边界条件没考虑全。比如约瑟夫环的编号加1、链表合并时空链表判断、多组输入的数据重置都是老生常谈但极易踩中的点。所以每次WA我要求自己必须写出“错在哪一组数据上”而不是笼统地说“代码错了”。5.3 我的几招备考细节最后分享几个实操细节都是这15题反复验证过有效的。第一写代码之前先写测试用例。哪怕只是草稿纸上列几条比如空输入、只有一个字符、两个链表长度差很大写完代码立刻拿这些用例跑一遍比闷头提交省时间得多。第二把输入输出模板固化下来。多组输入到EOF用while(scanf(...)!EOF)先给数据组数用scanf(%d,T); while(T--)单组输入直接读完做。这三种模板闭着眼睛都要能写出来现场再想就晚了。第三提交前检查行尾空格。很多OJ对行尾空格是判PE的输出时让“最后一个元素单独处理不要统一加空格”或者干脆用printf(%d%c, val, icnt-1 ? \n : )这种写法。第四遇到TLE先算复杂度。数据量是1e5还写O(n^2)不是代码优化能解决的必须换算法数据量很小还超时的才考虑是不是死循环。另外想说一点关于“刷题参考答案”的态度。网上确实能搜到很多OJ平台的答案包括东方博宜、郑轻OJ这些平台的题目解析参考思路没问题但复试上机考察的是你在现场独立写代码的能力只背答案等于没练。我自己的习惯是先独立写卡壳时翻思路解析看完后关掉参考重写一遍。这个“重写”的环节才是最值钱的部分。最后再分享一点个人体会刷完这15题我心里最明显的变化不是多会了几道题而是终于开始“把自己当成评测机器”了。每次代码写到最后我都会下意识地追问这里会不会越界这里如果是空串怎么办这里如果多组输入数据没重置会不会出错这些追问看起来浪费时间但恰恰是复试上机最需要的稳定感。考场上没有调试器、没有搜索引擎唯一可靠的就是平时练出来的条件反射。这个打卡系列我还会继续往下做。后面大概率会遇到排序规则的复杂输出、树的遍历、简单图论、动态规划入门这些专题等攒够了新的素材我会再按专题做一轮复盘。如果你也在刷东华复试OJ欢迎拿自己的思路来对比互相查漏补缺。备考本来就是一场持久战每天向前推进一点点坚持到考前量变自然会变成质变。
