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实现)不一样。
另外考虑如果给定数列是有序的,还可以使用二指针来做,这个在下面的3Sum等中非常常用了,因为sort的复杂度是$O(nlogn)$,可以直接忽略不计了。测试了一下,如果对这道题先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的题目没完没了了。这道题也是先排序,然后双指针相向移动,同时用update函数维护一个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)

30. Substring with Concatenation of All Words

题目中一个不和谐的点是字典中的所有的字都是一样长的。这个条件有点强啊。
写了一发暴力搜,也就是从i开始查看能否得到合法的子串。WA了一发发现字典中可能存在重复的字,这就说明要在提出的s的子串中出现两次。果断T了。
后面就是利用这个一样长的条件,这意味着我们可以不要从所有的i开始搜。我们令所有词的长度都是l。那么我们只需要从[0..i)位置开始按词搜索就行了。我们用st维护我们搜索的起点,用used维护目前已经找到的词。那么如果我们在j处成功,那么就执行j += l,将j指向下一个词(因为后面仍然可能有符合要求的);如果我们在j处失败,也就是出现了不在字典d或者多于字典d中的词时,就执行st += l右移一个词,并且从used中移除原先st对应的词。特别地,我们要维护st不能超过j

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]处水柱高。

43. Multiply Strings

大数相乘,瞎搞一下就行

44. Wildcard Matching

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

45. Jump Game II

青蛙跳,给定数组numsnums[i]表示在i位置能跳的最远距离,求达到最后坐标跳的最小次数。不禁想起悲惨的LCM Walk推公式题。
记到i点的最少步数是l[i],这条naive的方法自然是对于每一个i,用它来尝试更新自己的跳跃距离范围[i, i + nums[i]]内的所有的l[j],这样是个$O(n^2)$的复杂度,会超时。
查看题解,实际上这是一个贪心问题,我们使用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解法,这个感觉就像我们把梨子拿在手上一边转一边削梨子一样。其中zip(*matrix)实际上转置了矩阵,如[[1,2,3], [4,5,6]]变成[(1, 4), (2, 5), (3, 6)]。而zip(*matrix)[::-1]实际上逆时针旋转了矩阵。

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

这道题一开始想用二分,不过写砸了,因为可能原先的区间也要合并一部分。后来直接O(N^2)解决了。

58. Length of Last Word

简单题,注意要strip下

59. Spiral Matrix II

这条是简单的模拟,分为4个方向,长度从l - 10,注意0是一个合法状态。

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。后来重新理解了题意,原来是树只能建一次,然后可以不停调换。
显而易见这种变换有一个性质,如果我们选择一个分割点,我们便能够将其分为左右儿子,之后的调换顺序只会改变左右,不会影响分组,于是我们想到递归地枚举所有的分割点,这样可以先递归判断子树是否是Scramble的。将原问题分解为子问题(子树)的时候需要考虑两种情况,即如果我们对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

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

102. Binary Tree Level Order Traversal

层次遍历,就是把指针形式的二叉树转成数组形式

106. Construct Binary Tree from Inorder and Postorder Traversal

由后序和中序生成树。

109. Convert Sorted List to Binary Search Tree

将一个有序链表转成平衡二叉搜索树。这道题应该就是不停找中点。

110. Balanced Binary Tree

平衡二叉树高度差不能大于1。于是就是判断每个子树的高度差,注意还要检查子树是否递归地满足平衡性质

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

在接受了上一条T的教训后这次改用了双向BFS搜索,虽然还是T,但是点从Case22变成了Case29。后来用C++重写了一遍才过。
这里先说明一下这条双向BFS写法上注意点,首先介绍一个很好的双向BFS的模板。我们首先对模板进行改进,首先如果点c被正向bfs所发现,则将vis[c]标记为1,若是反向bfs,则标记为-1。然后我们定义一个bfs(q, flag)函数,flag表示我们现在是搜正向队列还是反向队列。那么在搜索过程中,一旦我们遇到一个vis[mat[c][i]] == flag,这就说明了我们的双向bfs相遇了,于是就返回。下面的问题就是如何记录搜索深度,一开始我的想法在两个队列q1q2中记录当前节点c的访问深度,例如正向搜索首次发现了c节点连通的子节点mat[c][i],那么就向正向搜索队列q1中增加(mat[c][i], d + flag),其中dc节点的搜索深度,容易得到起始节点的搜索深度是1,紧接着的正向队列的深度依次取2、3、4等。终点的搜索深度是-1,紧接着的反向队列的深度依次取-2、-3、-4等。与此同时使用deep1deep2来分别维护正向和反向bfs达到的最大深度。但是在提交时发现这是不对的,例如当反向队列与正向队列相遇时,相遇点不一定是正向队列最深的点。例如从catfin可以有下面的搜索路径,我们看到走cat -> can <- fan <- fin是最优解,但是如果按照维护的最大值的话,我们会算上pat -> paw这没用的一步。

q1 1: cat -> pat
q1 1: cat -> can
=================
q2 -1: fin -> fan
=================
q1 2: pat -> paw
=================
q2 -2: fan -> can

所以我们将deep1deep2去掉,而借助于vis[c]数组记录访问到c节点时的深度,这样我们就可以精确地知道相遇节点被正反向队列锁访问的时间了。

128. Longest Consecutive Sequence

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

129. Sum Root to Leaf Numbers

水题

130. Surrounded Regions

一个DFS了,比较取巧的是可以从边界先把能保留的O筛出来,然后将剩下的O清空。

131. Palindrome Partitioning

这道题很无聊,就是要你列出所有回文串的分隔可能性,有趣的是下面一条

132. Palindrome Partitioning II

这道题不太会,看了题解,原来就是首先找出来所有的回文数,然后套Word Break的模板。
T了一发,这是因为我是找出了所有的回文串文本,但实际上我们应当用dp[i][j]记录[i,j]是否是回文串。这个记搜一波即可

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自动机做,不过失败了。
其实这道题根本就不是AC自动机,直接DP[pos]维护一下从pos往后的子问题的答案就行了。

140. Word Break II

类似139。

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,其交点就是环的起始点。

144. Binary Tree Preorder Traversal

前序遍历,xjb写了个非递归版本

145. Binary Tree Postorder Traversal

经典的二叉树后序遍历问题,xjb写了个非递归版本

146. LRU Cache

在$O(1)$复杂度下,免不了Hash。但是为了能够方便进行排序,我们又要采用一个双向链表组成队列。于是就用一个dict来定位链表里面的各个Node。

147. Insertion Sort List

链表的插入排序,一开始写砸了,后来发现其实分成两个链表,从未排序的free list不停往排好序的sorted list插入元素。这道题Python居然T了、、、我也是服气。

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

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

154. Find Minimum in Rotated Sorted Array II

一个恶心的题目,要是能一遍做对就很厉害了。这题告诉我二分法在查找更新的时候不能激进地r = mid + 1,也要考虑下r = mid这样。一般能确定mid肯定不对,那就用前者。
由此严格地来做,我们可以将二分分为两种类型,F/T…TTT和TTT…F/T型,由于我们始终是要找第一个T。对于前者,如果我们fail了mid,那么我们就要更新lmid + 1,否则更新rmid,注意我们不能激进地更新到mid - 1,因为mid可能是第一个T。对于后者我们就要更新rmid - 1,否则更新lmid。下面我们考虑mid的求法时需要做到极限情况下不陷入死循环,以区间[3,4]为例。假设mid = (l + r) / 2,即mid = 3。对于前一种情况,我们OK之后会更新到[3,3],这时候l == r,我们可以成功返回结果。对于后一种情况,我们OK之后会更新到[3,4],这时候死循环发生了。由此我们对于后者应该做mid = (l + r + 1) / 2的更新。
特别地,如果对于668题这种暂时无法确定是F/T…TTT和TTT…F/T型的,我们可以直接判断它是rmid - 1型的还是lmid + 1的,如果是rmid - 1的算mid就要+1

