Leetcode解题报告

寒假没事情,在家里刷Leetcode。这里放的是LeetCode解题报告【更新中】,代码在GitHub上,有些被坑的题目会专门写一篇post。
必须先对Leetcode吐个槽,这复杂度卡的真是魔幻,同样的复杂度C++能过,Python就不能过,而且都是卡在最后两三个样例上(不会就最后两三个大数据吧?)
Leetcode上面有题解,不过有时候很奇怪他们算复杂度的时候会强行令某些操作,比如判断字符串是否相等(Problem 14),std::map查找元素(Problem 1)的复杂度为1,感觉这并不是很严谨的,后来在Google Codejam/Kickstart的官方题解上也看到类似的算法,只能说这是一种计算方式吧。
在刷Leetcode的时候,取得Accepted通常是容易的,但是如果能够翻翻Submissions里面速度靠前的答案,看看人家是怎么在同复杂度下进行常数优化也是很有必要的。

1. Two Sum

$O(n^2)$要T的,正解对任意的i,判断target - i是否在集合s中,如果不在,把i加到集合s中。注意因为Python中dict用散列表实现,所以查询复杂是$O(1)$的,这和C++中的std::map(RBT实现)不一样。
另外考虑如果给定数列是有序的,还可以使用二指针来做。测试了一下,如果对这道题先sort一下,居然速度要快十倍。

2. Add Two Numbers

链表比较麻烦,注意在两个链表全部遍历完毕后检查是否还有进位

3. Longest Substring Without Repeating Characters

计算最长不重复子串
从头开始遍历字符串S,记录字符S[i]出现位置到ex中。若ex[S[i]]已存在,即字符S[i]ex[S[i]](前出现)和i(后出现)出现过,这时候我们的最长长度便不能继续增长了,尝试用字符串S[start, i - 1]来更新最长字符串,并令start = ex[S[i]] + 1,即从S[i]前出现的下一个位置开始重新计算最长长度。这时相当于把字符S[i]从前出现移到了后出现,因此ex[S[i]]需要被更新到当前的i
有个注意点,在更新start的过程中,我们实际上重复利用了[ex[S[i]] + 1, i]这段肯定不重复的序列,包括它们的ex值,但同时我们也舍弃了[start(原), ex[S[i]]]这区间,因此在下面的遍历过程中如果字符ch对应的ex[ch]值出现在这段区间中,那实际上应该等同于它未出现处理。

4. Median of Two Sorted Arrays

文章

5. Longest Palindromic Substring

马拉车算法模板题

6. ZigZag Conversion

对模numRows * 2 - 2讨论

7. Reverse Integer

python转成string在转回int强行干

8. String to Integer (atoi)

看图说话题

9. Palindrome Number

通过整除和取余算出倒过来的数,比较和原来的数是否相等

10. Regular Expression Matching

编译原理复习题,撸个DFA。这里注意一下对.规则的处理,虽然NFA比DFA多了ε规则,但是NFA对于一个某个输入符号的下一个状态是确定的。而对于.*c这样的规则,如果读取到c,那么可以仍然在本状态,也可以通过c到下一个状态,因此是冲突的,要向前看一个字符。在本题中因为字母表就在[a-z]上,于是添加26条规则就可以了。
实际上可以DP搞

11. Container With Most Water

WA了n次,原来是和HDU1506直方图中最大的矩形面积搞混掉了,这个不要求连续。
不会O(n)算法,看了答案发现也是DP。主要原理是对于令i, j分别为数组的左右边界,显然这样的容器最宽。把i, j相对移动,要想还比它容积大,就要比它高。于是对于任意的ii, jj,如果height[ii] <= height[i]height[jj] <= height[j]那就不行了。注意不是height[i + 1] < height[i],这样遇到两个都不满足的情况就死循环了。

14. Longest Common Prefix

看名字想到后缀数组,然而并不是。直接O(nm)暴力就可以了,也可以用二分,还不如直接暴力

15. 3Sum

乍一看以为是01背包,然而并不是,看题目应该是和第一条类似,暴力就行了。于是照搬第一条撸了个$O(n^2)$的交上去,居然T了,看了一下T在倒数第二个点,卧槽还卡常啊。
查看题解,把对j的循环和仿照2Sum的使用dictk去掉改成双指针夹逼法。这个方法在于遍历每个i,然后对剩下的两个数jkj = i + 1k = n - 1开始相向搜索。
不过这次还是还是超时,根据这里的解释:But according to my submissions, this way will cause you double your time consuming almostly.,可能是我取unique拖慢了(然而排序后求unique是O(n)的啊)
放一张图

16. 3Sum Closest

这k-Sum的题目没完没了了。这道题也是先排序,然后双指针,同时维护一个best表示最优解

17. Letter Combinations of a Phone Number

直接暴力模

18. 4Sum

先放这儿吧。。

19. Remove Nth Node From End of List

链表的基本操作,维护[before, begin, end]三个指针即可,注意head被删除的情况。

20. Valid Parentheses

开一个栈维护就行了,注意pop的时候要先判断是不是空栈

21. Merge Two Sorted Lists

归并两个数列,手残忘了cur = cur.next,然后又RE了,原来是注释的预定义部分自己不要附上去

22. Generate Parentheses

卡塔兰数C(n)也表示所有在n*n格点中不越过对角线的单调路径的个数,所以直接递归搜索就全部能列出来。

23. Merge k Sorted Lists

一开始是硬上21条的解法,结果T了。假设n个列表中总共有p个元素,那么外层的while循环一次添加一个元素,共O(p)次,内层的for循环是一趟n次。这种算法复杂度上限是O(p*n)
Leetcode上的top解法是(C++)调用n-1次的MergeTwoList,归并一次的复杂度是两个列表长度之和,所以这种复杂度上限依然是O(p*n)。以上两种做法Python全被卡常卡掉了(而且卡在最有一个样例,那你告诉我为啥你不也把C++卡掉)。

