刷题记录

滑动窗口：和之前的做法类似，维护篮子里的水果的数量，遇到新水果就从前往后一一丢掉水果，直到篮子空了再装。复杂度$O(n)$
滑窗+字典优化：和昨天 LC: 3 的优化解类似，维护一个字典保存每种水果最后一个下标，则每次遇到第三种水果时，左指针的位置不需要一个个从左往右滑找，而是直接取两种水果中下标最小的值+1，它一定是左指针的新位置。复杂度$O(n)$

3-13

[01]-LC: 3. longest-substring-without-repeating-characters

滑窗：求最长子串的问题一般都是滑窗。题目要求不重复，所以直接上集合，滑动窗口，左右指针分别指向窗口的起点终点，维护一个变量ans表示左右指针的最大距离。右指针右移，经过的元素只要不在集合里就加入到集合中，如果在集合里就说明重复了，记录当前窗口的长度，左指针左移并从集合中移除，直到遇到这个重复的元素，此时滑窗的起点就是这个重复的元素+1。复杂度$O(n)$
滑窗+字典优化：上述方案中的集合以及左指针右移比较慢，考虑把集合换成哈希表，并把下标保存在哈希表中，这样当我们右指针找到重复元素时，左指针可以根据哈希表中的下标直接跳到重复元素的位置+1，并更新哈希表中该重复元素的下标。这里注意由于左指针不再像之前一样一步步回退，所以没法把原先的在哈希表中的元素清除，所以左指针有可能会跳到之前保存的下标，例如用例abba，所以左指针的跳跃应该当取max(重复元素下标位置+1, 当前位置)，这样保证左指针不会倒退就能保证答案的正确性。复杂度$O(n)$

[00]-LC: 27. remove-element^apple

partition：这个题就是标准的 partition 的板子，本质其实就是把所有的val放到数组的最末尾，所以直接交换法或者填坑法都可以。比如交换法就是从右边找到第一个不是val的，从左边找到第一个是val的，交换。复杂度$O(n)$，空间$O(1)$

[02]-LC: 39. combination-sum^apple

DFS+剪枝：直接参考之前的解法即可。排序，然后每次取用直到 target 不够取。

3-12

[00]-LC: 1051. height-checker^google

built-in 排序：直接排号序一一比对即可。复杂度$O(n\log n)$
计数排序：考虑到题目给的heights的长度是有限的(100 个)，所以直接用数组统计就能在$O(n)$时间完成排序。

[00]-LC: 925. long-pressed-name^google

朴素：这个题不难，但是 edge cases 特别多，比如name中的字符更多，typed和name比较完了但typed还有多的字符。具体做法：同时遍历两个字符串，如果字符不相同就直接返回 False，相同就假设字符为ch，维护两个 cnt，向后遍历统计typed和name中ch，直到不相同位置。比较两个 cnt 的大小，cnt1 更大就返回 False。直到遍历结束，如果此时两个字符串都遍历完成了，就说明可以返回 True，否则说明typed没有遍历完成。复杂度$O(m+n)$

[00]-LC: 482. license-key-formatting^google

朴素：先遍历去掉-并大写化，然后除k取余来保存第一组，剩下的每k个作为一组保存，整体返回。复杂度$O(n)$

[00]-LC: 388. longest-absolute-file-path^google

栈：先把字符串按\n分开，遍历数组，则每个元素前的\t个数表示该目录的深度。维护一个栈，栈的深度就表示当前目录的深度，整个栈就表示当前路径的绝对路径。如果当前目录的深度过低，那就需要出栈，直到深度合适再入栈。每次遍历到文件就记录一下当前绝对路径的长度，维护这个最大长度即可。复杂度$O(n)$

3-11

[00]-LC: 760. find-anagram-mappings^google

哈希：用哈希表存nums2的下标，因为可能存在重复，所以哈希表里的 value 是 deque 的形式。再遍历nums1得到答案。复杂度$O(n)$

[00]-LC: 1302. deepest-leaves-sum^google

BFS：题目要求的是最底层的叶子节点的和，所以使用 BFS 层序遍历，搜的时候计算当前层的和，最后返回这个和就是最底层叶子的和了。复杂度$O(n)$
DFS：题目也可以用 DFS 做，需要判断当前深度是否最深，复杂度也是$O(n)$，不过空间复杂度为树的深度$O(H)$

[00]-LC: 1237. find-positive-integer-solution-for-a-given-equation^google

朴素+剪枝：题目挺有意思，只告诉你函数递增，返回所有使 x+y=z 的解。可以把x和y从 1 取到 1000，如果等于 z 就记录结果，因为函数递增的，所以找到解或者结果超过z就可以直接 break 剪枝。两层循环都可以。复杂度$O(n^2)$
二分

[00]-LC: 1466. reorder-routes-to-make-all-paths-lead-to-the-city-zero^google

BFS：这个题目在给定了有向图的情况下要反转部分边，使所有点都能达到 0 点。可以从 0 点开始向外广度优先搜索(需要先建立无向图)，搜到了就在有向图里看这条边的走向和当前走向是否一致，一致就说明需要反转，记录下来。复杂度$O(V+E)$

3-10

[02]-LC: 162. find-peak-element^google

二分：关键点还是有坡必有顶。只要顺着坡走就一定有顶。所以二分法可以判断nums[mid]和它右边的值的大小关系，如果是小于右边的值说明还在爬坡，那一定还有顶，可以缩小左边界到mid+1，反之缩小右边界到mid。复杂度$O(\log n)$

[00]-LC: 459. repeated-substring-pattern^google

[00]-LC: 1021. remove-outermost-parentheses^google

朴素：维护一个变量表示当前括号的深度。当深度大于 1 时开始记录括号。最后返回即可。复杂度$O(n)$

[00]-LC: 1025. divisor-game^google

DFS+记忆化：博弈论经典题目，直接记忆化回溯快速解题。根据规则遍历所有情况即可。$O(n)$
DP：观察能发现 DFS 的做法可以直接变成 DP 解决问题，因为 DP 的下标是可以通过遍历搜索到的。复杂度$O(n)$
数学：打印 DP 数组会发现规律，奇数一定False，偶数一定True。所以可以直接返回not n&1。有个规律是两个人在取数时如果当前n是奇数，那下一个n一定也是奇数。因为必须在$[1,n)$之间取一个能被$n$整除的数，而奇数的因数都是奇数，所以下一个n一定是两个奇数相减，结果是偶数。而偶数则一定可以被 1 整除使下一个n为奇数。利用这个规则，先手如果拿到了奇数就无法摆脱奇数的状态，直到 base case n==1。复杂度$O(1)$

3-9

今天整理了 UF，抽空整理堆排。

[00]-LC: 118. pascals-triangle^bloomberg

朴素：经典杨辉三角。维护一个列表表示当前行即可。新的一行由上一行两两相加并两边补 1 得到。复杂度$O(numRows^2)$

;[00]-LC: 662. maximum-width-of-binary-tree^bloomberg

BFS：求二叉树的宽度，这个题最难的点在于它宽度的定义不是某一层节点的个数，而是某一层的左右节点的距离。所以我们在 BFS 的时候需要给节点编号，可以考虑成一颗完全树的编号(比如堆)，根节点编号为 1，那么节点i左右孩子的编号是i*2与i*2+1。那么层序遍历时计算队首和队尾的编号差就能得到答案。但这个答案用导致溢出。因为编号是为完全树编的，而给定的树如果故意非常深，那么编号就会非常大。所以在遍历当前层并添加下层节点及编号到队列时，还需要取队首元素的编号当作offset，在入队之前减去offset，保证每一层都是从 0 开始编号的。复杂度$O(n)$

[01]-LC: 35. search-insert-position^bloomberg

二分：经典二分找插入位点。复习一下手写法。复杂度$O(n\log n)$

[02]-LC: 547. number-of-provinces^bloomberg

并查集：老题，并查集。记得要路径压缩以及按秩合并。复杂度$O(V)$

3-8

今天把快排，快选还有归并的板子归纳了一下，明天整理 UF 和堆排！

[00]-LC: 404. sum-of-left-leaves^bloomberg

DFS：题目只要左叶子的和，但叶子本身不知道自己是不是左孩子，所以需要传参数告诉下面的节点是否是左孩子。复杂度$O(n)$

[01]-LC: 746. min-cost-climbing-stairs^bloomberg

DFS+记忆化：根据题目给的关系，当前位置i的 cost 一定是当前cost[i]加上上个阶梯或者上两个阶梯的最小值得到。再加上记忆化可以达到$O(n)$的复杂度。
DP：经典 DP 题，状态转移方程$dp[i]=min(dp[i-1],dp[i-2])+cost[i]$。复杂度$O(n)$
DP+滚动优化：当前状态仅与上两个状态相关，所以可以维护两个变量来求解。复杂度$O(n)$

[00]-LC: 1169. invalid-transactions^bloomberg

[00]-LC: 1029. two-city-scheduling^bloomberg

[01]-LC: 215. kth-largest-element-in-an-array

快选：用交换法完成 partition，返回 pivot 下标i，判断i与k的关系，如果i==k-1则是我们要的结果，否则去递归左部分和右部分即可。复杂度$O(n)$
堆：要找前 k 大的数，所以维护一个大小为 k 的小顶堆，存放最大的前k个数，则堆顶就是第k个元素。复杂度$O(n\log k)$

3-7

[00]-LC: 290. word-pattern^uber

哈希：基础水题，就是看单射是否重复。对于pattern和s各自构建哈希表，pattern的哈希表d为字母到单词的映射，s的集合s_set表示某个单词已被映射。遍历pattern，如果还没构建映射就构建，构建了就看该映射和这次的词是否相同。复杂度$O(n)$

[00]-LC: 542. 01-matrix^uber

BFS：题目和之前 LC: 1162 以及 LC: 994 很类似，都是从某一些点开始向外扩散的思想。所以直接用类层序遍历的 BFS，用一个变量step来维护当前层数。把所有数字为 0 的点全部入列开始 BFS，这些点上下左右如果有 1，且这个 1 并没有答案，就把当前 BFS 的层次step作为答案，并把这些点再次入列。复杂度$O(m*n)$

[00]-LC: 969. pancake-sorting^uber

朴素：每次在数组中找到最大值，通过两次翻转可以把最大的数放在最末尾(第一次翻转将最大值翻到最前面，第二次翻转将最大值翻到最末位)。复杂度$O(n^2)$

;[00]-LC: 581. shortest-unsorted-continuous-subarray^uber

双指针：题目要求找出最短的无序子数组，使其排序好后整体也排序好了。可以把这个数组分为三部分，其中左边和右边都是有序的，中间是无序的。这里有序除了本身要有序以外，左边要小于中间要小于右边。不难发现左右都一定是递增的，而中间的则不一定。所以从左往右遍历时，维护一个变量cur_max来表示当前最大值，如果在左右两部分遍历时，一定有nums[i]大于或等于cur_max；反之，则说明我们进入了中间部分，可以用一个变量来记录下标，从两侧遍历就能找到中间部分的两个边界。要注意从左往右遍历只能确认中间部分的右边界，因为乱序的部分可能存在一小部分有序，无法确认中间部分的左边界，但右部分是一定有序的，此时维护的变量就可以确定右边界。复杂度$O(n)$

[01]-LC: 1046. last-stone-weight

堆：每次取最大的两个元素，通过一定的计算再放回一个元素，典型的动态极值问题，直接用堆就可以操作了。复杂度$O(n\log n)$

3-6

[02]-LC: 198. house-robber^uber

mock 遇到这个题，再次练习

DP：练习更优的$dp[i]=max(dp[i-1],dp[i-2]+nums[i])$写法。
DP+滚动优化：虽然这是一维 DP，但它仍然可以用滚动数组的思想优化，因为其仅与前两个状态有关。

[00]-LC: 361. bomb-enemy^uber

前缀和：对于每一行每一列，分别计算其前缀和，如果是敌人E前缀和就+1，如果是墙W前缀和就置 0，如果是空格就可以放炸弹，在这个格子上累加当前的前缀和(即此时能炸到敌人的数量)。最后返回所有格子中的最大值即可。复杂度$O(m*n)$

[00]-LC: 243. shortest-word-distance^uber

贪心：遍历时维护两个变量表示下标，如果找到了word1或者word2，用维护的变量存放其下标。并计算其绝对值差即可。复杂度$O(n*max(len(word1),len(word2)))$

[00]-LC: 437. path-sum-iii^uber

DFS+前缀和+哈希：这题要求路径上连续任意长度和为targetSum，想到数组上任意一段连续的长度和就可以快速反应前缀和。前缀和想在$O(1)$时间找到targetSum就需要哈希表。整体复杂度$O(n)$
- 前缀和：前缀和presum可以放在 DFS 的入参中，以表示从 root 到当前节点的前缀和。朴素的前缀和本应是一个数组，取任意两点的差得到两点间子数组的和，但这个题如果直接用数组构建前缀和，每个节点都去遍历前缀和数组与当前presum的差是否等于targetSum的话时间复杂度就高了。
- 哈希：这里可以使用 LC: 1 two-sum 的哈希思路，反过来用presum去减targetSum，看这个结果是否在前缀和中，那这样我们就可以维护一个全局哈希表来表示当前路径的前缀和。考虑到可能有相同的presum，在哈希里表示为该 key 的数量即可。这样就可以在$O(1)$时间找到当前节点是否能和前面的路径构成targetSum。递归完成后在回溯前要把哈希表中当前节点的presum去掉(-1 即可)。这样哈希表中就只存在当前路径的前缀和。

[00]-LC: 113. path-sum-ii

DFS：LC: 437 的青春版，严格要求了必须从root-to-leaf的才算路径，无脑 DFS 然后判断叶子节点就行了。记得传个presum便于判断。复杂度$O(n*h)$，$h$为树的最大深度。

3-5

[00]-LC: 1176. diet-plan-performance^amazon

滑动窗口：k就是固定滑窗的宽度，可以在数组末尾加个 0 以处理特殊情况。直接把滑窗从头滑到尾，并维护滑窗内元素和，判断元素和与给的上下界的关系即可。复杂度$O(n)$

[00]-LC: 572. subtree-of-another-tree^amazon

DFS+暴力朴素：dfsroot时对每个节点都遍历subRoot，以检查是否相同。复杂度$O(m*n)$
DFS+KMP(built-in)：直接拼接字符串并用 built-in 完成 KMP。复杂度$O(m+n)$
DFS+KMP：前备知识：先序遍历中该树任意子树的都是连续的，所以可以把两棵树的先序遍历打出来，再进行 KMP 算法，要注意对于叶子节点的 None 也需要打出来，否则会有别的用例 WA。复杂度$O(m+n)$

[00]-LC: 1122. relative-sort-array^amazon

built-in 排序：直接用哈希表跑一遍arr2的元素和下标，下标需要减去 arr2 的长度(以保证比不在 arr2 的更靠前)，然后直接排序arr1且key=lambda x:order[x] if x in order else x。复杂度$O(n\log n)$
哈希：LC: 791 的换皮怪，怎么一样的题，号码到 1000+了就从 medium 变成 easy 了。还是用哈希统计arr1元素出现的个数，遍历arr2按顺序重新写入到ans即可，剩下的排个序加到ans末尾。设 arr1 和 arr2 元素个数分别为 m 和 n，则复杂度$O(n+m+(n-m)\log(n-m))$

[01]-LC: 1155. number-of-dice-rolls-with-target-sum^amazon

DP+滚动优化：之前的做法还可以进一步优化，可以直接起手用dp[0]=1来初始化，以规避n=1的初始化过程。其次遍历的过程也可以优化，因为第i-1个骰子的范围一定是$[i,k*i]$，所以从后往前遍历的范围是$[i,min(target,k*i)]$。其次dp[j]的对上一个状态求和的过程的下限不再是$[max(0,j-k),j]$了，$0$只能保证不越界，但实际上j-k还是有可能找到不可能出现的结果的。上个状态中骰子最小的下界应当为i，所以可以改为$[max(i,j-k),j]$。最后对于第i-1个骰子，我们还需要把dp[i]置 0。复杂度是$O(n*k*target)$的剪枝情况。

[01]-LC: 1160. find-words-that-can-be-formed-by-characters^amazon

哈希：构造 chars 的哈希统计表的同时，对每个 word 也构建哈希统计表。复杂度为$O(n)$，$n$为所有字符串的长度。

3-4

[00]-LC: 994. rotting-oranges^amazon

BFS：和 LC: 1162 一样的思路，把坏橘子考虑成发射源，多个发射源一起发射就一起加入到队列里进行 BFS 遍历即可。复杂度$O(m*n)$

[01]-LC: 59. spiral-matrix-ii^amazon

模拟：直接 while 循环里写 4 个方向的遍历即可，4 个方向需要判断是否越级以及是否覆盖到已填的格子。注意每个方向走完需要回退一格。复杂度$O(n^2)$
模拟：4 个方向可以用directions来表示，这样不需要写 4 个重复的循环代码，而是判断越界或者覆盖到已填的格子时转向即可。复杂度$O(n^2)$

[03]-LC: 1. two-sum^amazon

哈希：用哈希表构建value到index的映射，遍历列表时先看target-num是否在哈希表中，不在就将num添加到哈希表中，复杂度$O(n)$

[00]-LC: 957. prison-cells-after-n-days^amazon

暴力法：直接暴力法会 TLE。复杂度$O(n)$
位运算优化+找规律：考虑只有 8 个牢房，所以对于任意给定的输入，在相同的规则下，输出一定是有规律的。我做题的时候直接打印了所有情况找到了规律，它是 14 个一循环，所以直接算出前 14 个状态，然后对于给定的n直接进行一次取余即可。另外牢房可以用位运算优化，由于规则给的左右的情况相同就返回 1，直接对当前状态分别左移和右移 1 位，再去头去尾即可。复杂度$O(2^c)$，c 为牢房的个数

3-3

[00]-LC: 653. two-sum-iv-input-is-a-bst^amazon

集合+DFS：和 LC: 1 一样的思路，只是换成了树。深搜的时候用集合维护已经遍历的点，同时查找target减当前点是否存在于集合，缺点是并没有利用 BST 的特性。空间$O(n)$，复杂度$O(n)$
双指针+DFS：和 LC: 167 以及 LC: 1214 一样的思路，用双指针从 BST 的两端开始遍历，这里遍历要用非递归的写法实现。空间$O(h)$，复杂度$O(n)$

[00]-LC: 1071. greatest-common-divisor-of-strings^amazon

built-in：通过str1+str2==str2+str1判断是否存在这样的串，存在就直接math.gcd(a,b)求最大公约数，返回str1[:gcd]即可
数学：手动实现辗转相除法，核心是拿大数对小数取余，小数和取余重新构成大数和小数，重复直到小数变成了 0，当前的大数就是 gcd。复杂度$O(\log_{10}max(n_1,n_2))$

[00]-LC: 5. longest-palindromic-substring^amazon

中心扩展：在给定的字符串里找最长的回文子串，最好想的暴力法就是对于每个字符串，向两边拓展直到不构成回文子串，这里有两种情况要考虑，回文子串长度为偶数和奇数，所以遍历时对于i，需要分别考虑i向两边拓展的情况以及i与i+1向两边拓展的情况。最后比较找到的最长子串，返回最长的节课。这里建议抽象出个函数来完成拓展的过程，会让代码更清晰。复杂度$O(n^2)$。

