LeetCode刷题笔记（三）

每期10题，上一期参见LeetCode刷题笔记（二）。

本期内容多以动态规划为主。

动态规划

392. 判断子序列 - 动态规划

输入：长序列 t，短序列 s

判断：s 是不是 t 的子序列

条件：

• 从原始序列到子序列，可以删除部分字符，可以不连续，但是相对位置不能变
• 两个序列全是英文小写字母

传统方法：

• 如果可以不改变顺序地去重，那么就可以直接取筛选了

怎么样使用动态规划呢？

到了 t 的第 n 个字符，已经发现了 s 的字符数为 f(n)

那么

• 如果这一个（t_n）不是s中的下一个（s_(f(n-1)+1)），那么f(n) = f(n-1)
• 如果是，那么f(n) = f(n-1) + 1

推导至 t 的结尾，或者到了s 的结尾，就要停止了

如果s到了结尾，那就说明是子序列

特殊情况：

（1）短字符为空

（2）长字符和短字符一样长【如果不相等可以直接判断为False了】，那相等直接判定为True【其实这个也不必了】

这个问题最容易出错的地方是list的索引问题，上代码：

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        yes_num = 0
        if not len(s):
            return True
        # if len(s) == len(t):
        #     return False if s != t else True
        for i in range(len(t)):
            if t[i] == s[yes_num]:
                yes_num += 1
            if yes_num == len(s):
                return True
        return True if yes_num == len(s) else False

yes_sum 直接代表了 s 中的下一个位置【因为list从0开始】，也表示了 s 已经匹配的字符数量

所以最后对比yes_num和s的长度就不用长度减一了！！

所以长字符和短字符一样长的情况也就不再是特殊情况了

最后，最简化版本，特殊情况不特殊，最后判断也多余：

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        yes_num = 0
        if not len(s):
            return True
        for i in range(len(t)):
            if t[i] == s[yes_num]:
                yes_num += 1
            if yes_num == len(s):
                return True
        return False

746. 使用最小花费爬楼梯 - 动态规划

本题确实是一个动态规划方面的问题，但是我得说这个问题的描述有点迷糊

输入：一个列表，全是数值，长度至少是2

输出：最小子序列的和

要求：

• 该子序列可以连续，也可以间隔1个；
• 该子序列可以不包含第1个元素（索引为0）；
• 该子序列可以不包含最后一个元素（索引为 n-1）；

假设到第 n 个数值，最小和为 f(n)

有三种可能：怎么样去选择？

• $f(n) = f(n-1)$（可以从第2个数，也就是索引为1开始）【跳当前数值】

  • 问题：【那这个肯定比第二种要小，怎么说？】

• $f(n) = f(n-1) + i$（可以从第2个数，也就是索引为1开始）【连续】

  • 如果此时 n 是最后一个，那么 i 是不能加的【但问题是我不知道 n 到底是不是最后一个】

• $f(n) = f(n-2) + i$（可以从第3个数，也就是索引为2开始）【跳前一个数值】

  • 如果此时 n 是最后一个，那么 i 是必须加的

初始条件：

• $f(1) = i_0$
• $f(2)=min(f(1), i_1)$【如果能跳过2个，那么一定会跳过，否则和一定会变大】

终止条件：

• $n$ 到了结尾

现在思路开始混乱了：

在第 n 个数值，有几种情况？选择当前，不选择当前，不管选不选当前，都有可能选前一个数值

• 一般情况下，我肯定不会连续选择数值，除非旁边的数值更大，或者没得选

阅读题解

递归关系似乎是 $f(n) = i + min(f(n-1), f(n-2))$

最后一步，为了防止最后一步需要判断取舍，可以直接在最后选择 f(n) 和 f(n-1) 中比较小的，那就实现了最优

还有一点就是，这样的话，初始化就和上面略有不同了：

• f(1) = i_0
• f(2) = i_1

