算法打卡第9天：四道基础题吃透二分、双指针、链表与二叉树

1. 选题逻辑第九天我为什么还在啃基础题算法题打卡进行到第9天老实说最难的不是做题而是在“今天到底刷什么”上反复纠结。很多人打卡断掉不是不会做是每天打开LeetCode就开始刷首页推荐今天一道图论、明天一道位运算后天又碰上个DP结果什么都没吃透。我第八天结束的时候给自己定了条规矩宁可把一道模板题写三遍也不贪多求快。所以算法题打卡9这天我的题单只有一个方向——把平时最容易在面试里遇到的“套路题”重新过一遍。今天的四道题分别是搜索插入位置、有序数组的平方、反转链表、二叉树的层序遍历。看起来都很基础对应的正是大家常说的LeetCode必刷基础算法题那一批。但基础归基础每一道展开之后都有值得单独拎出来说的点。比如二分查找为什么最后返回的是 left 而不是 right再比如双指针为什么能把 O(n log n) 的平方排序优化成 O(n)这些东西不亲手写一遍代码光看答案解析是记不牢的。考虑到热词里同时提到了 python算法思维题 和 java常见算法题我这次刻意用 Java 做了主实现每个题后面附上 Python 版本对照。不是说哪个语言更好而是想让你看到算法题的思路是语言无关的真正决定你能不能写出来的是你脑子里的模型够不够清晰。2. 第一题搜索插入位置二分查找的一锤定音1.2 题目到底在问什么给定一个排序数组和一个目标值如果数组里存在这个目标值就返回它的下标如果不存在返回它应该被插入的位置。举个例子nums [1, 3, 5, 6] target 5 - 返回 2 target 2 - 返回 1 target 7 - 返回 4 target 0 - 返回 0这道题看着简单但它其实是二分查找里“找左边界”的经典变体。很多人第一次写会用线性扫描从前往后找第一个大于等于 target 的位置。这样当然能做出来但面试官下一句往往是“能不能用 O(log n) 的时间”。到那一刻你要是还没想清楚二分查找的循环不变量就会在 left 和 right 的边界条件里绕晕。2.2 Java 实现与循环不变量的确定直接贴我这次写的 Java 版本public int searchInsert(int[] nums, int target) { int left 0, right nums.length - 1; while (left right) { int mid left (right - left) / 2; if (nums[mid] target) { left mid 1; } else { right mid - 1; } } return left; }写二分查找最重要的不是背模板而是想清楚你的循环不变量是什么。我在这个写法里维护的是left 左边的元素都严格小于 targetright 右边的元素都大于等于 target。在这个前提下每次循环判断 nums[mid] 和 target 的关系如果 nums[mid] target说明 mid 位置不可能是答案而且 mid 左边更不可能是答案所以直接把 left 挪到 mid 1。否则说明 nums[mid] 是大于等于 target 的元素mid 可能是答案但不能排除左边还有更小的符合条件的元素所以把 right 挪到 mid - 1。循环结束时 left right此时 left 指向的就是“第一个大于等于 target 的位置”也就是题目要求的插入位置。针对上面的例子target2 时left 最终会停在 1正好是 2 应该插入的位置。Python 版本几乎一模一样def searchInsert(nums: list[int], target: int) - int: left, right 0, len(nums) - 1 while left right: mid (left right) // 2 if nums[mid] target: left mid 1 else: right mid - 1 return left2.3 为什么返回值是 left 而不是 right这是这道题最容易让人卡壳的地方。你去看很多题解知道要返回 left但不知道为什么。我当时理解透这一点是在纸上把最后一次循环推了一遍之后。假设 nums [1, 3, 5, 6]target 4。一开始 left0right3mid1nums[1]3 4所以 left 变成 2。此时 left2right3mid2nums[2]5 4所以 right 变成 1。循环结束left2right1而 4 确实应该插在下标 2 的位置。你会发现循环结束的时候right 停留在“最后一个小于 target 的元素”的位置left 停留在“第一个大于等于 target 的元素”的位置。我们要找的是插入位置也就是“第一个大于等于 target”的位置所以答案是 left。如果你非要返回 right那得到的就是前一个元素的下标在插入逻辑里就错了。2.4 二分查找的边界坑位我这次复习时在几个边界细节上专门做了测试分享给你mid 的计算用 left (right - left) / 2不要写成 (left right) / 2。虽然 Java 里数组长度不太可能大到溢出但这是个好习惯尤其当你在 C 里处理很大的边界值时这一步能直接避免整数溢出。while 的条件用 而不是 。如果用 循环结束的条件会不同最后返回的 left 可能不准。关键在于你的循环不变量是怎么定义的我建议你固定使用 这个版本因为它在“空区间”出现的时候left 正好是目标位置。数组为空的情况如果 nums.length 0循环根本不进入直接返回 0。这个边界很多初学者会忽略但实际跑测试用例的时候它经常是第一个报错的地方。3. 第二题有序数组的平方双指针比排序快在哪3.1 普通做法和优化做法的分水岭题目描述很简短给你一个按非递减顺序排序的整数数组 nums返回每个数字的平方组成的新数组要求也按非递减顺序排序。比如输入 [-4, -1, 0, 3, 10]输出 [0, 1, 9, 16, 100]。最直观的做法是先把每个数平方再对整个数组排序。代码就两行int[] res new int[nums.length]; for (int i 0; i nums.length; i) { res[i] nums[i] * nums[i]; } Arrays.sort(res); return res;这个版本的复杂度是 O(n log n)问题主要出在排序上。但你要是观察一下原始数组的特征会发现一个很关键的性质原数组本身就是有序的只是因为负数平方之后可能变大导致平方后的数组不再单调。可你有没有注意到平方之后最大的数一定出现在原数组的两端不是最左边就是最右边。这句话就是双指针解法的出发点。既然最大的元素位置可以确定那我从两端往中间走每次比较两端谁更大谁就放到结果数组的最右边接着缩小范围结果数组自然就是从前往后递增的。整个过程只需要一次遍历时间复杂度 O(n)空间复杂度 O(n)保存结果数组。3.2 双指针代码的完整推导Java 版我写的是这个public int[] sortedSquares(int[] nums) { int n nums.length; int[] res new int[n]; int left 0; int right n - 1; int index n - 1; while (left right) { int leftSquare nums[left] * nums[left]; int rightSquare nums[right] * nums[right]; if (leftSquare rightSquare) { res[index] leftSquare; left; } else { res[index] rightSquare; right--; } index--; } return res; }我每次比较的是 nums[left] 的平方和 nums[right] 的平方谁大谁就放到 res[index] 的位置然后 index 往左移一格相当于从结果数组的末尾往前填。因为每次放进去的都是当前剩余部分里最大的平方数所以整体填下来res 从后往前是递减的从前往后看就是递增的。这里有个小细节值得注意很多人会倾向于先比较 nums[left] 和 nums[right] 的绝对值再算平方。功能上没区别但直接算平方会让代码更直观特别是有负数的场景下你不需要额外解释 abs 的意图。你自己选一种固定的习惯就行。Python 版本def sortedSquares(nums: list[int]) - list[int]: n len(nums) res [0] * n left, right, index 0, n - 1, n - 1 while left right: left_sq, right_sq nums[left] ** 2, nums[right] ** 2 if left_sq right_sq: res[index] left_sq left 1 else: res[index] right_sq right - 1 index - 1 return res3.3 这个解法背后的思维模型你在做题的时候一定会遇到“看起来排序能解决但面试官非要你优化”的场景。这道题就是一个典型。它背后的思维模型是数组已经有序哪怕做了一些变换原有的有序信息也没完全失效只是需要换一种角度去利用。所有负数的平方在数组左半段是递减的所有非负数的平方在右半段是递增的相当于有两个有序序列现在要做的就是“合并”这两个序列。双指针从两端往中间走本质上就是在合并两个有序序列每次取大的那一个。想通这一点之后你会发现很多题都能套这个模型。比如后面常见的“合并两个有序数组”、“有序数组去重”、“容器盛水最多的双指针”都是类似的思想。3.4 常见翻车点填充顺序搞反我第一次自己写这个题的时候犯过一个不算低级但很容易犯的错误我用了两个指针从中间往两边走然后试图从头开始填充 res。结果发现每次选出来的都是局部最小的最后 res 的前半段顺序是乱的。正确做法一定是从两端往中间找最大从后往前填充结果。换句话说你要找的是当前剩余范围内的“最大值”而不是“最小值”。如果反过来问“所有平方数里最小的怎么找”思路其实也成立但你需要额外处理负数和非负数之间的边界复杂度会明显增加完全没有必要。4. 第三题反转链表迭代和递归缺一不可4.1 为什么这道题是面试高频题单链表反转几乎是我见到的面试题里出现频率最高的一道。有的公司会把它当成热身题有的公司会在你写错指针的时候直接结束考察。原因很简单题目本身不难但它能一次性考察你对链表结构的理解、对指针操作的熟练度以及边界条件的处理。题目描述就一句话给你单链表的头节点 head 请你反转链表并返回反转后的链表。比如 1 - 2 - 3 - 4 - 5反转后变成 5 - 4 - 3 - 2 - 1。如果只在脑子里面想反转就是把每个节点的 next 指向前一个节点。真动手写代码的时候你马上会碰到一个问题当你把当前节点的 next 改掉之后原来的下一个节点就找不到了。所以你这个操作的顺序必须是先保存下一个节点再改当前指针。4.2 迭代解法三指针模型public ListNode reverseList(ListNode head) { ListNode prev null; ListNode curr head; while (curr ! null) { ListNode next curr.next; // 先保存下一个节点 curr.next prev; // 反转当前节点指针 prev curr; // prev 前进 curr next; // curr 前进 } return prev; }整个过程可以想象成一条链条被一节一节地拆下来然后重新串到另一个方向。prev 始终指向“已经反转好的那部分链表的头”curr 指向“当前待处理节点”next 负责记住“还没处理的原链表剩余部分”。循环结束后curr 变成了 null说明所有节点都处理完了此时 prev 就是新链表的头。边界情况head 本身是 null或者只有一个节点循环里要么不进入要么只处理一次这两种情况都能正确返回不需要额外写 if。4.3 递归解法想清楚子问题返回什么递归版本是很多人理解起来比较吃力的地方。代码很短public ListNode reverseList(ListNode head) { if (head null || head.next null) { return head; } ListNode newHead reverseList(head.next); head.next.next head; head.next null; return newHead; }我自己当初学的时候最大的困惑是这代码看起来根本“没有做反转”就像套了个壳。后来我换了个角度理解一下子就通了。当你调用 reverseList(head.next) 时它返回的是什么它是“以 head.next 为头节点的那条链表反转之后的新头节点”。你不需要关心它内部是怎么做到的你只需要相信这个递归调用能把后面那一整串都反好。反好之后原来的 head.next 变成了新链表的尾节点此时让这个尾节点的 next 指向 head就相当于把 head 接到了反转后链表的末尾。最后再让 head.next null把头节点变成新的尾节点整个链表就反转完了。这里面最神奇的一行是head.next.next head。我第一次看到这个写法的时候觉得是绕口令但确实就是核心。如果你想验证可以拿 1 - 2 - 3 这个三节点链表在纸上把每一层递归的返回值标出来reverseList(2) 返回 3 - 2然后 2.next.next 2也就是 3.next 2再把 2.next null就得到了 3 - 2 - 1。4.4 面试追问递归版本的风险面试时一旦你写出了递归版本面试官有极大概率会追问一句“这个版本有什么问题”。答案就是当链表非常长时递归深度等于链表长度可能会导致栈溢出。所以实际开发环境里处理长链表我更推荐迭代版本。面试时如果时间够我一般会把两种版本都写一遍然后主动解释它们的取舍这比等对方面试官来问效果更好。迭代版本时间 O(n)、空间 O(1)递归版本时间 O(n)、空间 O(n)隐式调用栈。这道题也让我意识到刷题的时候不要只看“能不能过”还要主动去思考每种解法在极端场景下的表现。5. 第四题二叉树层序遍历一套模板吃透所有层次遍历5.1 BFS 标准模板二叉树层序遍历的题目描述是给你二叉树的根节点 root返回其层序遍历结果每一层的节点值放在一个子列表里。比如输入root [3, 9, 20, null, null, 15, 7] 输出[[3], [9, 20], [15, 7]]这个题的核心就是广度优先搜索BFS只不过普通的 BFS 只输出节点值而层序遍历要求你按“层”把结果分隔开所以需要额外做一层“分层”处理。Java 代码public ListListInteger levelOrder(TreeNode root) { ListListInteger res new ArrayList(); if (root null) { return res; } QueueTreeNode queue new LinkedList(); queue.offer(root); while (!queue.isEmpty()) { int size queue.size(); ListInteger level new ArrayList(); for (int i 0; i size; i) { TreeNode node queue.poll(); level.add(node.val); if (node.left ! null) { queue.offer(node.left); } if (node.right ! null) { queue.offer(node.right); } } res.add(level); } return res; }这里面最关键的一行是int size queue.size();必须在进入 for 循环之前固定下来。如果你把循环条件写成for (int i 0; i queue.size(); i)queue.size() 在循环过程中会一直变化因为每次 poll 一个节点之后又马上 offer 了它的左右孩子队列的大小并不是固定的最后各层节点就会混在一起输出结果完全错乱。5.2 一个 Python 版本的直观对比如果你平时写 Python 更顺手层序遍历用队列也是一样的写法from collections import deque def levelOrder(root): res [] if not root: return res queue deque([root]) while queue: size len(queue) level [] for _ in range(size): node queue.popleft() level.append(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) res.append(level) return resPython 里len(queue)在 for 循环外就已经固定了而且 deque 的 popleft() 是 O(1) 操作比 list.pop(0) 快很多。如果你是做 Python 算法题的建议直接养成用 deque 的习惯不要用 list 来模拟队列否则遇到大数据量测试用例很容易超时。5.3 同一套代码改三个变形题层序遍历这个模板吃透了能直接解决好几道题。我这次打卡顺手把变体也过了一遍这里列出来给你作为后续练习参考自底向上层序遍历最后把 res 反转一下就行Java 里用 Collections.reverse(res)Python 里用 res[::-1]代码其他部分完全不用动。二叉树的右视图按层遍历时只保留每层的最后一个节点值也就是内层 for 循环结束后把 node.val 加入结果而不是把整层列表加入结果。之字形层序遍历按奇偶层处理。如果当前层是偶数层正常从左往右如果是奇数层把这一层的列表反转之后再加入结果集。很多实现里会直接用双向链表头部插入尾部插入来回切换但我觉得先正常 BFS 再单独处理反转理解起来更容易代码也更好读。这道题给我最大的启发是算法模板不是背下来的而是通过一道题练熟之后自然迁移的。层序遍历的模板一旦熟练后面遇到矩阵的 BFS、图的层级遍历、甚至拓扑排序的队列实现都会有天然的熟悉感。6. 踩坑实录今天翻车的四个细节今天的四道题都不是第一次写了但我在重新敲代码的时候还是踩了几个不大不小的坑。这里全部记录下来建议你刷到同类题的时候先避开。问题场景错误写法正确写法一句话原因二分查找的循环条件while (left right)while (left right)循环不变量要求区间里至少留一个候选元素构造平方数组的填充方向从前往后填 res从后往前填 res双指针每次找的是当前最大必须从末尾放反转链表丢节点先改 curr.next 再保存 next先保存 next 再改 curr.next改指针后原链表关系失效不保存就找不到了层序遍历的队列大小for 循环里动态取 queue.size()循环前固定 int size queue.size()队列在遍历中会不断进新元素动态取会混层第六天和第七天打卡的时候我就栽在“以为会了就不用重新敲”这个心态上。这次我学乖了每道题先自己写写完之后再对照题解重点看那些“我跳过去但其实是关键”的地方。比如二分查找的返回值逻辑我第无数次提醒自己循环退出时 left 才是边界位置right 是补刀的那一个。如果你也在用类似“算法题打卡”的方式刷题我强烈建议你留一个笔记文件把每次踩坑记录成表格。这个动作花不了几分钟但等到第三周复盘的时候你会发现自己当初最容易错的地方就那么三四个早一点记录就能早一点形成肌肉记忆。7. 打卡第九天之后我对刷题的几点真实体会写到这里想说点跟题目本身无关但跟打卡强相关的东西。我见过不少朋友信誓旦旦地说要每天刷一道题结果坚持了不到一周就因为“今天太忙”“题目太难”“没啥效果”放弃了。作为一个已经连续打卡九天的过来人我的体会是算法题打卡能不能坚持下去关键不在于意志力而在于你每天给它分配的任务量是否足够小。我给自己定的规则很简单每天只做 2 到 3 道题做不到就只做 1 道。如果某道题真的毫无思路看题解也可以但看完题解之后必须关掉答案自己重新敲一遍隔天再复现一次。这个“隔天复现”的动作比我当天连做五道题都管用。很多知识当天看着懂了睡一觉就还回去了复现才是真正把它变成你自己的东西的唯一路径。第九天打卡结束的时候我回头看这几天覆盖的题目发现它们渐渐连成了一张网。二分查找、双指针、链表反转、层序遍历表面上是四个互不相干的专题但底层都在训练同一件事在处理数组、链表、树这些结构时你如何用一个简洁的状态模型在一个清晰的循环或递归里完成任务。这种能力的提升不是立竿见影的但当你写到第二十道、第三十道的时候会突然发现看题的速度变快了思路也不容易乱了。如果你也想开始自己的打卡计划建议你先别管“必刷题单”有多长就按今天这个组合来一道二分、一道双指针、一道链表、一道二叉树难度都不高但覆盖了四个最常见的考察方向。把这一组吃透再去碰更难的题你会感觉到明显的不同。