Becomin' Charles

这也是在一次字节的面试中遇到的题目，暂时也没有在 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

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

本原文发布于 2021-09-06

在有些场景下，App 为了防止用户误触返回按钮或者误触返回键，导致未保存的结果返回，都会想办法拦截用户的返回行为。WillPopScope 就是做这个用的。这个组件会提供一个回调 onWillPop，当用户尝试返回的时候，会被调用，如果返回 false，则会阻止用户的返回行为。

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

@override
Widget build(BuildContext context) {
  return WillPopScope(
    child: Scaffold(
      bottomNavigationBar: BottomNavigationBar(
        items: _items,
        currentIndex: _currentIndex,
        onTap: onTap,
      ),
      body: IndexedStack(
        children: _pageList,
        index: _currentIndex,
      ),
    ),
    onWillPop: () {
      var now = DateTime.now().millisecondsSinceEpoch;
      if (now - _lastClickExitTime > _exitDuration) {
        Fluttertoast.showToast(msg: "再按一次退出应用");
        _lastClickExitTime = now;
      } else {
        SystemNavigator.pop(animated: true);
      }
      return Future.value(false);
    },
  );
}

我一开始没有太注意这个类，和一个安卓的同事搭档的时候，看到他引入了这个组件，才想明白了，很多安卓手机上，有实体或者模拟的返回键，很容易误触，所以确实很需要这个回调。上面是一个使用 onWillPop 防止误触返回的例子。

不过，随着研发的深入，我发现一个很严重的问题。在 iOS 上我有一个习惯动作，就是从屏幕的左边沿，向右滑动，就可以返回上一个屏幕，在 iOS 上，这个动作有个专有名词，叫 Swipe Back，右滑返回。如果我用一个 WillPopScope 套住 Scaffold 的话，iOS 上这个页面，Swipe Back 就会完全失效。手指滑动上去，完全没有反应。而且令人发指的是，onWillPop 也完全不会被触发。等于说，在 iOS 上，这个类的作用仅有一个，就是 Swipe Back 手势被取消，回调也永远不会触发。

这真是太不美了，经过搜索，我发现这个是官方一个很著名的 issue #14203，2018 年 1 月打开，无数人反馈，至今没有一个明确的回应。有人（可能是官方）表示，这本来就是一个期望中的行为，只是文档没有说明。

也有观点认为，“只是拦截这个动作，而且 onWillPop 也可以返回 true，还是允许返回的，为什么在 iOS 就彻底失灵了呢？” —— 我也是这么想的。不过，我细细一想，也有点能理解实现者的做法，在 iOS 上，这个动作会有个配套的动画，右滑的时候，会好像翻书一样的视觉效果。如果这时候 App 不允许用户返回的话，滑到一半，这个动画的物理表现到底是怎么样的呢？像皮筋一样弹回？还是怎么做呢？确实有点恼火。还不如完全就没响应。

不过，这就太苦了我们这种想要在 iOS 上保证交互效果的开发。有某个老哥做了一个 CupertinoWillPopScope 插件，试图要去解决这个问题，不过我看了一眼，很不喜欢他的实现。他的实现其实基于一个事实，就是 WillPopScope 里，如果 onWillPop 为 null 的话，在 iOS 上，就不会阻止 Swipe Back，这个我自己写个变量也可以控制，何至于引入一个插件，一个变量就能解决的事情。

我自己遇到的一个场景，也确实很恼火，在 App 里，我引用了 flutter_inappwebview 这个插件，主要是提供了一个查看网页的 WebView，在 WebView 里，我想实现的效果是，Swipe Back 的时候，如果网页有 history，只是返回上一页，如果没有 history，就退出 WebView。这就需要我每次都能拦截 Swipe Back 这个动作，然后判定后决定到底是在网页里后退，还是干脆退出 WebView。