因为最后已经增加了判断最后一个数值取舍的步骤，这里的 f(2) 就没有必要多一次判断了

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        sum_cost = []
        sum_cost.append(cost[0])
        sum_cost.append(cost[1])
        if len(cost) == 2:
            return sum_cost[-1]
        for i in range(2, len(cost)):
            sum_cost.append(cost[i] + min(sum_cost[-1], sum_cost[-2]))
        return min(sum_cost[-1], sum_cost[-2])

面试题 17.16 按摩师 - 动态规划

输入：一个序列

输出：子序列的和，最大和

要求：子序列元素不能相邻

本题就是比较典型的动态规划

状态表达式：$f(n)$ 表示到第 n 个数的最大和

状态转移方程及条件：

（1）$f(n) = f(n-1)$，什么条件？

（2）$f(n) = f(n-2) + i$

那本题岂不是和198题相同？？

在746题中，因为可以连续，或者只能间隔一个，所以是先比较最大值（最小值），然后再加当前值

但是本题不能连续，不能先比较最大值

本题有个问题，一定会选择当前数值吗？不一定

和198题还真是一样的，就考虑三个特殊情况：

列表长度为0，1，2，分别是0，sum(list)，max(list)，有没有什么方法可以一句话搞定的？

389. 找不同 - 运算，ASCII和异或

输入：两个字符串 s 和 t

输出：t 中 s 没有的字符

要求：t 由 s 随机重排并添加了一个字母

本题居然是简单？

观察示例发现：

添加的字母有可能是s 中已有字母重复的，那么这样的话使用 set 元组做去重就是不太好的方法了

如果遍历 s 中的字符，找 t 中的位置，然后找出那个字符呢，时间复杂度为 o(n)，可能不是最好的方法【尤其如果s本身含有重复字母，那么t中肯定也有重复字母了】还好s最长只是1000，那么肯定会有重复的，这样确实不是太好难道说要统计s中每个字母的数量，然后去对比吗？普通的list并没有找出全部索引的功能吧

官方题解

（1）计数，还真的可以对字符串中出现的字母进行计数，然后比较（这里使用的方法是在t中进行递减计数，当数字为负，那就找到了数字）

（2）位运算【这个思路比较好】

把两个字符串合二为一，肯定有一个字母出现次数不是偶数，就是ta

类似 136题，这个题我做过了，但是说实话，这个异或我还是没有太明白

好像明白一点了，如果 一个字母是唯一的，那么任何字母和它异或，都不会改变它，而且由于其他的成双成对，最后一定都会相当于和自身异或一次，会最后剩下一个字母

这个方法的空间复杂度和时间复杂度都是一定的，而且没有优化的空间

（3）求和

这个方法用的是ASCII码的方法，ASCII码的和的差值就是多出来的那个字母的ASCII码

python ASCII码 ord('a')

从ASCII码反读字母呢：chr(num)

1025. 除数博弈 - 动态规划，数学

输入：int 数字 n，1到1000之间

输出：布尔值

功能：每一轮的要求如下，最后要求出来的是总轮数，如果为奇数那么返回True，如果为偶数返回False

• 对于任意 ==x<n==，余数如果为0就是true

• 然后 n=n-x，对于新的任意 y<新的n，余数为0就是true

• 直到找不到使余数为0的除数 z<新的新的n

题目中举了一个很有意思的例子：3

• 第一位选择 1，那么余数是0【其实对于任意 n，总可以以1为除数，得到余数为0】，然后3-1=2
• 第二位选择 1，余数还是0，然后 2-1=1
• 然后不能再选1了，因为不满足 x<n(此时n=1了)

也就是说每一轮，n在更新，除数的上限也在更新，除数也在更新，如果被除数变为1，那么游戏就结束了

难点：

• 找整除的数，1是万能的，除1以外-永远可以整除，但问题是也要防止给对方留下赢的空间
  • 比如4
    • 选2，剩下2，选1，输了
    • 选1，剩下3，选1，剩下2，选1，赢了
    • 那这样的话肯定第二种思路要比第一种要好
• 也就是说要最优化 - 尽可能赢，除非必输

本题居然是简单？

假设当前剩余数字 n，最佳轮数\路径是 f(n) 【这样不行】

