LeetCode-Solutions-in-Good-Style

说明：我和绝大多数同学一样，一边学习、一边总结。我会争取做更多的分享，给大家带来一些有用的知识，感谢大家一直以来的支持。

大家好，这里是一个《算法与数据结构》的入门级教程，适用于算法零基础和转行同学，不适合于准备算法竞赛。想传递的观点是：写逻辑清楚的代码，所以我写的代码一定经过了严格的思考，格式非常标准，不带有个人风格，不会为了缩减代码行数而少写一个空行和注释。在这里：

• 特别感谢 @AbbyDeng 同学的更名建议；
• 所有的代码都通过 LeetCode（力扣） 在线测评系统检测；
• 如果大家有问题，可以给本项目提 Issues；
• 本教程的目的是科普，帮助零基础和转行的朋友入门，养成正确的编写代码的习惯，所以不会花大量的时间和精力去研究一些比较偏门的算法和数据结构；
• 这里是一点个人意见：对于绝大多数朋友来说，算法与数据结构很有用，但是做算法题可能没有那么有用。掌握一定的算法与数据结构的知识和思维角度是有用的，算法题可以帮助我们更加深刻的理解算法与数据结构的设计思想，但我们没有必要掌握一些可能现在用不到的算法与数据结构知识。所以很遗憾，我一定会有很多问题不会做，但我也不想把它们搞明白。如果大家提出的问题，特别是面试中遇到的问题，我不会就直接和大家说我不会了；
• 建议安装 Octotree 插件，以获得最佳的阅读体验：

可以叫我 weiwei，在我力所能及且时间允许的情况下，我会尽可能回答我知道的问题。如果有不能及时回复的问题，可能是因为我没有看到站内通知，可以发邮件给我 [email protected] 。

我录制的视频题解

我从 2019 年 9 月开始录制视频题解。最开始的时候，我会对着要讲的材料录好几遍。现在讲解知识点的时候写逐字稿。已经沉淀了很多视频，其实也算是一个小小的体系课程，现在罗列在这里，希望能够对大家有所帮助。

0. 算法新手如何刷力扣（LeetCode）？【干货分享】

• 视频：算法新手如何刷力扣（LeetCode）？【干货分享】

1. 时间复杂度与空间复杂度

• 视频：时间复杂度与空间复杂度

这个视频提到了时间复杂度是一个渐进概念，需要用动态的角度去理解。并且讲解了时间复杂度的严格定义（极限形式），以便大家理解时间复杂度的计算规则。并且还指出了：时间复杂度不是程序的运行时间；应该使用「空间换时间」，更多关注在优化「时间复杂度」。

2. 二分查找

• 视频：用「排除法」（减治思想）写二分查找问题

这个视频介绍了如何写对二分查找算法，二分查找的细节虽然多，但只要我们掌握了正确的解题思路，并且多加练习、勤于思考、多做总结，写对二分查找的问题就不再困难。

下面的视频讲解了几道二分查找的例题，我们重点分析了题意和如何利用题目中给出的条件逐渐缩小搜索区间。

我们通过「力扣」第 4 题（寻找两个正序数组的中位数）的分析，向大家介绍了这样的技巧：如果要找的目标元素的性质比较复杂，可以对这条性质取反，进而写出可以简单的可以缩减问题区间的逻辑语句。

3. 和排序相关的问题

「归并排序」和「快速排序」是非常重要的排序算法，深刻理解它们对于理解「递归」函数的运行机制有着非常大的帮助，同时它们也是「分治思想」的典型应用。「逆序对」和「荷兰国旗问题（颜色分类）」也是非常经典的算法问题。

计算「逆序对」完全就是按照「归并排序」的思路而来。

在「颜色分类」问题的讲解中，我们向大家介绍了「循环不变量」，在编写代码的过程中，我们应该一直遵守所使用的变量的语义，在「程序执行前」「执行过程中」「执行结束」以后保持不变。遵守我们自己定义「循环不变量」是我们写对正确代码的重要方法。

「缺失的第一个正数」是一个经典的算法问题，用到的思想是「原地哈希」，可以理解为是「桶排序」算法的特殊应用：一个萝卜一个坑，一个桶里只存放一个元素。要和大家强调的是，可以这样做是和输入数组的元素的数值密切相关。

4. 滑动窗口

「滑动窗口」问题是典型的应用「循环不变量」解决的问题，比较考验我们编码和调试的能力。

5. 栈相关的问题

