Becomin' Charles

这道题目的意思是，计算每个数字的二进制表示里 1 的数量。其实，计算方法，也比较简单，就是写个循环，计算当前循环中的数字的 bit 位数。怎么计算一个数字的 bit 里的 1 的位数呢？

我想到的方法很简单，就是使用 “位与” 计算，一个整数，与 1 进行 & 运算，结果 1，说明最低位是 1，结果是 0，说明最低位是 0。然后，我们把这个数字往右移 1 位。重复这个过程，直到这个数字变为 0。就统计出了所有的 1 的数量。

然后我写出了这个算法：

1
2
3
4
5
6
7
8
9
10
11

class Solution:
    def countBits(self, num: int) -> List[int]:
        res = []
        for i in range(num + 1):
            cnt = 0
            n = i
            while n > 0:
                cnt += n & 1
                n = n >> 1
            res.append(cnt)
        return res

这个算法的复杂度是多少呢？第一重循环是 n 次，第二重循环最多是 log2(n)次，随着数字的缩小，次数还会减少。具体就比较复杂了：[
O(\sum_{i=1}^{n}\log_2i)
]但是，原来题目里有个提示，就是，它问能不能用 O(n) 的算法计算出来。还提示了一句，算法的空间复杂度是 O(n)。你看，上面那个算法空间复杂度是 O(1) 的，没有用额外的空间。而现在明告诉你用 O(n)，其实就是说这题目可以使用递推法。现在 LC 的人流行叫动态规划，不过，我觉得动态规划在这个场景里没有递推法听起来更明白。不过写起来是一回事。

什么是递推法，就是现在第 n 个解，可以用 n 以前的解推理得到。算是动态规划的特殊情况吧。不像动态规划理解起来那么抽象。当然，我说得头头是道的，当时看到题目的时候，脑子是空白的，这个读者你知道就行了。

其实，从我写的那个式子里就看出一种来。比如我用了移位操作，往右移位，其实就是除以 2 的意思。举个例子，假如我现在循环到 5 这个数字，最低位是个 1，然后往右移，继续循环，往右移后其实数字变成了 2，而刚才，其实计算过 2 里面的比特数的，但是在我的算法里，右继续计算了，如果我们不计算，而是查表所得，这里就不用循环了。不是么？

算法可以改改：

1
2
3
4
5
6

class Solution:
    def countBits(self, num: int) -> List[int]:
        res = [0]
        for i in range(1, num + 1):
            res.append(res[i >> 1] + (i & 1))
        return res

这个算法意思就是，先计算最低位的 1 的数量，然后高位部分，查表就行了。有了这个算法，官方题解的另一个算法就不难理解了。既然我们可以把最低位和上面部分分开计算。显然也可以把最高位和下面部分分开。不过，不像最低位这么直观。

我们可以把一个数字分解成，最高位 1 和剩余部分，举个例子：假如 5 二进制表示是 101，可以分解为 101 = 100 + 1，高位是 4，剩余的是 1，也就是 5 是 4 的比特数加上 1 的比特数。计算到 5 的时候，前面 1 和 4 肯定早就计算出来了。4 是什么呢？就是 5 前面最近的一个 2 的整数次幂。而怎么判断一个数字是 2 的整数次幂呢？i & (i - 1) == 0，想明白了么？

具体完整算法我就不写了。去看官方解答或者自己写也不难。

这是今天的打卡题，说实在做得我实在是心态崩坏，先来看看题目，我再来细说：

给你一个嵌套的整型列表。请你设计一个迭代器，使其能够遍历这个整型列表中的所有整数。

列表中的每一项或者为一个整数，或者是另一个列表。其中列表的元素也可能是整数或是其他列表。

示例 1:

输入: [[1,1],2,[1,1]]
输出: [1,1,2,1,1]
解释: 通过重复调用 next 直到 hasNext 返回 false，next 返回的元素的顺序应该是: [1,1,2,1,1]。
示例 2:

输入: [1,[4,[6]]]
输出: [1,4,6]
解释: 通过重复调用 next 直到 hasNext 返回 false，next 返回的元素的顺序应该是: [1,4,6]。

