东华复试OJ的每日3题打卡我坚持了整整35天。第29天晚上刚好做到题库里的第85、86、87题当天复盘写完已经是凌晨。回头翻这三天的记录发现正好覆盖了链表、栈、并查集三种完全不同的数据结构考察方式而且每道题都踩了不同类型的坑。这篇就把这三道题的复盘过程完整摊开顺便聊聊我在东华复试OJ上摸出来的刷题和排错经验。它适合正在准备复试机试的考生也适合所有刷OJ时总觉得自己“刷了不少但碰到新题还是没底”的人。1. 复试备考期的每日3题打卡我是怎么安排和记录的先说打卡这件事本身。很多人对“每日3题”有误解觉得数量太少不如一天刷十道来得爽。我一开始也试过一天七八道结果三天就撑不住了后面几天做题完全是在赶进度遇到不会的题直接翻题解抄一遍抄完脑子还是空的。后来把节奏降下来改成每天固定3道题才真正找到状态。3道题这个数字不是拍脑门定的。它可以拆成“1道新题型 1道旧题型巩固 1道综合题”。新题型用来扩展知识面旧题型用来保持手感综合题用来训练把多个知识点串起来的能力。数量再多一点当天晚上就没有足够时间做深度复盘再少一点又容易陷入“今天刷了一道明天不想刷”的惰性里。我的时间安排大致是这样时间段内容说明早上8:00-8:30看昨天的复盘文档快速过一遍错题重点看WA原因和代码里的坑上午10:00-12:00做第一道题通常是新题型不急着写码先花10分钟理思路下午14:00-16:00做第二道和第三道题第二道巩固旧知识第三道综合性较强晚上21:00-21:40三题统一复盘并归档写题解、记录错误原因、对比最优解这个节奏看起来慢但35天下来我的做题量是105道每一道都留下了完整的复盘记录。相比之下之前那种“一天十道”的方案看似量大真正消化吸收的可能一半都不到。复盘文档我放在Git仓库里每天新建一个Markdown文件命名格式是DayXX-题号范围.md。文档里固定有四个小标题考点标签、我的解法和标准思路的差异、WA原因、至少一种其他解法。这个结构让我后来检索错题非常方便比如我想找“链表题里我踩过哪些坑”直接搜标签就能把相关的复盘记录全部捞出来。另外要提一点东华复试OJ的风格和杭电OJ、郑州轻工业大学OJ这些公开平台不太一样。它的题面通常很短不会给你一大段背景故事很多时候就是一句话加一个输入输出约定数据范围也写得比较含蓄。这意味着你必须主动去判断这题在考什么而不是等题面把考点喂到你嘴里。后面我说的三道题都有这个特点。2. 第85题删除无序链表重复节点读题比写码更重要第85题的题面非常简单给定一个无序单链表删除链表中值重复的节点保留第一次出现的那个。示例是1 - 2 - 3 - 2 - 4变成1 - 2 - 3 - 4。这种题在面试里也很常见但在OJ上完全不是一回事。面试你可以嘴上说“用哈希表记一下就行”代码写不写得出来无所谓OJ要求的是你写出一段能直接编译、跑通所有隐藏数据的完整代码。2.1 三个隐藏条件决定了你的代码长什么样我花在“读题”上的时间比写代码多得多。第一件事是确认链表里的元素值范围。题面没给但根据经验这种链表题的值域一般不大用布尔数组做哈希就能搞定。第二件事是确认要保留一个还是全部删除。有些题考的是“重复节点全部删掉只留下从未重复的节点”那种题的写法完全不同。这道题是保留第一个所以只需要在遍历时判断当前节点的值是否出现过。第三件事最容易被忽略如果头结点本身就是重复值怎么办比如2 - 2 - 3删完之后应该是2 - 3。如果你不用哑结点删除头结点时就要单独写一段特判逻辑代码会很丑而且容易漏。我一开始就没用哑结点结果提交后WA了一次查了半天才发现是头结点重复的情况没处理干净。后来学乖了所有链表题一律先建一个dummy结点指向头结点。2.2 C语言实现里的几个关键点这道题我用C语言写的最终的删除逻辑是这样struct ListNode { int val; struct ListNode *next; }; struct ListNode* deleteDuplicates(struct ListNode* head) { if (head NULL) return head; bool seen[10005] { false }; struct ListNode *dummy (struct ListNode*)malloc(sizeof(struct ListNode)); dummy-next head; struct ListNode *pre dummy; struct ListNode *cur head; while (cur ! NULL) { if (seen[cur-val]) { pre-next cur-next; struct ListNode *tmp cur; cur cur-next; free(tmp); } else { seen[cur-val] true; pre cur; cur cur-next; } } head dummy-next; free(dummy); return head; }这里pre指针一直指向当前已保留链表的最后一个节点cur负责往前走。当cur的值已经出现过时跳过并释放它否则标记值并同时移动pre和cur。dummy节点的作用用一句话说清楚它让“删除头结点”这个操作退化成普通的删除操作代码不需要为头结点单独写if分支。2.3 踩坑记录free之后别再碰指针这道题我踩的第一个坑是放节点顺序错了。一开始我写的是if (seen[cur-val]) { pre-next cur-next; free(cur); cur cur-next; // 错cur已经被free了 }先free(cur)再cur cur-next实际上是在访问已经释放的内存。这个错误在本地小数据测试时可能看不出来因为cur-next的值还残留在内存里运气好还能读到但OJ的测试一多什么奇怪现象都可能出现有时候是答案错有时候是运行时崩溃。正确做法是先把next存下来或者像上面代码那样在释放之前完成cur的移动。这类问题用valgrind在本地能查出来但复试考场上没有工具所以写的时候就要养成习惯释放指针之后这一行之内不允许再对它做任何解引用操作。第二坑是布尔数组的大小。题面没有给值的范围我一开始只开了bool seen[100]遇到一个值大于100的测试用例直接越界。后来我改成10005因为复试OJ里链表节点的值域通常不会超过这个量级但如果你不确定更稳的方案是用哈希表或者先遍历一遍链表找到最大最小值再定数组大小。2.4 为什么不用二重循环二重循环的思路简单粗暴对每个节点往前扫描有没有值相同的节点有就删掉。时间复杂度O(n²)代码量更少。如果链表长度只有几百这个方案也能过。但我还是建议用数组标记加一次遍历的O(n)方案。理由有两个一是复杂度本身是一个考察点复试机试的判分员如果看到O(n²)解法即使通过了也可能影响印象分二是空间复杂度并没有因此变高一个布尔数组在题目的数据范围内完全可以接受。这道题就是典型的“用一点空间换时间”还换得特别值的情况。3. 第86题中缀表达式求值真正拉开分数差距的是边界处理第86题是一道非常经典的数据结构应用题中缀表达式求值。输入一个包含非负整数、 - * /和括号的表达式输出计算结果。示例是3(6-2)*48/2输出23。这道题在复试OJ里出现频率很高因为它把三个考点一次性打包数字解析、运算符优先级比较、括号匹配。你背过栈的模板不代表你能写对实际写起来很多细节都是在边界条件上翻车的。3.1 双栈框架为什么需要两个栈核心思路是维护两个栈一个数字栈、一个运算符栈。扫描表达式时遇到数字解析完整的多位数并压入数字栈。遇到左括号直接压入运算符栈。遇到右括号不断弹出运算符栈顶并计算直到遇到左括号最后把左括号弹出。遇到普通运算符如果栈顶运算符的优先级大于等于当前运算符就先出栈计算否则直接把当前运算符入栈。表达式扫描完后把运算符栈里剩下的运算符全部弹出来计算。优先级“大于等于”这个细节很关键。2-34这种表达式按数学的优先级和-是同级的。因为运算从左往右结合所以遇到后一个时应该先把前面的-算掉否则会先算34再算2-7结果就错了。所以比较的时候用而不是。我用C语言写的大致框架是这样int priority(char c) { if (c || c -) return 1; if (c * || c /) return 2; return 0; } int calc(int a, int b, char op) { if (op ) return a b; if (op -) return a - b; if (op *) return a * b; if (op /) return a / b; return 0; }数字栈和运算符栈都用数组实现C语言栈顶指针维护好就行。3.2 多位数解析是第一个WA来源题目给了示例3(6-2)*48/2你可能会想当然地以为每个数字都是一位数。但隐藏测试用例里必然有多位数比如233100。如果按字符一位一位处理解析出的就是2、3、3三个数字结果全错。正确的解析方式是在主循环里遇到数字字符时用while循环连续读完后面所有数字字符if (s[i] 0 s[i] 9) { int num 0; while (i len s[i] 0 s[i] 9) { num num * 10 (s[i] - 0); i; } i--; // 因为外层for循环还会再i pushNum(num); }这里的i--是很容易漏的一行。外层有一个for循环每轮结束会自动i内部while已经把i推到了最后一个数字字符的下一个位置如果不减回来外层再i会跳过一个字符。这种细节写的时候不注意调试半天才能发现。3.3 括号处理弹出到左括号为止但左括号不入栈也不参与计算右括号的处理逻辑是不断弹出运算符栈顶并计算直到栈顶是左括号然后把左括号弹出。这里有个常见的错误写法是把左括号也当作普通运算符参与优先级比较。实际上括号的优先级是特殊的它只负责在函数调用时设置一个“计算边界”本身不参与任何运算。我因为括号WA过一次。当时表达式是(23)*(45)我的代码在遇到第一个)时把(弹出但忘了把之前23的计算结果压回数字栈后还要继续把(也从运算符栈里弹出来。结果下一次循环里运算符栈顶还是(优先级函数返回0导致栈顶运算符比较的逻辑全乱了。3.4 负数和除法取整复试OJ的隐藏机关这道题我复盘时发现至少有三种变体。第一种是表达式里可能出现负数比如-53。这种题最省心的做法是在预处理时把-和作为单目运算符处理或者更暴力一点把表达式里的-x手动替换成(0-x)。虽然不优雅但确实能避开大量边界问题。第二种是除法要求结果向零取整。C语言里/运算对正数是向下取整对负数是向零取整的。如果中间结果出现负数行为可能不符合预期。好在当时题目里明确写了“中间结果均为整数”否则我得把int改成double再用floor或ceil处理。第三种是输入里混有空格和中英文括号。复试OJ的题面有时不太规范但输入数据一般不会有中文字符。我习惯在主循环里直接跳过空格防止gets或fgets把空格读进表达式。4. 第87题并查集连通块问题模板题反而最考验细节第87题是并查集题面是有n个点和m条边每条边连接两个点问最终这些边把所有点分成了几个连通块。n的范围没写但根据复试OJ的调性大概在1000到100000之间。说实话我刷到这道题之前只是知道并查集这个概念从没完整手写过一遍。这道题属于“模板题”但模板题恰恰最容易在细节上翻车。4.1 并查集的三个核心操作少一个都不行并查集本质上做的事情就是维护一堆集合支持两个操作查一个元素属于哪个集合、合并两个集合。代码核心就三块int parent[MAXN]; // 初始化每个元素自成一个集合 void init(int n) { for (int i 1; i n; i) parent[i] i; } // 查找找到根节点 int find(int x) { while (parent[x] ! x) { parent[x] parent[parent[x]]; // 路径压缩 x parent[x]; } return x; } // 合并两个集合的根节点相连 void unionSet(int a, int b) { int ra find(a); int rb find(b); if (ra ! rb) parent[ra] rb; }4.2 路径压缩的递归与非递归递归版的find很简洁int find(int x) { return parent[x] x ? x : parent[x] find(parent[x]); }但并查集有一种极端情况合并顺序是1-2、2-3、3-4……如果查找时全部走递归版递归深度会达到n在n比较大的时候会爆栈。虽然复试OJ的n一般不会大得离谱但谁也说不好有没有极端数据。我采用的写法是迭代版路径压缩也就是上面4.1里那种。它的思路是在往上找根节点的过程中顺手把经过的节点直接挂到祖父节点下面这样下次查找就快很多。复杂度近乎O(1)而且不会有爆栈风险。4.3 统计连通块的两种方式题目要求的是连通块个数。有两种做法第一种是在读入边的时候就维护一个cnt变量初始为n每成功合并一次就减一。这种方式的好处是最后直接输出cnt不用再遍历一次。第二种是全部合并完成之后遍历所有节点统计parent[i] i的个数。注意这里必须调用find(i)而不是直接看parent[i]因为路径压缩可能没有完全压缩所有节点直接看parent[i]会统计错误。我是用第二种方式做的因为它更直观而且不需要在union函数里额外处理计数逻辑。统计完发现有个细节如果节点编号是从0开始还是从1开始直接影响初始化和遍历范围。题目给的示例节点是1到n但为了保险我在读题时特意确认了输入说明。4.4 并查集题目的变化动态合并和离线查询复试OJ很少只考裸模板一般会套个壳。比如这题就是“问连通块数量”有的变体会问“加完某条边之后还有几个连通块”有的变体会问“两个点之间是否连通”。本质上都是并查集但答题方式略有差别问连通块数量维护计数或最后遍历。问两点是否连通只要find(a) find(b)不需要额外操作。跳过无效边合并时如果ra rb说明这条边没用不执行合并。我复盘的时候专门把这几种变体写在同一页笔记里因为它们的代码差别很小唯一要改的就是统计部分的逻辑。把模板吃透了变体题其实就是换皮。5. 三题连做后的复盘动作把刷题量变成算法直觉三天的题目做完真正的成长发生在复盘阶段。如果你刷题只是“做对就过做错就改”刷一年可能都很难形成算法直觉。下面是我自己的复盘动作供参考。5.1 每道题只写三句话我不重抄代码而是要求自己用三句话把这题讲清楚题目在问什么一句话说清楚。我用的核心数据结构和方法是什么。我的解法和标答思路最大的差异在哪里。比如第85题我写的是题目要删除无序链表中的重复节点核心是一个标记数组加dummy节点答解法和标答差异在于我用数组缓存了访问过的值而不是每步都往前扫描。这三句话看起来很朴素但写下来之后你会发现很多题其实是同一个模型的变形。比如第86题的“两个栈按优先级计算”和第87题的“合并时判断是否同根”它们本质上都是“用一个维护状态的容器把运算过程组织成有序步骤”。5.2 统计WA原因而不是统计AC数量我连续记录了三天的WA原因发现自己的错误来源非常集中错误类型出现次数典型例子边界条件没处理6次空链表、只有一个节点、节点编号从0开始数组开小或越界4次布尔数组只开到100值域过了100就崩输入读取方式错误3次多组数据和单组数据搞混逻辑判断马虎5次写成、写成||这种统计比“我AC了25道题”更能反映问题。边界条件频繁出错说明我读题时对边界情况不够敏感数组开小说明没把题面里没有明说的数据范围当回事。后来我在每道题提交前都会做一个checklist空输入、最大数据、最小数据、单点数据。这个习惯就是从这次统计之后养成的。5.3 当天晚上必须做一道同类题验货复盘还不够我会在当天晚上或者第二天找一道和当天题型相同但难度稍高的题做验证。比如第85题是链表去重我第二天就找了一道“删除链表倒数第k个节点”来练虽然它们考察的具体操作不一样但dummy节点、双指针这些技巧是通用的。第87题也是如此第二天我做了一道“判断图中两个点是否连通”的题本质上就是并查集的find操作套了个图论的壳。当场验证的好处是能立刻检验前一天的复盘到底有没有沉淀下来。如果第二天的同类题还是卡住说明前一天只是“看懂”了没到“会写”的程度。5.4 这一轮复盘让我的刷题状态发生了什么变化从第85到87题这个区间开始我发现自己的解题速度有了明显提升。以前读题要琢磨很久才知道用什么算法现在看到“删除重复节点”能马上想到哈希或标记数组看到“表达式求值”能自动脑内跑一遍双栈流程看到“连通分量”会第一时间检查是否能用并查集。这个转变靠的不是“看更多题”而是“把看过的题真正内化”。每一道题复盘时不急着开下一道先把当前题吃透短期看效率不高长期看反而节省了大量重复试错的时间。6. 东华复试OJ上的隐形扣分点本地调试看不出、一提交就崩最后汇总一下我在整个复试OJ刷题过程中遇到的隐形坑这些坑不会在本地编译时报错但一提交就可能WA、TLE或者RE。第85到87题期间我至少踩了其中四个。6.1 多组数据与单组数据的读取方式OJ题目经常不明确说“这题只有一组数据”。我一开始按照单组数据写提交后部分测试点通过、部分报错原因就是题目实际上有多组输入直到EOF。后来我养成了一个默认习惯所有输入都用while (scanf(...) ! EOF)或者while (fgets(...) ! NULL)包起来。while (scanf(%d, n) ! EOF) { // 处理一组数据 }这样做的好处是单组数据的题也不会出错多组数据的题直接兼容。6.2 老编译环境下慎用gets和这类危险函数有些OJ的C编译环境比较保守。我第一次用gets()读字符串时本地编译没报错提交后编译器直接给出了warning虽然没有整体判定为编译错误但某些严格要求的环境可能直接CE。我后来统一换成fgets()并手动去掉末尾的换行符char s[1005]; while (fgets(s, sizeof(s), stdin)) { s[strcspn(s, \n)] 0; // 处理s }这也符合现代C编码规范免得在考场上因为一个函数名被卡脖子。6.3 数组开太大导致MLE开太小导致越界第85题我的布尔数组最开始只开了100因为示例里的数都是个位数。隐藏数据里出现一个100以上的值数组越界后行为不可预测可能WA也可能RE。开数组的正确姿势是先看题面数据范围如果没写就按常见的1005或10005开并预留一点余量。但也不是越大越好如果你随手开一个一千万的int数组内存约40MB复试OJ的内存限制如果比较紧可能直接MLE。这里可以用short或者bool类型减小内存占用但最关键的还是心中有数。6.4 没有终止条件的递归是TLE的隐藏来源有一道题我在本地跑很快提交后却TLE。查了半天发现是递归函数里少了一个终止分支导致某个特殊输入下函数无限递归。本地测数据量小栈没有爆循环次数也少所以看不出来OJ的测试数据一上来递归次数指数增长直接超时。调试这种问题最好的办法是构造极端数据n1、nmax、输入为空、单字符、无重复、全重复。把这几组用例提前跑一遍再提交可以拦截掉大部分隐藏问题。6.5 提交前的五分钟自查清单我后来整理了一份提交前必查清单全部过一遍再交输入读取是否兼容多组数据数组大小是否覆盖题面给出的最大值链表为空时函数是否直接返回递归函数是否有明确的终止条件重点运算符比较用的是还是是不是符合左结合所有变量在使用前都完成初始化了吗free完的指针还有没有在后续代码中被访问这份清单看起来琐碎但复试OJ的题目通常本身不难大家比起谁能写出算法往往是比谁的代码更稳、更能扛住隐藏用例。第85到87题这三天的复盘让我意识到真正的差距往往就藏在那些平时不注意的边界条件和输入输出约定里。把这些细节处理好刷题才会越来越顺。
