复试OJ冲刺：每日三题复盘，吃透排序二分、字符串与DP

1. 复试OJ冲刺阶段为什么我选择每天固定3题而不是一把梭说句实在话考研复试的机试准备最怕的就是两种极端一种是前期跟打了鸡血一样一天刷十道二十道坚持不了一周就熄火另一种是漫无目的地翻题单看到哪道做哪道刷了两个月回头一看会的还是会不会的还是不会。我备考某高校计院复试的时候给自己定了一个特别死板的规矩——每天雷打不动3道题做完随手复盘。这个节奏从第1天一直跑到第25天中间只因为某天身体实在撑不住断过一次。现在已经进行到第19到21天的阶段复盘趁着这三天题目组里出现了好几道值得反复咀嚼的经典变体我把整体思路、踩坑过程、以及“每天3题”这个机制怎么运作的一次讲清楚。先解释一下这个“每日3题”背后的逻辑。复试OJ和平时自由刷题不一样它有明确的时间边界一般在半小时到两小时之间平台多为某校自研的在线评测系统题目风格偏向基础算法加一点思维难度不会出偏题怪题。每天3题这个数量是我测试出来的最优值——太少没有训练量太多就会挤占专业课笔试和英语口语的复习时间。关键是这3题必须分属不同知识块比如今天字符串、动态规划、数据结构各一题而不是三题全是链表。再说到复盘这件事。很多人在OJ上做题有个习惯Accepted之后就跑了一道题就算结束了。我前10天也是这么干的直到第11天碰到一道原题换马甲——头一天AC的二叉树遍历第二天换个输入格式我就懵了才发现自己根本没有吃透。那次之后我调整了策略每天的3道题做完不管AC没AC都必须花至少半小时写复盘笔记。这篇就是19到21天的复盘整理三天一共9道题我挑了7道值得讲的不按题号顺序按知识点归类。这三天刚好覆盖了几个复试高频方向排序与二分的嵌套使用、字符串处理中的边界条件、动态规划的优化与状态设计。接下来我把每天的题组逐个拆开题目是回顾性转述平台不让抄原题但核心考点、解法和坑点全部保留。2. 第19天题组复盘区间合并、旋转数组与逆序对排序二分组的三个陷阱2.1 第一题区间合并平台第一版代码居然TLE了第19天的第一题是区间合并输入给一组二元区间要求把有重叠或相邻的区间合并输出合并后的区间列表。这题本身不复杂但它的两个版本差别很大如果区间已经按左端点排好序O(n)扫描就能完成如果没排好序必须先排序O(nlogn)。我当时看到题目第一反应直接写排序加双指针用vector存答案遍历时判断当前区间和结果最后一个区间是否相交。判断条件我写成了cur.left res.back().right才追加新区间否则就更新右端点。这个逻辑本身没问题但第一版代码TLE了。查了一下问题出在我把排序写成了自定义比较器里面用了lambda捕获外部变量虽然能跑但每次比较都额外做了一次字符串解析——因为输入读进来是[a,b]格式的字符串我在比较器里才sv实现解析数字。这种在排序比较器里做耗时解析的操作数据量一大就会暴露。改成在读入阶段就把字符串解析成pairint,int之后再排序瞬间就过了。这个教训很实在OJ题里排序阶段必须是纯数值比较所有解析工作提前到读入阶段完成。还有一个容易漏的边界题目说“相邻区间也要合并”也就是[1,2]和[3,4]这种首尾相接的情况必须合并成[1,4]。有些平台题解甚至不要求合并相邻区间所以拿到题第一件事是把“合并”的定义看清楚。我见过有人在区间合并的讨论区争论一个小时最后发现只是两个平台的题目定义不同。区间合并题的关键代码套路其实就三行排序、遍历、维护当前合并区间的右端点。但三行之外的解析效率、边界定义才是真正拉开AC率的地方。2.2 第二题旋转数组搜索二分变体中的等号处理第二题是搜索旋转排序数组。经典题目给一个递增数组在某处旋转过比如[0,1,2,4,5,6,7]旋转成[4,5,6,7,0,1,2]再给一个target要求时间复杂度O(logn)。这题考察的就是二分在“部分有序”数组上怎么变体。核心思路是每次取mid之后nums[left]和nums[mid]比较判断左半段是否完全有序如果nums[left] nums[mid]说明左半段有序此时若target落在[nums[left], nums[mid])之间就搜左边否则搜右边。反过来当左半段不是有序的时候右半段一定有序用对称逻辑处理。我在这题上没TLE也没WA但复盘时发现一个值得记录的细节判断“左半段有序”时用的是还是会影响后续行为。在没有重复元素的标准版本里nums[left] nums[mid]和nums[left] nums[mid]在大多数场景等价但有一种极端情况——数组只有两个元素时比如[2,1]left0, mid0此时nums[left] nums[mid]恒成立如果用判断就会误判左半段无序导致搜索方向完全错误。虽然旋转数组题在复试OJ里很少加“允许重复元素”的条件但养成写成的习惯能同时兼容有重复元素版本的搜索题。这么说吧二分题里等号怎么写不是“差不多就行”的事而是每个分支都要对着leftmid的退化场景过一遍脑子。2.3 第三题逆序对数量归并排序分治的边界与逆天数据范围第19天最后一道题是逆序对计数。这题如果数据量小两层循环暴力没问题但复试OJ的数据范围通常在n 10^5级别严密一点的地方会加到10^6暴力必挂。正确解法是归并排序过程中计数。每次合并两个有序子数组时如果右边数组当前元素小于左边数组当前元素说明左边数组中从当前位置到末尾的所有元素都和这个右元素构成逆序对统计时一次性加上mid - i 1。写归并排序求逆序对的时候最常见的问题是澄清递归终止条件与合并函数的返回值。我当时在主函数里用一个全局long long记录答案每层递归在合并完成后把答案累加进全局变量。这个写法在代码正确性上没问题但面试场合里全局变量容易让代码评分打折扣——因为面试官会问“如果系统要并发调用你这个函数全局变量的状态怎么隔离”。复试OJ不太看代码风格但复试面试环节会有机试代码讲解建议写成在递归函数里返回long long的方式。这题还有一个很多人掉进去的坑答案范围。逆序对数量最大是n*(n-1)/2当n10^5时大约5*10^9int装不下必须用long long。很多人在暴力过样例之后觉得自己AC了结果数据一大就WA检查半天发现只是int溢出的问题。逆序对这题特别适合作为复试机试的“试金石”——考分治思想、边界处理、数据类型敏感性一道题能覆盖三个维度。第19天把它和排序组放一起明显是帮我们温习分治框架。3. 第20天题组复盘KMP模板、字符串哈希与括号栈别小看字符串组的细节3.1 第一题KMP算法的next数组手工推演解决了我三年的迷惑第20天第一题直接考KMP的next数组计算。题目给一个模式串要求输出它的next数组。复试OJ里这种题不算少见因为面试官想知道你是不是真的理解KMP而不是只会背模板。我复习的时候重新推导了一遍next数组的含义next[i]表示模式串前i个字符组成的子串中最长的相同前缀后缀长度注意有些教材版本里next数组下标从0开始有些从1开始具体看平台要求。理解这个之后代码就是从jnext[i-1]开始不断尝试扩展不匹配就回溯。很多同学写KMP容易在“回溯到哪”这一步犯错——不是j--而是j next[j-1]。第20天我在草稿纸上手算了两个模式串才彻底搞明白。以ABABCABAB为例核心就是每一段前缀后缀的相等关系递推计算。过程中的感悟是KMP的难点不在匹配思路而在next数组的语义——它既是你匹配失败时模式串指针回退的位置又是子串对称性的量化表达。没有第二层理解代码只能靠背。复试OJ考KMP还有一个变体——不做字符串匹配而是让输出匹配位置或者统计匹配次数。统计次数时有一个坑题目要求重叠匹配时比如主串aaaa模式串aa正确答案是3次还是2次这取决于KMP匹配成功后模式串指针是回到next[m-1]还是从头开始。我因为没仔细看题目要求第一次交了2次的版本WA后才改成3次版本AC。这提醒所有备考的人不要假设任何平台的KMP语义和你看过的博客一样必须读题。3.2 第二题字符串哈希与滑窗结合二分答案的代入感第20天第二题是一道典型的“字符串哈希二分答案”题目具体是求一个字符串中最长的重复子串长度。这题在复试OJ里出现频率很高因为它在考字符串哈希的板子之余顺势考了二分的“可行性判断”思想。字符串哈希的核心就是把一串字符映射成一个数值保证不同字符串大概率得到不同值。常用的有自然溢出unsigned long long自动取模和双模数哈希。复试写代码时我建议用双模数mod11e97、mod21e99虽然多个常数开销但碰撞概率低到可以忽略。自然溢出虽然快但平台如果出构造数据可能被卡成碰撞WA。这个题的关键环节是二分答案长度L对每个L判断是否存在长度为L的重复子串。判断方法从左到右滑动窗口把当前窗口内子串的哈希值存进一个unordered_set如果遇到同样的哈希值就说明有重复串。理论上这一步可以用unordered_map找碰撞但要注意哈希碰撞的极小概率最好在哈希值相同的情况下再做一次实际字符串比较否则可能出现误判。我当时在pow数组初始化时犯了一个低级错误——base的幂次是从0到n但我只初始化到n-1导致最后一个窗口的计算取到了0。调试了半天才发现是数组越界读到了未定义的脏数据。这种问题在本地编译器不一定报错但OJ上可能表现为随机的WA特别难查。3.3 第三题括号匹配变体栈不止用来判断合法还能统计未匹配位置第三题是括号匹配的变体题目是给定一个只包含(和)的字符串允许翻转任意一个括号问最少翻转多少次能让整串合法。或者另一种变体给定一个包含三种括号的字符串判断是否合法并指出第一个不匹配位置。最简单的括号合法判断就是栈遍历字符串遇到左括号入栈遇到右括号看栈顶是否匹配。但变体题目里栈常常解决不了“最少翻转次数”的贪心问题这时候需要用“计数”思想而不是栈结构。比如只包含小括号的翻转题维护两个计数器balance和flips遍历时遇到(则balance加一遇到)时如果balance大于0就减一否则把当前这个右括号翻转成左括号flips加一且balance加一。最后如果balance是奇数说明还剩一半要翻转答案是flips balance/2。这题让我在复盘中意识到复试OJ出题人在“数据结构”标签下面藏了挺多“思维题”的面孔——它考的不是栈的API而是你能不能把栈的模型转化成计数器模型。面试讲解代码的时候如果只会说“我用栈模拟”给面试官的解释深度是不够的。更好的说法是栈模拟的是括号的嵌套结构而计数贪心利用的是小括号的可交换性。第20天的三道题整体来看核心是在帮我们过一遍“字符串处理的方向感”KMP考匹配哈希考快速比较栈考结构转换。三个方向刚好覆盖字符串题刷题时的三个基本盘。4. 第21天题组复盘LIS二分优化、编辑距离与背包边界DP组的极限拉扯4.1 第一题最长上升子序列从O(n²)到O(nlogn)的思维跳跃第21天第一题是最长上升子序列LIS。数据范围n 10^5这意味着O(n²)的传统DP肯定超时必须用二分贪心的O(nlogn)解法。这种解法的核心是维护一个数组dd[i]表示长度为i的上升子序列的最小末尾值。遍历原数组每个元素x时在d里用lower_bound找到第一个大于等于x的位置p如果p不存在就往末尾追加否则把d[p]更新为x。这个过程正确性有点反直觉——它更新的不是当前最优解而是某个长度的最小末尾这样才能贪心地为后续元素留出更大的扩展空间。我之前对LIS一直处于“会背板子、但说不清为什么”的状态。这次复盘时我盯着一个例子演算了很久[2, 1, 5, 3, 6, 4, 8]。维护过程中d的变化是[2]-[1]-[1,5]-[1,3]-[1,3,6]-[1,3,4]-[1,3,4,8]。可以看到当3替换5的时候5这个“潜在长度为2的末尾”被改成了更小的3这样后面遇到4才能连续扩展。这个例子理解了LIS二分优化才算真正掌握。这个题还有一个衍生变体最长不下降子序列。区别只在二分时用upper_bound还是lower_bound。不下降意味着相等元素可以共存所以找第一个大于x的位置上升则行不行都不能相等找第一个大于等于x的位置。这个细节我在复试笔记里单独用红笔标了。4.2 第二题编辑距离状态设计里的边界矩阵要格外小心第二题是经典编辑距离给定两个字符串A和B允许插入、删除、替换三种操作求把A变成B的最小操作次数。这题的O(mn) DP几乎是所有DP入门者的必修课状态转移方程也简单dp[i][j]表示A前i个字符到B前j个字符的最短编辑距离。转移分三种情况取最小值匹配时dp[i-1][j-1]删除dp[i-1][j]1插入dp[i][j-1]1替换dp[i-1][j-1]1。虽然方程简单但我在实际代码里犯了一个特别容易忽略的错初始化二维数组dp[m1][n1]的时候我用vectorvectorint dp(m1, vectorint(n1, 0))然后只给dp[0][j] j和dp[i][0] i赋值却忘了处理dp[0][0]的语义——严格来说它是0我虽然赋了0但在后面写转移方程时有些脚本会写成dp[i][j] min({dp[i-1][j]1, dp[i][j-1]1, dp[i-1][j-1](A[i-1]!B[j-1])})这个min三参数写法在C里要初始值列表结果我写成了min(dp[i-1][j]1, min(dp[i][j-1]1, dp[i-1][j-1](A[i-1]!B[j-1])))层数一多返回值类型其实只要保证都是int即可但读性极差。这里真正想提醒的是编辑距离的DP表最后一行最后一列一定要逐个手推一遍。我拿horse到ros在草稿纸上走了一遍表发现转移方程里“替换”这个操作在某个单元格会产生优于“删除插入”的效果这是理解DP表结构的绝佳训练——你会直观地看到DP不是玄学而是每一步都在维护局部最优解。复试OJ出编辑距离通常不是为了难倒你而是为了看你对经典DP是否“手到擒来”。如果你连滚动数组优化都觉得费劲至少要把二维DP的边界写扎实。4.3 第三题背包变体为什么初始化那行代码决定了你WA还是AC第21天的压轴题是背包问题的变体具体是“分割等和子集”给定一个数组问能否把它分成两个和相等的子集。转化一下就是01背包问题是否存在一个子集其元素和等于总和的一半。我第一次写这题时用了二维DPdp[i][j]表示前i个物品能否凑出j。转移是dp[i][j] dp[i-1][j] || dp[i-1][j-nums[i-1]]。写完之后AC样例但提交时一个测试点WA了原因特别隐蔽当总和是奇数时直接返回false这当然没问题但我忘了检查数组中每个元素本身是否超过总和一半——如果某个元素大于半值终究凑不出来但DP表里因为下标问题不会越界所以结果会在某个点出现逻辑错误。后来我把二维改成一维滚动数组核心是内层循环要逆序for (int j target; j num; --j) dp[j] | dp[j-num];。原因很直白正序遍历会让同一个元素被重复使用相当于变成了完全背包逆序才能保证每个元素只考虑一次。这个点是01背包和完全背包最本质的区别。我看到很多人背了“逆序”这个结论但说不清为什么。实际上一维DP状态dp[j]在正序更新时dp[j-num]可能是本轮已经更新过的代表着已经放入过当前物品逆序更新时dp[j-num]还是上一轮的值代表没有放入过当前物品。理解了这一层背包问题的很多变体你一眼就能看穿。这题让我最受益的地方是它教我“在写转移方程之前先检查数据约束和极端情形”。背包题大多数WA不是方程错而是初始化、边界、元素大值这老三样中的一个。第21天三道题全落在DP上但题型几乎不重叠序列DP、双串DP、背包DP。这种集中式刷法的好处在于你能清晰感受到DP题的共性——状态设计和边界检查比方程本身更值得花时间。5. 三天的共性复盘怎么把刷题量转化成解题能力而不是变成AC计数器5.1 复盘维度一按“题型分桶”整理而不是按时间线整理这三天下来9道题横跨了排序二分、字符串、DP三个方向。单纯的“第19天做了哪些题”式复盘对后续冲刺帮助有限。我采取的是一个土办法——准备一个表格纵向是题型横向是题目、核心考点、我的失误点、改进策略。比如题型题目特征核心考点我的失误点改进策略排序/二分区间合并排序扫描比较器内做字符串解析导致TLE读入阶段完成所有解析排序/二分旋转数组搜索二分变体等号处理未形成习惯固定写兼容重复元素排序/二分逆序对计数归并分治int溢出风险全局想清数据范围再动手字符串KMP next数组前缀后缀理解统计次数时未读清重叠语义先读题再写板子字符串最长重复子串哈希二分pow数组初始化越界所有辅助数组多开一个字符串括号翻转计数贪心栈模拟思维固化考虑计数器模型DPLIS二分优化不理解为啥能替换手动演算一组样例DP编辑距离状态转移二维边界初始化不完整每次手推一行表DP分割等和子集01背包未检查元素过大边界转移前先做极值检查这个表格是复盘的骨架。复试前最后一周我只需要看这个表格就能知道自己哪些方向还薄弱。表格之外每道题我还留了一两句针对平台的备注比如“此题输入有空格注意getline处理”。这种题粒度的信息在新的OJ上会体现价值。5.2 复盘维度二按“失败点”归类避开同一个坑掉两次刷题最怕的是一道题AC了但它的坑你没总结十天后换马甲再考你又掉进去。所以我的复盘笔记里专门有一个模块叫“失败点清单”不做题解记录只记录我在哪里浪费时间或提交。第19天的TLE、第20天的数组越界、第21天的初始化遗漏这三个失败点单独列出来其实就是复试OJ最常见的三类雷效率雷解析放错位置、边界雷辅助数组不够大、逻辑雷初始化不全或顺序不对。每当我准备AC下一题时都会快速过一遍这三个雷。事实证明后几天刷题时我的首交AC率明显提升从第18天之前的不到一半提升到第21天之后的八成以上。还有一点关于平台差异不同OJ的输入输出格式会微妙地影响代码。有的平台要求多组数据直到EOF有的要求先读一个T再循环有的允许行尾多空格有的严格要求无多余输出。第20天KMP那道题我的WA就是“统计重叠匹配次数”的题目语义不同导致的。所以复盘的记录里我专门给每道题加了一个字段本平台的特殊要求。这个习惯在换平台刷题时特别有用。5.3 复试冲刺阶段每天3题模式外的辅助训练光靠每天3题机试还是不够的。第19到21天这段时间我在3题之外加了三个辅助动作这些动作让这3道题的价值翻倍。第一个动作每道AC的题强制用另一语言重写一遍。我用C做OJ提交用Python写一遍同逻辑。不是为了炫技而是Python代码更接近伪代码写一遍能逼你把算法逻辑重新组织一遍。特别是KMP和DP这种逻辑密集的题C里依赖指针或下标Python里强制想清楚每一步的意义。第二个动作每道AC的题尝试改一个条件变成一道新题。比如第19天的区间合并我把它改成“求覆盖总长度”第20天的括号翻转我把它改成“括号匹配并输出最长合法子串长度”第21天的分割等和子集我把它改成“最小划分差”。这种变式训练一天只做一个就好但能帮你把核心思路从“这道题”抽象成“这类问题”。第三个动作口述题解。每道题AC后我会用一两分钟时间像面试讲解一样把这道题的思路、复杂度、边界说完。口述时经常会发现自己的逻辑漏洞——比如区间合并那道题我说“如果当前左端点大于结果右端点就新增”然后面试官如果追问“等于呢”你就得说清楚相邻区间要合并这是个很容易忽略的细节。口语输出的反馈比心里默念强得多这也是模拟复试讲解的好方法。我一直觉得刷题数量乘以复盘深度才等于真实能力提升。每天3题只是输入复盘表格、失败点清单、变形训练和口述才是把题目内化成解题嗅觉的关键路径。5.4 最后提醒机试现场的时间分配与心态控制最后聊点复试机试现场的东西因为刷题复盘到后期技术本身的边际收益在递减决策和心态才是拉开差距的地方。我咨询过一位参加过复试机试的学长A同学当时给的建议很实用先花5分钟通读所有题按“可AC的把握度”排个序先做最有把握的再啃中档最后死磕难题。很多人在第一题上死磕了40分钟导致后两题明明会做也没时间写非常亏。复试OJ一般是两道到四道题总分未必均匀。保守策略是保二争三保证简单题和中等题全AC难题拿到部分分。怎么拿部分分输出样例值、暴力枚举小数据、特判某些case这些手段在平时刷题时可能不值得一提但在复试现场可能就是一分之差。另一个经验来自我自己的模拟测试连续做了几套限时140分钟的模拟题组发现前60分钟状态最好中间30分钟容易因为卡题而焦躁最后20分钟又会因为时间压力手抖。应对方法是第31到60分钟之间强制站起来喝水一次每次卡题超过15分钟就果断跳过。这看起来和代码无关但机试是脑力加体力的双重考验状态管理绝对是实战能力的一部分。复盘到第21天我最大的收获其实不是这9道题本身而是对“刷题”这件事有了更准确的认知复试OJ刷题不是打卡数每一道题的多一层理解都是真实考场上的多一分确定性。