• （堆优化版Dijkstra最短路）
  • （哈希表 + 找规律）
  • （排序 + 双指针 + 贪心）

• • （记忆化搜索 + 博弈论）

• （深搜 + 链式向前星）

• • （优先队列 + 哈希表）TLE
• （多路归并 + 优先队列）

• • （枚举 + 哈希表 + 双指针）

• • （随机 + 哈希映射）

• • （字符串 + 双指针）

或者我们就可以直接使用双指针的算法，直接判断一个字符串是否为另一个字符串的子序列即可。

判断一个字符串中是否存在另一个字符串其实只需要要遍历原字符串，在遍历的同时遍历我们需要检查的word，其中两个字符串中相同的字符就可以继续向下比较，否则就让原串中的指针向下即可。

注意：判断一个字符串中是否存在另一个字符串是一个常用的双指针模板。

109. 有序链表转换二叉搜索树

因为需要将链表中的数值构造成二叉搜索树，而需要满足二叉搜索树最大的性质就是要使得构造成的树的中序遍历是一个有序的，在本题中因此链表是升序的，所以二叉搜索树的中序遍历还必须是升序的。

根据这一点有一种构造的方法就是：每一次将链表中间的数值作为二叉搜索树的树根，然后将链表分成左右两个分别有序的链表即可。

因此链表中不能支持随机访问，所以我们可以将链表中的数组放在数组中这样就可以快速地找到数组中的数值了。

如果不将链表保存为数组也是可以的，但是我们每一次都需要去找链表的中间节点。

406. 根据身高重建队列

本题是一个排序题，而且是一个有两个维度的排序题。所以我们就需要考虑两个维度之间排序的优先级问题。因为题目中限定了第二维度，即第i个人前面只能由people[i][1]个人升高的高度比第i个人大。因此我们在排序的过程中是不能影响第二维度的。

所以如果我们想要将第一维升序排的话，那么我们就要考虑当前第i个人前面需要有people[i][1]个空位置（如果被别人占了的位置就不算空位置）加上自己需要占的位置，就是需要将people[i]放在ans中第people[i][1] + 1的空位置上。

如果出现了两个相同的身高的时候，我们需要按第二维度排降序。因此两个身高一样高，所以需要增加第二维度上的人数。为了不影响第二维的话，我们就可以降序排序，这样相同升高之间的人就不会相互影响了。

如果第一维降序排序的话，那么就在people[i][1]的位置上插入people[i]即可，因此people[i][1]表示的就是前面的人数，而因为第一维已经是降序排序了，所以ans中的人就是已经排好队而且比待插入的人的升高要高。

总结：在本题这种有两维需要排序的题目中，我们通常都是抓住其中的一维，固定下来之后在再第一维已经有序的情况下继续考虑第二维上的数字。

如第一种方法中：固定了第一维是升序的，所以我们需要看的是其中的空位置。

在第二种方法中：固定了第二维是降序的，所以我们需要看的数组中的人数。

（记忆化搜索 + 博弈论）

本题不能使用二分来解决，而是要使用递归来爆搜。

因为本题不是要求出能找到某一个数字的最少次数，而是找到任意一个数字的最小代价。因此我们需要考虑每一个数字作为第一个被猜到的数字。

使用递归（爆搜）或者动态规划枚举所有的情况。

r]中的最坏情况下的最小值。意思就是我们第一次猜的数字有n种情况，而每一种情况下需要的次数不同，最终的答案就是这n中情况中的最小值。但是猜每一个数字都需要考虑最坏的情况，即我们需要尽可能地猜错或者是多猜。这就是博弈论，在最聪明的情况下做出最傻的事情。

可以将递归的过程写成动规。因此我们枚举的一个一个的区间，所以可以使用区间DP的模板。

k)当枚举右边界枚举到n的时候，会用到n+1，所以需要开到f[n+2][n+2]。

也可以开到f[n+1][n+1]，但是需要判断一下特殊的情况。

1583. 统计不开心的朋友

