代码随想录刷题总结

最近把随想录剩下的题目都过了一遍。但是很多题目，我看了题解才会做，可能过几天就忘了。所以要多多重复，但要是每次复习都从头到尾一字不漏的看一遍，太浪费时间。

于是，我认为应该主动去总结，复习的时候写下自己的理解和方法论，方便之后的巩固，节省很多时间，减轻记忆负担。

数组

长度最小的子数组，使用滑动窗口，滑动窗口的题目主要关注左边元素弹出，右边元素加入，窗口内状态的变化。这个题要求窗口最小长度，所以在满足和大于target的基础上，尽量弹出左侧元素。

螺旋矩阵，模拟，没有什么套路。直接用评论区大佬的题解，首先设定上下左右边界，其次向右移动到最右，此时第一行因为已经使用过了，可以将其从图中删去，体现在代码中就是重新定义上边界，判断若重新定义后，上下边界交错，表明螺旋矩阵遍历结束，跳出循环，返回答案，若上下边界不交错，则遍历还未结束，接着向下向左向上移动，操作过程与第一，二步同理，不断循环以上步骤，直到某两条边界交错，跳出循环，返回答案。

哈希表

四数相加 II，有四组数字，求每组取一个数字和为0的组合数量。A组和B组为一组，n方复杂度遍历和作为key，下标记录在map里。C组和D组为一组，求和，找map里是否有合适的记录。因为不需要去重，比四数之和简单很多。

字符串

KMP

找出字符串中第一个匹配项的下标，这算法学一次忘一次。求文本串里第一个模板串的位置，首先要根据模板串求一个next数组，数组存的是下标之前的最长公共前后缀。得到next数组之后，遍历文本串当字符不匹配时，把指向模板串的下标调整到next数组指向位置。这样保证总共遍历一次文本串。时间复杂度变成了n + m，比n * m少得多。

求next数组也需要使用next数组的特性，和主函数一个套路，代码差不多可以背。

双指针法 链表

双指针法，可以解决移除元素、反转字符串、反转字符串中的单词（反转再反转），可以用java内置的方法来快速处理（正则匹配、链接、翻转）。

反转链表，迭代法是初始化空结点，循环链表指向前一个元素。递归法不用记。

删除链表的倒数第 N 个结点，一次遍历找到结点和前置结点就可以了。

相交链表常规方法是找到两个链表差值，从相同起点出发，比较是否相同。简单方法是，让两个指针同时出发，走完自己的路再走对方的，如果相等且不为空值就是交点。链表题目最好要画图理解清楚。

环形链表 II让找到环的入口结点，首先要用快慢指针判断是否有环，如果有环，相遇结点和头节点同时出发，最终相遇的结点就是环的入口。

双指针经典题目当然不能缺少 三数之和 四数之和这种nSum题目了。套路都是一样的，先排序好数组，三数之和就是遍历一个数，另外两个用双指针，四数之和就是两层循环遍历两个数，另外两个用双指针。

遍历数字去重一般都是if (i > 0 && nums[i] == nums[i - 1]) continue;和回溯的题目一个道理。而双指针控制左右数字去重是在一组数据符合要求之后，去掉左右重复的数字，不能在其他情况下去重。

LRU，这个经典题目，要用双链表、哈希、头尾指针来解决。尤其是头尾指针，因为我们需要用尾指针保证O1复杂度删除结点。初始化需要注意，head = new DLinkedNode(); tail = new DLinkedNode(); head.next = tail; tail.next = head;思路是使用的结点都放在头结点后。

栈与队列

栈和队列都能互相实现，两个栈可以实现一个队列，两个队列也可以实现一个栈（一个队列输出的时候把所有元素再输入到队尾也可以）。

有效的括号和逆波兰式求值，都可以用栈来实现。

