Go Over LeetCode

[caibirdme]

做了600+了，除了周赛不做题了，先复习总结

[caibirdme]

Median of Two Sorted Arrays
这道题其实就是在两个有序数组中找第n大数。找第n大，那么分别看两个数组的前n/2个数，a[n/2]和b[n/2]，比较这两个数，就可以一次性排除2/n个数。剩下的就是相同子问题

[caibirdme]

Longest Palindromic Substring
根据回文串的特点，可以利用中心扩展法，枚举每个串的中心，然后往两边扩展。复杂度O(n^2)，DP空间消耗过大，不是最优。 有O(n)的Manacher算法，这个需要后面单独学习

[caibirdme]

Regular Expression Matching
这道题一开始直接裸DFS，耗时比较高。像这种两个字符串对位匹配，基本上应该第一时间想到区间DP。而且这道题区间DP相当简单，直接记忆化搜索。转移时需要注意 *，因为它代表0个或多个，因此转移时要考虑不匹配的case

[caibirdme]

Divide Two Integers
这道题要求不能用乘除法完成除法运算。所以我们模拟小学时的竖式除法，把两个数转成二进制进行竖式除法。 要求不能用乘除法以及别的语法的题目还有很多，比如要求不能乘除法以及if和循环语句计算1+2+3+..n。不能循环就递归，不能有if我们可以利用 return condition && calc(&mut result)进行退出控制

[caibirdme]

Substring with Concatenation of All Words
这道题利用滑动窗口，或者更准确地说是双指针。R指针不断向右扩展，由于word的长度都一样，因此每次读一个word长度的字符串。如果读到的字符串不在words中，说明从左指针到有指针都不可能是符合条件的子串，因此左指针直接快进到右指针的位置，并清空各种状态计数器。如果新读的字符串t在word中，但是出现的次数大于目标次数，那么左指针到第一个t肯定不是目标子串，快进左指针并更新各计数器。 这种类似的题目非常多，印象中做了好多这样的题。比如简化版的，把words = Vec 改成 Vec且char不重复。需要领会这种双指针的思想

[caibirdme]

Longest Valid Parentheses
这道题最直观的就是O(n^2)的DP，计算f(i,j)表示i..j是否是合法的，DP过程中维护最大值。但是f(i,j)==true，可以转化为f(j) = j-i+1，即用f(j)表示以s(j)结尾的最长合法串的长度。然后可以分成两种情况：