问题是本题是数字n越小越容易发现正确路径，数字越大反而越不容易

比如 n = 1，直接输，1步

n = 2，直接赢，1步

n = 3，一定会输，没得选，2步

n = 4，可以赢，2步，3步（赢）

n = 5，

• 选1，为4
• 这下选择权在对方手里，一定输【每轮都是按照最优方法】2步（输），3步

n = 6，

• 选1，为5，1+1+2或3，最后一定输
• 选2，为4，2或3一定输
• 选3，为3，一定赢

【问题就在于这个关系是一个可以递推的关系吗？所以要怎么样才能实现动态规划？】

如果这一步过后，留给对手的总轮数可以是奇数，也可以是偶数，那么对手一定会选择偶数，那么我方一定会选择奇数，永远在博弈

其实已经渐渐发现规律了！

题解

非官方：https://leetcode-cn.com/problems/divisor-game/solution/qi-shi-shi-yi-dao-shu-xue-ti-by-coder233/

刚才比较的对剩下数字来说，轮数的奇偶比较

换一个思路：

1. 什么时候能判断最终结果？N = 2时。那么就是看到谁手里为2。
2. 剩下的数字是奇数还是偶数？

核心思想：==奇数的约数一定是奇数，偶数的约束可奇可偶==

如果开局奇数：第一次不管选什么，对方手里都是偶数

如果开局偶数：只要一直选1，那么对方手里一定是奇数（2一定不在对方手里），这样就到了上面的情况【妙啊，太妙了！】

所以，总结出来就是，开局奇数，必输，开局偶数，必赢

所以，只要判断奇偶数就好了【炸】

官方题解中还有一种思路是找让对方处于“必败态”的情况

分治法

50. Pow（x, n）- 基础，复杂度 - 分治

输入：正负100以内的浮点数 x 和 32位带符号 int 数 n

输出： x 的 n 次幂

本题就是纯粹的数学问题的算法实现，关键是这个幂的范围异常大，所以如果真的一个一个乘，时间复杂度会爆炸，所以就是为了尽量压缩时间复杂度诞生的问题！

首先计算不大于 n 的 $2^k$ 幂，k也就是循环的次数，这样能够尽量减少时间复杂度

• k = 0，那么就是 x
• k = 1， x * x
• k = 2，x^2 * x^2
• k = n，x^n * x^n

然后对于剩下的 $n-2^k$ 次幂，就转化为求解 x 的 $n-2^k$ 次幂的问题，就可以迭代了

细节：

（1）x 化为正数，直接把 x 变成 正数，但是最后结果的正负还要看 n 是奇数还是偶数

（2）指数为负时，直接把x的倒数求出来

（3）特殊情况：

• x 为0，直接为0
• n 为0，直接为1
• n 为1，直接为x

以下是我成功的代码：

class Solution:
    def myPow(self, x: float, n: int) -> float:
        if x == 0:
            return 0
        if x == 1 or n == 0:
            return 1
        if n < 0:
            x, n = 1/x, abs(n)
        weight = 1
        if x < 0 and n % 2:
            weight = -1
            x = abs(x)
        result = 1
        res = n
        while res:
            this_k, this_pow_2 = self.max_2_pow(res)
            this_x = x
            print(this_k, this_pow_2)
            while this_k:
                this_x *= this_x
                this_k -= 1
            result *= this_x
            res -= this_pow_2
        return weight * result
        
    def max_2_pow(self, n: int) -> int:
        # 求不大于 n 的 2 的 k 次幂
        pow_2 = 1
        k = 0
        while n >= pow_2:
            pow_2 *= 2
            k += 1
        return max(k-1, 0), max(1, pow_2 / 2)

其中，多次修改的部分是关于“不大于 n 的 2 的 k 次幂”的求解

一般情况下，$2^k \leq n < 2^{k+1}$，此时需要输出的是 k，但是因为满足 while 的循环条件，会多计算一层，所以最后的结果又要扒去一层，但是又要考虑 $ n = 1$ 的情况【这里n不可能为0，因为已经被其他的条件约束了】，所以又要防止把 k=0 和 n=1 又给削了

