刷完 24 道 Kata：学会问一个更好的问题

我把 Kata 当成一个练习解题的地方，而不是攒题的地方。

我想养成的习惯很朴素：把题目慢慢读一遍，写下第一个想法，找到这个想法在哪里会崩，再把那团乱糟糟的推理收拾干净。刷到第 24 题时，真正留在我脑子里的不是某一个算法，而是一个更小、更安静的转变：一开始该怎么问这个问题。

完整项目：Kata

记住对的东西

前面几题是常见的数组、字符串和查找，但它们与其说考技巧，不如说考“记忆”：我在数据里穿行时，到底想记住什么？

Two Sum 是最干净的例子。我的第一反应是老实的暴力解，两两都试一遍，能过，只是慢。让它塌成一次遍历的，不是什么技巧，而是换了个问法。与其问“哪两个数加起来等于 target”，不如问“我手上这个数，它缺的另一半是谁，而我之前是不是已经见过它了”。问题一旦这样问出来，用哈希表存答案就成了顺理成章的事。

接下来几题靠的是同一种直觉。Contains Duplicate 从头到尾只问“我见过它没有”，所以 set 比 list 更合适。Valid Anagram 多走一步，不光要知道某个字符出没出现过，还要知道出现了几次，于是该记的就不是 set，而是一张频次表。结构不同，底下是同一个动作：在伸手去拿数据结构之前，先想清楚它要回答的是哪个问题。

边界干的活比看上去多

有几道题，真正的主角是边界，不是元素。

Binary Search 里诱人的画面是“把数组切开，看中间”。真正的活儿要安静得多：攥住 left 和 right 两个边界，一边收缩，一边别把真实下标弄丢。First Bad Version 把这一点磨得更利，因为它根本不是在找某个值，而是在找条件从“好”翻成“坏”的第一个位置。这个重新定义会把更新规则整个改写。如果 mid 是好的，它不可能是答案，就越过它到 mid + 1；如果 mid 是坏的，它也许仍是最早那个坏版本，就把它留在范围里。原来二分不在于中间那个元素本身，而在于我可以安心扔掉哪一半。

当窗口不肯乖乖听话

Maximum Subarray 是最早悄悄改变我思路的题之一。

它看着像区间题，让人忍不住想滑动左右边界，问“最好的子数组该从哪开始”。但负数会把这幅画面打碎。有时候正确的动作不是把左边界挪一格，而是把身后整段前缀干脆丢掉。真正立得住的问法更窄：以当前这个位置为结尾、必须落在这里的子数组，最大和是多少？

这个状态很好维护：

current = max(nums[i], current + nums[i])

这是我第一次感到，解法不再是手动挪指针，而是给一个状态命名，然后让它一路滚下去。Climbing Stairs 是同一副骨架。你可以去数用了几个 1 步、几个 2 步，很快就绕晕；也可以问，踏上第 n 级的最后一步能是什么。要么从 n - 1 上来，要么从 n - 2 上来，于是整道题只依赖这两个。

指针不是值

链表那几题几乎不像算法，它们考的是你有没有老实面对：一个变量到底指向什么。

Merge Two Sorted Lists 里，比较本身没什么难的，真正的问题是我挑中一个节点之后，把它接到哪儿。这正是 dummy 头和 tail 指针存在的理由：它们让我不必把第一个节点当特例，就能顺手把结果串起来。Reverse Linked List 看着更简单，却教了我更多，因为它逼我面对一个一直被我糊弄过去的基本问题：head 是值，还是节点？只有把三件被搅在一起的事分开，它才想通：current.val 是节点里的值，current.next 是下一个节点，current = current.next 是变量往前挪。反转不是把值倒着打印，而是重接 next 指针；而在覆盖一个 next 之前，得先把它后面的东西存下来：

next_node = current.next
current.next = prev

Linked List Cycle 从另一面说了同样的话。环意味着再次遇到同一个节点对象，而不是同一个值。链表里值可以随便重复，但节点是身份，整道题就靠尊重这点区别。

一堆特例底下的一条小规则

有些题穿着“特例”的戏服登场。

Roman to Integer 看着像一摞例外：IV、IX、XL、XC、CD、CM。你可以给每种减法形式单独起个名字处理，也可以看出它们底下坐着同一条局部规则：一个数字如果比它右边的小，就减，否则就加。Plus One 是同一个味道。偷懒的读法是“这不就是数字加一吗”，在 Python 里你确实能把整个数组转成整数来蒙混，但那绕开了真正的问题，也就是进位怎样在各位数字之间传递。从末尾往前走：这一位不是 9，就加一然后停下；是 9，就把它变成 0，让进位继续往前跑。一道有很多名字的题，底下往往只有一条安静的规则撑着。

树改变了我在回答哪个问题

二叉树这一串，是这一批里真正的转弯。

Invert Binary Tree 起手很简单，把每个节点的两个孩子交换一下；让它变容易的，是承认这个形状本身是递归的：一棵树无非是一个根加一棵左子树加一棵右子树。于是函数只管处理根，把子树再交回给它自己。Maximum Depth 让返回值把话说出了口，maxDepth(root) 给的是 root 底下那棵树的深度，这句话一清楚，函数体就只剩 1 + max(左深度, 右深度)。

Same Tree 和 Symmetric Tree 又往前推了一步，而有用的动作是在写任何逻辑之前先挑对参数。isSameTree(p, q) 比较两个当前节点，isMirror(left, right) 比较两个镜像位置。把函数的形状定对，递归调用几乎是自己写出来的。Subtree of Another Tree 接着就复用了 Same Tree：一个函数问“这两棵树是不是一模一样”，另一个函数在 root 上游走，逐个试候选起点。把这两件事分开，正是代码好读的原因。

我真正想留下的那一课

最清楚的一条弧线，穿过三道都要用到子树高度的题：Maximum Depth、Balanced Binary Tree、Diameter of Binary Tree。变的是高度用来干什么。

在 Maximum Depth 里，高度就是答案，到此为止。在 Balanced Binary Tree 里，光有高度不够，因为函数得一边算高度，一边在往上走的过程中察觉：某棵子树是不是已经不平衡了。用一个像 -1 这样的哨兵值，就能把这个“失败”一路带上去。这是我一个从没意识到自己在抱着的假设第一次裂开：以为递归函数返回的就是答案。它不必如此。它可以返回父调用需要的任何东西。

Diameter 把这点摆得明明白白。我的第一反应是去问：最长路径是穿过根，还是藏在某棵子树里？这会把你拖进左边分支和右边分支之间别扭的比较，还悄悄混淆了两样不同的东西：某处底下已经成形的最好路径，和一个节点能报给父亲的那条向下的高度。干净的问法是局部的。对每个节点，如果有一条路径的最高点正好在这里，它有多长？这个长度就是 左深度 + 右深度。于是函数照旧返回高度，而直径在我走过每个节点时，在旁边单独更新。

这句话值得写在墙上：

24 道题加起来是什么

回头看这一批，反复出现的那一课，从来不是“用哈希表”“用递归”或“用双指针”。而是在动笔之前，先把问题问得更利一点。

少问一点“我怎么找到答案”，多问一点“这一步我到底需要什么信息”。少问一点“这落在哪个 case 里”，多问一点“有没有一条局部规则能覆盖全部”。少问一点“代码该长什么样”，多问一点“这个变量、这个函数，到底该是什么意思”。

这就是我想让 Kata 一直练下去的部分。

完整项目：Kata