最小栈，这个题目有一个大坑，Integer对象的比较，不是简单的int值比较，所以要用equals才会比较正确。题目思路是，用两个栈，第一个栈正常操作，第二个栈维护最小值，当有更小值push，没有则不操作。

单调队列

滑动窗口最大值，这个题目使用了单调队列。单调队列不是优先队列，不是简单的把窗口里的元素单调排列。这一点和单调栈类似。我们需要一个双端队列来保证元素可以从队列两边弹出。1.加入元素时，队尾小于元素的全部从右边弹出。2.删除元素时，如果队头元素相等则从左边弹出。这样，我们才可以保证，队列头部的元素是滑动窗口最大值。

优先队列

前 K 个高频元素，这个题目使用了优先队列。优先队列定义的时候，要写清楚排序规则。并且使用了map的遍历操作，方法要记得。

二叉树

二叉树的题目，首先要选择遍历方式，前中后序遍历和层序遍历。基本遍历代码这里就不放了，比较简单。我们要了解不同遍历方式的特点，灵活运用在解题上。

层序遍历

求树最后一行最左边的值，很明显要用层序遍历。但是我们可以从右往左的遍历，这样最后一个元素就是所求答案。

前中后遍历

二叉树的题目大多是选择一种合适递归遍历方式，核心是处理左右根三个结点。通常要处理四种情况：1. 根节点为null 2. 没有孩子 3. 只有一个孩子 4. 有左右孩子。简单情况下，后三种情况可以直接直接递归左右孩子，不做细分。

二叉树的最大深度，用的后序遍历，四种情况可以简化为1和其他。也可以用前序遍历，和普通的回溯套路是一样的，用变量去记录深度，返回最大的深度。路径总和，也类似的思路，代码简单。其实不用去纠结前序还是后序遍历，理解成简单的递归就可以了，能解决问题就行。

二叉树的最小深度，要注意最小深度是最近叶子结点到根节点的距离。所以3情况不能返回1，而是返回孩子深度+1。

平衡二叉树，简单方法是左右孩子都调用二叉树的最大深度获取高度判断是否平衡，时间复杂度n方很高。另一种方法是把求最大深度的函数改（先获取左右孩子深度，然后再处理返回值判断是否平衡），因为底层二叉树不平衡的话，整个树就不平衡。

特殊题型

对称二叉树，判断一个二叉树是否是镜像对称的。这个题目比较特殊，不同于普通遍历就传一个参数，要传入两个结点进行比较。return p.val == q.val && check(p.left, q.right) && check(p.right, q.left)

完全二叉树的节点个数，求节点个数当然可以n复杂度，但是完全二叉树有个规则，如果沿着左一直数和沿着右一直数相同的话，可以用公式直接求节点数量。如果不同，可以再去递归遍历左右孩子，个数相加。

从中序和后序遍历序列构造二叉树，后序数组中找到最后一个值作为根，分割中序数组，根据结果分割后序数组，接着再从两个后序数组中找到最后一个元素作为左右孩子，递归进行。1.分割的时候，要统一规则，比如全按照左闭右开2. 分割后序数组要按照前序分完之后的数组大小3. 递归参数要写对

二叉树的最近公共祖先，如果查到p或者q就返回结点，后序遍历，如果左右孩子都有返回值就说明找到了。

将有序数组转换为二叉搜索树，类似上面那个构造二叉树的方法，递归返回根节点，本题根节点需要返回中间位置的数组元素。

二叉树展开为链表，先序遍历，结点右孩子指向下一个遍历元素，但是会丢失原有右孩子。先序遍历的逆序，用右指针指向前一个结点即可。

回溯

回溯套路很固定，我通常的做法就是用path来记录过程，res来记录结果。要考虑的问题是结束回溯的条件、选择路径、复原路径。有的题目还需要考虑一下剪枝的问题。简而言之，回溯可以看成树型结构，哪些结点是一层，哪些结点是一条路径，这些需要考虑清楚。

组合 or 排列

