Becomin' Charles

又有许久不曾写过题解了，题目一直还在做着，就是懒得写题解，主要最近家里事有点让我烦心，心绪不宁无法安心写作。今天我猛然一看，统计数字 498 了，赶快找两道简单水题，凑个整，算是突破了 500 大关。当然，这对我个人来说，或者毫无意义，总是一个付出的明证吧。

LeetCode 刷题统计

从做题结构看，还是简单题偏多，你就可以想见，这个数字还是挺水的。含金量不像数字那么敦实。花了多久做了这么多题目呢？大概可以认为是 8 个月多吧。

LeetCode 打卡热力图

其实第一次尝试刷题是 2020 年 8 月开始，只在工作日，每天做 1 道，这样坚持了一个半月，放弃了，当时刷了 100 多道吧。今年的 2 月，又开始第 2 波了，上次使用 Go 刷的，这次是用 Python 刷的。两次都重开了做题计划，所以，第二次其实是把第一次的题都又做了一遍的。即这 500 题有 100 多道我是用 Go 做过一遍的。

如何看待刷题这个事情？

刷题大体来说还是快乐的，因为简单。这话不是凡尔赛，真实的个人体会。题目都是那么纯粹，有些题甚至是为了做题而出题，就更显得纯粹。你不懂的时候，可能会让你暴躁得抓头发，那只能是你的见识太少了。因为这些题并不难，只是没见过而已。

比起生活中遇到的那些无解的困难，比起工作上的这些困境。刷题相比之下只是一个纯粹而快乐的过程。刷题不能解决我的问题，但是可以让我从痛苦的生活中逃离一小会儿，用能获得的进步给自己一点点安慰。我想这和那些沉溺在游戏里打怪的人没有太多的区别，只是这个上瘾程度有限。

刷题有什么好处？

我加过各种群，自己也有个小群，都是大家一起刷题的。大部分人比我年轻 10 岁以上。对他们来说，刷题是很实在的，因为现在找工作，想去个好点的公司，都要考算法题的。刷题最大的好处是，让大家有所准备，能够胜任 Code Challenge，获得心仪的 offer，确实还是有效的。

于我而言，只是增加了我的些许自信。毕竟刷题不是面试的全部。对我来说，更大的好处是，增加了我日常工作中解决难题的信心。我们都知道，工作中可能没有算法题，不过工作中可能会有很多很麻烦的场景。那不是说问题多困难，就是十分麻烦，我感觉刷题训练让我更加耐烦。

会让你写麻烦烧脑，容易写错，难于调试的场景时候，更有信心一点，即使写不出来，也不会气恼，删掉重写就是，这种打击在刷题的过程中早已习惯了。

刷题有什么诀窍？

没有太好的。很多同学分享经验我都看了。有几个，我觉得挺认同。刷题呢，不要纠结于非要自己做出来，刚开始很多同学就会沉溺在这个误区里。看题解不丢人。其实这是非常重要的一点，很多人比如我，很晚才领悟这一点。

刷题呢，专项密集训练效果是不错的，就是把相近题，相同考点的题，堆在一起，一顿猛刷，这样效果好。一个主题完了，再去下一个主题。不是随机拉个单子刷，那样效果不好。举个不恰当的例子吧，比如你去健身房健身。你可能会看到眼花缭乱的器械。不过你请过教练，你就会发现，那么多器械，只是少量几个跟你有关。你每次去用的器械不会超过三种。这次去，深蹲，腿弯举，腿屈伸，倒登机。全部虐腿。下次去了，高位下拉，悍马机，引体，全是虐背。刷题也差不多，这个礼拜全是位运算，下个礼拜全是动态规划。

刷题呢，也会倦怠，需要休息。我第一轮刷题，什么都不懂的，就天天随机做，当时不懂回溯，就死磕了几天回溯，连续做了十几道，然后有点感觉了。第二轮刷题，隔了三四个月多吧，我发现但凡看到题目可能可以用回溯解的，我似乎都有点感觉，写个回溯也自然了许多。可见知识技巧，需要沉淀和发酵，有时候你需要的时间地积淀。一顿猛学后，休息几个月，捡起来，反倒觉得似乎脑袋更清楚了。

刷题呢，反复做相同的题目也是有效果的。比如，你看我做了 500 题，其实这里，很多题是做了不止一遍的，其中有一道题，我看到自己有 7 次正确的提交，都在不同的日期里。有不少同学分享经验，按照一些榜单去刷，比如 Hot 100 列表啊，Top 200 列表啊什么的。还有学习专区，有很多专项，动态规划，二分法，堆等等，专项里和列表里，重复其实很高的。但是你重复做也不用担心的，你再次遇到的时候，还真的未必会做的。我们掌握的知识可能没有自己想象的那么扎实。一些很基础的题目条件反射秒写对后，你才能在一些复杂的场景下，水到渠成写出来。再举个不恰当的例子就是，你盖房子的时候，砖块水泥沙子钢筋，最后房子塌了，你怎么确定砖块的问题，还是钢筋的问题，还是你房子结构设计的问题？谁的错？最后可能是沙子用得不够。所以反复做一些基础题，做到倒背入流随手就来，你就知道你的房子砖块水泥都没问题，就是结构不对。能帮你快速排除一些错误的猜测。

我现在什么水平？

很遗憾，我还是水平很低的，就好像上面说的，我刷题的结构里，太多简单题了。就是灌水成分大了点。我现在的水平就是简单题，大多数可以想出来，中等题，我大概 70% 把握，困难题，我大概 40% 把握，也即一多半做不出。

前天晚上周六，正好没有双周赛，我就开了个模拟周赛试试。最后 1 个半小时的时候，我做对了两道。又加了 5 分钟，终于第三道做出来了。第四道我都没读题目，时间耗完了。我历史上参加过 9 次周赛，6 次我做出来 2 道，2次只做出来 1 道，还有 1 次做出来 3 道，高兴坏了，那次也是我最后一次参加周赛。

未来

