【长期更新】LeetCode刷题笔记

自从上了大学，高中的算法竞赛的内容就逐渐地忘记了，到现在已经快退化到平均水平了。上了研也应该重新收拾一下，开始准备实习、找工作了。本篇博客长期更新，记录算法题的做题思路，只记录思路，不是特殊情况不记录代码。

LeetCode

25. K个一组翻转链表

题目链接

题面

给你一个链表，要求每k个链表为一组，将它们翻转。当剩余的链表不足k个时，不做任何操作。

输入：head = [1,2,3,4,5], k = 2
输出：[2,1,4,3,5]

思路

首先，可以再定义一个函数reverse(ListNode *head,ListNode *tail)用来转置head到tail的左闭右开区间的链表。接下来就是如何确定这些区间，我们可以用一个循环，位移指针来确定每次翻转的左右边界。

组内翻转是很容易的，但是翻转后还要考虑如何将各个组链接起来。注意这里有一个坑，就是翻转完第i组后，我们并不知道第i组的尾巴要连接到哪里，因为下一组也是需要翻转的。所以要等到第i+1组翻转完，才能确定尾巴并连接。这样就很自然地想到了递归。好像看代码更好理解。

代码

138. 随机链表的复制

题目链接

题面

提供一个链表，要求复制这个链表。主要注意的是，链表中还有一个random字段，指向随机一个链表中的节点。

输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]

思路

乍一看这题好像挺无脑的，直接遍历节点然后一个一个new过去就好了，但是注意到节点中还有一个random字段，是一个指针，指向链表中随机的节点。由于在建立第i个节点时，所有的j>i节点都是没有建立的，所以这个就不能使用显然的方法来做。

首先想到递归，但是递归的话新链表的random指针还是无法确定，遂放弃。

又想到在原链表的尾部追加一个新的链表，可以先将原链表的random指向原链表，然后再逐个向右移动n个单位，就指向新链表的对应元素，最后再断开链表即可。这个思路的正确性应该是没问题的，但是时间复杂度过高了。

最后是正解，将每个节点原地复制，即在自己的后面复制一个相同节点，这样新节点的random指针只需要平移一格即可。最后只需要遍历一遍，将第奇数和偶数个节点分到两个链表中，就成功解决了。

代码

146.LRU缓存

题目链接

题面

题面过于长且难懂，这里不放了，可以直接通过原链接看题。

思路

最初的思路就是使用一个链表来储存元素，每次将新的元素插到表头即可，同时访问的元素也从链表中取出并插入头部。但是这样会导致get操作的时间复杂度过大，为O(n)。

题解提到使用map来记录每个key对应的元素的地址，从而降低get操作的复杂度。如果引入这样的查询策略，就要将链表改为单向链表，因为删除当前节点还需要获得上一个节点的指针。这是一个很典型的时间换空间的策略。

顺便提一嘴，map、set的查询、插入、删除的时间复杂度均为$O(logn)$。

代码

101. 对称二叉树

题目链接

题面

给你一个二叉树，判断其是否轴对称。

输入：root = [1,2,2,3,4,4,3]
输出：true

思路

这题看似简单，但是有点小坑。乍一看我是想寻找中序遍历、后序遍历、先序遍历能不能用上，想了一下，应该只要根节点的左右子树的中序遍历是相反的就可以了。确实，如果这棵树是对称的，那么左右字数的中序遍历就是相反的，但是后者并不是前者的充分条件，因为还要考虑节点值相同的情况，如下图：

所以只能放弃先序遍历，使用双指针递归或者迭代的方法来做。其实题解中那么多方法，有用递归的，也有用迭代的，本质上都是搜索，只不过是深度优先还是广度优先的区别罢了。

108. 将有序数组转化为二叉树

题目链接

题面

提供一个严格递增的数组，要求将其转换成二叉搜索树。

输入：nums = [-10,-3,0,5,9]
输出：[0,-3,9,-10,null,5]
解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案：

思路

刚拿到这题，想到的就是如何构造一个二叉搜索树。但是突然想到，不管原始的数据输入是怎么样的，都可以构造成二叉搜索树，这题给了一个数组严格递增的条件，肯定有更好的解法。

查看题解，看到一条重要性质：二叉搜索树的中序遍历是严格递增的，又联想到题目给的数组也是严格递增的，所以可以考虑直接从数组入手。使用二分法，每次选择数组的中间元素，将其作为根节点，不断递归。当数组长度是偶数时，不管选择偏左的节点还是偏右的节点都是可行的。

代码

98.验证二叉搜索树

题目链接

题面

提供一个二叉树，要求检查其是否为二叉搜索树。

输入：root = [2,1,3]
输出：true

思路

最开始的思路，直接使用递归，对于当前节点只需要左儿子小于根，右儿子大于根即可，然后以左右儿子为根继续判断。实际上这样会有问题，例如下面这棵树：

.svg)

所以不能仅在局部进行判断，我们还需要在函数内维护一个全局的允许区间[l,r]，并在每次递归的时候设置新的允许区间。总觉得这个方法有一些不那么优雅，毕竟要求我们预先知道值的范围。

另一个方法还是利用了二叉搜索树的中序遍历严格递增这个性质，只需要获得二叉树的中序遍历，然后判断是否严格递增即可。

114.二叉树展开为链表

题目链接

题面

给定一个二叉树，将其按照前序遍历转化为链表。转化后的链表要使用原来的节点，左子树全部为空，右子树为下一个节点。

思路

一个非常弱智的做法是先进行前序遍历并记录节点顺序，然后再将其链接，但是这样空间复杂度为O(n)。我想到的做法是在前序遍历的时候顺便修改树的结构，当然了，因为在递归的时候是需要修改左右子树的，所以需要使用局部变量临时记录一下。这个算法看似优化了，但实际上空间复杂度还是要来到O(n)，主要是因为递归时需要使用栈的空间，具体空间取决于树的高度。

最优的做法是O(1)的复杂度，直接在树上进行修改。如上图节点2，我们可以将其作为1的右子树，然后将节点5连接到节点4（即2子树的“最右边”）的右子树，依此循环即可。这个算法可能需要一点洞察力和灵性，之后在做算法题的时候也可以多从几何直观来入手。

437.路径总和III

题目链接

题面

给定一个二叉树的根节点 root ，和一个整数 targetSum，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。

路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

输入：root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
输出：3
解释：和等于 8 的路径有 3 条，如图所示。

思路

涉及到连续一个序列的和，很自然的就想到使用前缀和，所以首先进行一次前序遍历，维护每个节点到根节点的路径的和。

接下来就是判断有多少条路径之和为targetSum，最朴素的想法就是使用$O(n^2)$的算法来枚举，但是这样效率可能有点低。题解中使用到map数据结构，记录前缀和为x的路径有多少条，这样就可以用$O(n)$的复杂度来计算出路径的条数。

实际上，如果按上面说的那样分两次进行处理，会重复计算很多路径，而且不符合路径“只能向下走”的特定。所以我们需要在遍历的过程中实时地维护map，使得map只记录当前节点到根节点的路径条数。

这题和之前遇到的某些题很类似，给我的启发是，当遇到求解“和为sum的路径条数”问题时，使用哈希可以更快地解决问题。

代码

236.二叉树的最近公共祖先

题目链接

题面