不过，因为刚才说的 WillPopScope 的问题，导致了很奇怪的局面。当我用了以后。在 iOS 上，效果诡异，我永远失去了 Swipe Back 退出 WebView 的能力，但是，在网页上后退却不受影响。只是退到第一页的时候，就再也滑不动了，不能滑动退出 WebView。如果我去掉 WillPopScope，则不论你在哪个页面，都会导致滑动直接退出 WebView，无法实现返回上一页的功能。

只剩下一个办法，就是通过判断 canGoBack，来决定是否绑定 onWillPop，就可以完全实现我的想法，不过 canGoBack 又是一个 Future 类型，我又不知道怎么写了。唉。问题仍然还是没有解决的，我特别记录在此，给遇到同样问题的同学一些参考，同时也希望高手看到了不吝赐教。

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
30
31
32
33
34
35

@override
Widget build(BuildContext context) {
  mUrl = ModalRoute.of(context)?.settings.arguments.toString() ?? "";
  final double pixel = MediaQuery.of(context).size.width / 375;
  return WillPopScope(
    child: Scaffold(
      appBar: MyAppBar.create(
        title: _pageTitle ?? "",
        pixel: pixel,
        actions: [
          IconButton(
            onPressed: () {
              NavigatorUtils.goBack(context);
            },
            icon: Icon(Icons.close),
          ),
        ],
      ),
      body: _webPageContent(),
    ),
    onWillPop: !_canGoBack
        ? null
        : () /** 此逻辑在 iOS 下无效 */ {
            var canGoBack = webViewController?.canGoBack() ?? Future.value(false);
            canGoBack.then((value) {
              if (value) {
                webViewController?.goBack();
              } else {
                Navigator.pop(context);
              }
            });
            return Future.value(false);
          },
  );
}

上述代码里，_canGoBack 这个变量，是我自己模拟的，但是这个变量的效果和 flutter_inappwebview 提供的就不太一样了，插件提供的 API，返回一个 Future<bool> 类型，在任何时候都可以判定当前网页是否存在 history 栈，但是我自己实现的 _canGoBack 变量，只是判定该网页已经不是首次加载的那个，经历过跳转。在我的场景里，大多数网页，只是看一眼就返回了，用户不会循着链接一层层深入，所以在很大程度上可以达到我要的效果，但是，显然没有真正解决这个问题，如果用户浏览了两个页面，就会退回我上文说的效果了。只是略微好了一点点。

– End –

– Update –

现在已经是 2022 年 11 月 17 日了，这个问题官方仍然没有好的解决方法，只是我在上述方案后面，又有了新的一些探索和问题。特此记录一下。

就我现在的理解来看，上述方案的实现背后，有一些关键性的事实：

第一，App 层面，默认是可以响应 Swipe Back 这个行为的，但是，套上 WillPopScope，提供 onWillPop 回调后，Swipe Back 失效（这是上文已经分析过的内容）；

第二，flutter_inappwebview 这个插件提供的 WebView 组件，内部本身可以响应 Swipe Back 这个动作，因为在 iOS 上，这个插件是用 WKWebView 实现的，所以其行为来自 iOS 系统本身的默认行为，这就是为什么开启 onWillPop 后，虽然不能 Swipe Back 退出 WebView，但是如果你在 WebView 内部多次跳转链接，可以用 Swipe Back 后退；本质上，就是有两层，外层是 App 层面的交互行为，内层是 WebView 内部的交互行为，这两者是分离的（从原文的描述中，可以体会到这一点，这里明确总结出来）；

第三，现在遇到的困扰，就是 Swipe Back 这个动作，在穿越 WebView 和 Flutter App 中间的界限的时候，出现了衔接的问题。这个地方本来就需要衔接，因为 App 和 WebView 都可以响应 Swipe Back 动作，那么应该谁来处理这个事件，程序员就需要自己决定。本来，如果 onWillPop 回调，在 iOS 上没有 bug 的话，一切都很美，可惜事与愿违；

第四，上述解决方案，就是在通过编程，来确立 App 和 WebView 谁来接管 Swipe Back 动作的边界，也即设立了一个 _canGoBack 的变量，作为 flag。核心原理是，内部 history 可以执行 goBack 的时候，就由内部接管，不能执行的时候，就由外部接管。程序员要做的，就是在恰当的时候，正确设定 flag 的值。