组合问题，求从n个数中选择k个数的组合，代码结构很简单，要考虑剪枝（控制选择范围）。

组合跟排列的区别在于，组合需要排序并且控制选择的起始点。而排列每层都可以选全部选项，但要保证选项没有被选过。

比如组合总和这一题，如果误以为每层选择都可以选全部，那就犯错了。组合总和II这一题，相同元素只能选择一次，所以选择时要去重。去重，就是先把选项排列好，相同元素跳过。

全排列使用的是没有重复的数字，全排列II使用的是可包含重复数字的序列。所以，后者也需要进行去重（排序+跳过），同时因为是排列，也需要保证选项没被选过。

组合总和II和全排列II这两道题搞清楚，组合和排列是什么区别就比较明白了。

分割

回溯题目，除了经典的组合排列问题，还有很多相似问题类型。比如分割回文串，aab截取a、ab、aab相当于[1, 2, 3]中选择1、2、3的组合问题，也能通过回溯的套路解决。判断回文串要用双指针方法。复原IP地址也是类似问题。回溯函数里传的是起始点，选项是终止点。

子集

子集问题其实就是组合问题，记录所有结点，而不是只记录叶子结点。子集和子集II。递增子序列这个题有些特殊，因为我们需要去重，但是不能把原有数组进行排序。所以我们选择set来去重，每一层都有一个set记录。

棋盘问题

N皇后和解数独，两个题目都是针对一个二维棋盘，遍历每一个位置，选择一个选项，然后继续回溯。别忘了，回溯之后把位置重置。其实，我认为难点在于判断棋盘是否可行。

贪心

贪心没有固定套路，如果可以局部最优推出全局最优，举不出反例就可以用。所以还是要多看看贪心的题目，记住解题方法。

分发饼干，大饼干先要喂给胃口大的。

摆动序列，答案就是只记录摆动的数量。要记录当前差值和前一个差值，当前差值不是0但前一个差值是0（平坡），符合要求，当前差值为0肯定不符合要求，不符合要求的时候，就不用更新前一个差值，相当于没有摆动，不做记录。

加油站，贪心思路是遍历每一天剩下的油，如果总和是负数则不能完成路线，遍历过程中负的最多的那一天的下一天就是起点。换一种思路，连续亏空最多的那一站，一定要最后走，等待前面所有正数填补

分发糖果，这个问题不能一次遍历同时处理元素的左右糖果数量，会顾此失彼。先从前往后遍历，处理右边评分大于左边的情况，再从后往前遍历，处理左边评分大于右边的情况，并且第二次遍历的时候，要选择加一或者上次遍历结果的最大值（保证满足两次遍历关系）。

根据身高重建队列，题目明确一个元素要考虑两种维度的属性，常用解法就是先按照一种维度排序，再后续处理。按照身高降序排序，再按照另一个维度当作下标插入队列，就能解决。

单调递增的数字，贪心：从后往前数，如果前一个数字大于当前数字，则当前数字变为9，前一个数字减少，保证数字最大。例如339-> 329->299

监控二叉树，这题是贪心和二叉树结合的难题。

区间问题

跳跃游戏和跳跃游戏II都是考虑区间动态覆盖范围的题目，每次跳跃都要更新这个最大覆盖范围。前者只需要最新范围大于数组长度就能判断，后者每次超过跳跃范围再更新并且记录跳跃次数。

区间重叠问题，贪心也可以处理。用最少数量的箭引爆气球意思是区间重叠的气球归为一组引爆。如何分组呢，我们首先把区间按照左边界排序，然后遍历左边界，左边界小于分组右边界的归为一组。缩小每个分组的右边界，重叠区间的右边界是不断在缩小的。具体代码如下：