刷题是需要长期坚持的，跟健身又很像，你一顿操作猛如虎，一看效果二百五。还不如细水长流，常年坚持。可能不需要很卖力，就是时不时练练，可以保持健康。在市场不断内卷的当下，保持头脑健康是很重要的。

现在我的水平已经进入瓶颈，每天这么做着也没啥长进。朋友说，你需要画个脑图一个点一个点细细去补那些漏洞了（数据结构和基础算法的漏洞，故意忽略的那些知识点），另外以前不曾踏足的领域也要逐步尝试，拓宽面，这样才可能在竞赛里做出好成绩。总之，是进入了一个边际效益很低的区段了。后续怎么做，还是要看自己的目的，想通过刷题得到什么。

– END –

好久没有写做题日记了，今天这题目有点意思，我做得蛮开心的。

这里有 n 门不同的在线课程，按从 1 到 n 编号。给你一个数组 courses ，其中 courses[i] = [durationi, lastDayi] 表示第 i 门课将会 持续 上 durationi 天课，并且必须在不晚于 lastDayi 的时候完成。

你的学期从第 1 天开始。且不能同时修读两门及两门以上的课程。

返回你最多可以修读的课程数目。

630. 课程表III —> 传送门

这个题目意思看得挺绕的。举个生活中的例子来说明这个意思，就比如，你买了一张游戏点卡，一旦激活每天扣 1 点，一共 30 点，但是半年内必须用完。于是，你得到的 [durationi, lastDayi] 是什么呢？[30, 180]。

这里有个显而易见的事情，如果 durationi > lastDayi，那么就是一个不可能值，durationi 不能被消耗完。你买个 30 天的游戏点卡，但是 2 天内必须用完，所以就是你不可能用完。因为两天你只能用掉 2 点。所以，我们做题的时候，只要挑那些 durationi <= lastDayi 的数组就可以了。如果没有满足的数组，那么可以直接返回 0。

接下来就开始思考，怎么挑课了。其实，你要这么想，既然 durationi <= lastDayi 那就说明，每上一门课，都会剩余一些时间，才能到 lastDay，最少会剩余 0 天，一般都或多或少会剩一些。上得课越多，攒得日子越多，越不容易突破 lastDay。那么最简单的做法，就是把所有数组按照 lastDayi 的大小，排序即可。然后，我们用一个变量记录上过一门课后，消耗的日子，如果当前课程消耗的天数，加上消耗的总天数，没有超过 lastDayi，那么就可以修此门课。否则就不行。

可以想见，在lastDayi 相同的课程里，我们上 durationi 持续天数最短的课程，比较有利后面上更多课，于是我们可以把 lastDayi 相同的课程，按照 durationi 顺序排序。优先选择持续天数比较小的课。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution:
    def scheduleCourse(self, courses: List[List[int]]) -> int:
        def cmp(a: List[int], b: List[int]):
            if a[1] < b[1]:
                return -1
            if a[1] == b[1]:
                if a[0] < b[0]:
                    return -1
                elif a[0] > b[0]:
                    return 1
            return 0

        courses = sorted([c for c in courses if c[0] <= c[1]], key = functools.cmp_to_key(cmp))
        if not courses:
            return 0
        days = 0
        count = 0

        for c in courses:
            if days + c[0] <= c[1]:
                days += c[0]
                count += 1
        return count

这是我实现的算法，主体是一个排序。另外，过滤掉 durationi > lastDayi 的不可能数组。这个算法我提交后，97 个用例 过了 80 个。遇到这样一个用例：**[[5,5],[4,6],[2,6]]**，没能通过。

这里我们看到，第一个课，正好把日子用完了，用我的算法再往后，都不能选了。但是这里很凑巧的是，假如我们第一个课不选，正好选后两个课，反而可以多修一门课。

我就意识到了问题，我知道我肯定在一个正确的方向上。只是忽略了一个问题。对于这个没能通过的用例，我们来看看问题在哪里。其实，给出的三门课里，如果我们只选一门课，那么选哪门课更有利呢？显然选持续时间最短的课比较有优势。但是因为我们按照 lastDayi 排序，则我们一定会先遇到 [5,5] 这门课。假如我们已经选了 [5,5] 这门课，那么当我们遇到 [2,6] 这门课，那么如果我们选择把 [5,5] 这门课替换成 [2,6] 这么课，结果是一样的，还是只修一门课，但是后续看到 [4,6] 这门课时候，就会得到不同的答案了。

所以，这里，我们进行这样的优化，还按照刚才的算法，如果我们遇到一门新课，但是总消耗的时间已经超过了，但是新遇到的课比已经选的课消耗时间短，我们就把已经选的课里消耗时间最长的课替换成新遇到的课，这样我们消耗的总时间显然会下降，但是我们选的课的门数却没有变化。这个替换，会优化出更多的空余时间，有可能容纳更多的课程进来。如此，可能得到更优的结果。

我们可以用最大堆来实现这个功能，每次新遇到一门课，如果可以选课，我们就选，如果不能选，就把已经选中的课里，消耗时间最长的课替换成消耗时间更短的课，这样可以在不减少选课数量的同时，空出更多时间来选新课。这样就能得到最终可选的最大课程数。实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

class Solution:
    def scheduleCourse(self, courses: List[List[int]]) -> int:
        def cmp(a: List[int], b: List[int]):
            if a[1] < b[1]:
                return -1
            if a[1] == b[1]:
                if a[0] < b[0]:
                    return -1
                elif a[0] > b[0]:
                    return 1
            return 0

        courses = sorted([c for c in courses if c[0] <= c[1]], key = functools.cmp_to_key(cmp))
        if not courses:
            return 0
        days = 0
        count = 0
        q = []

        for c in courses:
            if days + c[0] <= c[1]:
                days += c[0]
                count += 1
                heapq.heappush(q, -c[0])
            elif q and -q[0] > c[0]:
                days += q[0] + c[0]
                heapq.heappop(q)
                heapq.heappush(q, -c[0])
        return count