为了实现模拟，我们准备了match数组和close数组，这样就可以快速地找到一个数字的配对数字，也可以通过close数组来表示两个数组的亲密程度。

洗牌算法就是在模拟C++中的random_shuffle函数。即对于下标i而言，从[i, n - 1]中随机选出一个数字和i位置上的数字交换。这样就可以得到一个公平的洗牌结果。也就是前i个数字已经被打乱了，我们需要打乱下来的n -

863. 二叉树中所有距离为 K 的结点

因为本题需要顺着树枝往上找节点，所以我们就可以将树转换成无向图（树本就是一个有向图），这样就可以倒着往上找树的节点了。

然后就是从target这个节点开始往外找到第k层的节点即可。

如果使用爆搜的话，需要记得son != parent，这样就不会循环找同一个节点了。

如果使用宽搜的话，需要使用vis数组来标识节点已经被访问过了。

（深搜 + 链式向前星）

也可以通过使用数组的方式（链式向前星）的方法来建图。

如果将每一个nums1[i]都遍历一遍，时间复杂度为O(n²)。因为是要在一个数组中找两个和nums2[j]最接近的数字（左右两边），所以我们就可以使用二分。

可以使用set中自带的lower_bound函数，或者将nums1拷贝一份。将拷贝的函数进行排序，然后再拷贝并且排序之后的数组中使用二分。

如果使用暴力方法做本题的话，因为需要枚举每一个数字和其他数字的和然后再判断是否为2的幂，所以这样会超时。

所以本题就是一个使用哈希表去优化时间的典型案例。我们可以将前面的数字使用哈希表记录下数字和这个数字出现的次数。而且我们枚举的是可以配对成2的幂的一对数的后一个数字。然后每一次在2²²中挑选出，所有的2的幂进行判断，是否有2的幂 - 枚举的数字出现在前面枚举的数字中（即哈希表中），然后就可以使用O(1)的时间将算出可以和当前枚举到的数字进行配对的数字的个数了。

注意：因为我们只关心数字出现的次数，而不关心具体哪两个数组，所以可以使用哈希表以空间换时间来优化。其实本题很像「两数之和」都是边计算边存储。

981. 基于时间的键值存储

本题还是一个键值对的问题，所以可以使用哈希表来完成。

因此当得到一个key的时候，我们就可以在hash[key]这个数组中使用二分找到的最大的时间对应的值了。

也可以使用哈希表中套一个map，这样就可以使用upper_bound函数了。（这是使用upper_bound函数来模拟找到的最大值）。

target最小的数字。但是本题需要求出最大的数字，其实可以使用upper_bound找到> target最小的数字，然后-1就是最小的数字了。

（优先队列 + 哈希表）TLE

因为超级丑数有由另一个超级丑数和primes数组中的质数的乘积，所以我们可以通过不断的从超级丑数中选取一个数字和primes中的质数相乘就可以得到一个超级丑数，如果想要得到第n个超级丑数的话，我们可以将求得的超级丑数放入小根堆中，这样每一次堆顶的元素就是最小的超级丑数，在使用这个超级丑数去和primes中的质数相乘得到新的超级丑数。

注意：一个超级丑数可能是多个超级丑数和pirmes中乘积的结果，所以如果遇到相同的超级丑数需要跳过。

一列超级丑数一定是由另一列超级丑数和primes中的乘积构成的。所以primes中的每一个质数都可以构成一列新的超级丑数。

我们可以使用index数组表示primes中第i个质数在超级丑数的序列中已经排序到第几个位置了。例如：如果primes[i]已经加入到超级丑数的行列中之后，那么就将ans[index[i]] * primes[i]放入超级丑数的行列中，并将index[i] ++，这样下一次primes[i]就会与primes[i]这个超级丑数这个行列中的超级丑数相乘。

（多路归并 + 优先队列）

如果小根堆就可以快速地找到剩余超级丑数中最小的超级丑数了。并且将当前这个超级丑数所在的primes[i]对应的超级丑数的列的位置记录下来。