正解是二分分治对这kList归并,这样可以优化到O(p*logn)的复杂度。
另外也有大佬直接上堆排了,我也是服

24. Swap Nodes in Pairs

又是链表题,直接记录[before, begin, end]交换就行了。标算是递归,我用的迭代,迭代在更新end时要注意beginNone的情况

25. Reverse Nodes in k-Group

链表逆置问题

26. Remove Duplicates from Sorted Array

两个指针,i用来遍历,j用来维护插入位置即可,注意到i始终是要比j快的,所以不会产生覆盖的问题

27. Remove Element

同26

29. Divide Two Integers

不使用乘除和模实现整数除法,这里也不使用加减法

使用位运算实现整数加减法

两个比特$x (b)$和$y (b)$相加,结果需要两个比特来盛放,可能为$00 (b)$、$01 (b)$、$10 (b)$。注意到高位的比特值为$x \, and \, y$的结果,而低位的比特值为$x \, xor \, y$的结果,于是整个结果是$(x \, xor \, y) \, or \, (x \, and \, y)$

减去一个数等于加上这个数的补码

使用加减运算实现整数除法

这里需要使用快速幂的思想,减去小于被减数$a$的尽可能大的$b \times 2^n$。这里注意的是Python中的Integer是没有范围的,所以不能使用补码等运算,对于溢出的情况也要专门判断。

1
return min(max(-2147483648, res), 2147483647)

31. Next Permutation

在我的某篇文章里讲过直接求nth perm的做法
这道题目首先是找规律,还是挺有意思的。我们从倒数第二个数开始倒序取i,不断尝试把nums[i]与其后面满足nums[j] > nums[i]的最小的nums[j]交换。实际上我们要一个在尾部的最长的下降序列[i-1, end)。我们应当从尾到头找,因为i位置后数列一定是降序的,否则i + 1位置时算法就应当结束了。交换完后,我们将i位置后的序列片段按升序排列好(这时候该片段是最小的)便得到了最终答案。如果没有的话我们令i--继续循环。

此外,Python2里面的list切片是返回的一个新list而不是引用,写代码的时候被坑了次。

32. Longest Valid Parentheses

好像17年哪个公司的笔试题里面出现过这一条的。
简单的思考了下,这条是DP。我们令dp[i]表示字符串在i位置最长括号串的左边界,初始化为dp = range(i)。因此对于每一个s[i] = ')',我们从j = i - 1开始根据dp[j]往前跳转,直到dp[j] == j,此时我们看s[j]是否为'('即可。注意最后还要根据dp算一个ans,否则()()这种情况就是2而不是4了。
写的时候很粗心,WA了n次。

33. Search in Rotated Sorted Array

先二分一次找到第一个比arr[0]小的点,也就是唯一一个下降点,以此点将串一分为二,对两边数组分别进行二分

34. Search for a Range

同样是二分两次,第一次找到最左边边界,第二次找到最右边边界

35. Search Insert Position

简单的二分

37. Sudoku Solver

使用回朔法求解,代码修改自我的github
在修改代码时类back_solver方法和里面的solve_iter在返回结果res时出现了为None的问题,后通过改为self.res解决。

39. Combination Sum

dfs即可

40. Combination Sum II

解法类似,这次每个数只能使用若干次

41. First Missing Positive

在一个无序列表中找第一个没有出现的正整数。
这是一个很有意思的桶排序的题目。遍历数组,使用$h(x) = x - 1$将值为$x$($0 < x < length$)的数与$x - 1$位置上的数进行交换,这样经过$O(n)$后数组便会变成有序的。

42. Trapping Rain Water

看上去类似于第11题。
首先先想naive的$n^2$解法,对于每一个位置i,分别寻找其左右侧最高的柱子l[i]r[i],那么i处水柱的“海拔”是min(l[i], r[i])。显然我们发现寻找左右侧最高的柱子这个过程可以DP。
下面使用HDU1506直方图中最大的矩形面积的方法进行dp优化。其原理是如果j+1处水柱比j处的高,那么它肯定比r[j+1]处水柱高。

44. Wildcard Matching

类似第10题,可以通过DFA来做。这里使用DP来做

45. Jump Game II

青蛙跳,不禁想起悲惨的LCM Walk推公式题。
记到i点的最少步数是l[i],这条naive的方法自然是对于每一个i,用它来尝试更新自己的跳跃距离范围[i, i + nums[i]]内的所有的l[j],但这样会超时。
查看题解,实际上这是一个贪心问题,我们使用l记录跳s步达到的最远距离,这说明数组整个[0..l]片段至多s便能到达。使用r记录跳s + 1步达到的最远距离,显然r > l
下面我们对于每一个i,查看它需要用几步才能到达,期间需要同步更新lr

  1. 正常情况
    如果说i小于等于l,这说明i肯定是能够在s步内达到的。
    下面我们要尝试更新ri位置能够达到的最远范围是nums[i] + i,这说明如果我们在s + 1选择在i位置跳,那么能够覆盖[i, i + nums[i]]这段距离。因为i < l,所以在i位置跳能够覆盖[0, i + nums[i]]这段距离,我们用它和r取大值来更新r,如果需要记录起跳点p[s + 1],这时候也应当同时使用i比较更新。

  2. 额外情况
    如果i大于l,即跳s肯定不能达到了,就必须多跳一步了,此时总步数变为s + 1
    这种情况是可能发生的,虽然我们遍历i是一次一格,跳是一次若干格,但遍历到i时可能已跳次数s远少于i
    我们来看看跳完这s + 1步后能够达到的最远距离是什么呢?答案是i - 1位置时的范围[0, r],起跳点p[s + 1]在小于等于i - 1的某处。如果r < i的话,那么终点便是不可达的,但题目中保证了终点可达。所以我们用r来更新l
    接下来,i小于等于l,我们按照正常情况继续处理。