还有一种找 $2^k$ 的方式，是观察余数，如果 $n % 2^k < 2^k$，那么自然是介于$2^k$ 和 $2^{k+1}$之间了

阅读题解

官方题解说的分治思想确实很不错，从 n 开始，从后往前看，每次对指数向下取整，指数为偶数和奇数分两种结果，也很不错，而且优势在于这种方式可以递归！

第二种方法绝了，如果不是对二进制非常熟悉，恐怕很难发现这种规律。

53 同剑指offer42.连续子数组的最大和 - 动态规划、分治法

输入：数组（全为整数，有正负，不会超过10000个数字，绝对值不会大于100）

输出：最大子序列和

要求：子序列如果包含2个及以上数字，必须连续；可以是原数组中的任何片段

假设移动到数组中的第n个数字，此时满足条件的最大和是 f(n)，应该解释为：前n个数字中满足题干条件的最大序列和是f(n)

我怎么知道现在是不是连续的？

假设有某个连续序列比较大，是当前最大，那么后续数组是加还是减，是从后往前进行计算吗？

那么当新的 n+1 加入后，首先要看当前数 i 是正的还是负的

• 如果是负的，只需要比较和 f(n) 的大小就好了，不可能让 f(n) 更大， f(n+1)=max(f(n), i)
• 如果是正的，那么有可能让 f(n+1) 更大
  • 一方面是比较 f(n) 和 f(n+1)
  • 另一方面，从当前值 i 从后往前加各个数字，观察和能不能超过 f(n)
    • 但是这样会导致复杂度比较高，大概是 $O(n^2)$ ==要求$O(n)$==
    • 怎么样进行更加方便的判断呢？

我印象中前面有一个很类似的问题

有一种方法是从中间断开然后进行两段计算的方法

没错，是很类似前面的“买卖股票的最佳时机问题”，不过不一样的地方是，要把中间的数字也加上，而不是只计算头尾

前面做过的两道题都没有很好地进行学习

关键问题是一个数组是否吸收下一个数字不止取决于下一个数字，而是取决于下一个数字之后的一个连续序列是不是能够对当前序列进行增加。

这里本来是剑指offer42，结果和53题相同

！！！应该说53题当时没有好好学习

==这里注意 f(i) 的解释：表示以第 i 个数字结尾的连续子数组的最大和==

那么 $f(i+1) = max(f(i)+a_i, a_i)$ 就非常正确了，就不用再考虑从后往前加那么多了！

这道题的第二种方法是分治，其实是本题的深化：求序列的 [l, r] 区间内的最大连续子段和

贪心法

376. 摆动序列 - 动态规划、贪心法

输入：一个数组

输出：最长子数组的长度

要求：子数值后一项减前一项的差值必须是一正一反交替的；只有一个元素，或者只有两个元素的也算。

怎么样检测差值是不是交替？可以用乘法，差值乘积小于0，那么就是了

但是怎么样获得最长数组？

个人觉得还是一个动态规划的问题，题解标题来看也有说是贪心法的，如果用动态规划来说，最大问题是不一定后面的元素和前面的元素存在关系

思路：

比方说先计算一遍差值，形成一个新的数组，然后选择正负交替，最后差值数量 + 1 就是最后的结果吗

连续的正数，或者连续的负数都不会增加差值的数量，只有出现改变才增加一次

如果用一个数组记录新数组，那么这个空间占用率会很高，最好是一个循环直接带走，也是需要两个量来进行交替取值

• 新问题：如果差值为0，那么也是不能算的
• 另外：如果出现一个差值为0， 那么不能继续乘以它了，这样后面就无效了

==重新整理思路：==

• 第一个数，索引0，结果直接加1，不会比1小

• 从第2个数（索引1）开始，如果其和前一个数的差值 * 索引1与索引0的差值 < 0 ，那么结果就要加1了

• 如果差值为0，那么又不能使用这一个差值