给定一个二叉树，以及树上两个节点，求其最近公共祖先（LCA）。

思路

很经典的一个问题，在洛谷中这题是一个模板题，需要使用倍增算法来加速求解。但是LeetCode只要求求一对节点的LCA，所以可以直接用递归的方法来求解。

递归解法

从根节点向下遍历，令函数的返回值为与这对节点“关系最大”的节点，即：有公共祖先就返回公共祖先，有p就返回p，有q就返回q，两者都没有就返回nullptr。对于每棵子树的根节点root，有以下几种情况：

• p和q都在这棵子树上，返回root；
• p在子树上，q不在，返回p；反之同理；
• p、q都不在，返回nullptr。

我们肯定无法在当前这一层函数直接知道哪些节点在子树上，所以使用递归，分别处理左右子树的情况。

Talk is cheap, show me the code:

递归解法代码

倍增求法

先不考虑最近这个条件，单是求公共祖先的问题，在树的路径上是有单调性的，所以可以使用类似二分的思想。但是树上是没有办法进行二分的，所以采用倍增的思想。

倍增求LCA的难度主要来源于预处理，在计算前需要计算各个节点的深度，以及父节点信息。所以倍增算法在加速计算的同时，会消耗较多的空间，LeetCode的这题只需要求一对节点的LCA，所以没有必要使用倍增。但是本着复习的原则，还是把算法也回顾一下。

洛谷P3379

倍增求LCA

代码是洛谷风格的输入输出，这里面的log预处理，前向星存图都比较值得复习。

124.二叉树的最大路径和

题目链接

题面

二叉树中的 路径 被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。

路径和 是路径中各节点值的总和。

给你一个二叉树的根节点 root ，返回其 最大路径和 。

思路

题目描述的略复杂。这题其实和最大子序列和类似，都是判断连续的一段序列之和的最大值，所以这题也可以用到类似动态规划的思想。但是由于是在树上，所以直接维护最大路径和是不可行的，以为这里路径是不可以分岔的，不满足动态规划的无后效性原则。

但是这个路径是可以有拐弯的，即从某个节点的左节点上来，经过这个节点，再从右节点下去。所以，我们可以维护以root为起点的不带拐弯的路径，这个是很容易的，利用子序列和最大值问题的思想就可以解决。然后再判断从哪个结点发生拐弯即可（两个过程可以只用一个深度优先搜索达到）。

代码

994. 腐烂的橘子

题目链接

题面

一个矩阵，里面有新鲜的橘子和腐烂的橘子，腐烂的橘子每一个单位时间会传染给邻接的新鲜橘子，问传染完所有橘子需要多少时间。如果有橘子永远不会被传染，就返回-1。

思路

开始认为使用模拟去做肯定不太可行，于是想对于每个橘子，判断离其最近的腐烂橘子的距离，然后再取这些距离的最大值。后来发现这个复杂度有可能会更高，取决于什么橘子更多。

题解做法是使用多源广度优先搜索，思想比较简单，其实望文生义就可以知道大概做法了，这里不再赘述了。

22.括号生成

题目链接

题面

给定一个正整数n，要求给出含有n个括号的所有有效的配对。

输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]

思路

我的思路，最开始是试图从括号的嵌套中找出一些数学的关系。经过十几分钟的思考，好像真给我找到了，这个括号的配对实际上可以看成一棵树的构建过程，先想象有一个虚无的0号节点，代表空字符串。然后当i=1时，我们将1号节点作为0号节点的儿子。当i=2时，我们就去枚举是将2号节点作为1号还是0号的儿子，以此类推。当i=n的时候，就使用另一个递归函数来构造这个字符串。

看似问题解决了，但是没有这么简单，树的儿子在我们的储存里是有先后顺序的，而括号没有，所以这个方法会产生很多重复的字符串，我们还得使用一个map来判重。这么处理过后，算法的正确性算是对了，但是不管是时间还是空间都非常的拉跨，于是就参考了题解。

看了题解，豁然开朗，使用搜索的策略是没有问题的，但搜索的对象上不太对。这里引用一下这篇题解的图：


正解是直接去匹配字符串里下一个的左右括号的可能性，而我去枚举括号的嵌套关系了。

79.单词搜索

题目链接

题面

在一个含有大小写字符的矩阵中搜索指定的字符串，字符之间只要上下左右挨在一起就算是连续的。

思路

非常简单的搜索题，记录这题主要是想记录一下剪枝的思路。首先，“把尝试的字符全部置空”肯定是不行的，很容易就可以找出反例。一个表现非常优秀的剪枝思路是，记录字符的出现次数，当单词中某个字符的出现次数不足其在单词中出现的次数时，就直接返回false。另外，当结尾字符的出现次数较少时，可以考虑倒过来搜索，可能会有更高的效率。

131.分割回文字符串

题目链接

题面

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文串 。返回 s 所有可能的分割方案。

思路

暴力枚举分割点，当然，分割的前提是子串为回文串。注意到枚举的过程中，可能会重复判断子串是否为回文串，那么可以用记忆化搜索，或者使用动态规划来预处理，动态规划的转移方程为：

$$f[i][j] = \begin{cases} true, \ &i\ge j \\ f[i+1][j-1]\&\&s[i]==s[j], \ &i<j \end{cases}$$

发现评论区一个使用python+动态规划做的，感觉思路也很巧妙，但是可惜C++并不适合做这种需要记录解集的，如果是记录解的个数，可以尝试一下：

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        dp = [[[]]]
        # dp[i]表示s[:i]所有可能的分割方案
        for i in range(1, len(s) + 1):
            dp.append([])
            for j in range(i):
                tmp = s[j:i]
                if tmp == tmp[::-1]:
                    dp[-1].extend(l + [tmp] for l in dp[j])
        return dp[-1]

51.N皇后

题目链接

题面

要求在一个n*n的棋盘上放置皇后，皇后所在的那一行、那一列、主对角线、副对角线都不能再放新的棋子，要求给出所有可能的情况。

输入：n = 4
输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]

思路

朴素思路：按行搜索，观察到主对角线的行列之差为定值，副对角线的行列之和为定值，使用map来记录列、主对角线、副对角线是否放置棋子（这里直接用数组也可以，但是需要处理负数的情况）。提交之后代码正确，但是时间和空间比较拉胯，开始分析代码。

首先，发现将用于记录答案的ans从类的成员移到函数的引用参数可以略微加快速度。

然后，查看题解，给出一种使用整数的比特位来记录的方案。将列、主对角线、副对角线使用三个整数来记录，进入下一行的递归时，主对角线的值左移一位，副对角线的的值右移一位，就可以很方便地判断该位置是否能够放置。

尝试了一下，发现答案输出始终是空的，检查后发现是运算优先级的问题：

if((col&bit==0)&&(line1&bit==0)&&(line2&bit==0)) // 错误 ==运算的优先级高于&运算
if(((col&bit)==0)&&((line1&bit)==0)&&((line2&bit)==0)) // 正确

官解给的思路更加简洁，在每层递归中使用一个新的值来记录可用的位置，然后使用lowbit操作每次只取可用的那一位，可以说是十分巧妙了。部分代码如下：

int availablePositions = ((1 << n) - 1) & (~(columns | diagonals1 | diagonals2));
while (availablePositions != 0) {
    int position = availablePositions & (-availablePositions);
    availablePositions = availablePositions & (availablePositions - 1);
    // ...
}