以上是我实现的代码，因为 Python 只有最小堆，所以要加个负号不要忘记。

–END–

做算法题，不紧张是不可能的 —— Charles

给你一个字符串 s 和一个字符串列表 wordDict 作为字典，判定 s 是否可以由空格拆分为一个或多个在字典中出现的单词。

说明：拆分时可以重复使用字典中的单词。

示例 1：
输入: s = “leetcode”, wordDict = [“leet”, “code”]
输出: true
解释: 返回 true 因为 “leetcode” 可以被拆分成 “leet code”。

提示：
1 <= s.length <= 300
1 <= wordDict.length <= 1000
1 <= wordDict[i].length <= 20
s 和 wordDict[i] 仅有小写英文字母组成
wordDict 中的所有字符串 互不相同

139. 单词拆分 —— 传送门

题目如上，我没有都贴出来，省略了两个例子，太长了，凑合看吧。意思就是给你一个字符串集合，看看能不能刚好用集合中的词拼出给定的字符串。

解这道题目，我的想法还是先穷举，无论任何题目，其实都是穷举法，你首先要想出至少一种的穷举办法。当然你想出来的未必是最终用的方法，但是你至少想出一种。有了一个正确的穷举，你才可以谈论如何在上面优化。

这个题目让人迷惑在什么地方，我们可以用一个单词来分割这个字符串，例如，我们用 a 将 bab 这个串分割为两个 b，如果 b 在给定的字典里，那么就是可以拆分。但是因为目标串里的字母可以重复，所以，word 出现的边界不好确定，如果选错了边界，就会导致两侧不能继续被拆分。

这里其实有个问题，就是我们为什么会想到从中间拆分这个串呢？因为我们是按顺序遍历字典的。所以，字典里的第一个串，不一定出现在目标串的哪个位置。更一般的，我们会想到是从中间的某个地方去分割这个串。其实这是一个误区，因为从中间将串分为两截，前后两截也并不好处理，而且中间的位置，这个中间也是模糊的。

简化的想法其实是控制一头，我们总是去掉一个前缀，或者去掉一个后缀，如果剩下和还能用原来的字典拆分，则整个串可以被拆分。如果选错了前后缀，我们就换一个。这么一来，这就成了一个显然的递归算法。我们把目标串能否拆分，替换了目标串的前后缀能否拆分这样一个子问题。

1
2
3
4
5
6
7
8
9
10
11

def wordBreak(self, s: str, wordDict: List[str]) -> bool:
    n = len(s)
    def dfs(st: int):
        if st == n: return True
        
        for w in wordDict:
            if s.startswith(w, st):
                res = dfs(st + len(w))
                if res: return True
        return False
    return dfs(0)

设计一个递归算法的方法，其实就是假设我们已经设计出了这个算法。

假设，我们得到了一个算法，这个算法可以判定目标串从 st 开始的后缀能不能被字典拆分。显然，从 len(s) 也就是目标串的长度开始的后缀，长度是 0 ，一定是可以被拆分的。剩下，我们只要遍历字典，去掉一个以字典中的词前缀后，用递归方法判定后缀就可以了。

如果是高手很容易看出来，我当时设计算法的时候，不是用上述的想法，上述的想法是我后来编的。当然，能直接这么想出来，也没什么不自然。我设计算法的时候，是用另一个方法，就是回溯法，而回溯法和 dfs 又往往是千丝万缕，当然不完全是一回事，不过写多了就喜欢这么命名了。

从回溯法出发的思路也可以解释一下，就是从目标串的 st 下标开始搜索，如果可以成功扩展一个前缀，就深入一层，从 st + len(word) 这个下标开始，用相同的方法继续向前探索，如果探索失败就回退到 st，如果探索成功就直接返回。听起来是不是也有点像深度优先搜索呢？所以我总喜欢用 dfs 来命名回溯的方法名。

结合题目的规模提示，我们可以分析一下这个算法的时间复杂度，递归的每一层，分支数量是字典的长度 m，单词的长度是 n，时间复杂度是 O(m^n)，不超过 1000^300也就是 10^900。这是一个天文数字。当然，因为字典里每个词都是不同的，所以实际拆分没那么恐怖，但是你不用侥幸，肯定在那个量级。

考虑到我们设计的这个算法很很巧妙，只有一个标量参数，也就是开始下标。而且，显然这个 st 是会被重复访问到的。比如 babccc 这个目标串，测试字典是 [a, b, ba, ab, c]，其前缀 bab，对应字典前几个词，可以有多种方法，所以，显然 ccc 这个后缀会反复被搜索到，所以如果我们缓存了后，就会大量节省搜索时间。我可以用 st 作 key，缓存计算结果。

1
2
3
4
5
6
7
8
9
10
11
12
13

def wordBreak(self, s: str, wordDict: List[str]) -> bool:
    n = len(s)

    @cache   #注意这里
    def dfs(st: int):
        if st == n: return True
        
        for w in wordDict:
            if s.startswith(w, st):
                res = dfs(st + len(w))
                if res: return True
        return False
    return dfs(0)

Python 就是这么变态，只要在方法名前面加个修饰 @cache 就可以了，这个方法的值会自动调用 lru_cache。如此，就不会超时了（TLE）。加过缓存后，这个算法的时间复杂度就会大幅下降，目标串的每个 st 下标位置会缓存一个结果。然后就是对字典的遍历。

这道题目还可以用动态规划来解。因为我们发现，这个题目满足重叠子问题，最优子结构，无后效性三个条件。重叠子问题是，每个前缀后缀会被反复判定。最优子结构是，我们只需要回答能否被拆分，而不需要回答拆分的方法是什么。无后效性是，一个前后缀的拆分，跟已经切割掉的前后缀无关。

转移方程是这样的：f(n) = f(n - len(w)) && “w 是一个合法前后缀”

如果一个单词 w 是这个串的合法前后缀，那么去掉这个单词前后缀后，剩下的长度还是可以拆分，则说明整个串可以拆分，回到原初，一个空串显然是可以拆分的。基于上述分析，得到算法如下：