46. Permutations

47. Permutations II

我这里使用了字典来维护重复的数,在Leetcode里面我看到了一个较为巧妙的处理重复的方法

1
2
3
4
for(int i=0;i<nums.length;i++){
if(used[i]) continue;
// 在同一个循环里面,如果i位置的值和i-1位置的值相同,而i-1位置的数没有被使用,那么i位置肯定也不会被使用
if(i>0 && nums[i-1]==nums[i] && !used[i-1]) continue;

48. Rotate Image

这让人联想到$O(1)$空间转置矩阵的题目,但本题是顺时针旋转而不是转置。
由旋转公式得$ \begin{bmatrix} x \\ y \end{bmatrix} $变成$ \begin{bmatrix} y \\ -x \end{bmatrix} $。如果把这个变换看成两个变换的组合,第一个是关于次对角线的对折,第二个是关于横轴的对折,那么代码会更容易写,因为不要想inplace矩阵转置一样需要考虑一个链的问题了。
这里注意一下python的列表生成器可以使用两个循环变量,如[(x, y) for x in xrange(m) for y in xrange(m - x)],但注意x一定要在使用前有定义。
本题也可以使用矩阵转置的方法来做。以3行3列的矩阵为例,将其按行展开为一维数组。得到三条变换链:0-2-8-6-0、1-5-7-3-1、4-4。容易发现对于每个链,我们用前一个位置的值给后一个位置赋值即可,如2号位的新值为0号位的旧值。不过我们还要防止重复遍历链,例如我们首先以0号位为链头遍历完第一条链,以1号位为链头遍历完第二条链,但是位置2已经在第一条链中遍历过了。为了解决这个问题,我们在位置i处要确定是否要以这个位置作为新链的链头,例如我们以2位链头开始遍历,发现在2-8-6-0-2的序列中出现了位置0是小于2的,这种情况是不可能的。容易发现每条链的链头都是这条链中位置号最小的元素,这是因为我们是从0开始按顺序以每个位置作为链头的。

49. Group Anagrams

Anagrams指的是将原单词或短语字母打乱顺序,形成新的单词或短语,如“Tom Marvolo Riddle”变成“I am Lord Voldemort”
这道题将单词的每个字母sort作为key,然后用dict记录每个key拥有的所有单词,最后遍历输出即可。

50. Pow(x, n)

快速幂模板题

51. N-Queens

Submission里面看到有人用位运算(因为Python里面int无限大所以都不需要bitset)来搞的

52. N-Queens II

受上题影响这次用位运算搞一波
首先同样是按行搜索,每一行尝试放一枚棋子,递归深度$O(n)$。

53. Maximum Subarray

这是一个经典的动态规划问题。由于在每一点i都可以选择继续延伸之前的串(其和为acc)或者打断重新开始。明显当acc + nums[i] >= 0时保留之前的串是有增益的,否则就打断重来。使用m维护历史上最长的串的长度。

54. Spiral Matrix

这条题目我思路不够清晰,主要是找规律发现数列+(n-1), +(m-1), -(n-1), -(m-2), +(n-2), -(m-3), -(n-3), ...,对第0项特别处理,然后xy往下递推即可。
查看题解发现思路更便捷一点,它的想法是依次循环将最上、最右、最下、最左的行/列添加入ans数组中,每次添加完后更新指针。终止条件是上下界或者左右界溢出。
在discuss里面还看到一个骚气的Python解法,这个感觉就像我们把梨子拿在手上一边转一边削梨子一样

1
2
def spiralOrder(self, matrix):
return matrix and list(matrix.pop(0)) + self.spiralOrder(zip(*matrix)[::-1])

这里似乎在Python二维数组切片上遇到了坑,对二维数组a进行数组切片a[1:2][0]返回的是一个二维数组,而不是一维数组。

55. Jump Game

同45

56. Merge Intervals

首先是区间合并的原理,假设两个区间$(l, r)$和$(l2, r2)$,令$l2 \ge l$,则当$r \ge l2 \ge e$时区间能够合并。
因此,首先对intervals数组按照左边界大小排序,然后从头开始遍历该数组,每次试图运用上面的规则合并区间。如果不满足上面的规则,那么先前已合并了的区间就是最大的区间了,将其添加入结果数组中,并对下面的数组重新开始运用该规则。

57. Insert Interval

58. Length of Last Word

简单题,注意要strip下

59. Spiral Matrix II

60. Permutation Sequence

类似next_permulation函数,见POJ 1037这篇文章

61. Rotate List

链表题,看图说话

62. Unique Paths

m - 1个向右和n - 1个向下自由排列共有$\frac{(m + n - 2)!}{(m - 1)! (n - 1)!} $中方案

63. Unique Paths II

二维dp模板题
注意初始化二维数组时不要犯[[0] * 5] * 3的常见错误,最好用列表生成器

66. Plus One

处理一下进位即可

67. Add Binary

见29

69. Sqrt(x)

二分即可,注意取整

70. Climbing Stairs

i级可以从第i - 1级过来,也可以从第i - 2级过来

72. Edit Distance

DP是肯定的,定义数组dp[m][n]dp[i][j]表示word1[1..i]word2[1..j]的编辑距离,从1开始方便后面边界。
首先要先确定添加、删除和替换三个操作对应到状态转移上,这容易想到对于word1来说,删除i位置意味着忽略i位置对结果的dp[i][j]的影响,所以是 dp[i-1][j] + 1,其中+ 1是删除的成本。其他两个操作可依次得出。word1[i-1] == word2[j-1]dp[i][j] = dp[i-1][j-1]不能漏掉
然后还要确定递归边界,不只是dp[0][0] = 0了,也要设定dp[i][0]dp[0][j]

73. Set Matrix Zeroes

根据Follow up的要求,一个使用$O(mn)$的方法是遍历一遍matrix,然后将0的格子全部填好,最后and下
一个使用$O(m+n)$空间的方法是遍历一遍matrix,然后对每个0格子,标记其行号和列号,最后把所有的被标记行列全部置零
最好的是$O(1)$方法,把这$O(m+n)$的空间移到matrix的第0行和第0列上。注意整个过程不是迭代的,如果一个格子被设为0,它不可以再将自己所在行列设为0。特别是第0行列的清空工作一定要在最后完成。

74. Search a 2D Matrix

按行二分

75. Sort Colors

根据Follow up要求,需要一趟遍历搞定。解法如26题,这里使用三个指针,i负责遍历,l维护0值区间$[0,l)$,r维护2值区间$(r, length-1]$,注意到整个过程中$i \gt l$且$r \ge l$。使用多指针维护插入位置是一个常用的方法,在三向快速排序中也有用到。
题解给出了四种方法

76. Minimum Window Substring

感觉有点像3,不过这道题需要考虑每个字符的数量,如minWindow("a", "aa")结果是""不是"a"
这一条的思路是先找到T的匹配,然后试图移动窗口的左边界,使得匹配最小
d[ch] == cd[ch]而不是d[ch] >= cd[ch]时自增计数器,这样能够保证每个不同字符在达到规定数量时刻只会被统计一次(由于先保证有匹配,再保证匹配最小,所以每个字符数量一旦达到规定数量后就会一直保持在规定数量之上)。

77. Combinations

这条递归容易写T,不能新建list,题解使用了里面数组生成器,涉及到它的一些的性质。

78. Subsets

此题有非递归解法

1
2
3
res = [[]]
for i in nums:
res.extend([[i]+x for x in res])

此外对于C++可以借助于位运算的性质来做

1
2
3
for(int i=u; i; i=(i-1)&u){
// bit map i to array
}

84. Largest Rectangle in Histogram

HDU1506老题新做

85. Maximal Rectangle

这似乎是我做过的NUAA-HHU的一条赛题啊,典型的二维DP,不过实际上细节还是比较多的。
思路就是从左、右、左上角三个位置DP,其中左右是最优化最长的宽为1的“条”,左上角向下拓宽是要同时考虑dp[i-1][j-1]形成的矩形的左边界以及i行的左边界取大值,向右拓宽同理。
题解是借助于Largest Rectangle in Histogram的思路做的,可以参考

86. Partition List

简单题

87. Scramble String

题意是树只能建一次,然后任意换,因此统计字符数量1WA
显而易见这种变换有一个性质,如果我们选择一个分割点,我们便能够将其分为左右儿子,之后的调换顺序只会改变左右,不会影响分组,于是我们想到递归地枚举所有的分割点。
在编码过程中,还要意识到如果我们对s1枚举分割点i,那么对应到s2可以在ilen - i处分割。
这条击败的不多,常数优化有待完善。

89. Gray Code

格雷码,公式忘了,可以用三位找规律,注意格雷码是不唯一的

91. Decode Ways

觉得很好的一题,建议先写一下练习一下搜索。Corner case是特别特别地多。
这道题的正解是DP。

97. Interleaving String

暴力复杂度是$2^{min(len_1, len_2)}$,为了减到多项式复杂度,通常就是上DP,和LIS啥的一样,也是二维DP。
首先看最优子结构,显然在每一步,我们要么选择s1(从dp[i-1][j]过来),要么选择s2(从dp[i][j-1]过来)。然后还要与s3建立联系,于是我们定义dp[i][j]为最远可以达到的s3边界
交了一发,只击败了10%。。。这常数可以的,看了看题解,还有用dfs做的

98. Validate Binary Search Tree

从这题开始有一堆二叉树的题目
验证一个二叉树是否是二叉搜索树,注意二叉树需要左子树上所有的节点都小于根节点。

99. Recover Binary Search Tree

困难的地方是需要保持二叉树的原先结构

113. Path Sum II

一个基本的遍历

115. Distinct Subsequences

注意边界条件是dp[0][1..j] = 0dp[1..i][j] = 1,不能全为0。

120. Triangle

动态规划模板题

121. Best Time to Buy and Sell Stock

在扫描时维护一个当前的最小值和当前的最大利润即可(一开始还想复杂了,是Easy提醒了我)。这种方法比较常用,在求最大权子矩阵中也会用到。

122. Best Time to Buy and Sell Stock II

相比上面的题,我们可以进行任何次数的交易,但是不能engage in multiple transactions。只要知道(b-a)+(c-b)=(c-a)这道题目就很简单了,能赚就卖,不能赚就进

123. Best Time to Buy and Sell Stock III

由于不能engage in multiple transactions,首先想到的是枚举断点,将本题转成两个Best Time to Buy and Sell Stock问题。不过显然$O(n^2)$是超时的,得DP下。
所以仿照前面直方图的思路,维护一个$[0,i]$的解和一个$[i,length-1]$的解。
这条也常数也比较大,只击败了20%左右

124. Binary Tree Maximum Path Sum

说实话Leetcode的链表题和二叉树题我都不喜欢做,它的表示方法让人感觉很蛋疼,因此我写了两个辅助调试的函数,详见Github上的代码。
这道题就是两次dfs,第一个dfs是求出从某个节点往叶子方向权最长的一条链,类似于求和最大的子串一样。第二次dfs连接一个节点的两个儿子,看是否能得到一个更长的链。写的时候粗心得一腿,各种漏考虑条件。
有很大的常数优化空间,可以优化成一个dfs

125. Valid Palindrome

这个题目挺没意思的,这里Python有个方法.isalnum()

126. Word Ladder II

这道题,一看就是个bfs搜索。不过它一定要输出全部结果的全部路径,这就很麻烦。一开始写了个程序不仅T了还会M。
此外“Note that beginWord is not a transformed word”并不意味着beginWord不会在wordList里面出现。
最后还是T了,这条有点麻烦。

127. Word Ladder

128. Longest Consecutive Sequence

这条我是用反查字典+并查集实现的,不过其实可以直接用反查字典。

134. Gas Station

首先只要gas和cost的sum至少相等就可以实现,可以用归纳法证明。
其次,发现题意要求一个从唯一解起始节点i起经过所有节点的油量都大于零的性质,我们要找这个起始节点。进而可以发现从哪个节点开始找是无所谓的,因为每个节点总要经过一次。所以我们可以从例如0节点开始,在满足性质的情况下将序列向左右扩展,直到遍历玩所有的节点。一个具体的方法为首先尽可能往右移动左边界l,当l不能移动时则往左移动右边界r,直到l可以再次往右移动

135. Candy

一上来就理解错误,只有当严格大于的时候才要求糖数多,例如5 5 5 5这种,每个人可以分糖2 1 1 2(当然最优解是1 1 1 1啦)
然后就是硬写,首先将原数组分成上升段、平行段和下降段,如1 2 3 | 3 3 | 4 5 | 4 3。标记每一段的长度为segs[i],每一段最后一个人的糖果为last_candy[i]个。
上升段一定是从last_candy[i-1]+1开始以1为公差的等差数列。
下降段末项一定是1,为了尽可能小,所以是以seg[i]为首项,-1位公差的等差数列。但如果last_candy[i-1]小于等于seg[i],那整个下降数列放不下,所以此时要提升last_candy[i-1]seg[i]+1(注意只要改前一个数列的末项哦)

136. Single Number

老题新做

137. Single Number II

这道题同样可以用异或来解决(当然也可以借助于set)。在上一题中,我们通过异或的性质,实现了值相同的数两两相消。在这一题中,我们希望出现三个相同的数才相消。

1
2
3
4
5
6
ones = 0
twos = 0
for x in nums:
ones = (ones ^ x) & ~twos
twos = (twos ^ x) & ~ones
return ones

考虑一个比特位的情况。观察上面的代码,对于序列1 1 1能够得到(ones, twos)的值分别是(0, 0), (1, 0), (0, 1), (0, 0)。这里的& ~twos用来表示进位,当twos = 1时说明目前已经出现了两次,于是我们归零ones

139. Word Break

要根据字典进行分词。看起来是一个Trie的题目,题目也没规定大小写怎么说,而且也没说是否存在唯一表示。
花了很久尝试用AC自动机做,不过失败了。

141. Linked List Cycle

这种链表题一般都要考虑快慢指针的解法。
首先只可能有一个环,所以直接搞。

142. Linked List Cycle II

比上面的一题要求找到环的起始点的位置。可以发现若第一次快慢指针交于点X,则环的长度$c$等于下次快指针追上慢指针时慢指针走过的距离。
设链表头到环起点距离$s$,环起点到交点X距离$a$,交点X到环起点距离$b$,有$a + b = c$。且$2(s + k_1 \, c + a) = s + k_2 \, c + a$,有$s + a = k \, c$,即$s = kc + b$。则将两个指针分别置于链表头和交点X,其交点就是环的起始点。

145. Binary Tree Postorder Traversal

经典的二叉树后序遍历问题

146. LRU Cache

在$O(1)$复杂度下,免不了Hash。
【未完待续】

148. Sort List

写了几个辅助函数用来调试。这条就是按照CLRS上的思路写的快排,可参照第215条。居然T了

149. Max Points on a Line

这是一条神经病题目,两个相同位置的点居然算不同点。所以我是不知道它怎么解释$[[1,1],[1,1],[1,1]]$输出3,$[[84,250],[0,0],[1,0],[0,-70],[0,-70],[1,-1],[21,10],[42,90],[-42,-230]]$输出6的?所以说这些相等的点互相组成直线,但是和任何其他直线都不共线是吧、、、那你告诉我为什么TestCase31输出25而不是56。。。我最后HardCode了$[[1,1],[1,1],[1,1]]$才AC的。

151. Reverse Words in a String

这题有一点无理取闹的地方是要先将连续的空格合并成一个,然后就是一条经典的题目。原地解法是翻转每一个单词,再翻转整个字符串,代码只有很骚的一行

1
return ' '.join(map(lambda x: x[::-1], filter(lambda x: x, s.split(' '))))[::-1]

152. Maximum Product Subarray

注意这条是子串而不是子序列。这个不同于最大和,可以维护一个全局最大和当前最大来做。
Bruteforce的做法是$O(n^3)$的,遍历所有可能的数组,并累乘。一个动态规划的思路是维护$dp[i]$作为一个累乘序列,这样的话是复杂度是$O(n^2)$。注意遇到0之后可能认为当前数组结束了,0后面的作为一个新数组处理。
不过正解是$O(n)$的,相比先前的最大和,它的转移方程考虑三个分支,分别是使用前一个dp的最大值、最小值(因为存在负数翻转的现象),或不使用。

153. Find Minimum in Rotated Sorted Array

旋转数组求最小元素,这是一道经典的二分搜索题目。

160. Intersection of Two Linked Lists

找到两个链表的交点。注意一下链表的相交,在没有环的情况下一定是Y型而不是X型的,在有环的情况下那么两个链表一定最后进入同一个环。
本题是没有环的情况,容易发现将headB的链表头接到headA的尾巴后面,那么就能把本题化为第142题。
下面讨论有环的情况,首先判是否相交,根据上面的性质,我们只要找到A环上的一点,判断在不在另一个链表的环上就行了。
链表相交常被用在求普通二叉树的最近公共祖先上。

162. Find Peak Element

裸二分吧

169. Majority Element

一个很有趣的Brain teasing,要求找到出现超过floor(n / 2)次的元素

179. Largest Number

在贪心时我们需要考虑一个问题,即类似[76, 7621][76, 7698]的情况,这两种情况下最优解分别为76 76217698 76,但是考虑[7676, 76, 98][7676, 76, 54]的情况就难以处理了。但其实这种情况不会存在,因为98一定会在7676前面被去掉。
写了一份提交,发现死在了219Case上,简化一下发现[2, 213, 2281]这个样例,原因是2281还是比2大的。这个判断太麻烦了!后来发现还不如在两个字符串不相等时把两个字符串两种组合s1 + s2s2 + s1都试一下看哪个大呢。
在第321条中我们发现了类似的归并的问题。

191. Number of 1 Bits

这里使用n & (n - 1)去掉末尾的0,或者使用x & -x取到末尾的0

200. Number of Islands

一看应该就是条DFS裸题,转念一想像这种可以用搜索解决的集合分划问题也能用并查集搞。

206. Reverse Linked List

特别经典的链表反转问题,迭代方法借助prevcur指针。
题目还要求使用递归方法。

207. Course Schedule

判断一个有向图中是否存在环,拓扑排序。有关拓扑排序的内容,具体可见我的一篇博客
这边额外说一下有向图和无向图判环的方法。首先补充一下DFS的相关知识,一个无环的有向图当且仅当DFS中没有后向边,关于这个推论可以查看我的一篇博客,因此我们只要做一次DFS搜索(使用黑白灰标记),并观察是否出现后向边即可。
相对于有向图,无向图还有一些额外的判环方法。首先是并查集。

208. Implement Trie (Prefix Tree)

我先研究了Word Break那条,写了个AC自动机,没过,于是先把这条给水掉

210. Course Schedule II

看起来是个拓扑排序

215. Kth Largest Element in an Array

快排模板题,居然卡了(天哪噜,原来是两种常见写法混起来用了),既然如此就来介绍一下快速排序的两种常见方法吧。
快速排序的一种经典写法挖坑法是先取p = arr[fr]为支点元素,然后我们一定要先从arr[to]开始遍历,这么做的目的是将第一个不符合的arr[j]直接赋值给arr[fr](注意不需要交换了)。
注意一些错误的算法的实现总是不能有效地将arr[fr]移动到中间位置,所以我们必须得先把arr[fr]的槽空出来。建议在写快排时每次递归始终是在[fr, pos - 1][pos + 1, to]递归,并且arr[pos]放支点元素。我们还要考虑把等于的放到哪边,一般来说,如果我们取arr[fr]为支点,那么我们就要把等于支点的放到右边,这样才能够先把arr[fr]空出来,在下面的一个算法中,我们看到它使用fr, l, r, to将数列分为了四个部分,从而能在最后找到arr[fr]所放置的位置。但是对于上面的挖坑法来说,这是不必要考虑的,因为它保证了将第一个换掉arr[fr]。此外,在手写快排时写完一定要查一下当第一个元素是最小时是否成立,一般算法错就错在这里。
另一种方法,也是算法导论中介绍的,是仿照三路快排来做的。这种方法的主要特点是不再在数列两端来维护了,而是根据CLRS P96的那张图来维护,并且在最后唯一一次移动arr[fr]到准确位置。
注意如果说要找出K个的话,可以使用$O(n)$建一个最小堆,然后做$k$次$O(lg \, n)$的弹出。
此外对这一题我还实现了一个堆排序,堆排序要稍微简单一点,我们主要注意在pushDown交换的时候,我们应当选择两个son最大的那个进行交换

218. The Skyline Problem

这题实际上就是插线问点的问题,首先就是想到用离散化+线段树/树状数组来做。

221. Maximal Square

这条比之前的第85条多了是正方形的条件,我们当时应该是做的这条,比矩形要简单很多

233. Number of Digit One

可以用数位DP硬刚,设置状态status为高位上1的数量(之前以为不需要设的)。
当然这道题也有神奇的解法,具体还没研究

1
2
3
4
5
6
int countDigitOne(int n) {
int ones = 0;
for (long long m = 1; m <= n; m *= 10)
ones += (n/m + 8) / 10 * m + (n/m % 10 == 1) * (n%m + 1);
return ones;
}

236. Lowest Common Ancestor of a Binary Tree

经典的求LCA的题目。一个straightforward的做法是计算得到两个链然后求交。
一个通常意义的解法是离线的tarjan。Python的Hash啊,简直蛋疼,又不能自定义数据结构,解决不了并查集的问题。
用C++写了发终于过了,这里提醒一下,Leetcode的全局变量一定每次计算时要清空。

239. Sliding Window Maximum

如果说需要查任意区间的最大值那么线段树是比较好的办法,不过这道题要求是用$O(n)$时间解决。
这道题做完之后我看题解上是用了啥deque,但我自己做的时候直接维护了窗口两端的指针,然后分类讨论。居然击败了96%

260. Single Number III

老题新做

263. Ugly Number

没啥好说的

264. Ugly Number II

想一开始用筛法预处理打个表,然而TLE了。也没发现能够从各因数的幂上发现子结构。解决方案还是从$O(n^2)$的筛法上下手,原筛法是对第$i$个丑数,看看能从先前的丑数中进行更新得到的最小值。容易发现这个过程存在很多冗余计算。例如在计算$ugly[i]$时,我们需要知道满足$x * 2 > ugly[i - 1]$的最小的$x$,显然我们不需要在所有$ugly[1..(i-1)]$遍历$x$。不过我们发现每次使用$* 2$规则生成新丑数时,我们的$x$是严格递增的。递增很简单,因为新丑数比就丑数大,所以$x$要大。严格是因为所有的丑数都是偏序的。

279. Perfect Squares

点开Playground看一下它附加的后台代码,发现我们打表不能打在Solution对象的__init__上,而应该打在全局。

1
2
3
4
line = lines.next()
n = stringToInt(line)
ret = Solution().numSquares(n)
out = intToString(ret)

295. Find Median from Data Stream

300. Longest Increasing Subsequence

最长上升子序列模板题

309. Best Time to Buy and Sell Stock with Cooldown

首先要思考的是如何维护DP的状态,我觉得可以直接用一个二维数组来表示,因为每一天有三种行为,买、卖和不买不卖,分别导致三种状态,因此我们可以设置数组dp[n][3],紧接着在推导公式时我们发现一个问题,我们计算不买不卖这个状态很有难度。看答案才知道其实是想复杂了。首先它只设两个变量buy[i]表示第i买彩票能获得的最大利润,sell[i]表示在第i卖彩票获得的最大利润。下面我们考虑计算sell[i],最容易想到的是如果第i - 1天买了,那么利润就是buy[i-1]+prices[i],但是如果我第i - 1天不买不卖呢?那我们就直接使用第i - 1天的结果sell[i - 1]。计算

315. Count of Smaller Numbers After Self

我是从逆序对的经典问题出发找到这条题目的,这一条朴素解法是$O(n^2)$的,但似乎不太好套逆序对的模板,因为需要求每个位置的结果,而中途的sort会改变位置。一个straightforward的做法是线段树/树状数组神器,不过常数是比较大的。
但是还有一种思路,我们可以理解成从最后一个元素开始构造一个新的数列,对于每一个元素bisect_left查找它的插入位置,这就是解,搞了一发T了。
通过查看Related topics我发现了二叉搜索树(BST)其实就是用来做这个的,它能够进行动态插入。这里注意一下,不要用数组来实现二叉树,容易爆内存,而且要在每个节点上维护count,否则会爆内存

321. Create Maximum Number

这一条目前还是T的状态
这道题目一开始的思路就是枚举$k$,然后分别对nums1nums2生成最大的数,最后进行归并。
下面我们考虑子问题,从nums数组中取出按顺序的req个数使得组成的数最大。写了一个错误的思路是首先取ans = nums[0..req-1],然后对于从req开始的每个数,我们找到它能替换ans的最小index位置和最大长度,例如[8,5,3,6,7][6,7]能够替换[5,3]。不过这个思路是错的,例如[9,7,9,1],显然[9,1]不能替换[9,7],但是第2个9可以替换第一个7。此外也不能从req位置开始,而应该从1位置开始。
在归并时,我们要注意当nums[i]nums[j]相等时需要向下比较,如果当其中一个数列耗尽还没比较出来大小,那就选择另外的数列为大,因为另一个数列可能下面的元素就大了。例如[0][0, 6]

322. Coin Change

这是一道完全背包的问题。

324. Wiggle Sort II

这道题比前面的Wiggle Sort去掉了可以相等的条件。平凡解法依旧是$O(n log \, n)$的,使用排序之后一头一尾接着取,也能AC。题目要求的$O(n)$时间复杂度和$O(1)$空间复杂度就有难度了,首先DP肯定不行了。一个初步的策略是首先算出中位数,这个有一个$O(n)$的第k大数的算法std::nth_element,然后将大于中位数的放在奇数位,小于等于的放在偶数位。注意当数列为奇数个时,中位数放在偶数位作为一头一尾。因此我们必须新开一个数组,造成$O(n)$的空间开销。
题解用了一个很巧妙的思路,首先将原数列映射成[1, 3, 5, ... , 0, 2, 4, ...]的形式,然后考虑这个“新数列”。它的前半部分都大于中位数,后半部分都小于中位数。这又回到了之前的快速选择的问题上。不过这个做法还是有问题,例如[1, 3, 2, 2, 3, 1]的结果是[1, 3, 2, 2, 3, 1]。正确答案需要三向快排来处理相同值的情况。与二向划分不同的是,三向划分虽然拥有lreq三个指针表示小于等于大于三个边界。但它只使用一个循环,即用eq指针从前到后遍历数组,而不是使用两个指针相向移动。当遇到大于pivot的数的时候,就把它扔到r指针位置,并更新r。当遇到小于pivot数的时候就把它和l指针互换,保证l左边都是小于pivot的数

326. Power of Three

一道很有趣的题,要求不使用循环和递归来判断一个数是否是3的整数幂。我能想到是log,还有一个蹩脚的二分搜索。一个应该是最优解使用int范围内最大的3的幂1162261467来模这个数看是否能整除。
这里用log+python的is_integer写了一发,发现math.log(243, 3).is_integer()返回False,所以还是要自己用eps判定下。

338. Counting Bits

这条虽然可以按191的思路做,不过更好的方法是DP,以0011b为例,它中1的数目ans[0011b] = ans[0011b >> 1] + (0011b & 1)

343. Integer Break

经典的整数划分问题。这道题我记得看过推导是分成$N/e$个数为妙,不过我最后还是做了下记忆化搜索解决的。注意因为题目要求至少分两块,所以我们要存两个dp,一个是必须要分的,一个是可以不分的。
这里额外说一下几个常见的整数划分问题:

  1. 将n划分为若干整数之和

    1
    2
    // 这里k表示不超过k的整数
    dp[n][k] = dp[n - k][k] + dp[n][k - 1]
  2. 将n划分为若干不同整数之和

    1
    2
    // 这里k表示不超过k的整数
    dp[n][k] = dp[n - k][k - 1] + dp[n][k - 1]
  3. 将n划分为k个整数之和

    1
    2
    // 其中第一项为划分中不包含1的情况,第二项为划分中包含1的情况,注意不是dp[n][k - 1]
    dp[n][k] = dp[n - k][k] + dp[n - 1][k - 1]

354. Russian Doll Envelopes

这题很好用记忆化搜索做,因为信封之间是偏序的,即如果信封A能dfs到信封B,则信封B肯定不能dfs到信封A,因此dfs的时候不需要维护状态。不过撸了个Python版本的,超时了。后来发现要$O(nlogn)$才能保证过,不过C++又没卡住$O(n^2)$的复杂度。
后来发现这道题可以转化为LIS来做,把w看成横坐标,h看成纵坐标,我们实际上是要找h的最长的上升子序列。注意为了处理横坐标相等的情况,需要在此时将纵坐标从大到小排列,以便bisect_left能够定位到准确位置。

363. Max Sum of Rectangle No Larger Than K

这道题到现在还是T的状态。
这道题和前面的Maximal Rectangle有点像,这次我们来看一个不一样的DP方法,也就是将其转化为一维DP问题来做。这条的复杂度应该是$O(X^2 \times Y \, logY)$,其中$X, Y$分别为矩阵的长和宽之间的较小/大值。前面的O(X^2)很简单,可以仿照红书上的最大权自矩形来做。假设这个矩阵列数很多,我们维护一个列的累加和sum

1 1 1          1 1 1 
1 1 1    =>    2 2 2
1 1 1          3 3 3

然后我们枚举所有的(up, down),例如当枚举到(1, 2)时,我们计算一个sub表示所有上底为第1行下底为第2行的“棍状数列”的和。接下来我们采取同样的办法计算sub的累加和arr

sub = (3-2) (3-2) (3-2)
    =   1     1     1
arr =   1     2     3

于是我们的任务就变成了在arr中找到$l < r$,使得$arr[r] - arr[l]$是满足小于$k$最大的数。因此我们可以从i开始遍历arr,然后在一个数据结构内花$O(log n)$查询最接近$arr[i] - k$的值,然后再花$O(log n)$将$arr[i]$放到这个数据结构里面。显然我们可以用一个二叉树来维护,但是我T了,不知道为啥
这里说明一下题解上有人用bisect.insort(),注意这个复杂度是$O(n)$的,我之前写的代码效率不高,所以被卡常了。倒是C++里面的setmap啥的有lower_bound。使用二叉树之后反而更垃圾了。

390. Elimination Game

这道题和经典的约瑟夫和问题看起来有点像。当时觉得每次的起始值难算,所以就简单模拟了下,T了。继而我们发现对于任意偶数nn + 1的答案和n肯定是相等的。看来需要$O(logn)$的复杂度了。于是觉得确实可以把每次扫描数列作为一个子问题,但是我们现在对某个子问题不生成新数组,而是在原数组上进行操作。于是我们维护了se,表示我们的起始点和期望的结束点(也就是现在子数列的最末端),设置step为当前的公差。如对1 2 3 4而言,s为1、e4(不是3),而step为2。容易发现由于我们是偶数项,所以我们只能遍历delta = 2项,并没能遍历到4。我们发现规律,我们每次遍历,要不能遍历到e要不我们能遍历到actual_e,并且actual_ee相差step / 2。于是我们能够得到新的起点的位置

1
2
3
4
5
if actual_e != e:
news = e // Or
news = actual_e + step / 2
else:
news = e - step / 2

486. Predict the Winner

两个人轮流从数组两端取数字,和最大的胜利。数组最长为20。本题可以用AlphaBeta剪枝来做,Python会被卡掉,但是C++能过
Alpha指的是在自己的回合(MAX节点),自己能确保的最利于自己的值。Beta指的是在对手的回合(MIN节点),对手能确保的最不利自己的值。MINMAX博弈假设对手拥有完全信息,总是能做出完美决策,所以对手要最小化评价函数的增益。容易发现初始情况下取Alpha/Beta为-Inf/+Inf,由于我们还没进入游戏,所以这是可能的最高/低分。
容易发现我们需要尽可能提高Alpha值,考虑以一个MAX节点作为根往下遍历,我们首先计算其第一个MIN子节点,MIN子节点总是能够求出自己的Beta值,这时候根节点取该Beta值为自己的Alpha值,从目前看,结果不会比它更坏。但是我们不能就此停住,而是要接着遍历,看看有没有更好的结果。接着我们开始看第二个MIN节点,在计算开始时,我们要通知根节点当前的Alpha值。这个MIN节点肯定也要计算自己的Beta值,因此它要根据自己所有子节点的结果来计算自己尽可能小的Beta值。ALphaBeta剪枝认为此时不需要遍历所有的节点,因为一旦我们发现当前的Beta值低于我们通告的Alpha值,那么我们在根节点肯定不会选择这个MIN节点了,于是可以剪枝。
同理,以某个MIN节点为根向下遍历,也是先选取第一个子MAX节点的Beta值,然后通告给第二个子MAX节点。由于根节点MIN要选择尽可能小的,所以如果子MAX节点的Alpha值大于通告的Beta值,也进行剪枝。

494. Target Sum

这是一条变种的01背包,我们需要求一个和为(S + sum(nums))/2的子集。