25. 搜索插入位置

题目链接

题面

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

输入: nums = [1,3,5,6], target = 5
输出: 2

思路

二分法的思路非常简单了，主要是回忆一下代码怎么写：

int searchInsert(vector<int>& nums, int target) {
    int l=0,r=nums.size()-1;
    int ans=nums.size();
    while(l<=r) // 闭区间搜索
    {
        int mid = (l+r)/2; // 向下取整
        if(target<=nums[mid]) 
        {
            ans = mid; // 实时记录答案
            r = mid -1; // 区间中点始终不取
        }else if(target>nums[mid]) 
        {
            l = mid+1; // 区间中点始终不取
        }
    }
    return ans;
}

33.搜索旋转排序数组

题目链接

题面

最初有一个升序数组，将其前k个移动到尾部后，要求在数组中以$O(\log n)$的时间复杂度寻找出目标target。

输入：nums = [4,5,6,7,0,1,2], target = 0
输出：4

思路

可以观察一下旋转之后的数组，实际上是由两个递增的数组拼到一起的，并且中间有且仅有一个递减的位置，这个递减的位置就是两个递增数组的分界线。可以考虑先查找出这个分界线，再分两次，分别二分搜索两个递减数组。

朴素地遍历是不可行的，时间复杂度会到$O(n)$。观察发现左边数组的元素永远比右边的数组大，所以可以考虑用二分法搜索出中间这个分界线。

这里仅给出分界线的搜索算法，最需要注意的就是，题目保证了数组一定是旋转过的，所以搜索范围应该是的[0,n-1]，并且11、14行的搜索条件应该覆盖所有情况，否则将进入死循环：

int l=0, r = n-2;
int br=0;
while(l<=r)
{
	int mid = (l+r)>>1;
	if(nums[mid+1]<nums[mid])
	{
		br = mid;
         break;
    }
    if(nums[mid]>=nums[l])
    {
    	l = mid+1;
    } else if(nums[mid]<nums[r])
    {
    	r = mid-1;
    }
}

4.寻找两个正序数组的中位数

题目链接

题面

给出两个严格递增的数组，要求求出两个数组合并之后的中位数。

输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2

思路1

这是官解的做法之一，找中位数，实际上就是找两个数组中排位为$\frac{m+n}{2}$或$\frac{m+n}{2}+1$的数，我们设这个数的排位为k。然后使用二分法，去判断两个数组的第$\frac{k}{2}-1$个值，可以分为以下三种情况（引用官方题解的话）：

因此我们可以归纳出三种情况：

• 如果 A[k/2−1]<B[k/2−1]，则比 A[k/2−1] 小的数最多只有 A 的前 k/2−1 个数和 B 的前 k/2−1 个数，即比 A[k/2−1] 小的数最多只有 k−2 个，因此 A[k/2−1] 不可能是第 k 个数，A[0] 到 A[k/2−1] 也都不可能是第 k 个数，可以全部排除。

• 如果 A[k/2−1]>B[k/2−1]，则可以排除 B[0] 到 B[k/2−1]。

• 如果 A[k/2−1]=B[k/2−1]，则可以归入第一种情况处理。

作者：力扣官方题解
链接：https://leetcode.cn/problems/median-of-two-sorted-arrays/solutions/258842/xun-zhao-liang-ge-you-xu-shu-zu-de-zhong-wei-s-114/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

本质上，这个思路是从朴素的遍历算法演变出的。朴素的算法每次只排除一个值，而这个算法每次可以排除$\frac{k}{2}$个值，所以效率更高。

这个思路更有一般性，比如，“在c个有序数组中，找出第k大元素”，应该只要将这个算法稍加改进就可以了。

思路2

正难则反。想一想中位数有什么性质，发现中位数是可以将一个有序数组分成两个相等的部分的，那么就从这个思路出发。假如我在A数组中选定一个数A[i]，作为左边半部分的上边界，那么我可以用二分法在B数组中找到满足B[j]<=A[i]的值，然后判断i+j是不是m+n的一半。不难发现“在A数组中选定一个数A[i]”的过程也是单调的，所以实际上问题就使用两个二分法来分割数组。

想法很美好，但写一半发现上面这个做法不完全对，因为没法保证左半部分的上界在A中，那么就有可能找不到解，还需要交换A、B再找一次。

但是“均分数组”这个思路是没问题的，正解是二分法选出A[i]，那么既然我希望找到一个j使得i+j=(m+n+1)/2成立，那么我直接令j=(m+n+1)/2-i，然后判断这个分割是否是符合我们想法的，即左半部分最大值小于右边部分最小值。

代码， 改代码基于LeetCode官解修改。

84.柱状图中的最大矩形

题目链接

题面

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。求在该柱状图中，能够勾勒出来的矩形的最大面积。

思路

暴力解法，想都没想就pass了。考虑到要维护最矮的那个柱子，于是就想到使用动态规划，但是动态规划的时间和空间代价都是$O(n^2)$，所以也被pass了。结合这题所给的提示，想起了《接雨水》这题，于是考虑使用单调栈来维护一个“短板”，然后在维护这个单调站栈的最大值的过程中去更新最大值。

但是上面这个做法显然是不太对的，虽然这题确实用到单调栈，但是最大值的出现并不一定是在单调的柱状图中的。于是只能求助题解。

题解的思路还是比较清晰的，对于每一根柱子，我们可以想想，如果这根柱子就是矩形的高，也就是“短板”，那么它的左右区间最大可以扩张到多大。其实只要上面这句话出来，思路就很清晰了。对于左区间，可以用一个单调栈来维护，这样可以计算出再这根柱子左边的离这根柱子最近且小于它的柱子的序号，右区间同理。最后再枚举，谁作为这个短板时答案可以最大即可。

需要注意的是，我们需要为最左边和最右边放置一个高度为无限小“哨兵”，用于防止单调栈为空的情况。另外，上述提到的区间左右都是开区间，所以最终计算面积时，宽度为right[i] - left[i] - 1。

题解还做了另一个优化，即只需要一次遍历就可以同时求出左右区间。做法是在求左区间的过程中，每当一个栈的元素被弹出，就可以把这个元素的右区间记为当前新元素的索引。文字的表述十分苍白，可以直接看代码。

单调栈常规代码 单调栈常数优化代码

虽然常数优化后，右区间只能求出“小于等于”的那根柱子，但是这个实际上不影响题解。因为当有若干根相同柱子i,i+1...,j连在一起时，虽然第i根柱子会求出错误的答案，但是最终答案会通过最右边的柱子j来更新。

215.*数组中的第k大元素

题目链接

题面

望文生义，给定一个数组，要求计算其中的第k大元素，时间复杂度要控制在$O(n)$以内。

输入: [3,2,1,5,6,4], k = 2
输出: 5

思路1

方法之一是使用堆排序，堆排序的时间复杂度实际上为$O(n+k\log n)$，渐进时间复杂度为$O(n\log n)$，虽然不符合题目要求，但是实际上是可以做出这题的。为了顺便复习堆排序，所以记录一下这个思路。

