第六天。说实话能连续刷题六天比我预想的要难不少。第一天打开题库连题目描述里的术语都要反复查到了今天至少看到中等难度的数组题、链表题、二叉树题心里已经能快速判断“这题大概考什么套路”。这个编程题练习系列走到Day6我想认真记录一下这天的选题思路、做题过程、踩过的坑以及坚持六天后真实的感受变化。如果你也正处在刷题起步阶段或者刚好卡在“每天都在练但感觉没进步”的瓶颈里这篇Day6练习复盘应该能给你一些参考。今天的三道题我没有刻意去啃难题而是选了三个高频且经典的方向滑动窗口解决最短覆盖子串、快慢指针寻找链表环入口、二叉树的层序遍历变形。选这个组合有两个原因一个是这三个套路在面试和笔试中出现的频率确实高另一个是Day6这个阶段最该做的不是挑战极限题而是把基础套路真正内化让它们能组合起来解决新问题。下面我会把每道题的完整思路、代码实现、常见错误都拆开讲也会分享一些题外的方法论。1. 第六天的选题思路为什么练“组合基础”而不是硬啃难题到第六天很多人容易陷入两个极端要么觉得基础题刷腻了想去碰难题要么还是只敢刷最小白题不愿意提升难度。我两边都不想选所以特意把今天定位成“基础能力组合应用日”。1.1 前五天的进度复盘给自己定位我给自己定的计划是每天一到两小时不用贪多但必须保证每道题都吃透。Day1到Day2集中刷数组和字符串的基础题Day3专门练哈希表的应用Day4把链表的基本操作反转、合并、删除节点过了一遍Day5刚开始接触二叉树只做了前中后序遍历和简单的递归。这样走到Day6基础数据结构基本都见过一遍但说实话当时的状态是“单个套路好像都懂一旦题目把两个知识点的考察混在一起就会卡住”。这种“单个会、组合卡”的状态是刷题起步阶段最典型的瓶颈。如果这时候急着去挑战最难的动态规划或图论很容易被打击到心态而且就算AC了也大概率是靠记忆题解不是真理解。所以我给Day6定的目标很明确通过三道“基础结构组合应用”的题目把前面学到的东西真正串起来让自己开始习惯从“这个知识点我背过”过渡到“这个场景下我应该用哪个知识点的组合”。1.2 今天的做题标准套路明确、边界丰富、能迁移选今天这三道题之前我给自己列了三个筛选条件首先它得是高频面试题刷一道能解决一类问题其次它必须有明确的套路可循方便我整理成模板最后它必须包含足够多的边界情况能锻炼我的调试能力。三个条件缺一不可因为Day6的练习绝对不是“随便找三题做做”。拿最终选出的三道题来说最短覆盖子串属于“滑动窗口哈希计数”的组合链表环入口属于“快慢指针数学推导”的组合自底向上层序遍历属于“队列BFS结果处理”的组合。它们没有一个需要特别冷门的算法知识但对基础数据结构的要求都比较扎实正好匹配Day6的位置——既不吃力又能让你感觉到“题目开始有点综合了”。我也不建议刚刷题的人一上来就给自己定“每天五道题”这种目标质量比数量重要太多一天把三道题完全吃透比一天过十道题却只留个印象要有用得多。刷题是一个需要长期坚持的事节奏稳定比短期冲刺更可持续。2. 核心题目拆解三道题背后的算法思维下面按顺序讲今天的三道题每道题我都会给出可运行的Python代码和完整的复杂度分析。语言方面我选了Python因为它在刷题场景下最省事但思路完全可以用C或Java复现。三道题分别覆盖数组、链表、二叉树三个基础数据结构正好串起前五天的练习内容。每道题我都按“题目描述→核心思路→代码→坑点复盘”的顺序展开方便你照着练习也方便以后回头翻阅。2.1 数组与哈希最短覆盖子串的滑动窗口模板题目描述是这样给定一个字符串s和一个字符串t请在s中找出包含t所有字符的最短子串返回最短长度如果不存在返回0。t中的字符可能出现重复比如s ADOBECODEBANCt ABC时最短子串是BANC长度4。这题实际上是“滑动窗口”和“哈希计数”两个知识点的叠加。暴力做法是枚举所有子串再逐个检查是否包含t的所有字符时间复杂度是O(n^3)枚举起点终点要O(n^2)检查每个子串又要O(n)。n稍微大一点基本就跑不过了所以必须用滑窗把枚举检查这个过程压成一遍扫描。from collections import Counter def shortest_cover(s: str, t: str) - int: if not s or not t: return 0 need Counter(t) missing len(t) left 0 ans_len float(inf) for right, ch in enumerate(s): if need[ch] 0: missing - 1 need[ch] - 1 while missing 0: ans_len min(ans_len, right - left 1) need[s[left]] 1 if need[s[left]] 0: missing 1 left 1 return ans_len if ans_len ! float(inf) else 0第一个关键点是missing变量的设计。很多新手喜欢把“检查窗口是否覆盖t”写成单独的函数每次窗口变化都重新统计一遍这样窗口每移动一次就是O(t)的开销。我的做法是维护一个“还缺多少个字符”的计数器只有当need[ch]大于0时说明这个字符是t里仍然缺的此时右指针扫过它缺失数才减1。如果字符根本不在t里need[ch]会变成负数missing不受影响但哈希表里必须记录这个变化因为左指针收缩时要精确还原频次。第二个关键点是收缩条件。窗口满足条件后不能光更新答案还要尝试把左指针往右移看能不能在保证覆盖的情况下把子串缩到更短。收缩时need[s[left]]加回1如果这个字符重新变成“必需但缺失”的状态missing加1循环退出。这一套“右扩左缩”的逻辑就是滑动窗口框架的核心。注意滑动窗口模板里need这个计数器既可能变成负数表示窗口里有多余字符也可能重新变回正数表示又开始缺这个字符了。理解这一点才能理解收缩循环的退出条件。复杂度非常理想每个字符最多被右指针扫一次、被左指针扫一次整体O(n)need字典的空间开销是O(|t|)。这类题思路通了以后代码就那十行真正难的是理解missing和need之间的配合关系而不是把代码背下来。2.2 链表与数学找出环入口的快慢指针题目描述给定一个单链表如果链表中有环返回环的入口节点如果没有环返回None。这题经常被拆成“判断是否有环”和“找环入口”两个小问今天直接合并成一道完整题目来练。先用快慢指针判断有没有环slow每次走一步fast每次走两步。如果fast先到链表尾部说明无环如果slow和fast相遇说明有环。第一次相遇时的位置不一定是环入口所以要再走一次数学推导设链表头到环入口的距离为a入口到相遇点的距离为b相遇点到入口的剩余距离为c环长度L b c。相遇时slow走了a bfast走了a b kL其中k是fast在环里多绕的圈数。因为fast走的路程是slow的两倍就有2(a b) a b kL化简得a b k*L进一步推出a (k-1)*L c。这个式子说的是从头节点出发的指针和从相遇点出发的指针都一步步往前走它们一定会在环入口处碰上。def detect_cycle_entry(head): if not head or not head.next: return None slow head fast head while fast and fast.next: slow slow.next fast fast.next.next if slow fast: break if not fast or not fast.next: return None ptr head while ptr ! slow: ptr ptr.next slow slow.next return ptr这段代码有两个我必须单独拿出来说的坑。第一个是while循环的终止条件。fast fast.next.next要求fast和fast.next都不能为None所以循环条件必须写while fast and fast.next而且两个条件的顺序不能变。如果你先判断fast.next一旦fast本身是None空指针异常就来了。这种顺序细节看起来小但几乎每个新手都会在这里卡一次。第二个坑是无环情况的收尾。循环正常结束后slow可能已经走到了链表的某个中点它跟“环入口”半毛钱关系都没有。判断无环要看fast是否走到了链表尾部——也就是fast为None或fast.next为None。必须加上if not fast or not fast.next这个保护判断然后再进入找入口的二次循环否则你把slow当作入口返回遇到无环用例时答案就是错的。提示快慢指针相遇后不能直接返回相遇点必须先从头节点再走一趟第二次相遇的位置才是环入口。这个结论可以直接用距离公式记住a (k-1)*L c。复杂度方面时间O(n)空间O(1)。快慢指针是链表题里出镜率最高的技巧除了找环还常用于找链表中点、找倒数第k个节点把这一道题吃透等于同时带出了好几个知识点。2.3 二叉树与队列自底向上层序遍历的实现题目描述给定一棵二叉树自底向上逐层返回所有节点值。比如根节点是3左孩子9右孩子2020的左孩子15右孩子7最后要返回的结果就是[[15,7],[9,20],[3]]——底层在前根层在后。这题的核心是层序遍历也就是广度优先搜索BFS。层序遍历有一个非常固定的模板借助队列根节点先入队每次从队列左侧弹出节点记录值再把它的左孩子、右孩子依次入队循环到队列为空。因为要区分“每一层”还得加一个技巧每轮循环开始时先把当前队列长度n存下来然后只弹出n个节点这n个节点恰好就是当前层的全部节点。用for循环控制弹出的次数而不是把弹出和入队混在一起这样level列表才能保存每一层的值。from collections import deque def level_order_bottom(root): result [] if not root: return result q deque([root]) while q: level [] for _ in range(len(q)): node q.popleft() level.append(node.val) if node.left: q.append(node.left) if node.right: q.append(node.right) result.append(level) return result[::-1]这里为什么用deque而不是Python的list加pop(0)因为list.pop(0)的时间复杂度是O(n)每次弹出都涉及后面所有元素整体前移层内节点比较多时累积性能很差。deque是双向队列popleft()均摊O(1)是BFS场景的标准选择。拿到从上到下的层级列表后直接[::-1]反转就是自底向上的结果整体复杂度O(n)额外空间O(n)。如果面试中碰到“能不能不反转”的追问一种想法是把每层结果insert(0, level)但Python的insert(0, ...)也是O(n)操作多次插入反而更慢所以直接反转反而是最高效的。能在代码里讲清楚这个取舍会比单纯背模板显得更扎实。今天这三道题正好把基础的数据结构能力都覆盖到了。做完之后我还顺手整理了一个“套路速查”遇到子串/子数组问题先想滑动窗口遇到链表环/中点问题先想快慢指针遇到树的按层问题先想队列BFS。这种归纳本身就是Day6练习的一部分。3. 实操记录从读题到AC的三个阶段这一节记录的是我实际做题时的完整流程而不是理想化的标准流程。很多人刷题时会跳过一些看起来“不必要”的步骤比如画样例、先写暴力解、整理错误表格但这些步骤恰恰是最省时间的。把它们单独列出来说是因为它们比多刷十道题更能决定你能不能稳定进步。3.1 先画样例再写代码别急着敲键盘每次读完题我给自己一个硬性要求先在草稿纸上写一个不超过10个节点的样例然后用手工的方式把样例完整跑一遍。这个习惯从Day1就开始练到今天已经快变成肌肉记忆了。拿最短覆盖子串举例。s ADOBECODEBANCt ABC。手工推的时候我会把左指针固定在最左端右指针从0开始逐步右移同时在心里默记“当前窗口里A、B、C各出现了几个还缺几个”。右指针走到索引5时窗口变成“ADOBEC”A、B、C齐了缺失数归零记录当前答案长度6接下来左指针右移到索引3窗口变成“OBEC”C还在但A没了缺失数变回1收缩停止。这样手工推完一遍代码里每个分支应该怎么写基本就清楚了。这个过程看着慢其实一道题只多花两三分钟却可以省下后面写代码和调试的大量时间。因为手工推演会让你自然关注边界窗口什么时候满足条件、收缩什么时候停止、答案在哪里更新。很多朋友看到题就立刻打开编辑器一边写一边改改到最后边界还是漏了回头重新推演反而更浪费时间。3.2 从暴力解法到优化先保证会再追求快我还保持着一个习惯如果一道题五分钟内想不出最优解就先把暴力解写出来保证正确性后再优化。今天的三道题除了层序遍历本身就比较模板化另外两题我都在脑子里先过了一遍暴力方案。最短路覆盖子串的暴力方案就是枚举所有子串对每个子串用Counter统计字符频次再和t做一个覆盖比较。代码写起来很简单但复杂度是O(n^3)跑小样例没问题一上大的测试用例就超时。这时候回头分析“慢在哪”因为窗口每次扩展和收缩都在重复统计整个子串的频次。优化的切入点就出来了——用哈希表动态维护窗口内频次把“重复统计”改成“增量更新”。这种“暴力 → 分析瓶颈 → 针对性优化”的路径其实就是大部分标准解题思路的来源。Day6这一天给我最大的体会是优化不是凭空想出来的而是先拥有一个能跑的版本再问自己“哪一步在做无用功”答案往往就是优化的方向。3.3 调试实录今天真实踩到的三个坑今天的三道题我一道都没能做到一遍AC记录几个真实踩坑点。第一个坑在最短覆盖子串里。我把if need[ch] 0: missing - 1写成了if ch in t: missing - 1。乍一看好像差不多但t里有重复字符时就出事了。比如t AAB窗口里只出现了一个A用in t判断就会错误地把missing减成0窗口提前“假满足”答案当然不对。正确逻辑应该是need这个Counter里记录的是“还缺多少”只有need[ch] 0说明这个字符是当前真正缺的才能减少缺失数。第二个坑在找环入口。快慢指针相遇后我第一反应是“把slow当入口返回”。这个想法是错的因为相遇点在环上但不一定是入口。必须先让一个指针从链表头出发和slow同步向前两者再相遇时的位置才是环入口。如果你只练过“判断是否有环”的代码很容易在这里翻车判断有环是对的但返回的节点是错的。第三个坑在层序遍历的for循环里。我写的是for _ in range(len(q))但循环体里又对q执行append操作。range(len(q))的len(q)只在进入循环时求值一次但Python新手容易混淆动态长度的求值时机结果循环次数失控。更稳妥的做法是先把当前层长度存到变量里cur_len len(q)再for _ in range(cur_len)这样即使循环体内改变队列长度也不会影响本层处理次数。把今天踩过的坑整理成一张速查表错误类型出现场景本质原因排查方式计数不准确统计重复字符的题目用in t代替need[x] 0忽略频次手工推演一次窗口变化快慢指针误判入口链表找环入口把相遇点等同于环入口缺少二次推导完整跑一遍有环用例检查返回节点动态长度循环失控BFS按层处理循环长度和出入队操作纠缠不清先保存cur_len len(q)再进入循环这张表我打算留到Day7再翻一遍避免同样的坑犯第二次。4. 刷题避坑与效率提升经验第3节讲的都是今天实际遇到的坑这一节再补充一些更通用的经验也是我觉得坚持到Day6这个节点时特别值得沉淀下来的内容。刷题过程中真正拖慢节奏的往往不是某个算法不会而是那些反复出现的边界错误、低效复盘方式和工具习惯。这些问题只要提前规避每天能少浪费很多时间。4.1 最常见的边界错误速查表刷题这件事边界情况才是真正的分水岭。思路对但边界漏了照样过不了测试。我整理了这几天遇到频率最高的四类边界问题边界类型典型错误后果预防手段空输入函数开头没判断None或空数组空指针/空列表异常程序崩溃养成习惯第一行先判空索引越界访问arr[-1]或arr[n]逻辑错误或下标异常明确循环区间统一使用左闭右开区间死循环快慢指针没有正确移动或滑动窗口left忘记自增程序超时每道题手工推一遍确认循环能走到出口最小规模只测常规用例没测两个元素的反转链表隐藏bug漏过备好最小用例提交前必跑另外两个心得也很实用第一提交平台报错时不要只看“WA”或者“TLE”要复制出错用例到本地跑一遍看它到底是在哪个断言失败。第二遇到TLE先别急着整体重构先用数据规模估算一下复杂度是不是真的有问题有时候只是某一行代码多了一层不必要的O(n)循环。4.2 高效复盘的三个提问复盘这件事比刷题本身更重要。我给自己定的规则是每AC一道题回答三个问题做不到就说明这道题还没消化透。第一个问题这道题有没有更优的解法今天的最短覆盖子串滑动窗口已经是标准最优解但我会再想想“如果t中字符很少是不是可以用其他数据结构”。第二个问题我的解法在边界情况下都能通过吗我会专门构造空输入、只有一个元素、全部元素相同这几个特例去跑。第三个问题这个套路还能用在哪些题上以快慢指针为例AC了环入口之后我会立刻联想到“找链表倒数第k个节点”、“找链表中点”、“判断回文链表”它们本质都是同一套思想。这样复盘一道题相当于复习三到五道同类题。我还会把复盘写进本地笔记不追求文采关键是记录思考过程。Day6结束后我翻前几天的笔记发现Day1写的滑动窗口模板旁边还有一行注释“这里为什么收缩”当时没搞懂的问题今天已经能讲清楚了。这种前后对比就是坚持记录最直接的正反馈。4.3 工具与习惯别让环境拖慢练习节奏练习环境不用复杂但一定要顺手。我目前用的方案是“本地编辑器 简单测试脚本”每道题写完先跑一组本地用例再提交。这样能省下大量反复提交的时间也方便随时调试。测试用例一般固定四类空输入、最小规模、常规规模、极端规模。比如链表题我会准备空链表、只有一个节点、两个节点成环、长链表无环等用例。虽然看起来啰嗦但每次提交前能跑一遍心理会稳很多。还有一个习惯是控制思考时间读题两分钟思考五分钟不会就看题解。我见过一些朋友盯着一道题硬想一两个小时最后既浪费时间又挫败感很强。五分钟没有思路就大方地看题解看懂之后合上题解自己重新写一遍这个“重写”的动作才是真正的学习闭环。最后建议把常用套路模板整理成个人速查笔记。滑动窗口、快慢指针、BFS层序、二叉树递归每个模板都用自己的话重新写一遍不要直接复制网上的。这个过程等于把“别人的理解”变成“自己的理解”。5. Day6复盘坚持六天后的真实变化这一节不聊代码、不讲题目就聊聊连续刷题六天给我带来的那些并不轰轰烈烈但很实在的变化。这些变化不像AC一道题那么有成就感却能让我在第七天早上醒来时愿意继续打开题单。它们也是我认为所有刚开始刷题的人都该提前知道的东西坚持带来的回报往往是延迟出现的。5.1 从“背模板”到“理解模板”刷题的前几天我的学习方式很“机械”看到“最长不重复子串”就套滑动窗口模板看到“层序遍历”就套队列。到了Day6题目开始把多个知识点组合起来我发现自己没法靠背模板过关了必须真正理解每个模板背后的逻辑链条。比如滑动窗口模板里的missing和need为什么能同步变化关键在“频次”两个字上。need不是简单的集合判断它记录的是一个动态剩余的缺口。只有把整个字符频次的增减流程推演过一遍才算真正理解这个模板怎么用。理解和不理解的差别在Day6的三道题里体现得很明显背模板的人遇到变体题会愣住理解模板的人能把模板拆开重组应用到新问题上。坚持六天还有一个意外收获遇到不会的题焦虑感明显变低了。以前看到新题第一反应是“完了我不可能做出来”现在会自然拆解这题考的是数组还是链表还是树大概率该用双指针、哈希还是队列递归。这套“扫描题目并归类”的能力是在每天少量但高质量的训练里慢慢长出来的。5.2 时间分配每天1.5小时怎么安排我这六天的练习时间基本稳定在1.5小时左右具体分配如下阶段建议时长核心任务读题构思20分钟画样例、手工推演、理清边界编码实现30分钟先写能跑的版本再优化复杂度调试测试20分钟最小用例单测再跑极端边界复盘整理20分钟写笔记、归类套路、联想同类题如果某天状态不好就减量不减质哪怕只做一道题也得把这道题吃透。我之前也尝试过一天刷五道题结果到第三天就累得不想打开题库了。调整为“每天一到三道、质量优先”之后反而能稳定坚持下来。刷题本质上是马拉松不是百米冲刺节奏感比单日强度重要得多。5.3 下一步计划与给同样在坚持的人一个建议Day7开始我准备整理动态规划入门先只做最简单的爬楼梯、打家劫舍这类线性DP目标是建立“状态定义 状态转移方程”的思考方式。Day8到Day10继续巩固二叉树和双指针同时每道题都坚持写复盘笔记按“一句题目总结、核心思路、避免再犯的坑”三个部分来组织。如果你也在做编程题练习我特别建议把某一天专门当作复盘节点不一定是第六天但一定要有定时回看的习惯。刷题这个事最怕的就是“刷了很多却不知道自己到底学会了什么”。定期回头看看前几天的笔记你会发现自己其实在实实在在往前走。拿我来说Day1时连递归都要想半天今天已经能流畅地把BFS模板写在纸上并解释每个步骤的原因——这种肉眼可见的变化就是继续坚持下去的最大动力。最后再分享一个小技巧每次做完题把当天用到的模板和踩坑记录存进一个固定的文件里下次动手前先扫一眼真的比临时翻论坛高效很多也能明显感觉到自己正在一点点积累解题手感。这个方法不需要任何高级工具一个笔记软件就够了关键是要坚持记录。Day6的记录就到这里我去准备Day7的题单了。各位也在坚持刷题的朋友咱们明天见。