• 如果j前面是(，即 .... ()这种情况，f(j) = f(j-2)+2
• 如果j前面是)，那么f(j)是一个合法串只能是这样 .... ( (..... ))，因此如果s(j-f(j-1)-1)==( 时，f(j) = f(j-1)+2 + f(j-f(j-1)-2)

同时，也可用栈，每次遇到(就把下标入栈，每次遇到)，如果栈不为空，说明找到一组完整的匹配，那么把栈顶弹出。弹出后，现在栈顶就是离当前)最近的一个未闭合的(，形如 (()()()，由于每个)都能闭合一个(，所以栈顶就是最开始的那个(。因此两个作差就能算出当前合法的长度。如果遇到)且栈为空，说明是多余的)。为了避免()()这种情况，遇到)就弹出一个(，然后栈一直为空，找不到合法区间的开头，因此在栈为空时需要push一个当前位置到栈中，方便后续计算。

更进一步，如果我们每次遇到(就count+1，遇到right就count-1，那么当count等于0时，我们就找到一个合法区间。当有前导(时，可能导致count永远不为0，比如(((()()()，因此我们可以反着再遍历一次，这样相当于去掉前导的(。

括号匹配算是常见题型！需要熟练运用，尤其是dp和栈

[caibirdme]

First Missing Positive 这道题要求缺失的第一个最小正数，假如数组长度为n，那么答案一定是1..n+1中的一个。最简单就是hash记录哪些值出现过，然后从1开始扫一遍，遇到第一个没出现的就是答案。由于要求不用额外空间，因此我们可以直接利用原始数组。我们把数字j放到数组下标j，使得a[j]==j。最后扫描一遍即可。 核心的点就是一个while 循环

while a[i] != i && a[i] >= 0 && a[i] < n {
   a.swap(i, a[i])
}

这种以值作为下标进行hash存储的题目也有很多，经典的就是给定一个长n+1的数组，里面的数字是1..n有且仅有一个重复，找到那个数。也是一样的做法。

[caibirdme]

Jump Game II 这道题是一个贪心题，由于要尽快跳到终点，因此很显然每次只往前跳不会向后跳。每次选择要跳到哪个点，就看哪个点下次能够到达的距离最远。因为当你到达位置i时，1..i-1都是可以到达的点，因此你这次选择要到达的点，需要让下次到达最远。 然后一个小优化，这次直接跳能够到达的最远点，比如是i+v[i]，当你这次选择跳到j而不是i+v[i]时，下次从j开始跳时，直接考虑i+v[i]后面的点

[caibirdme]

Rotate Image 旋转矩阵是一个很常见的题目，不算是算法，应该是常用操作，属于execution的题目。旋转主要思路就是分治，每次旋转都会让4个点顺时针或者逆时针交换。因此需要根据题目要求，找到每次旋转的4个点。 类似的题目还有，比如转置，翻转，镜像，等等，都需要根据实际情况讨论。

[caibirdme]

Merge Intervals 给N个区间，把它们合并后输出剩下的区间。这道题我想复杂了，因为还做过另一道基于这道题改的hard题目。提前给出了所有区间，那么其实我们可以先对区间进行排序，按左端点排，左端点相同右端点大的排前面，这样可以避免不必要的区间扩展。最后线性扫描即可。

更进阶的问题是，让你实现一个add方法，每次add一个区间，同时返回现在合并后的所有区间。这种就没办法预先进行排序了。需要一个数据结构能动态地插入区间，并且快速地查找，这其实就是OrderedMap或者Rust里的BtreeMap。每次以左端点为key插入区间，然后想办法进行合并。

Intervals相关的题目有很多变种，像普通的区间合并，还有区间插入，以及动态区间插入。除此之外，比如会议室预定，更进阶的给定会议的起终点问最多参加多少会议。一般来说，这类题目的抓手都是排序

[caibirdme]

Set Matrix Zeroes 通过这次review才发现之前的做法是有问题的。因为题目没有规定数字范围，因此用任何值来代表"已被翻转"都是不严谨的，只是LC数据太弱。如果直接翻转，会把原本不是0的变成0，当后续遍历到某个0点时，你无法区分它本来就是0还是被翻转成的0。因此核心思路是，翻转时需要想办法既要表面哪行哪列要转成0，还不影响后续。所以办法就是，用每行和每列的第一个元素标记这行或者这列是否需要翻转。当遇到个0点A[i][j]，就把A[i][0]和A[0][i]设置为0。由于A[i][0]和A[0][i]都被扫描过了，因此它可以用来记录状态，也不影响后续。最后，再通过一次N*M的扫描进行真正的翻转。还要注意A[0][0]既可以表示0行也表示0列，如果用它表示第0列，就需要用额外的一个空间来存储第0行是否翻转。

[caibirdme]

Largest Rectangle in Histogram 这道题最重要的是推理过程。要求求矩形的面积，而矩形i..j的面积，其实是由i..j的最小值决定的。即Area = (i-j+1) * minHeight(i..j)。如果枚举i和j，那么最终复杂度就是n^2。既然面积和minHeight有关，那么能不能从minHeight入手。一个区间的minHeight满足的特点是，左边都大于等于它，直到遇到一个比它小的。右边同样也大于等于它，直到找到一个比它小的。 仔细一想，这是不是就是单调队列的构建过程？想想单调队列怎么维护的：元素单调递增地入队，如果遇到比队尾小的，就一直pop，直到队列有序。我们按照高度构建单调队列，当遇到一个小于队尾的高度h，这时想想队尾元素处于什么状态。比如对于如下序列，

(5) 9 10 12 (7) 6

单调队列里存[0(5), 4(7)]，这时遇到6，对于队尾的7来说，它左边都大于等于它，直到5，它右边小于等于它，因此以7为高的矩形的长度就很容易算出来了。

这道题其实就是考对单调队列熟不熟悉，能不能看出模型。实际上题目可以基于此进行各种变换，要有辨别能力。比如可以改改题目描述，假设给定一个数组，现在让你选一个数num[i]，如果这个数左边有连续p个数大于等于它，且右边有q个数也大于等于它，那你能够得到(p+q+1)*num[i]，问你取一个数的最大得分是什么。 本质上，这是一道题

[caibirdme]

Maximal Rectangle 其实和上面这道题是一样的，都是求矩形面积。我们可以预处理出height[i][j]，表示该元素向上有几个连续的1，也就是它的高。预处理完之后，枚举每一行，问题就转化成了前面这道题

[caibirdme]

Scramble String DFS,枚举交换点，可以把原串分为s[0..k]和s[k+1..n]，如果最后结果为真，要么T[0..k] <-> s[0..k] 且 T[k+1..n] <-> s[k+1..n]，要么T[0..k] <->s[k+1..n]且T[k+1..n] <-> s[0..k]。所以用f(l1,r1,l2,r2)来表示s[l1..r1]和t[l2..r2]是否可以互相转换。两个子串可以互相转换，一个显而易见的条件是它们长度相等。因此可以利用这个条件优化一维空间。f(i,j,len)表示s[i..i+len]是否和T[j..j+len]互相转换。枚举len，然后转移方程就显而易见了……

[caibirdme]

Recover Binary Search Tree 要知道那两个点错了，其实就是进行中序遍历之后，看交换哪两个点，然后使得最终有序。 比如 1 1 8 1 2 5 8 1，把第一个8和最后一个1交换就行了。要求不让用额外空间，那么其实可以利用中序遍历的性质，每次记录一下上次遍历的节点的值，和当前比较，记录下这两个需要交换的点。最后再交换即可。由于Rust无法同时获得两个可变引用，所以只能再进行一次中序遍历，进行交换，其他语法直接指针替换就行了

[caibirdme]

Maximal Square 在01矩阵中找面积最大的1组成的正方形。这道题利用DP，可能是矩阵找正方形的通用解法。

* * *
* A B
* C T

对于上述矩形，如果它是3*3的正方形，那么A必然是2*2的正方形的右下角，C和D也是2*2的正方形的右下角，当且仅当满足这个条件，T才可能是3*3的右下角。因此可以通过递推得知以[i,j]为右下角的正方形的边是多长

dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1

而且由于只和i-1相关，还可以利用01滚动优化一维

[caibirdme]

Ugly Number II 最朴素的就是堆方法，维护一个小顶堆，每次取最小的出来，分别乘以2 3 5，生成3个数，如果数不在堆里，就放进堆。 更进一步的做法是维护3个指针，由于每次都是找一个数乘以2，一个乘以3，一个乘以5,取这3个生成的数的最小值作为新生成的数。因此，假如A[i]*2是本次的最小值，那么下一次能用来乘以2的肯定就是A[i+1]。所以我们维护3个指针，p2表示当前哪个数乘以2能得到最小值，同理p3也表示当前哪个数乘以3得到最小值……，每次生成3个最小值后进行比较，然后更新对应指针。注意，因为生成的数不能重复，可能A[p2]*3 == A[p3]*3，因此只要生成的数相同，指针就都需要加一

[caibirdme]

Create Maximum Number 这道题需要进行拆解，把大问题拆解成几个不同的小问题。

• 一共要取k个数，那么数组A取i个，数组B取k-i个
• 需要一个pickup函数返回从单个数组取k个数能得到的最大值
• 需要一个merge函数把两个数组合并成一个
• 最终的结果就是max(ans, merge(pickup(A, i)m pickup(B, k-i)))

然后分别处理，首先pickup函数，从数组中选k个数，有两种方法：

• stack，每次把当前数和栈顶比较，如果当前元素大于栈顶且后续有足够多的数可以使得栈最终能放满k个数，那就可以一直pop栈。因此，总体来讲利用栈可以在O(n)的时间里找出k个数 *由于每次都要利用stack计算数组中选i个，因此可以考虑用DP一次性计算完：
  • f[i][j]表示从A[i..last]中选j个数，开头的那个数最大是多少。f[i][j] = max(f[i+1][j], A[i])

每次用栈和一次性DP其实总体时间复杂度一样（DP的常熟小一点），用栈的话空间消耗更小一点，但是DP相对更简单。

第二个问题是，我已经找到两个序列了，怎么把它合并成一个更大的序列，且合并后最大。这里很容易联想到归并排序合并的做法，每次取队首最大。但是有一个问题就是，如果队首相等怎么办。由于归并排序时保证两个数组都有序，因此相等时任意选一个即可。但是对于此题，两个排序数组并非有序，比如：

5 5 1
5 5 9

最终结果5 5 9 5 5 1是最大的，而只比较首指针相等时随机选肯定出问题。因此，比较方法是把剩下的两个数组进行字符串比较，找到字典序更大的那个数组，然后选使用该数组的首元素。因为这样可以保证后续更大的数字会先出现。

[caibirdme]

Count Numbers with Unique Digits 一般统计数字各个位置上有多个xxx，或者统计1..n有多少个符合条件Y的，都优先考虑DP通过排列组合进行状态转移。 设f[i]代表1..i位数一共有多少个unique number，可以推出：

• i位数一共有t = 10^(i-1)-10^(i-2)个
• i位数中一共有u = f[i]-f[i-1]个unique number
• i位数中有重复的的数字就有t-u个

利用上述信息，那么i+1位数中包含重复digit的数字可以这么构造：

• 不重复的i位数，选一个位放到放到最后构成重复数，一共有u*i个
• 有重复的i位数，最后一位随便填0..9，依然是重复的数，一共(t-u)*10

因此有重复的数的i+1位数，一共有p = u*i+(t-u)*i个，因此不重复的是w = 10^(i)-10^(i-1)-p个。 以上算的仅仅是i+1位数，加上之前的，因此有f[i+1] = f[i] + w

而求f[i]只和f[i-1]相关，因此可以用两个变量来存储，不需要开数组

[caibirdme]

Guess Number Higher or Lower II 这是一类比较常见的DP题目，如果没做过这类题，可能连题意都比较难理解。理解了题意，其实状态转移方程很好想。题意其实就是没猜一个数x，会损失x元。并且，极端情况下你每次猜都猜错。但由于每次猜都能排除掉一部分错误答案，因此，怎么用最小的代价让可猜测的数的范围快速收敛直到确定。 当然这样说也不好理解，但是为了做这类题，你必须理解。 f(i,j)表示从i猜到j，最小代价是什么:

f(i,j) = min{max{f(i,k-1),f(k+1,j)}+k}

与之相似的，还有扔鸡蛋。鸡蛋在某一层及以上往地上扔会摔破，该层一下扔则不会破，最少试几次能找出楼层。这道题其实完全是一样的，但是由于每次扔的代价都是1，因此不需要关注当前在第几层。

f(i) = min{ max(f(j-1), f(n-j)) } + 1

更进一步，如果告诉你总共只有m个鸡蛋，摔破一个就少一个，最少多少次能找到对应楼层。这里的关键点在于鸡蛋有限：

• 如果知道第i层楼不会摔坏，但只剩1个鸡蛋时，只能从i+1一次向上试了
• 如果第i层摔坏了，只剩1个鸡蛋，就需要从最下面开始依次试，直到第i层。
• 如果第i层坏了，那么就只剩m-1个鸡蛋，f(i,m-1)
• 如果第i层没坏，那么就是f(n-i, m)

f(i,m) = min{max{f(j, m-1) ,f(n-j, m)}+1}

本质上都是枚举扔鸡蛋的位置，根据扔的结果，分成两部分，然后因为要做最坏打算，因此取两个部分的最大值作为代价。枚举所有扔鸡蛋的位置，取所有中的最小值。把握这个原则，扔鸡蛋类的问题基本上就是送分题

[caibirdme]

Subarray Sums Divisible by K 对于连续子序列和或者积，基本上首先考虑前缀和数组。(sum[i]-sum[j]) % k == 0 可以推出sum[i]和sum[j]对k有相同的余数。因此统计所有的sum[i]%k，然后就可以得出结果了。这里需要注意的是，如果sum[t] < 0 ，需要单独处理一下：

8 - (-12)    % 5 == 0
3     -2
3    5+-2

4 - (-11)  % 5 == 0
4     -1
4     5+-1

所以
count[(MOD+sum[j]%MOD) % MOD] += 1;

类似的问题还有在数组中寻找连续子数组，和不超过K，问最大的和是多少。也是先求出前缀和。由于要求sum[i]-sum[j]<=k，等价于是sum[i]-K <= sum[j]。当我们枚举sum[i]的时候需要在0..i-1寻找最大的sum[j]，满足sum[j]<=sum[i]-K。因此可以动态维护一颗平衡二叉树，然后每次以logN的时间查出<=sum[i]-K的最大值

这题再进一步可以变成二维，找和不超过K的和最大的矩形。其实是一样，枚举i和j，把第i到j行压缩成一个元素，组成一列数组，然后用同样的方式求解。总体复杂度就是n*n*m*logm或者改变枚举顺序，m*m*n*logn，根据m和n的大小，选择相应的枚举顺序

[caibirdme]

Wiggle Subsequence 最直观的就是：

• up[i]表示第i个数一定在序列中且最后一次差是正数的长度
• down[i]表示……差是负数的长度

那么通过枚举前面的数字j：

• up[i] = max(down[j]) + 1 (a[i] > a[j])
• down[i] = max(up[j]) + 1 (a[i] < a[j])

总体复杂度是O(N^2)，但是题目要求O(N)，因此需要进一步优化。

这里有一个贪心的点，即，如果当前数字a[i] > a[i-1]，那么，如果a[i-1]是某个子序列中最后一个，且差大于0，那么a[i]肯定比a[i-1]更适合作为该序列的最后一个。因为a[i]>a[i-1]，肯定也能够与前面某个数差大于0，且由于a[i]更大，因此后续差为负的概率更大。 同理，如果a[i]<a[i-1]，假如a[i-1]和前面某个数差为负，那么选a[i]肯定比选a[i-1]好，因为后续有更大概率差为正。 因此

• 如果我们用up[i]表示以i结尾，最后一次差是正的序列长度，那么如果a[i+1] > a[i]，那么up[i+1] = up[i]，即选a[i+1]不会只会更好不会更差，否则up[i+1] = down[i]+1
• 对于down[i]，如果a[i+1] > a[i]，那么这显然可以构成一个更长的序列，所以up[i+1] = down[i]+1，否则，down[i+1] = down[i]。 而且，由于只和前一维有关，因此可以不用开数组，只有两个变量即可。

[caibirdme]

Frog Jump 每次跳的距离必须是比上一次跳的距离最多差1，假如上次跳k，这次只能k-1,k,k+1。由于坐标很大，距离也可能很大，并且很稀疏，因此用hashMap来存储状态更为合适。f: HashMap<i32, HashMap<i32, bool>>表示最后一次跳了j个units走到坐标a[i]，这个状态能否走到最后。 显然呢，f[i][j] = f[i+t1][j-1] || f[i+t2][j] || f[i+t3][j+1]，即从j-1,j,j+1中选一个步长跳。如果对应位置没有stone，则false，如果对应位置有stone，那么走到那个状态继续跳。 由于石子是有序的，因此可以用二分查找来减少下下一个石子的开销。

[caibirdme]

Split Array Largest Sum 这道题其实最简单就是二分答案+验证，然而它被归类到DP了，因此讲讲DP解法。 f[i][j]表示前i个数划分成j个子数组后，最大值最小是多少。 然后枚举k，f[i][j] = min(max(f[k][j-1], sum[i]-sum[k]))

[caibirdme]

Sentence Screen Fitting和Count The Repetitions这两道题其实都是一样的，只是换了个说法。通用的方法就是找循环节，关键点在于怎样设计状态，好让你能快速确定循环节。 对于第一个题目，<当填完某一行最后一个单词是w，且还有c个空格>，这可以用作一个状态，因为当下一次出现这个状态，那么这之间的就是循环节，可以进行无限循环。 对于第二个题目一样，<匹配完S1的第i个字符，匹配到了S2的第j个字符>。

但是你光知道状态也没用，因为你需要状态帮你判断循环节出现，当循环节出现时，你需要知道对应状态出现时匹配到多少行当时已经完整地填了几个sentence了，或者对应状态出现时匹配到S1的第几个字符串当时已经完整匹配了几个S2了。 有了这些数据，当循环节出现时就可以计算出循环节的长度，以及循环节内包含了多少个完整的匹配，然后根据循环节进行计算。

[caibirdme]

Unique Substrings in Wraparound String 因为要算子串的数量，子串必须连续，因此我们统计以每个字符结尾的子串最长有多长。假设以字符d结尾的子串最长为4，那么包含d的子串一共有 d dc dcb dcba4种。最终把所有的count值累加即可。

[caibirdme]

Remove Boxes 对于这类在数组中进行操作消除的题目，一般来讲都是二维的DP，枚举区间，然后根据题意进行转移并在转移过程中取最优值。这道题同样的思路。如果用f[i][j]表示box[i..j]的最优值，它确实具有无后效性。但是这里有个问题，由于每次merge的得分和k^2，我们在计算f[i][j]时，假设我们枚举一个k使得box[i]==box[k]，此时我们可以把i+1..j-1简单当做子问题计算，即f[i+1][k-1]，但是对于后续k..j这个区间，box[i]==box[k]仅仅是两个数merge，我们怎样构造出3甚至更多的个相同的数merge呢？ 一种办法是使用dfs，进行排列组合。比如我们可以计算出k..j一共有t个数等于box[i]，那么一共有2^t-1种选取办法，来构造合并。并且，每次选取之后会把k..j割裂成多个区间，我们需要分别计算小区间的结果并求和。这种方式使得问题过于复杂。

这道题我学习到的一种技巧就是“空间换时间”，通过加维度来表示更详细的状态，从而更容易地划分问题。如上所说，枚举k使得，box[i]==box[k]，此时合并其实只有2个数。假如我们把k当做要合并区间的右边界，如果我知道经过一系列合并之后，box[i]左边还剩t个和box[i]相同的数字，那么本次合并的得分就可以用(k+1+1)^2。因此我们多加一维，用f[i][j][k]表示，当0..i-1全部合并完之后还剩k个box[i]，合并i..j能得到的最大分数。

因为已经通过状态表示出merge的数量了，因此我们只需要枚举右边界即可。

f[i][j][k] = max(f[i+1][t-1][0] + f[t][j][k+1])   // if box[i] == box[t]