395. 至少有 K 个重复字符的最长子串

（枚举 + 哈希表 + 双指针）

一般看到了「最长字符串/区间」这种题目，我们都会想到使用双指针和滑动窗口的解法。但是如果本题使用双指针的话，却是不可以，因为这题不满足使用双指针的性质，即满足「单调性」。假设s串的一段区间[i, j]，如果右指针j向右滑动的话，如果加入的字符是一个i左侧出现过的字符的话，那么此时i指针向左滑动就有可能满足区间中的字符个数也是>k的，所以这就不符合单调性的要求了。

此时我们可以枚举区间中字符的个数，来限制滑动窗口的中的字符种类的个数。「当限制了窗口内的字符个数的时候，区间重新获得了单调性」。因为多了字符种类个数的限制，所以当右指针向右移动的时候，左指针只会不移动或者因为字符种类超出限制而也向右移动。这样区间就又获得了单调性。

注意：可以想到使用枚举的方法是因为题目提示中说明了s仅由小写字符组成，因为数量比较少，所以可以使用枚举的方法。

先按位数分类，1~9, 10~99, 100~999….。k表示数字的位数，t表示数字的个数，d表示10的k次数方。因为数字小于2³¹ - 1，所以最多只有10次计算。然后就可以计算在k位数下的第几个数字，最后转换成字符串计算在一个数字下的第几位上。

和「31. 下一个排列」的思考方法类似。如果贪心的想法就是尽量的将大的数字放在高位。

将数字的每一位数字都看成柱状图，那么降序表示高位上已经放着大的数字。而第一个升序表示可以有调整的空间。如果转折点为index的话，为了使得数字的交换一次之后可以变得最大，那么就需要取最后面一位最大的数字（因为最大的数字可能有多个）。将这个最大的数字和前面第一个比这个数字小的数字进行交换即可。

注意：本题不可以直接找到这个数字中最大的一个数字，然后和前的数字交换，因为最大的数字可能会有相同的多个，所以不能确定交换哪一个。

本题就是要模拟这个第一行是title（即食物的名称），第一列是桌号的二维表格。

1.第一行：Table + 去重的并且升序的食物

2.中间内容：升序的桌号 + 食物的数量

我们可以哈希表去重，然后排序来解决第一行的问题。中间的内容需要使用不同的桌号对应相同的食物名称。所以也可以使用哈希表做对应的报表格。并且因为每一个桌号都要对应相同的食物名，所以哈希表中还需要一个哈希表，被嵌套的哈希表需要维护在同一个桌号下不同的食物的数量。

528. 按权重随机选择

如果想要按权重来选择数组中的数字的话，那么我们就不能只仅限于不同的点（数字）来随机选择数字，我们可以将相同的数字放在一起，然后将数字放在数轴上，而相同的数字越多，那么选择的范围就越大，所以这样就可以做到一个数字的权重越大，那么数字的随机选择到了概率就越大。

但是将数字放在数轴上，我们怎么知道第n个数字应该对应原来第几个位置上的数字。

所以我们必须要使用前缀和的思想，w数字的前缀和可以解决这个问题。因为数轴上相同数字的最后一个数字，就可以表示这一段的数字。因此我们只需要枚举1 ~ sum中的随机数即可。

例如：前缀和数组为[1,3,6]，而随机数为5，那么我们通过二分的方式可以找到6，6的下标为2，所以就可以选择2。

318. 最大单词长度乘积

本题因为需要比较出两个长度乘积最大的乘积，所以只能将所有的单词两两进行乘积的比较。

但是两个单词之间还需要判断是否出现了公共的字母，所以我们可以使用哈希表将单词的所有字符放进去，然后判断另一个单词中是否存在公共的单词即可。

但是这样的做法时间复杂度就和单词的长度有关了。一旦单词的长度很长的话，这个办法就不可以了。