1
2
3
4
5
6
7
8
9
10
11
12

def wordBreak(self, s: str, wordDict: List[str]) -> bool:
    n = len(s)

    dp = [False] * (n + 1)
    dp[0] = True

    for i in range(1, n + 1):
        for w in wordDict:
            if dp[i] : break
            if i - len(w) >= 0:
                dp[i] = dp[i - len(w)] and s.endswith(w, 0, i)
    return dp[n]

这个算法的时间复杂度是O(mn)，m是字典长度，n 是目标串长度。空间复杂度是 O(n)。

— END —

这也是在一次字节的面试中遇到的题目，暂时也没有在 LC 找到题目的原型。题目是这样描述的：

给定一个二维矩阵，用于描述一处山地的地形，每个元素 a(i, j) 代表该座标位置的海拔高度，设想，现在下了一场足够大的雨后，将所有低洼处都填上水，请判断座标 (x,y) 的最高高度能否达到 h？（最高高度既可以是陆地，也可以是水面）举个例子：

给定地形为：

1
2
3
4

3, 3, 3, 3
3, 1, 2, 3
3, 3, 3, 3
3, 3, 3, 3

在这个地形里，坐标（1，1）的高度是 1，坐标（1，2）的高度是 2，其余位置高度都是 3，我们假设矩阵外部全是深渊，现在低洼就是（1，1）和（1，2）两个格子。很显然，灌水后，会被填平，所有的坐标高度都将达到 3。（被水填平了）

decideHeight( x=1, y=1, h=3) 返回 True，坐标（1，1）位置能否达到高度 3？答案是 True。

decideHeight(x=1, y=2, h=4) 返回 False，坐标（1，2）位置能否达到高度 4？答案是 False。

其实，我在 LC 做过一个一维的接雨水的题目，给定的是一个截面图，然后用两侧的柱子高度来盛水，计算总共能接多少水。但是这个题目不一样，这个是判定水面的高度。受到一维题目的影响，我一直在往那个方向思考，无非就是把一维改为二维，先判断一个方向的盛水情况，再判定另一个方向。

但是我怎么也想不明白怎么做。后来面试官提示我第一点，我没必要计算出实际盛水的数量，做判断和计算具体值，是不一样的。其实这是非常重要的一个提示。因为只是做判定的话，就比具体算出来是多少要简单一点。

只考虑一个方向，两侧如果有高于给定高度的遮挡，则可以认为能够接水，否则就是不行。扩展到二维后，一个坐标点，需要四个方向来遮挡，才能盛水。所以给定一个坐标后，我们判定其四个方向，如果都高于给定坐标，则认为能接水。如果，并不高于给定坐标，那么是不是一定不行呢？未必，因为如果更远处有足够高的遮挡，也可以实现盛水。所以我们要将当前判断记为暂定，然后向远处延伸出去判定，直到找到封闭的遮挡或者触达边界。

于是，我写出了这样的算法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

def rainDrop(m: List[List[int]], a: int, b: int, h: int) -> bool:
    row = len(m)
    col = len(m[0])

    visited = [[0] * col for i in range(row)]

    def _rainDrop(x: int, y: int) -> bool:
        visited[x][y] = 1
        if m[x][y] >= h: return True

        if x - 1 < 0: return False
        if x + 1 >= row: return False
        if y - 1 < 0: return False
        if y + 1 >= col: return False

        res = True
        if visited[x-1][y] == 0:
            res = res and _rainDrop(x - 1, y)
        if visited[x+1][y] == 0:
            res = res and _rainDrop(x + 1, y)
        if visited[x][y-1] == 0:
            res = res and _rainDrop(x, y - 1)
        if visited[x][y+1] == 0:
            res = res and _rainDrop(x, y + 1)

        return res
    return _rainDrop(a,b)

这个实现里，我用了一个递归算法，如果当前坐标的高度本身已经高于需要判定的高度，直接返回 True，否则就向四个方向延伸去判定是否能够遮挡。不过呢？为了避免重复，需要一个位图来记住已经访问过的坐标。这个算法，很显然，时空复杂度是 O(m×n)，因为最坏情况会遍历每个格子一次，需要格子同等数量的位图来记录访问历史。

其实在面试当场，我是没能写对的，我没有能防止重复遍历，回来写出来运行后，发现我当时写的版本会死循环。遗憾。

等我写对后，我发现，这题目本质上是一个无向图的广度优先遍历，和一维接雨水毫无关系的一个算法类别。还真是，类似的表述会是完全不同的算法。所以还是要深入去掌握题目的条件和问题来思考算法，不能凭记忆和感觉解题。

给定一个经过编码的字符串，返回它解码后的字符串。

编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。

你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。

此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。

示例 1：
输入：s = “3[a]2[bc]”
输出：”aaabcbc”

示例 2：
输入：s = “3[a2[c]]”
输出：”accaccacc”

示例 3：
输入：s = “2[abc]3[cd]ef”
输出：”abcabccdcdcdef”

示例 4：
输入：s = “abc3[cd]xyz”
输出：”abccdcdcdxyz”

394. 字符串解码 –> 传送门

今天做到这么一道题目，这个题目我一看，就想起了大学时候学习的编译原理，这个字符串解码，显然是“一个语言”，只不过这个语言的语法特别简单，只有字母，中括号和数字。我们要实现的就是，做一个这个“语言”的解释器，然后打印语句的结果。

既然是语言，我们就按照语言的方式来解决。这个语言里，只有四种 TOKEN（这是个专有术语），数字，左中括号，右中括号，字母，很容易划分 TOKEN，因为每种 TOKEN 的边界都是不同的字符。

语法非常简单，就是数字用于修饰一个字母串，中括号用于分割被修饰的字母串。只有唯一的操作，就是“打印”，有两种状态，“直接打印”，“重复打印”。于是我画了一个状态机：

状态机

在初始状态下，遇到字母就直接打印，遇到数字，马上进入重复打印的流程，遇到右括号的时候，开始将遇到的模式重复打印。并退出重复打印的流程。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