使用「栈」解决的问题，需要我们通过具体例子，发现解决它们正好符合「后进先出」的规律：

• 把暂时还不能确定结果的数据放入栈，把可以确定结果的数据从栈中拿出；
• 很多数据结构恰好应用于这种「动态」处理问题的场景，而发挥出它们的应用价值。

掌握下面这两个问题，离不开对具体例子的研究，进而归纳出一般规律。

「栈」最为广泛的一种应用就是作为「递归」「深度优先遍历」「分治算法」的数据结构支持。

6. 并查集

「并查集」这个数据结构目前来说在面试中出现比较少，如果是准备算法面试的朋友，可以跳过。

7. 树

树的问题很多都可以使用「深度优先遍历」或者「广度优先遍历」去做。

8. 回溯算法

「回溯算法」其实就是对题目中所蕴含的「树形结构」执行一次 深度优先遍历。做这一类问题，在草稿纸上画出树形结构图很重要。

9. 动态规划

10. 广度优先遍历与拓扑排序

11. 哈希表

12. 位运算相关

我的个人网站和算法学习笔记

• 个人主页：https://liweiwei1419.gitee.io/leetcode-algo/；
• 语雀笔记：https://www.yuque.com/liweiwei1419/algo；
• CSDN 博客：https://blog.csdn.net/lw_power；
• 微信公众号：力扣图解可能没有图（目前佛系运营）。

微信群与 QQ 群

如果需要一起刷题的朋友，可以加入微信群和 QQ 群。

• 微信群：每日一题打卡活动和加入微信群可以点 这里 。感谢 负雪明烛 建群；
• QQ 群：群号：812791932。感谢 二哥 建群。

我的 LeetBook

这里给自己做一个宣传，我最近在「力扣」上推出了自己的 LeetBook：零起步学算法（原名《使用「力扣」学习算法与数据结构》），主要面向 转行 、零基础 的朋友，讲解算法与数据结构的基础知识。

说明：

• 该 LeetBook 的前两章（ 时间复杂度、二分查找）是免费阅读的，后面的章节 需要付费 阅读，非会员价 99 元，会员价 69 元，您当前看到的主页目录与 LeetBook 是一样的，只有多出来的部分，不会更少；

• LeetBook 的课程标题、例题、练习、配套代码仓库（就是您当前看到的这个仓库）是完全公开的，如果 LeetBook 里设计的内容（包括练习）您已经掌握，就不太建议购买；

• 投入精力与平时写题解是一样的，只不过 LeetBook 在制作图表上会更细致一点。付费内容是：制作教程的时间精力付出、「力扣」的工作人员和高手参与制作和审核，阅读体验会更好一些。不排除平时写的题解知识点比 LeetBook 还要多；

• 中、高阶用户请谨慎购买；

• 可以在「力扣」站内或者是我的其他社交账号向我咨询课程内容，也可以向本仓库提 issue。不管是否购买课程，我都会尽量回答我所知道的问题（时间允许，能力范围之内）。感谢大家一直以来，一如既往对我的支持。有建议和意见也欢迎大家与我交流；

• 我所讲解的知识在我曾经向大家推荐的书籍，我写的博客、题解和笔记里都有，已经发布的题解、博客、笔记都会一直共享，并且只要我有时间和精力，我还会坚持做分享和答疑；

• 很感谢「力扣」给我机会做课程的机会，帮助我完成一个小小心愿。

「力扣」分类以及题解目录（按照 LeetBook 的章节编排，第 16 章以后为目前 LeetBook 不包含的章节）

说明：题目分类与我的 LeetBook 章节对应。

第 1 章 时间复杂度

这部分内容介绍了 时间复杂度 这个概念，可以收看 【视频讲解】 ，完全免费。 这一章节没有练习。

第 2 章 二分查找

• 可以我的 LeetBook 收看二分查找的知识点 讲解，免费；
• 知识点讲解：写对二分查找不能靠模板，需要理解加练习 （附练习题，持续更新）、【视频讲解】。

题型一：二分求下标

• 重点问题

说明：

• 第 34 题：二分查找找边界问题、CSDN、庸才顾子汐：关于 while (left <= right) 写法返回值的详细讨论；
• 第 4 题：二分查找里最难的问题，重点在于理解：① 为什么是在短数组里找边界；② 边界条件的判断。

练习：

题型二：二分确定一个有范围的整数（二分答案）

算法思想：减而治之。如果题目要我们找一个整数，这个整数有确定的范围，可以通过二分查找逐渐缩小范围，最后逼近到一个数。

