1月13号星期二。这是我在牛客网上连续打卡刷题的第61天。今天的计划不是学新知识点而是做一轮“拉练”把数组、链表、二叉树、动态规划这四个方向上出镜率最高的题型重新过一遍总共11道题简单4道、中等6道、困难1道。到晚上复盘时9道是一次AC2道看了题解才写出来。这篇文章就是今天的完整刷题记录——不仅记题目和代码更会把每道题背后的套路、我在现场踩过的坑以及一些只靠看题解学不到的判断经验写出来。如果你也处于春招实习的准备阶段正好可以拿这份笔记当参考。1. 牛客网刷题计划今天练什么、为什么这样练1.1 今日题单与难度分布今天的题单不是随手点的而是按照“面试考什么、我就练什么”的原则排的。每天早上我会花10分钟左右先列好清单避免打开牛客网之后被各种推荐题带偏。方向题目难度我的结果数组两数之和NC61简单AC数组三数之和中等AC数组合并两个有序数组NC22简单AC链表反转链表NC78简单AC链表合并两个有序链表NC33简单AC链表链表中环的入口节点NC3中等AC二叉树求二叉树的层序遍历NC15中等AC二叉树按之字形顺序打印二叉树NC14中等AC二叉树二叉树的最大深度NC104简单AC动态规划最长上升子序列(一)中等看题解动态规划接雨水问题NC128困难看题解11道题里数组和链表各3道二叉树3道动态规划2道。这个组合是我最近调整出来的“四三二一”比例四成题目用来保持代码手感三成题目用于巩固高频套路两成题目挑战中等偏上难度剩下一成专门留给困难题“压惊”。理由是面试中80%的算法题不会超过中等难度能把简单和中等题稳定写出最优解比硬啃困难题更划算。1.2 为什么今天要选这四个方向先解释一下选题逻辑省得有人觉得我在乱刷。数组题是所有算法题的底座排序、双指针、哈希、二分、滑动窗口都长在数组上链表题则是面试官最爱的“指针操作题”考察的就是你手稳不稳边界条件想不想得全。二叉树是递归思维和层次遍历的集中训练场很多高阶题目——比如二叉树转链表、最近公共祖先——本质上是把树的遍历玩出花来。而动态规划之所以放在最后是因为它最吃“状态定义”的功力需要单独留出整块时间思考不能像数组题那样闭眼写。时间上我也做了约束上午连续做题90分钟不中途看手机下午用40分钟整理错因晚上再花半个多小时把看题解的2道题重新手写一遍。整个周期大概3小时。刷题最怕“假努力”——题做了不少回头一问原理全忘。所以今天我会重点记录每一题为什么这么解而不是只贴AC代码。2. 高频题目核心解法拆解2.1 双指针的三种展开左右、快慢、滑动窗口双指针之所以是数组题里的绝对高频考点核心原因只有一句话它能把双重循环甚至三重循环的时间复杂度降一个量级代价只是多维护几个下标。先看最经典的两数之和NC61。暴力做法是两层循环O(n²)——第一层固定一个数第二层找另一个。优化方案是用哈希表把“找另一个数”的操作从O(n)降到O(1)整体O(n)。但很多人不知道还有另一种思路先排序再让左右两个指针从数组两端往中间走两数之和太大就右指针左移太小就左指针右移同样是O(n)。两种方案一种适合返回下标一种适合返回数值本身且要求空间O(1)。然后是快慢指针。链表判环和找环入口NC3都是快慢指针的典型应用。慢指针每次走1步快指针每次走2步如果有环两者必然在环内相遇。找入口节点还要再推一步相遇后让慢指针重新回到头节点快指针留在原地两个指针各走1步再次相遇的位置就是环的入口。这个结论我第一次看时觉得像魔术但自己推导一遍就理解了——本质是路程差等于环长度的整数倍。滑动窗口本质上也是双指针只是两个指针的移动方向相同。比如最小覆盖子串这类题right指针不断右移扩展窗口直到窗口里包含目标所需的全部字符然后left指针右移尽量缩小窗口。这类题的难点不是双指针本身而是“窗口内状态怎么维护”经常要配一个计数数组或哈希表。2.2 链表题的“哑节点”技巧链表题里有一个出场率极高的技巧——哑节点dummy node。我刷题前期经常在合并链表、删除节点这类题上卡住原因不是思路不对而是要单独处理头节点变化的情况代码写得很丑边界一多就出错。哑节点解决的就是这个问题在真正的头节点前面额外创建一个节点让它的next指向原链表头。这样做的好处很直接——头节点也可以像普通节点一样被“统一处理”不需要在循环里额外判断。拿合并两个有序链表NC33举例。如果不用哑节点合并时第一个节点到底选谁要先比较l1和l2的头节点再决定新链表的头是谁然后进入循环逻辑能写但很啰嗦。用了哑节点代码就变成def mergeTwoLists(l1, l2): dummy ListNode(0) cur dummy while l1 and l2: if l1.val l2.val: cur.next l1 l1 l1.next else: cur.next l2 l2 l2.next cur cur.next cur.next l1 if l1 else l2 return dummy.next注意最后返回的是dummy.next而不是dummy。这是初学者最容易犯的错——返回了哑节点本身导致答案多了一个0。我把这个错误写进今天的踩坑记录里了后面再说。哑节点还能用在“删除链表倒数第K个节点”上。删除倒数第K个需要找到倒数第K1个节点让它的next跳过目标节点。用快慢指针快指针先走K步慢指针从哑节点出发然后两个指针同步走快指针走到尾时慢指针正好停在目标节点的前一个位置。这个套路配合哑节点写出来几乎零边界问题。2.3 二叉树层序遍历一个模板吃掉三种题二叉树的层序遍历NC15是我认为投入产出比最高的模板题。为什么因为牛客网上一系列中等题——之字形打印NC14、右视图、二叉树最大宽度、层内最大值——全都建立在同一个模板之上。先看最基础的层序遍历代码from collections import deque def levelOrder(root): if not root: return [] ans [] q deque([root]) while q: size len(q) level [] for _ in range(size): node q.popleft() level.append(node.val) if node.left: q.append(node.left) if node.right: q.append(node.right) ans.append(level) return ans关键点在于“size len(q)”这一行。它记录的是当前层的节点数随后for循环只处理这一层保证level数组刚好是当前层的节点。如果不做这一步队列里会混入下一层节点层就分不开了。在这套模板之上任何变体都是小改之字形打印只是根据当前层数决定要不要把level数组反转一次右视图就是取每一层最后一个节点二叉树最大深度就是统计一共弹出了多少层。刷到后来你会发现真正面试的时候考官不会考你写过多少种树题而是看你能不能把一道陌生题目往已知模板上靠。2.4 动态规划的状态定义先想清楚dp[i]是什么今天卡我时间最长的不是接雨水而是那道中等题最长上升子序列(一)。原因很实在状态定义想偏了后面全是白做。动态规划题第一件事不是写代码而是问自己三个问题状态表示什么转移方程怎么写初始值是什么最长上升子序列的标准状态是dp[i]表示“以nums[i]结尾的最长上升子序列长度”。为什么要强调“以nums[i]结尾”因为只有把当前元素作为子序列的末尾才能和前面的元素建立起清晰的依赖关系。转移方程也不难写遍历i之前的每个j如果nums[j] nums[i]说明nums[i]可以接在nums[j]后面形成更长的上升子序列于是dp[i] max(dp[i], dp[j] 1)。初始时每个元素单独成一个子序列所以dp数组全部初始化为1。def lengthOfLIS(nums): if not nums: return 0 dp [1] * len(nums) for i in range(len(nums)): for j in range(i): if nums[j] nums[i]: dp[i] max(dp[i], dp[j] 1) return max(dp)今天我的问题出在把状态定义成了dp[i]表示“前i个元素的最长上升子序列长度”这样定义听起来很自然但遇到nums[i]必须被使用的情况时转移关系就很难写清楚。后来重新把状态改成“以当前元素结尾”整个思路马上顺了。这说明状态定义直接决定了算法的上限宁可多花5分钟把定义想清楚也不要急着敲代码。3. 现场做题记录三数之和的完整推演3.1 题目要求与暴力解法为什么不可行看题给定一个数组nums找出所有三元组[nums[i], nums[j], nums[k]]满足i、j、k互不相同且nums[i] nums[j] nums[k] 0并且不能包含重复的三元组。第一反应肯定是暴力三层循环枚举所有三元组判断和是否为0。但马上算一下复杂度三重循环是O(n³)。如果n是3000那就要执行约270亿次基本操作任何线上判题环境都不可能通过。这还不算去重——暴力解法里还要对结果做一套相当麻烦的判重逻辑复杂度只会更高。所以这道题的考察点从来不是“能不能做出来”而是“能不能在O(n²)时间内写对”。我把它作为今天的重点复盘题是因为它把排序、双指针、去重这三个基本功浓缩在一道题里一道题吃透数组类很多题都能顺手。3.2 排序双指针的具体实现优化思路分两步。第一步先排序这是关键排序有两个好处一是让相同的元素聚在一起去重变得简单二是让双指针找数成为可能。第二步是固定第一个数让双指针在剩余区间里找另两个数这样三重循环被降为一层循环加一次线性扫描总复杂度O(n²)。代码我贴在下面每行都有注释配合后面的解释看def threeSum(nums): nums.sort() n len(nums) res [] for i in range(n - 2): if i 0 and nums[i] nums[i - 1]: continue left, right i 1, n - 1 while left right: total nums[i] nums[left] nums[right] if total 0: res.append([nums[i], nums[left], nums[right]]) left 1 right - 1 while left right and nums[left] nums[left - 1]: left 1 while left right and nums[right] nums[right 1]: right - 1 elif total 0: left 1 else: right - 1 return res这里有几个容易出错的细节。外层循环为什么只到n-2因为要留出两个位置给left和right如果i到了倒数第二个位置区间里只剩一个数凑不齐三元组。然后在进入每个i时先判断当前元素和上一个是否相等——如果相等就跳过这是第一个去重保证第一层循环不选到一样的数。3.3 去重与指针移动的三个关键细节很多人把三数之和看懂了但一写就错错就错在去重的位置不对。第一个去重在外层nums[i] nums[i-1]时跳过。这里注意是跟前一个比较不是跟后一个。如果写成nums[i] nums[i1]然后跳过会错误地丢掉合理组合。比如数组[-1,-1,2]固定第一个-1时双指针能找到[-1,-1,2]这个组合但如果是跟后一个比较第一个-1会被跳过整个组合就丢了。判断顺序必须是i 0防止i为0时访问nums[-1]。第二个去重在内层当找到一个有效组合后left指针右移但右移前要一直跳掉和当前位置相同的元素。我这个实现里写的是“left 1之后再判断nums[left] nums[left-1]就继续跳”这样保证找到组合后left不会再次指向同一个值。right同理。这两个内层去重写完整个结果数组就不会出现重复三元组。第三个细节最隐蔽找到一组答案后left和right要同时移动一位而不是只动其中一个。只动left的话三个数的和要么变大要么变小但都不可能再等于0而且可能产生额外计算同时移动是效率和安全性的双重保证。验证的时候我跑了几组典型用例。空数组返回空列表长度小于3也返回空列表全0数组[0,0,0]返回[[0,0,0]]数组[-1,0,1,2,-1,-4]返回[[-1,-1,2],[-1,0,1]]单元素或双元素数组都不崩。边界用例全部通过后再提交一次AC。3.4 从这道题里提炼的通用方法论三数之和做完我想说的不是这道题本身而是它背后的一类套路凡是“找几数之和满足条件”的题都可以往排序和双指针上靠。两数之和能哈希也能双指针四数之和在固定前两个数之后后续区间依然是双指针收敛。这就是为什么我建议在牛客网刷题时把同一类题放在同一天集中做——你会发现套路是可以迁移的而不是一道题背一段代码。另外这道题也再次证明了一个经验考试时优先考虑O(n²)解法别一上来就想O(n³)降不下来就放弃。排序本身O(n log n)在n²面前可以忽略所以排序双指针的组合在数组题里能覆盖绝大多数中等题。4. 刷题踩坑记录与问题排查实录4.1 边界条件空数组、单元素、全是重复值今天踩的第一个坑不大不小——反转链表NC78在链表为空时我的初始写法直接返回了None提交居然AC了但我回头看代码发现是因为我没处理空链表而head.next在head为None时会直接抛异常。我的第一版代码写得碰巧安全但我不能依赖“碰巧”。正确的做法是拿到题目先想四类边界空输入、单元素、首尾位置、全是重复值。单元素数组在双指针里尤其危险left从1开始、right从0开始循环条件直接不成立不会崩但如果你在循环外访问了数组的某个下标就会越界。全是重复值的数组则是去重逻辑最大的考验很多题目在数字全部相同时错误率极高比如三数之和里全是0的用例如果去重写反要么返回空列表要么报重复。把这些边界整理成一张checklist每次提交前过一遍能省下好几轮编译错误。我之前面试时遇到过一位候选人代码主逻辑没问题就是没判断空树结果levelOrder第一行就崩。面试官不会直接说“你挂在这了”但心里已经扣了印象分。4.2 二分查找里的整数溢出今天虽然没直接写二分题但我在写合并两个有序数组时想到一个经典坑二分查找里中点的计算很多人习惯写mid (left right) / 2。这在Python里问题不大因为Python的整数不限制位数但如果你用Java或C当left和right都接近int上限时left right会直接溢出成负数mid瞬间变成负值二分直接乱套。正确写法是mid left (right - left) / 2或者更底层的位运算写法mid left ((right - left) 1)。这两种方式从数学上等价但第一种更直观推荐新手默认用这个。这个坑我在LeetCode和牛客上都踩过而且是在反复调试才发现的——报的错根本不是“溢出”而是“数组越界”因为负数下标访问数组抛异常很容易误导排查方向。4.3 递归的隐性成本栈溢出与重复计算今天做二叉树最大深度时第一版我用递归写的def maxDepth(root): if not root: return 0 return 1 max(maxDepth(root.left), maxDepth(root.right))代码很短逻辑也对但有两个隐患。第一如果二叉树退化成一条链递归深度等于节点数节点数一多就可能栈溢出。第二如果递归函数里存在重复调用——比如某些树的题里对同一棵子树递归多次——会导致大量重复计算时间直接爆炸。我养成的一个习惯是树类题目优先想迭代方案尤其是层序遍历相关的题BFS模板是可复现的、不依赖系统栈的。递归确实优雅但面试现场你永远不知道测试数据有多深稳妥才是第一位的。今天做之字形打印二叉树时我硬逼着自己用迭代写完实际代码量和递归版本差不多但心里踏实很多。4.4 死循环while条件里的指针更新位置今天唯一一次代码超时不是算法复杂度问题而是死循环。写链表合并的while循环时我一开始写成了while l1 and l2: if l1.val l2.val: cur.next l1 l1 l1.next else: cur.next l2 l2 l2.next这段代码本身没问题问题出在我一开始忘记在循环末尾写cur cur.next导致cur永远指向哑节点每次循环都覆盖同一个next链表永远连不完循环也不会终止。这种错误编译器不会报错只有程序跑起来才会卡住排查起来很费时间。后来我总结出一个口诀双指针/链表遍历题循环体的最后一定要问自己一句“谁在往前走”。left和right有没有更新cur有没有更新快指针有没有走得比慢指针快把这三句问完死循环基本能规避掉80%。4.5 今日问题速查表问题现象根因解决套路返回结果多出一个0返回了dummy节点而不是dummy.next记住哑节点只是辅助结果永远从dummy.next取相同三元组重复出现外层或内层去重缺失外层比较i和i-1内层找到结果后跳值单元素/空数组直接崩没做边界判断先处理n2或空输入再写主逻辑二分中点算出负数leftright溢出mid left (right-left)//2编译器不报错但运行超时循环无进展变量确认所有指针在每轮循环都会移动动态规划状态想不清dp定义含混状态里明确“以当前元素结尾”这类限定词这张表我每周更新一次把当周踩过的坑集中整理周末统一重刷一遍错题。它的作用超过了任何一本参考书。5. 关于刷题节奏和学习方法的几点建议5.1 一天刷多少题合适这是我在各个技术社区被问得最多的问题。我的答案是质量远比数量重要但数量是质量的引擎。如果你每天只刷1道题很难形成套路记忆今天学会的双指针下周就忘如果你一天刷20道后面10道基本是肌肉记忆根本没动脑。我比较推荐的分配是实习冲刺期每天6到8道新题加上3道错题持续2到3个月如果是上课期间时间不够就每天2道新题加上1道复习但必须保证周末有3小时整块时间做大一次总结。今天这种“拉着练”的节奏两周一次就行太频繁会挤占正常知识点学习时间太少又起不到查漏补缺的作用。5.2 牛客网题单怎么选最有性价比牛客网上的题单很多我的选择原则是“先跟榜、再自建”。前期直接用平台整理的“热门题目”和“剑指offer”题单因为这些题目是多年面试数据的沉淀高频考点集中刷熟之后我开始按自己的弱项自建题单比如我动态规划弱就连续一周只刷dp题每天在题单里选几道不同状态的题来练。一个容易犯的误区是盯着题单从头刷到尾遇到不会的题硬扛一小时不出来。性价比最高的做法是一道题思考20分钟没有突破立刻看题解看懂后关掉题解自己重写一遍第二天再独立重写一遍。能在48小时内独立AC两道相同题型才算真正吸收了。5.3 错题本不只是抄题和贴代码我自己的错题本有三个栏目题目、我当时的错误思路、正确解法和原因分析。反复出现的错误我会加一行“高频错点”标签。比如我今天在表格里记录的“返回dummy.next而不是dummy”就属于那种你犯过一次、下次一定不想再犯的错误。最后一个细节建议错题本要手写不要用打字替代。手写会强迫你放慢速度把逻辑在脑子里重新过一遍这和纯复制粘贴代码的效果完全不同。我坚持写了61天今天能在一道中等题上一次AC靠的正是这些积压下来的错题复盘。记录到最后说一下我个人最深的体会。刷题不是比谁刷得多而是比谁在每道题上留下的思考痕迹深。我今天看题解的这两道题如果只是看懂就关掉一周后必然忘光光但把它们写进这篇笔记里把当时的卡点、优化路线、边界设计全部记录下来思维被强行拉高了一个层次。这是我连续打卡第61天的真实感受。你如果也想认真准备面试不妨从今天开始建立属于自己的刷题笔记——不用等什么特殊的日子就现在。