备考东华大学复试这段时间我把OJ刷题当成了每天雷打不动的固定项目。每天3道题做完必须复盘复盘完顺手记到打卡表里。现在进度走到第13~15天刚好攒下9道题、三轮完整的复盘。这篇就把这三天的记录整理出来重点不是晒刷了多少题而是复盘过程中抓到的一些共性问题——边界条件、时间复杂度、输入输出处理这些恰恰是机试丢分的重灾区。如果你也在准备复试机试或者刚开始用OJ保持手感这9道题的复盘思路应该能提供一些参考。先说结论三天的题量不算大但覆盖了栈、单调队列、二分、字符串模拟、贪心、DP这几类复试机试的高频考点。我把每道题的解题思路、提交过程中的错误、以及优化前后的代码差异都拆开讲最后再集中聊一下这三类反复出现的坑和我在机试模拟时的时间分配策略。1. 13~15天的选题思路与题目全景1.1 复试机试的考察重点决定了选题方向东华复试的OJ平台题型一直比较稳定集中在基础数据结构、字符串处理、简单数学规律和二分查找这类高频考点上。往年经验帖里反复提到的几类题目我在选题的时候会格外照顾栈和队列的应用、字符串边界处理、需要二分思想的搜索题、以及能卡着O(n)或O(n log n)复杂度完成的经典题。选题不是随便挑题做我的原则是每天至少覆盖三类考点且难度错开。比如第13天选的是带通配符的括号匹配栈、滑动窗口最大值单调队列、翻转矩阵后的得分贪心这三道恰好覆盖了数据结构、复杂线性结构、贪心模拟三个维度第15天则是二分求平方根、旋转数组最小值、最大子数组和把二分和DP放在同一天练习因为它们在思路上容易混淆放在一起对比复盘印象更深刻。1.2 三天9道题的难度分布与完成情况先看这三天题目的整体数据天数题目类型预估难度我的提交次数最终用时主要卡点第13天栈 / 单调队列 / 贪心模拟中等2 / 3 / 262分钟星号配对逻辑、队列过期判断第14天字符串压缩 / 字符串模拟 / 细节模拟中下1 / 2 / 478分钟文本对齐的条件分支第15天二分 / 二分变体 / DP中等2 / 2 / 158分钟二分边界、旋转数组比较对象三天分别对应题目编号复盘在这里。需要说明的是提交次数指最终AC前的总提交数包含了编译错误和WA我习惯把每次WA的原因记下来这个习惯在后面的复盘里发挥了很大作用。2. 三天9道题的逐题复盘2.1 第13天栈、单调队列与贪心模拟第一题带通配符的括号匹配题目大意是给定一个只包含左括号、右括号和星号的字符串星号可以被当作左括号、右括号或空字符判断字符串是否有效。这道题考的是对括号匹配本质的理解。第一次提交时我用了贪心栈匹配的思路遍历字符串时把左括号和星号的位置分别压入两个栈遇到右括号时优先用左括号栈弹出左括号栈空了才用星号栈。这样写的思路是对的但我在遍历结束后的尾部匹配环节犯了个错——处理剩余左括号和星号配对时我循环里判断的条件写成了星号位置必须在左括号位置的左边才配对完全反了。星号要充当右括号它的位置必须在左括号之后也就是starIndex leftIndex。反过来判断的话正常输入也会判断失败。这道题还有个更简单的双指针写法一个指针从左往右、一个从右往左分别记录星号作为左右括号时能否平衡。我最终用的栈做法时间复杂度O(n)空间复杂度O(n)在机试环境里完全够用。复盘的收获是括号匹配类题目的核心不只是栈还在于左括号必须被右侧的符号闭合这个位置关系别把位置关系搞反。第二题滑动窗口最大值给定一个整数数组和一个大小为k的滑动窗口要求输出每个窗口内的最大值。这道题在复试机试里出现频率很高因为能考察单调队列的理解深度。我的核心思路是用双端队列维护一个单调递减的候选最大值队列队列里存的是数组下标而不是值。入队时如果队尾元素对应的值小于当前元素就把队尾弹出保证队列从头到尾是单调递减的队头永远是当前窗口最大值。窗口滑动后如果队头下标已经离开窗口范围就出队。这道题我提交了三次才AC。第一次WA是因为我忘记在窗口形成前只推入不输出从i k - 1才开始记录结果第二次WA是过期元素清理的判断写成了q.front() i - k 1还是严格小于的问题我自己把窗口左边界弄混了。第三次就是对照正确的边界公式重推了一遍确认是if (q.front() i - k)才弹出。这里的判断在窗口右移一位后左边界恰好是i - k 1出界的下标的临界值是i - k下标等于左边界时还在窗口内所以要弹出的是小于等于i - k的。第三题翻转矩阵后的得分有一个只含0和1的二维矩阵每一步可以选择任意一行或任意一列进行翻转0变11变0。目标是让每一行解释成的二进制数的总和最大。贪心思路很直接首先把每行的第一列都想办法变成1做法是翻转第一列为0的那些行然后从第二列开始逐列统计这一列中0和1的数量如果0多就翻转这一列。这样每列的1尽可能多整体数值最大。我的踩坑在遍历顺序上。处理第一列时是按行遍历处理后续列时是按列遍历我在一处套循环里把行列索引写反了导致翻转操作作用到错误的位置。这类模拟题不需要复杂算法就怕条件分支一多就手滑。建议遇到矩阵翻转的题先画一个3x3的小矩阵手动推演一遍流程再写代码实际上反而更快。2.2 第14天字符串处理与模拟细节第四题字符串压缩给定一个只含字母的字符串把连续重复的字符压缩成字符出现次数的形式比如aaabbc压缩成a3b2c1如果压缩后的字符串不比原串短则返回原串。我一次AC了但这道题值得复盘的点在于边界。统计连续字符时循环结束有两种情况一是遍历完了整个字符串二是遇到了新的字符。很多人写这类题目时容易漏掉遍历结束后的最后一次收尾处理也就是最后一个连续字符组还没写入结果。我的习惯是外层用while (i n)内层用while (j n s[j] s[i])统计相同字符的数量这样收尾逻辑天然被包含在内层循环里不会漏。另外题目明确要求压缩后长度对比如果没变短就返回原串。这个判断很容易被忽略因为很多类似题目默认压缩后一定更短。但类似abc这样的串压缩成a1b1c1反而变长了所以要记得比较目标串和源串的长度。第五题最长公共前缀变种这个变形比原版有意思给定一组字符串不只是求公共前缀还要求如果存在多个答案时输出字典序最小的那一个。我第一轮提交就WA了。原因是我先求了公共前缀然后直接输出忽略了题目要求的字典序最小。原版最长公共前缀比较常见的写法是纵向扫描取第一个字符串作为基准逐个字符与其他字符串的同位置字符比较一旦不匹配就截断。这个思路本身没问题但变形题里如果公共前缀是空的或者存在多个长度为0的答案空串字典序最小的就是空串。我第一次从空串的角度想以为所有空串答案都一样结果题目要求返回空串但我的代码返回了和string()混用某些环境下出现了输出格式的差异。这类字符串题最容易栽在题目理解上而不是算法上。建议AC之后把题目要求重新读一遍确认你对最小的定义和判题程序一致。第六题文本左右对齐给定一组单词和一个每行最大宽度要求实现文本左右对齐每行尽可能放入多的单词单词之间用空格隔开最后一行需要左对齐且任何相邻单词之间至少一个空格空格均匀分布在单词间。这是三天里我提交次数最多的题4次提交里有3次WA全部集中在两个地方一是空格分配的逻辑二是一行最后一个单词后面的多余空格处理。我的做法是先贪心收集每行能放下的单词计算单词总长度和需要的空格数然后计算多余空格怎么均分和余数怎么分配。题目要求空格尽可能均匀分布也就是前几个间隙各多分一个空格。这里要注意整除和取余的顺序。还有一个隐藏坑是最后一行左对齐。最后一行本来就不需要左右对齐分配直接把单词按顺序拼起来、尾部补空格到最大宽度即可。我第三次WA就是因为没判断当前是不是最后一行导致最后一行的空格被均分得乱七八糟。这类题的调试技巧是拿题目给的长样例一句一句比对我当时就是把期望输出的空格位置打印出来逐项对照才定位到问题。2.3 第15天二分边界与DP第七题求平方根给定非负整数x返回它的整数平方根也就是满足i * i x的最大整数i要求不能用内置的平方根函数。这道题几乎就是二分查找的模板题。区间设在[0, x]二分查找最后一个平方小于等于x的数。我的第一次提交WA在二分循环条件的写法上之前我习惯写while (left right)但这道题找的是右边界最后一个满足条件的位置应该用while (left right)在mid * mid x时直接返回在mid * mid x时把left更新为mid 1并记录答案在mid * mid x时把right更新为mid - 1。一个隐蔽的细节是mid * mid可能溢出int范围x最大可以到2^31 - 1mid取到46340以上时平方就超过int了。所以mid要用long long计算或者把乘法类型显式转成long long。这道题我第二次AC就是因为加了类型转换。第八题寻找旋转排序数组中的最小值一个升序排列的数组在某个未知的点上进行了旋转比如[4,5,6,7,0,1,2]要求找出最小元素。数组中没有重复元素。核心是利用旋转数组的部分有序性。最小值右侧的所有元素都小于最右元素nums[right]最小值左侧的所有元素都大于nums[right]。所以二分时拿nums[mid]和nums[right]比较如果nums[mid] nums[right]说明最小值在中点的右侧否则最小值在中点及中点左侧。这里我犯的错误是拿nums[mid]和nums[0]比较结果当最小值在数组中间位置时出现了边界误判。用最右端元素作为基准是因为旋转点右侧一定是递增的而且比左侧所有元素都小用它做锚点二分才能稳定向最小值收缩。第九题最大子数组和给定整数数组找到具有最大和的连续子数组返回最大和。经典的Kadane算法核心是动态规划思想dp[i]表示以第i个元素结尾的最大子数组和状态转移是dp[i] max(nums[i], dp[i - 1] nums[i])也就是要么自己单开一段要么接在前面的子数组后面。我一次AC但复盘时我特意把朴素的三层循环和Kadane做了对比因为机试里经常有人看到连续子数组最值就先写暴力结果数据一大就超时。这道题的数据规模如果到10^5O(n²)的暴力必然TLEKadane的O(n)才是正解。另外要注意返回的是最大子数组和而不是子数组本身某些类似的变种题要求输出起点终点那种题需要额外记录状态转移发生的位置别搞混。3. 9道题里反复出现的三类错误与避坑清单3.1 边界条件循环里的等号和临界下标的判断三天里我遇到的WA粗略统计一下超过一半是边界条件问题。具体来说有这几类二分循环的收敛条件while (left right)和while (left right)处理的是不同类型的边界前者天然跳出时left和right重合后者退出时left在right右边。做题前先想清楚题目要找的是第一个满足条件还是最后一个满足条件再决定循环怎么写。窗口类问题中下标的临界值以滑动窗口最大值为例窗口左边界是i - k 1所以下标小于等于i - k的元素要弹出。临界值差1结果完全错误。区间闭合与开区间求平方根的mid * mid x和 x虽然只差一个等号但决定你取的是下界还是上界。我给自己的建议是每一道题提交前在代码注释里写清楚三个边界值循环什么时候停、左边界怎么移动、右边界怎么移动。写注释的过程等于强制自己把临界条件梳理一遍很多WA能在提交前就被拦下来。3.2 时间复杂度从O(n²)到O(n)的优化思路第13天的滑动窗口最大值第一次我尝试的是每个窗口内遍历一遍找最大值复杂度O(n*k)数据一冲到10^6直接TLE。改成单调队列后就降到O(n)。第15天的最大子数组和暴力三层循环和Kadane的对比也是同理。机试和平时刷题最大的区别是数据范围往往藏在题目描述里不显眼的位置暴力解法也许在小数据量下能过但一旦用了多组输入O(n²)就很容易崩。我的建议是养成拿到题目先看数据规模的习惯以n10^5为分界线超过这个量级基本可以排除O(n²)级别的算法如果n是10^4O(n log n)比较稳妥只有n在10^3以内O(n²)才能考虑。这三天的题目里滑动窗口最大值、旋转数组最小值、最大子数组和都可以从暴力优化到线性或对数复杂度复盘时我把每一道题的暴力版本和优化版本都保留了一份目的就是给自己建立优化敏感度。3.3 多组输入与输出格式的隐性考点东华的OJ平台不少题目是多组输入也就是持续读取直到EOF。很多第一次接触OJ的人会栽在这里以为只有一组数据读完直接输出结果判题错误。处理多组输入的模板我很早就固定下来比如读整数直到EOF#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; while (cin n) { // 对每组输入做处理输出结果 } return 0; }如果是字符串行用while (getline(cin, line))注意前面用cin n读掉整数后会残留换行符需要先用getline吃掉。这个细节我在第14天的字符串题目里踩过一次读完了n但后面的getline直接读到空行导致结果全错。输出格式方面注意题目要求的是每个结果占一行还是结果之间用空格分隔以及最后一行是否需要换行。这类问题不会影响算法本身但会直接造成Presentation Error在机试里同样要被扣分。我的习惯是AC之后故意把输出末尾的换行情况测试一遍确保不因为格式丢分。4. 从第13~15天的复盘反推机试时间分配策略4.1 每日闭卷限时训练的具体方法打卡不能只是做了题我给自己定的规则是第13天开始强制模拟机试状态每天3道题必须闭卷完成不限语言我用C限时60分钟到点停笔。这比平时练习更能暴露问题。实际操作中每天的节奏是这样的先快速扫一遍三道题的题面给每道题标注一个预估难度值简单/中等/较难然后从最简单的一道入手。第13天我用了62分钟超时2分钟第14天78分钟明显超时第15天58分钟回到限时内。时间的起伏其实反映了题目的模拟复杂度和我对字符串题的陌生程度。限时训练的意义不是逼自己手速而是模拟考场上的决策顺序。我个人的策略是如果一道题思考超过12分钟还没理出思路就暂时跳过先做后面的题最后再回头。机试的判题规则通常按通过用例数量给分一道题卡死导致后面简单题没时间做是最大的策略失误。4.2 考场做题顺序和耗时预估的复盘修正第14天的复盘让我意识到字符串和模拟题虽然算法难度不高但细节分支多实际耗时往往超过预期。我在文本左右对齐上花了接近30分钟这在考场上是很危险的。结合这三天的数据我重新调整了自己的考场策略题型预估耗时上限遇到卡壳的处理简单模拟/基础字符串15分钟超过20分钟直接跳过数据结构栈/队列/链表12分钟超过15分钟标记后跳过二分/DP/贪心15分钟超过20分钟重新读一遍题面复杂模拟20分钟只在其他题全部做完后尝试第15天三道题能在58分钟内完成一个重要原因就是我先用二分思路解决了两道把最大子数组和这类DP题放在最后因为Kadane算法写起来很快正确的做题顺序本身就在节省时间。4.3 复盘时的错题时间线记录法每天打卡结束后我会单独花15到30分钟做复盘但不是简单地看一遍正确答案。我的记录表格式长这样日期第13天 题号1括号匹配WA 1次原因——结束配对阶段位置判断反了修正后AC 题号2滑动窗口WA 2次原因——过期下标临界值差1窗口左边界算错 题号3翻转矩阵WA 1次原因——行列索引写反翻转作用位置错误记录的重点不是我错了什么而是为什么我的思路会在这一步走偏。比如滑动窗口的过期判断错的本质是我对窗口左边界这个概念的动态变化不敏感后来专门用纸笔画了一次窗口滑动的过程把下标变化写出来才彻底记住。这个记录法会在后续复习时直接变成我的考前错题本。5. 复盘方法论让每天的3道题产生复利5.1 一次有效的复盘包含的四个环节打卡的真正价值在于复盘。第13~15天的复盘我把它拆成四个环节第一步重看每道题的WA记录找出错误代码和正确代码的具体差异不只改对还要分析为什么原来的写法会踩进去。第二步把同一类型的题横向对比。比如第13天的滑动窗口最大值和第15天的旋转数组最小值都和部分有序下的最值查找相关但一个用单调队列、一个用二分放在一起看就能搞清楚什么场景选哪个数据结构。第三步把每道题的时间复杂度和数据范围标注清楚。这个步骤是为了训练拿到题先估算量级的直觉避免暴力思维。第四步把错题中加入自己写的一段注释用一句话说明这道题最需要注意的坑。比如我在滑动窗口最大值那题的注释里写的是过期判断下标左边界-1时弹出队列存坐标不存值。这个注释以后复习时扫一眼就能回忆起整个坑。5.2 每天3题的打卡节奏为什么不需要再加量很多人在备考时会陷入刷题量越大越安心的心态但比起量稳定性和复盘质量更重要。每天3题看起来不多但它能保证一个可持续的节奏——不需要熬夜不需要占用大块整时间碎片时间拆开就能完成而且每道题都有时间做完后认真复盘。我在第13到15天特意保持这个节奏没有因为某天状态好就加到5道题。原因是状态好的时候加量状态差的时候就会产生负罪感反而容易中断打卡。保持每天3题连续打卡的惯性比一时冲量更宝贵。第15天结束的时候我已经能明显感觉到对二分类题目的边界判断速度快了很多这就是复利效果。5.3 给同样在准备复试机试的你的实操建议如果你也在用OJ刷题准备复试从这三天的复盘里可以直接抄作业的几条选题尽量覆盖不同考点不要一天只做数组题或只做字符串题机试考察的是综合能力。每道题提交后无论AC还是WA都花5分钟记录一下思路和卡点养成记录习惯。每周固定挑一天把本周所有错题重新做一遍。第13~15天的错题我计划在下周第一个打卡日重做这比只做新题有用得多。模拟机试时提前确认好OJ平台的输入输出格式要求因为平时练习的平台和考试平台可能存在细微差异比如是否需要处理到EOF、是否允许bits/stdc.h头文件等这些细节建议提前确认清楚。东华复试的OJ机试不考偏题怪题重点就是把基础数据结构和常见算法理解透彻能够在限定时间内稳定输出正确代码。这三天的9道题里没有一道需要非常高深的知识储备但每一道都在考你能不能把这套基础方法用得干净利落。每天3题打卡的意义就是在反复锤炼这个基本盘。