原文方案里，我只是在 WebView:onLoadStop 事件中，设定 _canGoBack 的值为 true/false，也即，如果内部 WebView 加载了超过一个页面，那么就由内部接管事件，这个时候开启 onWillPop 捕获，会自动屏蔽 iOS 下 App 级别的事件处理。

现在我们的业务场景遇到一个新的问题，就是 WebView 加载的内嵌页面，可能是一个 SPA，单页应用，这种类型的应用，在页面内部的路由切换，浏览器不需要重新加载，这个时候，就不会触发 onLoadStart/onLoadStop 事件，导致我们设定 flag 的意图无法实现，此种情景下，就会让 back 按钮一点就会退出整个 WebView。

其实，这个问题，也是一个“传统”的难题。比如，大家有没有这种经历，就是去你去街边小店，点餐的时候，从公众号里，点开一个界面，点到一半，想看一下上一步的内容，点了一下后退，结果整个界面被关掉了，十分恼火。微信发展这么多年，腾讯那么强大，竟然在这个小问题上还是没有完美解决，当然，也可能是点餐界面的开发者太垃圾，不管怎么说，都说明这个问题真的很难，很普遍。

那么在我们这里，这种情况是否有解决方案呢？办法总比困难多，目前，我们想到了一个部分解决问题的方法。就是利用 js 回调通信解决。我认真研究了一下单页应用的原理，在 SPA 内部，路由也是一个老生常谈的问题，就是在页面没有加载的情况下，如何根据用户的操作来切换场景。这也是一个经典的面试题。

SPA 的路由实现，其目标是浏览器不重新加载，全部交由页面的 js 来操控界面的绘制和场景的切换。如果通过地址栏 location 改变路径，可能会造成浏览器重新加载。那么常用的方案有两种，第一，使用 http 协议中的 fragment，也有叫 hash 的，就是一个带有 # 号的网址，浏览器在处理的时候，会自动把 # 后面的部分，理解为页面内部的锚点，不会发起 HTTP 请求，第二，使用 history API，这是现代浏览器都支持的一个内部对象，专门管理浏览器的状态，可以通过 pushState，replaceState，go，back，forward 等 API 进行操作。

使用 hash 进行路由的时候，可以直接更改 location，浏览器不会发送请求，但是，会进行处理。使用 pushState 的时候，浏览器完全不会进行处理，所以，哪怕你发个真实的 path 过去，浏览器也不会刷新。这种方式，可以把地址伪装成真实 URL 的样子，看起来很友好。

我发现 spec 里提到，使用 hash 的时候，浏览器会触发一个事件叫 hashchange，这是一个标准的事件，通过注入 js handler，来捕获 hashchange 事件，我们可以知道，内部页面发生了路由，可以进行 goBack，这时候设定 flag，就可以沿用原文中提到的逻辑了。

但是 pushState 本身就不会触发任何事件，每个框架会个自创建事件进行绑定，我们作为 WebView 的实现方，不太好做通用的方案。

– End Update –

SIP 是 MacOS 的一项新特性，System Integrity Protection，系统完整性保护，主要用于阻止系统运行未授权的代码。除了通过 App Store 正规途径分发软件给用户，开发者还可以通过公正，直接分发软件给用户。除此以外的软件分发，都是不被授权的。

执行命令：

1

csrutil status

可以判断系统的 SIP 特性当前状态是否开启。

关机后重启进入恢复模式，才可以在命令行关闭 SIP 特性。

1

csrutil disable

可以关闭 SIP 特性，但是关闭 SIP，会导致系统处于某种危险状态中，这时候运行不安全的软件，就不会被系统阻止，要谨防系统遭到入侵。

重启进入恢复模式的方法是，启动时候，按住 ⌘+R 组合键。如果想要恢复 SIP 的话，还是需要进入恢复模式。执行 csrutil enable 就可以恢复 SIP 了。