def decodeString(self, s: str) -> str:
    res = ''
    count = 0
    p = ''
    state = 'print'
    for c in s:
        if state == 'print' and ord('a') <= ord(c) <= ord('z'):
            res += c
        elif ord('1') <= ord(c) <= ord('9'):
            count = count * 10 + int(c)
        elif c == '[':
            state = 'start'
        elif c == ']':
            res += p * count
            count, p = 0, ''                
            state = 'print'
        elif state == 'start' and ord('a') <= ord(c) <= ord('z'):
            p += c
    return res

写出来一测，我才发现，原来括号是可以嵌套的。上面的代码对于嵌套的括号是没法正确处理的。并且通过编写这个代码，发现我识别的两个状态似乎也有点错误，这个语言太简单了，状态的切换也有点多于。

我发现，整个“语言”其实是一个递归的结构，可以表达成 “字母串 = 字母串 + 字母串 × 重复次数”，中括号其实就是字母串的分割边界。每遇到一个左括号，字母串的处理就深入一层，遇到一个右括号就跳出一层，只要用一个栈就可以轻松解决了。栈里要记录的东西，其实就是外层的前面一半字母串，以及内层需要重复的次数。这样，代码就改成了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

def decodeString(self, s: str) -> str:
    res = ''
    count = 0
    stack = []
    for c in s:
        if ord('a') <= ord(c) <= ord('z'):
            res += c
        elif ord('0') <= ord(c) <= ord('9'):
            count = count * 10 + int(c)
        elif c == '[':
            stack.append((res, count))
            res, count = '', 0
        elif c == ']':
            ctx_res, ctx_count = stack.pop()
            res = ctx_res + res * ctx_count
    return res

反倒更简洁了，我们需要求的是最外层的字母串，遇到左括号就压栈，遇到右括号，出栈的同时，做重复计算。栈里保留了当前字母串需要重复的次数。

这个算法的时间复杂度是O(n)，空间复杂度也是O(n)。当然，到这里，想要写出这个算法的递归算法也是非常简单：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

def decodeString(self, s: str) -> str:
    def process() -> str:
        nonlocal i
        res = ''
        count = 0
        while i < len(s):
            c = s[i]
            i += 1
            if ord('a') <= ord(c) <= ord('z'):
                res += c
            elif ord('0') <= ord(c) <= ord('9'):
                count = count * 10 + int(c)
            elif c == '[':
                res += process() * count
                count = 0
            elif c == ']':
                return res
        return res
    i = 0
    return process()

– END –

题目的内容是，给定一个 m×n 的矩阵，搜索一个目标值 target，返回 bool 值。这个矩阵的特点是：

• 每一行的元素从左到右升序排列
• 每一列的元素从上到下升序排列

传送门

一开始我以为，这个题目太简单了，这个不是直接写就好了嘛，我只要遍历就好了啊，如果当前元素小于 target，就遍历右侧元素，如果遇到大于 target 的元素，就向下遍历，如果还是大于 target 就向左遍历，总是会找到的。

不过这个自然而然的想法，却是不对的。我写了三遍也没写对自己的这个想法。感觉自己太蠢了。然后我看了看题解，才发现竟然如此简单，可是我竟然连最简单的解法也没做出来。自己想了一个莫名其妙的遍历算法，既不是最简单的解法，也不是最巧妙的解法。

我想，可能是做了一定数量的题目后，我就失去了初心，总觉得自己有点积累了，可以一下找到最高效最简单的解了。

如果，我们抛弃一切技巧，按部就班暴力解题，怎么解呢？当然是从左到右，从上到下，逐一遍历，直到遍历完毕或者找到目标。这才是正确的遍历方法。也是最自然而然，基本没学过算法的人应该能想到的算法，也显然是一个正确的算法。

• m == matrix.length
• n == matrix[i].length
• 1 <= n, m <= 300
• -109 <= matrix[i][j] <= 109
• 每行的所有元素从左到右升序排列
• 每列的所有元素从上到下升序排列
• -109 <= target <= 109

从题目的约束来看，这种暴力扫描法，复杂度 O(mn)，最大也才 9 万的规模。可是我花了 2 个小时，也没想到这么去做。其实，解算法题，你的初心是把题目做对，做对后，再来讨论效率优化。想到了乔帮主的 stay foolish，才有点明白，为啥这时候就不能 stay foolish 呢？

如果，我们要提高算法的效率怎么做呢？题目的一个条件是，有序，搜索有序，自然而然就要想到二分查找，所以，我们在每个横行里，进行二分查找，那么在单行遍历，时间复杂度会降到 O(logn)，总复杂度降到 O(mlogn)，在大多数简单算法题给定的规模里，这个复杂度都足够应付了。

最后，如果我们还想优化，还有办法么？最后这个办法，可能是唯一不是普通人，随便就能想到的办法，如果一下点醒你，你会秒懂，但是没戳破就觉得真的想不到。我自己也没想明白。我怎么也想不到，如何才能按部就班想出这样的解题法。

其实有个数学家说过。如果你解不出一道题目，一定是你还没有充份利用好已知条件。好像认真看已知条件就一定能找到破解之法，但是没那么简单。比如这道题目，我们想出二分法，就是利用了有序，这个条件。但是，显然这题目给出了两个有序。从左到右，从上到下都是有序的。

二维矩阵的例子

同时利用两个有序的方法，显然也是一个解法，就是没那么容易想到。而且，这是一个二维的矩阵。这个方法就是，我们遍历的时候，不一定从左上角开始遍历。而是从左下角或者右上角开始遍历。

程序员的思维定势是从左上角开始，当然也有一部分倒序的，那也会选择右下。但是能想到另外两个角，是要有怎样的经验和知识才能让你想到呢？这是我唯一的疑问。

以左下角为例，当你从左下角出发的时候，你发现，你上面的数字都比当前数字小，你右侧的数字都比当前大。右上角同理，其实左下角和右上角的数字，相当于所有数字的中间位置。

