1. 从一次连续AC失败说起第25-27题的定位与考察点最近我在一个OJ平台上连续刷到第25、26、27题一开始以为只是普通的顺序题单结果三题分别踩了稳定排序、动态规划状态定义、DFS栈溢出三个完全不同的坑。第25题看起来是最简单的我却因为没注意“相对顺序”的要求连续提交了三次才过第26题是加权区间调度状态转移思路好懂但二分查找的边界让我调了半天第27题是矩阵最大连通块DFS写起来特别顺手换了大测试数据直接Runtime Error。这三道题正好对应了OJ刷题中最常遇到的三个层次基础数组处理、经典DP、搜索优化。如果你也正在刷OJ尤其是已经过了入门语法关、开始接触算法题单的阶段这套题目非常适合拿来对照复盘。网上不少题解只给最终代码很少解释“为什么第一版解法不对”所以我想把这三道题从最初思路到最终AC的完整过程记录下来包括我踩坑时的错误代码以及最后总结出来的自测方法。无论你用的是华为OJ、东华OJ还是其他OJ系统这套题目考察的能力都是通用的。1.1 三道题的题目原型与输入输出先说第25题。题目原意大概是给一个整数数组要求把所有奇数放在偶数前面同时保持所有数字原本的相对顺序不变。也就是奇数和奇数之间、偶数和偶数之间的先后关系都要和输入数组一致。输入样例是[1, 2, 3, 4, 5]输出必须是[1, 3, 5, 2, 4]不能输出[1, 5, 3, 2, 4]这种乱序结果。第26题是一个任务调度问题。输入若干任务每个任务有三个参数开始时间、结束时间、价值要求选出若干互不重叠的任务使总价值最大。这个模型在现实里很常见比如会议室预定、兼职排班都可以套用。我刷到的题目数据范围是任务数量最多1e5所以O(n^2)的解法一定会超时。第27题是二维矩阵里的最大连通块。矩阵由0和1组成1表示陆地0表示水上下左右四个方向相邻的1属于同一块陆地要输出所有连通块中面积最大的那个。题目原文用的是字符矩阵所以输入是字符串列表。边界和去重是这道题的主要考察点。1.2 为什么把这三道题放在一起复盘单独看这三道题都不算太难但放在一起就有意思了。它们分别覆盖了“数组的稳定处理”“用动态规划替代暴力枚举”“用非递归搜索规避栈溢出”三个方向。刷题时最容易出现的问题是基础题忽略题目隐含约束中等题推不出高效状态转移图论题只会递归写法。这三道题就像三个路标每道题卡住我的地方恰好都是这个题型最常见的坑。另外这三道题还有一个共同点都要求你在“最简单写法”和“正确写法”之间做选择。第25题双指针交换很简单但破坏了稳定性第26题暴力枚举所有组合很直观但指数级复杂度不可行第27题递归DFS很简洁但大规模数据下会爆栈。刷完这一组我最大的体会是OJ刷题不能只看“能不能过样例”还要想清楚方案在极端条件下会不会出问题。2. 第25题稳定输出的要求让双指针失效2.1 第一版解法按奇偶分两遍输出这个题第一眼看上去太友好我心里马上冒出一个方案遍历两次第一次把奇数收集起来第二次把偶数收集起来最后拼在一起。用Python写就是def reorder(nums): return [x for x in nums if x 1] [x for x in nums if x 1 0]这里我特意用了x 1它的作用是取二进制最低位奇数最低位一定是1偶数最低位一定是0。用这个判断方式是为了避开C里负数取模的坑-3 % 2在C里结果是-1如果代码写if (a[i] % 2 1)负数就直接被当成偶数了。虽然Python里-3 % 2结果是1问题不暴露但OJ平台经常要求你用C提交所以我一律建议用位运算判断奇偶。这个解法的正确性其实已经足够了。它额外开了一个和原数组等长的列表时间复杂度O(n)空间复杂度O(n)能稳定通过。但我第一次提交时没有直接写这个版本而是想当然用了双指针。2.2 双指针交换为什么让相对顺序乱掉我一开始的思路是用两个指针一个从左边找偶数一个从右边找奇数找到后交换位置。这样一趟就能把所有奇数换到前半部分偶数换到后半部分看起来非常高效。代码大概是def reorder_double_pointer(nums): left, right 0, len(nums) - 1 while left right: while left right and nums[left] 1: left 1 while left right and nums[right] 1 0: right - 1 if left right: nums[left], nums[right] nums[right], nums[left] left 1 right - 1 return nums输入[1, 2, 3, 4, 5]时这个程序输出的结果就变成了[1, 5, 3, 4, 2]。奇数部分1,5,3不再保持原来的顺序偶数部分4,2也不对了。原因很简单交换操作本质上是把右边的奇数直接丢到前面两个相邻奇数之间的先后关系一旦被远距离交换打破就很难恢复。这个坑特别隐蔽因为原题描述里有一句话“保持所有数字的相对顺序不变”。很多人在快速阅读时会把这句话忽略掉以为只是单纯把奇偶分开。如果你遇到的是经常出现在面试笔试里的“奇偶排序”变种必须先用几秒钟确认题目是否要求稳定输出如果要求交换类算法一律不能用只能额外开辟空间或者用插入排序式的移动。2.3 正确解法用额外空间换稳定性确定题目要求稳定后最稳妥的写法就是开两个临时数组先分别收集奇数和偶数最后再拼起来。上面那个列表推导式写法就很合适。为了更容易理解我再写一个通用版本方便你迁移到C或者Javadef reorder_stable(nums): odd, even [], [] for num in nums: if num 1: odd.append(num) else: even.append(num) return odd even这个解法本质上没有移动原数组元素只是做了两次线性扫描所以所有元素的相对顺序天然被保留。如果你担心OJ要求只能使用常数额外空间那就需要思考另一种解法从后往前找偶数然后把它后面的所有奇数依次向左移动。但那种写法的复杂度很容易变成O(n^2)对1e5规模的数据并不安全。我在实际OJ上测试额外O(n)空间通常不会成为限制条件所以能开数组就开数组代码越简单越容易维护。2.4 边界条件和性能复盘这一题让我明白边界条件不是可有可无的。空数组要返回空数组长度是1时直接原样返回全部是奇数或全部是偶数时程序不能越界还有一个就是负数判断。现在我的习惯是提交前先手动跑三个边界用例[]、[-1, -2, -3]、[1, 2, -3, -4, 5]。不要觉得这些例子简单第25题我翻车的原因之一就是只测了正数。性能方面这题的时间复杂度是O(n)但要注意Python里列表拼接odd even会复制一次列表空间上会多一份临时开销。对于一般OJ的数据规模完全无压力。刷完之后我意识到判断一个数组题是否可以用双指针不是看时间复杂度的优劣而是看题目到底有没有“稳定”这个隐含约束。把它牢牢记下来后面刷相关题目会省很多时间。3. 第26题加权区间调度从暴力递归到二分优化3.1 题目描述与我的初始直觉第26题的描述是给定n个任务每个任务有开始时间start[i]、结束时间end[i]和权重value[i]要求选出若干个互不重叠的任务使权重总和最大。两个任务不重叠的定义是前一个任务的结束时间小于等于后一个任务的开始时间。我第一反应是贪心每次选结束时间最早的任务。但很快发现不行因为任务有权重一个区间短但权重小的任务可能会挡掉两个长但权重更大的任务。接着我想用穷举组合可是任务数量到了1e5显然不可能。于是开始回忆这块知识区间调度通常先按结束时间排序再做动态规划。3.2 从暴力递归推演出状态转移为了理解状态转移我先从暴力递归入手。假设任务已经按结束时间从小到大排序考虑最后处理第i个任务。选择它的话因为所有任务都按结束时间排了序那么排在它前面且结束时间不晚于start[i]的任务就是一组可以和它共存的候选。问题变成选第i个任务的最大收益等于value[i]加上“前p[i]个任务的最优解”不选第i个任务则直接等于“前i-1个任务的最优解”。两者取最大就是前i个任务的最优解。这里最关键的是找到p[i]也就是“在已排序的任务中最后一个结束时间小于等于start[i]的下标”。因为结束时间已经有序p[i]一定小于i所以可以用二分查找快速定位。如果用暴力遍历往前搜整体时间复杂度是O(n^2)1e5数据直接超时。3.3 二分边界最容易翻车的地方这个题的二分边界比我想象中难。先看最终代码from bisect import bisect_right def max_value(tasks): # tasks [(start, end, value), ...] tasks.sort(keylambda x: x[1]) # 按结束时间排序 starts [t[0] for t in tasks] ends [t[1] for t in tasks] values [t[2] for t in tasks] n len(tasks) dp [0] * n dp[0] values[0] for i in range(1, n): idx bisect_right(ends, starts[i]) - 1 take values[i] if idx 0: take dp[idx] notake dp[i - 1] dp[i] max(take, notake) return dp[-1]bisect_right返回的是在ends列表中插入starts[i]后仍保持有序的最右位置。举个例子如果ends [3, 5, 8]starts[i] 5bisect_right(ends, 5)返回2减一后等于1意味着下标0和1的任务结束时间都不晚于5。这里必须用bisect_right而不是bisect_left否则当某个任务结束时间恰好等于当前任务开始时间时我们会少算一个可选任务导致结果偏小。还有一点需要注意idx可能等于i吗不会因为当前任务结束时间至少大于等于开始时间更不可能小于等于自己的开始时间所以bisect_right结果最多是i减一后最多是i-1。但为了安全我仍会在代码里加一个if idx 0的判断防止idx为-1的情况也就是当前任务前面没有任何不重叠任务时只取它自己的价值。3.4 状态定义过程中的一个常见误区我最初写状态时想的是dp[i]表示“以第i个任务结尾的最大价值”这样就需要枚举前面所有能和它衔接的任务状态转移会是dp[i] max(value[i] dp[j])其中end[j] start[i]。这个定义也能做但复杂度还是O(n^2)而且最后还需要遍历所有dp[i]取最大值。换成“前i个任务内部选择的最大价值”后dp[i]天然单调不降最后答案直接是dp[-1]配合二分查找才能把复杂度降到O(n log n)。我提交第一版时用的就是“以第i个任务结尾”的写法小数据过了大数据超时。后来改成按结束时间排序后才把二分用上。这个经历告诉我们DP的dp[i]含义不是拍脑袋决定的它必须服务于“能否用高效方式从前面的状态转移过来”。如果你推了半天发现转移过程要遍历太多前驱大概率是状态定义选错了方向。4. 第27题最大连通块DFS栈溢出后的BFS改写4.1 题目描述与DFS的第一版实现第27题给了一个m x n的字符矩阵1表示陆地0表示水四连通方向算同一块陆地要求返回最大连通块面积。我脑子里第一反应就是递归DFS遍历每个格子遇到1就递归进入四个方向统计当前块大小同时把访问过的格子改成0避免重复计数。第一版代码是def dfs(grid, i, j): m, n len(grid), len(grid[0]) if i 0 or i m or j 0 or j n or grid[i][j] 0: return 0 grid[i][j] 0 cnt 1 cnt dfs(grid, i 1, j) cnt dfs(grid, i - 1, j) cnt dfs(grid, i, j 1) cnt dfs(grid, i, j - 1) return cnt本地用小矩阵测试结果全对。可是当我提交到OJ面对1000x1000的大矩阵时直接报Runtime Error。一开始我以为是递归访问和数组越界问题反复检查都没发现问题。后来才想到问题可能出在“递归深度”上一个连通块如果占满整个矩阵递归调用深度能达到1000000层解释器会直接抛RecursionError就算C也可能因为栈空间不够导致Segment Fault。4.2 为什么不能盲目迷信递归很多人学DFS时会形成刻板印象DFS就等于递归BFS才用队列。但这个题让我意识到在OJ的大数据限制下递归不仅是风格问题还是性能问题。递归调用会占用函数调用栈每一层还保存局部变量而一个连通区域深度很大的时候栈的消耗是巨大的。对比之下BFS使用显式队列队列占的是堆空间通常比栈空间宽松很多所以数据规模大时更稳妥。但并不是说DFS不能用。你可以把递归改成显式栈自己维护一个列表来模拟系统栈方向和递归完全相同。缺点是代码更复杂容易出错。对最大连通块这类广度遍历并不要求输出路径的题目BFS是更自然的选择。4.3 BFS实现的完整代码最终我改成BFS这里给出一个可以直接AC的版本from collections import deque def max_area(grid): if not grid or not grid[0]: return 0 m, n len(grid), len(grid[0]) dirs [(1, 0), (-1, 0), (0, 1), (0, -1)] ans 0 for i in range(m): for j in range(n): if grid[i][j] 1: q deque() q.append((i, j)) grid[i][j] 0 cnt 0 while q: x, y q.popleft() cnt 1 for dx, dy in dirs: nx, ny x dx, y dy if 0 nx m and 0 ny n and grid[nx][ny] 1: grid[nx][ny] 0 q.append((nx, ny)) ans max(ans, cnt) return ans有两个细节非常关键。第一方向数组不要写成8个方向否则会把斜对角也当成同一块陆地样例全错。第二一定要在点加入队列时就立刻把格子标记为0而不是出队时再标记。如果出队时标记同一个格子可能被多个邻居加入多次造成巨大的重复计算和错误计数。4.4 原地修改原数组的取舍这个解法直接修改了传入的grid把访问过的1改成0省掉了visited矩阵。OJ平台一般允许修改输入数组因为题目只要求返回面积不要求保留原矩阵。但如果你在面试中遇到这道题最好先跟面试官确认能否修改输入。如果不能修改就需要额外开一个visited布尔矩阵或者把格子编号存进set里。额外空间的代价通常是可以接受的。我最初用递归DFS时也采用了原地标记但BFS版本里有一个更容易忽略的点如果某个格子已经入队但它的邻居还没被处理你可能会再次遇到这个格子。此时标记0能让它不会被重复入队。只要把握住“入队即标记”原则就不容易出现死循环。5. 三道题之后的复盘错因分类与自测模板5.1 三道题的常见错误对照表刷完这三题后我把它们的核心考点、易错点和最优复杂度整理成了表格方便以后复习题目核心算法主要坑点时间复杂度我的第一版错误第25题稳定排序/分数组收集负数取模、双指针破坏相对顺序O(n)使用双指针导致奇数顺序乱掉第26题按结束时间排序 动态规划 二分状态定义不对、二分边界选错O(n log n)状态表示成“以i结尾”超时第27题图的BFS/DFS遍历递归深度过大、入队时未标记O(m*n)递归DFS在大矩阵下栈溢出这张表看起来简单但每一条都是从实际提交失败里总结出来的。如果你也在刷OJ建议每做完一组题都做类似表格因为错误模式比正确代码更有复用价值。5.2 从这三题里提炼出的刷题方法第25题让我养成了一个习惯动手写代码前先圈出题目描述里的限定词。比如“相对顺序不变”“不能使用额外空间”“连通方向为上下左右”等这些词直接决定算法选型。很多人栽在简单题上不是因为不会写而是因为漏看了条件。第26题让我学会从暴力递归反推DP状态。遇到没见过的优化问题先写一个能让小数据通过的递归版本在递归参数里找出“哪两个维度决定了返回值”然后把它们变成dp的维度。不要一上来就追求最优解先保证理解问题再逐步剪枝和优化。第27题让我重视了数据规模。一道搜索题如果m*n可能达到1e6递归栈就是一个隐患。现在我看到搜索题会先估算最大深度再决定用递归还是显式队列。通常来说显式BFS是更稳的方案。5.3 本地自测模板避免反复提交消耗信心OJ提交失败多了容易烦躁所以我后来养成了一个本地自测的习惯。写题时先写一个简单的随机测试数据生成器在本地把边界情况跑一遍。比如第27题我会生成一个2000x2000的矩阵随机填充0和1检查程序能不能在1秒内结束顺便看看会不会报递归错误。下面是一个很小的Python模板import random def generate_matrix(m, n): return [[str(random.randint(0, 1)) for _ in range(n)] for __ in range(m)]生成随机数据只能覆盖一部分场景还要手动构造一些极端输入空数组、只有一行、全是1、全是0、最大规模。这套模板配合前面的答题能在提交前发现大部分问题。刷到第25-27题时我正是用类似方式快速定位了递归栈溢出才没有在OJ上反复试错。我个人最大的体会是OJ刷题不等于背代码而是训练一种“先想清楚约束再选择算法”的思考习惯。第25-27题只是开始后面还有更多类似的组合等着你。如果你现在也卡在某道题上反复超时或报错不妨回头看看是不是踩了同样的坑题目有没有稳定性要求状态定义有没有选对递归深度是否可控把这些记下来下一道题就能少走很多弯路。