学会了使用 Provider 后，真是感觉无比畅快，恨不得每个页面都替换成使用 Provider 来开发。不过今天遇到了一个问题：

1

Unhandled Exception: A SettingsProvider was used after being disposed.

场景是这样的，我有一个 SettingsProvider 保存着“设置”页面的状态，这个页面也就是一般的 App 用于放置“退出登录”按钮的，也正式这个功能引发了问题。

业务逻辑是这样的，当用户点击退出登录按钮的时候，为了防止连续重复请求，我会先把按钮设置成禁用，并展示 Indicator，然后，发起网络请求，去服务器注销 Push Alias，以及注销当前客户端的登录态。

注销成功，或者注销失败，我会解除按钮的禁用，而注销成功后，我会把页面跳转到 Login。这里有些很复杂的情况需要交代：

1. 注销 Push Alias 是在极光；
2. 注销成功后，才能在自己的 Server 注销 registration_id；
3. 完成操作 2，才可以去服务器注销本地登录态；
4. 完成操作 2，才可以销毁本地保存的登录态，不然无法执行 2（需要登录态）；
5. 操作 1 可能会阻塞整个流程导致最终无法退出登录；
6. 完成操作 4 后，需要跳转到 Login。

其实上面一些事情的操作顺序也好，约束条件也好，都还可以进一步推敲，我要说的是，当我执行到 6 的时候，爆了一个 Uncaught Exception，就是上面说的那个 A SettingsProvider was used after being disposed.

经过我在网上搜索和反复比对后我发现，这个错误的成因是这样的。我在网络请求成功或者失败的回调里，尝试解放退出按钮的状态，但是这个时候，异步的执行已经把整个页面给 Pop 掉了，导致了 Provider 的 Listener 提前被 dispose 了，这时候，再去 notifyListeners() 就会导致上面的问题。这个问题提示很难被理解，也很难解决。

网上一种说法，你需要把 Provider 放到更加高一层级的节点上去，这肯定不是一个正确的解，因为这个错误的发生不是 Provider 被销毁，而是因为页面跳走，Provider 的 Listener 被 dispose 导致的。

我用的解决办法是，在调用的时候，用 Provider 的属性 hasListeners 来提前判断一下，是否还有需要通知的对象，然后再调用 notifyListeners()，就不会引发这个错误了。

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

set isWaiting(bool val) {
  _isWaiting = val;
  if (hasListeners) {
    notifyListeners();
  }
}

set buttonValid(bool val) {
  _buttonValid = val;
  if (hasListeners) {
    notifyListeners();
  }
}

代码示例如上。上面这个问题的解决，给我的启示是，当进行异步编程的时候，各种任务同步或异步的发起并执行，各种任务结束的时刻不同，这时候决不能对任务完结的顺序有任何侥幸，否则会给程序代理很多不可预测的问题。

– UPDATE–

最近又遇到个问题，我也续在这里吧，跟这个问题对称的，也是调用方法的时候，报对象已经被 dispose 了，说对称，因为这回是 Provider 被 dispose 了。场景是这样的，在 Provider 里面，触发网络请求，网络请求是异步的，在网络请求回来后，处理完数据，调用 notifyListeners() 是比较常见的一种方法，但是因为这是一个异步的方法，所以，这时候，因为某些原因，Provider 自己已经被 dispose 了，同样会引起 Uncaught Exception。

这个情况怎么处理呢？我这里也写一个，不过未必是最好的，可能也是 SO 看到的。

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

_disposed = false;

@override
dispose() {
  _disposed = true;
  super.dispose();
}

void updateData() async {
  await DioUtils.instance.requestNetwork(
    url,
    onSuccess: (data) {
      // do something
      if (!_disposed) {
        notifyListeners();
      }
    },
    onError: (code, msg) {}
  );
}

...

这个方法使用一个类变量来记录 Provider 是否已经被 dispose，并在 dispose 的时候，改变值，这样就可以随时知道当前的 Provider 是否已经被 dispose 了。虽然不是很雅观，但是很直接地解决了问题。

– END –