如果想要快速地判断两个单词是否具有公共的字母的话，可以使用位运算的方式（使用位图的形式）将单词中的字母（因为单词中仅包含小写字母）记录下来。这样想要判断两个字母是否具有相同的字母就可以通过(state[i] & state[j]) == 0来进行判断，如果等于0的话，说明两个单词之间没有公共的字母。但是如果两个单词之间有相同的字母的话，那么&之后的结果就一定!0。

可以利用字典树来实现用小到大的顺序。每一层的树枝我们都从左向右依次的排序即可。

而且可以直接使用dfs深度搜索出来，而不用实际地创建出一个字典树。

802. 找到最终的安全状态

本题最终就是要将从某个点出发的所有路径都没有环的点保留下来。这就让我们可以想到拓扑排序，但是因为所有的点并不一定是一个有向图中的点（可以会有孤立的点），所以我们判断一个点是否为安全的就会有困难。

我们从一个点出发，到达的点如果是安全的（即没有入度，也就不能向外扩散了）那么达到这个点的这条边也是安全的。因此我们其实也可以反过来想，如果一条边是安全的，那么达到这个点的所有边也都是安全的，所以到达这个点的出度也就可以减一，相当于没有这条边了。最终剩下的点中没有出度的边（也就是孤立的点）就是安全的。

本质：本题可以说是将所有边反向的拓扑排序。

本题如果使用暴力解法的话，就是将所有的从first, last中的所有数字依次的加上seat，但是这样的时间复杂度就太高了。

如果将在O(1)的时间内，将一段的区间中的数字都增加inc的话，就可以使用差分的思想。差分数组的前缀和数组就可以这个数组本身。所以差分和前缀和是一对相对的概念。按照差分的规则，如果想要[l, r]区间中的数字同时都增加inc的话，那么就需要将ans[l] +=

决定一个牌是否会倒取决于这个牌左右两边离得最近的牌的倒向。

L表示左边倒下的牌，R表示右边倒下的牌。

注意：为了对于前缀和后缀中都是.的字符来说，如果不想单独地进行判断的话，就可以在s的两侧加上‘L' + s + ‘R'，这个就不会对s[i]的的倒向造成影响，同时s[i]也可以进行判断倒向。

可以先算出相同位置上字母相同的字母个数，这个比较简单。然后再看同一个位置上的字母不同的时候，在serect中是否存在guess[i]，如果存在则y ++，然后将这个字母从哈希表中去除，否则的话，说明这一位数字猜的不对。

或者也可以将所有的在guess中有secret中的字母都计算出来，然后计算出相同位置上相同字母的个数，最后两数相减就是不同位置上具有相同的字母的个数。

需要求出n的格雷编码是有规律的。n的格雷编码是n - 1的格雷编码中所有的数字左移一位和n - 1的格雷编码逆序中所有数字左移一位再加一。

本题就是算出最长的一段并且区间中的种类个数小于等于2的区间的长度。

本题和leetcode第3题是相同的，都可以利用双指针维护一段种类k小于等于2的一段区间。

519. 随机翻转矩阵

（随机 + 哈希映射）

为了可以更方便的看到随机的效果，我们可以将二维的随机改造成一维的随机。

我们在一维的数组中可以随机的选择数字，但是已经选择的数字，在下一次的随机选择前我们需要将选择过的数字删除掉。为了时间复杂度更小的删除，我们可以使用类似删除堆中堆顶的做法，即将该数字与数组的末尾交换，然后删除数组的末尾，这样就可以使用O(1)的时间就将这个数字删除掉了。

并且为了空间复杂度的降低，我们不用开一个一维的数组来保存，而是使用一个哈希表来保存数字的映射关系。而且默认如果哈希表中没有数字，那么说明这个数字没有用过，直接这个数字的编号即可。如果哈希表中已经存在这个数字了，那么说明这个数字之前已经被使用过，而且这个位置映射值为其他没有用过的数字，因此就可以使用这个位置的映射。最后就是当前位置上这个使用的数字和数组末尾的数字交换，然后删除数组中最后一个数字即可。

本题就是一个暴力的结果，我们可以先将不用大礼包的钱算出来。然后再和购买大礼包的钱比较取一个最小值即可。