堆排序首先是堆的建立，如果采用逐个插入的方法来建堆，那么时间复杂度会达到$O(n\log n)$，而使用原地建堆的方法，时间复杂度可以降低到$O(n)$。建堆的过程，是从下到上，对每个非叶子结点进行遍历，遍历的目的是令其与每个最大的子节点比较，如果不满足大顶堆的性质就交换（注意，遍历的过程中，如果发生了交换，就要继续往深遍历）。

建完堆之后，就获得了一个大顶堆，对堆进行k-1次删除就可以获得结果。

堆排序求第k大元素

思路2

方法之二是使用快速排序。由于快排的特点，在对当前区间进行快排的时候，会形成两个区间，其中左边区间的元素全部小于右边区间，那么在寻找第k大元素时，我们就可以只对其中一个区间进行排序。因此快排的时间复杂度可以降到$O(n)$。

快排的具体写法，有三种，可以参考：[排序算法] 快速排序 (C++) (含三种写法)

但是，这题有个特别坑的地方，就是最后一组数据的数组里所有的值都是相等的。在这种情况下，使用普通的快排来进行排序，会导致每次区间划分不平均，即原先为[l,r]的区间在下一层递归中只能被划分成[l+1,r]，导致复杂度退化到$O(n^2)$。

题解的做法比较巧妙，是对左右指针法的一种改变，代码如下：

    int quickselect(vector<int> &nums, int l, int r, int k) {
        if (l == r)
            return nums[k];
        int partition = nums[l], i = l - 1, j = r + 1;
        while (i < j) {
            do i++; while (nums[i] < partition);
            do j--; while (nums[j] > partition);
            if (i < j)
                swap(nums[i], nums[j]);
        }
        if (k <= j)return quickselect(nums, l, j, k);
        else return quickselect(nums, j + 1, r, k);
    }

作者：力扣官方题解
链接：https://leetcode.cn/problems/kth-largest-element-in-an-array/solutions/307351/shu-zu-zhong-de-di-kge-zui-da-yuan-su-by-leetcod-2/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

这种写法可以保证即使所有元素相同，i和j最多同时进一位，它们更容易在中间相遇，不会出现划分不平均的情况。但是这个写法非常的不自然，不太好理解。

我对左右指针法进行了一点改变（其实和官解和类似，但是比较好理解）。既然不希望一次性进太多位，那么就把与枢轴判断的两个while循环中改成小于等于/大于等于。但这样会带来一个问题，当i==j时，这个值不会与枢轴进行判断。于是进行如下调整：原先我们是把$[1,i]$看成左边的区间，$[j,n]$看成是右边的区间，现在我们改一下，把$[1,i)$看成左区间，$(j,n]$看成右区间，于是代码改成如下的形式：

int quickselect(vector<int>& nums, int l, int r, int k) {
    if (l == r)
        return nums[k];
    int partition = nums[l], i = l+1 , j = r ; // nums[l]是枢轴，所以i = l+1
    while (i <= j) { // 退出条件发生改变
        while (i<=j&&nums[j] > partition)j--;
        while (i<=j&&nums[i] < partition)i++;
        if (i <= j)
        {
            swap(nums[i], nums[j]);
            i++;
            j--;
        }
    }
    swap(nums[l],nums[j]);
    if (k <= j)return quickselect(nums, l, j, k);
    else return quickselect(nums, j + 1, r, k);
}

这就是改变后的代码。

可以对快速排序和快速选择进行一个对比。我们知道，快排的稳定性主要就是来自两个while循环的<=或>=中的等号，但是就是这个等号，可能会导致快速选择算法退化，所以我们要对其进行调整。

那么为什么不直接对快排算法进行调整，以防其退化呢？很显然，快排是否退化，主要取决于枢轴的选择和数据的分布，按照上面的方法仅可以防止所有数据相同情况下的退化，但是不能防止其他更极端条件（如有序数据）的退化。为了这一点的性能牺牲稳定性，是不太能接受的。

LeetCode这题出这个数据是有点过分了，即使使用官解的代码，似乎也不能防止算法的退化，除非使用随机枢轴。

347.前k个高频元素

题目链接

题面

给定一个数组，要求输出其出现频率前k个的元素，返回的顺序不受限制。

输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]

思路

这题和上一题有异曲同工之处，稍微有点不一样的是，需要求前k个，而不是第k个。首先是记录元素的出现次数，这题元素最大可能达到50000，所以使用map来存会比较省内存。

然后就是排序，和上一题一样，可以使用堆排序，也可以使用快速排序。个人感觉堆排序和快排的时间好像差不多，但是官解说快排达到最慢时间的概率很低，所以渐进时间复杂度为$O(n)$。

快排在上一题已经讨论过了，这里主要说一下堆排序。看到前k个高频元素，很容易就想到建立大根堆，然后弹出前k个元素。但是似乎可以使用小根堆，建立一个元素个数最多为k的小跟堆，当新入元素小于堆顶元素时就直接返回，不用进行插入了。这个方法可以稍微优化，但是当k接近n时，性能与大根堆没有区别。

代码.txt

763.划分字母区间

题目链接

题面

给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。

注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s 。

返回一个表示每个字符串片段的长度的列表。

输入：s = "ababcbacadefegdehijhklij"
输出：[9,7,8]
解释：
划分结果为 "ababcbaca"、"defegde"、"hijhklij" 。
每个字母最多出现在一个片段中。
像 "ababcbacadefegde", "hijhklij" 这样的划分是错误的，因为划分的片段数较少。

思路

题目就是希望将字符串尽可能分割多段，并使一个字母不能出现在多个片段。很自然地想到，记录每个字母出现的左右区间，这个区间内是不能分割的，所以再用一个数组来存那些位置是可以被分割的。

这个做法是对的，但是做了一些无用功，多花了一些内存，题解的思路更清晰。

官解只记录当前字母的最后一次出现位置last[c]，然后直接进行区间划分。遍历到当前字母c时，就更新区间尾部为last[c]，当遍历到区间尾部时，就说明划分完成，将当前区间储存。

官解

300.最长递增子序列

题目链接

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

思路

这是一道很经典的动态规划题，简单的解法是使用$O(n^2)$的时间复杂度，进阶一点的解法是用二分来将时间复杂度优化至$O(n\log n)$。这里主要记录进阶解法。

进阶解法就是在简单解法的基础上，将向前寻找子序列的过程使用二分来简化一下。具体做法是，维护一个数组d[i]，表示长度为i的子序列的尾元素最短是多少，不难证明这个d[i]数组是单调递增的。于是对于当前元素num[i]，可以使用二分法来寻找小于num[i]的d[j]，并更新d[j+1]。

这个算法还是挺有意思的，首先d[i]这个数组没有时间这个维度，它仅仅记录当前时刻的最优值，其次就是对于当前元素num[i]，居然一定可以找到一个更新的值，因为如果小于所有的d[i]，就更新d[1]，如果大于所有的d[i]，就更新d[++len]。

官解

152.乘积最大子数组

题目链接

题面

给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续 子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。