160. Intersection of Two Linked Lists

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

162. Find Peak Element

裸二分吧

164. Maximum Gap

这题是求一个未排序数列的有序形式相邻两个数的最大差,要求线性复杂度。不会,Related topic显示还是sort,难道是考桶排序?xjb写了个,然后面向OJ二分桶大小就过了、、、但是这条还是需要改一下的,自己做法其实很慢,只击败了2%的人。
看了一下题解,首先他根据鸽笼原理求出最大差值的下界,即$(mx - mi) / (n - 1)$,我们把它作为桶的大小,这样的好处是我们的最优解肯定不在某个桶内求得,而一定在桶间。

169. Majority Element

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

174. Dungeon Game

这一条是倒推的动态规划,我们将原数组改为从1开始的数组,用need[i][j]表示从(i, j)到达公主所需要的最少HP,那么need[n][m]显然为1,我们要求need[0][0]。容易看出递推式为need[i][j] = min(need[i][j + 1] - mat[i][j + 1], need[i + 1][j] - mat[i + 1][j])。当need[i][j] <= 0时,也就是说从need[i][j]往下走还会盈余HP,但是我们不能结算给(i, j)前的位置,这是由于在过程中的任何时候HP都不能小于等于0,因此不能先欠再还。实际上我们的need[i][j]必须始终大于等于1。

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条中我们发现了类似的归并的问题。

187. Repeated DNA Sequences

暴力dict一波?

188. Best Time to Buy and Sell Stock IV

相比III,现在我们最多可以执行k次而不是两次交易。首先想了一个xjb搞的算法,将所有的连续上升串找出来,然后排序并尝试提取出差最大的k个,这里注意如果不足k个的话也不影响,因为性质(a - b) + (b - c) = a - c。但是发现WA在了2, [1,2,4,2,5,7,2,4,9,0],因此当我们的串的个数大于k时,我们需要尽量把这些区间合成到k个。
上面的想法想了半天不知道怎么搞,于是从Best Time to Buy and Sell Stock With Cooldown那条下手,用两个数组sellbuy分别表示第i天(从1开始)做至多j个任务的最大收益。写了一个O(nk)的算法,TLE了。most_trans表示第i天最多能做(i + 1) / 2个交易。

1
2
3
4
5
6
7
for i in xrange(1, n + 1): # at day i
most_trans = min((i + 1) / 2, k)
for j in xrange(1, most_trans + 1): # this is j-th transaction
buy[i][j] = max( buy[i - 1][j], sell[i - 1][j - 1] - prices[i - 1] )

for j in xrange(1, most_trans + 1): # this is j-th transaction
sell[i][j] = max( sell[i - 1][j], buy[i - 1][j] + prices[i - 1] )

用C++改写了一下,发现k可能非常大,虽然后来将buysell优化成滚动数组,但还是开不了这么大的数组。于是发现当k > n时这道题实际上退化为Best Time to Buy and Sell Stock II,于是可以$O(n)$时间,常数空间解决。
题解里面用最大堆的那个没有看懂。

189. Rotate Array

简单题,rev两次

190. Reverse Bits

这个很简单,直接不停n & 1然后n /= 2即可

191. Number of 1 Bits

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

198. House Robber

简单的动态规划

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

看起来是个拓扑排序

213. House Robber II

相比前一条,现在要求在环上DP了。当时觉着能够化为前一条来做,不过没怎么搞明白。其实给一个Hint就是第一个和最后一个房子不能同时被抢,所以问题就分解了。

214. Shortest Palindrome

这道题对我来说蛮难的,首先KMP比较难想,然后我KMP还写错了。

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条多了是正方形的条件,我们当时应该是做的这条,比矩形要简单很多

223. Rectangle Area

这道题蛮巧妙的,计算方法是容斥原理,找intersect蛮难的。因此我们要找到上/下/左/右除去边框的次级值。

228. Summary Ranges

这个我是维护每一个[fr, to]的区间,然后对每一个x二分出index表示x应该在index前面,接着查看能否将x贴到index - 1或者index上。最后查看能否合并index - 1index
不过其实这道题很简单,因为是排好序的,所以直接xjb跑一下就完了。

229. Majority Element II

这次是[x / 3]的。我们这次依然使用打擂法,也就是Boyer-Moore投票算法。不过这次我们需要维护一个大小为3的集合(即最多容纳三种不同值的数字),例如1 1 1 2 2 2 3表示成[(1, 3), (2, 3), (3, 1)],当随后出现一个4时,集合的容量不够了,那么这一个4就会和集合中的所有元素进行一次湮灭,例如现在的即可变成了[(1, 2), (2, 2)],其中3的数量不够了,就从集合中被去除。

230. Kth Smallest Element in a BST

随便写了一下,常数应该比较大,居然还击败了66%。用一个函数index求一个节点下的count。接着用函数dfs递归,首先看左儿子的节点数是否满足k <= cntl,注意k == cntl时答案不是左儿子,而是左子树中的最大值。
看到一个很简洁的答案,其思路就是不停地递归左儿子,并在k上减掉已经遍历过的数量n,并返回n处的值x。容易看到当k == 0时,要求的值在左子树上,k == 1时要求的值是根,否则递归右子树。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int kthSmallest(TreeNode* root, int& k) {
if (root) {
int x = kthSmallest(root->left, k);
return !k ? x : !--k ? root->val : kthSmallest(root->right, k);
}
}
int kthSmallest(TreeNode* root, int& k) {
if (root) {
int x = kthSmallest(root->left, k);
if(k == 0){
return x;
}else if(k == 1){
k --;
return root->val;
} else{
k --;
return kthSmallest(root.right, k);
}
}
}

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的全局变量一定每次计算时要清空。

238. Product of Array Except Self

这道题蛮有意思的,维护一个leftright累计积,然后对于i,就是它的左边乘以它的右边。

239. Sliding Window Maximum

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

258. Add Digits

求数x0的数位和得到x1,重复上一过程直到得到个位数。要求$O(1)$复杂度。打表发现规律1 + (num - 1) % 9,然后发现其实可以用数学归纳法证明这个规律的。

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$要大。严格是因为所有的丑数都是偏序的。

274. H-Index

桶排序,注意要是min(tot, i)

275. H-Index II

这道题就是二分答案$[0, citations[-1]]$啊。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public int hIndex(int[] citations) {
int len = citations.length;
if(len == 0) return 0;
int h = 0;
for (int i = 0; i < len; i++) {
if (citations[i] >= len - i) return len - i;
else if (citations[i] > h && citations[i] < len - 1) h++;
}
return h;
}
}

其实之前是考虑不二分答案而是二分index,我们试图找到最靠左的位置l使得[l, n)里面的数都大于citation[l],这是一个TTT..T/F型的,不过我们应该返回什么呢。返回citation[l]吗?答案不一定出现在citation数组里面,例如[0,0,4,4],在位置1的右边有2个数大于2,这个答案是2。返回n - l吗?还考虑[0,0,4,4],二分下来l是1,n - l等于3了。这里是因为虽然1位置的0满足了二分的条件,也就是说这是二分的边界情况,但这个边界情况不一定成立,我们得验证citation[l]要足够大,不然我们就要从l + 1位置开始算。
这个答案击败了100%,此外还有一个二分也值得一看,看起来我完全可以把二分的条件写得更严格一点,我当时是怕写出来不满足二分的性质了。

