东华复试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) { stack<char> 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; } list<int> 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 三道题横向对比表

刷完三题之后，把它们放在一起看，复习效率会更高。

这份表格给我自己的提示是：三题分别对应“数据结构使用”“算法建模选择”“指针操作细节”，恰好是复试机试三个层面的能力。括号匹配考察会不会用现成数据结构；约瑟夫环考察能不能根据题目要求选择合适算法；链表合并考察能不能把基础操作写到无懈可击。备考时最好按这三个层面分别训练，而不是只盯着题目本身。

5.2 上机提交最常见的几类报错与排查方法

复试上机提交代码时看到红色结果，第一反应不是重新乱改，而是先看错误类型。我把常见的报错整理成了速查表：

我统计了一下自己前15题的错误记录，占比最高的是WA，而WA里大半来自边界条件没考虑全。比如约瑟夫环的编号加1、链表合并时空链表判断、多组输入的数据重置，都是老生常谈但极易踩中的点。所以每次WA，我要求自己必须写出“错在哪一组数据上”，而不是笼统地说“代码错了”。

5.3 我的几招备考细节

最后分享几个实操细节，都是这15题反复验证过有效的。

第一，写代码之前先写测试用例。哪怕只是草稿纸上列几条，比如空输入、只有一个字符、两个链表长度差很大，写完代码立刻拿这些用例跑一遍，比闷头提交省时间得多。第二，把输入输出模板固化下来。多组输入到EOF用while(scanf(...)!=EOF)，先给数据组数用scanf("%d",&T); while(T--)，单组输入直接读完做。这三种模板闭着眼睛都要能写出来，现场再想就晚了。第三，提交前检查行尾空格。很多OJ对行尾空格是判PE的，输出时让“最后一个元素单独处理，不要统一加空格”，或者干脆用printf("%d%c", val, i==cnt-1 ? '\n' : ' ')这种写法。第四，遇到TLE先算复杂度。数据量是1e5还写O(n^2)，不是代码优化能解决的，必须换算法；数据量很小还超时的，才考虑是不是死循环。

另外想说一点关于“刷题参考答案”的态度。网上确实能搜到很多OJ平台的答案，包括东方博宜、郑轻OJ这些平台的题目解析，参考思路没问题，但复试上机考察的是你在现场独立写代码的能力，只背答案等于没练。我自己的习惯是：先独立写，卡壳时翻思路解析，看完后关掉参考重写一遍。这个“重写”的环节才是最值钱的部分。

最后再分享一点个人体会

刷完这15题，我心里最明显的变化不是多会了几道题，而是终于开始“把自己当成评测机器”了。每次代码写到最后，我都会下意识地追问：这里会不会越界？这里如果是空串怎么办？这里如果多组输入数据没重置会不会出错？这些追问看起来浪费时间，但恰恰是复试上机最需要的稳定感。考场上没有调试器、没有搜索引擎，唯一可靠的就是平时练出来的条件反射。

这个打卡系列我还会继续往下做。后面大概率会遇到排序规则的复杂输出、树的遍历、简单图论、动态规划入门这些专题，等攒够了新的素材，我会再按专题做一轮复盘。如果你也在刷东华复试OJ，欢迎拿自己的思路来对比，互相查漏补缺。备考本来就是一场持久战，每天向前推进一点点，坚持到考前，量变自然会变成质变。