• 所以就是，计算差值

  • 如果差值为0自然是不加不减

    • ==而且不能改变前一个趋势值 s1==

  • 如果前面差值为负数，当前为正，或者前面差值为正数，当前为负，则会加1

  • 如果前面差值为0呢？

    • 按照上面的说法，其实只有一种可能前面的趋势值 s1 为0，那就是从开头以来，s1就是0，而且还没有变过
    • 一旦 s2不是0，一定会把 s1变化一次的

其实我的方法是贪心法的思路！！

• 但是问题是我没有很好地==处理 0 的问题==，如果不能用乘法一劳永逸地解决，不妨直接==用不等号进行尝试==！
• 而且，也不要最后再加1，这样针对【0，0】这样的数组就会多加一次，应该在最开始就加到位，后面就是不停地补充就好了

阅读题解

摆动序列官方题解

峰谷思想：

• 两侧均小为峰，两侧均大为谷，非峰非谷为过渡
• 两端元素只有一侧，小为谷，大为峰
• 最后一个元素上升趋势，则为上升摆动序列，下降趋势则为下降摆动序列

状态表达式

状态转移规则（方程）

初始条件

动态规划思路：

状态表达

• 以当前元素结尾的序列中，最长上升摆动序列为 up[i]，最长下降摆动序列为 down[i]

状态转移规则

• 针对 up[i]
  • 当前元素小于上一个元素（包括等于），那么最长上升摆动序列不变
  • 当前元素大于上一个元素，那么既可以从 up[i-1]转移，也可以从 down[i-1]转移
• 针对 down[i]
  • 当前元素大于上一个元素（包括等于），那么最长下降摆动序列不变
  • 当前元素小于上一个元素，那么可以从 up[i-1]转移，也可以从 down[i-1]转移

最后的答案也是从 up[n-1] 和 down[i-1]中选择比较大的那个

135. 分发糖果 - 贪心法

这道题有一点像华为今年的题

输入：一个整数序列

输出：重建序列和

要求：对输入序列，对比相邻元素

• 如果元素比较大，重建序列中该值位置的数字应当+1
• 元素相等，不用+1，直接给1

当前元素有几颗糖完全取决于前面一个的糖？

• [0, 2, 1]，第三个数字介于前两个数字之间，如果0给1，2给2，那么1给1，完全没问题
• [2, 2, 1]，2给1，2给1，但是后一个是1，至少给1，所以第2个2不能为1

我的想法：

到第 i 个数字，首先给 1

从前往后的序列是相对比较容易的，直接对比，然后加就可以了

从后往前的序列是比较难的，需要对前面的序列一个一个对比大小和调整，直到遇到比较小的数字

如果一个序列就按照从大到小降序排列呢？那就要处理很多，复杂度就高了，这样显然不是太好

官方题解

其实刚才的想法中暗含了本问题的额正确解决思路：==就是需要反过来进行计算==，其实两个递减序列肯定是互不相关的，那么直接反过来再计算一遍不就好了？

总体想法：正着一遍，反着一遍

注意一个问题：

• 正着一遍，我们需要得到新的序列
• 反着一遍，其实序列本身并不是我们需要的，数字的和才是我们需要的

range(n-1, -1, -1)，从 n-1 一直到 0

官方题解中的 ret += max(left[i], right) 一句点明了两点：

（1）每一次循环其实决定的是新序列右侧值

（2）反向序列满足规律时才会修改，如果不满足规律那么right会是1，也就不怎么改变了

总结：贪心法，两遍扫描，已有相关题解

其他

118. 杨辉三角 - 基础

输入：非负整数 n

输出：杨辉三角的前 n 行

理论上可以硬解

特点：

• 每一行首尾都是1，其他数字i是上一行第i个和第i-1个数字的加和
• 第 i 行 i 个数字

按我自己的方法，主要是会有三种特殊情况：

（1）n=0，那么返回是空

（2）n=1，那么返回是[[1]]

（3）n=2，那么返回是[[1],[1,1]]

只有从n=3开始，才建立起递推关系

---

OK！本期10题就先到这里了，应该说在这段期间对代码的理解有了提高，但是对知识的巩固一如既往地糟糕，需要经常复习。

期待下一个10题快点到来！