1
2
3
4
5
6
7
8
9
10
11
12
13
start, end = 0, n-1

while start <= end:
mid = start + (end-start)/2
acc = n - mid
cite = citations[mid]
if cite == acc:
return acc
elif cite > acc:
end = mid-1
else:
start = mid+1
return n-start

279. Perfect Squares

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

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

282. Expression Add Operators

一开始打算二分,砸了。
后来打算dfs,这道题的话我们可以将算式看为若干个乘积式的加和

283. Move Zeroes

这道题直接统计0的数目然后覆盖移动就行了,前面有类似的题目

287. Find the Duplicate Number

这道题目很有意思,有n + 1个数,他们的值域为[1, n],里面只有一个数会出现> 1次(不一定只出现两次),要求找出来。这道题要求在$O(n log n)$时间,$O(1)$空间解决。那就是二分答案啊,然后我一开始想歪了,想通过和来比较,但其实是通过小于/大于mid的数的数量进行二分的。

295. Find Median from Data Stream

299. Bulls and Cows

很有趣的xAyB的猜数字游戏,一道小模拟。注意有易错点11101A0B而不是1A1B,因此要用dict来统计一下overlap的个数

300. Longest Increasing Subsequence

最长上升子序列模板题

301. Remove Invalid Parentheses

这道题要输出所有结果,那考虑考虑暴力咯。仔细查看样例,我们发现不能简单地消除能够匹配的括号。
看了题解,这道题和之前的某道题一样,就是挨个从原字符串中去掉1、2、3个字符,直到形成一个合法串,然后把相同长度的都列出来。注意为了加速使用一个set来做记忆搜索。

307. Range Sum Query - Mutable

线段树模板题

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,否则会爆内存

319. Bulb Switcher

【这道题直接打表解决了】
解释一下题意,灯有1表示开、0表示关两个状态。一开始都是1,之后选择%2=1的所有灯切换状态,之后是所有%3=2的灯,一直到%n=n-1的灯。问到最后有多少盏灯是亮的。
写了一个O(n^2)的T了,那应该是推一个很容斥原理一样的公式了吧?然后我打了个表。。。发现答案是3个1、5个2、7个3、、、原来是个等差数列,求和公式也忘了,直接打表和表然后二分AC

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判定下。

329. Longest Increasing Path in a Matrix

这道题挺有意思,Topic有拓扑排序、DFS和记忆化搜索在里面。这道题同信封那条一样是天生偏序的,所以我们不需要vis数组,所以可以通过非常基础的DFS解决。题解中还提到了可以借助于拓扑排序来做,原理也很简单,因为矩阵中相邻节点的偏序关系可以类比成有向边,因此拓扑序一定存在。

332. Reconstruct Itinerary

这道题之前好像在哪个微博上看到的,我还评论了一种可能的拓扑排序的做法。不过这道题目并不能这么做,因为我们可能重复到达某个机场(例如case2),因此并不存在一个特定的拓扑排序。
那这道题就是一个简单的DFS么?也不是,虽然我们要求出发机场相同时按字符串大小选择目的机场,但这一切要建立在整个行程单存在的情况下!例如[["JFK","KUL"],["JFK","NRT"],["NRT","JFK"]]就应该选择先去NRT而不是KUL

337. House Robber III

这贼真是辛苦啊,这次是带权二叉树,同样不能相邻。感觉是树形DP模板题吧,一搜POJ2342。我们使用dp[i][0/1]表示是否抢劫第i个节点的情况,那么可以得到

dp[i][0] = max(dp[lson(i)][0], dp[lson(i)][1]) + max(dp[rson(i)][0], dp[rson(i)][1])
dp[i][1] = value[i] + dp[lson(i)][0] + dp[rson(i)][0]

容易看到这个DP可以用一次DFS求得

338. Counting Bits

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

343. Integer Break

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

  1. 将n划分为若干整数之和
    这里设置一个k是为了去重

    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]

347. Top K Frequent Elements

找到k个最频繁的数。我直接map+sort搞了。

354. Russian Doll Envelopes

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

357. Count Numbers with Unique Digits

又到了我喜欢的数位DP时间。
又被算公式的大佬虐了,由于这条的区间很整,所以算公式反而简单。

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。使用二叉树之后反而更垃圾了。

368. Largest Divisible Subset

第一眼看到,觉得是一个LIS的题目。结果也确实就是这么简单,$O(n^2)$直接过了

371. Sum of Two Integers

用位实现加法,我可是刷过CSAPP的人啊。

372. Super Pow

请移步Kickstart2017G题目A

375. Guess Number Higher or Lower II

简单写了个dfs结果T了,加了个二维的记忆化搜索就AC了。。。注意数组要开到1000。

376. Wiggle Subsequence

