Leetcode解题报告

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

整理

序列性质

1. 11
   max(min(A[i],A[j]) * (j - i))
   维护单调减小的 j - i，那么极大值只能靠更大的 min(A[i],A[j]) 来产生，所以不能错过任何让 min(A[i],A[j]) 更大的机会。
2. 1014
   max(A[i] + A[j] + i - j)
   i 和 j 可以组成两个函数，从而变成 max(f + g) 的求和问题。
3. 962
   max(j - i), where i < j and A[i] <= A[j]
   类似于11，随着 i 增大，更小的 A[i] 才会被考虑。

二分

总结：

1. r = mid - 1搭配mid = (l + r + 1) / 2
2. l = mid + 1搭配mid = (l + r) / 2

记忆方法，带入 l = 0; r = 1，则 mid - 1 不能越下界 0，mid + 1 不能越上界 1。带入 (0 + 1 + 1) / 2 = 1，发现 mid + 1 超过 1 了，所以这里不能 + 1。相反同理。

1. Find Minimum in Rotated Sorted Array

Python 的 bisect 库：

1. bisect_left
   返回一个插入点，如果 x 存在 a 中，则返回该位置前。这个参数可以被用作 insert 的第一个参数。

C++ 的函数：

1. std::lower_bound
   返回第一个大于等于给定 value 的迭代器。如果不存在这样的数，就返回 end()。
   如果使用了 comp，则是第一个不满足 comp 条件的迭代器。comp 的类型是 comp(element, value)。
2. std::upper_bound
   返回第一个严格大于给定 value 的迭代器。如果不存在这样的数，就返回 end()。
   如果使用了 comp，则是第一个不满足 comp 条件的迭代器。comp 的类型是 comp(value, element)。

二分答案

树

1. DFS
2. Tarjan
3. LCA
   见236

双指针

1. Container With Most Water
   面积的大小取决于三个变量，左边界高度 L、右边界高度 R 和两个边界的距离 D。这里需要认识到，如果 D 变小，那么 L 和 R 要同时都变大才行，不存在 L 变小，R 变大的情况，因为是短板效应。

DP

动态规划的注意点是子状态不要搞反。

比较有趣的题目

1. 买卖股票系列
2. Burst Balloons
3. House Robber 系列
4. Jump Game 系列
   2 第一次做绕了，因为总想着反过来推，但这个是正过来的。
   从 3 开始没啥意思了。

排序

快速排序

递归的都一样，差别在如何做 partition。有三路快排、挖坑等方法。详细可见 215 快速选择。注意，快速选择的复杂度是 O(n)，这是因为每次只要处理半边。

三路快排

比较容易理解的是三路快排。
给定指针 fr、i、j、to：

1. [fr, i] 间的小于等于 pivot
2. [i+1, j] 间的大于 pivot
3. [j+1, to] 间的无限制
4. to 处是唯一元素，即 pivot

具体算法画个图，看看怎么维护性质就行了。最后的结果是，i 和 j 是从 -1 开始的。整个循环是移动 j，这个也是显然的，因为一开始总是移动最右边的指针，不然新数据从哪里来呢。

另外在 324 中还介绍了带 eq 指针的三路快排。这种情况下，就不能只在一边维护指针了。比如考虑 fr、i、eq、j、to，现在尝试移动 j 到 j + 1，发现 j + 1 小于 pivot，那就要移动到 i + 1 的位置。i + 1 所在的是原先的相等区间，所以原先 i + 1 位置的数要移动到 eq + 1 位置上。而 eq + 1 所在的是原先的大于区间，所以原先 eq + 1 位置的数要移动到 j + 1 位置上。如果 j + 1 等于 pivot，那就要移动到 eq + 1 的位置。
总之这很烦，如果在右侧维护大于区，会容易很多。

线段树和树状数组

1. Sliding Window Maximum

滑动窗口

1. Longest Substring with At Least K Repeating Characters

单调队列/单调栈

通过单调递增栈可以找到当前元素左起第一个比自己小的元素，也就是当前栈顶。在为了入栈当前元素时，会将比当前元素大的先出栈。

1. Sliding Window Maximum
2. Shortest Unsorted Continuous Subarray
3. Max Chunks To Make Sorted II
4. Maximum Width Ramp
5. Maximum Sum Circular Subarray
   单调队列

整数划分和整数性质

1. Ugly Number 系列
2. Integer Break

区间相关

1. Merge Intervals
2. Non-overlapping Intervals

背包

图论(不包含树)

欧拉回路

1. Cracking the Safe

线段树

1. My Calendar I

趣题

1. Perfect Rectangle
   几何性质
2. Find Median from Data Stream
   两个堆
3. Super Washing Machines
4. Super Egg Drop
   经典的高楼扔鸡蛋。

一题多解

1. Maximum Sum Circular Subarray

1. Two Sum

K-Sum经典题目，给定一串序列，找到a+b等于给定的n。
$O(n^2)$要T的，正解对任意的i，判断target - i是否在集合s中，如果不在，把i加到集合s中。注意因为Python中dict用散列表实现，所以查询复杂是$O(1)$的，这和C++中基于 RBT 实现的std::map不一样。
另外考虑如果给定数列是有序的，还可以使用二指针来做，这个在下面的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相对移动，要想还比它容积大，就要比它高。然后看起来是双指针了。问题是[i,j]、[ii,j]、[i,jj]、[ii,jj] 怎么一趟比大小呢？
这里需要认识到，如果 D 变小，那么 L 和 R 要同时都变大才行，不存在 L 变小，R 变大的情况，因为是短板效应。
令h = min(height[i], height[j])，则对于任意的ii, jj，如果height[ii] <= h或height[jj] <= h那就跳过。
首先，注意不是height[i + 1] < height[i]，这样遇到两个都不满足的情况就死循环了。
然后，需要发现这里的妙处是保持住优势，让劣势向前看，从而导致不会漏掉[ii,j]、[i,jj]的情况，例如(ii=5表示ii处的高是5)：

1. 初始情况 i=7,j=4
   h=4
2. 前方1：ii=5,j=4
   如果前进i到ii，我们就会漏掉7的所有可能。但如果开始j–，则并不会有什么损失，反正j已经“烂了”，不如搏一搏。
3. 前方2：ii=3,j=4

仔细想想，这里的实质是让 j - i 单调减少时，不能错过使得 h 能单调增加的可能性。我们的极大值取决于i和j的较小的，所以当记录了极大值后，较小的值既不会对 j - i 有贡献(因为这个肯定持续变小)，也不会对 h 有贡献(h 肯定只能单调递增，才能更新极大值)了。

14. Longest Common Prefix

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

15. 3Sum

乍一看以为是01背包，然而并不是，看题目应该是和第一条类似，暴力就行了。于是照搬第一条撸了个$O(n^2)$的交上去，居然T了，看了一下T在倒数第二个点，卧槽还卡常啊。
查看题解，把对j的循环和仿照2Sum的使用dict查k去掉改成双指针夹逼法。这个方法在于遍历每个i，然后对剩下的两个数j和k从j = i + 1，k = 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++卡掉）。

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

24. Swap Nodes in Pairs

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

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是没有范围的，所以不能使用补码等运算，对于溢出的情况也要专门判断。

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)$后数组便会变成有序的。
为什么不能映射为 $h(x) = x$ 呢？写代码就可以发现，[1,1] 这样的数据是过不了的。

n = len(nums)
if n == 1:
    if nums[0] == 1:
        return 2
    return 1
i = 0
while i < n:
    x = nums[i]
    if x == i:
        i += 1
        continue
    if x <= 0:
        nums[i] = -1
        i += 1
    elif x < n:
        nums[i] = nums[x]
        nums[x] = x
    else:
        nums[i] = -1
for i in range(1, n):
    if nums[i] != i:
        return i
return n

另外，即使映射为 x-1，[1,1] 的处理也很麻烦，容易死循环。

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