当前位置太小，就往右，太大就往上，循环往复，就会找到目标，或者结束遍历：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
    m = len(matrix)
    if m == 0: return False
    n = len(matrix[0])
    if n == 0: return False

    x, y = m - 1, 0
    while matrix[x][y] != target:
        if matrix[x][y] > target:
            if x - 1 >= 0:
                x -= 1
            else:
                return False
        else:
            if y + 1 < n:
                y += 1
            else:
                return False
    return True

这个算法的时间复杂度是O(m+n)，是已经分析过的算法里，复杂度最低的算法了。这题目说透了，就觉得太简单了。但是难点在于你就是想不到这里来。这题目给我一个最大的提醒，就是做题不要好高骛远，而是总要先想一个笨办法立于不败之地，再思考怎么优化，才是比较妥帖的做题态度。

昨天看到这道题目，我有点头皮发麻，主要是想到了字符串的处理，不过，我想到，既然要写算法，怕麻烦的心态不能有，算法题再麻烦，能有业务麻烦？

对一个二叉树进行序列化，其实就是把一个非线性的数据结构，转化成线性的数据结构。比如，我们按照某种顺序去遍历二叉树，就会把二叉树转换成一个序列，就相当于序列化了。我们可以使用：

1. 前序遍历
2. 中序遍历
3. 后序遍历

反序列化是什么呢？就是从一个给定的序列，恢复出原来的树。这个过程毛想想可能有点麻烦，不过真写出来，其实又不那么麻烦了。

先来说序列化的部分。我们选择前序遍历作为序列化的方法：

1
2
3
4
5
6
7
8
9
10
11

def serialize(self, root):
    res = []
    def _serialize(tree):
        if not tree:
            res.append('None')
        else:
            res.append(str(tree.val))
            _serialize(tree.left)
            _serialize(tree.right)
    _serialize(root)
    return ','.join(res)

我使用了一个内部函数，用一个变量 res 来存储结果数组，然后内部函数是一个递归前序遍历算法。这里注意的主要就是根节点被表示成了 None，也可以是别的，等会儿反正反序列化的时候，你照着反解就行了，这其实就是所谓的“协议”了。

二叉树的例子

对于图例里的二叉树，我们前序遍历后，得到的是什么呢？

1

1, 2, None, None, 3, 4, None, None, 5, None, None

接下来说反序列化，可能，这是大家可能会觉得难的部分，因为每次看到二叉树这个主题，研究怎么遍历这个树的次数，要远远多于研究怎么构建这个树的次数，所以，当我们想从一个字符串构建这个树的时候，就会感觉陌生，从而提高了难度。

我也是实际写了一下，才发现，好像写出来以后，也并不是很复杂。我写了一个递归方法，方法的功能是：把输入的序列当成一个前序遍历结果，然后返回恢复后的树的根。递归方法的构造过程很有意思，就是我们总是先假设我们已经写出了这个函数，再去写这个函数。有点像哆啦A梦穿越时空的糊涂账。这也就是递归有趣的地方。

二叉树为什么这么有意思？因为二叉树也是个典型的递归结构。一棵二叉树和这棵树的左右子树，在性质上是完全一样的东西，只是差了一层而已。

当我们恢复一个前序序列为树的时候，我们知道，第一个元素是根节点，然后，后面就是左子树，然后再后面是右子树，恢复左子树的时候，就可以递归使用自己来完成了，所以根本不用头疼后面怎么办，也不用头疼左右子树的分界点在哪里这种问题了，毕竟“我们已经写出了这个函数”，对不对？哈哈

1
2
3
4
5
6
7
8
9
10
11
12
13
14

def deserialize(self, data):
    l = data.split(',') # 字符串切割成列表
    i = 0               # 遍历列表的下标指针
    def _deserialize():
        nonlocal i # 解决 Python 的闭包问题
        if l[i] == 'None':
            i += 1
            return None
        root = TreeNode(int(l[i]))  # 第一个遇到的元素是根节点
        i += 1                      # 元素用掉后，下标后移
        root.left = _deserialize()  # 递归构造左子树
        root.right = _deserialize() # 递归构造右子树
        return root
    return _deserialize()

写完后，才发现，很意外，这个反序列化的方法，几乎和序列化一毛一样，也是一个前序遍历的递归过程。

好，到这里，序列化和反序列化就都写完了。还蛮有趣的。

• End -

今天，我参加了一场面试，一面竟然全是考算法。真是崩溃。

如题，就是我遇到的第一题，直接给我难住了。题目意思如下：

给定一个整数数组，设计一个方法，返回数组中最大值的下标。如果，最大值有重复出现，则按照相等的概率返回任意一个最大值的下标。附加条件：设计一个时间复杂度 O(n)，空间复杂度 O(1) 的算法。

这道题我在 LC 没找到，在 SO 倒是搜到了。—> 传送门

这个题目非常的抽象，我们来举两个例子，比如，给定一个数组是 [1,2,3,3,3]，这个数组的最大值是 3，其下标是 2，3 和 4，那么，你的方法要返回 2，3，4 中的一个，出现概率是三分之一。

再举一个例子，输入数组是[1,2,3,4,5]，最大值是 5，其下标是 4，因为只出现了一次，那么你的方法，每次返回值都是 4，也即 100% 概率返回 4。

反复思考了几遍，我才理解了这题目的意思。我的第一个思路很简单，就是用一个数组，记录下最大值的所有下标，然后用一个随机数取整，然后挑一个下标返回。

代码大概可以这样写：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

def findMaxIndex(arr: List[int])->int:
    maxVal = arr[0]
    indices = [0]
    
    if len(arr) == 1: return 0
    
    for i in range(1, len(arr)):
        if arr[i] == maxVal:
            indices.append(i)
        elif arr[i] > maxVal:
            maxVal = arr[i]    
            indices = [i]
    # choice 是一个库函数，作用是随机挑一个元素返回
    return random.choice(indices)