Arrays.sort(points, (a, b) -> Integer.compare(a[0], b[0]));
int res = 1;
int right = points[0][1]; // 区间的右边界
for (int i = 1; i < points.length; i++) {
    if (points[i][0] > right) { // 下一个分组
        res++;
        right = points[i][1]; // 下一个重叠分组的右边界
    } else {
        right = Math.min(points[i][1], right); // 不断缩小区间右边界
    }
}
return res;

无重叠区间也是类似解法，不断缩小重叠区间右边界，就可以保留最小区间。每个分组除了最小区间，其他的重叠区间都要移除。

合并区间和前面题目有点区别，因为合并的话要扩大区间右边界，而不是缩小了。right = Math.max(right, intervals[i][1]);

划分字母区间这个题目如果用上述方法，复杂度至少也是nlogn，但是可以换一种方法，两次遍历得到结果。第一次遍历获取每个字母的最后位置，第二次遍历不断更新当前字符串的最后位置，遍历到相等位置就存。

动态规划

动态规划，跟“状态”这一词分不开，复杂一点的题目，有好几个状态转换，dp数组的递归方程也有好几个。当然，也有很多简单题目。只要推导出递归方程，考虑好dp数组初始化，就可以解答。

背包问题

背包问题，需要掌握01背包和完全背包，简单来说就是从固定的物品中选择一些装背包。01背包是同一物品只能选择一次，完全背包是可以选择多次。

背包问题，有二维dp数组和一维dp数组两种写法。二维的dp[i][j]表示0 - i下标物品中取，放在容量为j的背包里，价值总和最大多少。递归方程是dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])。用滚动数组转换为一维dp数组，代码就固定如下：

for(int i = 0; i < weight.size(); i++) { // 求排列要外围遍历背包容量，求组合要外围遍历物品
    for(int j = bagWeight; j >= weight[i]; j--) { // 01背包遍历背包容量要倒序，保证物品不重复加入，完全背包要正序，可以重复加入同一物品
        dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

    }
}

背包问题的代码套路很固定，要先把题目转换为背包问题，解决就简单一半了。举一些转换为背包问题的例子如下：

分割等和子集，可以看作取集合元素装一半总和容量的背包，如果装满了就可以分割。所以说动态规划也不一定就是只作用于极值问题。

最后一块石头重量II，题目让两个一组碎石头，也可以转换为装一半总和背包的问题，尽量装满就可以保证剩下的碎石最小，也算是一个极值问题。

背包问题，不是只有装满背包有多大价值一种类型，还可以求装满背包有多少中取法，目标和这个题目，先进行一些数学运算，然后转换为了求取法类型。要注意，dp[0]要初始化为1，递归方程改为dp[j] += dp[j - nums[i]]。

一和零这个题，复杂度又有提升，需要同时满足两个维度的背包，所以dp数组上升为二维。

背包问题，还有一个考法需要考虑——求排列数量，而不是组合数量。简而言之，求排列要外围遍历背包容量，求组合要外围遍历物品。比如，1，5 和 5， 1是不同排列，外围遍历物品只会出现1，5的组合。单词拆分

完全背包的练习题有组合总和IV，零钱兑换，完全平方数

打家劫舍

打家劫舍这类问题递归方程较简单，因为相邻屋子不能偷，那么状态就是偷或者不偷，从隔一个或者前一个状态得到最大值。

打家劫舍II有要求首尾不能同时偷，所以要处理多种情况，归为两种偷法，考虑首不考虑尾 and 考虑尾不考虑首，两种情况都偷一遍，取最大值。

打家劫舍III规定结构为二叉树，树型dp怎么办？其实，考虑每个结点也无非两种状态，偷 or 不偷。解决方案是，采用后序遍历求每个结点偷或者不偷的最大值，并且要返回上一层。题解采用大小为2的数组，res[0]保存不偷，res[1]保存偷的最大值。

买卖股票

买卖股票问题，要获取最大利润。难度大的类型，要求我们明白动态规划的“状态”概念。