341. 扁平化嵌套列表迭代器 <– 传送门 力扣（LeetCode）

这道题虽然是简单，但是一看这复杂的操作，我就彻底懵逼了。每次将 n-1 个数字加一，最后要所有的数字相等。

这是太抽象的一个过程，脑海里自然联想到了滑块拼图之类的东西，或者覆盖问题，想得极其复杂，所以马上就不知道怎么做了。然后还草稿上画了很多，找这个问题的规律。找了半天也没找到。

暴力解，就是照着题目意思去做，我们想到的就是贪心法，每次挑出最大的一个，其他都加一，然后重复这个过程，直到所有的都相等为止。我想到了这个算法，但是一时半会儿也不能证明这个就是正确的操作法，因题目要求最小的次数。谁知道贪心法的次数是不是最小呢？

所以我就看答案了，果然这个就是最小，有时候做算法题看来也只能靠大胆了。这种根本不用证明的。。。猜一个就是了。猜错就跪了呗。

然后我看到官方题解竟然想出了四种解题方法，第一种就是我说的暴力法，照字面意思硬做。果然，超时，因为是 O(n^2) 的解法啊，肯定过不了。然后第二种是，每次不是加一了，而是直接加 最大值与最小值的 diff，这样可以少加几次。你这么说我当然明白，但是怎么证明这个加法和原来那个加法是等价的呢？也是靠猜就行了？这并不显然啊！！

第三种解法是什么动态规划，我就更懵逼了，根本不是人话好不好，我至今也没看懂。直到最后一个解法出现，我才明白过来。不过官方题解仍然不是用人话写的，我看了一个网友用人话写了，才终于恍然大悟，原来这么简单。

把 n-1 个数字都加一，其实相当于把最大值减 1，这样每次操作 n - 1 个数的抽象复杂情况，变成了一个极其简单的情况，每次挑最大值减 1，这就太简单了。最少肯定是所有值都减到最小值就可以了。太牛了，于是，就是很容易写出一个 O(n) 算法了。在一次遍历中，找到最小值，顺便找出所有数字的和，然后做个减法就完事了。

1
2
3
4
5
6
7

class Solution:
    def minMoves(self, nums: List[int]) -> int:
        nums.sort()
        res = 0
        for i in reversed(range(1, len(nums))):
            res += nums[i] - nums[0]
        return res

最牛逼的 O(n) 算法我就不写了，大家自己写吧，上面这个是我写的 O(nlogn) 的算法，排序后，把所有数字和最小值的差求个和。

给我的启发：

1. 试试逆向思维，不要忘记这一点；
2. 虽然想明白后一点不难写，但是很多时候，题目难都在模型的转换上面，你看到的是假象。

今天的打卡题，是一道“困难”，先来看看题目：

给定一个字符串 s 和一个字符串 t ，计算在 s 的子序列中 t 出现的个数。

字符串的一个 子序列 是指，通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的新字符串。（例如，”ACE” 是 “ABCDE” 的一个子序列，而 “AEC” 不是）

题目数据保证答案符合 32 位带符号整数范围。

115. 不同的子序列 <– 传送门

具体的例子，我都略去了，因为博客的排版比较弱，没法很好展示。其实，这道题目一看，就隐含了动态规划的气味，比如，求解的是个数，而不是具体的位置，第二，隐含了大量的穷举，才能进行的统计。

不过，如果你跟我一样小白的话，就会发现，你根本写不出状态转移的方程的，因为这个状态转移方程非常地不显然。

当然了，无论你想怎么去解决这道题目，首先还是要自己看懂题目。我们看看如何确定 t 在 s 中出现的次数。举个例子，假如 s = ababc，t = abc，那么很显然，t 在 s 出现了三次。然后我们来理一下，怎么统计。首先，我们把 t 的第一个字符 a，在 s 中标定，然后，是 b 标定，最后是 c，当 a 固定在第一个字符的时候，b 其实有两个选择。这两个选择的 b 都对应着唯一的 c，所以有两次，而 a，还有另一个选择，但是选那个 a 的时候，b，c 都只有唯一选择了，所以，总次数就是 3 次。