一开始的想法是仿照直方图那一条,对于每一个位置i,找到它前面的updown位置,然后统计lenuplendown,但这个思路是错的,因为我们不一定会从前一个位置开始。
现在我们考虑能不能将这道题转化为最长上升子序列LIS来做。用up[i]表示长度为i的最后为上升序列的末尾元素的值,而down[i]为最后为下降序列的末尾元素的值。不过后来发现这个不能做到是有序的,所以没办法二分。因此实际上我们只要从尾部开始遍历即可。
然后发现题目要求是$O(n)$的,看了题解,这道题有一种很妙的贪心方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def wiggleMaxLength(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
p = 1
q = 1
n = len(nums)
if n == 0:
return 0

for i in xrange(1, n):
if nums[i] > nums[i - 1]:
p = q + 1
elif nums[i] < nums[i - 1]:
q = p + 1
return min(n, max(p, q))

377. Combination Sum IV

看起来这道题目要求一个完全背包有多少组解。不过后来发现,我们要求的是排列数而不是组合数。
这反而简单了,事实上这类似之前的整数划分问题。我们用dp[i]维护和为i有多少种方案,则我们对于所有i,尝试对所有的nums[j],更新dp[i + nums[j]] += dp[i]。这类似于之前算平方数的解法。

378. Kth Smallest Element in a Sorted Matrix

这道题很简单,直接模拟归并排序就行了,我用了堆来简化。二分答案应该也可以做,没有试。

382. Linked List Random Node

从长度未知的链表中随机取出一个节点。这一道题是非常著名的水塘抽样算法。
我们首先清楚一个事实,n件物品让n个人选,那么先拿的人和后拿的人获取物品x的概率是一样的。第一个人的概率是$\frac{1}{n}$,第二个人的概率是$\frac{n-1}{n} \times \frac{1}{n-1} = \frac{1}{n}$。
这道题也是一样,我们对于第$i$个数,按照$\frac{1}{i}$的概率替换掉已有的数。

387. First Unique Character in a String

一开始做了个字典,居然T了。得手动维护一个vis数组

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

392. Is Subsequence

求串s是否是串t的子序列,s范围到500000。
朴素做法就是贪一下,$O(n^2)$。
【这道题还有Follow Up】

396. Rotate Function

一看这道题想到的第一就是排序不等式,不过这道题只能rotate而不是任意shuffle,所以不能直接套排序不等式。
一个直截了当的办法,根据Topic中Math的提示,我们需要推一个公式。首先我们设首项$X_0 = \sum^{n - 1}_{0}{i \times a[i]}$,则$X_k = \sum^{n - 1}_{0}{((i + k) \% n) \times a[i]}$,发现减不了。
不过如果直接找规律的话,我们发现$X_i$就是将第$(-i) % n$项置为0,然后其他项都自己加上自己下。因此递推公式很好求了$X = X - (n - 1) * A[(-i \% n)] + s - A[(-i \% n)]$

397. Integer Replacement

一开始我的想法是能/2/2,因为除法始终能减少一位,而减法只有在2的整数次幂的时候才会减少一位。下面要考虑的就是当低位为k个0的时候我们如何选择是+还是-。显然如果低位只有一个连续的1,那么肯定选择-,如果低位只有两个连续的1,我们分别计算,如果选择+,那么最快的转化是0b11 -> 0b100 -> 0b10 -> 0b1,如果选择-,则最快的转化是0b11 -> 0b10 -> 0b1,因此选择-。同理我们发现当7时两者相等。
不过这种解法WA在了1234,我的答案是17,而标准答案是14。后来发现把if n & x == x写成了if n & x,不过10000WA成了17。于是对拍了一下,发现59(0b111011)这个点WA了,正确答案应该是8,应该首先变为0b111100,这样前面就变成了4个1了。这是因为末三位011的策略被选为了-,而正确的策略应该是+。因此我们发现先前的最优策略建立在不考虑高位的情况下,而这对于3来说是不适用的。现在我们综合考虑高位有1的情况,如1011/10011等,我们发现这种情况下应当选择+。

1
2
3
4
5
6
7
8
9
10
// AC
elif (n & 3 == 3) and (n != 3):
n += 1
else:
n -= 1
// WA
elif n & 7 == 7:
n += 1
else:
n -= 1

403. Frog Jump

n个石头,坐标给定。青蛙在第一个石头上,希望能到最后一个石头上。青蛙第一次只能跳一格,假设第i次跳了k格,那么青蛙第i + 1次能跳[k - 1, k, k + 1]格,注意青蛙只能往前跳。问青蛙能否做到。
记搜一波呗,T在Case 34,后来加了个剪枝,A了,不过只打败了3.9%。
题解给出了一种更好的办法,也就是用int key = pos | k << 11;key,然后hash,而不是用二维数组。

407. Trapping Rain Water II

这次是二维的问题了,然后我们要注意边缘没有“墙”,也就是四周无法盛水。一开始想的是假设从点$(x, y)$往下倒水,那么水最多能流到哪里,后来发现不好操作,因为每一点的水位高度取决于其周围的方块高度,而这个是递归的。后来发现我们不考虑灌水而考虑漏水,可以将场景看成亚特兰蒂斯,然后水从边缘逐渐退去。我们用level[x][y]表示点$(x, y)$处的水位,我们查看从$(x, y)$能不能放跑其周围方块$(nx, ny)$中的水,这体现在$(x, y)$处的水位level[x][y]低于$(nx, ny)$的水位。我们注意要保证$(nx, ny)$的水位是至少heightMap[nx][ny]的,这样就相当于没有存水。但是我们却不能一开始就设置level[nx][ny] = heightMap[nx][ny],这样我们就无水可漏,倒是在边缘的level要这么设,因为他们一定不能存水。
然后发现其实一开始的思路也可做,不过我们首先需要按高度从低到高选取方块。为了实现这个顺序,我们需要进行优先队列+BFS。每次我们从优先队列中取出水位level(注意不是heightMap)最低的方块,然后查看它是否可以存放更多的水。这里有两种情况,第一种是该方块的四个邻居严格高于自己,这样我们可以补齐该方块的水位。第二种是出现了水位相同的邻居,这时候我们需要用一个dfs来搜一下。

410. Split Array Largest Sum

将长度为n的串分为m块,要求最小化最大的块的和。能贪么?想了想[2, 5, 6]分两块,贪的话就[2][5, 6]了。用DP做,发现我们要求的是min-max在i位置在第j块的和。
这道题的DP做法我们同样是维护dp[i][j]为前i个数字分成j组的最小的子数组最大和。计算dp[i][j]时我们可以考虑将它放到前一块中去,或者新开一个块,因此递推方程是dp[i][j] = min(max(dp[i - 1][j - 1], nums[i]), dp[i - 1][j] + nums[i])。但这个递推式是错的,连题目给的样例都通不过。这是因为我们不能断定在i - 1时就是最优子结构,因此我们需要遍历所有的dp[0..(i-1)][j - 1]才行。
题解还说原来这条可以二分答案。。。。因为是非负整数。。。。唉,果然二分答案和记搜是拯救DP苦手的神器啊!

413. Arithmetic Slices

给定一个序列,问有多少个子串是等差的。感觉很简单啊,因为是子串而不是子序列嘛,直接统计一下完事了。

414. Third Maximum Number

水题,用个优先队列

416. Partition Equal Subset Sum

背包问题不解释

421. Maximum XOR of Two Numbers in an Array

要求在线性时间内找到数组中两个元素的异或的最大值。看看相关Topic,居然是Trie?想了想确实有道理,整个过程类似于在Trie树上递归,对于Trie树的某个节点有0个或1个孩子的情况都很好处理。但当某个节点具有两个孩子时就比较麻烦,我们需要跨两个树进行比较,看来我们不应该在树上递归。
这道题目挺难的,我直接看题解了。首先我们尽可能地希望高位是1,然后对后面的位我们迭代解一个子问题,迭代次数是和字长相关的常数。因此在第i次迭代中我们希望能够用少于$O(n^2)$的时间来判定当前i - 1位是最优的情况下,第i高位是否能取到1。以样例3, 10, 5, 8为例,其二进制[0011, 1010, 0101, 1000]。首先查看这四个数的最高位[0, 1, 0, 1],我们需要检测是否有两个数满足$a \hat{} b = 1$,这同样是个$O(n^2)$得到过程。为了能够减少复杂度,我们可以运用异或的性质$a \hat{} b = x \Rightarrow a \hat{} x = b$,将问题转变为是否存在$a, b$满足$1 \hat{} a = b$,因此我们只要维护一个Map或者Dict对于任意的$a$,寻找Map或者Dict是否存在$1 \hat{} a$,总复杂度可以降为$O(n)$或者$O(n \ lgn)$。在实现的时候,我没有用Map或者Dict,而是用了Trie,这样做前缀比较方便。
【这道题还有其他的解法】

424. Longest Repeating Character Replacement

允许替换X次,求最长的Repeat子串。这道题我们要注意必须向两边搜,例如BAAAB,不能以开头的B为主元。因此朴素是$O(n^{2k})$的,我们需要枚举向两边搜的长度。
然后我想到能否二分答案,对于每一个可能的长度length,我们找到所有的s[i:i+length],来验证它们是否可行。这样的验证是平凡的,我们只需要找到数量最多的元素,看看它的数量加上k能不能大于等于length即可。这个方法是$O(n^2 lgn)$的,T了,这是因为check函数是$O(n^2)$的,我们可以优化掉一个$n$,但这仍然是T的。
后来我发现其实完全没有必要二分答案啊,我们将k移到不等号的右边。

434. Number of Segments in a String

简单题

440. K-th Smallest in Lexicographical Order

这道题其实就是对一个十叉树进行先根遍历,不过普通的搜会T。所以要做到log的复杂度,不过我WA了好多发。
一开始我希望能够仿照数位DP,计算长度为len的以i开头的数字有多少个。不过这道题这么做并不讨巧,因为我们只限定了长度len,而没有限定位置pos,而在不同的pos,由n给定的end是不同的。而我使用了三维数组之后发现这次记搜根本不会被Hit了。
这道题的正解,可以分为两步,第一步是求一个节点包含自己的所有子孙的节点总数;第二步是找出第k个节点。

442. Find All Duplicates in an Array

【这一条有多种解法,值得一看】
这是第287条的升级版,我们记得上一条是用的二分答案,但这一条不行了吧。但是我们发现Range是[1..n],我们可以从这上面下功夫。这个有点类似于第41条的思路,我们希望通过交换将nums[i] = x移到x - 1的位置上去。如果此时x - 1位置上的值nums[x - 1]x,那么我们就可以知道x是重复的了;如果是y,那么我们就将xy交换,这样x就回到了正确的位置上,而我们下面继续将nums[i] = y归位,这个循环一直执行到nums[i] = i + 1,然后我们处理下一个位置i + 1。这道题击败了99.93%。。。

446. Arithmetic Slices II - Subsequence

首先来一波暴力的dfs,果断T了。看看能不能改成记搜,这里的麻烦之处是状态很难解决,因为公差和末项可能很大,难以存储。然后我想到$N$只有1000,所以可以离散化公差是一个思路,不过好像还是会超空间。通过题解,发现可用数列的末两项(用首两项也行)来离散化首项+公差,不过这次T在了69/101,比之前的39/101稍有进步。后来给l == 1也加上记搜,发现就WA了,后来想想居然也不知道为啥l == 2情况记搜就能过,先放这儿把。不过发现都不能记搜l == 1的情况,否则结果都会被置为0(如果先搜不选的情况的话)。以末两项[2, 4, 6]为例,考虑我们2不取,这时末两项为(4, 6)l == 2,不能构成等差数列,那么搜索会记dp[1][2] = 0,仔细考虑这种情况,是因为我们没有将l`纳入考虑。再考虑首两项的情况也类似。

这道题之前一直尝试记忆搜索,不过一直没搞定,后来发现直接DP反而更简单。
不过后来发现O(n^3)会T在78/101。后来看了题解知道由于可能的差是很少的,所以我们可以维护一个反查的dict

449. Serialize and Deserialize BST

由于是BST,所以根据中序遍历就行了,但是这道题我用Python写在最后一个点MLE了。。。

451. Sort Characters By Frequency

简单题。

452. Minimum Number of Arrows to Burst Balloons

有若干起点和终点的horizontal线段,问最少用多少条vertical直线才能全部与它们相交。这道题并不是问若干直线最多能经过多少条线段,而是需要全部相交,那么方法就很明显了,按照起点排序然后贪心。

453. Minimum Moves to Equal Array Elements

操作只能是对n-1个元素进行自增。我们注意到对n-1个元素自增相当于对唯一一个元素自减。

456. 132 Pattern

这道题非常好,我只想出了$O(n^2)$的方法,但正解要$O(n)$。具体做法看我源码里面的注释。

462. Minimum Moves to Equal Array Elements II

相比上一题,这道题允许选择任意元素+1或者-1。一开始我觉得是尽量往平均数靠拢,但Case[1,0,0,8,6]会WA。其实这道题是求绝对值距离最小,通过Google,这其实是最小一乘法的一个结论,应当选取中位数。
Leetcode上还提供了一个类似贪心的解法,也就是先排序,然后每次选取一个最高分一个最低分,让他们相等,然后去掉。

464. Can I Win

Alice和Bob轮流从[1..maxChoosableInteger]中取数字加到一个总和上,不能重复取,最先达到或者超过desiredTotal的就胜利。问先手能不能胜利,maxChoosableInteger小于20,desiredTotal小于300。
先来个AlphaBeta剪枝(原理见486),WA了,10 40的样例我输出true。去掉剪枝,连dfs都是错的,反省一下自己的思路,我是直接dfs,然后当和大于desiredTotal,就更新self.best,这是错误的,因为没有考虑对手的optimal选择。
其实来一波记搜就好了。
注意记搜不要和AlphaBeta剪枝一起使用。

467. Unique Substrings in Wraparound String

这道是DP,由于要考虑重复的问题所以不能直接算。蛮要想的,原理是dp[x]表示以x结尾的连续串的最长长度。这样最末位的元素不同就能保证了。然后注意不是dp[p[i]] = dp[p[i - 1]] + 1啊,因为dp[p[i - 1]]的最大值不一定在这里取到。

473. Matchsticks to Square

由于火柴棒长度很长,所以不能背包(超大背包啥的也算了)。
这道题就是老老实实DFS,然而我怎么样都TLE。记忆化+bitmask居然更慢。有人说先DFS分成两个,再分成四个,不过很慢。
网上看到一个题解,使用了一个非常好的DFS方法,它每一个dfs枚举火柴i放在第j个边上。这样相比我们每一个dfs试图把剩余的某个火柴加到现在的和里要快些。

474. Ones and Zeroes

二维费用背包模板题

477. Total Hamming Distance

这条直接按位统计0和1的数量,然后计算乘积的和就可以了

483. Smallest Good Base

这个妹(ti)妹(mu)我是见过的,其实就是算满足$x^0 + x^1 + … + x^{k-1} == n$的最小$x$。要解这个方程,不会怎么办,考虑到n才到10 ** 18,令x == 2的话k也才到61,这里就枚举k咯,然后x直接二分即可,下界注意是2不是3,我在这里WA了一次,上界的话我不会解那个不等式,直接令到10 ** 18居然也过了

486. Predict the Winner

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

493. Reverse Pairs

这是一个变种的逆序对,即现在逆序对不仅是nums[i] > nums[j],而要满足nums[i] > 2*nums[j]。一般逆序对可以借助于树状数组和分治法来做。树状数组的做法基于它能够在$O(log n)$的时间内求出$A[1..n]$的和。这里的A其实是一个01数组,A[x]表示数字x是否存在。因此我们小于x的元素的数量是A[1..x-1]的和,可以通过树状数组快速求出。现在我们遍历nums中的每个数字x,并修改A[x] = 1,那么包含x的逆序对的数量就是目前树状数组中值大于$x$的元素的数量,因为这些本来应该在x遍历到之后再被遍历的。
这条如果用树状数组来做的话,A需要离散化。在离散化的同时需要处理好找不到的两种情况。

494. Target Sum

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

495. Teemo Attacking

这道题就是说在技能冷却的时候放技能不能重复统计技能有效时间,数组是有序的,因此我们直接维护一个边界r,每次根据起始时间是否与r重叠讨论,最后更新r即可。

498. Diagonal Traverse

对角遍历矩阵。
这道题其实不难了,遍历就两个方向交替,主要就是越界时改变方向需要想几个样例找规律即可。总结下来就是一般出格时只需要将导致出格的那个速度分量保持不动,另外一个坐标直接+1。不过还有一个特殊情况就是在矩阵四角,两个速度分量都会导致出格。

513. Find Bottom Left Tree Value

BFS即可

514. Freedom Trail

很明显是DP,用dp维护准备填入i字符时轮盘指向j的最少步数,那么对于每一个(i, j),我们查看所有的kj的最短距离。这里要注意一下最短距离是min((j - k) % m, (k - j) % m),而不是abs(j - k) % m

515. Find Largest Value in Each Tree Row

二叉树层次遍历,么得意思

516. Longest Palindromic Subsequence

最长回文序列(不是串了)。这道题又是$O(n^2)$然后Python的T,C++的AC的题目。。。
我们用dp[i][j]维护[0,i][j,n-1]这两个区间上对称字符串的长度。例如bbbab[0,1]区间上是bb[4,4]区间上是b,左边的一个b能和右边的一个b对应,因此dp[1][4]是2。而我们最长的回文序列的长度有两种情况。第一种是[0,i] [i+1,n-1]这样,那么结果是dp[i][i+1];第二种是[0,i] [i+2,n-1]这样的,也就是说长度是奇数,中间夹了个i+1位置的,这种结果是dp[i][i+2] + 1
注意初始化的时候应该首先将dp设为0(而不是1),然后预先计算dp[0][j]dp[i][n-1]

518. Coin Change 2

见343

523. Continuous Subarray Sum

【有趣而且坑多】
这道题很有趣,我虽然过了,但是$O(kn)$而不是最优解$O(n)$。题目要求判断是否存在一个长度大于等于2的子数组,它的和是k的倍数。那么我们维护到i为止所有以nums[i - 1]为结尾的后缀和到一个集合s中,对于i,我们检查(k - nums[i]) % k是否存在于set中即可。我们注意要在检查完之后更新集合s,也就是将集合中的所有数(同余地)加上nums[i],并且在集合中加上nums[i]
枚举一下这道题一不小心会遇到的坑:k为0(数组中含有/不含有/连续/不连续的0),k为1(这个一定成立),k为负数。
下面是这道题的$O(n)$解法,如果当前的累加和除以k得到的余数在set中已经存在了,那么说明之前必定有一段子数组和可以整除k。

524. Longest Word in Dictionary through Deleting

这道题先排个序,然后对d中每一个x用$O(n)$的时间来计算一下能否通过删除s中的某几个字符得到。

547. Friend Circles

统计连通分量了,和之前一条海岛的题目挺像的,直接DFS。

552. Student Attendance Record II

这道题当时想直接推个公式,但是好像比较难。然后我决定分两部分来考虑,首先不考虑缺席A的情况。那么问题变成计算不能超过连续两个迟到L的方案数。这是一个简单的DP。我们分别用P[i]L[i]表示第i天选择出勤和迟到的方案数,则递推关系如下。

1
2
3
4
# 第i天出勤则第i-1天可以出勤或者不出勤
P[i] = (L[i - 1] + P[i - 1]) % M
# 第i天不出勤,要么第i-1天出勤,要么第i-2天出勤,不能两天都不出勤
L[i] = (P[i - 2] + P[i - 1]) % M

下面我们考虑缺席A就很简单了,假设一次不缺席,问题退化成上面的解答。假如缺席一次,我们就枚举缺席的那一天,然后题目变为了两个上面的情况。

553. Optimal Division

这条随便写一下居然击败了99.4%的人,感觉写的常数很大啊。
mxmi维护了区间[i,j]上的最大值,计算这个枚举分割点k就可以了。WA了一次是因为可能不分割,例如[6,2,3,4,5]应当是6/(2/3/4/5),后面的2,3,4,5不需要分隔。
我们还要返回一个具体的括号方案,这个就使用pmxpmi来维护两边的字符串,注意当只有一个数字的时候不要加括号。

554. Brick Wall

556. Next Greater Element III

这个类似Next Permutation那条,直接找到第一个上升型,然后用它之后的大于它的最小数来交换。注意要判断爆int的情况,WA了好几次。

576. Out of Boundary Paths

哎,和之前那个骑马的概率DP蛮像的,这边其实也能正过来推的哦。

583. Delete Operation for Two Strings

最短编辑距离模板题

611. Valid Triangle Number

首先sort一下是肯定的。枚举ij二分最后一个长度,T在了219/220。那应该是$O(n^2)$了。我们考虑每个数的范围最多直到1000,因此考虑统计le_n[x]为小于等于x的数的数量。那么我们考虑a[i] < a[j] < a[k],我们从0开始遍历j(为什么是j不是k稍后说明),此时我们的le_n更新到nums[j]了。我们考虑,要满足a[i] + a[j] < a[k],我们不妨考虑反例,也就是a[i] <= a[k] - a[j]。那么我们从j + 1开始遍历k,我们就可以得到满足以上条件的a[i]的上界。因此我们可以le_n来确定有多少个这样的x <= a[i]。注意一下这里a[k] - a[j]是可能大于a[j]的,这样就不满足a[i] < a[j] < a[k],因此我们查表的时候应当是取min(a[k] - a[j], a[j])的,否则会重复计算。

621. Task Scheduler

假设在i时刻执行了任务A,那么任务A下一次至少在i + n + 1时刻才能执行,问全部执行完的时间。
由于最多26个任务,我们统计一下对应的Nd(task_name, count),然后每一次选取能够执行的、并且数量最多的任务来执行,否则这个时间就闲置。
有一个WA的点是要考虑到比较Nd涉及到与当前时间相关的全局变量global_t,所以每一次时间戳更新之后堆里面的排序都要重新调整。考虑到最多26个项目,所以我直接用了一个list,然后每次sort一下。然后开始疯狂T,这里我的d = {i:tasks.count(i) for i in tasks}写法又贡献了一点功劳,但修改之后还是只能过35/62个样例。
其实题解根本就不要考虑global_t,而是直接算。这和之前做过的一条有点像,就是就着数量最多的来。我们考虑假设有most_cnt个数量最多的任务,例如这里most_cnt为2,设这两个任务为AB,各有most个。那么根据上面的结论最优解是ABXXXABXXXABXXXAB,其中X`首先用其他的字母填,不行了就得补空。

646. Maximum Length of Pair Chain

魔改LIS即可,可参考我的文章,我们把右端点放入dp里面,然后bisect找左端点。注意是bisect.bisect_right(dp, s - 1)不是bisect.bisect_right(dp, s),这里WA了一发。

647. Palindromic Substrings

计算一个字符串中有多少个回文串(看位置而不是值来区分异同)。这道题不复杂,因为$O(n^2)$就能解决了。就是按照Manacher那样扩充一下,然后枚举每一个中心i,向两边扩展直至找到对应最长的回文串,然后枚举下一个中心i + 1,容易看出这样的结果是依照对称中心而不会重复的。

649. Dota2 Senate

这道题就是模拟啊,只要前面健在的R的数量大于0,那么当前的D就滚蛋。注意可能会转好几圈,所以要mod一下。

650. 2 Keys Keyboard

首先我们考虑一下最优策略,肯定是能复制就复制,因为这两种情况A -> AAAA -> AAAA复不复制次数是相等的。
然后我们要注意到我们每次复制必须复制全部,所以这道题不是说我尽量减去2的$k$次方这种。事实上我们将n做因式分解,然后从小到大得进行复制黏贴即可。例如30可分为[2, 3, 5],那么最优的算法就是先复制黏贴成两个A,然后变成3个AA,最后变成5个AAAAAA,对于因数i,一次这样的翻倍耗费1 + (i - 1) = i个操作。特别地,我们可以验证有多重因数的情况,例如8,也应该分成2*2*2

657. Judge Route Circle

弱智题

664. Strange Printer

【这题Python目前还是T】
这道题蛮有意思的,我用Python的$O(n^3)$T了,但是C++的过了。首先不难想的是用dp[fr][to]来记录从frto的次数,然后我们从2开始枚举step,然后对每个位置的fr对应的to = fr + step计算dp[fr][to]。我们也容易知道dp[i][i] = 1dp[i][i + 1] = s[i] == s[i + 1] ? 1 : 2。不过下面的递推方程就蛮考验的。我们考虑情况a***a其中***表示任意的字符,为了生成它,第一种方案是a -> a*** -> a***a,第二种方案是aa...a -> a***a,其中aa...a表示与***长度相等的a,我们于是发现,只要两端相等,那么使用第二种方案总是最优的。

668. Kth Smallest Number in Multiplication Table

这道题其实就是摆明了的一个二分答案。

688. Knight Probability in Chessboard

感觉就是一个概率DP啊。求概率正推,求期望逆推。因此这道题我们可以正推,我们设dp[k][i][j]为第k步走到(i, j)的概率即可,特别地,dp[0][r][c] = 1.0

670. Maximum Swap

逆序排一下,然后贪心交换就行

678. Valid Parenthesis String

首先觉得就统计star的数量,然后当左括号不够的时候就用star补,最后看多下来的左括号能不能用star搞掉。结果WA在*((*。仔细分析,如果左括号不够,确实可以用star补,但并不是所有多出来的左括号都能用star补,如上面的错误,我们不能用左边的star去补。因此对于每一个剩下来的左括号我们都需要知道它右边有多少个star。于是我们可以维护一个SL数组表示[0,i]之间有多少个star(注意要减掉补左括号的),然后算出dp表示[i,n-1]有多少个star,然后把每一个还在栈里面的左括号弹出来,看看它的右边还有没有star可以当右括号用了。

698. Partition to K Equal Sum Subsets

状压DP了一波,从过3到了过7,并无卵用。后来发现是写挫了,剪枝应当在dfs递归调用前就做。

712. Minimum ASCII Delete Sum for Two Strings

字符串编辑距离的魔改版,挺简单的。注意dp[i][0]dp[0][j]要作为边缘条件提前算好。

713. Subarray Product Less Than K

很基本的双指针了,注意我们动态维护prod而不是预先计算,否则会T,而且你做那么多乘法再除也是等着溢出吧

714. Best Time to Buy and Sell Stock with Transaction Fee

现在买卖股票需要缴手续费了。相比Best Time to Buy and Sell Stock II,我们需要知道并不是交易越多越好了,例如[1,3,7,5,10,3], 3。一开始我打算生搬硬套Best Time to Buy and Sell Stock IV的办法,然后T了。
然后发现这道题和交易次数没关系,所以将内层循环去掉了,就过了。

718. Maximum Length of Repeated Subarray

一道类似于最长公共子串的题,不过更新规则略有不一样,只有A[i - 1] == B[j - 1]时才去做更新。居然WA了两次,sad。

719. Find K-th Smallest Pair Distance

这个并不是最近点对,因为它是一维的。这道题解法挺多的,我建议最后都看一下题解。主要思路是二分答案gap,然后有两种方法来算有多少个点的距离小于等于gap
第一种方法我们维护lt_cnt[v]表示小于等于v的点的数量,那么我们就可以用lt_cnt[nums[i] + gap] - lt_cnt[nums[i]]来计算对于点i有多少个点j和自己的距离小于等于gap的。然而这是错的!因为我们还要考虑到i重复值的情况。因此我们需要用strk[i]来维护下连续的i的个数。我们注意下这种方法彻底避免了其他的办法陷入重复统计的困扰,因为它值使用一个指针i
第二种方法是使用滑动窗口来直接算,这个方法需要小心避免重复计算的情况。

738. Monotone Increasing Digits

找到小于等于n的单调递增数(不一定要是严格地)。这一条就是贪,一直按着上界来,直到遇到下降走不下去,例如1332会死在最后一个2上。这时候我们开始回退到132->122,最后在后面补全9。

739. Daily Temperatures

直方图那条吧,水题

753. Cracking the Safe

保险柜的密码是由k个字母组成的长度为n的串。问密码多长能覆盖所有情况。
其实这道题是欧拉回路。我们首先乐观地想是不是可以每一次复用前面的n - 1的长度,我们将证明这是可行的。将k ** n的每一种情况视为图上的一个节点,而每一次添加的字母看做一条边,那么我们实际上就是要找一条欧拉回路。例如

00 -> 01 -> 11 -> 10 -> 00
       |    |
       <---->

我们知道有向图欧拉回路的存在条件是所有节点出度等于入度,但是我们如何找到这个回路呢?我们这里使用套圈法,其基础是一个DFS

1
2
3
4
5
6
7
8
9
10
11
12
def dfs(prev_state):
for j in xrange(k - 1, -1, -1):
next_state = ...
if not (next_state in self.visp) and not next_state == prev_state:
self.visp |= set([next_state])
check_end()
update_path(next_state)
dfs(next_state)
check_end()

self.visp = set([start_state])
ans = dfs(start_state)

我们注意到,DFS中首先会找一个环,但这个环不一定就通过所有的节点,这时候我们就从上一次分叉的地方继续遍历出一个环,然后我们可以连接这两个环组成一个更大的环,如此循环往复即可。DFS的栈式递归优雅地实现了这一点。我们应当注意的是遍历欧拉回路中的点是可以访问多次的(等于度数),但只能访问一次。不过在上面的模板代码里面,我们却用visp数组来维护点(其实在我的上一次提交中额外使用了vis数组来为边,但后来发现这是没必要的),因为我们每个点虽然有很多出度和入度,但在DFS搜索序列中他们只会出现一次,我们用for循环来枚举节点p所有未访问的出边,然后这些出边会各自形成环回到节点p

757. Set Intersection Size At Least Two

首先我们可以用函数inter求出两个interval的交集。如果这两个区间的交集容量等于1或2,那么这个交集一定出现在答案里面。如果交集容量等于0,那么这两个区间就需要和别的区间试试运气,直到最后将自己全部加进去。容易看出,上两种情况是确定性的。但是考虑容量大于2的情况,交集的一部分一定算在答案里面,问题是哪一部分呢?
这个问题困扰了我一会,后来通过查看题解发现我们可以考虑不相交和交一个的情况,而不是容量大于2的情况。对区间排序,然后对于不相交的情况就贪心,取最大的两个加入集合,这样加入集合的两个元素最可能能够被后面的覆盖到,从而不浪费。注意我们sort的时候要按照右端点sort,这是显然的,因为我们的贪心策略是希望尽可能覆盖到右边。
下面我们从左到右遍历,设置already数组表示目前已经得到的集合。对于新的区间[s, e],我们尝试将其与already中的所有项匹配。注意这里不能默认匹配already[-1],因为可能出现[5, 9]匹配[[6,6], [8,8]]的情况。我们使用flag记录[s, e]中总共有多少个数字已经被覆盖到了,显然当flag大于等于2时我们就可以直接结束。每一次计算[s, e]already中元素相交[s1, e2]的时候,我们根据交集part大小更新flag。特别地,当交集大小是1时,我们需要记录下[s1, e1],我们不能在这里立即处理,原因同样是上面的这种情况。
下面当我们遍历完后,检查flag,对于等于0和大于等于2的情况很简单。对于等于1的情况需要特别考虑。我们需要看两种特殊情况match [2,6] in [[0,1], [4,4]]match [16,18] in [[18,18]]。我们注意对于后一种情况我们不能向右扩展右边界,而只能扩展左边界。

761. Special Binary String

【WA】
这题真恶心,建议不要做。

763. Partition Labels

这道题很简单,我们就不停地扩大右边界,直到我们目前的集合实现distinct。

767. Reorganize String

一开始觉得直接按item出现次数sort然后双指针头尾就行了,后来发现我们应当先尽量用item个数多的。然后就用一个方向的双指针还是不行,这是因为可能前面item的用掉一些次数之后就不是最多的了,所以我们应该用优先队列来动态维护。

769. Max Chunks To Make Sorted

首先题意理解一下,不是reverse而是sort。这道题就是逆序对。对于位置i,查看它之前出现了多少个大于等于i的数字,只要有那么这个数字就不能分割。
注意使用树状数组的时候必须从1开始,所以要对arr的值统一右移一位

775. Global and Local Inversions

这道题就是数学题,要求A[i] < A[j] forall j > i + 1,我们可以反过来计算A[i] >= A[j] forall j > i + 1即是否存在A[i] >= A[j] forall i < j - 1即可。

778. Swim in Rising Water

其实就是要求从(0, 0)(n - 1, n - 1)路径上的最大值的最小值
其实这道题又是可以二分答案糊弄过去的,但我们是体面人。。。所以研究一下搜索的解法。
这道题我从前一直尝试用记搜来做,但一直失败。后来从题解上看到一个简化思路,为了尽快游泳,我们肯定尽量从高度低的地方走,因为水会尽快漫过去,所以我们这次做BFS,然后维护一个当前路径上的最大值即可。

780. Reaching Points

按照(x, x+y)(x+y, y)的规则走路,问是否能够从(sx, sy)走到(tx, ty)。这道题挺有意思的,让我想到LCM Walk这道题。LCM这道题是按照LCM(x,y)来更新的,实际上是一道数论题。这道题更简单,肯定也是用数学做,当然你爱用矩阵搞事情也行、、、
这一道题的简单之处在于我们不需要证明从终点往起点走的唯一性,因为数都是大于0的。这里注意一个细节,为了不t,我们会批量减,但是我们要注意减去的txty最少要是1个,最多不能使得到的差小于sxsy,否则会丢失结果。

781. Rabbits in Forest

排序的话要O(nlgn),但是可以由于值域不大(1000),所以可以直接用桶。我们知道如果有dp[i]个人说和自己相同颜色的还有i个人,那说明有i + 1人有相同的颜色。当dp[i]大于i时,那么就说明有这dp[i]个人至少有$\lceil dp[i]/i \rceil$组不同的颜色。

785. Is Graph Bipartite?

判断是否是二分图。我们可以联想到匈牙利方法是怎么找增广路径的。因此我们直接一个DFS,然后在vis数组上进行标记,对于节点pos,设其vis1,表示在二分图的一边,那么它能访问到的所有nxtvis一定是-1,表示在二分图的另一边。那么一旦我们找到一条边其visnxt相同,那么就不可能是二分图了。
注意二分图可以是不连通的,所以我们应当DFS完毕。在这里WA了次。

786. K-th Smallest Prime Fraction

【本题Python TLE了】
这道题其实蛮好的,主要有用堆和二分答案。其中用堆的我Python是TLE,C++倒是能过。不过用了vis数组,其实可以不用vis数组,只添加(p, q - 1)。我们考虑一下[1, 2, 3, 4]的情况,我们首先添加(1,4), (2,4), (3,4),然后我们出(1,4),只添加(1,3),那么(2,3)在哪里添加呢?因为(2,3)肯定在(2,4)后面,因为2/32/4大。

790. Domino and Tromino Tiling

问用2x1和短L型方块铺满2xN的板子有几种方案。这道题是一个有趣的动态规划,我们可以设dp[i][0]为刚好填满第i个槽的方案数,设dp[i][1]为填满第i个槽但是在第i + 1个槽鼓出来的方案数。我们可以对五种情况进行讨论,具体可以见我代码里面的注释。在写的时候WA了几次,都是方案没有考虑周全。

799. Champagne Tower

这个倒酒的题目我是在哪次ICPC热身赛上做过的,当时好像直接大模拟了。
这道题其实也是模拟,我们第一步是对每一层,将每一个酒杯应得的酒(由上一层计算而来)冻成棍子全部塞进去,然后我们让棍子融化,让多出来的酒流到下面的1/2个杯子里面。

801. Minimum Swaps To Make Sequences Increasing

咋一看因为是逆序对。不过这个是在两个数列对应位置之间进行交换。这个直接xjb动态规划了,按照套路设SNS两个数组表示是否交换i位置,然后根据是否交换i - 1地推即可。

802. Find Eventual Safe States

这道题就是DFS,黑白灰染色法,根据前向边后向边和横边讨论。这道题WA了两次,第一次是将横边和后向边一起处理了,第二次是忘了flag |=,写成了flag =

813. Largest Sum of Averages

这道题一开始是想的一个淳朴的$O(n^2)$的DP,即设dp[i][k]表示到第i个数split了k次的最大值。那么我们在i处有两个策略,一个是跟之前的队,另一个是在这里split下来自立门户。由此写出一个WA的算法,对[2561,9087,398,8137,7838,7669,8731,2460,1166,619], 3会WA。
正解是需要$O(n^3)$,我们需要额外的一个j表示我们的区间是[j+1, i]。这是因为我们虽然跟之前的队,但是此时之前最优的队不一定到这里就是最优的了,这题实际上有点类似于410这条。

823. Binary Trees With Factors

这道题要求用数组A中的数组成二叉树,要求二叉树的父亲等于两个儿子的乘积,问有几种方案。这题显然就是dp了,我们首先sort一下,然后用dp[i]表示第i个节点为根的二叉树有多少种排布方案。我们只需要枚举[0, i)区域内节点作为lson,然后查看是否存在rson即可。

826. Most Profit Assigning Work

这道题就是贪,因为任务可以重复完成,所以每个人做能力范围内利润最高的工作

827. Making A Large Island

用0和1表示的矩阵,1是岛屿,问最多将一个0改成1,能形成的最大的岛屿的面积是多少。
这道题就是先找出所有的连通分量并染色,记录每个连通分量的大小。然后对于所有的0,尝试改为1,并且查看这次变动能否合并上/下/左/右四个方向中的两个或多个(WA了一次是因为漏掉了这个)连通分量。此外我们还要判断这两个连通分量是否已经是连通的,例如下面的情况,括号处的0实际上并没连接上下两个连通分量,因为他们本来就是一体的。

1
2
3
4
1 1 1
1 1
1 (0)
1 1 1

829. Consecutive Numbers Sum

不等式限制一下k的范围就行了。有点类似483题。

835. Image Overlap

837. New 21 Game

我们注意到分数是只增不减的,所以这道题很好递推,写了个$O(WK)$的结果T了。后来发现其实dp[i]可以由sum(dp[i-W..i])/W求得,于是动态维护一个和tot就行了。这里我们要注意一下,当i - 1 >= K时就不能加到tot上了,因为这时候游戏已经结束了。

838. Push Dominoes

这道题首先要注意的是样例2的情况,不是RRRL或者RRRR哦……然后我们的主要关注.,比如R...这样就会引发骨牌效应变成RRRR,也就是多个L或者R的力量是不能叠加的,因此一开始推的骨牌的命运是注定的。于是第一个想法是维护l[]r[]表示每个LR向两边传播的“力”的大小,例如R...就表示成[1, 2, 3, 4],不过这没卵用。后来发现我们可以通过简单的判断每一个.到两边的LR的距离来判定这个.究竟倒向谁。然后我们要讨论几个特殊情况,因为有的时候骨牌不能往左或者往右倒。我们考虑i能否向左倒:

  1. 假设最近的ri右边往左倒,从而往左撞倒i。我们应当注意到r可能不存在,也就是r == inf的情况
  2. 假设r向左撞倒i前碰到了向右倒的rb,即出现i(.) rb(->) r(<-)的情况,这时候i也是倒不了的

对于以上的两种情况,我们要先预先处理,然后再进行左右的力量较量

841. Keys and Rooms

判断一个图是否是连通图

846. Hand of Straights

用一个dict来维护每个元素的个数,然后从小到大依次check还在的元素。

865. Shortest Path to Get All Keys

【Contest 92.4 没做】

866. Smallest Subtree with all the Deepest Nodes

【Contest 92.2 1A】
二叉树上多个节点的LCA,拉出链表来搞一波

867. Prime Palindrome

【Contest 92.3 1A】
老哥你才10**8,还回文数+质数,我直接打一个表然后bisect完事。。。

868. Transpose Matrix

【Contest 92.1 1A】
矩阵转置,没啥好说的