首先是买卖一次，最佳时机I，很简单，只需要记录前面天数的最低价格，获取最高差价就可以。

买卖多次，不对次数做出限制的话，也可以用贪心轻松解决。只要前后差价是正数就进行一次买卖。

如果对次数做出限制，就需要我们构造“状态”了。参考打家劫舍题目，每个屋子都有偷和不偷两个状态。比如，最佳时机III规定买卖2次，需要有5个状态。代码和解释如下：

// dp[i][0]无操作
   // dp[i][1]第一次已持有 的现金
   // dp[i][2]第一次已卖出 的现金
   // dp[i][3]第二次已持有 的现金
   // dp[i][4]第二次已卖出 的现金
   // 答案一定是第二次已卖出 的现金，已经包括了一次或者零次（最后一天多次买卖）
   public int maxProfit(int[] prices) {
       int len = prices.length;
       int[][] dp = new int[len][5];
       dp[0][1] = -prices[0];
       dp[0][3] = -prices[0];
       for (int i = 1; i < len; i++) {
           // 状态变换方程，要么继承前一天的状态，要么当天发生状态变化
           dp[i][1] = Math.max(dp[i - 1][1], -prices[i]);
           dp[i][2] = Math.max(dp[i - 1][2], dp[i - 1][1] + prices[i]);
           dp[i][3] = Math.max(dp[i - 1][3], dp[i - 1][2] - prices[i]);
           dp[i][4] = Math.max(dp[i - 1][4], dp[i - 1][3] + prices[i]);
       }
       return dp[len - 1][4];
   }

最佳时机IV，规定买卖k次，我们可以从上题总结出买卖k次的代码，有2 * k + 1个状态

最佳时机含冷冻期，规定每次卖完股票有一天冷冻期，之后才能购买股票。做这个题目，第一步还是划分好状态。持有股票，未持有股票（继承上次未持有 and 今天卖出股票，只有今天卖出股票会导致冷冻期出现），冷冻期状态。所以有四个状态。后续操作都一样。

子序列

子序列的题目，重点在于构造二维dp数组，解决两个数组之间的问题。

求两个数组的最长重复子数组这一题，首先dp[i][j]代表nums1[:i-1]和nums2[:j-1]的最大公共后缀长度，这样定义可以简化代码。其次，递归方程是 if (nums1[i - 1] == nums2[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;这是经典题目，要牢记。

最长公共子序列和上题对比一下，dp数组定义一样，状态转移不一样。当前元素不同的话， dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]); 不相交的线这一题，看似没思路，但可以转换为这个题。

最大子序和这个题目，可以用贪心只算正和，也可以用dp来对比当前元素和前面元素的和，比较简单。

编辑距离是子序列的经典题目。我们先看有关的几个题目，判断子序列是要判断s是否为t的子序列，其实求出最长公共子序列为s的长度就可以判断了。通过这道题目可以看出，求最大公共子序列其实就是两个字符串都可以删除元素，判断子序列是t可以删除元素，s不可以。所以dp[i][j] = dp[i][j - 1]。

两个字符串的删除操作，想求两个字符串相同的最小步数，要求只用删除操作。可以用两个字符串长度总和减去最长公共子序列长度。

不同的子序列这一题是求s的子序列里有多少个t，比如rabbbit里有三个rabbit（删掉任一个b，都是不同的答案）。所以是s可以删掉，t不能删掉。匹配相同的时候，可以选择不匹配当前s[i - 1]。所以状态转移方程如下：

if (s[i - 1] == t[j - 1]) {
    dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
} else {
    dp[i][j] = dp[i - 1][j];
}

编辑距离终于要解决了，要求两个字符串相同的最小步数，状态转移方程如下：

if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
    dp[i][j] = dp[i - 1][j - 1]; 
} else {
    dp[i][j] = Math.min(Math.min(dp[i - 1][j - 1], dp[i][j - 1]), dp[i - 1][j]) + 1; // 删除相当于添加元素，修改元素在i-1 j-1基础上
}