青蛙跳，给定数组nums，nums[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，查看它需要用几步才能到达，期间需要同步更新l和r：

1. 正常情况
   如果说i小于等于l，这说明i肯定是能够在s步内达到的。
   下面我们要尝试更新r。i位置能够达到的最远范围是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里面我看到了一个较为巧妙的处理重复的方法

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维护历史上最长的串的长度。
本题还有二分法。我也实现了一遍：

1. 最优解在左边
2. 最优解全部在右边
3. 最优解由 (, m] 和 [m+1, ) 构成

54. Spiral Matrix

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

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 - 1到0，注意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$。使用多指针维护插入位置是一个常用的方法，在三向快速排序中也有用到。
题解给出了四种方法

需要注意，下面的解法是不行的

class Solution(object):
    def sortColors(self, nums):
        """
        :type nums: List[int]
        :rtype: None Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        i = 0
        i0 = 0
        i2 = n - 1

        for i in range(n):
            if nums[i] == 2:
                nums[i2], nums[i] = nums[i], nums[i2]
                i2 -= 1
            elif nums[i] == 0:
                nums[i0], nums[i] = nums[i], nums[i0]
                i0 += 1

应该改成，要点如下：

1. 不能和已经排序好的2进行交换，所以是i < i2而不是i < n
2. 如果交换了2，那么需要再尝试一下当前的位置的数

...
        while i < i2:
            if nums[i] == 0:
                nums[i], nums[i0] = nums[i], nums[i0]
                i0 += 1
            elif nums[i] == 2:
                nums[i2], nums[i] = nums[i], nums[i2]
                i2 -= 1
                i -= 1
            i += 1
...

76. Minimum Window Substring

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

77. Combinations

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

78. Subsets

此题有非递归解法

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

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

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

81. Search in Rotated Sorted Array II

要求在一个旋转了的有序序列中查找是否存在某项。相比之前那一题，现在允许重复了。
同样，我们要去寻找序列里面存在唯一一个下降点。我们讨论一下新的二分情况

1. arr[l] < arr[r]
   则下降点只可能位于[r, ]，类似[5,6,7,5]中r为7
2. arr[l] == arr[r]
   则下降点位于内部，类似5,6,7,5中r为5。
   有个特例是当l==r时，两个必然相等的。
3. arr[l] > arr[r]
   下降点只可能出现在[l, r]区间内部，如[6,7,1,2]

注意，这一条有个corner case就是[1,1]，很难找到splitter。特判一下这种情况，返回0就行。

82. Remove Duplicates from Sorted List II

简单题

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可以在i和len - i处分割。
这条击败的不多，常数优化有待完善。

89. Gray Code

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

90. Subsets II

这一条就是加上了去重，也没啥花头，毕竟要全部列出来嘛，那我还不如直接借助于set来判定了。
不过似乎go不能够使用list作为key。那就用str并编码一下咯。。。。
另外一种方法是排序，然后统计相同值的有多少数，例如有l个，那么对于每个现在已有的结果，都分别加上1到l个这个数。这种思路常常出现在有重复项的题目中。
在写代码的时候发现，似乎不能指望append不会改变顺序， 现象是使用[]int{0,3,5,7,9}作为测试集时，下面的代码在最后一个循环中ret[a]的值会有变化。TODO

...
        nr := len(ret)
        fmt.Printf("=== %v %v %v\n", i, j, ret)
        new_ret := make([][]int, nr)
        copy(new_ret, ret)
        for a := 0; a < nr; a++{
            // 对于每一个已有的lst，分别添加0-l个当前的数
            for k := i + 1; k <= j; k++{
                fmt.Printf("%v/%v %v %v", a, nr, ret[a], nums[i:k])
                new_slice := append(ret[a], nums[i:k]...)
                fmt.Printf("%v\n", new_slice)
                new_ret = append(new_ret, new_slice)
            }
        }
...

改成下面这样就行了，看起来是append会改变第一个参数。

...
                r := make([]int, len(nums[i:k]))
                copy(r, nums[i:k])
                l := make([]int, len(ret[a]))
                copy(l, ret[a])
                new_slice := append(l, r...)
...

这条题目涉及下面的知识点：

1. copy
2. slice

91. Decode Ways

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

96. Unique Binary Search Trees

想想二叉排序树的性质，再从对称的观点看看样例，就解决了。

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

简单的想法是前序遍历二叉树是有序的，所以我们可以前序遍历出来，记下位置，再 sort，再 restore 回去。
困难的地方是需要保持二叉树的原先结构。

101. Symmetric Tree

递归比较l.left和r.right以及l.right和r.left。

102. Binary Tree Level Order Traversal

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

104. Maximum Depth of Binary Tree

简单题

105. Construct Binary Tree from Preorder and Inorder Traversal

构造树是一个递归的过程。对于前序来说，我们很容易找到root，剩下来的工作是把剩余的列表分给两个儿子。对于中序来说，我们找到root，它左边的点和右边的列表就分别是左儿子和右儿子。这道题要注意一下split的情况。
另外递归方法简单，但非递归方法。。。

106. Construct Binary Tree from Inorder and Postorder Traversal

由后序和中序生成树。

107. Binary Tree Level Order Traversal II

简单题

109. Convert Sorted List to Binary Search Tree

将一个有序链表转成平衡二叉搜索树。这道题应该就是不停找中点。也就是所谓的快慢指针

110. Balanced Binary Tree

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

111. Minimum Depth of Binary Tree

BFS

113. Path Sum II

一个基本的遍历

114. Flatten Binary Tree to Linked List

看上去就是把这个树preorder到链表上，但要求原地修改树。看起来，我们把每一个节点左子树遍历完的最后一个节点缓存下来，并且连接到右子树上面。
我觉得这一类 preorder 的题目，其实可以套一个模板

def preorder(cur) -> (first, last):
    if left:
        (left_first, left_last) = preorder(left)
        if right:
            (right_first, right_last) = preorder(right)
            ...
        else:
            ...
    else:
        if left:
            ...
        else:
            ...

115. Distinct Subsequences

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

117. Populating Next Right Pointers in Each Node II

简单题

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相遇了，于是就返回。下面的问题就是如何记录搜索深度，一开始我的想法在两个队列q1和q2中记录当前节点c的访问深度，例如正向搜索首次发现了c节点连通的子节点mat[c][i]，那么就向正向搜索队列q1中增加(mat[c][i], d + flag)，其中d是c节点的搜索深度，容易得到起始节点的搜索深度是1，紧接着的正向队列的深度依次取2、3、4等。终点的搜索深度是-1，紧接着的反向队列的深度依次取-2、-3、-4等。与此同时使用deep1和deep2来分别维护正向和反向bfs达到的最大深度。但是在提交时发现这是不对的，例如当反向队列与正向队列相遇时，相遇点不一定是正向队列最深的点。例如从cat到fin可以有下面的搜索路径，我们看到走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

所以我们将deep1和deep2去掉，而借助于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）。在上一题中，我们通过异或的性质，实现了值相同的数两两相消。在这一题中，我们希望出现三个相同的数才相消。

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。

138. Copy List with Random Pointer

一个单向链表，有一个random_index可以指向随机的节点，或者null，要求深复制这个链表。
一个很Naive的办法就是先构建next指针，再构建random指针。不过也可以一趟构建完。

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

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

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

相比上一题，数组中可能有重复的元素了。如果我们二分到重复元素怎么办呢？和 nums[0] 比较就行了。
一个恶心的题目，要是能一遍做对就很厉害了。这题告诉我二分法在查找更新的时候不能激进地r = mid + 1，也要考虑下r = mid这样。一般能确定mid肯定不对，那就用前者。
由此严格地来做，可以将二分分为两种类型，F/T…TTT和TTT…F/T型，由于始终是要找第一个T。对于前者，如果我们fail了mid，那么就要更新l到mid + 1，否则更新r到mid，注意不能激进地更新到mid - 1，因为mid可能是第一个T。对于后者我们就要更新r到mid - 1，否则更新l到mid。下面考虑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型的，我们可以直接判断它是r到mid - 1型的还是l到mid + 1的，如果是r到mid - 1的算mid就要+1。默认while (l < r)。
总结：

1. r = mid - 1搭配mid = (l + r + 1) / 2
2. l = mid + 1搭配mid = (l + r) / 2

155. Min Stack

设计一个最小栈，要求能够满足三个原语之外，还支持getMin操作，要求常数代价。这个和单调栈还不一样。
解法很神奇，就是每次入栈的时候多入一个当前元素的最小值。。。真贱。。。

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)$，我们把它作为桶的大小，这样的好处是我们的最优解肯定不在某个桶内求得，而一定在桶间。

165. Compare Version Numbers

简单题，注意补零

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

182. Duplicate Emails

写了半天子查询，似乎不行。主要原因是必须要用到GROUP BY

SELECT Email FROM Person
GROUP BY Email
HAVING COUNT(Email)>1

SELECT Email FROM(
    SELECT Email, COUNT(1) as Num 
    FROM Person
    GROUP BY Email
) as e
where Num > 1

SELECT DISTINCT a.Email from 
(SELECT p.Email, COUNT(p.Email) as cnt from Person as p
GROUP BY p.Email) as a
where a.cnt > 1

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那条下手，用两个数组sell和buy分别表示第i天做至多j个行动的最大收益。写了一个O(nk)的算法，TLE了。most_trans表示第i天最多能做(i + 1) / 2个交易。

# i 从 1 开始
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
        # max(不买, 买)，注意必须之前卖了才能再买
        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
        # max(不卖, 卖)，注意必须之前买了才能卖
        sell[i][j] = max( sell[i - 1][j], buy[i - 1][j] + prices[i - 1] )

用C++改写了一下，发现k可能非常大，虽然后来将buy和sell优化成滚动数组，但还是开不了这么大的数组。于是发现当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。

195. Tenth Line

Linux命令，，简单题

198. House Robber

简单的动态规划。

199. Binary Tree Right Side View

简单题。

200. Number of Islands

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

201. Bitwise AND of Numbers Range

只要高位有进位，后面就肯定有0。只要有0，那一位AND的结果肯定为0。

204. Count Primes

求小于n的质数的数量，经过实测，n有至少499979的规模。因此打表的话就wa了。

205. Isomorphic Strings

同构，很范畴论了。现在要判断两个字符串是不是同构的。
办法很简单，我们用第一个字符串构建一个查询字典，如果出现冲突就不同构。
但是要正过来比一次，再反过来比一次。

206. Reverse Linked List

特别经典的链表反转问题，迭代方法借助prev和cur指针。这个方法的思想和一般动态规划不一样，它不是取一个通用的状态，而是类似于摘果子一样，摘一个下来，连上去。

prev -1> cur  -2> next -5>
next -3> cur  -4> prev -6>

题目还要求使用递归方法。

207. Course Schedule

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

208. Implement Trie (Prefix Tree)

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

209. Minimum Size Subarray Sum

双指针经典题，一定要会！
我好久不写了，WA了好久

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

222. Count Complete Tree Nodes

经典题，计算完全二叉树的最后一个节点。这道题其实就是比较左右子树深度。

223. Rectangle Area

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

228. Summary Ranges

题目给定一组已经排序好的整数，要求将连续的部分克兵成一个区间表示
这个我是维护每一个[fr, to]的区间，然后对每一个x二分出index表示x应该在index前面，接着查看能否将x贴到index - 1或者index上。最后查看能否合并index - 1和index。这里二分偷懒用了bisect_left，这里可以看出来。
不过其实这道题很简单，因为是排好序的，所以直接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时要求的值是根，否则递归右子树。

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的数量（之前以为不需要设的）。
当然这道题也有神奇的解法，具体还没研究

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的做法是计算得到两个链然后求交。但这么做需要有parent指针，这样才能倒着上溯回root节点。
一个通常意义的解法是离线的tarjan。Python的Hash啊，简直蛋疼，又不能自定义数据结构，解决不了并查集的问题。
用C++写了发终于过了，这里提醒一下，Leetcode的全局变量一定每次计算时要清空。

还有个很骚的解法，只对二叉树有用。我们直接在左右子树中都去找p或者q。如果左右子树各找到一个，那么返回树根；否则返回左子树或者右子树。如果p是q的祖先，这也没问题。因为这种情况，p还是和q在一个子树里面。不然的话，我们搜索另一个子树一定会找到q。除非就没有q这个节点，但和题目不符合。

if not root or root == p or root == q: return root
left = self.lowestCommonAncestor(root.left, p, q)
right = self.lowestCommonAncestor(root.right, p, q)
if left and right:
    return root
return left if left else right

237. Delete Node in a Linked List

我想应该是很无聊的一条题目，就是 nd.val = nd.next.val 这样。

238. Product of Array Except Self

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

239. Sliding Window Maximum

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

不妨想一想 dequeue 怎么做了：

1. 对于 4 5 这样的序列，只需要维护 5 就行。也就是当读到 x 时，可以从右边开始 pop 出来所有小于等于它的数 y。
2. 对于 5 4 这样的序列，需要同时维护 5 和 4，因为一旦 5 出去之后，4 就有可能是最大值。

240. Search a 2D Matrix II

二分，upper_bound 行，然后 lower_bound 列。

241. Different Ways to Add Parentheses

问怎么可以通过加括号，让一个包含+-*表达式，要求输出加括号能得到的所有值。
对于每一个 op，可以在两边加括号，从而进行分治。
于是这种题的思路是确定的，就是遍历每一个 op，并且用一个字典记忆左右两边能得到的所有值。
然后WA了，原来不能用set输出。。。

258. Add Digits

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

260. Single Number III

老题新做

263. Ugly Number

没啥好说的

264. Ugly Number II

定义Ugly Number是所有包含2/3/5为因子的正整数，求第n个。
本题需要 $O(n)$ 时间和 $O(n)$ 空间来完成。

想一开始用筛法预处理打个表，然而TLE了。也没发现能够从各因数的幂上发现子结构。

解决方案还是从$O(n^2)$的筛法上下手，原筛法是对第$i$个丑数，看看能从先前的丑数中进行更新得到的最小值。
这个过程存在很多冗余计算。例如在计算$ugly[i]$时，需要知道满足$x * 2 > ugly[i - 1]$的最小的$x$，显然不需要在所有$ugly[1..(i-1)]$遍历$x$。

不过发现每次使用$* 2$规则生成新丑数时，我们的$x$是严格递增的。递增很简单，因为新丑数比就丑数大，所以$x$要大。严格是因为所有的丑数都是偏序的。

容易写成类似于nth_ugly_number_wa的做法，这样不需要维护所有历史的res。打印出来就能看到，m2/3/5始终是乘自己作为质因数，肯定是不对的。

i  res  m2  m3  m5
1   2   4   3   5
2   3   4   9   5
3   4   8   9   5
4   5   8   9   25
5   8   16  9   25
6   9   16  27  25

做了第二遍，思路是：

1. 新的丑数是在老的里面选择三个数，ans[a2]*2、ans[a3]*3、ans[a5]*5 得到的。
2. a2/a3/a5 来自于历史的 ans。
3. 当 ans[a2]*2 被使用后，下一个通过 *2 获得的丑数，一定是从大于 a2 的位置获得的。

274. H-Index

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

275. H-Index II

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

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%，此外还有一个二分也值得一看，看起来我完全可以把二分的条件写得更严格一点，我当时是怕写出来不满足二分的性质了。

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__上，而应该打在全局。

line = lines.next()
n = stringToInt(line)
ret = Solution().numSquares(n)
out = intToString(ret)

注意，本题还可以使用四平方和定理进行优化。

282. Expression Add Operators

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

283. Move Zeroes

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

284. Peeking Iterator

简单题

287. Find the Duplicate Number

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

289. Game of Life

就是 Convey 的生命游戏要你算状态，但要求做成 inplace 的。
这个做法就是位运算一下。

292. Nim Game

简单的博弈论。
这题的点主要是比如 n = 8，则自己拿 1-3 个都可以转成对手面临 n=5/6/7 个时的状态。

295. Find Median from Data Stream

用两个堆来实现。

299. Bulls and Cows

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

300. Longest Increasing Subsequence

最长上升子序列模板题

301. Remove Invalid Parentheses

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

304. Range Sum Query 2D - Immutable

求一个不变的矩阵的某个子矩阵的和。由于不变，所以我们不需要用到线段树。
这一条要做到常数的查询复杂度，其实很简单。我们维护dp[i][j]表示(0,0)-(i-1,j-1)张成的矩阵的大小即可。
特别地，如果求最大权子矩阵的解法是$O(n^3)$的，详见红宝书。

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]。计算

310. Minimum Height Trees

Floyd一波T了。。。因为是无权的嘛，所以BFS咯、、、$O(n^2)$的BFS也T了，看来是$O(n)$的了，这让我想到834这道题。
细究下来这道题还蛮有意思的，首先需要明白MHT的数量只可能为1或者2。知道这一点，我们就不停地把叶子剥掉，这个过程有点类似于拓扑排序。

312. Burst Balloons

一条蛮久之前就准备做的题目了。就是打气球 i 的得分是 a[i-1] * a[i] * a[i+1]，如果 a[i+1] 不存在就 a[i+2]，直到越界就算 1。
这道题的话首先是DP如何维护状态，一般来说有用bitset维护的，或者去跟踪某个点i的状态，一个i就是一维，抑或去跟踪ANY/NONE/ALL这样的状态，抑或进行二分然后合并左右两个区间的结果，这样只需要考虑相邻节点的状态。
于是我首先推出方程，使用dp[L][R]维护打爆[L, R]处所有气球的最大值

for burst in [L, R]:
    dp[L][R] = dp[L][burst-1] + dp[burst+1][R] + nums[burst-1]*nums[burst]*nums[burst+1]

但我突然意识到我们是仅仅消掉burst，所以两边的burst-1和burst+1不能分治。那怎么办呢，且慢，好像有哪里不对劲。
反省一下上面的dp，我犯的最大的错误是认为消掉burst的得分和burst-1和burst+1有关，实际上这是不可能有关的。因为在这种假设下此时这两个气球应该是已经爆掉的，于是我们恍然大悟，应该和L和R有关啊。于是此时burst就是最后打爆的气球。
然后这一条如果DP的话因为是从[l, burst-1]和[burst+1, r]更新的，所以不能for l for r这样，比较好的是for l for len或者直接记搜。

313. Super Ugly Number

要求找到第n个Super Ugly Number。这个数的定义它的所有的因数来自给定一组素数prime，其中1是第一个。其中n是10**6的规模。这条和第264条有点像。
看上去我们可以维护一个最小堆，对于每一个新来的数，就依次乘上prime的每一个数，再放到这个堆里面。
这一条是用go写的，需要用到container/heap去维护一个优先队列，它实际上是一个最小堆。

315. Count of Smaller Numbers After Self

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

316. Remove Duplicate Letters

一开始想的是怼每一个字符维护一个harm和benefit表示为了减少害处或者增加益处需要保留下来的index。不过这个在样例阶段出现了错误，因为我们还需要考虑各个保留下来的字符之间的相对位置。其实这道题实际上是个贪心，我们试图将s逐一append到ans上，然后如果当前的x比ans[-1]要小，那我们肯定是倾向于用x替换ans[-1]的，只需要ans[-1]在后面还有备胎。

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的状态，加个剪枝就过了。。。C++还写WA了一发】
题目要求是在nums1和nums2中总共取k个数，然后进行归并，要求组成的数最大。这道题目一开始的思路就是枚举k，然后分别对nums1和nums2生成最大的数，最后进行归并。

1. 从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位置开始。
   实际上我们可以维护一个大小为req的栈，来表示这个最大可能的数。我们遍历数组A，对于每一个nums[i]，我们试图用它来替换最靠栈底的数，除非剩下来的数不够填满栈了。
2. 归并
   我们要注意当nums[i]和nums[j]相等时需要继续向后比较，如果当其中一个数列耗尽还没比较出来大小，那就选择另外的数列为大，因为另一个数列可能下面的元素就大了。例如[0]和[0, 6]。

322. Coin Change

这是一道完全背包的问题。完全背包朴素的状态转移是f[i][j]=max(f[i−1][j−k∗w[i]]+k∗v[i])∣0<=k∗w[i]<=j，但实际上可以做到O(VN)。
dp[i][j]表示只使用前i个物品，总价值在j时的最小数目。完全背包不一样的地方是对j的循环策略

for i in xrange(1, n + 1):
    for j in xrange(amount + 1):
        dp[i][j] = min(dp[i][j - coins[i - 1]] + 1, dp[i - 1][j])

而01背包是

for i in xrange(1, n + 1):
    for j in xrange(amount + 1):
            dp[i][j] = min(dp[i - 1][j - coins[i - 1]] + 1, dp[i - 1][j])

对于01背包而言，要保证f[i]全部是从f[i - 1]更新的，而完全背包需要复用一部分dp[i]的结果

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,…]的形式，然后考虑这个“新数列”。我们要让它的前半部分都大于中位数，后半部分都小于中位数。完了再映射回去。

自己做一遍，也就是将数组按照小于、等于、大于分成三段，然后按照偶数在前，奇数在后的原则映射成一个新数组。这个可以简单推得是 f = i/2 + n/2，也就是排完序后的数组的第 i 个元素要映射到新数组的第 f(i) 个元素。如果我们要一边排序一遍完成这个过程，那么显然得使用 f 的反函数。也就是 [0,1,2,3,4] -> [0,2,4,1,3]。
这又回到了之前的快速选择的问题上。不过这个做法还是有问题，例如[1, 3, 2, 2, 3, 1]的结果是[1, 3, 2, 2, 3, 1]，这个答案允许相等了，所以不正确，更好的是[1, 3, 2, 3, 1, 2]。正确答案需要三向快排来处理相同值的情况。与二向划分不同的是，三向划分虽然拥有l、r、eq三个指针表示小于等于大于三个边界。但它只使用一个循环，即用eq指针从前到后遍历数组，而不是使用两个指针相向移动。当遇到大于pivot的数的时候，就把它扔到r指针位置，并更新r。当遇到小于pivot数的时候就把它和l指针互换，保证l左边都是小于pivot的数。
但这个方案有一个不能处理的 [4,5,5,6] 的问题，它会输出为 [4,5,5,6]，但实际上它可以是 [5,6,4,5]。这里的做法是不应该按照偶数在前奇数在后映射，而是和题解一样是奇数在前偶数在后，并且按照大于、等于、小于三段进行排序。其实这里的区别就是中位数放第一个还是最小的放第一个。

326. Power of Three

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

327. Count of Range Sum

同样类似560，注意LL

328. Odd Even Linked List

这道题很简单，实际上是一个无状态迭代的过程，可以想象为不断地take 2 lst。注意判断None。我们实现一个函数

def solve(odd, even):
    return nxt_odd, nxt_even

329. Longest Increasing Path in a Matrix

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

330. Patching Array

【这道题很有趣】
首先我们计算nums中的数能够组成多少个和，我们对于每一个nums[i]，尝试加到集合中。
这道题没有思路，后来接受了一个Hint，也就是考虑miss为[0, n]中间第一个不能表示的数。然后是一个key observation，当我们能表示[0, miss)时，如果引入一个新的x，那么我们能够表示[0, x + miss)的数了。那么我们希望这个x等于miss，这样能够最大化利用率。

332. Reconstruct Itinerary

这道题之前好像在哪个微博上看到的，我还评论了一种可能的拓扑排序的做法。不过这道题目并不能这么做，因为我们可能重复到达某个机场（例如case2），因此并不存在一个特定的拓扑排序。当然，V是可以重复的，但E不会重复，也就是每张票都会用刚好一次。
那这道题就是一个简单的DFS么？也不是，虽然我们要求出发机场相同时按字符串大小选择目的机场，但这一切要建立在整个行程单存在的情况下！例如[["JFK","KUL"],["JFK","NRT"],["NRT","JFK"]]就应该选择先去NRT而不是KUL。
其实这是一个欧拉通路问题。Hierholzer算法其实就是个 dfs。

335. Self Crossing

给定一个长度为n的数组，表示分别向北、西、南、东走了多少铬，要求用一趟遍历和O(1)的空间去判断线路是否发生自交。
这一道题我完全不会，为啥复杂度能做到这么低呢？其实这是有限制条件的，因为我们每一步一定是有方向转换的，我们没必要考虑全局。而这个实际上只有三种情况。分别对应于和-3、-4、-5相交。
能不能和-1、-2相交呢？不可以，因为两个不在一个方向上。如果和-6相交（实际上是重合的情况），那么必然要和-5相交，同理，对-7也是这样。因此我们只要追溯到-5即可。具体地，我们是要追溯0和-3， 0和-4，0和-5的相交情况。
用了这个模板算cross，其原理也就是跨立实验。即以一条线段为标准，另一条线段的两端点一定在这条线段的两边。但互相跨立并不能解决共线问题，所以还需要继续快速排斥实验。

336. Palindrome Pairs

拿到题，想的是反向建Trie，然后对每一个终止状态判剩下的是不是回文串。然后我们对每个串遍历树，讨论到底是树短还是串短。对于树短，我们判断串多余的部分是否是回文；对于串短，我们dfs那个trie树，找到所有的合法路径。

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)

341. Flatten Nested List Iterator

用个栈维护一下

342. Power of Four

注意这一题是求是否是4的幂，而不是是否是4的倍数。这个很简单了，4的幂都是1(00)*这样的形式的

343. Integer Break

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

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

   // 这里k表示不超过k的整数
   dp[n][k] = dp[n - k][k] + dp[n][k - 1]

2. 将n划分为若干不同整数之和

   // 这里k表示不超过k的整数
   dp[n][k] = dp[n - k][k - 1] + dp[n][k - 1]

3. 将n划分为k个整数之和
   【经典讨论1的数量】

   1. 如果划分中包含1，相当于就是dp[n-1][k-1]，这个很简单
   2. 如果划分中不包含1，那么就将每个数都减掉一个1，得到子结构dp[n-k][k]，其划分数肯定是相同的

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

4. 将n分为k个整数的积，要求积最大，这也是最大分解问题

   dp[n] = max(dp[:k-1] * dp[k:])

   但是这一条有数学方法，主要可以考虑下面的性质：

   1. n的最大分解中不可能出现大于4的数
      反证法，如果出现了m大于4，那么可以用(m-2)和2替换m，得到的积是2m-4>m，矛盾
   2. 存在不含4的n的最大分解
      这是因为我们可以把任意的4变成2*2，而不影响结果
   3. 最大分解中，一定不会出现1
   4. 综合上面三点，最大分解中一定只含有2和3，并且2的数量只能为0/1/2
      这是因为3*3*3大于2*2

5. 将n划分为k个正奇数的和
   f[i][j]表示将i分为j个正奇数的和，g[i][j]表示将i分为j个正偶数的和。
   可以看出f[i-j][j] = g[i][j]，也就是将这j个奇数变成j个偶数。
   讨论两种划分：

   1. 包含1
      也就是从i-j中划分j个偶数g[i-j][j]
   2. 不包含1
      f[i-1][j-1]

347. Top K Frequent Elements

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

如果需要在线的，可以手写一个二叉堆，然后用一个map来索引堆中的元素。这里如何把非堆顶的元素移出来呢？可以让它和堆顶元素交换，把堆顶元素弄出来，然后重新整理堆。

我在里面写了个二叉堆的实现。

352. Data Stream as Disjoint Intervals

从一个流持续读取非负整数，要求随时输出当前所有整数构成的区间。这个有点类似于第228的Summary Ranges，但要求支持在线查询。
此外，还有一个Follow Up，问如果合并次数非常多，不相交区间的数目很少，应当如何优化？
应该是用一种树的数据结构来进行维护。我直接看题解了，原来使用红黑树进行维护。接着我们用类似于228的思想，查看是否需要合并左右区间。
此外，似乎也可以用并查集来做，我们使用并查集来维护每一个节点属于哪一个集合。剩下来的就是我们需要知道这个节点是否存在，这个可以借助于一个map来实现。
本题我是参照着题解用go实现的，主要涉及以下知识：

1. 自定义struct
2. 基于Node而不是数组实现的并查集，因为这条题目没有办法知道总的数据规模
3. 在并查集Merge的时候同时更新状态
4. 使用map，和用struct做结构的map
5. go里面的“指针”

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++里面的set和map啥的有lower_bound。使用二叉树之后反而更垃圾了。

368. Largest Divisible Subset

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

371. Sum of Two Integers

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

372. Super Pow

请移步Kickstart2017G题目A

373. Find K Pairs with Smallest Sums

这道题就是在[i+1,j]和[i,j+1]里面选一个

375. Guess Number Higher or Lower II

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

376. Wiggle Subsequence

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

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

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

381. Insert Delete GetRandom O(1) - Duplicates allowed

用O(1)的复杂度实现insert()、remove()和getRandom()。其中getRandom()要根据每个数字的出现次数来平均分配。
首先，既然需要随机，那么我们肯定要维护一个向量表，然后随机它的索引。既然如此，我们如何去对这个向量表进行动态增删呢？
主要问题就是删，这里可以借助于C++里面的库函数pop_heap的类似做法来实现，也就是说将要删除的元素和列表末尾的某个元素交换，然后再把列表末尾的元素给pop掉。为了实现这一点，我们就需要为这个向量表建立一个索引表
这个题目的insert和remove的返回值的要求很奇怪，WA了半天

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}$的概率替换掉已有的数。

386. Lexicographical Numbers

又是和数位DP类似的题目，各种WA。总结一下

1. 如果pos < ll - 1，那么从0一直dfs到9
2. 如果pos == ll - 1，此时我们在处理最末位。我们考虑目前的前缀prev
   1. 如果是一个不合法的前缀。我们更新prev考虑两种情况，第一个是原prev不合法，那么新prev也不合法；第二个是prev虽然合法，但是是满的，而当前的位超过了nums。对于不合法的前缀，我们不能往下dfs。
   2. 如果是一个合法的前缀。我们dfs到nums

387. First Unique Character in a String

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

390. Elimination Game

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

if actual_e != e:
    news = e // Or
    news = actual_e + step / 2
else:
    news = e - step / 2

391. Perfect Rectangle

给定一系列长方形的坐标，问这些长方形形成的覆盖，是否是一个长方形。注意，这里既不能漏掉，也不能重叠。
第一种做法 isRectangleCoverTLE 是先 O(n) 判断是否完整覆盖，在 O(n^2) 判断是否重叠，TLE 了。
第二种做法，同样是先判断完整覆盖，然后判断重叠用面积算，但这样不行。比如有两个 1x1 的小方块，我可以同一个算两次，而不是每一个算一次。

看到一个非常巧妙的解法：

1. 如果是完美矩形, 则四个角只出现一次, 其他的点成对出现。然后还要结合面积
2. 另一种做法是计算完整覆盖，不重不漏。但不能只计算边缘的线，还需要计算内部的线。

392. Is Subsequence

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

395. Longest Substring with At Least K Repeating Characters

每一个元素出现的次数都大于等于k。

思考：

1. 什么时候可以移动右边界？
   如果此时有合法窗口，并且移动右边界窗口依然合法，则可以移动右边界。
   如果此时有合法窗口，并且移动右边界窗口不合法，则可以移动右边界。因为尽管此时不合法了，但移动左边界只有坏处。
   如果此时没有合法窗口，并且移动右边界合法，那显然需要移动。
   如果此时没有合法窗口，并且移动右边界也不合法。此时移动左边界和移动右边界都有可能后续构成合法窗口。那如何考虑呢？
   我们显然无法一直贪心移动左边界，考虑 k = 2 情况下的 abbcca，如果我们过早地缩掉了左边界，会导致只能返回次优解。
   那么一直贪心右边界呢？似乎也不行，考虑 bbaaacbd。答案是3。
2. 什么时候可以移动左边界？

另一种思路是维护 l[x]、c[x]、v[x] 表示对于 x，它第一次出现的位置、截至目前出现的次数、第一次 valid 也就是数量大于等于 k 的位置。用 b[i] 表示在 [b[i], i] 之间的窗口是合法的。

这一条的理解方式是：我们要想办法去掉在全局中出现次数少于 k 的数。如果不存在这样的数，那么答案就是整个串。不然答案就是这些问题数的两边的数。

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等，我们发现这种情况下应当选择+。

// AC
elif (n & 3 == 3) and (n != 3):
    n += 1
else:
    n -= 1
// WA
elif n & 7 == 7:
    n += 1
else:
    n -= 1

398. Random Pick Index

维护个 map，没意思的题目

400. Nth Digit

居然打败了100%，这道题WA得好苦，其实细心一点就行

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，而不是用二维数组。

406. Queue Reconstruction by Height

这道题让我想起了315的那个树状数组的题目，其实这道题为了不T，还真的要树状一下。注意当有多个k符合条件的时候我们要选择h最小的。卧槽不仅要树状还要离散化。。。然后还是T了。
其实这道题应该是$O(n^2)$的，是一个类似插入排序的思路。

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] 了，但实际应该是 [2, 5] 和 [6]。用DP做，发现要求的是 min-max 在 i 位置在第 j 块的和。
这道题的 DP 做法同样是维护 dp[i][j] 为前 i 个数字分成 j 组的最小的子数组最大和。计算 dp[i][j] 时可以考虑将 i 位置放到前一块中去，或者新开一个块。因此递推方程是dp[i][j] = min(max(dp[i - 1][j - 1], nums[i]), dp[i - 1][j] + nums[i])，前面一部分是 append 上去，后面一部分是另起炉灶。
但这个递推式是错的，连题目给的样例都通不过。这是因为不能断定在 i - 1 时就是最优子结构，因此需要遍历所有的 dp[0..(i-1)][j - 1] 才行。
题解还说原来这条可以二分答案。。。。因为是非负整数。。。。唉，果然二分答案和记搜是拯救DP苦手的神器啊！

413. Arithmetic Slices

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

414. Third Maximum Number

水题，用个优先队列

416. Partition Equal Subset Sum

背包问题不解释

417. Pacific Atlantic Water Flow

据说是Google北美的面试题。所以你家你家现在输出又是[]不是[[]]`了，真的搞不懂。。。
这道题就是dfs两次啊，matrix需要预先包裹处理一下。注意填充的初始值是-1而不是0，因为有0的cell。

419. Battleships in a Board

这是一条 dfs 求连通分量。Followup 要求用 one-pass，常数空间，并且不能改棋盘。
这也很简单，直接看是否和上面或者左边连通就行。

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移到不等号的右边。

427. Construct Quad Tree

给定一个N*N的矩阵，N是的幂，要求构造一个四叉树。递归搞一下就行了

434. Number of Segments in a String

简单题

435. Non-overlapping Intervals

TODO
给定一些区间，问至少移除多少区间，才能让它们彼此都不重叠。
这道题看起来就是一个贪心。我尝试以每条线段和其他线段的overlap的次数做参考，每一次选择次数最多的线段删掉。但是这样会WA在\[\]\[\]int\{\{0,2\},\{1,3\},\{1,3\},\{2,4\},\{3,5\},\{3,5\},\{4,6\}\}这个case上面。
猜想是重复的问题，于是我尝试去重，结果倒在倒数第二个case上面。那个case真大，希望后面能找到一个简洁的反例。。。。
最后解决方案是按照右边界排序，然后贪心过一遍就行。
其实我觉得这一类区间Interval相关的问题，一般都会涉及按照左端点或者右端点进行排序。

436. Find Right Interval

看不懂这一题想干嘛，题目都是错的。

437. Path Sum III

建一棵和树st，然后dfs这个树，并且按照类似560的办法维护一个哈希集。
WA了蛮多次，都是粗心，比如说要有d[need] > 0的判断，和+= d[need]而不是+=1。

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，那么我们就将x与y交换，这样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。

448. Find All Numbers Disappeared in an Array

简单题，类似于442题

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)$。具体做法看我源码里面的注释。

459. Repeated Substring Pattern

很好地简单题，细节蛮多的

462. Minimum Moves to Equal Array Elements II

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

463. Island Perimeter

这条不需要DFS哦

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剪枝一起使用。

466. Count The Repetitions

[s1; n1] 表示重复 s1 n1 次。
求一个最大的 m，使得 [[s2; n2]; m] 是 [s1; n1] 的子序列。
一个观察是 aaaa 需要由很多个 a 得到。所以 s2 未必是 s1 或者 [s1; 2] 的子串或者子序列。

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

二维费用背包模板题

475. Heaters

476. Number Complement

还是得while x >>= 1一下的。。。

477. Total Hamming Distance

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

478. Generate Random Point in a Circle

如果去sample一个圆周，很简单，那么如何sample一个圆呢？
最简单的方法是所谓的rejection method，我们去sample圆的一个外接正方形是容易的，然后我们while掉在圆外面的点即可。
但其实我们可以通过修改sample圆周的方法来解决这个问题，令随机量为$u$，我们也就是将$r = R * u$改为$r = R * \sqrt{u}$即可。为什么其sqrt，其原因很简单。因为对面积均匀划分，我们实际上要$\pi r^2 * u$是要得到这样的一个均匀的统计量。化简一下就能得到一个根号了。

480. Sliding Window Median

这个得用C++做，其原理是利用multiset的动态排序功能

481. Magical String

一个很有趣的问题。给定序列1 22 11 2 1 22 1 22 11 2 11 22，我们统计连续数字的长度，得到如下的序列1 2 2 1 1 2 1 2 2 1 2 2。发现这两个序列是同构的。现在要问前N(N<100000)里面有几个1。这个可以顺着推出来，类似DNA转录那样，我们双指针维护一个转录列表指针和读取指针即可。

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

【本题是AlphaBeta剪枝暴力掉的，但可以DP】
两个人轮流从数组两端取数字，和最大的胜利。数组最长为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值，也进行剪枝。
对于本题，剩下的工作就是选取一个适合的评价函数，这里选取两者和的差即可。

491. Increasing Subsequences

【不使用set如何做呢？Leetcode上似乎有一个Discuss】
用一个set来维护已有的上升序列，对于i位置的考虑能否扩展set中的序列。注意需要去重，这里用了一个很投机取巧的办法，虽然Python不能序列化list，但是可以序列化str或者tuple，所以。。。
不过下面我们来考虑普通的DFS的方法，我们如何来去重？一开始我想的是根据长度和最后一个元素来去重，认为以某个元素结尾的固定长度的递增序列是固定的。

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。不过还有一个特殊情况就是在矩阵四角，两个速度分量都会导致出格。

502. IPO

一开始有W的钱，用它在n个项目里面选k个来做，项目i需要C[i]的启动资金，带来P[i]的纯利润，问最后能够达到的最大的资本是多少。
用两个PQ维护一下就行了。

503. Next Greater Element II

数组复制一遍，然后对于每一个元素如果比栈顶小就入栈，否则就出栈

504. Base 7

简单题

513. Find Bottom Left Tree Value

BFS即可

514. Freedom Trail

很明显是DP，用dp维护准备填入i字符时轮盘指向j的最少步数，那么对于每一个(i, j)，我们查看所有的k到j的最短距离。这里要注意一下最短距离是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。
而最长的回文序列的长度有两种情况：

1. 从[0,i] 和 [i+1,n-1] 得到，那么结果是 dp[i][i+1]。
2. 从[0,i] 和 [i+2,n-1] 这样的，也就是说长度是奇数，中间夹了个 arr[i+1]，这种结果是dp[i][i+2] + 1。

注意初始化的时候应该首先将dp设为0，而不是1，然后预先计算dp[0][j]和dp[i][n-1]。
最后是求 max。

517. Super Washing Machines

emmmm，洗衣机，让我想到某次区域赛的赛题。题意是有n个洗衣机，里面衣服的数量用一个数组machines表示。每一次行动时，需要选择任意的m个洗衣机，同时将每个洗衣机中间的一件衣服移到相邻的洗衣机中。要求输出使得每个洗衣机中衣服数量相等的最少的移动次数。每个洗衣机里面最多有1e5件衣服，最多有10000个洗衣机。从数据规模上来看，无法维护每一个洗衣机的状态。
其实，可以算出最终一个洗衣机里面要放多少衣服，因为衣服是要逐个洗衣机进行移动的，所以可以统计每一个洗衣机左边和右边分别有多少衣服，就能知道这个洗衣机要执行多少次移动操作了。问题是，但是这里面有多少移动操作是可以并行执行的呢？
我们可以算得lb[i]表示洗衣机i左边还需要多少衣服，rb[i]表示右边还需要多少衣服，m[i]表示i当前有几件衣服。如果m[i] > 0 && lb[i] > 0，那么则可以进行一次向左移动，m[i] > 0 && rb[i] > 0则可以进行一次向右移动。那么，只要能整除，就一定能达到最后的解。这个解法T在第105/120个TestCase

题解是O(n)的，很神奇。从左到右遍历数组，维护一个balance是累计和，表示到现在为止，需要向右边拿/然后，还要考虑每个洗衣机都要送多少衣服，这个也要最大值。我们不考虑每个洗衣机要拿多少衣服，因为它可能从不同的洗衣机拿衣服，例如我们取Abs，就会WA在[9,1,8,8,9]这个case上面。上面两个检验是必要的，但为什么是充分的呢？TODO

518. Coin Change 2

见343

521. Longest Uncommon Subsequence I

最长的非公共序列。
如果两个串不等，那么选择较长的串肯定是可以的。
如果两个串相等，那一定不行。

522. Longest Uncommon Subsequence II

需要认识到，LUS 在给定的 string set 里面，例如 abcde/abdce/abdec，还是可以取 abcde。
直接暴力过了。

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中的某几个字符得到。

525. Contiguous Array

用C++做，本题可以规约到560这种形式

526. Beautiful Arrangement

记搜

528. Random Pick with Weight

让我想起了382的那个水塘抽样算法。这道题实际上是有放回的，所以很简单。直接二分累积和，找最小的大于ran的self.r[i]。其中ran = random.randint(1, self.r[-1])，注意不是1，因为至少要取一个。

539. Minimum Time Difference

简单题。

540. Single Element in a Sorted Array

异或的基本性质。
不过也可以二分做。

546. Remove Boxes

有点像312那条打气球的题目和488的Zuma球。这条裸DFS显然会T，如果使用普通的记搜，下层递归如何处理由于上层递归中的某个Box被移除导致两边颜色相同的Box连起来的情况呢？我们如果记录一下哪些Box被移除了，那我们status的长度最多是100位，这肯定是要爆的，所以我们得想想用其他的东西来描述状态。
在另一方面，根据经验，使用dp[l][r]维护一段区间内的最优解是容易想到的。进而我们想到dp[l][r]的最优解一定是盒子被全部移除之后的（否则我们总可以再移除一个盒子以得到更优解），而在dfs(l, r)前这段区间里面的Box都是存在的。于是我们实际上就可以特判一下L[take-1][0]和L[take+1][0]是否相等然后做个合并就行了。但这样是错误的，因为我们是二分的区间，只切一刀，这样无法得到下面这种情况的最优解。

(1,1) | best_solution | (1,1)

因为无论我们这一刀切在哪里，中间的best_solution都会错误地和后面的(1,1)做合并。于是我们

(1,1) | not_best_solution

于是我们的应对之策就是在枚举一下第一刀切在哪里，不过这个做法也不行，我们看下面的样例，正解应该是14。但是我们切两刀也是不行的，于是乎发现这道题似乎不能靠切。。。

1, 2, 2, 1, 3, 1

所以最终结果是这一条我不会。。。看题解，dp[l][r][k]表示有k个后缀和nums[r]一样的情况下l到r得分最大。于是我们有两种case，将L[r]和后面的k个合并，或者将L[r]和某个l <= pos <= r合并。
https://leetcode.com/problems/remove-boxes/discuss/101314/C++-29ms-dp-solution!

547. Friend Circles

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

552. Student Attendance Record II

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

# 第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%的人，感觉写的常数很大啊。
mx和mi维护了区间[i,j]上的最大值，计算这个枚举分割点k就可以了。WA了一次是因为可能不分割，例如[6,2,3,4,5]应当是6/(2/3/4/5)，后面的2,3,4,5不需要分隔。
我们还要返回一个具体的括号方案，这个就使用pmx和pmi来维护两边的字符串，注意当只有一个数字的时候不要加括号。

554. Brick Wall

556. Next Greater Element III

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

560. Subarray Sum Equals K

这是类似Two sum一类的Hash经典题，我们要求是否存在j使得sum[i]-sum[j]==k也就是求对于任意的i，是否存在sum[j]==sum[i]-k

561. Array Partition I

排序一下，然后就是结果。。。

576. Out of Boundary Paths

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

581. Shortest Unsorted Continuous Subarray

挺有意思的一题。找一个子串，只需要排完这个序列，那么整个序列就是有序了。
设该串 a[l:r]，bound 为 L 和 U，则可以发现性质：

1. a[:l-1] 有序
2. a[r:] 有序
3. a[l-1] <= L <= U <= a[r]

还有几点直觉：

1. 两个有序的串，可以组合成一个无序的串，如 [3,4,1,2]
   这也就意味着如 [2,3,4,1] 这样的串，尽管左边已经是有序了，但最终我们还是要重新排序整个串。
   而诸如[1,3,5,6,4]，只需要重排 [5,6,4] 就行了。
2. 如果两端的数比较拉胯，那么排序会很麻烦
3. 单调栈的问题是 [3,4,1,2]，在处理完 1 之后，2 会漏掉，因为此时栈里面是 1 了。

综上的一个想法是，当遇到第一个有问题的数时，可以比如二分找到第一个比它小的数字，然后后面的数都需要重排。例如 [1,3,5,6,4]，需要从 5 开始重排。而 [1,3,5,6,4,2]，需要从 3 开始重排。但这个想法解决不了 [2,6,4,8,10,9,15]。

新的想法是：

1. 理论上每个 x 都要大于它左边所有的数。
2. 但我们不能维护一个全局最大值，不然 [2,3,4,1] 是2。

看题解，发现这是个逆序对有关的问题：

1. 从左到右遍历，对于每一个 x，找到 x 左边第一个比它大的数。因为用单调栈维护，所以栈中是递增的。找到的也是从左边起第一个和 x 逆序的元素。

583. Delete Operation for Two Strings

最短编辑距离模板题

594. Longest Harmonious Subsequence

找最长的子序列，要求序列中的值的差为1。简单题。

600. Non-negative Integers without Consecutive Ones

无脑数位DP

605. Can Place Flowers

简单题，注意边界情况

611. Valid Triangle Number

首先sort一下是肯定的。枚举i、j二分最后一个长度，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])的，否则会重复计算。

617. Merge Two Binary Trees

简单题

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，设这两个任务为A和B，各有most个。那么根据上面的结论最优解是ABXXXABXXXABXXXAB，其中X首先用其他的字母填，不行了就得补空。

629. K Inverse Pairs Array

从 1 到 n，有多少种办法排列，得到正好有 k 个逆序对？
限制：

1. n-1 的情况，可以缺 0..=k 个逆序对。如果一个不缺，那么 n 放最后就行。
2. 但 k 未必能取到。最多缺 n-1 个逆序对。因为即使将 n 放到最前面，也只能新增 n-1 个逆序对。这也意味着，dp[n-1] 至少要有 (k-(n-1)) 个逆序对。

因此要累加的是 dp[n-1][k-n+1:k]。WA 了一次，原因是 n、k 和 i、j 没区分。
不过这个立方复杂度的算法 T 了。改成累加和就行。

662. Maximum Width of Binary Tree

BFS

630. Course Schedule III

首先想到的是区间段问题，首先是不停地贪最早的结束时间，果断WA了一波。后来我意识到这个问题结束时间是由起始时间来动态调整的，我们不妨反方向，从结束时间开始贪，每次希望找开始时间最晚的课程。然后又WA了一波，Case是[[9,14],[7,12],[1,11],[4,7]]，我第一步贪的是[1,11]，但实际上[9, 14]更好。这个原因不在于区间段的问题的解法是错的，而是我们不能认为每个课程从结束时间就是最优的，对于[1,11]这样的课程，它的性能非常好，它固然能用来替换[9,14]以最右化右边界，但是更好的去处是到最前面。
这道题还和最长上升子序列有点像，不过最长上升子序列有个固定的取用顺序，但是这道题没有。
题解借助了优先队列。每一次我们的课程X不能满足deadline时，我们取出长度最长的课程Y，并用X替换Y。容易看出这一道题其实和开始时间无关，我们应该上完一门之后立即上下一门。

632. Smallest Range

638. Shopping Offers

这个就7**6个状态，很好做hash，所以直接记搜。

641. Design Circular Deque

设计环形队列

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

652. Find Duplicate Subtrees

简单题，Hash一下子树即可

654. Maximum Binary Tree

这也太简单了吧，，，我还以为会有重复的元素然后两种树有个大小的比较呢

657. Judge Route Circle

弱智题

658. Find K Closest Elements

给定一个有序数组，要求找到第k接近x的数，其中x不一定出现在数组里面。
初步想法是先二分搜索，然后分能够找到（一个或多个）x和不能找到x两种情况进行讨论。

659. Split Array into Consecutive Subsequences

这道题我一开始就是用tail[i]维护所有以i结尾的序列。tail[i]是一个优先队列，里面存放着所有序列的长度，每一次我们遇到值x时就tail[x] = tail[x-1].get()+1，也就是增长tail[x-1]中最短的一项，结果T了。
用C++写就能AC。。。

664. Strange Printer

【这题Python目前还是T】
这道题蛮有意思的，我用Python的$O(n^3)$T了，但是C++的过了。首先不难想的是用dp[fr][to]来记录从fr到to的次数，然后我们从2开始枚举step，然后对每个位置的fr对应的to = fr + step计算dp[fr][to]。我们也容易知道dp[i][i] = 1，dp[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

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

673. Number of Longest Increasing Subsequence

令dp[i][j]为以i结尾的长度为j的自增序列的个数，则
$$
dp[i][j] = sum(dp[k][j - 1]) for k in [0, i) if nums[k] < nums[i]
$$
朴素的DP是$O(n^3)$的会T。
然后我们可以想到一个优化方案，也就是去掉j这个维度，这样可以做到$O(n^2)$，因为我们发现我们不会从j - 2去更新j。

674. Longest Continuous Increasing Subsequence

简单题

684. Redundant Connection

无向图删除连通图上唯一多余的一条边，这个很简单，并查集维护一下每条边的两个顶点即可。
注意我一开始想使用DFS三色法来解决，但实际上这个是不行的，因为我们要输出最后出现的边。

这个思路常常被用在最小生成树的Kruskal算法中。这个算法将边按照权值从小到大排序，然后贪心地选择。如果被选到的边能和既有的子树成环，则放弃。因此需要快速判定一条边是否成环。这就用到类似的做法。

685. Redundant Connection II

从无向图改成有向图就难了很多，这道题我们要根据是否成环（至多一个环）和是否有点入度为2来讨论。

687. Longest Univalue Path

DFS一下咯

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可以当右括号用了。

696. Count Binary Substrings

简单题

698. Partition to K Equal Sum Subsets

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

699. Falling Squares

离散化+线段树，和218很像。可以直接套218的模板，顺便还发现218里面Query有个地方写错了，幸亏那个是改线查点，所以没有WA。这道题需要注意的是Case 2那样两个正方形共边的情况，我们可以对于正方形[l,r]查看[l+1,r-1]的最大值，但是对于l >= r - 1的情况，我们需要特殊处理下，看它能不能放在[l-1,r+1]上。这道题居然击败了96%。

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。
第二种方法是使用滑动窗口来直接算，这个方法需要小心避免重复计算的情况。

728. Self Dividing Numbers

一个 self dividing number 表示它可以被自己的每一位整除。返回 [left, right] 之间所有的数字。
我是打表过的。总感觉这个可以用什么 dp 的办法做。

729. My Calendar I

首先是看到732，然后回来看得这一条。这一条一看就是个线段树，但是这条比较蛋疼的是要离散化，而且是在线的。这里借鉴了732 Discuss里面的做法，用指针来维护，这样就不要4N的开销了。
这里注意在query时如果没有子节点需要返回root节点的值，可以查看样例\{\{6,14},{0,7\}\}。因为在update的时候，如果一个节点下面的结果是一致的，类似决策树里面，是“纯节点”，那么会剪枝掉下面的子树。需要将这种情况和因为update时没有覆盖到对应区间所以直接没有这个子树的情况区分开来。

if(!root->left && !root->right){
    // IMPORTANT
    ans = root->data;
}

730. Count Different Palindromic Subsequences

还在上学时尝试过，不过当时就做挂了。一开始想到516题，但这道题需要去重，如样例1所示。
这题是子序列而不是子串。并且只能取 abcd 四个字母。

732. My Calendar III

这一题是对一段区间的值+1，然后查看一个区间中的最大值。这属于查线改线的，所以需要lazy。
不过根据样例，上面的思路还是有问题的，如下图所示，简单得求最大值的算法，得到的结果是2，而这个区间实际上和两个独立区间重合，所以结果应该是3，这种错误的解法在leetcode.732.1.cpp。

|-------|         |--------|
      |--------------|

735. Asteroid Collision

从后往前扫一遍即可

738. Monotone Increasing Digits

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

739. Daily Temperatures

直方图那条吧，水题

740. Delete and Earn

简单DP

741. Cherry Pickup

从地图的左上角到地图的右下角，再从右下角到左上角。问最多能摘多少个樱桃，地图上有障碍。地图是方的。
这一条不是 bruteforce dp 的原因是它需要返回。进一步可以想到，这个问题可以转化为走两次，求最大值。
感觉可以第一遍 dp 之后，第二遍 dp delta。发现好像 delta 不是那么好求。
然后觉得这道题是可以贪心的，然后被打脸了。。。

1 1 1 1 0 0 0
0 0 0 1 0 0 0
0 0 0 1 0 0 1
1 0 0 1 0 0 0
0 0 0 1 0 0 0
0 0 0 1 0 0 0
0 0 0 1 1 1 1

看题解，知道它怎么做 delta 的了，也就是可以想象成两个人同时从左上角出发，然后找 dp[x1][y1][x2] 最优解。如果发现走到同一个格子，就只能算一个人捡到了。 从这个思路来，可以写得很简单。注意需要判断 y2 = x1 + y1 - x2 是否合法。
本题 dp 数组可以开大一点，这样就不需要判断边界了。

743. Network Delay Time

看题目就猜到了这题是干什么的。裸dijkstra，注意是有向图。。。

747. Largest Number At Least Twice of Others

简单题

753. Cracking the Safe

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

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

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

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。

765. Couples Holding Hands

这道题其实可以贪，还有一些并查集的做法，是一道好题目

766. Toeplitz Matrix

简单题，Pick One太差劲了。。。

767. Reorganize String

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

768. Max Chunks To Make Sorted II

题目是将一个int数组切成若干块，并且对每个块进行排序，我们将排序好的块再次按顺序连接起来，应该能够得到一个有序的数组。那么我们最多能切成几块呢？这种序列的题目，我们往往能够联想到直方图问题和逆序对问题。
这道题比769要复杂一些，首先arr[i]的值域变到了10**8，我们不太方便用树状数组（当然我们可以离散化）来做了。其次，增加了一条限制是可能出现重复项。
我一开始的想法是sort一下数组变成lst，这时候lst[i]实际上就是lst[0..i]上的最大值，那么当lst[i]和arr[i]相等时可以认为i前面可以通过一次sort来变得有序了。但这个假设实际上是错的，我们考虑[1,1,0,0,1]这种情况，由于重复元素的出现，我们无法通过这个条件来判断arr[i]应当位于已排序数组的哪一个位置。即使我们维护一个mx表示arr[0..i]的最大值，然后要求arr[i] == mx == lst[i]也不行，可以考虑[0,3,0,3,2]的情况，下面错误的代码会输出3而不是正确答案2，这同样是重复元素的锅。

def maxChunksToSortedWA(self, arr):
    n = len(arr)
    inf = 5555555555
    ans = 0
    lst = sorted(arr)

    mx = -inf
    for i, x in enumerate(arr):
        mx = max(x, mx)
        y = lst[i]
        if mx == x:
            ans += 1

    return ans

然后这道题解法出奇的简单，我们维护lst和arr的前缀和，然后统计他们在对应位置相等的数量即可。
【后面还有线性解法】我们维护i位置遍历到的最大值left[i]和未遍历的最小值right[i]。我们知道有序数列lst[i]的左边肯定没有比他大的数，右边没有比他小的数（但可以相等），也就是right[i] >= lst[i] >= left[i]。对于乱序数组arr[i]，我们希望将到i的部分割出来进行排序，这样肯定是安全的，因为i右边不存在比left[i]要大的数了。也就是需要max(left[i], arr[i]) <= right[i]，注意我们这里不需要right[i] >= arr[i] >= left[i]这么强的条件，因为可以通过对(?, i]区间的sort来满足arr[i] >= left[i]这个条件。
【此外还有一种单调栈的解法】单调栈具有线性复杂度，并且一趟遍历，也就是每个元素只会一次进栈。通过单调递增栈可以找到当前元素左起第一个比自己小的元素，也就是当前栈顶。如果当前元素比当前栈顶小，我们就一直进行出栈操作。那么维护一个单调递增栈，它其中的元素数目表示遍历到当前数字前，可以拆分成块的数目。因为一旦出现一个数使得这个栈不单调了，我们必然要进行一次排序。

注，文章中列出了这道题的四种解法，还是很有趣的一条题目。

769. Max Chunks To Make Sorted

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

732. My Calendar III

733. Flood Fill

简单题

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即可。

777. Swap Adjacent in LR String

任意次数反转某个区间，问能够得到目标串。

778. Swim in Rising Water

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

779. K-th Symbol in Grammar

一开始以为是个DP，后来发现这样不就直接生成答案了吗，而且这个依赖状态也有限，所以直接DFS了。这道题就是想第n行怎么从第n-1行过来，然后就很简单了。

780. Reaching Points

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

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，设其vis为1，表示在二分图的一边，那么它能访问到的所有nxt的vis一定是-1，表示在二分图的另一边。那么一旦我们找到一条边其vis与nxt相同，那么就不可能是二分图了。
注意二分图可以是不连通的，所以我们应当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/3比2/4大。

790. Domino and Tromino Tiling

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

795. Number of Subarrays with Bounded Maximum

这道题蛮有意思的，我们还是用了在题目【】中防止重复统计区间的办法，也就是对于i，我们统计以i为结尾的合法区间数。接下来分三种情况讨论即可，我WA了很多次，都是因为没有考虑周全所致。

796. Rotate String

复制一份即可，简单题

797. All Paths From Source to Target

简单的dfs

799. Champagne Tower

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

801. Minimum Swaps To Make Sequences Increasing

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

802. Find Eventual Safe States

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

803. Bricks Falling When Hit

很有趣的问题，n行m列的墙上有砖头靠四边和天花板连在一起。现在有Q次查询，要求输出敲掉(i,j)之后会掉落多少块砖头。
首先莽了一个DFS的，也就是直接模拟，对于每一个格点，DFS它能不能到天花板。T了之后优化了一下，从每个天花板DFS看能不能到达，然后check所有不能到达的节点，还是T。
后来想到可以反过来考虑这个过程。
是机械的时候WA翻了。首先我们敲掉的那个砖块不算掉落的，但是我们在处理的时候是将(hx, hy)周围的所有点进行merge的，我们在一些时候不能直接进行d -= 1，例如当(hx, hy)在天花板上，或者已经连到了天花板上，那我们merge的时候实际上就没有算上(hx, hy)，自然也没有必要减掉了。锤子可以空敲，所以我们不能凭空往上面加东西。WA了一次是因为DFS时候没有初始化fa。WA了一次是因为并查集merge的时候，没有判断pfa == qfa的情况。最后一次WA是在第15个点上，调试了半天，把hits简化到了[[1,4],[1,6],[0,2],[0,5],[1,5]]。原来错误是我们要考虑天花板上的砖块被敲掉的情况，例如[[1,0,1],[1,1,1]], [[0,0],[0,2],[1,1]]这个Case，如果不经过处理就会WA。我当时是选择在添加这个天花板上的(hx, hy)时DFS一下，构建以(hx, hy)为基元的并查集。但在这第15个点上就发现这个方案不行。因为这个Case中我们先添加了(1,5)，然后添加了(0,5)，这时候DFS一下就会直接将(1,5)添加到(0,5)的集合中了。

805. Split Array With Same Average

如果是和相等而不是平均数相等，那就是一道背包问题，因此我们的思路一是能不能转化为len(A) / 2个背包问题来做。于是我们的问题变为是否存在有恰好m个数的和加起来为need。这个实际上就是01背包，然后在dp数组上dfs找是否有一条到(0, 0)长度为m的路径，可参考这篇文章的track方法。

此外，本题还有其他解法，如https://xingxingpark.com/Leetcode-805-Split-Array-With-Same-Average/

807. Max Increase to Keep City Skyline

这个很简单，维护一下行列的最大值

808. Soup Servings

记搜呗，概率正推，期望逆推。注意虽然我们数组开不了那么大，但是我们可以默认在N很大时概率趋于1。这道题需要按照25离散化一下，不然会MLE

810. Chalkboard XOR Game

组合博弈咯。。。我们知道必败态P的下一步一定是非必败态，而非必败态存在下一步是必败态N。我们研究最简单的必败态1，非必败态1,1，因此先手者只要保证自己手里的数字都是成对的就行了。当然如果果然这样那么先手者直接赢了，因为XOR下来就是0。当然肯定有成单的，我们只要保证成单的也是偶数个就行了。
然后发现这道题还要特判一下[1,2,3]这种一开始XOR下来就是0的。因为我们要考虑成单的数异或起来是不是为0，因为我们担心像前面多个数异或起来为0的情况，例如1^2^3==0这样会不会影响结果。我们先考虑成单的是偶数，但是Alice先手会输，也就是说当Alice取了数x之后，剩下的XOR起来为0了，例如[1,2,3,4]，取了4，剩下的为0，因此我们肯定不能取这个4，而应该取那XOR起来为0的奇数个数中的一个数，我们可以将这奇数个数的异或等价为两个相同的数a ^ a == 0，因此我们取走任意一个a != x，就会给对手留下奇数个成单的数，并且XOR的值非0这样的情况，这肯定是对方的一个必败态。
下面我们需要注意在成单的是奇数个的情况下我们是可能赢的，当XOR起来为0的情况，这个只可能发生在一开始，因为往后我们不可能给对方留下这个状态，除非我们自己是必输的。

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这条。

814. Binary Tree Pruning

在微软的面试题，注意要去掉没有儿子的节点

815. Bus Routes

这道题的关键在于要对Stop和Routine同时建立vis数组维护。

818. Race Car

首先我们的翻转方向一定要尽可能在前面，因为$2^i - 2^{i+1}$是小于0的，而$2^i - 2^{i+1} + 2^{i+2}$是超过$2^{i+1}$的，因此如果我们追求在$2^i$和$2^{i+1}$之间的值那么我们递归的深度是有限的。然后看清题目我发现R会重置速度绝对值为1，这道题就有点类似于650这种题目了，但我们同样要知道最多加速的次数是有着固定的上界，也就是我们最多走到$S = 1 + 2 + … + 2^i \ge target$，不会再往后面加速了。现在我们得到DP的思路，也即是我们在这个$2^0$到$2^i$的加速区间内我们可以在任何时候选择R然后重新来过。一开始我分为两种情况，第一种我们先走过target，然后R回来变成子问题。另一种我们在中间任意的时刻连R两次，将速度减少为1，我们稍后看到第二种情况是不全面的，因为我们可以以退为进一段，而不需要连R。
一个难点是target=5的情况，它的结果并不是我之前算的8而是7，也就是AARARAA，究其原因是因为我们从3到5时不能直接套用dp[2]，因为我们在3处的前进方向不同了。

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 1 1
1   1
1   (0)
1 1 1

828. Unique Letter String

看起来是个双指针维护，然后我们同样是按照r坐标来计数以防止错漏。我们知道一个显然的性质，如果在[l, r]区间中没有任何重复的元素，那么这个区间的输出是(l + r) * (r - l + 1) / 2。如果我们考虑在[l, r]中存在一个old_i使得S[old_i] == S[r]（我们可以使用一个哈希表来维护这个性质），那么我们可以将区间分为[old_i+1, r]和[l, old_i]来计算。现在的问题是，如果这个区间中出现了不止一个的重复元素怎么办？
我们注意到在任意的区间中如果字符x出现重复，那么它对整个结果都没有贡献，因此我们可以围绕每个字符来做，也就是求每个字符contribute多少次自己。

829. Consecutive Numbers Sum

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

834. Sum of Distances in Tree

求一棵树上每个端点到其他端点所有距离的和。一个朴素的肯定会T的方法是维护一个数组dist[N][N]表示从点X到Y的距离，那么就可以对每一个点X来DFS一下，是平方的复杂度。优化的方案来自一个观察，也就是两个节点之间的最短路径是唯一的，并且一定会经过两个节点的LCA。因此可以引入第二个观察，也就是说给定一个遍历顺序，例如从X到Y，或者从Y到X，那么子树的数量是固定的。那么其实我们只需要两次DFS就行了。
下面就很简单了，比如我们从X遍历到Y，那么从X到Y的所有孩子的距离等于从Y到它所有孩子的距离（这是一个子问题），再加上孩子的个数。

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[]表示每个L或R向两边传播的“力”的大小，例如R...就表示成[1, 2, 3, 4]，不过这没卵用。后来发现我们可以通过简单的判断每一个.到两边的L和R的距离来判定这个.究竟倒向谁。然后我们要讨论几个特殊情况，因为有的时候骨牌不能往左或者往右倒。我们考虑i能否向左倒：

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

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

840. Magic Squares In Grid

我特么看成行列对角线和相等了，，，还有个distinct的条件要考虑

841. Keys and Rooms

判断一个图是否是连通图

842. Split Array into Fibonacci Sequence

这个就暴力枚举下fst和snd，然后check就行了。注意范围是int，并且fst和snd的大小没有要求。

845. Longest Mountain in Array

找到数组中最长的山。
有几种情况：

1. 上坡：需要 arr[i] > arr[i-1] 且 arr[i] < arr[i + 1]，上坡必须要求左边有元素
2. 山顶：需要 arr[i] > arr[i-1] 且 arr[i] > arr[i + 1]，山顶必须要求左右都有元素
3. 下坡：需要 arr[i] < arr[i-1]

这道题目有很多 corner case 需要注意，主要是可能取等号的问题。实际需要定义：

1. is_valid_peak，必须不位于边界，并且大于两边
   只有前面的序列中有 valid peak，才能通过下坡来更新 ans。
2. is_peak，只要大于等于两边就行。在边界的时候，只要大于等于一边就行
   记录 peak 的原因是找到第一个上升点。这很简单，如果之前已经经历过 peak，那么后续就应该全部是下降。需要注意，不能漏掉平台。

846. Hand of Straights

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

847. Shortest Path Visiting All Nodes

要求最短的汉密尔顿通路，但不要求只访问一次。此外网上有解法是Floyd+松弛，对S*V的这个状态空间进行遍历并松弛。要注意这里不能再Floyd之后直接记搜，除非在Floyd要维护一下mask的情况。

848. Shifting Letters

简单题

849. Maximize Distance to Closest Person

简单题

851. Loud and Rich

给定一个偏序关系richer[i] = [x, y]表示人x比人y要富裕。给定每个人一个quiet[x]值。对于每一个人，找到所有钱大于等于x的人中quiet值最小的人。所有人的quiet是不同的。
如果我们反向建立一个有向图，那么答案就是每个点的所有子树中quite最小的点。

852. Peak Index in a Mountain Array

最基础的二分查找

853. Car Fleet

1. 车子相撞后的速度是多少？被撞的车的速度
2. Car fleet彼此相撞吗？根据1，我们可以认为后面的车撞上前面的车之后就消失了。。。因此我们可以统计最后剩的车的数量即可。

所以我们计算出每辆车在到达终点时能不能超过自己前面的车辆，这道题一个WA点是不能简单比较一辆车能够超过前面的车。比如下面的这个case，即10, [0,4,2], [2,1,3]，车位置A B C，其中C最慢，B最快，于是B和A先后粘住C，但A却没有超过B。所以这一题的思路应该是对于每一辆车，我们统计后面有多少车的时间比自己短，然后把它们去掉。
这个朴素算法是$O(n^2)$的，但实际也能过。我们可以优化成$O(n)$的，此时我们只要维护一个ctime来表示当前最慢时间，然后我们从后往前遍历，如果有比这个时间还要慢的，那么这辆车一定不能粘在前面的车子上。

854. K-Similar Strings

如果可以通过将 A 中的两个小写字母精确地交换位置 K 次得到与 B 相等的字符串，我们称字符串 A 和 B 的相似度为 K（K 为非负整数）。
给定两个字母异位词A和B，返回A和B的相似度K的最小值。A和B只包含集合{'a', 'b', 'c', 'd', 'e', 'f'}中的小写字母。
这道题让我想起来之前O(1)空间矩阵转置的问题，我们实际上知道始态和终态，现在问如何通过两两交换来达到。
假设我们需要把a移动到b的位置，那么我们建立一条从a到b的有向边，可以看出如果从b到a也有一条有向边，那么我们就可以消去这两条边。那么剩下来还有的就是长度大于2的环。对于长度为n的环，需要n-1次操作进行消除。所以问题变成了我们需要去迭代地把图里面的环去掉。
写了一个DFS找后向边的方案，WA在了A = "aabbccddee", B = "cdacbeebad"这个case上面，发现是a<-b<-c<-a和a<-e<-d<-a和b<-d<-e<-c<-b这三个环，而不是之前的小环b c和e d。TODO 我们如何修改这个方案呢？一般来说，找最小环，就是给定一条边(i, j)，找(j, i)的最短路，这个可以借助于dij来做，不过看起来开销有点大。。。
直接看题解，首先是一个类似DP的seen，用来记录到seen[S]至少要经过多少步，然后用一个BFS去计算这个seen数组。现在就是我们如何找到所有能从S一步到达的T。

855. Exam Room

贪心即可，注意特别处理0和n - 1的情况。注意两点，max_dis()相等时根据l来判断，合并区间时需要注意单独一个p的情况。

856. Score of Parentheses

一看就是和栈有关，不过具体思路还是蛮麻烦的。首先我们知道维护一个计数器，当一个右括号出现的时候我们就将计数器乘2，那么我们什么时候重置这个计数器呢？这一题我们可以借鉴逆波兰式这样的思路，使用一个栈去维护我们的中间结果，每一次右括号会double掉栈顶到最近的左括号的所有值的和。

857. Minimum Cost to Hire K Workers

有N个工人，具有quality[i]和wage[i]两个属性。现在需要雇佣K个工人，要求每个工人按照他们的quality[i]的占比给付工资，每一个工人必须给到wage[i]的工资，求最小需要的钱。其中1 <= K <= N <= 10000。
首先，我们不能按照wage[i]来贪心，不然，如果出现一个人他的性价比quality[i]/wage[i]超级低，那么即使wage[i]很低，也会把总工资搞得很高。我们也不能按照性价比quality[i]/wage[i]来贪心，因为考虑极端情况，我们只需要一个人，那么我们肯定选工资最低的，而不是性价比最高的。二分答案是不可行的，因为似乎答案不一定是整数。DP的话，我们需要假设DP[K]能从DP[K-1]中推出，但这也不行，我们可以考虑quality = [1,5,5], wage = [10,11,11]的情况，那么DP[1]选0，而DP[2]选1,2。那么我们能够DP[N]么？也就是我们先随便放K个人进队伍里面去，然后我们从第K+1个人开始尝试能不能用他把队伍里面最坏的一个人换掉，从而减少工资总额。我认为已经被淘汰的人不会在后面的轮次中被再次添加上去，因为至少我们已经有K个比他好的结果了。它的复杂度是O(N(尝试替换的人)*K(与K个人比较)*K(计算总工资))。计算总工资的流程是把所有人的quality[i]加起来得到Q，然后求max(wage[i]/(quality[i]/Q)))，这个复杂度看上去就是要T的。。。不过我先写一遍，万一过了呢？并且这种方案如何处理换不换工资总额一样的情况呢？
跑了一下，WA了。算了，直接看题解了。题解同样指出我们实际上是要维护两个指标，一个是性价比，一个是工资。总的思路是，我们首先按照性价比对员工进行排序入堆，按照能力值出堆，优先出能力值最大的员工。在这个方案来自于一个观察，即max(wage[i]/(quality[i]/Q)))是由性价比最低的人决定的，因此这个就类似一个滑动窗口问题，我们移出堆里面要吃最高工资比例的人，这是有利于减少总工资的，但现在就少了一个人了，所以只能入一个对总工资增加影响最少的人。

859. Buddy Strings

简单题

860. Lemonade Change

没啥好说的，就是贪

861. Score After Flipping Matrix

首先我们希望能够将高位尽可能变成1，我一开始的思路就是通过行变换一定能够让最高位变为1的，然后我们进行列变换，使得每一列上的1也是最多（过半数）的。WA了一次之后发现我们还需要考虑先对第一列进行一次列变换，继续WA，原来是犯了个低级错误，行和列搞混了。

862. Shortest Subarray with Sum at Least K

同样要考虑为负数的情况。这道题如果直接做是$O(n^2)$的，类似560这道题，但实际我们可以做到$O(n)$。我们还需要注意Google的Kickstart2018 Round D的第一条也是这种类型的，不过使用了一个set。
因为题目要求找最小的i > j满足B[i] - B[j] >= K，其中B是前缀和，我们使用一个deque来维护所有可能成为j的数。这是一个很奇怪的话，难道有的数不可能成为j么？我们需要考虑两种情况。

1. 出现一个更好的结果
   例如A = [1,2,7]; K = 3，我们实际遍历序列B = [0, 1, 3, 10]，当我们遍历到10时，q = [1, 2]（稍后我们能够自己得到这个结果），现在我们读取到10，然后从左边尝试出队。也就是说当x - B[q[0]] >= K，我们会得到一个可行解，用它来更新ans。容易看出只要后面的数是合法的，那么前面的数肯定是没用的。
2. 出现一个更差的结果
   这个对应于负数的情况，例如A = [1,-2,7]; K = 3，对应的B = [0, 1, -1, 6]，我们发现当遍历到-1时它都小于前面入队的1了。那么这个1肯定是不会被取的了，因为我的-1不仅比你小，还比你靠后，肯定是**不可能成为j**的，因此我们从队列中删除这个-1。

863. All Nodes Distance K in Binary Tree

给定一个二叉树root，返回到目标结点target距离为K的所有结点。
先转成一个图，然后在图上面bfs

864. Shortest Path to Get All Keys

从此往后的四题发生了题号的更改，原先是从865开始的。
【Contest 92.4 没做】

865. Smallest Subtree with all the Deepest Nodes

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

866. Prime Palindrome

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

867. Transpose Matrix

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

868. Binary Gap

【Contest 93.3 1A】
简单题

869. Reordered Power of 2

【Contest 93.3 2A】
Python居然T，C++就过。。。这题感觉只能暴力啊

870. Advantage Shuffle

【Contest 93.3 1A】
这个就是田忌赛马嘛，排序贪心就行，用了del A[i]都能过

871. Minimum Number of Refueling Stops

这道题很难过了，本来以为可以贪的，导致上一条看都没看。当时想法首先是维护have数组表示从i往后所有加油站的存油量，然后贪心的情况就是看当前油量能不能到下一点，以及将来的总油量能不能到终点。后来发现100,25,[[25,25],[50,25],[75,25]]会WA，便使用max_need维护从i往后从j到j + 1需要的油量的最小值，这个思路也是错的，因为我们前面可以存油。也就是说[1..j]的最优解不一定是[1..i]的最优解。
所以这道题还是要老老实实DP。一开始我想到类似于第45条一样，维护到i点的最小加油站数l[i]，不过这道题i很大。我们实际上使用dp[i][j]维护到第i个加油站时候总共在j个加油站加油的最大剩油量。然后这条题目相同的代码一发T一发AC，我也是醉了。。。

873. Length of Longest Fibonacci Subsequence

维护dp[i][j]为满足A[i] + A[j] = A[k]的k。我们逆序遍历i < j，然后使用一个集合s维护，我们在这个s里面找有没有A[k]。
T了，原来我们要在预处理阶段就算出最长的长度，改一下过了。

875. Koko Eating Bananas

有N组香蕉，每一组有piles[i]个。猴子每小时选择一组，然后吃掉这一组中的K个香蕉。问在H小时内全部吃完的最小K是多少。
这条应该是一个裸的二分答案。K最大值是一次吃完一组香蕉，所以是max(piles)/N，最小值是一次吃sum(piles)/H个香蕉，少了肯定不行。
注意写的时候要max(1, s / H)，不然可能为0。然后X/Y向上取整是(X+Y-1)/Y

877. Stone Game

记搜

879. Profitable Schemes

有 n 个罪犯，有一些阴谋，每个阴谋需要 group[i] 个人完成，赚 profit[i] 的钱。现在需要最少赚 minProfit 的钱，问有多少方案。所有的 range 都小于 100，这应该是一个 dp。我猜应该是 dp[i][restPeople][restProfit]。
这里注意的是，restProfit = 0 的时候，还需要考虑 restPeople 是否够用，而不是简单的 2**(i+1)。
总之这一题虽然是 hard，但还是没啥 tricky 的，就是比较难写一点。

880. Decoded String at Index

这个很蛋疼，要求多个层次重复的字符串中的第K个是什么。这种问按照一定规律生成的串中的第N个元素是什么的题目一直困扰着我，因为每次都没有总结出一个比较优雅的解法。
本题我们首先不停地扩展我们的字符串，直到超过了需要的长度K。

881. Boats to Save People

经典的装箱问题，贪一下咯。用C++写，std::multiset很方便。取个负数方便用lower_bound找最大的小于X的数。

887. Super Egg Drop

【强烈建议看官方的Solution学习】
这一条注意没碎的鸡蛋仍然可以用来二分，所以我们最坏的情况应该按照碎的来算，所以我们不能裸算二分的次数加上最后线性搜的次数。
算了我还是记搜吧。。。TLE。。。看题解，实际上我们可以二分这个drop，因为我们取的是max(if_break, not_break)，所以实际上我们希望它们尽可能接近。
还可以根据鸡蛋数和行动数DP。

889. Construct Binary Tree from Preorder and Postorder Traversal

从前序遍历和后序遍历构建二叉树。

896. Monotonic Array

简单题

897. Increasing Order Search Tree

简单题

898. Bitwise ORs of Subarrays

$O(n^2)$的解法是TLE的，我又XJB搞了半天，想用201的那个做法。其实我们不需要将A[i]去or上s中[0..i-1]的所有结果，我们只要or上s中i-1对应的结果就行了，因为i-1之前有的，or到i-1肯定也有。
此外还有的$O(logn)$的解法。这道题蛮好的。

899. Orderly Queue

有意思的脑筋急转弯，当K>1时始终可以得到最小字符串。这是因为我们首先可以将已排序部分调整到串的尾部，然后我们可以利用字符串顶部的2个空间来维护出剩余字符串中的最小值。

901. Online Stock Span

找到i位置之前的最长的值比prices[i]小的连续序列的长度。这是直方图那条的模板题，例如11题。

903. Valid Permutations for DI Sequence

从0到n的数字组成排列，对于任意的i，要求第i位和i+1位满足一定的大小关系，求所有排列的数量。
从排列本身查看局部特征是并不明显的，例如DI的D实际上不禁止01的排列，但I会禁止01排列。
显然，dp思路是设dp[i][j]是满足长度为i的序列的末维a[i]==j的排列的数量。不妨假设S[i] == D，那么它等于sum(dp[i+1][k]), k∈[0..j-1]。又考虑计算dp[i+1][k]，假设S[i+1]=I，那么在计算时需要sum(dp[i+2][l]), l∈k..n-1，那么a[i+2]可能和a[i]取到同样的数。
因此，不妨加一个约束，也就是dp[i][j]是**使用数字[0..i-1]**的排列，那数字就不可能重复了。

905. Sort Array By Parity

双指针简单题

918. Maximum Sum Circular Subarray

感觉就是复制一份，然后 dp 一个最长为 n 的长度。
一个平方复杂度的做法 T 了。
有三种方法：

1. 减少上面方法的复杂度，也就是不要通过遍历来选择合适的长度或起点。比如以 e 为终点，最多能加到 S[e-n+1..e]。那么就找 [e-n, e-1] 之间的 l 使得 S[l] 最小，这样得到 S[e] - S[l] 最大。

这里同样是一个单调队列，但比较复杂，需要比较队头和队尾。首先，如果找到一个小于等于队尾的元素，我们始终可以弹出队尾，因为它是最优的。那么这个单调队列是个递增队列。然后每入队一个元素，都需要比较是否需要出队。
然后这里需要二分么？因为队头元素永远最小，并且合法，所以不需要二分。

926. Flip String to Monotone Increasing

翻转一个0和1构成的串，让前面是0，后面是1。可能全是0或者全是1。
这个应该是 n 的办法。首先统计一下每个数前面有几个1，后面有几个0。然后枚举任意一个 i，要求 i 前面全是0，自己和后面全是1。其中 i 的取值是 0 到 n。我们要把 i 前面的 1 变成 0，后面包括自己的 0 变成 1。

931. Minimum Falling Path Sum

从棋盘A的左上角到右下角，输出和最小的路径，注意A[i][j]可能为负数。
啊 题目理解错了，是一行一行往下找，例如(i,j)的下面是[(i+1,j-1), (i+1,j), (i+1,j+1)]
这个应该是一个裸DP。

950. Reveal Cards In Increasing Order

定义一种操作，每一次取牌顶的一张牌，如果还有牌，将现在牌顶的牌放到最下面，如果还有牌，重复前面一个步骤。已知输出序列是升序的，求输入序列。
第一眼想到的就是倒推。

962. Maximum Width Ramp

一个ramp满足i < j且A[i] <= A[j]，定义宽度是j - i，求一个数组里面宽度最大的A。
显然可以有一个O(n^2)的Naive的办法解决这个问题，那么显然是希望找一个复杂度较低的办法。看起来有点类似直方图的那条题目？也许我们可以使用类似逆序对的方法，二分解决问题？
解法有点类似第768，用的单调栈。维护一个单调递减的栈，然后二分查找栈里面第一个小于等于当前数的位置。这是一个F/T…TTT形式的二分。
这个单调栈不需要出栈，考虑 5 7 6 3 1，如果后面的 3 比 5 都小了，它肯定不会尝试 7。

978. Longest Turbulent Subarray

和 Wiggle Sort 类似，这是要求最长的 Wiggle 子串。从 Stock 的直觉上，感觉是要维护两个 dp，分别是两种波浪形状。
不过先来看题。用 dpD[i] 表示以 i 为波谷，dpU[i] 表示以 i 为波峰的子串的最长长度。那么如果 S[i] 大于 S[i-1]，则 dpU[i] = dpD[i-1] + 1.

979. Distribute Coins in Binary Tree

这道题应该暗含了保证恰巧有 n 个节点和 n 个硬币。总感觉这道题有 FollowUp，例如如果保证每个节点至少有 1 个硬币，求最优方案。
对于每棵子树，进行下列操作：

1. 下发：也就是说这个子树所持有的总硬币数，小于它实际需要的。这个时候它需要往自己的 parent 请求下发。
2. 上交

诸如将左子树的 coin 搬到右子树上，可以简化为上交+下发。

1011. Capacity To Ship Packages Within D Days

用传送带往船上运东西，要求D天内运完，船不能超重。求满足要求的最小的船的载重。
因为验证很容易，并且上下确界是已知的，所以可以二分答案。

1012. Numbers With Repeated Digits

给定正整数N，返回小于等于N且具有至少1位重复数字的正整数。
感觉这是一个数位DP啊，写了一下，很多报错。原因是要处理高位为0的情况。
TODO
看了一下题解，发现还需要存当前出现过哪些数字，这一点是我没想到的。题解还保存了flag维，但实际上不需要，加上反而更耗时间

1013. Partition Array Into Three Parts With Equal Sum

有N个数组成的序列，可能为负数，问能不能分成和相等的三份。注意，我们不是随机存序列中挑，而是直接往序列中切两刀。因此这个就很简单的，我们扫一遍求和就行

1014. Best Sightseeing Pair

给定正整数数组A，A[i]表示第i个观光景点的评分，并且两个景点i和j之间的距离为j - i。一对景点i < j组成的观光组合的得分为A[i] + A[j] + i - j，返回一对观光景点能取得的最高分。朴素做法是平方复杂度，这个肯定是想办法线性了。
也就是说要两个景点尽可能分数高，并且距离尽可能近。这个和11题是相反的，11题的话是双指针i和j相向移动是一个惩罚，而1014则是奖励，也许 j - i 会好做点。

另一个想法是把两个指针相遇变成快慢指针，也就是快指针j往前走，一直走到 value[j] 不能扩大 mx 之后，让慢指针i 往前走。但问题是，快指针不能前进之后，慢指针可能也不能前进。因为慢指针i前进虽然会缩小 i - j，但可能 value[i] 变小了。但实际上这种交替前进的模型并不适用于这个题目，因为A[i] + i和A[j] - j都不是单调的。但反省一下，对于任意的j，我们需要的i是确定的，也就是[0..j)这个范围中A[i] + i的最大值，在 j 扫过时，我们可以让 i 也扫过。

【另一种思路】对于每个A[j]，我们希望找它前面尽可能近的A[i]。也许我们可以把A[i] + i整体放入一个单调栈里面，对于每一个A[j] - j，我们尝试找一个最大的A[i] + i，不过等等。。。我们直接维护一个最大的A[i] + i就行了啊，不需要单调栈。

1015. Smallest Integer Divisible by K

给定一个 k，找到最小的正整数 n，n 由 1 组成，能被 k 整除。如果不存在就返回 -1。
也就是对于一个 k，找到一个 x 使得下面的式子被 k 整除。
$$
\frac{10^x - 1}{9}
$$
那么就是要求是否存在 y，对于给定的 k，有 $9ky + 1 = 10^x$。
这个也许可以用指数循环节简化，也就是
$$
A^B (mod C) = A^{B mod \phi(C) + \phi(C)} , B \ge \phi(C)
$$
最后是莽过去的。

1027. Longest Arithmetic Sequence

给定一个整数数组A，返回A中最长等差子序列的长度。这题目有点似曾相识啊。。。
数列长度是2000，值是10000，不过这个应该没有二分的性质。首先想到的是确定一个等差数列需要两项，那么选择前两项还是末两项呢？从之前的做题经验来看，选择后两项的比较方便DP。那么我们用dp[i][j]表示末项为i，公差j的等差数列的最长长度，那么它的值等于dp[i - j][j] + 1。因此，我们想到一个方案就是对于每一个i，我们先检查它能否和之前的某个数组成新的序列，然后我们再查看，它是否能拓宽已有数列的长度。这个也很容易做到，我们遍历前面所有的数j，然后得到一个公差d，我们尝试能不能更新dp[j][d]即可。dp可以用map来维护。
不过上面这个逻辑有点问题，实际上我直接查看能否从dp[j][d]更新dp[i][d]即可，不要什么两次遍历了。不过WA了。原因是要用dp[i][j]表示末项为A[i]，公差j的等差数列，而不是i。

1036. Escape a Large Maze

一个100万乘以100万的迷宫，有一些格子是被blocked的，问两点间是否存在通路
感觉直接对这个图进行搜索就行，但进行搜索需要维护一个vis数组，而显然我们开不了这么大的数组。于是我们注意到最多有200个区块被阻拦。所以我们完全可以对源和汇单独进行一下一个有限宽度的BFS。
我一开始觉得遍历半径为200应该，只要能走到100开外就够了，因为事实上一个200×200的正方形上面的对角线也是200长度的，因此我们至少要走到200步开外才行，这样BFS会T。
后来看题解才发现，其实我们只需要不停的BFS，直到走到第19900个格子还能走，那么就肯定在外面了。

1049. Last Stone Weight II

有n个数，我们随便取两个数x和y进行下面的变换，如果x == y，则得到新的数0，否则得到max(x, y) - min(x, y)。问如此循环下去，得到的最小的数是什么。最多有30个数，每个数最大是100。如果采用记搜的方案，复杂度是C(30,2)*C(29*2)*...这样的规模，看起来不能够承受。这个有点辗转相除的味道，但其实不是，因为每一次会少一个数，所以实际上可以看做用加减和括号将这几个数连接起来，考虑到括号可以脱掉，所以实际上就是在这些数前面加上加号和减号，从而得到去最小值，而这个是一个很简单的DP问题。
一开始我希望尝试dp[i][j]表示用到i个数能够达到的最接近j的数。后来发现两个问题，首先，也许可以估算到整个过程中最大的合法的j大概是30*100/2，但是我们如何处理在dp更新的过程中发生的上下溢出的问题呢？其次，比如我们要求的j是2，我们通过加法和减法能够分别得到0和4，那么其中哪个更好呢？
因此后来直接可以维护用到i个数能够得到的所有的数字了。

1054. Distant Barcodes

一个有重复数的列表，要求去重新排序它，使得没有重复元素相邻。
如果我们仅仅去sort的话，那么显然相邻的元素会靠在一起，但是如果我们给值相等的元素编号，并且再sort，应该就是成了。
但其实不成，比如第二个case[1,1,1,1,2,2,3,3]。解决方案就是用一个pq维护每个数的个数，然后拿最多的出来填。但是要注意可能填完一个A之后发现A还是最多的，这时候需要将a放到一个no_use里面冷却一下。

1079. Letter Tile Possibilities

看起来是给定一些字母，问用这些字母能够组成多少单词。
看起来是可以推一个公式的，但是有点困难。
先尝试用最简单的方法做，我们从长度为1开始维护一个集合，然后依次尝试往这个集合中添加一个合法的元素。它的复杂度是O(l^3)的，令l是给定tiles的长度。这个是会T的。
然后还是推推公式吧，其实还是比较容易的，我们把每个元素的个数标成一个排列。例如aaabbc可以表示成3 2 1，那么其能组合出的数量就是(3+2+1)!/(3!2!1!)，然后我们去计算它的所有子集就行了。考虑到最长为7，所以可以用字符串编码进行记搜。不过这样似乎在1这个情况下会被重复统计。
看了题解，这道题的其实不需要O(l^3)这样遍历，直接按字母种类按照顺序往下填就行。

1092. Shortest Common Supersequence

先求一个LCS，然后往上面补数字即可。类似于gcd和lcm。

1103. Distribute Candies to People

简单题

1105. Filling Bookcase Shelves

放书。每一层的宽度最多等于给定 selfWidth。 求可以做到的最小的厚度。
疑问，如果按照 (height, width) 降序排列，然后每次取能 fit 的最小 width 会有什么问题呢？
给定 [[7,3],[8,7],[2,7],[2,5]], 10 这个数据是有问题的，原因是要按照顺序依次摆放书。这应该是说，一旦第二层已经形成了，就无法再去让第一层变高了。
所以，我们依次遍历所有的书，对于每一本书，可以选择放到某一层上，这可能导致这一层变高，或者新开一层。题目给出的样例说明这题不能贪心去选择都放在某一层上。
看了下题解，终于搞明白是怎么回事了。就是选择放到某一层，那也只能放在当前层，不能放到某个历史层。它可以让当前层变高，但不能让历史层变高。。。所以感觉这题目好蠢。

1115. Print FooBar Alternately

并行算法问题，Python依然始终T。。。

1116. Print Zero Even Odd

并行算法问题，Python始终T。。。

1123. Lowest Common Ancestor of Deepest Leaves

在二叉树上LCA，老题新做，得到两个List，然后zip比较即可

1124. Longest Well-Performing Interval

一条讽刺996的题目。数组hours的一个子数组中大于8的数字的个数严格大于小于等于8数字的个数，那么这个数组是好的，问最长的好数组是多长。
朴素做法是O(n^3)的，包含一个O(n^2)的循环用来遍历所有区间，然后用一个循环来检查区间是否合法。
我们能用双指针来去掉一个循环么？考虑一下双指针的适用场景。比如分别从左和从右相向移动的双指针，这种方案是我们能够保证当指针已经移到(i, j)时，不会产生一个情况(i-1, j)这样的最优解。
其实我发现可以用O(1)来判断是否是好的，就用+1或者-1维护一个累积和acc就行了，得到一个O(n^2)的方案，但是T了。
看了题解，其实最佳解法是O(n)的，使用单调栈去处理累积和acc。单调栈适合解决对i, j和arr[i], arr[j]同时有要求的题目。例如这条题目，我们就是要求一个最大的跨度(i, j)，满足acc[j] > acc[i]，这样保证这段区间内1是比-1要多的。
到这里可以发现，本题类似于第962题。不过令人遗憾的是我似乎没有学会962的方法。。。照搬一下，发现会WA在[6,9,6]这个case上，错误地输出2。
比了一下逻辑，发现其实和数组acc[0]应该设置为0，从而得到一个WA3。
最后终于过了，原因是首先要在二分完之后看一下l是否合法，可能l也不合法，然后要在acc前面加一项0，不然第一项为1的情况可能不被计算，因为我们是算得(i, stk[l]]。
TODO

1125. Smallest Sufficient Team

一个项目要选几个人来完成，req_skills表示完成这个项目需要哪些技能，people表示每个人的技能。现在要求找到最小的人的集合。
这道题的Naive解法是幂的复杂度，二分答案的话验证也不好做，所以应该是一个DP或者记搜，并且是要压缩状态的。我们定义dp[s]表示要达到状态s需要哪些人的参与。
不过这样的记搜面临一个问题，也就是说例如我们最终需要1245，现在有一个1需要一个2，我们有123和124的选项，那么选哪个好呢？反而是用DP的方式推要容易一点

1130. Minimum Cost Tree From Leaf Values

给定所有的叶子节点，构造一个二叉树。每一个非叶子节点的值等于左子树最大值和右子树最大值的乘积。问所有非叶子节点和最小是多少。
先扯一点别的，给定N个点，能形成多少个二叉排序树？这个是Leetcode96。那么给定N个点，能形成多少个二叉树？可以看这篇文章
回到这一题，看起来有点线段树的构造啊。于是令dp[i][j]表示[i..j]区间上的非叶子节点的值的和。
不过WA在了[15,13,5,3,15]上，原因是我是fori、forj，但实际上应该先短后长。

1143. Longest Common Subsequence

LCS老题老做

1155. Number of Dice Rolls With Target Sum

有d个骰子，每个有f面，问这些骰子朝上面总和是targe时有多少种情况，要求模10^9 + 7。每个骰子是独立计算的。
看起来是一条数学题，继续看下数据范围1 <= d, f <= 30，1 <= target <= 1000，似乎可以DP。一个容易的想法是dp[i][t]表示用前i个骰子达到target有多少种方法。那么dp[0][1..f]的取指肯定都是1。对于dp[i][t]，那么其方案总数就是for 1..f尝试去更新一下。

1222. Queens That Can Attack the King

从king处按照八个方向找到第一个Queen即可。

1227. Airplane Seat Assignment Probability

n个人坐座位，第一个人没带票随机坐，有1/n的概率坐到自己对应的座位上。后面的人座位没被占的就坐自己的，不然就随机坐。问第n个人坐到自己座位上的概率是多少？
一个直截了当的做法就是算dp[i][j]表示第i个人坐到第j个座位上的概率。然后T了，看Hints，似乎可以打表找规律。结果发现从1之后都是0.5。。。这个题目很有意思，应该可以用数学归纳法证明一下P[i]==P[i+1]

1232. Check If It Is a Straight Line

检测一条线是不是直线

1239. Maximum Length of a Concatenated String with Unique Characters

给定一个字符串数组arr，选择其中一些串组合起来，要求组合之后的串没有重复字符，问能组成的最长的串的长度是多少？其中1 <= arr.length <= 16，1 <= arr[i].length <= 26。
这个题目感觉很熟悉。。。类似于我们要选择价值最大的几个元素，但是要满足一些规定，例如元素A和元素B不能同时存在。
没思路，直接看了题解。。。结果居然是回溯法，直接枚举也行。。。反正复杂度是2^16。
回溯法相对来说比较容易，我们用一个26bit的int来压缩每个字符出现的次数。
这一题要注意[yyy]这种特殊情况，字符串本身有重复，也是不可以的。

1262. Greatest Sum Divisible by Three

给定一个nums数组，要求找到和最大的一个子集，要求这个和能被3整除。这个题目很简单，直接按照模分成三个数组，然后把模1和模2的数组从大到小对应相加就行。但WA了，因为两个模可以组成一个模2，这种情形要考虑进去。
然后我们可以联想到是否可以通过背包问题来做。发现没有必要。我们可以设dp[n][mod]，然后查看能否用nums[i]更新dp[i - 1][0..2]。

1291. Sequential Digits

一个有趣的观察是通过首位和长度，就可以唯一确定一个序列，剩下来的就是如何通过low和high去截断序列。

1298. Maximum Candies You Can Get from Boxes

【TODO】
status[i]表示箱子有没有打开，candies[i]表示箱子里面有多少糖，keys[i]是箱子里面的所有钥匙，containedBoxes[i]是box[i]里面包含的箱子，没搞懂最后一句什么意思。

1306. Jump Game III

给定 arr，初始在 start。在 i 可以跳到 i + arr[i] 或者 i - arr[i]。问能不能跳到所有值为 0 的格子里面。
感觉这就是个单元连通性问题，问从 start 是否可达任意的 0。

1314. Matrix Block Sum

给定K，和一个二维数组。要计算i - K <= r <= i + K, j - K <= c <= j + K范围内的所有的数的和。
可以在O(n*m)复杂度完成。

1334. Find the City With the Smallest Number of Neighbors at a Threshold Distance

emmmmm，这题目很长啊。。。翻译过来就是一个带权无向图，我们筛选出从每个城市能够在distanceThreshold距离内到达的所有城市，我们需要返回的是能够到达最少城市的城市。当有多个答案时，返回index最大的。
其实就是Floyd模板题。

1345. Jump Game IV

TODO 感觉也是个图论。

1338. Reduce Array Size to The Half

一个整数数组arr。选出一个整数集合，并删除这些整数在数组中的每次出现。返回至少能删除数组中的一半整数的整数集合的最小大小。
看起来就是说有n个东西，每个东西有价值v，总价值V，问如何选择最少的东西使得总价值至少大于V，贪心就行了

1340. Jump Game V

相当于 Jump Game II 加上只能往下跳的条件，问最多能跳几次。感觉是个 DP，子结构很容易看出来。
TODO

1354. Construct Target Array With Multiple Sums

给你一个整数数组target。你有一个数组A，它的所有元素均为1，重复该过程任意次以下操作，问能否得到target。

1. 令x为你数组里所有元素的和
2. 选择数组里面的任意元素，并将其变为x

观察一下，因为原数组都是1，所以每进行一次操作，总和x就会变大。不妨考虑两个的情况，令[a, b]，其中a > b，那么它肯定是从[b, a - b]得到的，依次重复这样的操作，看看最后能不能得到一个全是1的数组即可。
所以模拟一下就行，不过这个方案T了。下面就能够很自然想到用优先队列优化，但是我们要同时自己维护一下当前target的和。
此外还有特定优化一下[1,1000000000]的情况，特判一下只有一个元素的情况。

1696. Jump Game VI

每次可以跳到 [i + 1, min(n - 1, i + k)] 中的某一个位置。希望跳到 n - 1，并且得分是路过的每个点上的 val。求最大的 val。怎么感觉这条很面熟。注意，val 可能是负数。
简单的 dp TLE 了，我说为啥这是个 medium，因为 k 可能很大。
其实可以用滑动窗口维护一下，就是 [i-k, i-1] 这个区间中的最大的值。这个显然是个单调队列。每个元素都要进一次队列，进一个 pop head 一个，然后用出的那个去更新最优解。队列本身通过 pop tail 维护单调性。
这里的单调性是，如果发现要入队一个更大的值，那么队列里面已有的小于等于这个值的都可以出队。所以这个队列是一个单调递减队列。

1705. Maximum Number of Eaten Apples

考虑下面的情况，我们可以把某些苹果放到稍后再吃，所以不能简单用min(apples[i], days[i])更新

eatenApples(apples = [2,1,10], days = [2,10,1])

不过也许可以从后开始遍历天数，看有没有苹果能吃。不过如果有一天能吃多个苹果怎么办呢？吃 range 最短的？

2145. Count the Hidden Sequences

这题也太水了

2453. Destroy Sequential Targets

容易发现，给定num[i]，所有的数都是模space同余。
注意，返回的一定要在列表里。

2484. Count Palindromic Subsequences

有重复算的问题：

1. side 1 2] [2 1
2. mid 1] (2) [2 1
3. mid 1 2] (2) [1
4. neglect 1] 2 [2 1
5. neglect 1 2] 2 [1

2521. Distinct Prime Factors of Product of Array

感觉是很无聊的题目，可以将 2..1000 中的数因式分解即可。