我上面描述的这个过程，就是一种最直观的统计策略。逐个标定 t 的每个字符，而且要穷尽每个字符的多个位置选择。这个就是一个比较明显的回溯过程。所以，很自然，我写出了回溯算法：

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

class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        self.res = 0
        self.dfs(s, t, 0)
        return self.res

    def dfs(self, s: str, t: str, p: int) -> None:
        if len(t) == 1:
            self.res += s[p:].count(t)
            return

        for i in range(p, len(s)):
            if s[i] == t[0]:
                self.dfs(s, t[1:], i + 1)

虽然是一道困难题，但是解法却很短小嘛，这个算法，每成功标定一个 t 的字符，就把 t 截短一截，然后继续向前扩展。这里有很低效的地方，比如每次截短 t，以及每次拷贝 s 之类的，容我偷个懒。

这个算法通过了 87% 的用例，说明，这是一个正确的算法，但是时间复杂度过高了。可以简单分析一下递归算法的时间复杂度，函数体内部，最坏情况循环大约是 len(s) - len(t) 次，而没深入一层，s 和 t 各减少了 1 （t 截短了 1 个字母，s 的下标后移了一个）。所以，然后把每层乘起来，综合复杂度是 O((m - n)!) 的复杂度。难怪过不了。

很容易想到，这个算法的优化空间，就是引入缓存，对中间结果进行记录，可以大幅减少搜索的数量。让我们来优化一下：

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 numDistinct(self, s: str, t: str) -> int:
        self.s, self.t = s, t
        self.m, self.n = len(s), len(t)
        self.mem = {}
        return self.dfs(0, 0)

    def dfs(self, p: int, q: int) -> int:
        if self.m - p < self.n - q:
            return 0

        # 缓存
        k = (p, q)
        v = self.mem.get(k, -1)
        if v > 0:
            return v
        
        if q == self.n - 1:
            v = self.s[p:].count(self.t[-1])
            self.mem[k] = v
            return v
        
        total = 0
        for i in range(p, self.m):
            if self.m - i >= self.n - q and self.s[i] == self.t[q]:
                total += self.dfs(i + 1, q + 1)
        
        self.mem[k] = total
        return total

然后，我优化出了这个算法：

1. 不在使用字符串作为参数，只是使用下标，避免了字符串拷贝
2. 改换了函数的返回值，使得方便去缓存
3. 引入了缓存来记录结果
4. 如果 s 长度小于 t 显然就不用继续搜索了，可以直接剪枝

这么多优化后，总共 62 个用例，过了 61 个，好消息是优化是有效的，效率提高了很多。坏消息是，仍然 TLE。这给我们最大的提示就是，非多项式时间的算法，无论怎么优化，在足够大的问题规模面前，就是无法有效运算。哈！

还是要使用递推方法，用动态规划来解，一个是不用递归，省去了栈的开销，另一个就是放弃了大量无效的搜索。但是写不出状态转移方程怎么办？不要急，仔细观察一下咱们优化后的算法。

为了避免拷贝字符串，我们用 p 和 q，记录了 s 和 t 的下标搜索位置，从上述算法里，我们能看到 dfs(p, q) 其实就是 dfs(i + 1, q + 1) 当 s[i] == t[q] 时，i 的取值范围是 [p, m)。这几乎就是状态转移方程了。