在购买大礼包的时候，我们就可以使用最暴力的方法：一个一个比较。如果可以在needs数组（即所需数组）的范围中，那么就可以购买这个大礼包。如果大礼包中的物品个数已经超过了needs数组中所需要的物品的数量，那么就不能购买这个大礼包，然后挑选下一个大礼包。

使用红黑树map将已经计算过的答案ans保存起来，这样就可以减少很多的重复计算。

1743. 从相邻元素对还原数组

我们需要将打散的数字相互串联起来，那么就需要将两两相邻的数字进行映射，这样就可以在O(1)的时间中找到一个数字左右两边相邻的数字。所以我们可以使用unordered_map>哈希表进行类似于建图（邻接表）的形式将两两数字做一个映射。

只有数字之间的映射关系还不够，我们需要将有映射的数字之间串联起来，因此我们需要找到这一串数字的头或者尾部，因为这两个数字相邻的数字只有一个，所以我们可以从这个数字出发然后向后延伸。

最后就可以利用搜索的方式将数字串联起来，如果前面已经放入ans数组的数字不用重复放入，所以要是用哈希表保证所有的数字都是单独的串联相邻两边的数字。

1.匿名函数中[]的意义

• [] //未定义变量.试图在Lambda内使用任何外部变量都是错误的.
• [&] //用到的任何外部变量都隐式按引用捕获
• [=] //用到的任何外部变量都隐式按值捕获

注意：当传递函数名的时候，function需要加上const。如果使用function函数指针传递的话，可以不用加上const。

（字符串 + 双指针）

本题只需要将相同连续的数字的个数通过双指针数出来，然后再加上这个数字本身即可。

可以将“1"通过n-1次的变化就可以形成最终的答案。

本题看似很复杂，好像要将从[0, 0]点到target的路径和所有的ghost到target的路径都输出出来，然后一个一个比较。但是其实我们可以使用数学中不等式的思想就可以解决这个问题。

假设[0, 0]到target的距离为a的话。如果说我们最终会被ghost抓住的话，那么ghost一定会在我们去往target的途中就会和我们相遇，也就是a >= ghost和我相遇的距离，那么延伸一下，ghost到target的距离是b，那么b 。反过来理解，如果ghost比我们先到target的话，我们就不可能到达target了。

300. 最长递增子序列

可以根据动规进行优化，即使用贪心的手法。

我们可以维护一个不同长度下最长上升子序列的结尾的最小值，因为都是最长上升的子序列，所以结尾的最小值也一定都是单调递增的。并且因为相同长度下最长上升的子序列的结尾一定是越小越好，因为结尾的值越小留给后面上升子序列的”发挥空间“就大，这样可以保证所以的子序列的长度都可以最长。

所以我们可以在这个单调递增的序列中二分出最大的一个数字然后将这个数字后面一个位置替换为nums[i]形成一个以这个数字为结尾的最长上升子序列。或者可以找到>= nums[i]最小的数字，然后替换掉这个数字形成一个以这个数字为结尾的最长上升子序列。

334. 递增的三元子序列

要找到三个连续的递增三元组，其实就是在找子序列中是否有长度为3的上升子序列。所以我们就可以使用最长上升子序列中的框架，只不过这一次我们只用维护一个最长最多为3的最长上升子序列的最小值的队列即可。

因此只用维护一个长度为3的序列，所以可以直接枚举。

最简单的形式就是我们只维护两个数字，如果就覆盖small。如果就覆盖mid，如果> mid说明已经出现了三元组，可以直接返回true。

650. 只有两个键的键盘

我们可以发现一个规律：每一次复制一次，然后粘贴k次，这样操作后的结果就是原来字符串的k + 1倍。所以我们可以将一次复制+k次粘贴看成是一组操作。最终是很多个这样的一组一组的操作形成了字符串。而每一组操作中的操作的次数相乘就是n，也就是说一组操作中的个数就是n的因子。

