大家好，这里是一个算法学习的小教程。可以帮助新手朋友们入门「算法与数据结构」。

• 特别感谢 @AbbyDeng 同学的更名建议；

• 本项目是我在学习《算法与数据结构》的时候，在 LeetCode（力扣） 上做的练习，目前主要提供 Java 语言，Python 语言会写一些；

• 本项目可以认为是一个《算法与数据结构》的简易教程，适用于零基础和转行的同学；

• 适用于准备算法面试，不适合于准备算法竞赛；

• 所有的代码都通过 LeetCode（力扣） 在线测评系统检测；

• 建议您安装 Octotree 插件，以获得最佳的阅读体验。

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

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

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

讲解如有错误，欢迎指正！

我的 LeetBook 是收费教程，投入精力与平时写题解是一样的，只不过 LeetBook 在制作图表上会更细致一点，并且有「力扣」的工作人员和高手参与制作和审核。不排除平时写的题解知识点比 LeetBook 还要多的情况。

以下原来是写在「力扣」主页里的，由于要配合「力扣」的工作，因此写在了这里。

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

感谢负雪明烛和二哥组织建群。

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

说明：

• 该 LeetBook 的前两章（ 时间复杂度、二分查找）是免费阅读的，后面的章节 需要付费 观看（非会员价 99 元，会员价 69 元，可以点击下面图片浏览课程目录）。付费内容是：制作教程的时间精力付出，还含有其他工作人员的时间和努力、有针对性的答疑和帮助；
• 中、高阶用户请谨慎购买；
• 我所讲解的知识在我曾经向大家推荐的书籍，我写的博客和笔记里都有，已经发布的题解、博客、笔记都会一直共享，并且只要我有时间和精力，我还会坚持做分享和答疑；
• 免费题解和 LeetBook 在制作上是完全一样的，我都投入了同样的精力和时间，LeetBook 的内容制图和审核都由「力扣」的工作人员完成，阅读体验会更好一些；
• 可以在站内或者是我的其他社交账号向我咨询课程内容。不管是否购买课程，我都会尽量回答我所知道的问题（时间允许，能力范围之内）。感谢大家一直以来，一如既往对我的支持。有建议和意见也欢迎大家与我交流；
• 很感谢「力扣」给我机会做课程的机会，帮助我完成当教师这一小小心愿。

说明：题目分类与我的 LeetBook 章节对应，LeetBook 的课程标题、例题、练习都是公开的。

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

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

• 重点问题

说明：

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

练习：

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

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

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

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

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

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

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

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

说明：

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

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

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

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

public class Solution {

    public String minWindow(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 题，收集符合条件的语句不一样而已。

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

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

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

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

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

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

说明：

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

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

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

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

说明：

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

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

练习：

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

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

说明：

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

练习：

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

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

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

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

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

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

选做问题：

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

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

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

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

说明：

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

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

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

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

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

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

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

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

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

问题分类参考：

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

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

• 第 509 题：斐波拉契数列递归做一定要加缓存，记忆化递归；
• 第 70 题：和斐波拉契数是同一道问题。

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

练习：

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

练习：

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

练习：

区间 DP：

划分型 DP：

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

树状数组、线段树、背包问题、并查集、第 128 题

其它典型问题（待添加）