题型三：复杂的判别函数（最大值极小化问题）

说明：这一类问题本质上还是「题型二」（二分答案），但是初学的时候会觉得有一些绕。这一类问题的问法都差不多，关键字是「连续」、「正整数」，请大家注意捕捉题目中这样的关键信息。

• 二分查找之「最大值极小化」相关问题及解题步骤
• 二分查找之「最大值极小化」例题选讲

第 3 章 基础排序算法

这一部分包含了四种基础排序算法：选择排序、插入排序、希尔排序、冒泡排序。

「力扣」第 912 题：排序数组 的 题解：总结了排序问题的一些要点和学习资料，可以从排序问题开始学习算法。

数组的问题可以作为算法「新手场」，因为这些问题只需要掌握编程语言的基础知识就可以完成。以下问题都很容易想到解决方案，即使没有学习过相关的数据结构和算法知识。

知识点：循环不变量

• 循环不变量用于证明算法的有效性，也是编码正确的理论依据；
• 循环不变量定义帮助分清先加还是先赋值，还有一些边界条件。定义清楚循环不变量以后，代码的编写就会很轻松；
• 建议把「循环不变量」作为注释写在代码里，以方便自己调试和他人阅读。

第 4 章 高级排序算法（重要）

这一部分需要重点掌握三种高级排序算法：归并排序、快速排序、堆排序。

说明：

• 第 88 题：归并排序，注意这里从后向前归并；
• 《剑指 Offer》第 51 题：归并排序、树状数组（选学）；
• 第 75 题：著名的「荷兰国旗」问题、快排；
• 第 215 题：快排、优先队列；
• 第 451 题：快排、优先队列。

第 5 章 非比较排序（选学）

这一部分包含了三种非比较排序排序：计数排序、基数排序、桶排序。解决这些问题需要知道 原地哈希 这个概念。

第 6 章 滑动窗口与双指针

一、滑动窗口

• 思想简单，但是代码比较难一次写对；
• 滑动窗口的思想是：先向右移动右指针、再向右移动左指针，这样左右指针交替执行（ 不回头 ），可以完成一些问题；
• 滑动窗口是 暴力解法的优化 ，如何 根据目标函数把暴力解法的一系列解排除掉，是使用滑动窗口的前提 ，一定要分析清楚；
• 下面提供的是一种参考的写法，请不要照搬，应该 先理解滑动窗口的思想（暴力解法的剪枝） ，然后多加练习，掌握编写代码的技巧和细节。

滑动窗口的参考写法（不是模板，请不要原样照搬，仅供参考，理解算法设计思想是更重要的）：

public class Solution {

    public String slidingWindow(String s, String t) {
        // 起始的时候，都位于 0，同方向移动
        int left = 0;
        int right = 0;
        while (right < sLen) {
            if ( 在右移的过程中检测是否满足条件 ) {
                // 对状态做修改，好让程序在后面检测到满足条件
            }
            // 右边界右移 1 格
            right++;
            while ( 满足条件 ) {
                // 走到这里是满足条件的，左边界逐渐逐渐左移，可以取最小值
                if ( 在左移的过程中检测是否不满足条件 ) {
                    // 对状态做修改，好让程序在后面检测到不满足条件
                }
                // 左边界左移 1 格
                left++;
            }
            // 走到这里是不满足条件的，右边界逐渐右移，可以取最大值
        }
        return 需要的结果变量;
    }
}

友情提示：第 3 题和第 76 题是必须要会做的基本问题。上面的问题理解透彻了，下面的问题就可以比较轻松地做出来。

重点问题：

说明：

• 第 3 题：先暴力解法，再优化；
• 第 76 题：滑动窗口的典型问题，重点分析为什么可以使用滑动窗口。字符频数数组可以使用哈希表，也可以直接使用数组；使用 距离 的定义加速计算；
• 第 424 题：重点分析为什么可以使用滑动窗口。设计变量 maxCount 的含义：在滑动的过程中，出现的字符频数最多的个数；收集结果的判断语句（while (right - left > maxCount + k)）比较难想到。第 424 题同类问题：「力扣」第 1493 题：删掉一个元素以后全为 1 的最长子数组 。

public class Solution {

    // 第 424 题代码：滑动窗口（暴力解法的优化）