所以这个问题就是转换成了n的所有因子的和的最小值的大小。我们知道a * b >= a + b，所以我们需要因子尽可能的分解成最小的质因数，这样就可以将因子拆解成质因数分成一组，在这种分类的情况下因子的和最小，也就是操作的次数最少。

所以本题就是求出n的所有质因子的和。

797. 所有可能的路径

本题考察的就是一个有向无环图的深度优先搜索，我们可以使用dfs的方式”一路走到黑“，每一次dfs就可以获得一条以0开始n - 1结尾的路径。

我们每一次只要到[l, r]的范围之内找到一个最大值做当前树的根即可，root左边连着左边递归出的子树，右边连接右边递归出的子树即可。

我们只要按照题目中的要求对链表进行改造即可。

第一种改造的方法可以是直接在原链表上改造，可以先找到链表的尾，然后再遍历链表中的节点，比较节点的大小，如果val 就直接跳过，如果val >= x的话，就插入到原链表的末尾。

第二种改造的方法就是：我们可以创建出两条链表，一条链表上的节点上的值全部，一条链表上的值全部>= x，然后将两条链表连接起来即可。

457. 环形数组是否存在循环

在链表中我们知道可以使用快慢指针来判断环，即一个指针一次走两步，一个指针一次走一步，如果图中有环的话，那么这两个指针一定会相遇的。

类似的，我们可以在数组中也使用快慢指针来判断图中是否有环。只不过我们需要判断从一个点出发的边是否有反向边或者自环，这些边需要跳过。

说到需要判断图中是否存在环，我们最先想起来的就是拓扑排序了。但是为了直接使用拓扑排序，我们需要将图中有正反向的边去掉，还有一个点的自环去掉，这样就可以满足题目中图中的环只能往一个方向走并且环的长度>1。

713. 乘积小于K的子数组

因为数组中的数字都是正的，所以数组本身前后是具有单调性的。即如果使用双指针的话，如果前面的指针向前，那么后面的指针绝对不会向后的。

并且我们每一次找到以i为结尾的数字的最左边可以延伸到的数字，即这两个数字中所有子数组的乘积都，这样的话我们就可以在O(1)的时间内，通过ans += i - j + 1的方式得到子数组的数量。

447. 回旋镖的数量

如果我们暴力解的话，需要枚举三遍数组中的点。但是我们其实就是要得到到一个点i距离相同的两个点而已。所以我们就可以枚举一个中心点，然后计算其他所有点到这个点的距离，并且使用哈希表记录下不同距离下的点的个数。而我们需要的就是相同距离下的两个点，因此可以从距离同一个点相同距离的x个点中任意选取2个点，即求出n个点中2个点的排列数加入答案当中。

662. 二叉树最大宽度

为了计算树层的宽度，所以我们可以将二叉树转换成二叉堆，这样就可以给每一个节点一个编号了，因此我们也可以通过一层二叉堆的两个端点来计算一个树层的宽度了。

因此在二叉堆中会将二叉树中的null节点也计算上编号，所以这样就可能会浪费大量的空间（主要是编号可能会超级大），所以我们将每一层的节点的编号都从1开始计算。

本实例采用二分查找法查找特定关键字的元素。要求用户输入数组长度，也就是有序表的数据长度，并输入数组元素和査找的关键字。程序输出查找成功与否，以及成功时关键字在数组中的位置。例如，在有序表 11、13、18、 28、39、56、69、89、98、122 中査找关键字为 89 的元素。

(2) main() 函数作为程序的入口函数。程序代码如下：

 

 二分査找就是折半查找，其基本思想是：首先选取表中间位置的记录，将其关键字与给定关键字 key 进行比较，若相等，则査找成功；若 key 值比该关键字值大，则要找的元素一定在右子表中，则继续对右子表进行折半查找：若 key 值比该关键宇值小，则要找的元素一定在左子表中，继续对左子表进行折半査找。如此递推，直到査找成功或査找失败（或査找范围为 0）。
 

经验,知识,百科,个人图书馆,在线图书馆