输入: nums = [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。

思路

这题跟和最大的子数组有一点类似，但是需要注意的是，直接使用单个数组来维护最大乘积是不可行的，因为乘积有可能会从负值跳到正值。

官解做法是分别使用两个数组来维护乘积最大值和乘积最小值，这样就克服了符号的问题，实际上两个数组都可以通过状态压缩，变成单个变量，从而节约空间复杂度。

另一个很巧妙的解法是，正向遍历一遍，再反向遍历一遍。最开始我就是用这个方法，但是想不到使用反向遍历。思路就是首先把0看成分割数组的标志，然后每一串连续的非零元素中都可能含有乘积最大的子数组。考虑：

$$a_1,a_2,a_3$$

那么答案只有可能是

$$a_1*a_2*a_3\\ a_1*a_2\\ a_2*a_3$$

其中的一个。

其中$a_2$可以是多个元素的乘积，所以这个解法也是可行的。

官解

解法2 (来自Conqueror的题解)

32.最长有效括号

题目链接

题面

给你一个只包含 ( 和 ) 的字符串，找出最长有效（格式正确且连续）括号子串的长度。

输入：s = "(()"
输出：2
解释：最长有效括号子串是 "()"

思路1

首先看到这题是“动态规划”栏目下的题，所以可以考虑使用动态规划来求解。最开始想到的是区间DP，但是数据规模显然不允许我们使用$O(n^3)$的算法去解，思考了一会，只能求助官解。

设$dp[i]$为以$i$结尾的最长有效括号子串的长度，那么状态转移方程也是比较清晰的：

$$dp[i]= \begin{cases} dp[i-2]+2, \quad if \ s[i]==')'\ and \ s[i-1]=='(',\\ dp[i-1]+dp[i-1-dp[i-1]-1]+2, \quad if \ s[i]==')' \ and\ s[i-1]==')' \ and \ s[i-1-dp[i-1]]=='(' \end{cases}$$

其他情况下，dp数组的值均为0。这题动态规划解法的妙处就是将dp[i-1]用上了，因为其包含了有效长度的信息，不需要我们再去遍历先前的数组，判断是否合法。

解法1

思路2

看到这种括号配对，就可以考虑使用栈来解决。与以往不同的事，这次需要记录子串的长度，所以栈中记录的不能是括号，而应该是下标。当遇到左括号时，直接将其入栈；遇到右括号就弹栈，如果弹完栈中还有元素，就说明栈顶是先前没有被匹配的元素，那么可以使用这个下标更新一次答案。

为了避免“右括号偏多”的情况下，将栈弹空，需要在遍历前先推入一个-1。

解法

思路3

和我最开始的思路挺像的，但是我还差了一步。只要用left和right变量来记录左右括号的个数，从左往右遍历，当左右均为0时就更新一次答案，而当右括号个数比左括号多时，此时不可能匹配上，就直接将两个变量置零，开启新的遍历。

但是这样会有个问题，就是像(()、()(()这样的情况无法被更新，那该怎么做？可以参考152.乘积最大子数组的解法，从右往左再遍历一次即可。

感觉这种做法思路是最清晰的，也是最省空间的。

解法3

72.编辑距离

题目链接

题面

给定两个单词，可以有三种操作，分别是：插入一个字符，删除一个字符，替换一个字符。输出将两个字符串变得相等的最少操作次数。

输入：word1 = "horse", word2 = "ros"
输出：3
解释：
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')

思路

和最长公共子序列有点像。仔细分析一下这三个操作，实际上插入字符和删除字符是等价的，对第一个字符串插入字符，就是对第二个字符串删除字符。设$dp[i][j]$为word1的前i个和word2的前j个字符相互转化的最少操作数。如果第word1[i]和word2[j]相等，就直接从dp[i-1][j-1]转移，否则可以从下面三个状态转移过来：

dp[i][j] = min(
    dp[i][j-1]+1 // 插入
    dp[i-1][j]+1 //删除
    dp[i-1][j-1] // 替换
);

其实看着有点复杂，但是这个状态转移方程还是很清晰的。就是边界情况需要额外初始化一下。

代码

169.多数元素

题目链接

题面

给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

输入：nums = [2,2,1,1,1,2,2]
输出：2

思路

思路有很多，其中最清奇的是随机算法，每次随便从中取一个元素，然后判断它是不是多数元素。另一个是Boyer-Moore算法，代码很简单，但是用自然语言描述的话可能会难懂。简而言之就是“同归于尽消杀法”：

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int candidate = -1;
        int count = 0;
        for (int num : nums) {
            if (num == candidate)
                ++count;
            else if (--count < 0) {
                candidate = num;
                count = 1;
            }
        }
        return candidate;
    }
};
作者：力扣官方题解
链接：https://leetcode.cn/problems/majority-element/solutions/146074/duo-shu-yuan-su-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

这个算法似乎只适合这题，因为这题保证了一定会有超过一半的多数元素，在其他情况下，例如：1 4 4 4 4 1 1 3 3 3这种情况就找不到正确解了。

31.下一个排列

题目链接

题面

给定一个数组，要求原地生成其下一个全排列（按字典序）。

输入：nums = [1,2,3]
输出：[1,3,2]

思路

貌似思路很固定，可以看成是生成全排列的一种固定算法。下面是题解的算法流程：

1. 从后向前 查找第一个 相邻升序 的元素对 (i,j)，满足 A[i] < A[j]。此时 [j,end) 必然是降序
2. 在 [j,end) 从后向前 查找第一个满足 A[i] < A[k] 的 k。A[i]、A[k] 分别就是上文所说的「小数」、「大数」
3. 将 A[i] 与 A[k] 交换
4. 可以断定这时 [j,end) 必然是降序，逆置 [j,end)，使其升序
5. 如果在步骤 1 找不到符合的相邻元素对，说明当前 [begin,end) 为一个降序顺序，则直接跳到步骤 4

可以尝试发现一下规律，给定一个数组，我们需要生成更大的且尽可能小的全排列，那么应该尽量从尾部入手，因为改变头部会较大地改变字典序的位置。更具体地，入手的位置就是尾部的下降序列。为什么呢？因为如果有上升的序列，那么就说明这个上升的地方可以产生一个新的全排列。

所以首先是要找到这个尾部的下降序列 [j,end)，然后我们肯定是希望生成的下一个全排列尽量小，所以选择比A[i]大且尽可能小的元素，与A[i]置换，并对尾部的下降序列求逆序。

代码

287.寻找重复数

题目链接

题面

给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。找出这个重复的数字。

输入：nums = [1,3,4,2,2]
输出：2

思路1

想用特异元素那题的异或法来解，然而应该是解不出来的，正解应该是二分法。

题目已经明确了整数的范围在[1,n]之间，可以维护一个cnt[i]，表示小于等于i的元素个数。那么假设这个重复的数字是target，对于大于等于target的元素，有$cnt[i]>i$，而对于小于target的元素，则有$cnt[i]==i$。所以这个规律是有单调性的，只要找到最小的使得$cnt[i]>i$成立的元素i即可。

具体地，二分法枚举i，并使用一次遍历来统计cnt[i]（实际上只用一个变量就行了，不需要数组），时间复杂度为$O(n\log n)$。

思路1代码

思路2

关注点还是在整数的范围在[1,n]之间。那么可以把这个数组看成链表，数组的值就是链表的next指针。由于题目告诉我们一定存在重复的整数，那么就是环形链表，可以使用Floyd判圈算法来求解，我们只要找到进入环的那个结点即可。

但是问题是，Floyd判圈算法终止时，快慢指针停留的位置只能保证在环内，要如何找到入环的节点呢？

先假设环的长度为$P$，从起点到环的入口的长度为$m$，相遇时慢指针走了$n$步。快慢指针相遇时，快指针走了$2n$步，那么多出来的$n$步全在环里循环了，即$n \%P==0$。另一方面，快指针在环中行进的距离比慢指针多$m$步（因为慢指针多花了$m$步在环外）。那么给慢指针补上$m$步，它就刚刚好到了入环元素处了。

那么如何知道这个$m$呢？只需要在起点放个新的元素，让它与慢指针一起走，直到相遇即可。

思路2代码

环形链表的数学建模

趁着吃饭的时间思考了一下，对于这样的环形链表，似乎可以将其抽象成一个代数系统。因为在$\mod c$意义下，指针在环里走$c$步，刚好就回到原点。但是由于环前面还有$m$个元素，不好表达，我们可以直接省略慢指针入环之前的步骤。即当慢指针入环的第一个元素时，才进行数学建模。

先约定，环的第一个元素为$L_0$，第二个元素为$L_1$，最后一个元素为$L_{P-1}$。入环前的最后一个元素为$L_{-1}$，那么链表起点元素为$L_{-m}$。最开始时，慢指针处于环的起点，我们令其为$0$，那么快指针为$m\mod P$：

此时继续进行快慢指针的迭代，假设$s$步后两者指向同一个元素，则有可以解出$s$：

$$m+2s\equiv s \mod P\\ s \equiv -m \mod P$$

此时快慢指针的位置均为：

$$-m \mod P$$

那么我们令其向前移动$m\mod P$步即可到重回0的位置。

274.H指数

题目链接

题面

给你一个整数数组 citations ，其中 citations[i] 表示研究者的第 i 篇论文被引用的次数。计算并返回该研究者的 h 指数。

根据维基百科上 h 指数的定义：h 代表“高引用次数” ，一名科研人员的 h 指数 是指他（她）至少发表了 h 篇论文，并且 至少 有 h 篇论文被引用次数大于等于 h 。如果 h 有多种可能的值，h 指数 是其中最大的那个。

输入：citations = [3,0,6,1,5]
输出：3 
解释：给定数组表示研究者总共有 5 篇论文，每篇论文相应的被引用了 3, 0, 6, 1, 5 次。
     由于研究者有 3 篇论文每篇 至少 被引用了 3 次，其余两篇论文每篇被引用 不多于 3 次，所以她的 h 指数是 3。

思路

很显然解是有单调性的，那么当然可以用二分做。但是记录这题主要是想记录排序的做法，可以从大到小排序然后根据下标来递增h，这样的时间复杂度是$O(n\log n)$。由于h一定不会超过n，所以可以考虑桶排序，进一步优化时间复杂度，可以把引用次数超过n的全部计入引用次数为n的中，从而节约空间。

代码

42.*接雨水

题目链接

题面

给一个数组，表示柱子的高度，要求求出这些柱子之间能接的雨水的最大值。

思路

这题算是很经典了，一共有三种做法。

单调栈做法

维护一个单调下降的栈，当新来的柱子高度破坏了单调性时，就把过于低的栈顶元素出栈。注意，每当有元素出栈时，就相当于这个元素的高度已经被淹没了：由于单调栈的性质，左边一定有比他高的，又由于右边有新元素，所以右边也有比它高的。所以在每次出栈时，我们都可以更新一次答案。这个答案是按行来计算的。

每次更新答案的公式为：

$$ans += cur\_height*cur\_width\\ cur\_height = \min(height[i]-height[st.top()])-height[last\_top]\\ cur\_width = i-st.top()-1$$

需要注意两点，一是高度的计算，是两边端点取最小值，并减去刚刚出栈的元素；二是，当新元素将栈清空时，左边没有柱子可以接水了，不能更新答案，需要做特殊处理。

单调栈代码

动态规划

一言以蔽之，用一个数组维护$i$左边的最大值，再用一个数组维护$i$右边的最大值，然后按列更新答案。

$$ans += \min(leftMax[i],rightMax[i])-height[i]$$

双指针

双指针实质上是对动态规划的空间优化。由于动态规划的两个数组从头到尾都只用了一次，所以可以考虑将其两者都转化为单个变量。很容易想到压缩左边数组的方法，因为是从左到右遍历的，所以几乎不用做什么改动，一个变量重复使用即可，但现在问题是右边如何压缩。

我们可以直接用双指针$left$和$right$来更新$leftMax$和$rightMax$两个变量。可以观察一下上面这个动态规划的答案更新式，每次都是取左右中的较小值。假如这一次的答案更新，左边的柱子更矮，那么我们肯定希望下一次更新左柱子的值，因为右柱子的值较大，更新了右边也不会让$rightMax$变小，反之同理。

这个思路真的很难理解，下面贴一下官解评论区其他人的理解：

来自zwjason的评论

// 双指针解法
// 注意到动态规划中
// 对于位置 i 的接水量取决于 leftMax 和 rightMax 中的较小者
// 所以我们不必真的知道较大者是谁
// 只要知道较小者是谁就可以了 

// 初始化 left = 0, right = n-1, leftMax = 0, rightMax = 0
// 注意到对于位置 left 来说, leftMax 是真正意义上的左侧最大值, 而 rightMax 不是真的右侧最大值
// 而对于位置 right 来说, rightMax 是真正意义上的右侧最大值, 而 leftMax 不是真的左侧最大值

// 从左往右扫描
// 1. 使用 height[left] 和 height[right] 更新 leftMax, rightMax
// 2. 若 height[left] < height[right], 则说明对于位置 left 来说, 
//     leftMax 一定小于其右侧真正意义上的最大值
//     因为连当前右侧的局部最大值 rightMax 都比不过, 更比不过右侧真正意义上的最大值
//     而我们又不需要真的知道右侧真正意义上的最大值
// 3. 类似地处理 height[left] >= height[right] 的情况

来自AC自动机的评论

可算看懂了，原来双指针同时开两个柱子接水。大家题解没说清楚，害得我也没看懂。 对于每一个柱子接的水，那么它能接的水=min(左右两边最高柱子）-当前柱子高度，这个公式没有问题。同样的，两根柱子要一起求接水，同样要知道它们左右两边最大值的较小值。

问题就在这，假设两柱子分别为 i，j。那么就有 iLeftMax,iRightMax,jLeftMx,jRightMax 这个变量。由于 j>i ，故 jLeftMax>=iLeftMax，iRigthMax>=jRightMax.

那么，如果 iLeftMax>jRightMax，则必有 jLeftMax >= jRightMax，所有我们能接 j 点的水。

如果 jRightMax>iLeftMax，则必有 iRightMax >= iLeftMax，所以我们能接 i 点的水。

而上面我们实际上只用到了 iLeftMax，jRightMax 两个变量，故我们维护这两个即可。（题解都没说清楚，就说个 LeftMax，RightMax，谁知道为什么就可以这么做了。)

双指针代码

209.长度最小的子数组

题目链接

题面

给一个数组和一个target，要求计算数组中总合大于等于target的子数组（子数组要求连续）。

输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。

思路

首先想到暴力，然后想到二分。然而二分的时间复杂度为$O(n \log n)$，而空间复杂度为$O(n)$，实际上还是有很多优化空间的。使用滑动窗口的方法，时间复杂度和空间复杂度分别为$O(n)$和$O(1)$。

具体做法是，使用双指针，初始在下标为0的位置。每次将end右移一个单位，然后查看start到end是否满足条件，然后更新答案，每次迭代还需要将start也右移，直到这个区间不满足条件。感觉直接看代码更好懂。

代码

30.串联所有单词的子串

题目链接

题面

给一个字符串s，和一个字符串数组words（words中每个字符串的长度相等），要求返回这个字符串数组全排列生成的新字符串在s中的下标，顺序不限。

输入：s = "barfoothefoobarman", words = ["foo","bar"]
输出：[0,9]
解释：因为 words.length == 2 同时 words[i].length == 3，连接的子字符串的长度必须为 6。
子串 "barfoo" 开始位置是 0。它是 words 中以 ["bar","foo"] 顺序排列的连接。
子串 "foobar" 开始位置是 9。它是 words 中以 ["foo","bar"] 顺序排列的连接。
输出顺序无关紧要。返回 [9,0] 也是可以的。

思路

考虑word中字符串长度相等，所以这题实际上是438.找到字符串中所有字母异位词的升级版。依旧是使用滑动窗口。

可以回顾438的做法，维护一个变量和一个数组，用于描述窗口中的字符和目标字符之间的差距。每次试图将窗口右移，然后判断差距是否为0，即可更新答案。

问题是如何描述字符串和目标字符之间的差距，438中使用一个数组，因为字符的数量是已知的，并用一个变量differ来简化判断（否则要遍历整个数组）。而本题的字符串数量是不确定的，所以大概是逃不掉使用哈希表了。以上面的样例输入输出为例，可以每3个字符划分为一个字符串（滑动窗口的移动每次也移动3格），然后用438的方法来更新答案。但是这样会有一个问题，就是起始点不一定是3的倍数，所以还需要一层循环，从0枚举到2，把所有情况考虑进去。

代码

425.用最少数量的箭引爆气球

题目链接

题面

给定一系列区间，要求你放置若干个点，使得所有区间中至少有一个点。求这个点的数量的最小值。

输入：points = [[10,16],[2,8],[1,6],[7,12]]
输出：2
解释：气球可以用2支箭来爆破:
-在x = 6处射出箭，击破气球[2,8]和[1,6]。
-在x = 11处发射箭，击破气球[10,16]和[7,12]。

思路1

朴素做法，进行区间的合并，当然，在此之前需要对区间按照左边界进行排序。具体做法是，按左边界排序后，尝试合并两区间，如果更新成功就继续更新，更新失败就尝试下一个区间。

最后剩余（不相交）区间的数量就是答案。

朴素做法的题解

思路2

使用贪心算法。首先，如果一个子弹能够射穿当前这个气球，那么就无所谓具体是在哪个位置射穿的，我们可以直接每一个子弹射在左边界或右边界，这样能够保证达到最优解。

假如我们每次发射子弹都射在左边界，那么其实会存在一个左边界最右的区间，这个区间是必须得耗费一颗子弹的。因此，左边界最靠右的区间应该优先处理。

由此可以理出一个思路，可以将区间按左边界排序，优先处理左边界靠右的区间，在其左边界射一颗子弹，看齐能否“顺带”处理其他区间。当然，代码具体编写的时候是有些区别的。

下面是射击右边界的代码。

代码

57. 插入区间

题目链接

题面

给定一个无重叠的、按照区间左边界排序的区间列表，和一个新的区间，要求将这个新的区间插入到区间列表中，并且仍然要按照左区间排序，且不能重叠。

输入：intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
输出：[[1,2],[3,10],[12,16]]
解释：这是因为新的区间 [4,8] 与 [3,5],[6,7],[8,10] 重叠。

思路

想了很久，感觉思路混乱，直接查看题解。

题解的代码思路是很清晰的，是尝试将区间列表中和新区间有重叠的区间合并到新区间中，而不是将新区间合并到列表中。这样的思路让代码非常清晰，只需要分情况讨论即可。

还要注意代码中加入placed变量，判断新区间是否放入列表中（有可能合并后一直未找到适合放置的地方）。

224.基本计算器/227基本计算器II

题面

给定一个表达式，计算它的值。

输入：s = "(1+(4+5+2)-3)+(6+8)"
输出：23

输入：s = " 3+5 / 2 "
输出：5

思路

LeetCode上总共有三个名为“基本计算器x”的题，其实难度应该是循序渐进的，这里直接一步到位，实现最复杂的版本。

实现一个基本计算器，可以考虑使用双栈法。即一个栈nums存储将要运算的数字，另一个栈ops存储运算符。由于运算符是存在优先级的，所以需要使用一个函数来判断运算符之间的优先级，具体地说，乘除次之，加减最次（括号需要特殊处理）。实际上，整个计算过程是在维护ops这个单调栈，但排序key的不是字符的值，而是优先级。也就是说ops这个栈，新入栈的运算符的优先级应该要比栈中所有元素的高，如果新入栈的运算符优先级的较低的（或相等），那么就可以将栈内元素弹出进行运算。

对于括号，还需要特殊处理。上述说的维护ops单调栈的操作，有三个终止条件，一是栈空，二是栈顶优先级低于新元素，三是遇到左括号。而右括号到来时，就直接依次弹栈，进行计算（如果维护了上述所说的单调栈，那么这个栈中的优先级是非递减的）。

还有一个细节，就是可能存在单元运算符负号。我的解决办法是，加入一个flag，当要压入减号时，判断上一个插入的元素是符号还是数字，如果是符号（右括号除外），就说明这个是一个单元运算符，应该在nums中先压入一个0。

整个代码中，细节还是很多的，需要认真处理，使用函数式编程可以减轻编程难度。

另外，发现直接使用C++的stoi来转化数字会导致超时，而手写则不会。

代码

175.*二叉搜索树迭代器

题目链接

题面

设计一个二叉搜索树迭代器，其中包含next()函数和hasNext()，分别用于获取中序遍历的下一个元素和判断是否有下一个元素。

输入
["BSTIterator", "next", "next", "hasNext", "next", "hasNext", "next", "hasNext", "next", "hasNext"]
[[[7, 3, 15, null, null, 9, 20]], [], [], [], [], [], [], [], [], []]
输出
[null, 3, 7, true, 9, true, 15, true, 20, false]

解释
BSTIterator bSTIterator = new BSTIterator([7, 3, 15, null, null, 9, 20]);
bSTIterator.next();    // 返回 3
bSTIterator.next();    // 返回 7
bSTIterator.hasNext(); // 返回 True
bSTIterator.next();    // 返回 9
bSTIterator.hasNext(); // 返回 True
bSTIterator.next();    // 返回 15
bSTIterator.hasNext(); // 返回 True
bSTIterator.next();    // 返回 20
bSTIterator.hasNext(); // 返回 False

思路

原题的题面十分抽象，但是还是可以看懂的，另外，这题好像和二叉搜索树没什么关系，只要是二叉树都可以用这样的算法。

两种思路，最简单的就是直接搜索一遍整棵树，把结果存成一个数组放在对象中，但是这个方法太耗空间了。

另一种思路是自己手动实现一个栈，这个还是蛮有意思的，之前就有想过，函数的递归调用都可以通过手动实现一个栈来实现。对于中序遍历，每次总是会尽量往左子树走到底，所以对于当前的子树，必定要先将所有的左儿子依次入栈，这样就能满足最左的儿子先被遍历。如果当前子树有右子树，则在对右子树如法炮制。

class BSTIterator {
private:
    TreeNode* cur;
    stack<TreeNode*> stk;
public:
    BSTIterator(TreeNode* root): cur(root) {}
    int next() {
        while (cur != nullptr) {
            stk.push(cur);
            cur = cur->left;
        }
        cur = stk.top();
        stk.pop();
        int ret = cur->val;
        cur = cur->right;
        return ret;
    }
    bool hasNext() {
        return cur != nullptr || !stk.empty();
    }
};

先序遍历和后序遍历也可以使用栈来实现，先序遍历的比较简单，就是深搜（但是要注意，入栈顺序应该是先右子树，再左子树），下面是后序遍历迭代器的代码：

class PostorderIterator {
private:
    stack<TreeNode*> nodeStack;
    TreeNode* lastVisited;

public:
    PostorderIterator(TreeNode* root) : lastVisited(nullptr) {
        if (root) {
            nodeStack.push(root); // 初始化时将根节点压入栈中
        }
    }
    bool hasNext() {
        return !nodeStack.empty();
    }
    int next() {
        while (!nodeStack.empty()) {
            TreeNode* current = nodeStack.top();
            // 如果当前节点是叶子节点或已访问过
            if ((!current->left && !current->right) ||
                (lastVisited && (lastVisited == current->right || lastVisited == current->left))) {
                nodeStack.pop();
                lastVisited = current;
                return current->val;
            }
            // 按右子树、左子树的顺序压栈（后序为 左 → 右 → 根）
            if (current->right) {
                nodeStack.push(current->right);
            }
            if (current->left) {
                nodeStack.push(current->left);
            }
        }
        return -1; // 理论上不会到这里，保证返回值合法
    }
};

后序遍历比较与众不同的就是需要使用一个lastVisited来判断迭代的方向。

总体来说，使用迭代器来访问二叉树还是比较新奇的，之前都没有怎么考虑过这个问题，于是这里就记录下来，感觉可以作为一个代码模板稍微背一下。

222.完全二叉树的节点个数

题目链接

题面

给定一棵完全二叉树，求其节点数量，要求时间复杂度低于O(n）。

输入：root = [1,2,3,4,5,6]
输出：6

思路

正常来说使用O(n)的时间复杂度是肯定可以遍历完的，现在问题是如何降低时间复杂度。既然题目强调了完全二叉树的概念，那关键肯定就是如何利用完全二叉树的性质。不难发现，完全二叉树非叶子层是满的，我们就可以先计算层数，再计算叶子层的节点个数来得出总节点个数。

现在关键就是叶子节点要怎么算，直接遍历是没有办法做到的，查看题解之后确定使用二分法。首先叶节点个数是有单调性的，其次我们想知道叶节点k是否存在，可以通过将其二进制分解，然后得出从根节点到第k个叶节点的路径，然后判断路径是否存在。

在实际编写代码的过程中，有许多细节需要注意，比如说叶节点的个数区间应该是[1,2^level]。具体的代码编写方式有很多，取决于树的高度是从0还是1开始、二分查找区间的开闭、叶节点个数的区间等。

399.除法求值

题面

题目链接

给你一个变量对数组 equations 和一个实数值数组 values 作为已知条件，其中 equations[i] = [Ai, Bi] 和 values[i] 共同表示等式 Ai / Bi = values[i] 。每个 Ai 或 Bi 是一个表示单个变量的字符串。

另有一些以数组 queries 表示的问题，其中 queries[j] = [Cj, Dj] 表示第 j 个问题，请你根据已知条件找出 Cj / Dj = ? 的结果作为答案。

返回 所有问题的答案 。如果存在某个无法确定的答案，则用 -1.0 替代这个答案。如果问题中出现了给定的已知条件中没有出现的字符串，也需要用 -1.0 替代这个答案。

**注意：**输入总是有效的。你可以假设除法运算中不会出现除数为 0 的情况，且不存在任何矛盾的结果。

**注意：**未在等式列表中出现的变量是未定义的，因此无法确定它们的答案。

示例 1：

输入：equations = [["a","b"],["b","c"]], values = [2.0,3.0], queries = [["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]]
输出：[6.00000,0.50000,-1.00000,1.00000,-1.00000]
解释：
条件：a / b = 2.0, b / c = 3.0
问题：a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ?
结果：[6.0, 0.5, -1.0, 1.0, -1.0 ]
注意：x 是未定义的 => -1.0

思路

题目很长，但是其实并不难理解，就是从已知的分式退出未知的分式。这题的做法应该不止一种，官解的做法是使用并查集，然而用图也是可以做的。

用图论的思路来做，就是将一个分式的分子和分母看成节点，加入到图中去，然后使用Floyd算法。不一样的是，图中的节点是字符串，需要使用哈希表来存。可以直接使用二维的map，也可以先map一下然后再用数组。

使用并查集，就是将分式的分子和父母都加到并查集中去，但是这里除了维护father，还要维护weight，即这个节点比去父节点的值。

对于和并查集的合并，在连接根节点时需要知道weight，这时候就需要使用类似平行四边形定则的方法，即a不管是从d还是b比去c，这个比值都应该是相等的。

图论的代码比较简单，下面是并查集的代码

399.txt

188.买卖股票的最佳时机IV/III

题目链接

题面

给你一个整数数组 prices 和一个整数 k ，其中 prices[i] 是某支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。也就是说，你最多可以买 k 次，卖 k 次。

**注意：**你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

思路

最开始的思路是区间DP，但是在这题的姊妹题买卖股票的最佳时机III中，数据规模来到了10000，所以显然区间DP是很有可能爆内存的。但是这里不妨讲一下。

记$dp[i][k]$为前$i$天，进行$k$次买卖的收益，则不难得出转移方程：

$$dp[i][k] = max(dp[i][k],dp[q][k-1]+imax[q][i]-prices[q])$$

直观理解，就是从第$q$天转移到第$i$天，多进行一次股票交易。这样的转移方程，空间复杂度不是来自于$dp$，而是来自$imax[i][j]$（表示从$i$到$j$的最大值）的预处理。

题解思路也是比较清晰和简单的，是将买入和卖出的状态分开进行存储。用 $buy[i][j] $表示对于数组 $prices[0…i] $中的价格而言，进行恰好 $j $笔交易，并且当前手上持有一支股票，这种情况下的最大利润；用$ sell[i][j] $表示恰好进行 $j $笔交易，并且当前手上不持有股票，这种情况下的最大利润。那么状态转移方程为：

$$buy[i][j] = max\{buy[i-1][j],sell[i-1][j]-price[i]\}\\ sell[i][j] = max\{sell[i-1][j],buy[i-1][j-1]+price[i]\}$$

最后取$sell[i][0...k]$的最大值即可。

这个思路的转移方程是不难的，最难的地方在于边界条件的判断，首先$sell[0][j],buy[0][j]\ (j\ge1)$均为不合法的，需要将其赋值为一个较小的值，其次，$sell[i][0]$永远是0，不需要参与上面的状态转移。

这个思路最巧妙的地方在于，将状态转移的决策方式改变了，我最开始那个思路的决策方式是“哪天买入”，而题解的思路是“今天要不要买入”，可以很好地压缩占用内存的维度。