    public int longestSubarray(int[] nums) {
        int len = nums.length;
        int left = 0;
        int right = 0;

        // 连续的 1 的个数
        int ones = 0;

        // 删除一个元素以后全为 1 的最长的子串的长度
        int maxCount = 0;
        int res = 0;

        while (right < len) {
            if (nums[right] == 1) {
                ones++;
            }
            maxCount = Math.max(maxCount, ones);
            right++;
            // maxCount + 1 里的 1 就表示删除的那个元素
            while (right - left > maxCount + 1) {
                if (nums[left] == 1) {
                    ones--;
                }
                left++;
            }
            res = Math.max(res, right - left);
        }
        // 注意：这里返回 res 要减 1
        return res - 1;
    }
}

练习：

说明：

• 第 209 题：题目中给出的关键信息：数组里的元素全部是正整数。一共有以下 3 种方法。

  • 方法一：暴力解法

  • 方法二：滑动窗口（分析可以使用滑动窗口的原因）

  • 方法三：构造前缀和数组，然后使用二分查找

• 第 438 题：同第 76 题；

• 第 567 题：同第 76 题，收集符合条件的语句不一样而已。

二、双指针

「双指针」问题其实也是朴素算法的优化，一下子排序掉很多不符合题意的解，「滑动窗口」技巧也是这样的。依然是分析为什么可以使用双指针是更重要的。

二分查找算法应用于查找下标也可以认为是双指针的解法。

第 7 章 链表

解决链表问题，很实用的技巧是「画图」。其它算法问题的分析和讲解（和面试官讲解）也是这样。

可以为链表编写测试函数，方便调试。建议实现的方法有：① 通过数组创建一个单链表；② 根据当前结点打印当前结点以及后面的结点。这两个方法可以非常方便地帮助我们调试关于链表的程序。

题型一：基本的链表指针指向问题

注意：有一些问题需要使用「虚拟头结点」，以避免对链表第一个结点的复杂的分类讨论逻辑。这个思想在数组里我们见过，叫「哨兵」。

使用递归函数，避免复杂的更改指针变量指向操作，使得求解问题变得简单。

说明：

• 这些问题使用递归和迭代都可以完成：206、24、25、328、203、21；
• 第 148 题需要知道如何使用递归函数实现链表排序，迭代的写法仅供参考。

题型二：快慢指针技巧

确切地说，叫「同步指针」可能更好一些。

使用两个指针变量，刚开始都位于链表的第一个结点，一个永远一次只走一步，另一个永远一次只走两步，一个在前，一个在后，同时走。这样当快指针走完的时候，慢指针就来到了链表的中间位置。

解决这些问题的共同特点就是使用两个指针变量同步移动。快慢指针的前进方向相同，且它们步伐的「差」是恒定的，根据这种确定性去解决链表中的一些问题。使用这种思想还可以解决链表的以下问题：

说明：

• 第 19 题：，快指针先走几步，不是靠猜的，要在纸上画图模拟一下，就清楚了；
• 第 141 题：，在环中的时候可以想象，A 同学开始有存款 100 元，每天赚 1 元，B 同学开始有存款 50 元，每天赚 2 元，B 同学一定会在某一天和 A 同学的存款一样；
• 第 161 题：起点不同，构造相同长度让它们相遇，同样是利用了同步走这个等量关系。

题型三：设计数据结构

第 8 章 栈与队列

一、栈

题型一：基本的使用栈解决的问题

下面的问题非常基础，一定需要掌握：

练习：

题型二：单调栈

单调栈就是普通的栈，在使用的过程中恰好符合了「后进先出」，栈内元素单调的特点。「单调栈」和「单调队列」的问题通常来说很特殊，掌握例题和一些练习就可以了。

经验：单调栈中一般存下标。

说明：

• 第 739 题：推荐阅读 程序员的自我修养：739. Daily Temperatures；

练习：

二、队列

题型一：基本的使用队列解决的问题

所有的使用广度优先遍历解决的问题，都使用了队列。

题型二：单调队列

单调队列就是普通的队列。「力扣」上的单调队列目前就发现这一个问题，关键分析清楚为什么设计的算法恰好使得单调队列。另外，「背包问题」中有使用单调队列进行优化的例子，感兴趣的朋友可以了解一下，是竞赛方面的知识。

经验：单调队列中一般存下标。

第 9 章 优先队列

说明：了解「堆」作为「优先队列」的实现是有必要的，有助于理解 remove() 、replace() 这些编码的细节，使用堆的时候才会更加有效。

应用：动态 选取当前队列中优先级最高的元素，重点理解「动态」的含义。

第 10 章 并查集

