2022.08.09 开始做 LeetBook 高级算法，每周 7 题，平均每天 1 题。
除去当前元素的乘积就用当前元素左侧和右侧的数乘起来即可，这是核心的思路，根据这种思路有一种直接的，另一种优化空间的，值得多看看。
这个题看起来有点复杂，但是还是要是思路清晰的话还是没什么问题的。做题的时候根据 3 乘 3 和 4 乘 4 的例子可以看出，整个方向的顺序时固定的，然后就是维护最大高度和最大宽度，可以看出每次向左或向右的话，最大高度-1，每次向上或向下的话，最大宽度-1。其次就是代码的一些细节需要主义，为了统一代码需要把初始位置设置为(0,-1)。
这题核心的思路很简单，把四个数分成两组即可，然后用哈希存储前两个数的和，再用后两个数的的的相反数确定是否键值存在在哈希表中。因为做过 2sum 和 3sum，感觉思维反而被限制了。而且另一个区别是，2/3/4-sum 都是只在一个数组中找，但是这题给了四个等长的数组，这一点做的时候确实没有很敏感。
这双指针，我只能说用的很妙，贪心的想法也很妙，没有那么多弯弯绕。双指针只需要每次在 while 循环里进行一个操作即可，要么移左边要么移右边。每次移动的是更小的边界，因为往里收，所以间隔会减小，下一步算出的结果会小，所以结果不可能是再是更小的数字的作为边界了（贪心的思想）。
这题由于要求同时原地修改，所以需要修改格子中的数来匹配不同的状态（活到死，死到活，活到活）。标记设置的比较巧妙，初始是活的保证绝对值都是 1，这样就能够在改变的过程中记住原来的活细胞。
这题难度是 hard，两个官方题解给的解法都很妙。第一个是哈希表+负号标记，第二个是置换法。负号标记对数组大改，显得没有置换法那么优雅，置换法给了我们一个启示就是交换一次恰好可以把存在的整数换到对应的位置，如果当前位置 index 的数并不是 index+1 那么显然就返回 index+1 即可，如果都满足那么就返回 n+1。这方法真的很妙。
这题想要 O(n)复杂度，就不能用排序。所以这题很巧妙的用了一个unordered_set来存储出现的元素，在循环的过程中，并不需要每个元素都进行判断，这题进行了剪枝，只要判断比当前元素数值小 1 的个数是否出现在集合中（O(1)复杂度），如果出现了，当前的元素肯定不是起始元素，否则就是，然后进入内层循环。其实我感觉有两层循环的情况，在序列短的情况下，或者元素间隔远的情况还是可能会超过 O(n)时间复杂度的。
这题可以用题解的二分查找和二进制得到 O(nlogn)复杂度的解法，但是用快慢指针法就可以让时间复杂度降到 O(n)。真的都是非常巧妙的方法。具体的解析已经写在代码里了。
能想到怎么做和能快速又优雅地做出来还差的远呢...比如这题，数字栈和符号栈，优先级，一切都很清晰。但是因为空格的迷惑我的第一反应是先把数字和符号分离出来，但当我真的写了又觉得是冗余的。看了标准解答后一切豁然开朗，完全不需要搞两个栈，一个 vector 足够，这个 vector 存储所有需要加的数，上一个符号如是加号，将数加入数组，如是减号将相反数加入数组，如遇乘除将当前数和数组最后一个数进行计算。最后再进行一次整个数组的累加。真的写的很巧妙。
由于优先队列是以堆的形式存储的，这样我们向右移动窗口的时候就可以把新的元素放入优先队列中，此时顶堆的元素就是所有元素的最大值，只有它在滑动窗口左边界的左侧的时候在不会在滑动窗口中，所以每次就删除就好了。
这题难度是 hard，是一个典型的滑动窗口题。左指针用于尽可能地缩小长度，缩小到不能缩小时，就移动右指针，右指针用于向右探索，尽可能延长长度，直到又能再次满足条件。知道这个思路之后，写也需要注意一些细节，比如移动左指针时要恢复当前滑动窗口的 map 的值，移动右指针写成一个 while 循环等等，值得多看看。
这题有好几种做法，不过都需要非常熟悉 leetcode 第 21 题的做法。第一种方法就是朴素的合并，每次都和最终的链表进行合并，第二种方法是分治法，将给的 K 个链表两两合并，最后得到合并的链表。还有一种方法是优先队列法，就是维护当前每个链表没被合并的元素的最前面的一个，然后选取 val 属性最小的元素合并到答案中。
这题要用归并排序来做，有两种方法，一种是自顶向下的归并排序，另一种是自底向上的归并排序。第一种比较好理解，但是第二种的空间复杂度可以达到 O(1)，主要的思路就是从小到大拆分成越来越大的子链表进行多轮合并，合并的算法完全就是 leetcode 第 21 题的做法。
其实这题主要就是要解决当前的节点随即指针指向的节点还没创建的情况，所以可以用哈希表来记录，如果没创建，那么就递归地进行创建即可，递归的的写法真的值得记忆。
这题只要想到如何建图，那么就可以转化成一个很典型的 BFS 的问题了。建图的思路是把一个单词的每个字母都分别替换成星号，然后将原来的单词和只带一个星号的单词进行连边。BFS 就是从起始的单词开始走，然后最后的路径要除以二再加开始的 1 个单词，非常巧妙。
这题的思路很巧妙，我没有想到。可以反向考虑，不会被改变的 O 必然是和边缘的 O 连接的，所以只需要从边缘 O 进行 DFS 或者 BFS 即可。
这题可以有两种方法，一种是直接递归，另一种是存储父节点。后一种的可读性比较强，但是速度比较慢。第一种是通过一个判断条件来确定是否是最近公共祖先。有两种情况，要么是左右子树都包含 q 或 p 节点，要么是以下的这种情况：当前节点是 q 或者 p 并且左右子树有一个包含 q 或 p 节点。
这题官方题解的递归真的写的很好，怎么从顶递归到底，怎么把左右两个子树的路径和获取，怎么筛选，怎么设置返回值，非常值得多看。
计算连通子图的个数，只有一个节点也算一个子图。可以用三种方法，DFS、BFS 和并查集。都是非常经典的写法，值得记忆。
典型拓扑排序题，可以用深度优先搜索和广度优先搜索两种方法，经典写法了，具体算法写在代码注释里了。
基本只需要在 207 的基础上小改一下，加上记录顺序的结果数组即可。
这题是 DFS 和动态规划的记忆化搜索，注意每次 DFS 递归后的累加。从每个节点作为起点都进行一次 DFS，同时两次取 max 的地方也要注意。
回溯 + 动态规划，真的很绝。
字典树和递归 DFS 的结合。有一些细节需要注意，比如防止取重复的操作等等。
回溯法，值得学习的是一维的序列是怎么回溯的。同时还要注意去重的问题，这个也是回溯可能会导致的问题。还有另外两种做法用 BFS 和状态子集枚举下次二刷的时候再学习一下（TODO）。
用动态规划法来进行匹配，dp[i][j] 表示字符串 s 的前 i 个字符和模式 p 的前 j 个字符是否能匹配，然后从字符串的每一个字符 s 出发都遍历一遍模式 p 的每一个字符。问号的情况比较容易匹配，但是星号需要考虑用或者不用，这样就会有两种情况。
和上一题类似，动态规划法，dp 的意思也完全一样，包括便利形式也很类似，主要是处理星号的部分需要进行考虑，要么匹配 1 次，要么匹配 0 次，这个需要不同的状态转移方程。官方题解的匿名函数里直接考虑了点号。
这题最简单的思路就是确定一个可以放之奇偶皆准的排序，大致的思路就是把后半部分插到前半部分来，然后再倒序。这样的话写法非常简洁，还有一些优化的方法下次再看（TODO)。
这题有好几种解法，比较巧妙的除了优先队列还有二分查找。优先队列的解法类似合并 n 个有序数列，只利用了列递增的性质，而二分查找是行列的递增性质都利用到了。
这题使用到的是二分查找的思想，但是重要的是要找到怎么样求两个数组的中位数的过程，有一点双指针的思路，但是能够和二分的思想结合在一起，真的很巧妙。
这个题解我还没完全理解，先放一段时间。
这题的动态规划很经典，从因果关系考虑状态转移方程，思路非常清晰。
给整数 n ，返回和为 n 的完全平方数的最少数量。可以用动态规划枚举 1 到根号 n 的所有数，然后在动态规划的过程中计算出最小值。 另一种方法是四平方和定理，任意一个正整数都可以被表示为至多四个正整数的平方和，所以直接分情况考虑，1 个（即 n 本身就是完全平方数），2 个（进行一次遍历就行），4 个的情况有有一个具体的值，除了以上三种情况是 3 个的情况了。
dp[i]表示字符串 s 前 i 个字符组成的字符串是否能被空格拆分成若干个字典中出现的单词。初始化dp[i]为 0。从前往后地考虑状态转移方程，每次循环都会计算出dp[i]，而在循环内部，会进行一个探索，j 从 0 到 i 逐个查找，如果dp[j]为真，且后面的部分也能找到对应的单词，那么探索结束，当前的dp[i]为真，如果怎么找都找不到，那么为假。最后返回dp[n]。
这题在上一题的基础上要返回所有的结果。这题使用回溯+记忆化搜索，回溯是从前到后地遍历，然后递归函数返回的时候，会从后往前地将单词组合起来，所以最后，是从 index 为 0 对应的 vector 里获取所有的句子。太妙了。
有点类似分治的记忆化搜索和动态规划方法。 记忆化搜索和上一题有异曲同工之妙，类似回溯。 具体的总结写在题解了。
这题倒不复杂，就是很多细节，代码也不短。LRU 是最近最少的策略，由于 key 需要按照取用的顺序来排列，所以用一个双向链表来维护，表头永远是最近使用的，表尾是最远使用的，如果超过容量，就删除表尾的，如果访问了表内的元素，需要删除并移动到表头元素，如果访问了不存在的元素，直接插入表头。
构建一个 Trie 树，主要是要构建出 TrieNode 这个结构体，为了支持查找完整词语和前缀的要求，需要区分叶子节点和中间节点。可以用一个布尔类型来存储，也可以在叶子结点存储到达该节点的路径的完整词汇。只要确定了结构体之后，函数的实现就很简单了，只是要注意，因为用的是 unordered_map，所以只要键值有调用，那么就会自动地填充进去，这样在搜索时如果逻辑写的有问题，就可能修改 Trie 树。
用DFS应该深深刻在心里，对于这种嵌套的结构，完全可以用DFS。还有一种方法是用栈（TODO）。
用两个优先队列（大小堆）来维护，或者用一个有序集合来确定。
将两个数拼接后的结果，比大小，用这个函数来排序数，然后就按照这个排序来组合所有数，就能得到最终的结果了。很机智，但我想不到。
这题比较值得学习的是小数的表示并不是直接用浮点数，因为这样会导致精度问题。所以题解进行了一系列的转换，得到一个类似哈希值，然后用哈希表来维护点的个数。
根据身高重建队列
接雨水
天际线问题
用单调栈来解决，将时间复杂度降到O(N)，因为需要确定一个范围，所以对于当前枚举的高度，我们需要知道从左侧和从右侧出发的第一个高度比它低的矩形，然后根据index来计算围起来的矩形，分别对左侧和右侧执行单调栈的操作，很巧妙，我想不到。