好几天没有写题解了，为什么没有写呢？就是我觉得好像这道题没有什么意义：比如，这道题，极其繁琐，没什么巧思；或者，这道题，根本就是脑筋急转弯，想得出来就无比轻易，想不出来就误入歧途，功底无用。
这种状态就是极其危险的状态，所谓的高不成、低不就。非要等一道完美的题目出现，才去认真学习和分析么？这是心飘了。要警惕，深刻地警惕。每道题，都要认真对待，尽量读懂，自己做出来了，要跟别人的做法去比较，自己做不出来，要看懂别人的做法，不能轻视一道题目。
自勉结束，看看今天的打卡题。题目要求是按照顺时针螺旋顺序，打印一个给定的 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
19class 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
2
3
4
5
6
7
8
9class 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
34class 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
34class 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
30class 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
18class 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 避免无畏地搜索。
从 Git 出来，到我逐渐用上，过去了多年，我搜了一下，这个博客上竟然写了很多关于 Git 的文章，于是我打算做个合集，把关于 Git 的内容汇总一下，便于大家查看。
Git 有个功能，可以对每次的 commit 进行签名防伪，GitHub 上会为这样的 commit 展示一个 Verified 标签，这篇文章介绍了，如何在本地配置 GPG key，并配置 git 来实现给每一个 commit 签名。
介绍了我对代码版本控制过程中，分支的理解，也谈及了一些 Git 分支的优势和用法。
Git 文档和书籍里面多次出现了 staging area 这个属于，而 git 的命令行参数里也有 index 和 cache 的字样，如果不弄清楚这三个概念的意思，就始终觉得模模糊糊的心里不通透，于是我在网上各种搜，找到了这几个概念的缘由，记录在这篇文章里面。
这篇文章介绍了我爱 git 的几个理由。在 git 早期的时候，还是有不少人没有切换过来的。现在基本已经全民 git 了。可能这篇文章就不那么有意义了。
在 git 出现早期，各个大公司还没有跟进，还在普遍选用 SVN，而整个程序员群体，也还没能熟练使用 git，而 git 本身也不像现在那么完善，对应的工具链也好，研发管理流程也好，都还不成熟，那个时候，我更推荐小团队或者创业公司选用 SVN，因为有更少的管理成本而人员摩擦，小团队找不到高素质的人，SVN 的多年成熟，市场上的程序员普遍会用。不过，中文互联网圈的人看了我的文章，说我在一本正经地胡说八道。其实你一个人开发，爱用什么用什么，当你组织团队生产的时候，你不得不降低自己的标准，因为不可能所有人都有相同的理解力和执行力啊。
遇到这个问题是因为我们的研发流水线使用一个图形化界面的上线系统。这个系统每次需要用下拉列表展示待上线的 tag，我们是用 tag 管理线上版本的。结果因为天长日久积累了太多的 tag，导致这个下拉列表渲染极其缓慢。Gitlab 的 tag 页面也都展示不正常了，不得不去删除一些 tag 来解决问题。
这篇文章用文字描述了 Git 代码提交的过程，以及在 Git 里提交代码时候的一些概念。此外，还对比了 Git 与 SVN 的不同。
使用文字介绍了使用 Git 时候，你将会接触到了第一个命令 clone 的一些用法和解释。并且把 clone 与 SVN 的 checkout 命令进行了比较，分析了两者的异同，帮助读者理解这个 git 特有的概念。
本文是对版本控制工具 Git 的简介。
本文介绍了在 Git 中，怎么回滚变更。因为在 Git 中，代码所处的状态有很多种，所以，从每种状态中，回滚代码的操作都不一样。更为关键的是，理解每种状态的原理和设置原因，才能用正确的命令去回滚它们。
介绍了一个基础操作，怎么撤销本地的更改。
尝试从 0 开始介绍 Git 版本控制系统的使用，似乎当时想写一本介绍 Git 的书来着，然而，并没有坚持下去，就也放在这里吧。这篇精华帖子看，我还是写了很多内容的，凑齐来也差不多够本小书了。
直击灵魂的根本性问题，我们到底为什么需要版本控制系统？VCS，被发明出来的根本原因，我们为什么需要保持代码的多个版本？因为长久以来这就是一个毫无疑问要遵守的惯例，以至于我们根本想不起来是什么原因了。这个篇文章为您解惑。
今天的题目是矩阵的转置。题目懒得抄了，帖个图吧。
矩阵转置示意图
其实，例子里这个图给得不是很好的，因为这正好是一个特殊的矩阵，叫方阵，行和列是一样多的，实际上，我们遇到的矩阵未必是方形的。
其实矩阵转置根据直觉做就可以了，没什么难点。核心就一句话：
result[j][i] = matrix[i][j]
什么意思呢？就是把某个元素的二维下标两个下标交换一下位置。所以，我写了下面这样的代码：1
2
3
4
5
6
7
8
9
10
11
12
13class Solution:
def transpose(self, matrix: List[List[int]]) -> List[List[int]]:
m = len( matrix )
n = len( matrix[0] )
result = []
for i in range( n ):
result.append( [0] * m )
for i in range( m ):
for j in range( n ):
result[j][i] = matrix[i][j]
return result
先测量长度，然后生成结果矩阵，然后逐一遍历，然后交换下标。打完收工。时间复杂度是 O(m・n)。
给定一个排序数组，要求把重复项删掉，然后返回新的去重数组的长度。要求空间复杂度 O(1)，其实发现一个重复的，就把后面的挪上来。这个题目直觉上就没有什么特殊的，硬做：1
2
3
4
5
6
7
8
9
10
11
12
13class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
l = len(nums)
if l == 0 or l == 1:
return l
r = 0
p = r + 1
while p < l:
if nums[p] != nums[r]:
nums[r+1] = nums[p]
r += 1
p += 1
return r + 1
我写出了这样的方法，就是第一个指针指着开始位置，第二个指针指后面一个，然后往后挪第二个指针，如果遇到不重复的，就拷贝到第一个指针后面一个位置，遇到重复的就一直往后挪第二个指针。
提交后，这个算法通过了。看了题解，这个方法叫双指针。前面一个叫慢指针，后面一个叫快指针。
知识点：
这是一道打卡题，没想到难度是“困难”，每次看到红色的“困难”，我还是菊花一紧的，感觉很多脑细胞要死亡了。
题目规则很简单，就是大信封能套小信封，然后，问最多能套多少层。信封用 [w, h] 来标记宽度和长度。比如在宽度和长度都更大的前提下才能套入。
因为有两个维度，就显得有些复杂，我的第一个直觉就是排序。至少先按照其中一个维度比如宽度，进行排序。完事后，对长度开始穷举。穷举自然就是回溯法：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23class Solution:
def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
self.envelopes = sorted(envelopes, key = lambda x : x[0])
self.l = len(envelopes)
if self.l < 2:
return self.l
self.visited = [0] * self.l
self.max_env = 0
self.dfs(0, 0, 0)
return self.max_env
def dfs(self, start: int, maxW: int, maxH: int):
if start == self.l:
self.max_env = max(self.max_env, sum(self.visited))
else:
for i in range(start, self.l):
env = self.envelopes[i]
if env[0] <= maxW or env[1] <= maxH:
continue
self.visited[i] = 1
self.dfs(i + 1, env[0], env[1])
self.visited[i] = 0
self.max_env = max(self.max_env, sum(self.visited))
我写出了这样的代码，回溯的时候，用一个状态组记住一个信封有没有被套入，用 maxW 和 maxH 记录套到此时此刻，最大的 (w, h) 是多少，这样好判断下一个能不能套。因为要严格递增，w 又是有序的，那么我们可以把那些 w 相等的信封跳过，相当于剪枝了。所有信封都检查过，或者后面已经没有任何满足条件的信封时，就搜索到了结局，visited 里用到的信封总数，就是最长值。
第一个信封选择，理论上有 N 种，而第二个信封选择，理论上有 N - 1 种。只有 w 值相等时候才能剪枝。这就看出来，上面的算法，时间复杂度是 O( n! )。果然是无法 AC 的，超出了时间限制。
我的智慧估计就到这里了，能写出来不错了，还没有能力想到更短的算法。然后看了官方解法。我们设想，w 有序后，我们彻底摒弃 w 这个维度的影响，单纯看 h 这个维度的影响，应该怎么做呢？其实就是求剩下 h 的序列里，最长严格递增子序列。但是，这里其实有个问题，就是如果在 w 值相等的情况下，h 的最长严格递增子序列长度是错的。解决方法也很简单，在 w 相等的时候，h 按降序排列，就好了，这样就无法形成严格递增子序列了，只能在 w 不同的情况下增加子序列长度。
到了这一步，就可以设计一个动态规划的算法，其实，这里也是递推法。状态怎么转换的呢？第 i 个状态，就是前 i 个数构成的最长严格递增子序列长度。这时候，新来的第 i + 1 个数，就要去和前 i 个数里的每个数去比，如果更大，就能得到一个比当前这个状态长 1 的子序列，这里最大的一个，就是第 i + 1 个状态的值。太绕了，举个例子：
对于一个序列 6, 5, 1, 2，第 1 个状态是 1，一个数字的子串长度只能是 1，第 2 个状态是 1，因为 5 比 6 小，所以这两个数字构成的最长递增子串长度还是 1，以此类推，第 3 个还是 1，第 4 个是 2，因为 2 比 1 大，所以可以构成一个 2 个数字的递增子串，此时的状态数组就是 1，1，1，2。设想，现在下一个数字是 7。7 比 6 大，所以能构成 2 个数字的递增子串，对于后续的 5 和 1 来说也是如此，但是对于 2 来说，之前 2 已经可以构成一个长度为 2 的子串了，这时候来了 7 就能得到 3 个数字的最长子串了，所以下一个状态的值是 3。扫描到 7 的时候，状态数组变成了：1，1，1，2，3。基于这个原理：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
26class Solution:
def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
self.l = len(envelopes)
if self.l < 2:
return self.l
def cmp(x, y):
if x[0] < y[0]:
return -1
elif x[0] > y[0]:
return 1
else:
if x[1] < y[1]:
return 1
elif x[1] > y[1]:
return -1
else:
return 0
self.envelopes = sorted(envelopes, key = functools.cmp_to_key(cmp))
dp = [1] * self.l
for i in range(self.l):
for j in range(i):
if self.envelopes[j][1] < self.envelopes[i][1]:
dp[i] = max(dp[i], dp[j] + 1)
return max(dp)
忽略上面乱七八糟的 cmp 函数，就是为了排序而已。关注 21 - 25 行。就是上面说的推导下一个状态的过程。这里算法，我们可以看到，每扩展一个新状态，需要扫描前面 n - 1 个状态。所以，时间复杂度是 O( n^2 )，这比起 O( n! ) 已经好了很多了。然而，悲摧的是，仍然不能 AC，还是超时，我看了这次超时的用例，更长了～
这个递推法比回溯法优秀到哪里了呢？其实在回溯法里，每出现一个子串，我们不但计算出了子串的长度，还计算出了子串的排列。visited 数组就给出了哪几个信封够成了该子串。而这本是没必要算出来的。在递推法里，我们只关心能构成的子串中长度最大的那个的长度是多少，其他都不关心了。所以节省了很多。
再来看最后一个解法，官方解法的说明，说实在的太抽象了，都是用的代数，我看不懂。我自己想了个。我们朴素来想想，如果我们想要套得更多层，到底怎么挑选信封比较有效呢？比如第一个信封是 (w:1, h:1)，这时候第二个信封有两个选择(w:2, h:5)和 (w:2, h:2)，你选哪个呢？不傻的话，都会选后者吧，因为 h 更小，意味着将来可以被下一个信封套进去的概率更大。
这个新的动态规划算法，状态这样设计的，假如，我想组成一个层数为 i 的套娃，那么用到的最小的那个信封高度，记为第 i 个状态值。注意这个算法仍然建立在 w 已经是升序，而 h 是降序的基础上。这时候，新来一个信封。如果它的高度，比 i 大，那只能套在 i 的外面，其高度变成第 i + 1 个状态。如果其高度比 i 小的时候呢？注意我们的策略，组成一个套娃的时候，尽可能选满足条件最小的一个信封，将来套入新信封的概率才会变大。所以，如果其高度比 i 小的话，理论上我们应该把第 i 个状态的值调小，也即没有扩展新状态。不过，我们真应该更新第 i 个么？如果前面还有比这个值大的呢？那这个肯定是套不上去的，所以得往前找一个位置，正好是前一个状态比它小，后一个状态比它大，然后把比它大的那个给更新了。这个位置可以用 二分查找 来搜索。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17class Solution:
def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
if not envelopes:
return 0
n = len(envelopes)
envelopes.sort(key=lambda x: (x[0], -x[1]))
f = [envelopes[0][1]]
for i in range(1, n):
if (num := envelopes[i][1]) > f[-1]:
f.append(num)
else:
index = bisect.bisect_left(f, num)
f[index] = num
return len(f)
于是，我们得到了这个算法，这是我抄的，不是我自己手撸的。我们可以看看这个算法的复杂度是什么，排序是 O( n logn )，二分查找是 O( logn )，所以动态规划的过程，复杂度还是 O( n logn )，总的时间复杂度是 O( n logn )。比上一个算法又进步了。
那么这个算法到底节省了什么东西呢？上一个算法里，出现了 i 个数字的时候，我们记录了每个数字能组成最长子序列长度。还拿那个 6, 5, 1, 2 来举例，其状态数组是：1, 1, 1, 2。这里我们看到，6，5，1 三个数字，其能形成的最长子序列都是 1，被记录了 3 次。其实，6 和 5 如果能跟后续新出现的数字，比如 7 ，组成更长子序列的话，1 也一样可以，因为 1 更小，适应性更强。在新算法里，我们就把 6，5 的状态值，都给抛弃了，只保留了 1。这样，如果新出现一个数字的时候，显然我们需要遍历的状态就更少了。于是将 O( n^2 ) 节省到了 O( n logn )，终于 AC 了。
问题总结：
第一，我对 Python 的排序还是太不熟悉了，查了文档，还是写出了那么 Ugly 的排序，其实 List 自己就有 sort 方法，而且，对于 List 是有默认多级排序的，不用自己写 Comparator，尤其我还不熟悉 Python3 怎么利用 Comparator；
第二，才知道，还有个类库 biset，可以直接二分查找，比如这个题的考点不是写二分，完全可以直接用现成算法，来集中注意力研究场景。
题目简述一下，就是给定两个升序有序链表，然后合并它们。
昨天看到这个题目，我的大脑一片空白，其实这个题目没什么难的，就是单纯地考察对一个数据结构链表的掌握程度，单链表。
太久没有写了，真的写不出，我就看了答案，意思我是完全知道的，但是就是写不出：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
result = ListNode(-1)
point = result
while l1 and l2:
if l1.val <= l2.val:
point.next = l1
l1 = l1.next
else:
point.next = l2
l2 = l2.next
point = point.next
point.next = l1 if l1 is not None else l2
return result.next
以上是看完答案默写的，首先是声明两个新的指针，一个指向最后结果的链表头，另一个是用作游标，然后就是迭代，注意看里面 next 也是一个指针，也利用到了。
这个题目还可以写出其递归算法，其具有的递归结构是这样的，在给定的两个链表里，找到一个最小的节点后，去掉这个节点，剩下的问题跟原理的问题是一致的，递归调用原来的解法就可以了。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
if not l1:
return l2
if not l2:
return l1
result = ListNode(-1)
if l1.val <= l2.val:
result.next = l1
l1.next = self.mergeTwoLists(l1.next, l2)
else:
result.next = l2
l2.next = self.mergeTwoLists(l1, l2.next)
return result.next
先找到最小的节点，然后，把剩下的递归解决。写完看了下，发现 result 是完全多余的，去掉也可以。就跟官方给的题解一样了。
知识点：