并查集知识点的【视频讲解】在第 990 题视频题解里有。基础且常见的问题有：

选做问题：

第 11 章 树（二叉树与二分搜索树）

第 12 章 回溯算法

题型一：基本回溯问题

通过这些问题理解回溯算法的思想，回溯算法的知识点讲解在「力扣」第 46 题的视频题解和文字题解。

回溯就是用深度优先遍历的方式去搜索 树（图）的所有解。深度优先遍历有很明显的递归结构。

做对下面这些问题的技巧：① 画图、画图、画图；② 理解深度优先遍历与递归；③ 多调试、多调试。

题型二：字符串上的回溯问题

重点理解：由于字符串每次都生成新字符，无须状态重置。

题型三：Flood Fill

题型四：一些游戏问题

说明：

• 第 51 题：经典问题，掌握「空间换时间」技巧；
• 第 529 题：寻找连通分量。DFS 和 BFS 均可。

第 13 章 动态规划（上）

动态规划的两个重要思想：

• 穷举：动态规划没有为问题设计专门的算法，它考虑了完成一件事情所有的情况；
• 空间换时间：记住了每一步求解的结果。

动态规划的两个思考方向：

• 「自顶向下」记忆化递归：
• 「自底向上」递推。

可以使用动态规划的解决问题需要具备的三个条件：

• 重复子问题：在计算的过程中，有一些问题会重复计算，必须记住结果。没有重复子问题的话，可以「分而治之」求解；
• 最优子结构：广义上说是「大规模问题的解与小规模问题的解的关系」，不一定需要在求最优解的场景下；
• 无后效性：特别重要，无后效性是设计状态非常重要的思考角度。「无后效性」即当前阶段一旦计算出结果，后面阶段的计算不会修改前面阶段计算出的状态值。整个求解的过程构成「有向无环图」。

动态规划的两个重要概念：

• 状态：记录了解决问题到了哪一步，通常用若干个变量表示；
• 状态转移方程：表达了大规模问题的解与小规模问题的解的关系。

问题分类参考：

• FennelDumplings：力扣上的 DP 问题分类汇总；
• 日沉云起!：leetcode动态规划题目总结。

说明：下面给出的典型问题还会添加（2020 年 12 月 2 日）。

一、入门问题

了解「自顶向下」记忆化递归与「自底向上」递推两种动态规划的方式。

• 第 509 题：斐波拉契数列递归做一定要加缓存，记忆化递归。

二、重复子问题

这部分需要用到「分步计数乘法原理」、「分类计数加法原理」。

第 70 题：和斐波拉契数是同一道问题。计数类问题会用到分类计数原理、分步计数原理。

三、最优子结构

说明：

第 377 题注意甄别不是背包问题。

四、无后效性

练习：

以下是一些「动态规划」经典问题。因为这些问题很重要，所以单独作为一个分类。

五、最大子段和

练习：

六、最长上升子序列

说明：第 300 题是非常经典的动态规划问题。$O(N \log N)$ 的解法，针对问题本身的特点进行状态定义，并证明状态数组是有序数组，降低了时间复杂度。

练习：

七、最长公共子串

八、区间 DP 与划分型 DP

区间 DP：

划分型 DP：

九、树形 DP

第 14 章 动态规划（下）

一、背包问题

背包九讲：https://github.com/tianyicui/pack

（会补充「博弈类型 DP」、「状态压缩 DP」、「数位 DP」等。）

其它问题

第 15 章 贪心算法

第 17 章 哈希表

第 18 章 前缀和与哈希表

第 19 章 广度优先遍历

树的广度优先遍历的一些问题、LeetBook 里的一些问题。

第 20 章 图论算法（最小生成树）

• 文章：最小生成树算法（Prim、Kruskal）；

第 21 章 图论算法（单源最短路径）

• 文章：Dijkstra 算法（解决没有负权边的单源最短路径问题）。

第 22 章 分治算法

分治思想（分而治之）把一个规模较大的问题拆分成为若干个规模较小的相同类型的子问题，然后对这些子问题递归求解，等待每一个子问题完成以后，再得到原问题的解。

分治算法可以并行执行，但是在基础算法领域，分治算法是以 深度优先遍历 的方式执行的。

应用分治思想的典型算法：归并排序、快速排序。

分治思想的典型问题：「剑指 Offer 第 51 题」：《剑指 Offer》 51. 数组中的逆序对（视频讲解）。

其它典型问题（待添加）

还会继续更新，欢迎朋友们多提宝贵意见！