第一版状态转移方程：[
f(i, j) = \left {

\right.
]

现在这个方程基本上是没法写出代码来的，基本上是递归搜索方法的原本表达，一个是里面有个求和公式，就算写出来，算法的时间复杂度也是O(n^3)的，另一个就是，在 s[i] != t[j] 的时候，没有写出方程。这时候，我们就要耐心下来深入研究一下，怎么把这个状态方程给写完整了。

再来观察一下 dfs 的实现，在 for 循环里，套了一个 if，所以我们直接写出了 s[i] == t[j] 时候的情况，if 的 else 子句，代码里没写，其实就是 s[i] != t[j] 时的状态转移，我们发现，其实 else 的情况，就是跳过了这个下标，直接从下一个重复这个扫描过程了。相当于是调用了 dfs(i + 1, j) 了。这里可以品味一下。

然后在看怎么解决那个求和公式，其实解决起来也不难，就是咱们可以展开这个求和公式来看看：[

]

不知道这么解释，容易理解么？这里我们用了一个数列求和的小技巧，就是错位相减，然后得到了 f(i,j) 的递推公式，到此，我们就构造了我们的第二版状态转移方程：[
f(i, j) = \left {

\right.
]

有了状态转移公式，我们还要处理好边界条件，当 j = len(t) - 1 的时候，f(i, j) 的值，其实就是那个字符出现的次数。所以，我们可以把 i 从 0 到 len(s) 的值，初始化成在这个范围内搜索 t 的最后一个字符的出现次数。而实际上，更抽象地看，可以理解成，空串出现的次数。因为空串是任何串的子串，所以空串都会出现 1 次。当然，这个结论并不显然，这可能需要一些证明，我们可以这么猜测，如果是对的就万事大吉了。毕竟我们不是在做数学证明。

另外一个边界，就是递归代码里也用到了，就是 s 剩余的长度小于 t 剩余的长度时，就不用扫描了，显然结果是 0 。

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

class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        if len(s) < len(t):
            return 0
        dp = [[0] * len(t) for _ in range(len(s))]

        for i in range(len(s)):
            dp[i][len(t) - 1] = s[i:].count(t[-1])
        
        for i in range(len(s) - 2, -1, -1):
            for j in range(len(t) - 2, -1, -1):
                if s[i] == t[j] :
                    dp[i][j] = dp[i + 1][j + 1] + dp[i + 1][j]
                else:
                    dp[i][j] = dp[i + 1][j]
        return dp[0][0]

我写出了这样的实现。7 - 8 行，可以用我说的更抽象的形式去替代，这样效率会更高一点。少了 len(s) 次的字符串统计行为。这个代码经测试是正确的。

总结，我通过这篇文章，从分析题目，到写出朴素的回溯算法，然后进行性能优化，发现了状态转移，并优化了状态转移方程，最终写出了动态规划算法。状态转移方程的物理意义，在优化过后已经变得比较模糊了，有时候强行去解释的话，，听起来很绕，而且一下子想看懂，恐怕也非常难。学习动态规划，不用去纠结这一点，不然真的会陷在里面。

这道题目，展示了一款二进制手表，然后问，给定点亮的灯的数量，计算可能展示出来的所有时间。这个题目，一看就知道可能要用回溯法了。

回溯法，其实就是穷举法的一种，只不过穷举得比较有章法而已，有时候我们说回溯法是深度优先搜索。回溯法的关键是，第一步，确认目标达成条件，作为回溯停止的点；第二步，找出状态空间，确认扩展下一步的方法；第三步，确认所有需要保存的状态；最后，写出递归算法。

对于这道手表的题目，题目要求点亮 num 盏灯，然后计算可能的时间数量。所以，我们可以把所有 num 盏灯都点亮，作为达成了目标的条件。第二，手表上，有代表小时的灯，1，2，4，8，四盏，以及代表分钟的灯1，2，4…… 等六盏灯，其实就相当于一共有 10 个位置，每次可以点亮一个。这么看，总状态空间，也就 2^10 个，就算都遍历了，也没多少……第三，我们要保存的状态，就是，点到第 i 盏灯的时候，表盘上所有的灯的亮灭情况。可以开动了：

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
36
37
38
39
40
41
42
43

class Solution:
    def __init__(self):
        self.result = []
        self.possible = [1,2,4,8,1,2,4,8,16,32]
        self.visited = [0] * 10

    def readBinaryWatch(self, num: int) -> List[str]:
        self.num = num
        self.dfs(0, 0)
        return self.result

    
    def dfs(self, step: int, start: int):
        if step == self.num:
            self.result.append( self.time_to_str() )
        else:
            for i in range( start, 10 ):
                self.visited[i] = 1
                if not self.valid():
                    self.visited[i] = 0
                    continue
                self.dfs(step + 1, i + 1)
                self.visited[i] = 0
    
    def valid(self) -> bool:
        h, m = self.cur_time()
        return h < 12 and m < 60
    
    def cur_time(self) -> ( int, int ):
        h = 0
        m = 0
        for i in range(10):
            if self.visited[i]:
                if i < 4:
                    h += self.possible[i]
                else:
                    m += self.possible[i]
        return h, m
    
    def time_to_str(self) -> str: 
        h, m = self.cur_time()
        return str(h) + ":" + ( "0" if m < 10 else "" ) + str(m)ç

上面的算法，用 visited 记住了每盏灯的亮灭情况。然后，把所有灯做了一个数组，逐盏去点亮，尝试每盏灯的亮灭组合。所有 num 盏灯点亮后，就算达成条件。剩下的就是剪枝了，对于不可能的时间（小时超过 11，分钟超过 59），可以直接跳过。

使用位图记录访问过的状态，是一个比较通用的做法，想不出来怎么记录状态的时候，这种“好记性不如烂笔头”的思维，很容易奏效。但是未必是最好的方法，不过好的方法总是需要灵光一现的。题解里，有个 C++ 的同学，提供了一个写法，他的不同在于，他用 dfs 方法的参数来记住状态，方法的参数也具有局部性，只在调用的时候有效，调用结束后，就天然可以回退。我们注意一下我们的做法，我们把 10 盏灯顺序排列了。从左往右去遍历，这个时候这个行为本身是有序的。而 visited 数组也是有序的，就是顺序这件事情我们记录了两次。其实其中一次是可以省略的。所以，这个同学用 hour 来记住小时，用 minute 来记住分钟，下标本身已经带有了顺序，就不用额外记录了：

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

class Solution:
    def __init__(self):
        self.result = []
        self.possible = [1,2,4,8,1,2,4,8,16,32]

    def readBinaryWatch(self, num: int) -> List[str]:
        self.num = num
        self.dfs(0, 0, 0, 0)
        return self.result

    
    def dfs(self, step: int, start: int, hour: int, minute: int):
        if step == self.num:
            time = str(hour) + ":" + ("0" if minute < 10 else "") + str(minute)
            self.result.append( time )
        else:
            for i in range( start, 10 ):
                if i < 4 and self.possible[i] + hour < 12:
                    self.dfs(step+1, i+1, hour + self.possible[i], minute)
                if i > 3 and self.possible[i] + minute < 60:
                    self.dfs(step+1, i+1, hour, minute + self.possible[i])

换种说法，上面第一种算法使用 visited 无法就是为了用于推算 hour 和 minute 的值，现在我直接记住 hour 和 minute 的时间就可以了，也做到可以正确回退，visited 就没用了。于是，写出了更简短的算法。不过在复杂度上是一样的。

好几天没有写题解了，为什么没有写呢？就是我觉得好像这道题没有什么意义：比如，这道题，极其繁琐，没什么巧思；或者，这道题，根本就是脑筋急转弯，想得出来就无比轻易，想不出来就误入歧途，功底无用。

这种状态就是极其危险的状态，所谓的高不成、低不就。非要等一道完美的题目出现，才去认真学习和分析么？这是心飘了。要警惕，深刻地警惕。每道题，都要认真对待，尽量读懂，自己做出来了，要跟别人的做法去比较，自己做不出来，要看懂别人的做法，不能轻视一道题目。

自勉结束，看看今天的打卡题。题目要求是按照顺时针螺旋顺序，打印一个给定的 m×n 的矩阵。也就是字面意思，我不想抄题目了，给个传送门吧。这里是传送门 。

这道题目真的看起来极其简单的，就是判断一个数字是不是完全平方数，比如 16 是 4 的平方，9 是 3 的平方。可惜，愚笨如我，能想出来的方法，只有一个，就是从 1 开始求平方，然后逐一去比较，不能更蠢了吧？就是穷举法。

于是我去看题解，还有什么解法，才知道，原来这么简单的一道题目有那么多种解法的。官方题解里说可以用“递归”，我是完全没想出来的，官方的题解里也没列举，所以只好作罢了。直接说说二分查找法吧。

其实，从 1 开始逐一去求平方，然后尝试，这个方法，已经接近了二分查找法了，既然能想到顺序逐一穷举，就自然能想到二分查找啊，两大要素是：1，有序；2，逐一遍历；妈呀，我为啥想不到，还是太浮躁。

另外，让人头痛的是，二分法真的很不好写。每个人都可以轻飘飘说句，二分呀，你试试直接一口气写对？上下标直接叫人疯狂，每次我狂推理搞明白了，过几个月，就又回到了从前。

如果我们要用二分法的话，那么首先要知道起始和终止的位置，然后用二分法解决。起始位置很容易判定，就是 0，终点呢，是 num 本身么？也未尝不可，不过，如果稍微对数字有点感觉，就知道到，只要到 num/2 就可以了。证明起来也很容易，就是证明这个不等式：[
\sqrt{n} \leq \frac{n}{2}
]可以看出，在 n > 4 的时候，显然是成立的，在 1 < n < 4 的时候，也不会妨碍程序的正确性。

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

class Solution:
    def isPerfectSquare(self, num: int) -> bool:
        if num == 0 or num == 1:
            return True
        
        start = 0
        end = num // 2

        # 这里使用闭区间[start, end]
        while start <= end:
            mid = ( start + end ) // 2
            sqr = mid * mid
            if sqr > num:
                end = mid - 1
            elif sqr < num:
                start = mid + 1
            else:
                return True
        return False

关于二分法怎么能一次写正确，以前我也看过，自己也反思过，不过还是忘记了，这次我又是打开谷歌搜索来搜的“怎么才能把二分法写正确”，这次搜的文章，我觉得讲得挺清楚的，没有各种“酷炫”的比喻，就是很抽象地硬是给你讲清楚了《二分法其实很简单，为什么老是写不对！》，这里推荐一下。

把握住一个关键点，就是循环不变量。关键在于你怎么理解你的搜索区间，根据你对区间的理解，来决定用 < 还是用 <=，用 +1 还是用 -1，虽然，循环不变量的概念很抽象，开闭区间的概念也很抽象，但是，这个说法确实是准确和好用的，判断起来也比较容易。咱们写代码还是期望能快速的写对才是正事。

第二种比较高级的解法，是使用牛顿迭代法，大家自己去看就行了，我就不写了。我觉得，牛顿迭代法首先就要求比较高的数学功底，而且，就算你数学层面懂了，还要知道数学层面怎么才能转化成代码。这个题目里，函数正好是一个平方函数，而且函数的根正好收敛。在函数二阶不可导的情况下，是不能使用牛顿迭代法的，而且初次 guess 选点如果碰巧选到了二次曲线的顶点也是要糟糕的，LC 给出的算法，什么都没考虑，就直接正确了。要么是他运气好到炸裂，要么就是确实那些人家都考虑了，没有处理的必要，所以写出来才能如此间接。但是就好像那个画马，“增加一些细节”的步骤，你不会的话，你永远画不出一匹马的。

第三种解法，我看在 LC 上，真的点赞很多，底下网友都说机智，这也是对数学有着非常敏锐的感觉的人，才能想出来的妙法。奇数等差数列的和，正好是序号的平方。也即，1 到第 k 个奇数的求和，正好等于 ，这点用等差数列求和公式可以轻松证明。于是，从 1 开始做个循环减法，减到 0 就是完全平方数，减不到 0，就不是。太妙了。

1
2
3
4
5
6
7
8
9

class Solution:
    def isPerfectSquare(self, num: int) -> bool:
        if num < 2:
            return True
        i = 1
        while num > 0:
            num -= i
            i += 2
        return num == 0

这个真是绝了，简短而且健壮，几乎不容易写错。不过那个灵光一闪，不是每个人都能想出来的。

其实，昨天我就打开了今天的打卡题，看到中等难度，我心里也是一咯噔，毕竟我现在的水平，简单也未必都能做出来的啊。

仔细读了题目意思后，发现，真的是难，超出了我能控制的范围了。晚上睡在床上就在反复推演，这个题目到底应该怎么做，没有什么头绪睡着了，早上起来，马上看答案。原来是用分治法。

这个题目的意思是，找到一个最长的子串，子串里的每个出现的字母，出现频次不少于 K。我真正反思的是，为啥我写不出一个算法，我发现，我就算不用代码，用嘴也不能说清楚，我到底按照怎样的步骤来做这个题目。这里的问题就严重了，如果你能说出一个算法，那可能往往是性能差，效率低，但是终究还是有一个算法的。现在的问题是，我根本连一个算法也拿不出，这就有点困扰了。智商被碾压。

分治法的实际做法是比较朴素的，就是先统计每个字母的出现频次。因为只有小写字母，所以一共就 26 个，这里如果所有的字母频次都大于等于 K，那么整个串的长度就是我们要的解。如果有至少一个字母频次不足 K，我们可以用这个字母来分割字符串。先从第一个分割位置开始，逐一统计每个分割出来的子串的长度，最大的值就是我们的解。

这个解法是递归的，对于每个子串来说，我们也用同样的策略来统计。于是就有了这样的算法：

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

class Solution:
    def longestSubstring(self, s: str, k: int) -> int:
        return self.dfs(s, 0, len(s) - 1, k)

    def dfs(self, s: str, l: int, r: int, k: int) -> int:
        freq = collections.Counter()

        for i in range(l, r + 1) :
            freq[s[i]] += 1

        split = '#'
        for i in range(l, r + 1) :
            if freq[s[i]] < k:
                split = s[i]

        if split == '#':
            return r - l + 1

        ret = 0
        i = l
        while i < r:
            while i <= r and s[i] == split:
                i += 1
            
            if i > r :
                break

            start = i
            while i <= r and s[i] != split:
                i += 1

            ret = max(ret, self.dfs(s, start, i - 1, k))
            
        return ret

算法的主体是个深度优先搜索。每次分割，要重新统计里面每个字母的频次，主要因为切割过后，新的子串里的某个字母可能出现了少于 K 次，这就成为了重新切割的依据，这也是说这个解法是递归的原因。

官方题解里，还提到了一个滑动窗口的算法，不过我看了两遍，竟然真的没有理解到底是什么意思。略微崩溃，容我回头再细细体会吧。

这是今天的打卡题，我打开一看标签是困难，心里咯噔一声，觉得完蛋，今天我肯定做不出来了。事实也确实如此。

这道题的意思是，给出一个 word，和一个 puzzle，然后判断 word 是不是 puzzle 的一个解。满足的条件是 puzzle 的第一个字母在 word 中出现，然后就是 word 中的每个字母，都在 puzzle 中出现。没有顺序的约定，也没有频次的约定。

看起来似乎不那么难，于是我写了这样的代码：

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

class Solution:
    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:
        # 初始化答案数组
        result = {}
        for p in puzzles:
            result[p] = 0
        
        sets = {}

        for w in words:
            for p in puzzles:

                if p in sets:
                    p_set = sets[p]
                else:
                    p_set = set([i for i in p])
                    sets[p] = p_set
                
                first_c = False
                c_c = True
                for c in w:
                    #检查第一个字母
                    if c == p[0]:
                        first_c = True
                    if c not in p_set:
                        c_c = False
                        break
                
                if first_c and c_c:
                    result[p] += 1
        
        return [ result[key] for key in puzzles ]
                    

果断写了一个 O(m*n) 的算法，也是可以跑出第一个用例的答案的，不过颤抖吧少年，这道题的精髓在“提示”里面，words 这个列表的长度有 10^5，而 puzzle 的列表长度 10^4，如果，按照上面的算法，不要侥幸，肯定是 10^9 次比较，不知道算到哪年能算出来了。在这里等着呢。

好吧，只能看答案了。原来这道题目的套路叫“状态压缩”，我自己主动放弃的一个已知条件是，“没有顺序也没有频率的要求”，与其说是“放弃”，不如说是“不会用”。还有个条件是，word 和 puzzle 里只会出现小写字母。然后这题目就成了判断 word 里出现的字母，是不是都在 puzzle 里有，至于 word 里每个字母出现位置和次数都不重要了。

因为字母一共只有 26 个，所以我用一个 26 个 bit 的位图，就可以表达每个字母的有无了。一个整型是 32 位，正好可以用一个整数表达。于是，所有的 word 都可以表达成一个整数的位图。显然有些 word 虽然字面不一样，表达成位图后是一样的。于是我们可以用一个字典记录下来次数。

接下去，第二个任务就是怎么把 puzzle 也表达成位图，然后去字典里查表就可以了。因为 puzzle 也只不过是一个字母的集合，word 包含的字母只要是任何一个 puzzle 的非空子集，就算是合法解了。这里留了一个小曲折，就是必须包含 puzzle 的第一个字母。那就变成了，除去 puzzle 的第一个字母外的所有子集（含空子集），与第一个字母（也是一个子集）的并集。总归是一个求子集的问题。

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

class Solution:
    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:
        freq = collections.Counter()

        for w in words :
            bitmap = 0
            for c in w :
                bitmap = 1 << ord(c) - ord('a')
            freq[bitmap] += 1

        ans = []
        for p in puzzles :
            total = 0

            mask = 0
            for c in p[1:] :
                mask = 1 << ord(c) - ord('a')

            s = 1 << ord(p[0]) - ord('a')
            total += freq[s]

            subset = mask
            while subset > 0:
                total += freq[s  subset]
                subset = ( subset - 1 ) & mask

            ans.append(total)
        return ans
                    

参考答案，我写出了这样的算法。这里有几个点，第一，用到了一个数据结构叫 Counter，我以前没用过，只会用 dict，其实就是一个内置的封装，没想到还挺好用的，以后可以多用用。这种计数性质的任务还挺多的。

第二，比较神奇的是 23 - 25 行代码，这里展示了一个求二进制数字的子集的方法。这个方法，简直神了，我网上搜了一下，解释得比较清楚的是这篇文章，基本陈述了这个算法的推理过程和原理。虽然我也没有看得很懂，但是比官方题解好多了。

第三，有个优化点我没写，就是题目有个已知条件，puzzle 一共只有 7 个字母，每个字母都不一样，如果 word 的 bitmap 里面的 1 的数量超过七个，其实不用加入到 freq 这个 Counter 里面了，可以节省一点空间，不过因为这个是 O(1) 的查询复杂度，其实对性能影响微乎其微。

这第二个写法，基本的复杂度是 O(m + n) 的，这里 m 和 n 肯定是有系数的，比如，每个 word 的长度是不超过 50，对于每个 puzzle， 有 7 个字母，所以子集的数量有 2^6 个（第一个字母都包含），这个就是 n 的常数系数了。空间复杂度是 O(m) 的。

位运算技巧集锦：https://graphics.stanford.edu/~seander/bithacks.html

OI 比赛的网站：https://oi-wiki.org/ 有空可以学习

这道题目，我直接想到的就是双指针算法了，一个指针从头往后找，一个指针从后往头找，然后找到元音后停下来，然后，交换，继续循环。

关键是循环终止的位置，应该是头尾两个指针碰到的时候。我就写出了这样的代码：

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

class Solution:
    def reverseVowels(self, s: str) -> str:
        ss = [ x for x in s ]
        i = 0
        l = len(ss)
        j = l - 1
        vowels = ['a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U']
        while i < j:
            while i < l and ss[i] not in vowels:
                i += 1
            while j > 0 and ss[j] not in vowels:
                j -= 1

            if i <= j:
                ss[i], ss[j] = ss[j], ss[i]
                i += 1
                j -= 1
        return "".join(ss)

我先把字符串转换成了 list，因为我发现字符串里的字符不能更改，记得 Python 的 string 是 immutable 的。所以换了。

这个算法的复杂度理论上是 O(n) 的，不过在尾指针那里，往头部找元音的时候，如果最坏情况，可能会是重复搜索，可以增加一个条件，就是 j >= i 避免无畏地搜索。