1月15号力扣刷题打卡照常进行。今天给自己排了三道题一道字符串模拟、一道滑动窗口、一道二维动态规划难度控制在简单加两个中等。字符串题考察的是边界细节滑动窗口考察的是指针维护的节奏感动态规划则是老生常谈的状态抽象能力。把这三类放到同一天练我发现它们其实共享不少底层思维——窗口收缩和双指针翻转练的是同一套谁先动、谁后动的逻辑动态规划的表格填充又和滑动窗口的右进左出有某种相似感。这篇文章就是把当天从读题、思路到写代码、调试的完整过程记录下来再附上一些常规题解里不会写的坑点。刚开始刷题的朋友可以直接把代码拿去用刷了一段时间的朋友可以参考里面的对比分析和优化路径。1. 今天的刷题计划与选题思路1.1 三道题怎么安排各花多长时间刷题这事最怕的就是打开题库随机抽题抽到什么刷什么看起来努力实际效率不高。我今天的安排是有意为之先花两分钟扫一遍三道题确认题型不重复然后按简单→中等→中等的顺序推进预计总时长控制在九十分钟以内。实际用时记录一下第一道字符串题从读题到 AC 用了 25 分钟第二道滑动窗口 17 分钟第三道动态规划 38 分钟总共 80 分钟。为什么推荐这样固定时间因为面试做题是有时间压力的日常如果不对自己限时到了现场很容易在某一题上死磕到底搞崩整场节奏。我给自己定的规则是简单题 15 分钟内必须出思路中等题 30 分钟以内超时直接看题解然后把这道题标记为弱项隔天再重做一遍。今天第一题超时了几分钟问题出在练习题太少后面会细说。1.2 选题的逻辑三种常见考法的底层联系刷题要刷出效果不能只刷数量要刷类型。我把今天三道题放在一起是因为它们分别代表了算法面试里三种最常碰面的能力维度字符串模拟题考查的是边界条件管理滑动窗口考查的是单调性和贪心直觉动态规划考查的是状态抽象能力。这三种能力不是孤立的。字符串原地翻转需要双指针滑动窗口的收缩同样依赖两个指针的移动策略状态转移方程的填表过程又和窗口维护有相似的递进关系。把相关联的题型放在同一天练比一天刷五道同类题更能锻炼举一反三的能力。我见过很多刷了三百道题的人遇到新题还是没思路就是因为只记了题目答案没有抽象出题型骨架。2. 字符串模拟反转单词背后的三个坑2.1 题目要求与初步思路今天第一道题是这样的给定一个字符串其中包含若干单词和空格要求把单词顺序反转同时去除多余空格——首尾空格去掉单词之间的连续空格压缩成一个。举个例子the sky is blue 要变成 blue is sky the。读题之后第一反应是这题考整体反转 局部反转先把整个字符串反转一遍这样单词顺序就反了但每个单词内部字符也反了然后再把每个单词内部反转回来两步一组合顺序正确。这个套路在字符串类题目里很常用就像你先倒着读整句话再把每个字正过来念效果就是整句倒了但词没倒。不过这道题还加了去除多余空格的要求所以不能只靠两次反转了事。2.2 两种实现代码少的不一定适合面试第一种写法非常短用语言自带的分隔和切片def reverseWords(s: str) - str: words s.strip().split() return .join(words[::-1])strip()去掉首尾空格split()默认按任意空白字符切分连续空格会被忽略所以多余空格的问题也顺带解决了。这段代码跑测试用例毫无压力如果你只是日常解题这完全够用。但面试场景下这种写法可能被追问如果要求空间复杂度 O(1)不准用额外的数组你还能实现吗所以还得会写手动版。Python 字符串不可变要原地操作只能先转成字符数组。我的实现思路是先把整个字符数组反转然后从头部扫描遇到单词就往前拷贝单词前补一个空格拷贝完立刻把这段单词局部反转最后把多余部分截断。代码这样写def reverseWords(s: str) - str: chars list(s) n len(chars) # 第一步整体反转让单词顺序反过来 chars.reverse() # 第二步扫描每个单词拷贝到前面并局部反转 storeIdx 0 i 0 while i n: if chars[i] ! : # 在非首个单词前补一个空格 if storeIdx ! 0: chars[storeIdx] storeIdx 1 j i # 拷贝完整单词到 storeIdx 位置 while j n and chars[j] ! : chars[storeIdx] chars[j] storeIdx 1 j 1 # 反转当前单词内部字符 start storeIdx - (j - i) chars[start:storeIdx] list(reversed(chars[start:storeIdx])) i j else: i 1 return .join(chars[:storeIdx])整体下来就是一次线性扫描时间复杂度 O(n)空间上除了字符数组没有额外开销。理解这段代码的关键在于 storeIdx它是写指针记录的是下一个要写入的位置。扫描指针 i 负责找单词写指针负责把单词搬回数组前端搬完一个单词立刻反转它这样单词内部顺序从倒着变回正着但单词之间的顺序维持了倒着。2.3 踩过的三个具体坑第一个坑是补空格的时机。我第一次写的时候在每个单词前无条件加空格结果首单词前面多出一个空格。正确做法是判断 storeIdx 不为 0也就是当前已经写过至少一个单词才补空格。这个判断要放在拷贝单词之前。第二个坑是整体反转后扫描逻辑容易混淆。因为chars.reverse()之后字符串内容已经不是原来顺序我从头扫描时见到的是最后一个单词在前面的倒序所以扫描顺序和拷入顺序必须匹配容易绕晕。后来我用纸笔走了一遍样例才想清楚扫描是从左往右遇到单词就拷这个单词本来就是原来的最后一个单词拷出来之后局部反转一下正好变成正序。第三个坑是切片反转的边界。chars[start:storeIdx]这个切片的长度恰好是j - i因为拷贝过程中 storeIdx 正好推进了j - i次。但如果你在拷贝循环里额外做了别的事导致 storeIdx 偏移这里就会截错范围。调试时我发现切片末尾多抓了一个字符当时就是因为在单词拷贝前先补了空格却没把补空格的偏移算进去。正确写法是补空格发生在拷贝之前storeIdx 先自增之后拷贝的长度依然等于j - i此时 start 用storeIdx - (j - i)计算而不是用拷贝前的 storeIdx。提示字符串类题目最容易出错的地方不在算法本身而在边界。建议写完代码后用空字符串全空格只有一个单词单词间多个空格四类用例快速自测能挡掉大多数低级错误。3. 滑动窗口最短子数组的模板与易错点3.1 问题建模与双指针移动逻辑第二道题是给定一个正整数数组 nums 和一个目标值 target找出数组中满足总和大于等于 target 的长度最小的连续子数组返回长度。如果不存在返回 0。示例target 7nums [2,3,1,2,4,3]最短连续子数组是 [4,3]长度 2。最直接的暴力做法是枚举所有起点和终点两层循环把每个子数组的和算一遍时间复杂度 O(n²)。这道题的数组长度可能到十万级别O(n²) 肯定超时。能优化的地方在哪里关键在于数组元素都是正整数所以子数组的和随着右端点右移只增不减具有一定的单调性。一旦某个窗口满足 sum target右端点继续右移时窗口还在扩大长度只会更长没有继续保留的价值。因此我们可以用两个指针维护一个动态窗口右指针不断向右扩展把新元素纳入窗口当窗口和达到 target 时记录当前窗口长度然后左指针向右收缩尝试找到更短的满足条件的窗口。这个思路和日常生活中的排队窗口很像——队伍的右边有人不断进来左边有人不断离开我们只关心当前排队的人总和够不够一旦够了就看看能不能少排几个人。3.2 模板代码与复杂度分析代码模板直接给出def minSubArrayLen(target: int, nums: list[int]) - int: left 0 cur_sum 0 ans float(inf) for right in range(len(nums)): cur_sum nums[right] # 满足条件时收缩左边界 while cur_sum target: ans min(ans, right - left 1) cur_sum - nums[left] left 1 return 0 if ans float(inf) else ans这个模板几乎可以套用到所有最短/最长满足条件的连续子数组问题里。外层 for 是右指针内层 while 在条件满足时收缩左指针。这里有一个细节值得注意ans 的更新放在 while 循环内部。我在第一次写的时候把ans min(ans, right - left 1)放在了 while 外面导致记录到的不是满足条件时的最短窗口而是收缩结束之后的窗口结果全错。更准确地说窗口满足条件的状态只出现在 while 的入口所以必须在 while 内部先记录长度。复杂度方面虽然代码里有两个循环但每个元素最多被 right 访问一次、被 left 移出一次整体是 O(n) 时间O(1) 空间。3.3 变体如果数组有负数会怎样滑动窗口能工作的前提是数组元素为正或非负这样窗口和有单调性。如果 nums 里有负数左指针收缩时窗口和不一定变小右指针扩展时窗口和也不一定变大left 和 right 的移动逻辑就失去了依据。这时候要换思路常见方案是前缀和 二分查找或者用单调队列维护窗口内的某种极值。本次题目明确给了正整数所以不需要处理这种情况但面试官可能会追问提前想清楚为什么负数的存在会破坏模板也是刷题的价值所在。那遇到有负数的变体怎么排查我习惯先写几个带负数的测试用例观察模板的输出是否明显不符合预期然后从窗口和变化方向不可预测这个根因出发寻找新的数据结构。这种分析习惯比记住一堆题解有用得多。4. 动态规划网格路径的状态迁移4.1 状态定义与边界推导第三题是经典的网格路径问题一个机器人位于 m 行 n 列的网格左上角每次只能向下或向右移动一步问到达右下角总共有多少条不同路径。这道题用 DFS 当然可以做但会重复计算大量子问题。动态规划的核心是用一个表格记录子问题的答案定义 dp[i][j] 表示从左上角走到第 i 行第 j 列的不同路径数。机器人只能从上方格子向下走一步、或者从左方格子向右走一步来到达当前位置所以状态转移方程是dp[i][j] dp[i-1][j] dp[i][j-1]边界条件第一行的所有格子只能一直向右走路径数都是 1第一列的所有格子只能一直向下走路径数也都是 1。把第一行和第一列初始化为 1然后从 (1,1) 开始逐行逐列填充右下角的 dp[m-1][n-1] 就是答案。这个过程在草稿纸上画一个 3×3 的表格手动填一遍六十秒就能理解。填表顺序是上一行先填完当前行从左到右填这保证任何一个格子在计算时它依赖的 dp[i-1][j] 和 dp[i][j-1] 都已经有了确定值。4.2 滚动数组优化二维表格的完整空间复杂度是 O(m×n)但观察转移方程就会发现计算每一行时只需要上一行的数据而不需要更早的行。这就像你在看账本时只关心上一页的余额没必要把前面所有页都背下来。因此可以只用一维数组滚动更新def uniquePaths(m: int, n: int) - int: dp [1] * n for i in range(1, m): for j in range(1, n): dp[j] dp[j] dp[j - 1] return dp[-1]这里的 dp[j] 初始值代表第一行每个格子的路径数都是 1。进入第二行循环时dp[j] 保存的是上一行第 j 列的值dp[j-1] 因为刚被更新过保存的是当前行左边格子的值两者相加正好等价于 dp[i-1][j] dp[i][j-1]。等这一行更新完毕dp 就代表了当前行每个格子的路径数下一行继续用这份数据滚动更新。这个优化把空间从 O(m×n) 降到 O(n)在 m 和 n 很大的时候收益非常明显。4.3 从组合数角度验证答案网格路径问题还可以用组合数学来理解从左上角走到右下角不管怎么走总步数是 (m-1) (n-1)其中向下走 m-1 步向右走 n-1 步。路径的差异只在于向下走出现在哪几步所以答案就是组合数 C(mn-2, m-1) 或等价的 C(mn-2, n-1)。我在拿动态规划跑完结果后又用组合数公式算了一遍用于交叉验证。比如 m3、n3 时动态规划结果是 6组合数 C(4, 2) 也是 6两边对上了代码基本没有错。不过要注意直接用组合数公式计算时中间结果可能很大需要处理溢出动态规划用加法逐层累加天然避开了这个麻烦所以日常刷题我更推荐先写动态规划再用组合数做验证。5. 复盘调试技巧与通用心得5.1 今天的排错全记录三道题都不是一遍过的记录一下实际遇到的典型问题按题目整理成速查表题目遇到的问题排查思路与解决字符串反转单词间补空格导致首单词前多出空格加 storeIdx ! 0 判断区分是不是第一个单词字符串反转局部反转的切片边界多抓一个字符明确 start 应基于拷贝后的 storeIdx 计算滑动窗口ans 记录成了收缩后的长度把长度更新移到 while 循环内部写在 cur_sum - num[left] 之前动态规划滚动数组初始化错了行方向手动模拟 3×3 填表确认 dp 数组更新顺序与行扫描一致这里想多说一句定位 bug 最有效的手段不是反复读代码而是构造极端用例。今天我就是在全空格字符串的用例上发现第一题的补空格逻辑漏了判断又在 target 大于数组总和的用例上发现第二题float(inf)的兜底返回值没问题。如果你写完代码先空想逻辑再拿三五个手工用例跑一遍基本能覆盖八成错误。5.2 刷题节奏和心态调整的经验刷题不是刷得越多越好每天都刷同样的题型容易陷入舒适区。我现在的方法是每周一三五练基础数据结构字符串、数组、链表二四练算法思想二分、双指针、动态规划周末随便挑一两道之前标记的错题重做。今天正好踩中一个新问题字符串第一题在 15 分钟没出完整思路心里有点急硬着头皮死磕结果 25 分钟才写完。复盘时发现这种题应该拆成两个子步骤来看——先不考虑空格压缩把反转做好再加空格处理而不是一上来就想一步到位。把复杂问题分步拆解的思维本身就是刷题要练的内功。5.3 一个可以长期用的自查清单结合今天的实战我整理了一个自查清单每次提交前照着过一遍输入为空或长度为零时代码是否报错边界值第一个元素、最后一个元素是否被正确处理连续重复输入、全相同输入是否会导致死循环指针或索引在循环结束时是否可能越界答案变量初始化值是否足够大/足够小能否区分无解和有解空间优化后旧数据是否可能被新数据提前覆盖这份清单花不了两分钟但能挡住大量低级失误。我最近一个月按照这份清单检查线上做题的通过率明显提升更重要的是做错之后返工的时间少了。最后再分享一个小技巧刷完一道题后不要急着点下一题先花两分钟在题解的评论区或者自己的笔记里写一句这题的核心套路是什么和哪道旧题类似。坚持一个月你会发现脑子里慢慢形成一张题型网络再遇到新题时会本能地问自己这题该套双指针、二分还是动态规划这比刷题数量更重要。