[00]-LC: 973. k-closest-points-to-origin^amazon

这个题目的本质其实还是topK，只是把数组的数换成了点到原点的距离。我对快排/快选的 partition 还是不太熟练，要多写写。

堆：维护一个长度为k的大顶堆来存前k小的元素。遍历数组，如果元素比堆顶小(即比前k小的元素最大的还要小)，则移除堆顶，把该元素入堆，否则直接跳过，可以把堆内元素想象成k个候选人，最可能被挤出堆的就是这k个里最大的，也就是堆顶。复杂度$O(n\log k)$
快选：用交换法 partition 做的。根据 partition 后在pivot左边的数组长度来判断，如果正好等于k，那就直接返回即可。如果大于k，那就对这左边的元素再次 partition，如果小于k，则小于的部分以及pivot保留，对右边的部分再次 partition，注意这次的k应当变为k-n-1。(切片排序法)。平均复杂度$O(n)$

[01]-LC: 47. permutations-ii

DFS：深搜并回溯，这个题是标准的八皇后回溯，需要维护visited并且在一次子过程调用完成后将visited改回为 False。此外题目中给的nums可能会有重复的，而题目要求结果不能重复。考虑一个递归树，重复的情况就出现在同一个节点的所有节点里有重复，显然先遍历的节点会把后来遍历的节点的所有情况覆盖掉，比如[1,1,2]，遍历时首先访问第一个1，随后访问第二个1(兄弟)，而第一个1的子过程已经覆盖了后者的所有情况，所以需要对第二个子过程剪枝。具体来说就是对于已经排序了的nums而言，nums[i]==nums[i-1] and not visited[i-1]的情况要跳过。复杂度$O(n*n!)$

[01]-LC: 46. permutations

DFS：深搜回溯，和 LC: 47 的解法一样，而且由于给了前提数组不会重复，所以只用维护 visited 数组即可，复杂度$O(n*n!)$

3-2

[00]-LC: 717. 1-bit-and-2-bit-characters^adobe

朴素：直接判断当前 bit 是否为 0，为 0 就向前跳 1 格，为 1 就向前跳两格，复杂度$O(n)$

[00]-LC: 703. kth-largest-element-in-a-stream^adobe

堆：给的输入是数据流，所以动态极值直接想到堆。维护一个长度为k小顶堆即可。比堆顶小的元素直接不要，这样堆顶元素一定是第k大的元素。这个题麻烦在他初始化的数组可能没有k个元素，需要在 add 的时候判断元素够没够 k 个。每次 add 的复杂度$O(\log n)$

[00]-LC: 9. palindrome-number^adobe

转字符串：直接转字符串比较即可$O(\log_{10} n)$
比一半：在x逐步自除 10 的过程中，构造一个反转的数ans，当这个数不再小于x的时候停止循环，此时x和ans分别是左半边的结果和右半边的反转数，如果原先的x的位数为偶数个则直接比较 x 和 ans 是否相等即可，如果是位数为奇则将ans除 10 后比较。要注意这种方式会遗漏x以 0 结尾的情况，x以 0 结尾会让ans在乘 10 增位时无法增加位数。而且以 0 结尾本就不可能是回文数，直接作为 edge case 处理即可。复杂度$O(\log_{10} n)$

[00]-LC: 415. add-strings^adobe

built-in：直接转 int 再相加再转回 str 即可。(面试不允许)
朴素：和 LC: 2 类似方法。按位相加并进位即可。当然也可以通过补足量的 0 后再相加并进位，最后去掉 0 的方法完成。复杂度$O(n_1+n_2)$

[00]-LC: 315. count-of-smaller-numbers-after-self

暴力法：直接反向遍历，见一个就往新数组里合适的位置用二分插一个，它的下标就是要求的结果。复杂度$O(n^2)$，考虑到现代计算机对于向列表里复制/移动都有特殊处理，这个暴力法竟然能在 LC 上 AC。
built-in：通过SortedList这个容器实现了向数组里插入且保证 sorted 的情况下也只需要$O(\log n)$时间，复杂度$O(n\log n)$
归并排序：真正适合面试的算法。这个题和 bala 的第二次作业最后一题以及 BS: 757 有异曲同工之妙，本质都是在找逆序对。这个题更隐晦一些，要求右边小的，其实右边小的就说明这是个逆序对了。但题目求的不再是总逆序对个数和了，而是确切的所有数的逆序对个数的数组。所以在归并排序的归并中，需要传入的不再是原数组，而是原数组的下标，这样才能在找到逆序对时把答案保留下来。此外，逆序对个数的计算可以维护一个变量count来表示，在合并时，判断较小者使用nums2就说明找到了一个逆序对，count+=1，而这个数对应的逆序对是所有nums1尚未遍历完的数，所以等它们归并时再计入答案即可。复杂度$O(n\log n)$

3-1

[00]-LC: 1331. rank-transform-of-an-array^amazon

排序+哈希：排序并用哈希记录其rank，最后按顺序返回。复杂度$O(n\log n)$

[00]-LC: 1214. two-sum-bsts^amazon

DFS+二分搜索：在 DFS 树 1 的时候对树 2 进行二分查找，利用了二叉搜索树的性质但复杂度高$O(n_1\log {n_2})$，空间复杂度降低$O(h_1+h_2)$(h 为树的深度)
DFS+集合：DFS 树 1 并用集合记录节点值，再 DFS 树 2 并检查 target-节点的结果是否出现在集合中，复杂度降低为$O(n1+n2)$，但空间复杂度提高为$O(max(n1,n2))$。在 LC 的用例中，python 用这个方法跑的最慢。(大概是慢在 hashset 的计算与写入)，且该方法没有利用 BST 的性质。
DFS(非递归)+双指针：考虑到 BST 的中序遍历是有序的，可以把两棵树想成是两个有序数组，就变成了 LC: 167 的类似思路，左指针就是正常的中序遍历，右指针就是反向的中序遍历。和正常的遍历不同点是，左右指针的继续遍历依赖于双方所指向的节点和。所以很难直接使用递归方法去遍历，而是需要使用辅助栈进行非递归中序遍历。复杂度$O(n1+n2)$，空间复杂度$O(h1+h2)$。这个方法合理的利用了 bst 的性质且复杂度较低。

[01]-LC: 167. two-sum-ii-input-array-is-sorted