当然，面试的时候我只是口述了这个思路，根本就没写，因为这个算法明显不满足要求。最大值出现的频次是不确定的，也可能直接就出现 n 次。所以，存储最大值的下标的数组，明显破坏了空间复杂度约束。（上面的代码是我回家后，反思的时候写的，大家看最后一行，用了一个叫 choice 的方法，从一个数组里，随机返回一个元素，其实正是等概率返回其中一个元素的意思。当我们可以生成一个 [0,1] 的随机数的时候，怎样才能实现一个 choice 方法呢？毛想想好像很容易，真想写的时候，才发现我并不会写这个方法，而且，很奇妙的时候，如果我会写这个 choice 方法，那么做出这个题目也就没什么难的了，大家可以想想，如果题目换成实现一个 Python random 包的 choice 方法，你会怎么实现？）

因为我是第一次看到这个题目，又是在面试的场景下，我真的大脑一片空白，虽然我已经很努力压榨我的大脑了，仍然是一片空白。只好厚颜无耻地要求面试官给出提示。面试不是竞赛，可以厚颜无耻。

如果读者朋友你也没有见过这个题目，你可以现在假设一下，面试官怎样提示你，你才能想到正确的写法？反正我现在仍然是懵，我如果是面试官，我都不知道怎么去提示候选人，如果她/他真的没概念的话。

我的面试官是这么说的，你先考虑一个最简单的情况，[1,2,3]，这个数组，你会返回 2（唯一最大值 3 的下标），这时候，又多了一个数字 3，变成了 [1,2,3,3]，这个时候你会怎么办？

妈呀！这也叫提示啊？我听完了，完全是十脸懵逼好不好。不过，懵逼也不能慌，要装白小纯，单就这个情况来看，不考虑以后，现在只有两个 3，我应该按照 50% 的概率去挑选 2 和 3 两个下标，没错吧。所以，我可以生成个随机数，如果小于 0.5 我就返回 2，大于 0.5 我就返回 3。很朴实嘛。

后面就不知道了。继续厚颜无耻。面试官说，还是这个例子，这时候，又来了一个 3，变成 [1,2,3,3,3]，这时候你怎么办？我还能怎么办，我还绕在第一个思路里出不来呢，因为我刚才已经返回了 2，或者 3，现在又来了一个怎么办呢？我想，他这么提示，莫不是让我用递归思想？不不不，我肯定递归不出来。假设我刚才选定了 2，现在怎么办？假设我刚才选了 3，现在又怎么办？我只选了一个，另一个被我放弃了啊，又多了一个怎么办呢？

等等，等等，我刚才已经按照 50% 的概率选中了 2 或者 3，也就是，我上一次选定的数字，既可能是 2，也可能是 3，虽然我选定了一个，但是给另一个的机会也是均等的啊，就完全没必要记住另一个是几了啊！！！到这里我已经开窍了，终于被提示出来了！太不容易了。

唯一的难点来了，现在又多了一个 3，其下标是 4，直觉上，我觉得，只要把刚才 50% 的概率给降下来，降到 33%，然后把 4 这个下标混进去，就可以了。所以，应该用 66.6% 的概率选择上一次的选择，按照 33.3% 的概率选择 4，是不是就可以了？

其实，现在我已经知道这就是正确答案了，终于两次厚颜无耻地要求提示下，我想出来了。当然，现场我是非常不确定的，也没什么自信，毕竟太烧脑了，我状态也不轻松。好在面试官没有为难我，说这是对的，用数学归纳法不难证明。你把这思路写出来写成代码吧……

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

def findMaxIndex(arr: List[int]) -> int:
    maxVal = arr[0]
    selected = 0
    count = 1

    if len(arr) == 1: return 0
    
    for i in range(1, len(arr)):
        if arr[i] == maxVal:
            # 下面这行很重要，注意！
            if random.random() <= 1 / (count + 1):
                selected = i
            count += 1
        elif arr[i] > maxVal:
            selected = i
            count = 1
            
    return selected

其实我还是懵的。就硬着头皮开始写，写得多难看我就不提了。不过好歹写出来了。其中生成随机数，并且控制概率输出的部分，我大脑一片空白，胡乱写了个语法完全不对的，号称伪代码的东西，就蒙混了，面试官说，能说清楚意思就行了。

注意看第 11 行，假设我们已经遇到了 n 个数字，并且我们按照 1/n 的概率，选中了一个下标 a 的时候，这时候，又来了一个数字，第 n + 1 个，其下标是 b，那么，这时候我们到底是返回 a 还是返回 b 呢？注意，我们最终返回的下标，其出现的概率是 1/(n+1)，我们已经知道 a 出现的概率是 1/n，这时候怎么处理 b 呢？

我们应该按照 1/(n+1) 的概率返回 b，并且按照 n/(n+1) 的概率返回 a。这样，返回 a 的概率是 1/n × n/(n+1) 正好等于 1/(n+1)，这样就可以满足题目的要求了。简直完美。这个算法，也叫蓄水池采样（Reservoir sampling）算法。非常巧妙，用一个迭代的算法，完成了等概率的分配。

这时候，35 分钟过去了，面试官说，还剩 10 分钟，要不再来一道吧……我靠！！我内心是崩溃的，因为刚逃脱一个危险，又来，实在是压力倍增。幸亏第二题遇到了我做过的题目，著名的打家劫舍。可是我两个多月没刷题了啊，就算一直在刷也不能总是在刷动态规划吧。还好他说时间不够，就讲解思路，简直如蒙大赦。这个打家劫舍也不是最平凡的那个，而是环形打家劫舍，虽然我曾经做过，但是当时真的吃得不透，这时候，只好信口胡诌，好在原理是没差别的，就在于怎么处理环形。被我蒙混过去了。我暗忖，真要写，怕是没那么容易写对的。

虽然我不知道结果如何，但是面试结束后，我还是有点小成就感的，竟然还是答出来了，今年刷了三个多月的题目，真的没白刷。可见还是熟能生巧的一个过程。虽然我又闲散了两个月，已经又生疏了，但是和以前真的不同了。这次面试无论成败我想我都可以泰然面对了。并且涌起了新的刷题的动力。还是要持之以恒啊。