补充

解码方法，每个数字要么单独一个数字，要么与前一个组成数字。

正则表达式匹配，dp[i][j] 表示 s 的前 i 个字符是否能匹配 p 的前 j 个字符，一维是字符串，二维是表达式

if (pChar == sChar || pChar == '.') {
                    // 如果当前字符匹配，或者正则表达式中是 '.'，则可以选择匹配一个字符
                    dp[i][j] = dp[i - 1][j - 1];
                } else if (pChar == '*') {
                    // 如果当前正则表达式字符是 '*'，则有两种选择：
                    // 1. 匹配零次前面的字符，即跳过 '*'
                    // 2. 匹配一次前面的字符，即使用 '*' 匹配一个字符，一定要把 '*' 留下
                    dp[i][j] = dp[i][j - 2] || (dp[i - 1][j] && (sChar == p.charAt(j - 2) || p.charAt(j - 2) == '.'));
                }

单调栈

单调栈，通常是题目要求在一维数组中，要寻找任一个元素的右边或者左边第一个比自己大或者小的元素的位置。

每日温度这道题目，记录数组元素右侧第一个大于自己的下标，维护一个递减的栈，当加入元素大于栈顶，就弹出所有不符合元素并且记录答案。

下一个更大元素I这道题目，两个数组之间有对应关系，这种情况可以用map来处理，这是一个技巧。下一个更大元素II这题多了个循环数组的要求，可以通过下标取余遍历两次数组，长度是2 * len。

接雨水，经典常考题目，当前列雨水面积：min(左边柱子的最高高度，记录右边柱子的最高高度) - 当前柱子高度，简单解法是，用两个数组两次遍历，记录柱子左侧和右侧的最高高度，然后再遍历原数组求和。

这个方法还可以更简单，只用一次遍历就可以。用首尾指针去记录左右最大值，取较小的一个指针移动，同时就可以计算那个指针所在位置的雨水，很巧妙。

单调栈的方法写这个题目，比较麻烦，减少记忆负担算了。

图论

对于图，简单来说就是两种遍历方式，一种是dfs，沿着一条路走到底，递归。另一种是bfs，一层一层搜索，队列。和树不同的点在于，图可能出现走回头路的情况，需要额外控制。

如果要求是遍历图的话，用dfs写代码更方便，如果是要求最短路径那就需要bfs。

DFS

dfs的题目，和回溯法是一样的。代码上看，都要另外写一个回溯函数，需要考虑终止条件和返回值。函数里遍历所有选择，结构相当于树的同一层。递归返回后要撤销选择。

矩阵中的最长递增路径

BFS

bfs的题目，必须要有队列来控制。目的就是求最短路径。单词接龙

岛屿问题

岛屿问题是图的经典问题，求数量的时候，可以dfs遍历的岛屿就下沉，这样也不会走回头路，算是一个技巧。求面积的时候，dfs就需要定义返回值为面积了。

有的题是从边界出发dfs，然后标记一些可以到边界的岛屿。有的题是通过高度差去标记可以流到边界的岛屿，思路都一样。

太平洋大西洋，需要标记同时到两个边界的岛屿，建议用两次dfs，然后合并找出都标记的岛屿，代码好写很多。

最大人工岛，建议不要去遍历所有空格变成人工岛的情况，时间复杂度很高。而是去标记现有的成片岛屿获取面积，然后只需要把人工岛周围岛屿面积相加就可以了。

岛屿周长，简单题，周长 = 岛屿数量 * 4 - 2 * 接壤边数（统计右/下或者左/上）

并查集

太难，放弃

其他

两数相除，不能用乘除取余运算，思路是用移位运算，把被除数一直移位，移到能被减掉的最大位置做减法，之后循环。异或判断符号很好用。

前缀和

和为 K 的子数组，和可被 K 整除的子数组