双指针+二分优化：双指针是一步步缩小范围找答案，考虑到数组是sorted，显然希望能用二分法加速缩小范围。但要注意不能直接使用二分法去找目标，否则复杂度会变为$O(n\log n)$，因为每次找到底的开销为$\log n$，而 worst case 需要找$n$次。正确应用二分法的方式是，每次只试探一次：双指针是判断left+right和target的关系，而我们可以在此基础上额外判断一端加 mid与target`的关系。试探成功就可以舍弃一半数组，失败就只缩一步，这样确保了最坏情况的复杂度为$O(n)$，而最优情况的复杂度是$O(\log n)$。

2-28

[00]-LC: 292. nim-game^adobe

数学+博弈论：题目每次只能取 1-3 中的任意数，且可以重复，考虑 base case 即n为 1-3，则先手必胜，再考虑另一个 base case 即n为 4，则先手必败，可以假设先手取$1\leq a\leq3$，那后手一定能取到$b$使$a+b=4$。再推理一下就能发现如果当前n能被 4 整除，则我无论怎么取，对手一定都能在 1-3 里取到数使当前n能被 4 整除。所以只要n能被 4 整除，先手必败，否则先手必胜。复杂度$O(1)$

[00]-LC: 461. hamming-distance^adobe

题目就是求两个数异或后二进制的 1 的个数。

built-in：直接用bin(x ^ y).count('1')，复杂度$O(n)$
位运算：异或后用xor&=xor-1来翻转数字以计算 1 的个数。复杂度$O(\log n)$

[00]-LC: 7. reverse-integer^adobe

这个题目对 python 用户极端不友好，要求不使用比32-bit更长的数据。而且正反取余在 python 里还不一样(更数学)。

朴素：不考虑题目的限制，直接所有数取正，然后一位一位加就行。复杂度$O(\log_{10}n)$
按要求：对于 python 来说，负数情况下需要用负数来整除和取余，负数整除负数的结果还要记得重新改为负数。核心点是在ans自乘 10 之前先检查是否溢出，有两种，一个是ans大于$(2^{31}-1)/10$的情况，另一个是ans正好等于该边界时但是leftover大于 7。当然如果 ans 是负数就对应负数的情况，即小于$(-2^{31})/10$的情况或等于边界且leftover小于-8。复杂度$O(\log_{10}n)$

[00]-LC: 561. array-partition-i^adobe

贪心：题目要求给数组两两组队，每个队取最小值，使这些最小值的和最大。考虑到数组中的较小者一定要和别的数字组队，所以把较小的和较小的组队才能使总和最大。直接对数组排序，每两个数字取一次并累加。复杂度$O(n\log n)$

[01]-LC: 40. combination-sum-ii

回溯+剪枝：比起 LC: 40，这个题要求每个数字只能使用一次，而且不能有重复的情况。数字只使用一次比较容易想到，循环的时候传递 dfs 时传i+1即可，则每次 dfs 都是从candiates[i+1]开始遍历。但candidates可能会有重复的数字，比如[1,1,2,5]，而target是 8，这种情况下第一个 1 搜到的答案会和第二个 1 搜到的答案部分重复(第 1 个 1 搜到的更全面)，所以可以对candidates排序，在遍历第二个 1 时规避candidates[i-1]==candidates[i]的情况，因为只需要跳过第二个 1，所以同时还要满足i>cur。复杂度$O(n*2^n)$

[01]-LC: 39. combination-sum

DP：这就是背包问题的回溯版，需要把得到target所需的内容保存起来，所以 dp 数组里存所需的内容即可，因为每次需要把上一格子的内容复制一遍，所以复杂度为$O(n*(target/min)*target)$
回溯+剪枝：用回溯直接去模拟每次拿取，要注意这里不应重复取用(所以回溯时应从i到n取用candidates)，递归树最大深度为$target/min$，所以最坏情况每次遍历长度为$n$，每次深度为$target/min$，故整体复杂度为$O(n^{target/min})$。

2-27

[00]-LC: 346. moving-average-from-data-stream^amazon

队列：直接用队列就能很好的实现这个题，每个操作的复杂度都是$O(1)$

[00]-LC: 1128. number-of-equivalent-domino-pairs^amazon

哈希：对每一个 domino 二元组都排序，然后直接用哈希表统计个数x，x个 domino 可以形成$x(x-1)/2$对，最后再求和即可，复杂度$O(n)$

;[00]-LC: 836. rectangle-overlap^amazon

第一次 mock 的时候简单题没做出来，反而是 medium 做出来了。

数学：画图是最好理解的，直接随便画两个重叠的矩形并且把已知的坐标标出来即可。如果有重叠，则重叠部分在 x 轴的投影一定是从max(rec1[0], rec2[0])到min(rec1[2], rec2[2])。y 轴类似，所以只要任意方向的投影存在就说明二者有重叠。复杂度$O(1)$

[00]-LC: 763. partition-labels^amazon

集合+栈：遍历时维护可能为一组的集合，每次加入新元素时向前搜索看自己是否在前面的集合中，在的话就把过程中所有元素都出栈并求并集，再把这个元素压栈。遍历结束就得到了分组，复杂度$O(n^2)$
哈希：把上面方法的栈设法改成哈希表就能降低复杂度。分组的定义可以理解为组内最后一个元素不会再在后面出现，所以我们可以第一次遍历时用哈希表记录每个元素最后出现的下标，即为last[ch]。接下来只需要遍历时维护一个变量保存已遍历字符的最大last[ch]就行了，一旦当前下标等于这个最大值，就说明这个组内只有这些元素，就可以返回长度了，复杂度$O(n)$。

[01]-LC: 814. binary-tree-pruning

DFS：设计递归函数为本身就能返回按要求剪枝后的树，对自己的左子树和右子树分别递归调用子过程，并把左右子树返回为调用后的返回值。左右子树都已经修剪完成了，如果左右子树存在，或当前节点为 1，则说明这个节点不会被剪掉，返回当前节点，反之返回 None。复杂度$O(n)$

2-26

[00]-LC: 1160. find-words-that-can-be-formed-by-characters^amazon

哈希：直接构造char的哈希统计，对于每个word的每个字符去验证其是否在哈希表中且数量是否大于 0，是则消耗掉(统计值-1)，否则就直接 break。如果没有 break 则说明word能拼出来，累加答案。复杂度$O(s*t)$，$s$为chars字符串的长度，$t$为words的个数。要注意这里涉及哈希统计值的修改，所以遍历前需要深拷贝一次。

[00]-LC: 1155. number-of-dice-rolls-with-target-sum^amazon

DP+滚动优化：题目里给了个比较大数字的 example，容易想到用动规做，这个骰骰子找 target 其实可以简化为背包问题，定义动规数组dp[i][j]表示前i个骰子的和得到j的个数。思考只增加一个骰子动规数组的变化就能想到状态转移方程$dp[i][j]=\sum_{t=1}^k dp[i-1][j-t]$，即再投第i个骰子时，它有k种可以使和变成j，把上个状态的加起来即可。题目还有些边界情况比如j-t不能小于 0 等。此外当前状态仅与上一状态有关，所以可以用滚动数组优化，复杂度$O(n*target*k)$

[01]-LC: 1319. number-of-operations-to-make-network-connected

UF：经典并查集，不要去想怎么移线缆，最小的移动次数一定是当前连通子图数-1。所以直接用并查集算连通子图数即可，前面要判断其 connections 总数是否满足让其全部连通。复杂度$O(E)$，顺便一提这个题如果不按秩合并的话速度会慢很多。

2-25

[00]-LC: 1022. sum-of-root-to-leaf-binary-numbers^amazon

DFS：题目要求叶子节点的和，运算方式是从上到下移位得到，所以递归入参除了要传node还要传val表示上面节点的计算结果。base case 有两种情况(我 mock 的时候没注意这一点，折腾了半天)。一个是节点为空，一个是节点为叶子节点(这个 base case 我一开始以为不需要，惨痛的教训)，节点为叶子节点就返回val左移 1 位+自己的 val。空节点就返回 0。递归就是直接递归调用左右子树即可，传入的参数和叶子节点的val一样，左移 1 位并加上自己。复杂度$O(n)$

;[00]-LC: 1258. synonymous-sentences^amazon

这个题充分的教育了我不要困了做算法题，全是他妈错的，脑子是糊的。

UF+回溯：题目的第一个难点是synonyms(的拼写(bushi))可能会存在 a 和 b，b 和 c 都是近义词的情况，所以这里synonyms可以看成是连接点的边，我们要先用并查集把连通的词找出来。由于题目要求我们用给出的近义词来替换text中的词，所以我们用text和synonyms中都出现的词作为哈希表repls的 key，并把近义词以集合的形式放入哈希表。题目的第二个难点是替换。替换最好的方式就是直接回溯，取text.split(' ')中需要替换的词以及其在数组中的下标形成列表words，这就是我们要回溯的数组。设计递归函数，入参为递归深度，对于当前深度i找到需要替换的词word以及其下标idx，替换并递归调用到下一层。替换完成后再恢复这个词原来的结果。设需要替换的词有$n$个，每个词可替换的词有$m$个，复杂度$O(m^n)$

[01]-LC: 924. minimize-malware-spread

并查集：用并查集可以在$O(V)$时间找到所有子连通分量，以及并查集每个 root 的 size，随后遍历initial，考虑到一个连通分量下如果有两个或以上的节点在initial则去除了也无效，所以要进行去重。最后在剩下的initial节点找出其 root 的 size 最大的(即最大连通分量)，取其最小值返回。复杂度$O(V+n)=O(V)$，n 为initial的长度。
DFS：染色问题解法，和并查集类似。用 DFS 去搜所有initial节点并染色，使同一连通分量的节点具有相同颜色(即给定了分组)。剩下的处理类似，复杂度$O(V+n)=O(V)$

2-24

[00]-LC: 541. reverse-string-ii^amazon

amazon 的水题。

朴素：循环每次步进2k，循环过程中把前k个反转即可。复杂度$O(n)$

;[00]-LC: 1192. critical-connections-in-a-network^amazon

暴力 DFS：对每个边都去假设其不存在，然后从一端深搜到另一端看是否连通，复杂度$O(E*V)$，超时
DFS+tarjan：tarjan 可以简单理解为通过一次 DFS 在无向图里找环(准确的说是有向图里找强连通分量)的算法，有向图里的强连通分量在无向图里可以理解为是找环。而这个题要我们找脆弱边(也被称为桥，即删除后使图不再连通的边)。首先明确一点，如果一个边在环里，那么这个边一定不是桥。反过来也成立(暂不知证明)。所以只需要找到图里所有的环并删除环的边，剩下的就是桥(优化版可以直接找桥)。复杂度$O(E+V)$，具体就直接应用 tarjan 算法：
- tarjan 算法基本思想：DFS 时维护一个全局数组visited，初始化为-1以表示没有访问，如果访问了则暂时记录为 DFS 的深度。所以 DFS 的入参需要传入当前搜索的深度。那就不难想到如果某个节点i在深搜时发现节点j的visited[j]要小于等于自己的当前深度，那说明深搜的过程一定遇到环了，这一趟递归的路径全是环，但现在只有递归树的最深处(即节点i)知道有环，而且这个环是从visited[j]一路连当前节点的depth，这个信息需要向上传递，所以我们把visited[j]返回。返回之前把j到i这条边记录下来。
- tarjan 思想总结：以上是 tarjan 的基本思路，对于当前节点i周围的点去调用子过程找到比自己更浅的节点，则i和比自己更浅的点间的边一定在环中。此外递归过程是从浅到深最后再回溯到浅，所以如果i周围有多个比自己浅的点应该取最小值返回(防止漏掉回溯后和自己上层形成的环)。
- 优化(直接找桥)：因为节点i与其周围较浅的节点之间的边一定在环中，那反过来节点i周围比它深的节点是不是一定不在环中呢？答案是否定的，因为我们无法保证遍历的顺序，也许i节点最后才访问某个已经访问过的节点j，尽管j确实在环中，但visited[j]保留的是其深度信息，而不是其所在环的最浅深度，对此我们可以优化visited数组，可以在递归结束前用visited[i]保存自己找到的最浅的深度。这样就可以直接找到桥了。
- 此外真正实践的时候递归的入参还需要传 parent 节点(因为两个节点间的一条边不算环)，需要跳过。

[01]-LC: 547. number-of-provinces

并查集的基础题型，回顾学习一波。

DFS：用 DFS 搜每个连通的点即可，入参为节点号，dfs 和这个节点连通的每个点，设置visited，复杂度$O(n)$
UF 工具类：手写了并查集的工具类，有两个重点：调用查找的时候要记得路径压缩，建议写成递归式的查找；合并时最好按秩合并，即小树往大树身上合并。复杂度$O(n)$
嵌入式 UF：尝试了不单独写 UF 工具类(因为看起来像在背 UF 的代码)的最佳实践，需要抽象出find函数，因为合并一般就一次操作，所以可以直接inline写，复杂度$O(n)$

2-23

;[00]-LC: 675. cut-off-trees-for-golf-event^amazon

BFS：题目要求按从小到大的顺序去砍树，所以本质是给一个点序列，求序列相邻两点间的最短距离，返回其和。我 mock 这题想到方案了，但是答案差一点没写出来，很烦。这个题里有障碍物，所以求最短距离需要通过 BFS 获得，思路比较清晰，但实现起来代码量大，容易有各种 bug。具体的，先遍历数组，把每颗树附带其坐标按照大小排序(复杂度$O(mn\log{(mn)})$，有$m*n$个树，所以要进行$m*n$次BFS，每次 BFS 最坏情况是搜索了每个点，复杂度$O(m*n)$，所以总复杂度为$O((mn)^2)$
BFS 优化：另一种实现 BFS 的方式，但目前其实没有搞的很透彻。上一种方式就很好。

[00]-LC: 819. most-common-word^amazon

朴素：替换所有标点符号为空格，然后再用split方法拆分并剔除 banned，最后用哈希表统计。复杂度$O(m+n)$

[01]-LC: 面试题-17-17. multi-search-lcci

前缀树：用所有small串构建前缀树，(设k为所有small串的字符数和则复杂度为$O(k)$)，然后用big的所有后缀子串去匹配(也可以理解为是从 big 的每个位置作为起点的串)，如果在前缀树里找到了那就保存结果，没找到就从下一个起点开始，匹配的复杂度为$O(n*max(smalls[i]))$，整体复杂度$O(k+n*max(smalls[i]))$。
哈希：这题的哈希解法比较另类，把big每个字符的下标用哈希存起来(存为列表即可)，然后遍历small子串，此时已经可以在$O(1)$时间获取big中每个字符的下标，直接用small去对比即可。遍历big串复杂度$O(n)$，对比子串复杂度$O(n*k)$(最坏情况smalls中每个字符都要和big的每个字符比)。最坏情况复杂度$O(nk)$
KMP：求子串的问题当然也可以用 KMP 解决，和 LC: 28 完全类似，不过这里的 KMP 匹配到子串后不能停下来，而是要回退一步j，继续循环。设$m$为smalls的个数，则复杂度$O(k+m*n)$

[02]-LC: 2. add-two-numbers

$O(1)$空间法：之前一直都是开辟新空间存放得到的链表的，完全没练过原地存放，edge case 也不少，练习一下以防止面试官刁难。

2-22

[00]-LC: 445. add-two-numbers-ii^microsoft

这个题是 LC: 2 的升级版，它把链表顺序反了过来，高位在前，考点是如何不反转链表得到相加的答案。

朴素：很容易想到直接反转链表，再两个链表相加即可，这里两链表相加可以新开链表，也可以直接原地修改，如果面试没要求记得要问问。复杂度$O(n_1+n_2)$
递归进位：不考虑进位的情况，只要对齐两个数组并且相加还是相对容易实现的，剩下的进位部分可以通过递归调用来处理，把反转链表的部分隐藏进递归调用栈中。具体的，递归函数给入参节点p，函数返回进位结果(0 或 1)，base case 是如果节点为空就直接返回 0，随后当前节点的val自增下个节点的进位结果(递归调用p.next)，修正自己的结果(%=10)，根据是否需要进位返回 0 或 1。复杂度$O(n1+n2)$

[00]-LC: 669. trim-a-binary-search-tree^microsoft

DFS：如果节点小于low，那它只有右边的部分有可能保留，递归调用其右部分并返回。类似的，大于high则递归调用其左部分并返回。如果正好处于边界之中，则分别递归调用其左右部分，最后返回。复杂度$O(n)$

[00]-LC: 1185. day-of-the-week^microsoft

built-in 的屑：小技巧，不知道或者不记得 api 名字的话，可以试试打印obj.__dir__()，复杂度$O(1)$
朴素：计算这一天到 0 年 1 月 1 日之间经过了多少天再%7即可。具体需要记得闰年计算方法，选择公元起始点是方便year*365再去加year//4再去减year//100再加year//400。复杂度$O(1)$

[02]-LC: 232. implement-queue-using-stacks^microsoft

经典双栈实现队列。

双栈：对于输入的序列，只 push 到back栈中，只在需要的时候(即 front 没有元素可以出队了)，才将back一次性倒腾到front中。可以保证对于输入的序列，每个元素最多只入栈和出栈了两个栈各一次。均摊复杂度$O(1)$

[01]-LC: 677. map-sum-pairs

熟悉前缀树写法就比较容易 AC。

前缀树+无限嵌套：使用了 zhy 秘技之无限套娃字典defaultdict(x:=lambda: defaultdict(x))。不过因为默认为字典类型，反而有很多别的地方需要额外判断。具体细节看下面。复杂度$O(n)$
前缀树：普通实现，题目的 sum 要求的前缀树的任意节点的前缀和，所以每次插入时需要给每个节点累加val，同时题目要求如果插入相同字符，则要替换掉val，所以插入前需要先搜索其是否存在，如果存在则需要先把它对应val减掉。复杂度$O(n)$

[00]-LC: 402. remove-k-digits^microsoft

昨天太晚没有总结这个题，今天补上。题目有点难想，mock 我只想出了$O((n-k)*k)$的算法，其实当时想到了单调栈，后来花了巨长时间想出了单调栈的类似解法。但最后选择了题解中更为合理的思路。

暴力+剪枝：题目要求需要移除的数字，所以反过来也可以求需要保留哪些数字，对于每一位要保留的数字，我们需要在合理范围内保留最小值。具体的，第i位要求的数字应当取num的某一范围内的最小值。这个范围的左边界为第i-1位在num中的位置+1(上个数字位置的下一个)，右边界则为k+i。每次在这个范围内取最小值即可。复杂度$O((n-k)*k)$
单调栈：考虑到答案的每一位在遇到临界点(即已经移除掉了 k 位数字，此时只能把剩下的位复制到答案上)之前都是单调递增的，我们可以维护一个单调栈，栈顶最大，单调栈在遇到比栈顶更小的元素时会弹出当前栈顶，直到满足单调性。此时弹出的元素其实就是需要被移除的元素。所以在单调栈弹出时维护一个变量，保证单调栈只会弹出k次即可。根据最后的k值返回答案。复杂度$O(n+k)$
单调栈复杂版：自己想的单调栈写法，当时始终没有想清楚弹出的元素就是需要被移除的，而是在用n-k思考问题，在正常的单调栈过程中通过判断len(stack)+n-i==n-k，即单调栈过程中如果栈内元素加上剩下的元素已经够n-k那就直接可以返回了。其实本质就是如果已经 pop 了k次。复杂度$O(n+k)$

2-21

[01]-LC: 75. sort-colors^microsoft

哈希：第一次遍历统计不同颜色的个数，第二次遍历重新向数组写入颜色，复杂度$O(n)$
一趟遍历：这是题目的考点，是类 partition 的操作。我们维护两个指针left和right，$[0,left)$区间全部是 0，$[left,i)$区间全部是 1，$(right,末尾]$全部是 2。确定了分区后，遍历时维护好分区即可，比如循环结束的条件就应该为$i\leq right$。具体的，对于遍历中某个时刻的nums[i]，如果它是 0，那就和left交换，并left+=1然后i+=1，如果是 1，那就不用管，直接i+=1，如果是 2，那就和right交换，right-=1，但要注意此处i不能继续右移，因为有可能换到i的还是 2，所以把它当新的i继续循环即可。复杂度$O(n)$

[00]-LC: 509. fibonacci-number^microsoft

递归：写好 base case 后return f(n-1)+f(n-2)即可。复杂度$O(2^n)$
DP：根据斐波那契公式有状态转移方程$dp[i]=dp[i-1]+dp[i-2]$，复杂度$O(n)$
滚动 DP：因为dp[i]仅与前两个数字相关，改进为滚动动规数组，降低空间复杂度至$O(1)$，复杂度$O(n)$

[00]-LC: 575. distribute-candies^microsoft

贪心：题目要尽可能多种类的糖，但是总数不能超过n//2，所以用集合获取糖果的种数 m，return min(m,n//2)即可。复杂度$O(n)$
排序：如果希望空间复杂度降低到$O(1)$，则可以排序糖果，遍历时计算不同的种类(不用额外空间)，再返回种类与 n//2 的较小者。复杂度$O(n\log n)$

[01]-LC: 208. implement-trie-prefix-tree

前缀树：实现前缀树，写个基础板子。前缀树其实就是一个多叉树，方便快速查找前缀。假设关键词长度为 n，则插入和搜索的复杂度都是$O(n)$。

[00]-LC: 796. rotate-string^microsoft

暴力法：这题的测试用例限制比较小，直接暴力法双重循环也能 AC，复杂度$O(n^2)$
KMP：这里把题目的s复制到s末尾，则其子串包含了所有旋转的情况。剩下的就是求 goal 是否包含在这些子串中，直接使用 KMP 算法可实现复杂度$O(n)$，KMP 详解参考 LC: 28。

[02]-LC: 28. implement-strstr

KMP：经典 KMP 算法，关键要理解 next 数组的含义与构建方法，next 数组：真前后缀相等串的最大长度，同时也是在子串和原串匹配失败时的回退点(后缀匹配失败后，可以直接从前缀继续出发匹配)。它的本质就是动规数组，状态转移方程为：$next[i]=j$，而j的状态转移方程为$j=next[j-1](needle[i]!=needle[j])$，相等时j+=1，j表示的其实是后缀的开头，i在滑动时j会试探其是否和i相同，相同则说明前后缀长度+1，不同则回退到上一个"保存点"，即前缀退一格去尝试。复杂度$O(m+n)$ 最好的记忆点是回忆子串aabaaf的 next 数组构建过程。从i=1开始遍历子串(i 是潜在的后缀头)，前缀则从j=0开始，如果两者相等，j+=1，next[i]=j，如果不等则回退j，直到退到 0(前缀和后缀无匹配)。构建 next 的过程和匹配的过程非常相似，甚至可以把 next 的构建看作是和自己在匹配。

2-20

~~昨天的债有 3 道总结以及复习 KMP，还有 4 道微软的题。今天还有日常抑题+4 道微软的题。冲鸭！~~

昨天的债除了 KMP 都还了，但今天的 4 道微软只能留给明天了，明天要冲 KMP 和 8 道微软的题还有日常抑题😢

[00]-LC: 237. delete-node-in-a-linked-list^microsoft

原地修改：把当前节点的值和后继全部改成下一个节点的值与后继即可(不要思维固化，说是删这个节点但不一定真要删它)，复杂度$O(1)$。

[00]-LC: 191. number-of-1-bits^microsoft

朴素：每次判断末尾是否为 1(n&1)，是则计数+1，右移 n，直到 n 为 0。复杂度$O(\log n)$
位运算优化：上面的思路每一位都要比较并计数，而用n&=n-1直到 n 为 0，可以确保只循环 1 的个数次。复杂度$O(\log n)$

[01]-LC: 88. merge-sorted-array^microsoft

朴素：每次取两个数组中的较小者放入新数组中，最后把新数组覆盖回nums1，时空复杂度均为$O(m+n)$
空间优化：考虑到给定的nums1本来就是够长的，且nums1后部分为空，所以每次取两数组中的较大者填入nums1的尾部，空间复杂度仅为$O(1)$。复杂度$O(m+n)$

[00]-LC: 285. inorder-successor-in-bst^microsoft

DFS：遍历二叉树，把中序遍历的结果保存起来再找p的后继即可。复杂度$O(n)$
DFS+二叉搜索：因为题目给的是 BST，其重要性质是 BST 的中序遍历是递增的。即p的后继一定是刚刚大于p的节点，而p节点已给出，那只有两种情况：后继在p的右边或者上边，所以我们按照二叉搜索树的方式去找节点p，如果节点比p大，那就保留它(因为之后中序遍历会碰到它，是p的后继之一)并且往左走；如果节点比p小或者就是p，那就无视并往右走(后继一定在它右边)。复杂度$O(\log n)$

[01]-LC: 78. subsets

位运算：集合中某元素存在或不存在有两种状态，这些状态的组合构成了集合的所有子集。将某元素的存在和不存在表示为 1 和 0，则从 0 循环到2^n-1，保留位数为 1 在数组中对应的元素，即可得到所有子集。复杂度$O(n*2^n)$
一行位运算：一行代码简化流程。复杂度$O(n*2^n)$
数学：另一个得到子集的方式是递增，对于 n 个元素集合，如果已知前i个元素集合的子集ans，则前i+1个元素的子集只用考虑前面的子集带上第i+1个元素或者不带这两种情况。复杂度$O(n*2^n)$

[00]-LC: 229. majority-element-ii^microsoft

哈希：记录每个数出现的次数后返回最长的，复杂度$O(n)$
摩尔投票算法：和 LC: 169 思路类似，重点在于抵消。这次是多方混战，要留下出现次数大于n//3的数。考虑有 AB 两个阵营以及其他阵营的人，维护两个阵营的人数，遍历数组，如果来者是 A/B 阵营的人，其阵营人数+1；如果两个阵营都不是，则 3 方混战，AB 阵营和该来者各减员 1 人(抵消)。如果任意阵营的人人数降低到 0，则下个来者直接占领该阵营。最后留在 A/B 阵营的人即为可能的答案，最后需要重新遍历这两个数的总次数，以确保出现次数大于要求。复杂度$O(n)$，空间占用为$O(1)$

2-19

今天和女朋友打了一天游戏，许久才调整好了状态学习了一会儿。总结至此已是 2 点半了，还没做每天的 mock，明天一定要补起来(直接 qmo=quad mock)，先提前把部分明天要总结的题写上来。晚上和好友们交流下做题心得，终于踏出了投简历的第一步，查查各种公司。希望暑假能找到实习呜呜。

[00]-LC: 169. majority-element

哈希：记录每个数出现的次数并返回最长的，复杂度$O(n)$
摩尔投票算法：题目中众数的定义指出现次数超过n//2的元素。摩尔投票的思路重在抵消，想像当前有个队伍占领了据点ans，当前有cnt人，其他队伍也想占领这个据点。遍历时如果来者是这个队伍的人，则cnt+1，反之则双方交火 b 并抵消，cnt-1。如果据点里没人了，则下一个来的人占领据点。摩尔投票法的优点是在这种特殊情况下空间复杂度仅为$O(1)$，时间复杂度$O(n)$

[00]-LC: 136. single-number

哈希：直接遍历统计次数为 1 的即可，复杂度$O(n)$
位运算：异或满足交换律，因为其他数都重复了两次，所以将数组的所有数都异或在一起会把相同的数消除，剩下的就是答案，优点是空间复杂度为$O(1)$。复杂度$O(n)$

;[01]-LC: 260. single-number-iii

哈希：直接遍历统计次数为 1 的即可，复杂度$O(n)$
位运算：数组中仅出现 1 次的数有两个，所以全部异或在一起得到的是这两个数异或的结果，问题集中在如何把这两个数分开：充分利用异或的性质：相异为 1。考虑该结果为 1 的位$x$，则原先两个数的第$x$位一定不同。依据这一点可以把数组分为两部分：第$x$位为 1 和为 0 的数。可以使用xor^=-xor从而快速求出第 1 个为 1 的位。分开对这两部分进行累计异或就能得到这两个数，这样可以让空间复杂度降低至$O(1)$。时间复杂度$O(n)$

2-18

[00]-LC: 832. flipping-an-image^microsoft

朴素：直接循环即可。学习了nums[~i]的用法，取反比直接算负数好用。复杂度$O(n^2)$

[00]-LC: 872. leaf-similar-trees^microsoft

DFS：直接深搜返回叶子节点并保存即可。复杂度$O(m+n)$

[01]-LC: 932. beautiful-array

分治法+数学：题目的难点在于线性变化与奇偶组合。
- 奇偶组合：题目给出的条件$2*nums[k]!=nums[i]+nums[j](i比较难应用。对于自然数而言，一定有\(奇+偶=奇$，套用到上面的公式，考虑一个 beautiful array 全都是奇数，另一个 beautiful array 全是偶数，则两者拼接起来也必然满足条件。
- 线性变化：一个 beautiful array 通过线性变化后仍然是 beautiful array(相当于是条件的不等号两边同时乘系数 k 再加常数 b，仍然保持不等。
所以我们可以通过线性变化在已知的 beautiful array 构造全为奇数/偶数的 beautiful array。例如[1,3,2]，全部乘 2 就全为偶数，全部乘 2 后-1 就全为奇数，两者拼接仍为 beautiful array。具体的，[1]可以视作递归的 base case，把n分为n//2和n-n//2两部分，分别递归调用，把调用的结果分别进行线性变化使其分别全为奇数和偶数，最后拼在一起。递归树深度为$O(\log n)$，每次操作要执行 n 次，复杂度$O(n\log n)$。
递推分治+数学：改进上面的思路。答案可以从 base case 直接迭代出来，即由 base case [1]可以进行 x 次线性变化的扩张得到长度为$2^x$的 beautiful array。最后返回的答案剔除大于 n 的结果即可。复杂度$O(n\log n)$

2-17

[00]-LC: 345. reverse-vowels-of-a-string^facebook

双指针：题目要求让字符串中所有元音交换位置，要注意大小写两种情况。直接双指针从左往右和从右往左搜索，分别找到元音就交换。复杂度$O(n)$

[00]-LC: 515. find-largest-value-in-each-tree-row^facebook

BFS：树的层序遍历，用队列即可。while中套for，以保证目前只出列这一层的节点。复杂度$O(n)$

[00]-LC: 157. read-n-characters-given-read4^facebook

OOP 简单题，能 bug free 肯定分高，但是我漏了一种情况，而且这个题读起来特别麻烦，写倒是很快。

朴素：读文件需要考虑两种情况，n 大于文件和小于文件，大于时只能读到文件就结束，小于时不能把文件全读完。循环调用read4，返回值保存为cnt，每次取n和cnt的最小值，只往buf里赋这个长度的值。

[00]-LC: 303. range-sum-query-immutable^facebook

OOP 水题，给定数组，基本是要求在$O(1)$时间找到任意一个子数组的和，前缀和没得跑

前缀和：在初始前缀和数组pres最前面加一个 0，保证在算子数组时不会越界。返回pres[right+1]-pres[left]即可。复杂度$O(1)$

[02]-LC: 23. merge-k-sorted-lists

这个题算做好几遍了，主要的做法就是小顶堆和归并两个思路，设 lists 长度为$n$，单个链表最长为$k$，则复杂度为$O(kn\log n)$

归并：和归并排序类似，把链表两两合并，最后合并为整体。两两合并的递归过程，最底层是$\frac{n}{2}*k$，即$n/2$个长度为 k 的链表合并，一般化公式则是第i层的合并是$\frac{n}{2i}$个长度为$i*k$的链表合并，递归树一共有$\log n$层，总复杂度$O(kn\log n)$
小顶堆：维护一个长度为 n 的小顶堆，入堆lists的每个头结点。每次出堆最小的结点，并把该节点的后续入堆，堆大小为$O(n)$，有$nk$个节点要进行入堆出堆操作，所以复杂度为$kn\log n$。

2-16

[00]-LC: 904. fruit-into-baskets

滑动窗口：维护一个哈希表 basket 表示滑窗内的不同类水果的数量，右指针滑动，窗口内有两种以上的水果时，左指针右滑，直到窗口内的水果只有 1 种。窗口内水果种类的判断需要额外维护一个变量。复杂度$O(n)$

[01]-LC: 95. unique-binary-search-trees-ii

DFS(回溯)：和 LC: 96 区别在于要把所有情况的树都打出来。只能回溯并且保存路径。这里递归函数的入参用 py 的列表切片特别方便。复杂度$O(n!)$

[01]-LC: 96. unique-binary-search-trees

DFS 记忆化：深搜最好想，考虑递归函数入参为x，x小于等于 1 就直接返回 1，其它情况循环i从 1 到n，递归调用dfs(i-1)*dfs(x-i)，累加并返回。要注意需要记忆化递归，否则铁定 TLE，复杂度$O(n)$
DP：设dp[i]为所求答案，则$dp[i]=\sum_{0\leq j。思路是类似的，复杂度\(O(n)$
数学法：这个东西叫卡塔兰数，递推公式为：$C_{n+1}=\sum_{i=0}^nC_iC_{n-i}$，也可以表示为$C_{n+1}=\frac{2(2n+1)}{n+2}C_n$。前者和 dp 的状态转移方程一致。复杂度$O(n)$

2-15

元宵快乐！

[00]-LC: 121. best-time-to-buy-and-sell-stock^facebook

朴素循环：题目要求低买高卖的最大收益，维护两个变量ans, min_price，遍历时维护min_price保持最小，并计算当前 price 和min_price的差，取最大值。遍历完成后 ans 即为答案。复杂度$O(n)$

[00]-LC: 238. product-of-array-except-self^facebook

题目限制了不允许使用除法，所以需要前缀积和后缀积来获得我们需要的结果。

前缀积+后缀积：分别从前往后以及从后往前遍历数组获得前缀积pre与后缀积post，则ans[i]=pre[i-1]*post[i+1]。(越界情况处理为 1)，复杂度$O(n)$
前后缀积改进：把前缀积向右移一位，后缀积向左移一位，对齐，空白部分补 1，就能使答案变成ans[i]=pre[i]*post[i]，且不需要考虑越界情况。复杂度$O(n)$
前缀积：题目希望空间复杂度为$O(1)$(不考虑返回的 O(n)空间)，可以把前缀积存放在ans中，反向遍历ans，维护一个变量来存放后缀积并由此得到答案。复杂度$O(n)$

[01]-LC: 881. boats-to-save-people

贪心+双指针：每艘船最多载两个人，为了让总船数尽量少，应该让每艘船尽量载满。对people降序排序，两个指针i, j指向两端，即最胖和最瘦，对于最胖的人而言，如果所有人里最瘦(即people[j]和people[i]组合还是超出了 limit，people[i]单独乘船，i右移，否则就带上people[j]乘船，i, j同时向内移，直到指针相遇。复杂度$O(n)$

2-14

[00]-LC: 71. simplify-path^facebook

栈：水题，先把path按照/split，设一个栈ans，如果有'.'或者''直接略过，如果有..，那出栈一格，否则直接压栈，最后拼接得到答案'/'+'/'.joins(ans)。复杂度$O(n)$

[00]-LC: 270. closest-binary-search-tree-value^facebook

朴素法：二叉树求最临近的节点，直接按二叉搜索的顺序从上到下搜索，过程中记录val以及其与target的距离，最后返回结果即可。H 为 BST 的深度，复杂度$O(H)$

[03]-LC: 435. non-overlapping-intervals

这个题太有意思了，今天再回顾一下他作为 LIS 的 dp 做法和二分做法(LIS 候选人)，以及他最好用的贪心法。首先记得反向思考，本质是取尽可能长的不重叠区间再拿总长度去减。

类 LIS 的 DP：状态转移方程：$123$，复杂度$O(n^2)$，py 跑直接 TLE，看 LC 题解意思是别的语言可能不会 TLE
类 LIS 的贪心+二分优化：也是 LC:300 的做法，设置ans数组表示LIS 候选人，ans[i]指长度为i的 LIS 末尾的元素，复杂度$O(n\log n)$
区间贪心法：不考虑排序的情况只需要一次遍历即可。将所有区间按右界排序，维护一个cur表示当前最长不重叠区间的右区间，遍历时用intervals[i]的start去和cur比较，如果start>=cur，则intervals[i]对区间长度有贡献，计数+1，cur 改为当前intervals[i]的end，复杂度$O(n\log n)$
- 右界排序的理解：这个题目的区间贪心，贪的是使区间数最多，按照右界排序，可以让右界小的先被选中，保证剩下的空间尽可能的大。类似的还有 LC: 452，贪的是尽量让区间重叠，左界和右界排序可以按顺序找到和这个区间重叠的所有区间。只能左界排序的也可以参考 LC: 253 去对比理解。

[03]-LC: 253. meeting-rooms-ii

这个题目需要和 LC: 435 这类右界排序的区间贪心题一起思考，才能更清晰的体会到什么时候用哪个界来排序。要注意这次题目考察的是需要多少个房间，即要求把所有区间都安排好(不能舍弃或任意重叠，而是要尽可能少重叠)。

区间贪心法+堆：不考虑排序的情况下只要一次遍历即可。将所有区间按左界排序，维护一个堆rooms来表示当前每个房间最早的可用时间(也就是区间的 end)，因为贪心要每次要在多个房间里选最早时间，也就是动态极值，条件反射想到堆。遍历区间，用start, end表示当前遍历的区间的左右界，如果start比当前的堆顶的时间更早，那么开个新的房间(push 入堆)，反之则把堆顶的时间更新为当前区间的end。最后返回堆的长度即可。复杂度$O(n\log n)$
- 左界排序的理解：这个题目的区间贪心，可以让区间重叠，但是要使重叠尽可能的少，所以转换一下也就是尽可能让区间之间不要有间隙。考虑已经安排好了的房间，它的结束时间是固定的，为了让区间尽可能不要有间隙，在选择下一个区间时应该要先选择开始时间早的(start 小的)区间，所以才要按左界排序。可以类比 LC: 435 的右界排序思路以及 LC: 452 的左右界排序均可思路。

2-13

[00]-LC: 1360. number-of-days-between-two-dates^facebook

恶心人纯考编码的简单题，如果平常没练到，至少比普通中等题浪费一倍时间。

built-in：面试时很容易忘记某些不常用的 api，比如这里的datetime.date.fromisoformat()，直接一行搞定。复杂度$O(1)$
朴素：分别计算date1和date2从公元 0 年开始经历了多久。需要注意闰年规则，4 年一润，100 年不润，400 年又润。本质是计算这一年已经经历的日子(为 days+1 月到上个月的所有日子)，再加上从 0 年到上一年所有日子。先按一年 365 考虑，然后再加上 4 年一闰的日子，减去 100 年不润的日子，再加 400 年又润的日子。复杂度$O(1)$

[00]-LC: 1428. leftmost-column-with-at-least-a-one^facebook

题目很有意思，第一眼会想每行都二分做一次，再多思考一下还可以优化。

最左二分+剪枝：每一行都用二分找到最左的 1，保存最小的结果即可，否则返回 1。由于求的是所有行里最左的 1，所以每一行在二分的时候可以把右界直接确定为当前ans因为超出 ans 的不用考虑。复杂度$O(m*\log n)$
贪心法：上面思路的剪枝延伸，设当前值的坐标为(i,j)，那么如果当前值是 1，左侧是有可能有 0 的，j-=1，如果当前值为 0，则下面是有可能有 1 的，i+=1，最后超出边界时，返回j+1即可。

[01]-LC: 455. assign-cookies

贪心法：两个数组分别排序，然后同时遍历，如果s[i]>=g[j]，即满足了条件，则计数并使i和j分别前移，否则只移i，直到能满足当前g[j]。i和j任一指针超出数组返回计数值。复杂度$O(m+n)$

2-12

;[01]-LC: 2008. maximum-earnings-from-taxi

这个动规有点意思，专门给了一个单独的参数n来提示我们$O(n)$的做法。

类 LIS 思路 DP：先给rides按 end 排序，然后用类似 LIS 的双重循环去看$dp[i]$有没有可能由前面的某个点更新而得(且更大)，定义dp[i]为从 0 到i的可能的最大获利情况。$dp[i]=max_{0\leq j，非常像 LIS 的思路。设len(rides)为 m，复杂度\(O(m^2)$，在 LC 上超时。
类 LIS 思路 DP+最右二分法：考虑到上面在二重循环时，dp[j]是有序的，而且如果某个dp[j]不满足条件，则大于它的一定都不满足条件(因为是按 end 排序的)。所以二重循环的部分可以用最右二分快速找到第一个满足条件且在最右边的值。复杂度$O(m\log m)$
单循环 DP：如果合理利用上题目给出的参数n以及rides提供的 start 和 end，算法可以在一次遍历rides后找到答案。上面两个方案里 start 和 end 都只提供了金额的信息，但它本身可以作为 dp 的下标来找到"上一次如果没载这个乘客的最大收益"，即dp[start]。所以我们以长度n构建dp数组，定义为"从 0 走到i时的最大收益"，遍历rides，设start,end,tip表示当前乘客的几个参数，则有状态转移方程$dp[i]=dp[i-1] (i，以及\(dp[i]=max(dp[i],end-start+tip+dp[start]) (i=end)$。复杂度$O(m\log m+m)$

[00]-LC: 364. nested-list-weight-sum-ii^facebook

题目读起来有点麻烦，但实质就是 DFS，搜的同时维护数组的值，以及嵌套的深度，最后算答案。

DFS：在搜索过程中用两个数记录当前元素的值以及所在 list 的深度，最后根据要求计算结果即可。复杂度$O(n)$
DFS+数学：不需要维护两个数组记录结果。因为需要的结果$\sum (nums[i]*(max\_depth-depths[i]))$可以拆开变成$\sum (nums[i]*max\_depth)-\sum (nums[i]*depths[i]))$，我们只要在 dfs 的过程中维护 list 的不带权和，带权和以及最大深度就能解决问题。空间复杂度优化到$O(1)$。时间复杂度还是$O(n)$

[00]-LC: 938. range-sum-of-bst^facebook

这个题在 mock 的时候耽误了点时间，思考出剪枝并写出正确结果不难，但那会儿有点卡壳就应该直接先写出能 AC 的方法，再慢慢优化。

DFS：直接深搜二叉树，条件符合的 node 就加上，复杂度$O(n)$
DFS+剪枝：DFS 的过程中，如果当前节点本身就高于 high 了，那它右边的节点就不用考虑，只返回他左边的部分；低于 low 的同理。复杂度$O(n)$

[01]-LC: 1266. minimum-time-visiting-all-points^facebook

昨天的题补一下一个好用的 python 自带 api

贪心法+built-in：改进一下，使用 python 自带的itertools.pairwise可以每次取 list 的两个元素，自动处理了边界情况，即pairwise('ABCD')-->AB BC CD。

2-11

[00]-LC: 1528. shuffle-string^facebook

这个题还可以原地更改，但是比较麻烦也没有必要。真要搞那就是类似并查集的思想，略麻烦。(可能就是考点)

朴素模拟：给定字符串和与之相等长度的数组，数组元素是下标，要把各个位上的字符重新放在数组元素表示的下标上，重新安排一个数组ans，ans[indices[i]]=s[i]即可。复杂度$O(n)$
原地修改：原地修改有点像并查集，维护两个临时变量idx和ch来保存下标和字符，从字符串任一位置启动(假设从i=0开始)，idx和ch先保存i=0状态下的下标与字符，找到下一个位置(就是 idx)，交换新位置的字符和ch，交换新位置处的下标与当前下标(也就是使indices[i]=i，防止被找到)。这个过程的循环可能会提前中断，所以外面要再套一层循环，确保每个字符都被遍历到。复杂度$O(n)$
built-in 烂活：虽然是一行，但是复杂度高达$O(n\log n)$

[00]-LC: 1266. minimum-time-visiting-all-points^facebook

贪心法：仔细理解题意就会发现它要求按照顺序穿过点，所以只要保证上一个点到当前点选择最短距离即可。而在题目的定一下这个距离就是两个点 x 坐标与 y 坐标的相对距离的最大值，复杂度$O(n)$。这个距离又叫切比雪夫距离。可以分类讨论证明，设两个点 xy 坐标的相对距离绝对值为dx,dy：
- $dx=dy$：那么直接沿着对角线走，距离就是$dx$
- $dx：先由对角线走，走到头了再沿竖直方向走，距离为\(dx+(dy-dx)=dy$
- $dx>dy$：先由对角线走，走到头了再沿水平方向走，距离为$dy+(dx-dy)=dx$

2-10

[00]-LC: 795. number-of-subarrays-with-bounded-maximum

子数组数量这个类型的题目，一般可以先单独考虑以nums[i]结尾且满足给定条件的子数组个数，而这个个数一般是可以累积的。对于单个nums[i]而言找到这样的个数复杂度为$O(n)$，但因为它可累积，故一次遍历就可以求出每个以nums[i]结尾且满足条件的子数组个数，从而在$O(n)$时间完成题目。

前缀和：设有函数atmost(k)，表示nums[i]中最大值小于等于k的子数组个数，那么答案就是atmost(right)-atmost(left-1)。对于atmost(k)可以先单独考虑以nums[i]结尾且最大值小于等于k的子数组的个数已知，同时nums[i+1]也小于等于k，则以nums[i+1]结尾且满足条件的子数组就是以nums[i]为结尾的个数+1。以状态转移方程来表示就是$dp[i]=dp[i-1]+1$，复杂度$O(n)$。

[01]-LC: 467. unique-substrings-in-wraparound-string

前缀和：如果只考虑以p[i]结尾且满足条件的子串，显然$O(n)$时间就能找到，从 0 遍历到i，满足条件就累加，不满足就置 1。而这一结果是可以随着遍历累积的。即满足条件时存在状态转移方程$dp[i]=dp[i-1]+1$，不满足条件则$dp[i]=1$，直接用一个变量以前缀和的形式表示即可。剩下的部分就是保证答案唯一，需要哈希表来存放以p[i]结尾的子串的最大长度。复杂度$O(n)$

[01]-LC: 322. coin-change

滚动 DP：常规背包问题，求和为amount的最小硬币个数，可用滚动 DP 完成。硬币数无限，故滚动 DP 直接从前往后遍历即可。具体情况和 LC: 518 完全一致，只是求和改成了求最大值。状态转移方程也非常类似，$dp[j]=max(dp[j-coins[i]]+1,dp[j])$，复杂度$O(n*amount)$
状态压缩+滚动 DP：另类解法，复杂度很低$O(n*amount/min(coins))$，LC 上用例的时间而言要快 20 倍。动规问题转换成了在已经给定硬币数量为i的情况下，是否存在解使其和为j。则有状态转移方程\(dp[i][j]=0|dp[i-1][j-coins[k]],(0\leq k。改为滚动 DP+状态压缩的方程则为：\(dp=dp|dp>>(j-coins[k]) ,(0\leq k。从i=1开始找，只要 dp 的最后一位为 1 就return i。具体可以看我的题解：Python 52ms 状态压缩+动规超过最快方法将近一倍时间

[01]-LC: 518. coin-change-2

滚动 DP：常规背包问题，求和为amount的不同硬币的组合数，用滚动 DP 完成即可。这里硬币数是无限的，所以直接从前往后遍历即可。具体的，把 amount 作为一个维度，设dp[i][j]为从 0 到i的硬币中任取若干个，使其和为j的最大数量。考虑取用coins[i]硬币和不取用的情况，不取用则$dp[i][j]=dp[i-1][j]$，取用则有$dp[i][j]=dp[i-1][j-coins[i]]+1$，要求最大数量，所以把二者相加即可。而次态仅与当前态相关，所以应用滚动数组的方式，状态方程为$dp[j]=dp[j-coins[i]]+1+dp[j]$，复杂度$O(n*amount)$。补充一点，可以提前给coins按从大到小排序，减少 dp 的更新。

[01]-LC: 2. add-two-numbers

朴素法：先算成整数，再相加，再构造链表，复杂度$O(m+n)$
朴素法：链表头表示最低位，所以直接模拟整数相加并进位即可，复杂度$O(m+n)$

[01]-LC: 13. roman-to-integer

朴素法：遍历字符串，扫描，特殊情况需要向前试探，复杂度$O(n)$，边界情况多，不容易一遍 bug free。
提前记忆法：因为特殊情况就 6 种，所以可以用哈希表还记住特殊情况，遍历时直接试探长度为 2 的字符串，在哈希里就直接使用对应的值并挪两格，不在就只取长度为 1 并挪 1 格。复杂度$O(n)$，思路清晰，容易一遍过。

[01]-LC: 494. target-sum

题目最巧的地方是数学转化，在一堆正整数里取任意数为正，剩下的为负，使和为target。设正数和为pos，负数和为neg，那么有$pos+neg=sum(nums),\ pos-neg=target$，故$pos=(sum(nums)+target)/2$。题目转换成了在数组里取子序列，使和为 pos，求子序列的个数，题目就成了经典的背包问题。

DP：构造一个二维动规数组，从 0 到 pos 是其中一个维度，则dp[i][j]表示从nums[0]到nums[i]任取若干数后，其和为j的个数。状态转移方程则有：$dp[i][j]=dp[i-1][j]+dp[i-1][j-nums[i]]$，即当前状态可以选择取 nums[i]或者不取，不取就直接继承上一个状态的结果，取就加上上一状态中和为j-nums[i]的情况(即取了nums[i]结果正好为j的情况)，因为要算个数，两种情况相加即为结果。复杂度$O(n*pos)$
滚动 DP：上面方法的改进，因为 DP 仅与上一状态i-1有关，所以只需要一个一维数组滚动更新即可。复杂度$O(n*pos)$

2-9

[00]-LC: 21. merge-two-sorted-lists

朴素法：是 23 的青春版/前提，就是每次取最小的节点放到 ans 里，为了避免额外的 edge 可以考虑让 ans 有一个头结点，最后返回的时候再去掉头。复杂度$O(m+n)$

[00]-LC: 325. maximum-size-subarray-sum-equals-k

这个题乍一看特别像滑动窗口，非常像 BS: 843 的题。都是在给定的数组中找到一个子数组，使其和为k，求这个子数组最长的长度。但实际上这题不能套用滑窗的思路，因为滑窗需要数组里的元素均为正数(则滑窗和会保持递增)。而题目的数据范围明示了只能接受$O(n)$复杂度。

前缀和+哈希：前缀和可以在 O(1)时间获得任意子串的和，设前缀和是pre，遍历数组nums，对于nums[i]，我们就只需要快速找到k-pre[i]的下标即可(因为前缀和中$pre[i]-pre[j]=k$)。对于这一要求，用哈希的 key 保存pre[i]，value 保存下标即可在$O(1)$时间找到哈希表中 key 为k-pre[i]的元素。考虑到哈希的 key 并不唯一，而题目要求我们取最大长度，所以哈希表应当只保留最先存入的记录，即只在pre[i]不在哈希表中时存入。相反如果题目要求 minimum-size 那就是每次都要更新哈希表。复杂度$O(n)$，具体操作时pre数组可以和哈希在同一循环中更新。

[02]-BS: 843. Number-of-Operations-to-Decrement-Target-to-Zero

前缀和+哈希：这个题除了滑窗以外的另解，思路同上，求前缀和，用哈希存前缀和和下标，前缀和相同不更新哈希表，复杂度$O(n)$

;[01]-LC: 416. partition-equal-subset-sum

背包问题的基本思路都忘了，太久没做 dp 了。回顾一波

背包问题的特征是在原有数组上增加一个维度target，即背包的容量，容量从 0 到 target，考虑的是对于一个新的元素，我们是否要把它加入背包。dp[i][j]表示的是对于容量为j的容量，把 0 到i的物品中的部分装进去能得到的最大价值，判断的依据是dp[i-1][target-nums[i]]+nums[i]是否比dp[i-1][j]更大。

回到这个题，先算target，即nums的和除 2，剩下的就和背包问题一样了，背包问题是价值最大化，这个只要能等于target就行，所以 dp 里存的布尔值，所以这题还可以用状态压缩加快 dp

原始 DP：dp[i][j]表示对于target为j的情况下，任取 0 到i的元素，其和是否为j，在这个定义下可以想到，我可以选用nums[i]或不选，不选那就直接沿用dp[i-1][j]的结果，选那就可以用dp[i-1][j-nums[i]]的结果(局部最优解，表示背包容量比现在少 nums[i]的情况下能否满足条件，能那么选用了nums[i]也能)。状态转移方程：$dp[i][j]=dp[i-1][j]\ |\ dp[i-1][j-nums[i]]$，复杂度$O(m*n)$，n 为数组长度，m 为 target。
滚动 DP：因为 DP 更新的过程中仅与上一状态(i-1)相关，所以可以让一维数组滚动更新，而且要注意需要从右往左更新。(后面值的更新依赖前面的值)，状态转移方程$dp[j]=dp[j]\ |\ dp[j-nums[i]]$，复杂度$O(m*n)$
状态压缩 DP+位运算：因为 DP 中的元素均为 boolean，所以可以用 bitset 来替代。同时分析滚动 DP 的状态转移方程$dp[j]=dp[j]\ |\ dp[j-nums[i]]$分为两个部分，j-nums[i]就相当于是对于nums[i]把整个 dp 的 bitset 右移了nums[i]位，状态转移方程变成了$dp\ |\ =dp>>nums[i]$。而这可以将原来计算m次变成一次，复杂度$O(n)$

2-8

[00]-LC: 977. Squares of a Sorted Array^facebook

暴力法：直接平方后排序，复杂度$O(n\log n)$
双指针：找到 0 的位置，两个指针分别向左向右出发扫描，每次选绝对值最小的平方后放入答案，问题是边界情况处理有点麻烦，复杂度$O(n)$
双指针改进：反向更新数组，让双指针从nums两端出发，每次选最大的放在数组末尾。复杂度$O(n)$

[00]-LC: 791. custom-sort-string^facebook

这个题有点妙，我以为考察的是手写排序，没想到考察的是哈希

哈希+排序：题目给定了自定的顺序，所以用哈希保存给定的顺序(value 存下标)，重写一个排序(我写的归并)，排序比较时用哈希表，复杂度$O(n\log n)$
哈希+built-in 排序：同上，可以用sorted(s，key=lambda x:d[x])直接指定排序的key为哈希表的值。复杂度$O(n\log n)$
哈希：因为 order 的顺序本来就给定了，直接用哈希统计字符串s的个数，遍历 order 的时候直接根据哈希统计的信息构造答案即可。记得遍历完了 order 还要遍历不在 order 里的字符，复杂度$O(n)$

;[01]-LC: 464. can-i-win

旧题新做，虽然这次很快找到了思路，但是 debug 的路上出了一点差错，猜想正确但是没改过来。不然至少能用@cache给解了。基本算做出来了吧)。

这个题本质就是要去模拟，题目中所表达的"Assume both players play optimally."其实意思就是双方两个人都会把所有情况探个遍，换句话说就是我一个人会把我的所有可能和对方的所有可能全部探索一遍，以找到可能的解。所以模拟就直接 DFS 了。

DFS：用visited数组表示当前数是否被取用，DFS 递归需要传递剩余的 desiredTotal 够不够减，设为target，遍历试探所有没有被访问的数，如果取的这个数直接大于target，说明这次试探成功，返回 True，否则就递归调用到下一层，传入target-num。应当注意visited数组如果当作全局变量则需要像八皇后的题目，在递归调用结束后及时修改为未访问，或者作为递归参数每次 copy 后传入，否则会卡在用例 40/57(10, 40)。复杂度$O(n!)$
DFS+记忆化+偷懒cache：上面的思路是正确的，只是回溯会进行多次重复计算，我们可以用@cache偷懒，让修饰器帮我们完成记忆化。复杂度$O(2^n)$
- 注意此时 DFS 必须把visited当作参数传入，因为@cache 只能记忆入参和结果。
- visited如果仍然是数组则无法完成@cache的 hash 化(它是通过 dict 存入参的)，故可以用状态压缩的位集或者tuple来实现(后者内存爆炸，高达 200MB)
DFS+记忆化(单一参数)：偷懒法的问题在于不得不使用target和visited两个参数来记忆。实际上，对于任意一个状态visited，它所对应的target一定是固定值。visited中，二进制下1的位数表示当前已经取走的 num，所以对于任意visited，它有且仅有一个target对应，所以我们只使用visited来记忆化即可。构建一个数组dp，长度为$2^n$，初始化为 None，每次确定答案时，存到dp数组，递归时先访问dp，有答案就不用继续 dfs 了。复杂度$O(2^n)$

2-7

今天的每日 emo 差点没做完，太菜了，没想出第二个题(496)的最优解。最后无奈用暴力法过了。

[00]-LC: 1213. intersection-of-three-sorted-arrays^facebook

哈希：直接三个数组一扫，频率为 3 的放到答案里返回。复杂度$O(n)$
三指针：和双指针类似，三个指针的元素都相等那就把这个数放到答案里，所有指针右移，不相等就选数最小的指针右移，复杂度$O(n)$

[00]-LC: 496. next-greater-element-i^facebook

个人觉得这个题要想出$O(m+n)$的复杂度才算过关，需要用上单调栈，这个专题我一直没怎么接触过，太菜。其实思考的时候想到了维护一个上升序列去操作，但是没想深。题目有三个要点：在nums2中快速找到nums1的元素(哈希扫nums2)；对于nums2的元素快速找到它的 next greater 元素(败在这里)；保存它(哈希表就行)

暴力哈希：把nums2哈希扫一遍，key 存值，value 存下标。遍历nums1的过程中，通过哈希从 value 下标处出发向右找第一个大于它的元素，返回，相当于就是暴力法的剪枝版。复杂度$O(mn)$
单调栈+哈希：题目需要对nums2的每一个数快速找到其右侧第一个大于的数，可以对nums2从右往左遍历，这样扫过的数才是在下一个数的右侧。对于扫过的数，维护一个单调栈，保证栈内单调递减。每扫一个数nums[i]就和单调栈栈顶对比，如果比栈顶小，很好，nums[i]右侧第一个大于的数就是栈顶，用哈希存起来。如果比栈顶大，那就出栈，直到比栈顶小或者栈为空。复杂度$O(n)$
- 一点个人理解：单调栈可以理解为是 next greater 元素的候选人，因为是 LIFO，所以栈顶是最有可能的候选人。因为是单调栈，所以加入新候选人时只会排出比它小的元素，比新候选人还大的仍然保留了。单调栈不能保证单次搜索的复杂度为$O(1)$，但对于整个数组的遍历，每个元素的均摊复杂度为$O(1)$(每个元素最多入栈和出栈各一次)

[02]-LC: 688. knight-probability-in-chessboard

现在懒得写记忆化了，直接加@cache解决问题，面试可能需要自己补充，平时练习就不写了。

DFS+记忆化：直接朴素递归模拟并记忆化即可，每次跳的时候试探可跳的 8 个位置，形参有坐标和剩余步数。不过记忆化需要三维数组，写起来略微麻烦，直接@cache处理。复杂度$O(n^2k)$
DP：其实这题是个三维数组的动规，不过因为下一状态只和当前状态有关，所以同样可以用二维的滚动更新数组替代三维数组。状态转移方程$dp[i][j][k]=\sum dp[\hat i][\hat j][k-1]\quad (\hat i,\hat j为所有可能的位置)$，最后二维数组求和即可。复杂度$O(n^2k)$

2-6

[00]-LC: 1329. sort-the-matrix-diagonally^facebook

naive 思路：把每个对角线找到(也就是-m到0到n)，提出来并排序，再放回去即可。

[01]-LC: 859. buddy-strings^facebook

今天做 Facebook 的 mock 遇到了这题，顿时心如死灰，勉强用 20 分钟做出来了，反而是另一道 medium 却很简单，10 分钟不到搞定

naive 哈希思路，复杂度$O(n)$：
- 如果长度不同则直接返回 False
- 用哈希表统计字符个数，字符个数不同则直接返回 False
- 再同时遍历两个字符串，记录相同位置不同字符的个数，超过 2 返回 False，不可能为 1，如果为 0 则检验哈希表 key 的长度是否等于 n，相等则说明每个位置的字符都各不相同，返回 False
naive 思路改进：无需哈希表
- 长度不同直接返回 False
- 同时遍历两个字符串，还是记录相同位置不同字符的个数
  - 超过 2 返回 False 或者为 1 都返回 False
  - 如果为 0 就需要判断每个字符是否都各不相同，如果是就返回 False
  - 剩下的情况就是为 2，那就需要我们能找到这两个字符的下标，判断它们是否互换位置后相等

[01]-LC: 63. unique-paths-ii

DP：这个题 edge case 比较多，初始化 dp 的时候就需要用到 dp 的转移方程，以保证遇到障碍物时的递推关系仍然正确，复杂度$O(mn)$

[02]-LC: 62. unique-paths

纯属练手多写了几个写法。以下复杂度除纯 DFS 外均为$O(mn)$

DFS：写着玩，直接超时，复杂度$O(m!n!)$
DFS+记忆化：过
DP
排列组合：math.comb

2-5

;[00]-LC: 1143. longest-common-subsequence

太菜了，二维动规都忘了七七八八了。

DP：二维动规，设dp[i][j]为text1[:i]和text2[:j]的最长公共子序列。这个定义出来了，一切就都好解决了，复杂度$O(n^2)$。考虑任一dp[i][j]：
- 若此时有text1[i]==text2[j]，那说明当前两个子串text1[:i-1]和text2[:j-1]他们再加上当前字母text1[i]/text2[j]后，正好使它们的公共子串长度加 1。也就是$dp[i][j]=dp[i-1][j-1]+1$
- 否则则是text1[i]!=text2[j]，那么可以考虑为text1[:i]在text2[:j-1]的情况下增加了一个不相干的字符text2[j]，也可以看作是text2[:j]在 text1[:i-1]的情况下增加了一个不相关的字符text1[i]，结果保持不变。两种情况显然取最大值。即$dp[i][j]=max(dp[i-1][j],dp[j-1][i])$
滚动 DP：上述改进，每个单元格的更新仅与上方，左方和左上方的单元格相关，所以可以将二维数组变成滚动的一维数组(需要保留两行，否则左上角更新会被影响)。复杂度$O(n^2)$

[02]-LC: 673. number-of-longest-increasing-subsequence

贪心+二分+前缀和：接昨天的贪心+二分思路，其复杂度高在必须要遍历一整行以获得从 a 到 b 之间的元素和，而前缀和就可以优化这个问题。还是构建LIS 候选人二维数组，同样每个元素是一个二元tuple，包含数字本身和它对应的nlis，只是这里把nlis改成了前缀和的形式，这样对于第i-1行的任意个元素的元素和都可以在 O(1)时间求得。设 m 是每一行元素的个数，所以时间复杂度为$O(n(\log n+\log m))=O(n\log n)$，具体的：
- 遍历nums，复杂度$O(n)$，对于每个nums[i]
  - 最左二分：如果它比所有元素都大，说明nums[i]对 LIS 长度有贡献，append 到末尾，否则就在已有的LIS 候选人里找到最接近但比它大的，取代附在后面(说明每行候选人都是递减的)，复杂度$O(\log n)$
  - 最右二分：对于新元素nums[i]，在通过最左二分找到自己的位置后，需要通过i-1行候选人的nlis来获取自己的nlis值，具体则是通过最右二分(需要手写，因为是递减的)，找到第一个比自己小的元素。复杂度$O(\log m)$
  - 前缀和得区间和：找到第一个比自己小的元素后，通过前缀和的特性，计算所有比自己小的元素的nlis和，复杂度$O(1)$

[01]-LC: 287. find-the-duplicate-number

快慢指针：思路要参考环形链表(即 LC142)，LC142 简单来说就是，在一个有环的链表中找到成环处的交点。而这个题给出了 n+1 个数，且数字在$[1,n]$之间，所以数字一定有重复的。把nums[i]看成节点，而它的值看作链表的后继，也就是下一个节点的下标i，就可以构成一个链表，因为一定有数字重复，所以链表必然有环。然后依照 LC142 的做法完成。复杂度$O(n)$。具体的：给出快慢指针，因为有环，二者必然相遇。再从相遇点出发，同时另一个指针从起点出发，他们相遇时就是成环处的交点。

2-4

673 永远是心中的刺，又被 673 给干翻了。写完顺便复习 300。害！

[00]-LC: 287. find-the-duplicate-number

这个题还有快慢指针法，明天再看！

naive：双重循环，TLE，复杂度$O(n^2)$
哈希：不符合题目要求，SC 要求为$O(1)$，复杂度$O(n)$
能力检测二分：这个思路没想到，因为重复的数字一定是$[1,n]$，那么对于每个数字i，去nums中找小于等于i的数字的个数，设为count(i)，显然count(i)随i有序(非递减)，且随着i的增加，一旦出现重复的数字，原本$count(i)\leq i$的关系会被打破，则可以使用二分找到这个关系打破的临界点，复杂度$O(n\log n)$。

[02]-LC: 300. longest-increasing-subsequence

DP：状态转移方程为：$dp[i]=max_{0\leq jnums[j])$，其中dp[i]为以nums[i]结尾的最长上升子序列长度，思路是，对于当前以i为结尾的子序列，只要nums[i]在之前的任意一个子序列的基础上是上升的(也就是nums[i]>nums[j])，那么dp[i]就是至少是dp[j]+1，遍历i之前的所有j并保留最大值作为dp[i]，最后返回 dp 数组的最大值即可。复杂度$O(n^2)$
贪心+二分法：贪心法的应用。为了让 LIS 尽可能长，我们希望每次 LIS 长度增加时所加上的数字尽可能的小。我们可以维护一个数组，表示每次 LIS 增长时所加上的数字的最小值，我称之为LIS 候选人。遍历时对于nums[i]，如果其大于序列中的最大值，说明它对于 LIS 的长度有贡献，直接加到末尾。否则，找到序列中最接近但大于nums[i]的数，替换。由于该序列是有序的，则需要替换时可以应用二分法。复杂度$O(n\log n)$
- LIS 候选人：设为ans，对于任意ans[i]，它是长度为i的 LIS 的末尾元素的最小值。

;[02]-LC: 673. number-of-longest-increasing-subsequence

这个题还有贪心+二分+前缀和优化大法，明天再实现！

DP：和 300 类似，只是题目变成了数 LIS 的个数。可以用相同的方法求 LIS 的长度，dp 数组设为llis，则llis[i]表示以nums[i]结尾的 LIS 的长度。同时基于llis维护一个nlis数组表示以nums[i]结尾的 LIS 的个数¹。则显然有这样的状态转移方程$nlis[i]=_{0jnums[j]) $。即`nlis[i]`为其前面所有`llis[j]+1=llis[i]`的`nlis[j]`的和。也很容易理解，长度为n的LIS个数一定是长度为n-1的LIS个数的和。复杂度$O(n^2)$
贪心+二分法：LC300 思路的延续。300 中维护的LIS 候选人是一维数组，它留下的是长度为i的 LIS 末尾元素的最小值，舍弃了其他结果，而 673 算的是 lis 的个数，所以我们维护一个二维的LIS 候选人，它会保留所有历史信息，同时它是有序的，此外它还要额外记录一个信息：该元素为结尾的 LIS 的个数，也就是 DP 思路中的nlis，其推导也和 DP 一样，通过对长度为i-1的行中小于该元素的nlis求和即可。所以这个 LIS 候选人是个二维二元的tuple，它其实就是原先 dp 方案的浓缩，区别在于它是有序的，所以可以通过二分法来快速定位。复杂度$O(n(\log n+\log m+m))$，m 某一长度的 LIS 的个数。具体的，遍历nums 的过程中，对于nums[i]
- 如果它比所有 LIS 候选人的最小值都大，那它对 LIS 的长度增加有贡献，另起一行，统计nlis
- 否则就二分查找，找到离它最近但大于它的那一行，加入该行，统计nlis
返回最后一行的nlis之和。

2-3

91 天算法的每日一题已经回到了我去年 11 月份刚开始刷题的进度，之后每天都大量出现做过的题。争取每个 dp 的题都用记忆化写一遍，加强手感。

[01]-LC: 198. house-robber

不难看出下面两个 dp 思路都能解题，但前面一种明显更有时间色彩，而后面一种则更有跳脱出时空限制，局部最优找全局最优的感觉。举例来说，如果这个题nums[i]可以为负，那么第一个 dp 方程就有问题。它是必然会取nums[i]的。即我们第一种状态转移方程我们是默认了当前打劫会使结果增加的，这就是没有跳出时空限制(说法有点怪)

DP：按照$dp[i]=max(dp[i-3],dp[i-2])+nums[i]$的思路，dp[i]表示从 0 开始到当前房子i且i必被打劫的情况下算最优解，复杂度$O(n)$
DFS：回溯，TLE。就是想写着玩
DFS+记忆化：上面的 dfs 改进一下就有了，复杂度$O(n)$
DP：按照$dp[i]=max(dp[i-1],dp[i-2]+nums[i])$的思路，即从 0 开始到当前房子i的情况，当前房子i不一定打劫的情况，复杂度$O(n)$
DP：上述 dp 方程只和前两个数有关，故可用两个变量滚动替代 dp 数组，将空间复杂度优化至$O(1)$，复杂度$O(n)$

[00]-LC: 213. house-robber-ii

DP：和上面一样的动规思路，区别是首尾相连，所以要进行两次 dp，两次的边界分别只取左边界和只取右边界。复杂度$O(n)$
DP：改进空间复杂度，用两个变量滚动取代 dp 数组。复杂度$O(n)$

;[00]-LC: 337. house-robber-iii

这个题目将 DFS 和 DP 结合起来非常妙。传统 DP 都是在线性结构上构造的，上一状态和当前状态往往是数组左右的关系，而树状结构下，上一状态和当前状态变成了父节点和子节点的关系，更考验如何构造状态转移方程。

DP+DFS：树状 DP，每个节点是否选择要看它的子节点和父节点情况。但 DP 的要素之一是要有顺序性，只能由已知状态推未知状态，显然会想到从树的最底端往根推。问题在于当前节点是否要被选择依赖其父节点是否被选择，也就是当前状态的真实值依赖于下一状态，显然有悖 dp 的顺序性。这里只能把选择当前节点和不选择当前节点的两种状态的局部最优都给出，以供下一状态决策。

具体的：给每个节点设两个 dp 值：$dp[node]=(x,y)$，表示劫到节点node时的收益情况，这里的x y是分类讨论的不同情况，供父节点作决策。x表示劫这个节点的情况下的最大收益，y表示不劫这个节点的情况下最大收益。则对于 node 而言有：
- $x=node.val+dp[node.left][1]+dp[node.right][1]$，劫当前节点，那么它的两个子节点就都不能劫，所以要加上其两个子节点的 y 值
- $y=max(dp[node.left])+max(dp[node.right])$，不劫当前节点，那么它的两个子节点就可以任意劫取或不劫取，直接取最大值即可。
现在对于父节点而言，x和y都只和子节点有关，成功构造了 dp 状态转移，后序遍历即可。

2-2

[00]-LC: 167. two-sum-ii-input-array-is-sorted

哈希法：用 dict 存已扫描的 numbers，每扫一个就去 dict 里查是否存在满足条件的情况，复杂度$O(n)$
二分法：遍历 numbers，每次用二分法查是否存在满足条件的情况，复杂度$O(n\log n)$
双指针法：左右两个指针向中间扫，和大于target就右指针左移，小于target就左指针右移，复杂度$O(n)$

[01]-LC: 746. min-cost-climbing-stairs

DFS：回溯大法，TLE
DFS+记忆化：好用，本质和动规一样。复杂度$O(n)$
动规：过！复杂度$O(n)$

2-1

今天多做了俩水题，芜湖。大年初一新年好！

[00]-LC: 349. intersection-of-two-arrays

集合：直接 set 就能搞定。复杂度$O(m+n)$
二分法：排序nums2，遍历nums1，遍历时二分在nums2中找是否存在答案。复杂度$O((m+n)\log n)$

[00]-LC: 350. intersection-of-two-arrays-ii

哈希：直接哈希即可。复杂度$O(m+n)$

[01]-LC: 199. binary-tree-right-side-view

BFS：层序遍历，保存每一层最后一个节点即可。复杂度$O(n)$

[00]-BS: 248. Top-View-of-a-Tree

BFS+哈希：层序遍历树，遍历时标记节点的下标并存到哈希表里，再把哈希表按 key 顺序返回即可。复杂度$O(n)$
BFS+双端队列：上述改进，层序遍历树并标记下标，维护两个变量表示ans的左右界，下标超过左右界时在其左右新增元素即可。复杂度$O(n)$

1-31

;[00]-BS: 694. Shortest-Cycle-Containing-Target-Node

题目要求某个起点的最小环路长度，直接使用 BFS 搜索就能满足最小这个条件。

DFS(回溯)：从起点出发，DFS 搜索，复杂度$O(v!)$，超时。
BFS：以入度构造邻接表，从起点以 BFS 反推回起点。复杂度$O(v+e)$
BFS：上述改进，直接从起点出发，BFS 搜到起点。复杂度$O(v+e)$

1-30

[00]-LC: 1161. maximum-level-sum-of-a-binary-tree

BFS：层序遍历，正常操作，取最大值即可。复杂度$O(n)$
DFS+哈希：深搜的同时用哈希存对应层数的求和。复杂度$O(n)$

[01]-LC: 153. find-minimum-in-rotated-sorted-array

二分法：旋转前的数组最右边一定比中间大，所以二分比较 mid 和右端点，复杂度$O(\log n)$

[00]-LC: 200. number-of-islands

DFS：遍历格子，只要是 1 就深搜并且计数，然后更改标记。返回计数结果。复杂度$O(m*n)$

[00]-LC: 1162. as-far-from-land-as-possible

BFS+遍历：遍历所有格子，如果是 0 就开始 BFS，更改grid值表示访问过，BFS 时找到 1 就停下来，并将所有修改过的 grid 值还原，复杂度$O(n^4)$，实际情况会有剪枝，以 6800ms+在 LC 上通过。
BFS：找到所有的 1，同时向四周开始 BFS，直到覆盖了全图。(感觉上就像所有的点向四周发射一圈波，所有波产生干涉的时候就是结果)。复杂度$O(n^2)$。

1-29

[00]-LC: 744. find-smallest-letter-greater-than-target

二分法：题目本质就是最右二分，所以手撕二分法的判断条件是>=。右边界需要为 n，越界说明 target 比所有都大，直接返回letters[0]。复杂度$O(\log n)$
built-in：思想同上，直接bisect_right，复杂度$O(\log n)$

[00]-LC: 695. max-area-of-island

DFS：每个格子试一遍，如果是 1 那就 dfs 搜索相邻位置，每搜一个就把这个格子置 0 表示 visited。复杂度$O(m*n)$

[01]-LC: 1423. maximum-points-you-can-obtain-from-cards

和BS: 843. Number-of-Operations-to-Decrement-Target-to-Zero 题类似，两端缩到中间求和最大。

滑动窗口：在中间用滑窗滑动找到一段列表使和最小，即能找到从两端缩到中间使和最大。复杂度$O(n-k)$

1-28

[01]-LC: 52. n-queens-ii

打表法：一行妙，虽然咩背过，但是可以复制呀 hhhreturn [1, 0, 0, 2, 10, 4, 40, 92, 352][n - 1]
回溯+集合：正经回溯配合set来快速判断当前行列对角线是否有其他棋子。棋子坐标为i, j，列集合就用j，45 度对角线集合就是i-j，135 度对角线集合就是i+j。

[01]-LC: 658. find-k-closest-elements

之前说玄之又玄的二分法，理解后其实并不难。题目是要求一个长度为k的子数组，这个k个元素都尽可能的离x近。所以很自然会想到先二分法求出最接近x的下标，然后以这个下标为基础左右扫描找到最近的k个元素，复杂度$O(k+\log n)$，而且情况很多很复杂。更快的解法是直接用二分法去找这个子数组的最左侧的下标。复杂度$O(\log n)$

二分+滑动窗口：假定有一个定滑窗为$[t,t+k]$，假定x落在滑窗内，如果我们能移动滑窗使x到两端的距离尽可能相等，也就是x-arr[t]=arr[t+k]-x，那滑窗一定包裹的就一定是最近的k个元素。有判断条件，t也有上下界$(0，len(arr)-k)$，二分要素齐全。复杂度$O(\log n)$

[02]-LC: 76. minimum-window-substring

哈希+滑动窗口+预判断：之前方法的新写法，属于滑窗复习，用了滑窗for嵌套while的板子。用for遍历窗口右界，里面嵌套while来控制左边界。

1-27

[00]-LC: 367. valid-perfect-square

built-in：一行秒了(虽然不让用)
二分法：二分求平方根，最后验证，复杂度$O(\log n)$。

[01]-BS: 843. Number-of-Operations-to-Decrement-Target-to-Zero

滑动窗口：题目要求从数组nums两端到中间的两端和为target，返回最短长度。逆向思维就是在中间找一段最长的并使其和为sum(nums)-target。滑动窗口即可。复杂度$O(n)$
滑动窗口改进：上面的写法里一个while里套了两个while，旨在模拟变长滑窗的左右界，问题在于写起来边界情况复杂，容易出错，可能会有重复判断。更好更快的方法可以用for遍历窗口右界，里面嵌套while来控制左边界。复杂度$O(n)$

[01]-LC: 401. binary-watch

老题，给二进制手表亮灯个数，求当前可能的时间，思路就两种，根据钟面时间搜索；遍历$60*12$的空间(每一分钟)

遍历：遍历所有可能的时间，分别算时和分的二进制中有多少个 1，个数符合turnedOn就是一个答案。复杂度$O(60*12*1)=O(1)$。
遍历：思路同上，一行搞定。
built-in 组合：列出时钟的刻度，排列组合，校验结果是否符合要求。复杂度$O(C_{10}^n)=O(1)$。
回溯：列出时钟刻度，递归搜索刻度，递归参数要传入深度、当前下标，小时和分钟。复杂度$O(C_{10}^n)=O(1)$

1-26

[00]-LC: 50. powx-n

built-in：return x**n舒舒服服
记忆化递归：先处理特殊情况，n=0 直接返回 1，n<0 就x,n=1/x,-n，然后类似归并排序的方式，n 分成n//2和n-n//2两部分，递归调用。提前准备好哈希 dp，存放已得到的递归解。复杂度$O(\log n)$
快速幂递归：上述方法改进，不需要记忆数组，因为 n//2 两个部分一定相差 1，所以得到n//2幂的结果y后，根据 n 的奇偶性返回y*y或y*y*x即可，此时计算无重复部分。复杂度$O(\log n)$

[01]-LC: 162. find-peak-element

二分法：同之前的做法，换了个判断条件

;[01]-LC: 76. minimum-window-substring

哈希+滑动窗口：右边先动，直到完整包含了字符串t(可以哈希统计字母个数并比较来判断)，左边再动，直到无法完整包含字符串t，此时窗口包裹的为可能的答案之一。重复直到右边滑出字符串s。时间复杂度$O(s+t*26)$
哈希+滑动窗口+预判断：思路同上，简化了"窗口包含了字符串t"的判断，维护一个变量t_cnt表示窗口内包含的字符串t的长度，当窗口左右滑动时调整。让判断过程优化到了$O(1)$。时间复杂度$O(s+t)$

[01]-LC: 438. find-all-anagrams-in-a-string

被 Howyn 启发灵感，写了个时间复杂度更低的算法，但因为 python 的 if 语句耗时比用 c 实现的列表循环慢得多，所以实际速度反而更慢。

哈希+滑动窗口+预判断：和之前的思路类似，但之前的算法复杂度高在比较的时候要重复 26 次。可以使用 bits map mask来代表 26 个字母是否都相等，滑动窗口每次移动时会调整cur列表，判断被调整的字母是否和 p 的对应字母相同，并调整mask，比较的代价降低到$O(1)$，复杂度$O(abs(s-p))$。

1-25

;[00]-LC: 658. find-k-closest-elements

二分：二分法找到 x 的下标，再从 x 出发向左右试探，直到找到长度为 k 的列表，返回。复杂度$O(\log n+k)$
二分：玄之又玄的奇妙二分。先留白之后再想想再写。关键二分判断：x - arr[mid] > arr[mid + k] - x

[02]-LC: 475. heaters

昨天的题又吸收了新的思路

排序+双指针+marker：上述方法改进，计算heaters之间的中点marker，以切割每个 heater 的"管辖范围"，在这个范围内的 house 一定属于该 heater，从而减少前面方法在 while 中的计算量(比左比右)。复杂度$O(m\log m+n\log n)$

1-24

[01]-LC: 475. heaters

这个题之前因为时间太晚没把别的方法写完，今天补上。

排序+二分：之前方法的改进，完全不需要能力检测二分。heaters排序之后，二分就能找出每个 house 邻近的左右两个 heater，直接保留左右中的较小者，所有 house 遍历后取这些较小者中的最大值即可。复杂度$O(m\log m+n\log m)$
排序+双指针：分别排序heaters和houses，用两个指针i, j同时遍历两个数组，j去找到离i最近的 heater，找到后保留当前结果，i, j从当前位置继续移动。在保留的结果中取最大值即为最小半径。复杂度$O(m\log m+n\log n)$

[00]-LC: 438. find-all-anagrams-in-a-string

哈希+滑动窗口：用 dict 作为滑动窗口的容器，每次移动窗口时调整 dict 元素个数，并对比字符串 p 对应的 dict。复杂度$O(abs(s-p)*26)$。
哈希+滑动窗口：上述方法改进，只用一个 dict 解决问题。复杂度$O(abs(s-p)*26)$。
列表+滑动窗口：上述改进，哈希在对比前需要把计数为 0 的 key 丢掉，影响速度，换成定长 26 的 list 速度快。复杂度$O(abs(s-p)*26)$
列表+滑动窗口：上述改进，只需要一个 list 就可以搞定，速度稍慢，复杂度$O(abs(s-p)*26)$

1-23

;[00]-LC: 837. new-21-game

回溯：写起来简单，纯模拟，复杂度爆炸，TLE (用例86 / 151)
回溯+记忆化：用二维数组(数组+哈希)储存入参的结果，复杂度仍然爆炸，TLE(用例90 / 151)
动规：dp[i]表示当前点数为i时，达到条件的概率。maxPts 为每次可以取的点数，那么状态方程显然有：$dp[i]=sum(dp[i+1:i+maxPts+1])/maxPts$。即dp[i]是它后面maxPts个 dp 的平均值。以maxPts=10，k=17，n=21为例，显然$dp[17]\dots dp[21]$均为 1，$dp[22]\dots dp[26]$均为 0，dp[16]即为当点数为 16 时，随机抽$[1,10]$使结果小于等于 21 的概率，答案即为$(\sum^{10}_{i=1}dp[16+i])/10$，复杂度$O(k*maxPts)$，TLE (用例102 / 151)
动规+滑动窗口：求和不需要重复计算，每次都只用滑动一位，复杂度$O(k+maxPts)$

1-22

[00]-LC: 778. swim-in-rising-water

能力检测二分+BFS：二分用来快速缩小边界找到符合条件的t，BFS 用来判断时间为t时是否能到达右下角。二分复杂度$O(\log n)$，DFS 最坏情况$O(n^2)$，总复杂度$O(n^2\log n)$
能力检测二分+DFS：思路类似，因为只用找一条路径，所以 DFS 更快，复杂度同上
最短路径(堆)：类似 Dijstra 算法，每次从堆里取出所需t最小的点，然后向堆里添加该点可达的所有点(以及所需的t)。最多需要向堆里添加$n^2$个点，所以复杂度为$O(n^2 \log n)$

[01]-LC: 1456. maximum-number-of-vowels-in-a-substring-of-given-length

滑动窗口：优化小 tips：滑动时，只在 cur 增加时判断是否为最大值，以减少判断次数

1-21

先补昨天的题，再整点小题加强信心，明天早上早起补今天的题！

[00]-LC: 34. find-first-and-last-position-of-element-in-sorted-array

built-in：bisect 还算好用
二分法：手写更快

;[00]-BS: 817. Kth-Pair-Distance.py

这个题目的关键在于绝对不能$O(n^2)$遍历数组来找到所有对的差的绝对值，只要$O(n^2)$就一定 TLE。

暴力法+排序：简单但超时 TLE
堆：同样超时
双指针+计数二分：可以用双指针来在$O(n)$时间知道差值在diff以内对有多少个；再用二分法在$O(\log n)$时间找出正确的符合要求的diff
- 双指针计数：i和j构造窗口，窗口内的即为nums[j]-nums[i]<=diff，计数就是j-1-i，$O(n)$的遍历就能知道有多少个数小于等于diff。
- 计数二分：diff上下限分别为0和max(nums)-min(nums)，因为上面的函数包含了等于diff的情况，所以即使传入了正确的diff返回结果也一定大于 k，右边界缩小为 mid(否则会错过正确的diff)。
双指针改进+计数二分：如果遍历左指针i，那么j在向前试探的时候需要判断是否越界；换成遍历右指针j则i一定在j左边，不用判断越界，在 BS: binary search上速度快了 300ms。

1-20

消极怠工还熬夜，颓废的人生啊

1-19

;[00]-LC: 475. heaters

排序+能力检测二分：复杂度$O(\log{(max(m,n))}*m*\log n+m\log m+n\log n)$。(设 houses 数量为 m，heaters 数量为 n)
- 对heaters和houses分别排序。复杂度$O(m\log m+n\log n)$
- 对于给定半径r，遍历heaters，确保每个heaters最近的 house 都在半径内(否则返回 False)。复杂度$O(m*\log n)$
- 对于半径，下限为 0，上限为 m 和 n 的最大值，二分求得最小的半径。复杂度$O(log(max(m,n)))$
排序+能力检测二分：可以只排序 heaters，能力检测的判断遍历不需要排序的 house，判断 house 最近的 heaters 能否覆盖即可，复杂度$O(\log{(max(m,n))}*n*\log m+m\log m)$

;[00]-BS: 791. Minimum-Light-Radius

这个题要先想到：在给定半径的情况下，验证三个灯是否能 cover 所有点。这个点没想到就很难展开思路。验证三个灯是否能覆盖所有点显然可以使用二分法。同样，确定半径也可以使用二分法。

排序+能力检测二分：复杂度$O((n+\log{[max(nums)-min(nums)]})*\log n)$
- 先排序，复杂度$O(n\log n)$
- 能力检测二分：用二分法确定在给定半径r的情况下，三个灯是否能覆盖所有点，第一个灯light一定在nums[0]+r的位置，第二个灯则在light+r的位置，但这是具体值，需要在 nums 中找到light+r元素(二分要素察觉)，以此类推摆满 3 个灯并返回 bool 值。需要进行三次二分查找，复杂度为$O(\log n)$
- 半径r的取值范围为$[0,(nums[-1]-nums[0])/2]$，而nums中的元素均为整数，所以半径的步进大小为 0.5，枚举r判断是否能 cover 所有点即可。枚举可以直接循环，但二分显然更加快，复杂度为$O(\log{(max(nums)-min(nums))})$。

1-18

[00]-LC: 153. find-minimum-in-rotated-sorted-array

built-in：$O(n)$大法好，不符合题意
二分法：$O(\log n)$，写的复杂了一点(条件判断部分)
二分法：$O(\log n)$，改进，直接和右端点/左端点比较并根据情况缩放范围

[00]-LC: 154. find-minimum-in-rotated-sorted-array-ii

和上面类似的题目，但是是困难题，因为出现了重复数字

built-in：$O(n)$大法好，不符合题意
伪二分法：$O(n)$，重复数字在相等的时候不能二分缩小返回，只能把右边一步一步的挪

;[00]-LC: 1901. find-a-peak-element-ii

昨天做的162的后续

二分法：将二维数组脑补成一维数组，按昨天"有坡必有顶"的思路同理，去比较它右边/左边的元素，区别在于昨天的一个元素变成了今天的一列元素，为保证能找到 peak，就必须选这一列元素的最大值(可以认为最大值一定是纵向的 peak)，这样保证了纵向是 peak，再用二分法横向去找坡来爬即可。复杂度$O(m\log n)$。

[00]-BS: 757. Triple-Inversion

看了 hint 才做出来的，一开始根本没想到归并排序，归并排序 YYDS。

朴素暴力法：$O(n^2)$，直接双重循环就行，TLE
二分法：$O(n^2)$，朴素暴力法改进得到，如果内层循环的查找是在一个有序列表中进行，就并不需要$O(n)$才能找到，而是可以用二分法做到$O(\log n)$，所以在外层遍历的同时构建一个有序列表。但这里构建有序列表要涉及到移动数组，插入的复杂度仍然为$O(n)$，所以总复杂度依然是$O(n*(n+\log n))=O(n^2)$，但是 BS 上勉强能过(py黑魔法出现了)。
二分法+平衡二叉树：$O(n\log n)$，继续优化上面的方案，结合平衡二叉树来保证有序列表的插入复杂度能降低到$O(\log n)$，总复杂度为$O(n*(\log n+\log n))=O(n\log n)$
归并排序：$O(n\log n)$，这个题目出题人的意图解法，将数组分为前后两部分，对这两部分递归调用自己排序(可以理解为已经有序了)，合并的时候因为两部分已经有序了，可以在$O(n)$时间内算出满足条件的个数。

1-17

;[00]-LC: 162. find-peak-element

遍历: O(n)思路，不符合要求
二分法: 关键点：有坡必有顶。只要有坡，顺着坡走一定能找到顶

[00]-LC: 278. first-bad-version

二分法：没什么好说的，简单题，4 分钟秒了，直接套bisect那套二分模板

1-16

[00]-LC: 33. search-in-rotated-sorted-array

二分法：强行把 nums 还原成旋转前的样子再二分。
二分法：改进，不再还原数组，直接再二分的 left 和 right 上加上旋转的偏差，数组越界问题直接取余即可。

;[00]-LC: 375. guess-number-higher-or-lower-ii

回溯+记忆化

[00]-LC: 374. guess-number-higher-or-lower

二分法

[00]-LC: 69. sqrtx

built-in：直接 returnint(x**0.5)或者int(math.sqrt(x))
二分法：参见我 1-6 号总结的 python built-in 二分法 api bisect的模块。[00]-LC: 35. search-insert-position，同时这次另总结出了一条新规律：因为bisect将数组分为了[left,mid]和[mid+1,right]两个部分，我们在灵活运用时可以这么分，也可以分为[left,mid-1]和[mid,right]，比如这个题就得这么分(当真值在右边也就是x>mid*mid的时候，因为题目要求开根号的整数部分，left 取 mid+1 就有可能丢弃掉真实结果，所以 left 必须取 mid，那为了避免死循环就必须取right=mid-1，也就是第二种分法)：
- 如果是left=mid+1，说明即使left等于mid了也是左边界在缩小，那么为了避免死循环，mid的值应当相对偏左，即mid=(left+right)//2
- 如果是right=mid-1，说明即使right等于mid了也是右边界在缩小，那么为了避免死循环，mid的值应当相对偏右，即mid=(left+right+1)//2

1-15

深夜想起来今天没做新题，凌晨 3 点补上。基本上 15 分钟搞定归并，剩下 15 分钟写了写计数排序。然后花了 1 个半小时写快排，debug 半天还踏马超时。看来快排在没有random以及填坑法partition这类 trick 的加持下还是很慢的，有个题解说快排的话 c++提交要看运气，有时候会超时。难怪 python 的 built-in 排序是写的归并，归并排序 YYDS！

计数排序：不符合题目要求
快排：能用但是超时(debug 很麻烦，且没法用填坑法做 partition)
归并排序：yyds

[01]-LC: 912. sort-an-array

归并比较熟练了，15 分钟搞定，快排还是花了快 30 分钟，partition不是很熟悉，可能还得再练，以后就填坑法了

归并排序
快排+填坑法
计数排序法(哈希表)
计数排序法(列表，又快又好)

1-14

;[00]-LC: 1737. change-minimum-characters-to-satisfy-one-of-three-conditions

朴素枚举+哈希：核心点是枚举字母a-z，令其为x，计算使字符串a完全小于x并使字符串b完全大于等于x所需要的操作数就能找到满足条件 1 的最小操作数，条件 2 完全对称，条件 3 直接统计可得。
朴素枚举：将哈希替换成了列表，企图加快速度，然而在 LC 上速度更慢
枚举+动规：朴素枚举的问题在于重复计算，拿满足条件 1 的情况举例，枚举字母x为a的结果，与x为b的结果之间是存在联系的，x=a的结果只需要再-A[i]+B[i](i为 x=b 时的下标)，就能得到x为 b 的结果。本质和上面的朴素枚举是同理的。

1-13

;[00]-LC: 1904. the-number-of-full-rounds-you-have-played

这个题轻微超时了(3 分钟)，有点菜，一开始把开始时间和结束时间都提前取整了，导致整个代码又臭又长，条件判断还错中复杂。说起来现在越来越怠惰了，昨天上一天课啥都不想干

朴素思路：把开始时间和结束时间分别提取出来，对于分钟进行取整处理(开始时间向后取整，结束时间向前取整)，然后根据小时的不同情况去判断，算总分钟数(可以看作时间戳)，最后返回结果。
朴素思路优化：既然本来都要算总分钟数，那就不要提前取整，直接获得总分钟数，然后调整开始时间(向后取整)，最后除 15 即可

1-12

[00]-LC: 1834. single-threaded-cpu

模拟题，动态极值，基本就是堆了。

双堆(小顶堆)：把所有task全部入堆(记得要先带index)。然后pop出所有在current_time之前的 task 并push到另一个堆，根据processing_time在另一个堆顺序出堆(并修改current_time)
小顶堆+排序：不再用堆排处理tasks，直接把它带index进行built-in排序，其余一样
小顶堆+排序优化：带着index排序tasks还是比较慢(因为是tuple)，可以直接排序下标(sorted(list(range(n)),key=lambda x:tasks[x][0]))，其余一样

1-11

[01]-LC: 657. robot-return-to-origin

模拟：根据指令变化 x 和 y 的值
built-in：虽然蠢但是速度却最快
哈希：一遍统计后看上下与左右的数量是否相等，和方法一思路相同

;[00]-LC: 467. unique-substrings-in-wraparound-string

前缀和+动规：需要前缀和前备知识²。如果p[i]和p[i-1]只差 1 或者差-25，那就符合条件。计算从开头到i为结尾的字符串的符合条件的子数组个数即可。但结果不能直接把动规数组相加(也就是前缀和数组求和)，而是要记录i作为字符串结尾的符合条件的子数组的最多的结果，需要哈希表。

1-10

;[00]-LC: 1203. sort-items-by-groups-respecting-dependencies

不会做呜呜呜，按照正确的思路写出来就是 TLE 我 tcl…

1-9

;[00]-LC: 886. possible-bipartition

今天的题被自己菜到了，没看出来是染色问题，光在想怎么去 DFS 了，没有想到用colors/visited数组/哈希表来表示分组的结果，光在那愣愣的想创建俩集合了。

DFS：染色问题，深搜最适合解决了
DFS+all 函数：试着用 python 的 all 函数简化代码，好用是好用就是慢了不少
BFS：用辅助空间(队列)处理，在 LC 上速度比 DFS 更快

[00]-LC: 785. is-graph-bipartite

和上面思路完全一样的题，二分图。纯属练习做，30 分钟搞定了下面两种方法哈哈。

DFS：和 LC. 886 一样的思路
BFS：和 LC. 886 一样的思路

1-8

[00]-LC: 997. find-the-town-judge

朴素哈希：一开始没反应过来这题是图，变量命名用trusted和trusted_by_me太稀碎了
哈希：用哈希表标记节点的入度数和出度数，返回出度为 0 且入度为 n-1 的节点即可

1-7

;[00]-LC: 239. sliding-window-maximum

学习了一下单调队列，发现这玩意儿和堆在push和pop这些操作上挺相似的，难怪堆又叫优先队列。

这个题目有两个关键点：1. 动态取极值；2. 移除无效值。第一点可以很容易想到堆，但是第二点堆却很难做到，这里可以通过检查堆顶是否已经无效了来移除无效值。但更好的思路是维护一个单调队列。

朴素暴力法：复杂度$O(n*k)$，直接 TLE
暴力法剪枝：同样 TLE，复杂度$O(n*k)$
堆：维护一个大顶堆，每次滑动完成后，将堆顶元素作为结果保留。复杂度$O(n\log n)$
- 移动滑动窗口时将新元素入堆
- 检查堆顶元素是否已经不在滑动窗口范围内，如果不在，出堆，直到最新的堆顶在范围内
单调队列：维护一个单调队列，滑动窗口移动后，将单调队列的队首作为结果保留。nums中每个元素恰好被入列一次并出列一次，复杂度为$O(n)$
- 每次将新元素从队列末尾入列，入列时移除所有比它小的元素
- 检查队首元素是否在滑动窗口范围内，如果不在就出列，直到队首在范围内

1-6

[00]-LC: 35. search-insert-position

我也没想到我从小到大居然没在 LC 上做过二分查找的题，今天正好借机会研究了下 python 里bisect的源码，分析了一波

朴素二分查找
二分查找：更标准的板子(分为[left,mid]和[mid+1,right]，更合理)，和bisect包的源码类似。
- bisect_left的时候，
  - 去考虑target插到右边的情况，也就是target>nums[mid]：现在要缩左边界，target最终的结果一定不会为mid(因为是bisect_left，且已经比nums[mid]大)，所以缩小左边界不用考虑mid，left=mid+1
  - 而target插左边的时候：要缩右边界，即使target小于nums[mid]，但由于插的位置是bisect_left，有可能target还是除了mid以外的值都大，那最终结果依然有可能是mid，所以缩小右边界的时候不能忽略mid，right=mid
- 类似的，bisect_right的时候，
  - 去考虑target插左边的情况，也就是target<nums[mid]：现在要缩右边界，target的最终结果一定要考虑mid (因为是bisect_right，哪怕是比nums[mid]小，下标也要往右挪)。所以缩小右边界一定要考虑 mid，right=mid
  - 而target插右边的情况：要缩左边界，就算target是等于(或 $\geq$ )nums[mid]了，但由于插的位置是bisect_right，下标必然要往右挪，所以缩小左边界不用考虑mid的情况，left=mid+1123
bisect：直接调 api(源码和上面的类似)

1-5

[00]-BS: 801. Quadratic-Application

built-in 排序法：线性变化之后直接 sort，又快又好，$TC: O(nlogn)$
队列+双指针：因为线性变化是抛物线，所以适合双指针从两端出发，根据抛物线开口方向，取两端线性变化后的值的较小者/较大者³，进行入列/入栈操作。如果a==0则直接列表解析搞定，$TC: O(n)$
队列+双指针：上述方法的改进，a==0的情况依旧可以用队列解决，删掉分类讨论。$TC: O(n)$

[01]-LC: 26. remove-duplicates-from-sorted-array

双指针：一个 cnt 留在原地，一个快指针依次遍历，cnt 仅在发现不同时移动并赋值

1-4

[00]-LC: 974. subarray-sums-divisible-by-k

前缀和+同余定理+哈希集合嵌套：和 BS: 924是换皮怪关系，不过我一开始看错题意了，以为要把所有符合条件的子串都输出出来，所以在哈希表中用 set 保留了所有下标。
前缀和+同余定理：上述方法的改进，哈希表里只存数量即可。又是写出了官方题解类似的代码 2333。

[00]-LC: 523. continuous-subarray-sum

前缀和+同余定理：和 BS: 924是换皮怪关系，居然写出了和官方题解几乎一样的代码，笑死

[01]-LC: 876. middle-of-the-linked-list

快慢指针：一个一次动两下，一个一次动一下，快的到头了慢的就到中间了。

[01]-BS: 924. Delete-Sublist-to-Make-Sum-Divisible-By-K

前缀和+同余定理：同下，对昨天的题进行一个总结和复习，改日再做一遍。

1-3

;[00]-BS: 924. Delete-Sublist-to-Make-Sum-Divisible-By-K

这个题要找出一个子列表，使原列表和在除掉子列表后能被 k 整除

废物思路：强行搞了个$O(m*n^3)$复杂度，$n^2$找子串，n 求和，再包个 m 以适配不同的 target，完美诠释了什么叫废物
循环：$O(n^3)$循环，把 targets 放在 set 里，找到需要的子串和之后直接对 set 验证即可
朴素循环：$O(n^2)$循环找需要去除的子串，$O(n)$子串求和，直接对 k 取余验证即可(所以上面两个方法连 naive 都不如)
前缀和：$O(n^2)$去循环找要去除的子串，子串求和通过前缀和在$O(1)$搞定，复杂度$O(n^2)$
前缀和+同余定理⁴：通过两者的结合复杂度能实现$O(n)$

\[ \begin{align} (total-delete)\% k&=0\\ total\%k&=delete\%k\\ &=(pre[j]-pre[i-1])\%k\\ (pre[j]-total)\%k&=pre[i-1]\%k (i\leq j) \end{align} \]

有了以上推论，对于任意$j$，我们只用去找所有小于等于$j$的$i$对应的pre[i-1]%k，是否等于(pre[j]-total)%k即可。但显然这依旧是$O(n^2)$的复杂度，该如何降到$O(n)$呢？用哈希表即可：原先对于每个j，我们都要向前找一遍所有i，看i是否满足条件，但如果我们把"满足条件"的计算结果作为哈希表的 key 储存起来呢？

具体的，在遍历j的时候：
- 要先看等式左边的(pre[j]-total)%k是否存在于当前的哈希表中，如果存在，保留j-i，这里的i指哈希表的 value。
- 把pre[j]%k的结果作为key,j作为哈希表的value存起来，至于key相同的问题看这里的上标⁵

1-2

今天这个题是真的恐怖如斯恐怖如斯。

;[00]-LC: 30. substring-with-concatenation-of-all-words

设 n 为字符串长度，m 为 words 个数，k 为单个单词的长度

naive 思路：缝缝补补拼凑而成，最后成功但 TLE 的方案；其实正确思路就在这里面了，就不考虑复杂度了(很乱)
遍历+哈希：符合要求的子串长度一定是len(words[0])*len(words)，直接遍历 s，取出这些子串，再对这些子串判断其是否符合要求即可。(对 words 建哈希统计，看子串能否符合要求即可)。有 n 个子串，每个子串要在哈希表中访问 m 次来确定子串是否符合要求，复杂度为$O(n*m)$
遍历+哈希+条件优化：上述方法的改进，不再一个字符一个字符的跳，而是一个单词一个单词的跳跃，且根据不同情况优化跳跃，以达到剪枝的效果⁶ 。
- 找到了不在哈希表里的词：直接将i跳到这个词后面，j从i开始，当前哈希表重置
- 完全匹配的情况：记录i，将i向后跳一个单词的长度，同时调整当前哈希表(删除跳过的单词)，j从当前位置继续
- 找到的词重复次数过多的情况：让i开始向右跳并调整当前哈希表(删掉跳过的词)，直到重复次数等于当前结果。j从当前位置继续
其实这个方法依然有 n 个子串要考虑，但是由于对哈希表的维护已经不同的跳跃规则，所以每个子串中对哈希表的访问变少了。具体的：
- 如果单词不在哈希表中，那就放弃这种情况；
- 如果完全匹配，只会移除上一个单词，中间的信息保留了；
- 如果重复次数过多，则从前向后调整哈希表，没有完全清零；
平均每个子串只访问了一次哈希表，所以复杂度为$O(n)$

1-1

新年好！这是1-2补写的，因为元旦在朋友家聚餐吃饭，勉强写了点题，没时间写总结了。而且题目其实也没写的很好，计算器这类题没有总结出一个通解，日后再补。

[01]-LC: 227. basic-calculator-ii

计算器最好想最简单的题

栈：把+/-当成一元运算符考虑，默认表达式一开始有+号，然后运算符则是保留上一个运算符，每次遇到新的运算符就去处理上一个运算符。个人不是很喜欢这种思路，之后再找更好的方法

;[00]-LC: 224. basic-calculator

栈+dfs：这个题目比上面的稍难一点，因为加入了括号的运算。题目提到的一元表达式倒是因为直接把+/-当成一元表达式提前解决了。括号是直接用 dfs 解决的。

;[00]-LC: 772. basic-calculator-iii

比224多了乘法和除法，本质上就是224和227的结合体，在 224 的基础上加上乘法除法即可。

栈+dfs

[00]-LC: 3. longest-substring-without-repeating-characters

哈希：naive 想法，每次遇到重复的字符，从重复字符的起点开始重置字典重新统计，这样 worst case 复杂度就是$O(n^2)$
哈希+滑动窗口：上面方法的改进，不需要重置字典，因为除了那个重复的字符以外其它的字符都是没重复的，所以可以应用滑动窗口，当右指针扫到和 set 重复的情况，左指针向右滑直到找到这个重复的字符，滑动的同时从 set 中删掉。复杂度$O(n)$

2021

12-31

[00]-LC: 447. number-of-boomerangs

这个题教会了我：千万不要在提交之前删掉print，我本来 mock-interview 已经做完了，而且思路也是最优解了，结果忘了删 print 疯狂 TLE，硬生生在那想 nlogn 的思路(并不存在)。

哈希：朴素思想是$O(n^3)$⁷，但可以用哈希保存某一个点到其他点的距离的个数，{distance: counter}，把每个点的哈希表存下来，最后进行排列计算：$(n-1)*n$，累加得到答案。$O(n^2)$
哈希：上述方法已经是最优解了，进行亿点点优化，从 1500ms 降到 500ms
- 哈希表并不用存起来，得到一个点的哈希表后保留其排列计算的结果即可。
- 算距离的部分，python 中**要比*慢的多
- 计算距离是算平方，并不需要abs(我是啥 b)

12-30

[00]-LC: 697. degree-of-an-array

哈希+循环重复：naive 思路，通过哈希表找到 nums 的 degree，将能得到最大 degree 的 candidate 都列出来，依次判断这些 candidate 能构成的答案，(关键点：subarray 必须要包含所有 candidate)，在这些答案中找到最小值，尽管在 LC 里跑赢了 100%的 submit，但是很显然 worst case 复杂度 O(n^2)。比如[1,2,3,4,5,6,7,1,2,3,4,5,6,7]这样的用例，可以自己提交一个[0-24999]*2 的例子，会超时
哈希：LC 上的思路，在哈希表里额外存放同一个数的起点和终点下标，方便之后计算长度，复杂度 O(n)

[01]-LC: 347. top-k-frequent-elements

哈希+排序：先统计频率，然后对其排序。设字典长度为 m，则复杂度为(n+mlogm)
哈希+堆：调 Counter 自带的 most_common 库，底层其实还是 heapq 的 nlargest，复杂度 O(n+mlogk)
哈希+堆：自己维护了一个小顶堆，和方法 3 底层的 nlargest 同理。复杂度 O(n+mlogk)

12-29

[00]-LC: 589. n-ary-tree-preorder-traversal

简单题，和树的遍历一个东西

[00]-LC: 590. n-ary-tree-postorder-traversal

简单题，和树的遍历一个东西

[02]-LC: 1. two-sum

老经典题目了，哈希表 yyds

用哈希表构建 value 到 index 的映射，遍历列表时先看 target-num 是否在哈希表中，不在就将 num 添加到哈希表中

12-28

现在怠惰的真就只做每日一题了吗，太菜了

[00]-LC: 987. vertical-order-traversal-of-a-binary-tree

dfs+排序：用哈希表{col: list}的形式储存节点坐标，其中 list 的元素为(row,val)，以方便排序

12-27

笑死，根本早不起

[00]-LC: 297. serialize-and-deserialize-binary-tree

朴素 BFS 思路：第一次写的有些青涩，基本思路就是队列作为辅助空间，层序遍历(并且把 null 带上)。反序列化类似操作。
BFS：和上述方法类似，略微改进调整，反序列化前删掉了多余的 null，比前者思路更清晰

DFS：递归，YYDS。不得不说这个思路太妙了，其实复杂度和 BFS 一样，只是递归代码量少很多，运行起来无比玄妙，具体来说就是：

序列化：先序遍历，用,隔开

反序列化：data=data.split(',')，然后整个nonlocal变量i，递归过程中data[i]就是根节点(先序遍历)，i+=1，然后左子树右子树分别递归调用即可。

def deserialize(self, data):
    i = 0
    data = data.split(',')

    def dfs():
        nonlocal i
        if data[i] == 'null':
            i += 1
            return None
        root = TreeNode(data[i])
        i += 1
        root.left = dfs()
        root.right = dfs()
        return root

    return dfs()

12-26

md 作息还没调过来，明天早上等人收快递，必早起，今天必早睡！

[00]-LC: 513. find-bottom-left-tree-value

用 BFS 直观，DFS 稍微想想也能搞定

BFS：层序遍历，思路清晰
DFS：naive 思路，先求最大深度，再找节点
上述 DFS 改进：DFS 过程中维护一个最大深度和 ans(当前答案)，同样仅需一次遍历

12-25

圣诞快乐！这几天作息有点颠倒，要调过来！

[00]-LC: 129. sum-root-to-leaf-numbers

naive dfs 思路：模拟测试写出来的。每次深搜的时候把目前的结果传递下去即可
dfs 思路：上面方法的优化。主要是代码更简洁了。
bfs 思路：经典层序遍历。把 node 和当前结果作为 tuple 放在队列里，到子节点再计入 ans 即可。

12-24

圣诞节和朋友聚餐，今天就做 2 题 3 个法就结束！

[01]-LC: 100. same-tree

递归：一行我秒了，有什么好说的 return p.val == q.val and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right) if p and q else p == q
非递归：用两个队列维护，pop 出来的如果 p 和 q 都不是 None 就比较，然后 leftright 继续入队；如果有一个 none 那就直接看 p!=q

;[00]-LC: 227. basic-calculator-ii

navie 思路：写的不是很好，而且有限时间内也没写出来，计算器这个专题明天好好看了攻略再动手！逆波兰冲！

12-23

今天做计算器非常失败，4 道题，明天就淦它了！

[00]-LC: 946. validate-stack-sequences

这是个大一考试里出现过的题，不过那会不要求写程序，而是自己模拟。

栈模拟：设一个栈s，现在对pop的数组遍历，设为pop_num，pop_num那一定得是push数组里来的，有且只有两种方法：
- 本来就在当前的栈顶，那就把它 pop 走
- push 的时候找到了

[00]-LC: 150. evaluate-reverse-polish-notation

栈写法：逆波兰表达式计算，经典题目了，遇到数字就入栈，遇到计算符就 pop 两下计算结果再入栈

[01]-LC: 104. maximum-depth-of-binary-tree

队列：非递归写法，用队列作为辅助栈模拟层序遍历的过程
递归：一行搞定，每次返回当前节点的深度，+1 比较大小

12-22

今天早上起晚了，下午人生第一次在美帝看了电影(一个人)，两场连看，晚上也摸鱼了好久，凌晨 1 点才写了每日一题，写了俩个方法。就这样吧，早点睡，明天早起把今天的量补一补！

;[00]-LC: 146. lru-cache

双向链表+哈希表：操作比较基本，双向链表用来维护队尾的元素，哈希表构建 key 到链表节点的映射
OrderedDict：python built-in 数据结构，真香。

12-21

;[00]-LC: 859. buddy-strings

这个题我 18 分钟才在浏览器上过，edge case 巨多

naive 模拟
改进上述思路：理清楚所有 edge case：
1. s 和 goal 长度不等
2. s 和 goal 中出现了 3 个及以上不同的字符
3. 只出现了 1 个不同的字符
4. 没有不同的字符：需要 set 来判断是否有两个以上的重复字符

[00]-LC: 59. spiral-matrix-ii

模拟：难点主要是 edge case 要在不提交前就能想清楚并 bug free

;[00]-LC: 142. linked-list-cycle-ii

快慢指针 navie 思路，只领会了快慢指针的表皮，没有深入理解题目第二个难点同样可以快慢指针解决
快慢指针：上述方法改进。假设环形链表公共部分是 a，要求的点是 ans，快慢指针第一次相遇点是 meet，那么起点到 ans 的路程是 a，ans 到 meet 是 b，meet 到 ans 是 c，而快指针走的路程是慢指针的两倍则有 2(a+b)=a+n(b+c)+b，化简得到 a+b=n(b+c)，a=n(b+c)-b。如果从起点走到 ans (路程为 a)就等于从 meet 点走 n 圈再回退 b 步。两个人可以相遇到 ans 点

[01]-LC: 141. linked-list-cycle

发现 lc 上竟然记录了我 4.5 年前用 C 提交的记录。

快慢指针法：slow 指针一次一跳，fast 指针一次两跳，有环则二者一定相遇

12-20

愉快的放假第三天，~~也只刷了一个新题。明天开始加大题量，把讲义里的题也刷上去~~。反手来一个痛定思痛，学了一个下午，4 道新题+12 个方法，我太强了😂

;[00]-LC: 41. first-missing-positive

这是个困难题，他难就难在他非要你用 O(1)的空间复杂度+O(n)的时间复杂度，然后搞笑的是比起 hastset，虽然理论上都是 O(n)，但是和 hashset 的 O(n)比起来还还是要慢不少(一个 80ms 左右，一个 170+ms)。

naive 思路：集合，得到数组中正数的个数 cnt，则答案一定在 1~cnt 之间。把 num 变成集合(违反题目 SC 要求)，判断 1~cnt 是否出现在集合中，未出现的就是答案
上面方法的改进版：集合。去掉了没用的 smallest，答案一定在 1~len(nums)+1 之间，遍历即可。
LC 题解：标记法(哈希)，关键点：答案一定在 1~n+1 之间，所以用 num 和下标进行映射并标记规则是 num->index-1，比如[3,4,1,1]，3 的话就在下标 2 处标记，4 就在下标 3 处标记，遍历的时候返回第一个没有标记的下标+1 就是结果。标记可以用负号表示第一次遍历需要把原有非正数变成 n+1(即不再考虑)，第二次遍历进行映射，第三次遍历返回答案
LC 题解：标记法(哈希)，思路类似上面，区别在于这个方法是直接通过调整元素，使数组尽变成 num[i]=i+1 的样子，比如[3,4,1,-1]就是通过交换变成[1,-1,3,4] 那么第一个 num[i]!=i+1 的下标+1，就是缺失的第一个正数

;[00]-LC: 380. insert-delete-getrandom-o1

这个题最有意思的就是你以为 set 就能搞定，但 set 并不支持随机读取

所以需要 list+哈希，list 用来随机读取，哈希维护 list 的下标，保证能在 O(1)时间在 list 里删除

naive 思路，worst case 会让 getrandom 复杂度为 O(n)
列表+哈希，列表来搞定随机取用，哈希来维护列表的 index 以保证能 remove 能在 O(1)找到并删除

[00]-LC: 88. merge-sorted-array

简单题，没什么好说的，多写几个方法吧

naive 思路，O(m+n)时间得到一个新的数组，再倒腾回去
最慢思路，插一个数挪一排，O(m*n)复杂度
方法 1 改进，O(m+n)时间的同时空间复杂度为 O(1)，省略再倒腾一趟的 O(m)

[00]-LC: 160. intersection-of-two-linked-lists

朴素思想，算长度差，对齐
链表互补法，A 走完了从 B 继续走，B 走完了从 A 继续走。两个指针都走了同样的长度
同上，写法更简洁

12-19

愉快的放假第二天，刷了一个题

[00]-LC: 109. convert-sorted-list-to-binary-search-tree

naive 思路：遍历链表找中点，把链表截断分成左中右，递归构造树，复杂度 O(nlogn)，慢在每次要遍历链表
参考的思路：链表顺序和树中序遍历结果相同。可以根据链表长度提前把树构造好，直接中序遍历树填空即可。复杂度 O(n)
上述优化：不再提前把树建好，而是用 left 和 right 来找到边界，边遍历边建树
偷懒思路：把链表变成列表，可以在 O(1)找到中点。

12-18

愉快的放假第一天，好好休息了会儿，今天只刷了两个题

[01]-LC: 24. swap-nodes-in-pairs

用一个空节点来作为头，省掉头的 edge case。然后两个指针换来换去就行了

[00]-LC: 剑指 Offer-53-II. que-shi-de-shu-zi-lcof

二分法：左右找呗
遍历：慢，不过可以一行写完

12-17

算法考试要人命了。终于结束了。今天的每日一题还是做过的，得再翻一个没做过的出来做，淦。

[01]-LC: 61. rotate-list

基础链表题，将链表首尾相连，对 k 取余处理一下再遍历 k 次，断开链表即可

[00]-LC: 414. third-maximum-number

简单题，5 分钟 AC 了。

维护 first,second,third，遍历一趟就行
类似方法但是长的好看一些

12-16

期末考试要人命，今天就只能做一个新题了。不然复习搞不完。还是得规划好复习时间。balance

;[00]-LC: 768. max-chunks-to-make-sorted-ii

这个题单调栈的思路还没完全理清，只是看了个大概，得去复习了，明天再看。

naive 思路：从右往左一个一个找 max_num，找到了且左右指针相同时存栈里，左右指针不同说明仍然是同一个块，要取代而不是 append。速度奇慢
单调栈：就遍历就完事，如果当前数比栈顶还大那说明这个可能可以单独成块，入栈，要是发现了一个数比当前栈顶还小，那说明前面的可能泡汤了，这个小的数得和前面的一起成块，一直出栈直到这个数比栈顶大了。再把最大值入栈。

12-15

[01]-LC: 232. implement-queue-using-stacks

用两个栈实现队列，一个in_stack存入列，out_stack放出列，in 倒腾到 out 的时候顺序就变成了 FIFO

lazy pop 方法：只有在out_stack为空的时候才倒腾，可以让 pop 的均摊 TC 为 O(1)

[01]-LC: 1054. distant-barcodes

统计频率，每次选一个频率最高的放入 ans 里，再放频率第二高的，交替。要注意频率是动态变化的，用堆很合适

贪心法+堆：统计频率，根据频率建大顶堆。先 pop 出堆顶，ans 放一个答案。随后再 pop 出一个项，把之前 pop 出来的频率-1 后放回堆顶，重复步骤即可。barcodes 长度为 n，不同的 code 数为 k，因为要对堆进行 n 次操作，所以复杂度为 O(n+nlogk)
数学法：和上面的思路一致，只是填坑的部分不需要用堆解决。barcode 按频率排序后，每隔一个空填充一下即可。例如
1
2
3
4
5
[1122223]
统计频率后{2:4，1:2，3:1}
2_2_2_2
21212_2
2121232
统计频率复杂度为 n，排序字典为 klogk，复杂度为 O(n+klogk)

12-14

[01]-LC: 378. kth-smallest-element-in-a-sorted-matrix

二分法：利用了 sorted 的特性，仅通过 O(n)次比较，就能找到所有小于等于 mid 的个数

具体的：从右上角开始遍历i=0,j=n-1，
    如果它比mid还小，说明从这到左边都比mid小，直接下移，i+=1, count+=j+1
    如果它比mid大，那就往左移，j-=1, count不变
直到i=n为止。注意下移的时候，j是不需要重置为n-1的，
因为向下移后右边肯定都大于等于当前元素，重置为n-1也会左移到这里

[00]-LC: 240. search-a-2d-matrix-ii

暴力法：用 py 的语法糖，一行搞定return target in sum(matrix, [])
斜线查找：和 378 的找法一模一样，舒服。

[00]-LC: 394. decode-string

贼简单的一个题，经典计算栈。30 分钟没写出来，我是废物。限时的内容就不应该想着搞花活，切记切记。

我是笨比写法
再写一遍，计算栈，不再使用"#"作为分隔了，可以当以后的板子用
参考题解写的递归法

[02]-LC: 435. non-overlapping-intervals

这题和后面的都是复习区间相关的贪心法，关键点在于要搞清楚区间是按左界/右界排序

贪心法：这题算是我贪心法入门，右界排序，理由是为了让间隔尽可能不重复，右界小的先安排能保证剩余的空间尽可能大。(当然左界排序然后从数组右边开始也是一样的)

[02]-LC: 452. minimum-number-of-arrows-to-burst-balloons

贪心法：右界排序。要尽可能少用箭，且所有气球都要社保。关键就是要用一个排序来帮助我们尽可能让气球重叠起来。可以想象我先找一个右界最小的气球，气球按右界排序了，那后面的所有气球的右界都比这个气球的右界要大，所以后面的气球里只要左界比这个右界小，他们就是重叠的。

[02]-LC: 253. meeting-rooms-ii

贪心法+堆：leetcode 付费题，没想到我们算法课遇到了这个题。左界排序。和 435 的区别在于我们不允许存在重叠，且所有间隔都必须安排(不像 435 搞不定可以直接甩)。当安排了一个房间后，这个房间的end_time就已经确定下来了，而剩下的所有会议都是必须安排的，所以最优解是尽可能让时间紧密，对于当前已有房间的end_time，我们需要在剩下的间隔中找到左界最小的，才能尽可能保证时间紧密。这里出现了动态最小值，所以还能用堆找到已有房间中的最小end_time。因为已经确定的是右界，所以要按左界排序(让时间尽可能紧凑)。我个人理解是，因为所有的间隔都是要安排下来的，贪的是尽可能让他们时间短，已经安排的右界是确定的，所以按左界排(小的先来)。而前面的题目比如：
- 435 贪的是尽可能找到多的不重叠间隔，它贪的是间隔的数量，所以要右界排序，让剩的空间尽可能大。
- 452 贪的是尽量少用箭，也就是尽可能让间隔重叠，右界排序，可以快速找到左界在它左边所有的气球(它指某个气球的右界)。

[02]-LC: 252. meeting-rooms

贪心法：上面一题的青春版，直接排序就可以了，左界右界都 ok。

12-13

[00]-LC: 451. sort-characters-by-frequency

这题不难，hash 存频率，排序再重组字符即可。

直接快排
手撕堆
heapq 堆

[01]-LC: 378. kth-smallest-element-in-a-sorted-matrix

这个题尝试了 4 个做法，还没尝试最快的二分，明天试。

直接快排
归并排序
固定堆 1: 维护一个大小为 k 的大顶堆，需要遍历所有元素，heapq，复杂度 n^2logk
固定堆 2: 类似题目 23，维护一个大小为 n 的小顶堆，heapq，复杂度 klogn

[01]-LC: 23. merge-k-sorted-lists

这个题太经典了，今天又尝试了用 heapq 搞定，不用手撕堆了。但需要改写 ListNode，要继承它并让它 comparable

heapq 堆实现

[01]-LC: 1381. design-a-stack-with-increment-operation

笑死，3 个月前做过的题再做还是想不起最优解

Naive 思路，直接模拟实现
lazy_increment 思路，只在出栈的时候去进行之前的 increment 操作，以规避对栈内元素过多的操作

dp 定义永远是重点，对于这个题目，这个定义是最方便列出状态转移方程的。↩︎
算连续子数组的个数可以分别求以每个元素的下标作为子数组结尾的个数，再求和。比如[1,3,4]可以分别求以1结尾的个数，加以3结尾的个数，加以4结尾的子数组的个数，而他们之间的是+1的关系，即以3结尾的子数组个数为 2，那么比它稍长一个元素的话呢？那就要比以3结尾的子数组个数多 1，很多动规题的根基就在这里↩︎
开口朝上则两端都是结果中较大的值，取较大值放入 deque，用appendleft(想象成是每次把最大值入列)；开口朝下则说明两端都是结果中较小的值，取较小值放入 deque，用append(想象成是每次把最小值入栈)↩︎
$(a-b)\mod k=a \mod{k} -b\mod{k}$，当然这个公式表达的其实不完全正确↩︎
key相同可以直接存是因为这个j是距离后面要遍历的j最近的一个，哪怕是覆盖了字典中的key也没关系，因为这个j的下标肯定比前面有相同key的更近↩︎
因为是一个词一个词跳的，所以整个过程还需要重复单词长度遍(即len(words[0]))，让i分别从不同的起点开始↩︎
说实话做题的时候甚至没想到这个思路↩︎

写在前面

2022

3-15

[00]-LC: 949. largest-time-for-given-digitsgoogle

;[00]-LC: 307. range-sum-query-mutablegoogle

[00]-LC: 268. missing-numberapple

[00]-LC: 38. count-and-sayapple

3-14

[00]-LC: 929. unique-email-addressesapple

[01]-LC: 904. fruit-into-basketsapple

3-13

[00]-LC: 27. remove-elementapple

[02]-LC: 39. combination-sumapple

3-12

[00]-LC: 1051. height-checkergoogle

[00]-LC: 925. long-pressed-namegoogle

[00]-LC: 482. license-key-formattinggoogle

[00]-LC: 388. longest-absolute-file-pathgoogle

3-11

[00]-LC: 760. find-anagram-mappingsgoogle

[00]-LC: 1302. deepest-leaves-sumgoogle

[00]-LC: 1237. find-positive-integer-solution-for-a-given-equationgoogle

[00]-LC: 1466. reorder-routes-to-make-all-paths-lead-to-the-city-zerogoogle

3-10

[02]-LC: 162. find-peak-elementgoogle

[00]-LC: 459. repeated-substring-patterngoogle

[00]-LC: 1021. remove-outermost-parenthesesgoogle

[00]-LC: 1025. divisor-gamegoogle

3-9

[00]-LC: 118. pascals-trianglebloomberg

;[00]-LC: 662. maximum-width-of-binary-treebloomberg

[01]-LC: 35. search-insert-positionbloomberg

[02]-LC: 547. number-of-provincesbloomberg

3-8

[00]-LC: 404. sum-of-left-leavesbloomberg

[01]-LC: 746. min-cost-climbing-stairsbloomberg

[00]-LC: 1169. invalid-transactionsbloomberg

[00]-LC: 1029. two-city-schedulingbloomberg

3-7

[00]-LC: 290. word-patternuber

[00]-LC: 542. 01-matrixuber

[00]-LC: 969. pancake-sortinguber

;[00]-LC: 581. shortest-unsorted-continuous-subarrayuber

3-6

[02]-LC: 198. house-robberuber

[00]-LC: 361. bomb-enemyuber

[00]-LC: 243. shortest-word-distanceuber

[00]-LC: 437. path-sum-iiiuber

3-5

[00]-LC: 1176. diet-plan-performanceamazon

[00]-LC: 572. subtree-of-another-treeamazon

[00]-LC: 1122. relative-sort-arrayamazon

[01]-LC: 1155. number-of-dice-rolls-with-target-sumamazon

[01]-LC: 1160. find-words-that-can-be-formed-by-charactersamazon

3-4

[00]-LC: 994. rotting-orangesamazon

[01]-LC: 59. spiral-matrix-iiamazon

[03]-LC: 1. two-sumamazon

[00]-LC: 957. prison-cells-after-n-daysamazon

3-3

[00]-LC: 653. two-sum-iv-input-is-a-bstamazon

[00]-LC: 1071. greatest-common-divisor-of-stringsamazon

[00]-LC: 5. longest-palindromic-substringamazon

[00]-LC: 973. k-closest-points-to-originamazon

3-2

[00]-LC: 717. 1-bit-and-2-bit-charactersadobe

[00]-LC: 703. kth-largest-element-in-a-streamadobe

[00]-LC: 9. palindrome-numberadobe

[00]-LC: 415. add-stringsadobe

3-1

[00]-LC: 1331. rank-transform-of-an-arrayamazon

[00]-LC: 1214. two-sum-bstsamazon