这个题目意思比较简单，就是求一个数组中，有多少个和为 k 的子数组。输入数组的规模，最少一个元素，最多 20000 个元素。

例如：[1,2,3] k=3，返回 2，因为和为 3 的子数组有两个 [1,2] 和 [3]。所谓子数组，有两个特点，一是连续，另一个是有序。

解这道题目的最直观的办法是遍历。因为一个子数组，比如有一个开始的下标，一个结束的下标，且 0 <= start < n，0 <= end < n，且 start <= end，只要分别遍历就可以了，遍历了 start 和 end，还要求和，如果处理不好的话，会写出 O(n^3) 的算法，因为对 start 到 end 中间的数字求和复杂度也是 O(n) 的。其实，我们可以用一个变量记住 [i, j] 的和，[i, j + 1] 的和就是 [i, j] + nums[j+1]，这样整个算法就可以降到 O(n^2) 的复杂度。

还有一个办法，也可以避免求和的计算，就是使用前缀和。设 prefix[i] = sum(0, i)，prefix[j] = sum(0, j)，则 sum(i, j) = prefix[j] - prefix[i]，这样，只要事先准备好 prefix 数组，求 sum(i, j) 的时候，O(1) 就可以得到。

不过，看题目的规模达到 2 万，则 O(n^2) 最坏有 4 亿次计算，也一定会超时了。

怎么优化呢？我们要求的是 prefix[j] - prefix[i] = k，其中 i < j，我们不难发现，如果 prefix[i] = prefix[j] - k，则，prefix[j] - (prefix[j] - k) = k，所以，当我们在求前缀和的时候，看看已经出现的前缀和，等于 prefix[j] - k 的值有几个，就可以知道满足题目要求的子数组数量。

由此写出算法：

1
2
3
4
5
6
7
8
9
10

def subarraySum(self, nums: List[int], k: int) -> int:
    counter = Counter([0])
    res, prefix, n = 0, 0, len(nums)

    for i in range(n):
        prefix += nums[i]
        res += counter[prefix - k]
        counter[prefix] += 1

    return res

这个算法的时间和空间复杂度都是 O(n)。可以比较有效的求出答案。

今天的打卡题目，中等难度，我拼搏了 2，3 个小时吧，终于做出来了。

给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。

返回被除数 dividend 除以除数 divisor 得到的商。

整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2

29. 两数相除

其实，CPU 只能做逻辑运算，加减乘除都是模拟出来的，在高级语言里封装成算术运算的运算符或函数，供我们使用。这个题目要求不能用乘法，除法，取模，剩下能用的只有位运算，逻辑比较，加减法等。

从最平凡的情况开始，从被除数 dividend 中减去若干个除数 divisor，直到不够减，就能求出商。依据这个原理，我们来写一个最简单的代码。

1
2
3
4
5

res = 0
while dividend >= divisor:
    dividend -= divisor
    res += 1
return res if not neg else -res # neg 是符号判定，省略了计算 neg 的代码

如果不考虑数字的取值范围，这就是正确的解法。题目中提到，被除数最大值可以达到 2^31，如果单纯用减法，可能计算 20 多亿次，必然超时。

所以，必然要用到移位操作，假设 dividend ÷ divisor = quotient，那么本质上要寻找一个整数 Q，使得 Q × divisor ≤ dividend ＜ (Q + 1) × divisor，通过这个数量关系，我就把除法转换成了乘法。

怎么寻找 Q 呢？因为 Q 也是单调的，所以，显然可以使用二分查找法。到这里，基本就剩下编码了。

首先我们要求 Q × divisor 的值，怎么用加法模拟乘法呢？这其实是一个算法，叫快速乘法，不过我也背不出来，就从 0 推导一下好了。其实就是 Q 个 divisor 加起来，跟上面那个迭代的减法差不多，就是时间复杂度太高。要用到移位运算，可以先把 Q 表达成 2 进制。

正整数怎么转二进制，我想大家都应该会。所以，两者的积，可以写成：

就得到了乘法的迭代算法。

1
2
3
4
5
6
7
8

def quickAdd(q: int) -> int:
    res, add = 0, divisor
    while q > 0:
        if q & 1 == 1:
            res += add
        add += add
        q >>= 1
    return res

这段算法认真阅读不难理解，怎么来记住这个算法呢？参考上面的公式，我们从二进制最低位开始，如果这个位是 1，那么就累加一个乘数，是 0，则不用处理，然后右移，要处理第二位，第二位上的 1，代表的是两倍的乘数，所以 add 翻倍一次 add += add，依此类推。

抛开符号问题不看，商的取值范围是 0 到最大值 ，于是我们在这区间二分查找即可。注意我们要找到使乘积小于等于 dividend 的 Q值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution:
    def divide(self, dividend: int, divisor: int) -> int:
        neg = dividend < 0 or divisor < 0
        neg = neg and not (dividend < 0 and divisor < 0)
        dividend = dividend if dividend >= 0 else - dividend
        divisor = divisor if divisor >= 0 else - divisor

        def quickAdd(q: int) -> int:
            res, add = 0, divisor
            while q > 0:
                if q & 1 == 1:
                    res += add
                add += add
                q >>= 1
            return res

        left, right = 0, 1 << 31
        maxInt = right - 1
        while left <= right:
            mid = (left + right) >> 1
            if quickAdd(mid) > dividend: # 注意：最终右边界会停在 <= dividend 的地方
                right = mid - 1          #      我们的答案正是右边界
            else:
                left = mid + 1
        res = -right if neg else right
        return res if res < maxInt else maxInt

整体代码如上。这里要注意二分查找的写法，这个二分查找并不容易写，我自己是纠缠了好一会儿才写对的。而且，二分查找的各种写法也很容易忘记，一段时间不写，就会写错。没有好建议，就是每次都认真理解，总有一天能记住吧。