2022.05.30 开始做 LeetBook 中级算法，每周争取一个章节。
经典面试题了，找不重复且和为 0 的三元组。不重复就可以先排序，然后枚举的数是越来越大的。第一个数按顺序枚举，然后找剩下的两个数加起来等于第一个数的相反数（target）的解。第三个数起始位置在排序后的数组列表末尾，在保证第三个数不小于第二个数的时候，逐渐缩小范围。如果两个数重合，那么就舍弃解，如果能找到等于 target 的第二和第三个不重复的数，就添加进解数组中。
把矩阵的存在 0 的行和列都置零，这里一开始我还在想这么简单为什么还算 medium，结果是因为我脑子里第一反应就是直接遍历，但是这会在更新时有问题，因为会影响后续的 0 的存在判断。所以，官方题解给出了两种思路，空间复杂度分别是 O(m+n)和 O(1)。 前一种是使用两个一维的标记数组分别记录行和列的零的出现情况，后一种是直接用两个标记变量存储数组的第一行和第一列含 0 的情况，然后再用原矩阵的第一列和第一行来代替前一个方法的标记数组。再优化后一种方法就用一个标记变量记录第一列是否含零，然后第一列的第一个元素就可以标记第一行是否含零了，但是这里需要从最后一行来倒序处理矩阵元素防止提前更新。
异位词包含的字母和字母的数量均相同，第一种方法是先排序字符串中的字符，然后用字符排序后形成的字符串作为哈希值，从而确定字母异位词。我的思路和第一个很像，但是我忘记了 string 就是字符的数组，可以直接用sort(str.begin(),str.end())，还非常费劲地自己写了一个哈希，搞得时间非常慢。
第二种方法使用相同字母出现的次数用字符串表示作为哈希值，这种方法的官方题解 C++版本过于高深，推荐啃一下，会 get 到很多新知识和语法。
滑动窗口经典题，建议全文背诵（不是），这题只需要求最长子串的长度，和下一题可以形成对比。
第一种是官方题解的思路。用一个 unordered_set 来存储[left,right]的字符，随着 left 的遍历，这个集合会不断舍弃最左边的元素。然后不断右移右指针，直到right+1的字符出现在集合中，然后更新 ans，取当前 ans 和 right-left-1 较大的一方。这里值得注意的 right 的初始化，是从-1 开始，判断 right+1，这样 right 指向的就是重复元素的前一个元素，保证[left,right]没有重复元素。
第二种做法是用 unordered_map 来存储字符和对应的位置，这里也是一种双指针的思想，从零开始遍历右指针，如果右指针指向的值存在在 map 中，那么就更新左指针，向右移动到右指针所在位置的下一个指针。然后插入右指针键值对，并更新长度。
求数组的最长回文子串。
用动态规划，初始化一个 n*n 的二维数组，其中dp[i][i]为真（只有一个字符的字符串显然是回文串）。首先遍历回文串的长度，然后对每个长度len，遍历左侧的位置left，同时计算出右侧结束的位置left+len-1。如果右侧位置超过 n，那么直接 break；否则判断s[left]和s[right]的关系：如果不相等，那么dp[left][right]的布尔值为 false，如果相等，那么如果回文串长度小于四的话，那么就为真（长度为 3 和 2 都满足）；否则，dp[left][right]和dp[left+1][right-1]相同（根据状态转移方程得出）。每一步更新 dp 的时候，顺便就存储最长的子串和起始位置。
另一种方法和动态规划类似，就是遍历每一个字符，然后分别以奇数和偶数的回文子串来进行扩展。
第一种做法：两次遍历。设计两个数组 leftmin 和 rightmax，分别从数组开始和末尾进行遍历。leftmin[i]表示原数组中第 i 个数的左侧最小的数，rightmax[i]表示元素组中第 i 个数的右侧最大的数。然后再次遍历，对第 i 个数组，如果有leftmin[i]<nums[i]<rightmax[i]，那么就返回 true，如果没有就返回 false。但这个方法的时间复杂度为 O(n)，空间复杂度也为 O(n)。
第二种做法：贪心。贪心的主要思想就是尽可能地使得 first 和 second 小，这样使得找到递增三元子序列的可能性更大。先令 first 为数组的第一个元素，second 为 INT_MAX。从第二个元素开始遍历数组，如果当前元素大于 second，那么序列找到，直接返回 true，否则判断当前的元素和 first 的关系，如果大于 first，那么就更新 second 的值为当前元素，反之则更新 first 的值为当前元素。这个思路很简洁，值得学习。
中级的链表题略有难度，这几题都很经典。
逆序的存储数字数位的链表相加，需要考虑金文问题，特别是遍历结束后的进位也需要注意。两个链表不等长的情况，可以每次循环判断，如果已经是 null 的话就直接把当前节点的值记为 0 即可。接着判断是否头节点指向 null（第一个节点的情况），如果是的话就将新建一个节点，将头尾节点都指向它；否则尾节点指向的下一个节点是这个新的节点，并更新尾节点。
链表奇数节点全部放前面，偶数节点全部放后面。奇数链表的头节点：head，偶数链表的头节点：even Head= head->next。两个指针分别指向奇数节点（odd）和偶数节点（even），当偶数链表的节点不为空且指向的节点不为空时，分别进行如下操作：
1） 奇数指针指向的节点的下一个节点指向下个奇数节点（odd->next = even->next）。 2) 奇数指针指向的节点更新到下一个奇数节点上（odd = odd->next）。 3) 偶数节点的下一个节点指向下下个偶数节点（even->next = odd->next），这里用odd->next表示下下个节点，因为odd已经在第二步更新了。 4) 偶数指针指向的节点更新到下一个偶数节点上（even = even->next）。
while循环结束后，当前的 odd 停在最后一个奇数上，将它指向evenHead，就将偶数节点挪到所有的奇数节点之后了。
有两种方法，一种是用元素为ListNode*的哈希集合来存储出现过的指针，显然空间复杂度较高，因为哈希集合所需要的存储空间较多，第二种是用双指针，官方题解里非常巧妙的一种做法，把空间复杂度降到O(1)，感觉和那个判断链表里有没有环的题有异曲同工之妙。两个指针从两个链表开始循环，如果循环完了还没有找到的话，就赋值到另一个链表的 head，这样如果有交点，那么肯定能在一个时刻发现两个链表指向同一个节点（看题解立马就懂了），而如果没有交点的话，两个指针都会指向 null。非常妙的做法。
中序遍历也有好几种做法呀，我只会递归的方法。还可以用的方法包括栈迭代和 Morris 中序遍历，后者可以把空间复杂度降为 O(1)。时间缘故，就不细致地讲算法了，后续再整理。
层次遍历的框架，加上双端队列来处理反向顺序的遍历。但是看了评论，说的是实际上这样并不能满足不同方向的遍历的要求，所以也可以 BFS 的时候直接用双端队列来分别处理两种方向的遍历。
这题刚开始看有点懵，看了题解以后就马上能反应过来了。核心点就是用中序遍历来确定每次根节点左子树和右子树的节点数量，这需要每次在中序遍历中定位到根节点（这里可以用哈希表提前存储中序的节点值和位置的对应关系）。递归函数会每次构造左子树和右子树，除了前序和中序的原始序列，还需要相应的开始和结束的位置。
这题还是层次遍历的套路，只需要每次层次遍历时将当前节点的 next 指针更新到队列的下一个节点即可。另一个想法是直接考虑每一层的节点应该怎么链接，分为两种情况，链接同一个父节点的和在不同的父节点的。实际上也并不难，只需要在已经建立 next 关系的当前层，更新下一层的 next 关系即可。每次沿着左侧更新 leftmost，每次 leftmost 都指向当前层的第一个节点。
取中序遍历之后得到序列的第 K-1 个即可。还可以按照一种类似二分的做法，每次记录求左子树和右子树的个数，如果大于左子树，那么这个数就在右子树中，否则在左子树中。也可以像题解那样，手写平衡二叉搜索树（长度过于离谱了）。
经典题，可以用深度或广度优先搜索，扫描整个二维网格，在搜索的过程中不断把 1 置为 0。最后的次数恰好就是深度或广度优先搜索执行的次数。还可以考虑并查集，也很巧妙。
第一次完整地做回溯相关的题，感觉还是套路满满。解这类题要能很快地想出怎么样去构建回溯的函数，就像在模板里填内容一样。
比较简单的回溯题，可以作为一个回溯的模板题。
回溯函数除了常见的参数还会传入两个参数，分别是 left 和 right，用于维护回溯中的左括号和右括号数量。回溯过程中分别判断这两个数量，但判断条件不同，左括号数量不能超过 n，右括号数量不能多于左括号的数量。然后就进行普通回溯即可。
这题可以和下面的子集这一题形成对比，在全排列里需要注意一个问题，元素是不能重复的。如果是用vector<int>类型的 tmp 来加入和删除元素，作为中间结果，那么就可能出现同一个位置的元素重复出现的情况。为了保证每个元素只出现一个，我们直接将原始的数组传入，回溯函数中会交换和恢复元素的位置的操作，从而得到一个新的排列。
可以有两种方法，位运算和回溯。位运算其实只要掌握之前总结的就能很快写出来，回溯的方法是非常基础的，这个题适合当做回溯的模板题。
在二维的 board 里搜索出指定的单词，单词需要按照顺序且在相邻的单元格中构成。这一题还是有一点难度的，我直接参考题解的思路了。每次考虑单元格每次回溯要在相邻的位置（更新 i,j 再传入回溯函数），而且需要保证在同一次回溯的时候，不能访问已经访问过的单元格。
这章都是一些比较经典的排序和搜索题，搜索都是二分查找的变体。
只有 0、1、2 三个元素的数组要按照递增排序，也叫荷兰国旗问题。 主要的两种做法的整体思路如下。 方法一：先把 0 交换到最前，再把 1 交换到最前。（这样需要两次遍历） 方法二：只维护一个头部，始终有连续的 0 和连续的 1。用两个指针分别指示最后一个 0 和 1 的下一个位置，如果找到 1，那么就和 one 指针交换，并后移，如果找到 0，那么就和 zero 指针交换，但是这样会把一个 1 换出去，所以就再把它换到 1 的最后即可。
快排典型题，记住模板就比较好写。还可以用小顶堆，等后续再总结。
快排典型题，和上一题类似。
看讨论区和官方题解有很多花式解法，比如直接找最大值、找到第一个下一个元素比当前小的元素就满足条件。当然也可以用爬坡法，只要每次往高处走肯定能找到，这个思想是很重要的， 明白了这一点其实代码还是很好写的。
老题重做，再做了一次还是不太熟练。元素的最后一个位置可以转化成大于这个元素的第一个元素的位置，所以两个二分的条件是有区别的。还有一个需要记忆的点是初始化的位置和最后的筛选，两个位置都以数组的长度来初始化，这样如果大于这个数的元素找不到的话，在最后的减一操作下，最大位置也不会成为-1。
感觉还是比较简单的，只需要先按照区间的左端点排序（这个直接默认排序即可，不需要额外写），然后把第一个区间放入最终的数组中，然后不断地遍历所有的区间，看能不能被最终数组的最后一个区间包含，如果能就更新，否则就把当前区间加入最终数组。
这题真的是非常巧妙的二分法，考察的是我们对于二分的灵活运用。乍一看好像并不是一个有序的数组，但是实际上，二分法一定会分出一个部分有序的和一个完全有序的数组，然后我们需要判断 target 到底在完全有序的数组还是在部分有序的数组，由于部分有序的数组不好判断 target 有没有，因此每次判断只需要看是不是在完全有序的数组里就行，不在肯定就在部分有序的数组，然后按照这样的原则来更新 left 和 right。
之前做过的一题，但是完全忘记思路了。大致的想法就是从右上角开始搜索，如果 target 小于当前元素，那么就将列减 1，反之将行加 1，这个想法非常巧妙的。
这里刚开始我理解错了题目的意思，题目给的是最大的范围，也就是说下一次跳跃并不是一个点而是一个范围。所以从倒数第二个可跳的范围开始，如果当前的 index 加上可跳范围能够 cover 住 end 的值的话，那么就更新 end 到当前的 index，就这样一步一步，如果最后不能到达 0，那么就不可达。
贪心的想法就是维护能走到的最远距离，看看能不能 cover 到 end。
这题很简单，只能向下走和向右走，可以很明显得到状态转移的思路是：当前的块的路径数等于到左侧和上侧的块的路径数之和，然后把起点的路径设为 1，这样遍历就可以得到最终的结果了。
这题的状态转移公式有多种，这里介绍最简单的：对每个硬币值，都计算先计算除去 1 个后金额的最少硬币数，然后求最小值，再加 1，当前的硬币值就是自身和上述值取较小者。因为没有小数，所以最多的硬币数就等于金额，根据状态转移方程再减少就行。
老题了，但我也没做得很快。一维的 dp 数组的第 i 个表示从 0 到 i 的最长递增子序列的个数，然后在更新第 i 个时，需要先将dp[i]置为 1，再从数组的第一个到第 i 个数进行更新，其中 dp[i] = max(dp[i], dp[j] + 1);是状态转移方程，感觉和零钱兑换那题有异曲同工之妙，对每个 j 都会计算一次dp[j]+1，并和当前的dp[i]进行对比，更新。
另一种方法是贪心+二分查找，因为不是动态规划章节的主要内容，就不赘述了。
就是把二叉树进行序列化之后，在进行反序列化，不固定序列是什么，因此可以使用 BFS 和 DFS 两种方法来做，其实序列化和反序列化看起来是相反的，但是两个函数还是比较相近的。
这个比较典型的就是用哈希表来额外存储每个元素对应的 index，实际的元素是存储在 vector 中的，这样插入操作就是在 vector 后追加，删除操作就是要把待删除的元素和最后一个换一下，这样删除最后一个就能保证时间复杂度为常数，获取随机元素就是直接获取即可，可以重点看一下 C++是怎么写的。
这个章节的题比较多是模拟计算的，比如指数、平方根、除法、小数的，主要是要明确计算机在计算的时候的一些细节，比如溢出情况的考虑，同时掌握快速幂、快速乘的一些算法思想，就其实可以把问题转化成简单模拟题。
这题的模板值得记忆，leetcode 166.分数到小数同样用了相似的写法。主要的思路就是寻找有没有循环。其实写的时候有点卡在数字会不会一直变大的情况，根据题解计算最多位数的最大数，可以发现它不可能无限增大下去，所以这个情况实际上是可以被排除的。然后就是利用哈希集合在每次更新数字的时候存储这个数，然后 while 循环的判断需要添加当前数字是否在哈希集合的这个判断。
这题其实思路是对的，但是想复杂了。因为我还真的考虑了因子 2 的个数，但实际上肯定因子 5 的个数显然比 2 要少，所以恩本无需考虑。直接计算从 1 到 n 每个数的质因子 5 的个数，再累加即可。
三年前写过的一道题，再写的时候竟然和力扣官方题解惊人的相似。反正是挺简单的一道题，可以把序号当成一个二十六进制的数然后转十进制就行。
直接简单模拟会超时，所以考虑使用快速幂算法。把次数当成一个二进制数，二进制位上为 1 的数，相当于就是需要乘的幂次，最后再累加就行，每次以 2 次幂更新当前位数的幂次值。除此之外，需要考虑一些边界条件，在最开始转换正负号时，如果 x 是 INT_MIN，直接转会变成 INT_MAX+1，就会溢出，所以需要先转成 long long 类型。
典型二分法的题目，建议全文背诵（不是）。只需要找到平方小于 x 的最大的整数即可，二分查找就能找到答案。
这题还挺复杂的，有好几个需要考虑的情况：
- 被除数是 INT_MIN，除数是 1 直接返回 INT_MIN；除数是-1 返回 INT_MAX（处理溢出情况）。
- 除数是 INT_MIN 时，被除数是 INT_MIN，返回 1；其余情况返回 0。
- 除此之外，在考虑符号的时候，要正数转为负数，因为如果反过来就会溢出，除非改成 long long。
整体的思路使用二分查找，但是判断条件需要用类似快速乘的方法来计算（因为不能用乘法除法），这里我是使用官方题解的写法，感觉还是比较巧妙的。
模拟竖式除法的部分非常巧妙，找循环节的过程和 202.快乐数那一题如出一辙，计算到恰好一个循环节结束就可以了。跳出循环时，实际上计算了未循环的部分和一个完整的循环节，访问当前余数对应的 index，就可以找到循环节从哪一位开始，就能够加上括号了。
其他专题的题，都很不拘泥于套路，都是不能马上想出来的题目。
这题一开始的失误在于打算按位来累加，但是在一个地方卡住了，就是无法判断三个 1 中至少有两个 1 的情况，就没办法解决进位。但是官方题解的思路非常巧妙地一点就在于，它并不期望从右到左逐位的模拟，而是直接算出两个数的全体进位，再慢慢左移从而每次都处理一个整体的进位（这个很难描述，但是想象出来了就能立马 get!）。
这题很快写出来了，没什么好说的，只要知道逆波兰表达式不需要考虑括号，其本身就具有表征运算的顺序即可，那么实际上就用一个栈机械模拟就好。
这题有好多巧妙的方法，使得复杂度能够得以降低。
- 排序法：通过排序，能够确定下标为$\lfloor \frac{n}{2} \rfloor$的元素一定是所求的众数。
- 随机化法： 随即找一个数，验证它是不是众数。
- 分治法：用比较经典的回溯或者说分治法来计算，直到所有的子问题长度都为 1。这里题解的证明还用了主定理，算是学过的知识的真正实践了。
- Boyer-Moore 投票算法：重点介绍这个算法，主要就是维护两个数组，一个是 count 数组，另一个是 value 数组。 count 数组的计算是这样的：如果当前 index 的 count 数组值为零，那么当前 index 的数就会是当前的 candidate，count 表示的是当前 candidate 出现的次数比非 candidate 出现的次数多几次，这样在遍历数组计算 count 时，遇到和当前 candidate 相同的数就加 1，否则就减 1。 在最后一段中，candidate 存储的候选众数就是真正的众数。（为什么？可以理解乘众数和非众数两个阵营以一敌一地厮杀，直到最后剩下的必然属于多数阵营，所以最后存储的就是多数阵营）
我只能说，这题的两个官方题解的解法都很妙。一个是对时间的模拟，每次选择不在冷却时间且剩余执行次数最多的任务，每次遍历时需要维护任务的最早可以执行的时间和次数。另一个是画格子构造法，由于每个任务占的时间是1，所以可以用格子来逐个排列任务的数量，最后还需要比较任务总数的大小，这部分的讨论也很值得读一下题解原文。