良好风格的 LeetCode 解决方案
1.0.0
This document provides a comprehensive overview of LeetCode-Solutions-in-Good-Style, a resource offering beginner-friendly tutorials and video solutions for algorithm and data structure problems. It features a structured approach with clear code, detailed explanations, and focuses on building a strong understanding of fundamental concepts rather than competitive coding.
LeetCode-Solutions-in-Good-Style
说明：我和绝大多数同学一样，一边学习、一边总结。我会争取做更多的分享，给大家带来一些有用的知识，感谢大家一直以来的支持。
大家好，这里是一个《算法与数据结构》的入门级教程，适用于算法零基础和转行同学，不适合于准备算法竞赛。想传递的观点是：写逻辑清楚的代码，所以我写的代码一定经过了严格的思考，格式非常标准，不带有个人风格，不会为了缩减代码行数而少写一个空行和注释。在这里：
可以叫我 weiwei，在我力所能及且时间允许的情况下，我会尽可能回答我知道的问题。如果有不能及时回复的问题，可能是因为我没有看到站内通知，可以发邮件给我 [email protected] 。
我录制的视频题解
我从 2019 年 9 月开始录制视频题解。最开始的时候，我会对着要讲的材料录好几遍。现在讲解知识点的时候写逐字稿。已经沉淀了很多视频，其实也算是一个小小的体系课程，现在罗列在这里，希望能够对大家有所帮助。
0. 算法新手如何刷力扣（LeetCode）？【干货分享】
1. 时间复杂度与空间复杂度
这个视频提到了时间复杂度是一个渐进概念，需要用动态的角度去理解。并且讲解了时间复杂度的严格定义（极限形式），以便大家理解时间复杂度的计算规则。并且还指出了：时间复杂度不是程序的运行时间；应该使用「空间换时间」，更多关注在优化「时间复杂度」。
2. 二分查找
这个视频介绍了如何写对二分查找算法，二分查找的细节虽然多，但只要我们掌握了正确的解题思路，并且多加练习、勤于思考、多做总结，写对二分查找的问题就不再困难。
下面的视频讲解了几道二分查找的例题，我们重点分析了题意和如何利用题目中给出的条件逐渐缩小搜索区间。
我们通过「力扣」第 4 题（寻找两个正序数组的中位数）的分析，向大家介绍了这样的技巧：如果要找的目标元素的性质比较复杂，可以对这条性质取反，进而写出可以简单的可以缩减问题区间的逻辑语句。
3. 和排序相关的问题
「归并排序」和「快速排序」是非常重要的排序算法，深刻理解它们对于理解「递归」函数的运行机制有着非常大的帮助，同时它们也是「分治思想」的典型应用。「逆序对」和「荷兰国旗问题（颜色分类）」也是非常经典的算法问题。
计算「逆序对」完全就是按照「归并排序」的思路而来。
在「颜色分类」问题的讲解中，我们向大家介绍了「循环不变量」，在编写代码的过程中，我们应该一直遵守所使用的变量的语义，在「程序执行前」「执行过程中」「执行结束」以后保持不变。遵守我们自己定义「循环不变量」是我们写对正确代码的重要方法。
「缺失的第一个正数」是一个经典的算法问题，用到的思想是「原地哈希」，可以理解为是「桶排序」算法的特殊应用：一个萝卜一个坑，一个桶里只存放一个元素。要和大家强调的是，可以这样做是和输入数组的元素的数值密切相关。
4. 滑动窗口
「滑动窗口」问题是典型的应用「循环不变量」解决的问题，比较考验我们编码和调试的能力。
5. 栈相关的问题
使用「栈」解决的问题，需要我们通过具体例子，发现解决它们正好符合「后进先出」的规律：
掌握下面这两个问题，离不开对具体例子的研究，进而归纳出一般规律。
「栈」最为广泛的一种应用就是作为「递归」「深度优先遍历」「分治算法」的数据结构支持。
6. 并查集
「并查集」这个数据结构目前来说在面试中出现比较少，如果是准备算法面试的朋友，可以跳过。
7. 树
树的问题很多都可以使用「深度优先遍历」或者「广度优先遍历」去做。
8. 回溯算法
「回溯算法」其实就是对题目中所蕴含的「树形结构」执行一次 深度优先遍历。做这一类问题，在草稿纸上画出树形结构图很重要。
9. 动态规划
10. 广度优先遍历与拓扑排序
11. 哈希表
12. 位运算相关
我的个人网站和算法学习笔记
微信群与 QQ 群
如果需要一起刷题的朋友，可以加入微信群和 QQ 群。
我的 LeetBook
这里给自己做一个宣传，我最近在「力扣」上推出了自己的 LeetBook：零起步学算法（原名《使用「力扣」学习算法与数据结构》），主要面向 转行 、零基础 的朋友，讲解算法与数据结构的基础知识。
说明：
该 LeetBook 的前两章（ 时间复杂度、二分查找）是免费阅读的，后面的章节 需要付费 阅读，非会员价 99 元，会员价 69 元，您当前看到的主页目录与 LeetBook 是一样的，只有多出来的部分，不会更少；
LeetBook 的课程标题、例题、练习、配套代码仓库（就是您当前看到的这个仓库）是完全公开的，如果 LeetBook 里设计的内容（包括练习）您已经掌握，就不太建议购买；
投入精力与平时写题解是一样的，只不过 LeetBook 在制作图表上会更细致一点。付费内容是：制作教程的时间精力付出、「力扣」的工作人员和高手参与制作和审核，阅读体验会更好一些。不排除平时写的题解知识点比 LeetBook 还要多；
中、高阶用户请谨慎购买；
可以在「力扣」站内或者是我的其他社交账号向我咨询课程内容，也可以向本仓库提 issue。不管是否购买课程，我都会尽量回答我所知道的问题（时间允许，能力范围之内）。感谢大家一直以来，一如既往对我的支持。有建议和意见也欢迎大家与我交流；
我所讲解的知识在我曾经向大家推荐的书籍，我写的博客、题解和笔记里都有，已经发布的题解、博客、笔记都会一直共享，并且只要我有时间和精力，我还会坚持做分享和答疑；
很感谢「力扣」给我机会做课程的机会，帮助我完成一个小小心愿。
「力扣」分类以及题解目录（按照 LeetBook 的章节编排，第 16 章以后为目前 LeetBook 不包含的章节）
说明：题目分类与我的 LeetBook 章节对应。
第 1 章 时间复杂度
这部分内容介绍了 时间复杂度 这个概念，可以收看 【视频讲解】 ，完全免费。 这一章节没有练习。
第 2 章 二分查找
题型一：二分求下标
说明：
练习：
题型二：二分确定一个有范围的整数（二分答案）
算法思想：减而治之。如果题目要我们找一个整数，这个整数有确定的范围，可以通过二分查找逐渐缩小范围，最后逼近到一个数。
题型三：复杂的判别函数（最大值极小化问题）
说明：这一类问题本质上还是「题型二」（二分答案），但是初学的时候会觉得有一些绕。这一类问题的问法都差不多，关键字是「连续」、「正整数」，请大家注意捕捉题目中这样的关键信息。
第 3 章 基础排序算法
这一部分包含了四种基础排序算法：选择排序、插入排序、希尔排序、冒泡排序。
「力扣」第 912 题：排序数组 的 题解：总结了排序问题的一些要点和学习资料，可以从排序问题开始学习算法。
数组的问题可以作为算法「新手场」，因为这些问题只需要掌握编程语言的基础知识就可以完成。以下问题都很容易想到解决方案，即使没有学习过相关的数据结构和算法知识。
知识点：循环不变量
第 4 章 高级排序算法（重要）
这一部分需要重点掌握三种高级排序算法：归并排序、快速排序、堆排序。
说明：
第 5 章 非比较排序（选学）
这一部分包含了三种非比较排序排序：计数排序、基数排序、桶排序。解决这些问题需要知道 原地哈希 这个概念。
第 6 章 滑动窗口与双指针
一、滑动窗口
滑动窗口的参考写法（不是模板，请不要原样照搬，仅供参考，理解算法设计思想是更重要的）：
友情提示：第 3 题和第 76 题是必须要会做的基本问题。上面的问题理解透彻了，下面的问题就可以比较轻松地做出来。
重点问题：
说明：
练习：
说明：
第 209 题：题目中给出的关键信息：数组里的元素全部是正整数。一共有以下 3 种方法。
方法一：暴力解法
方法二：滑动窗口（分析可以使用滑动窗口的原因）
方法三：构造前缀和数组，然后使用二分查找
第 438 题：同第 76 题；
第 567 题：同第 76 题，收集符合条件的语句不一样而已。
二、双指针
「双指针」问题其实也是朴素算法的优化，一下子排序掉很多不符合题意的解，「滑动窗口」技巧也是这样的。依然是分析为什么可以使用双指针是更重要的。
二分查找算法应用于查找下标也可以认为是双指针的解法。
第 7 章 链表
解决链表问题，很实用的技巧是「画图」。其它算法问题的分析和讲解（和面试官讲解）也是这样。
可以为链表编写测试函数，方便调试。建议实现的方法有：① 通过数组创建一个单链表；② 根据当前结点打印当前结点以及后面的结点。这两个方法可以非常方便地帮助我们调试关于链表的程序。
题型一：基本的链表指针指向问题
注意：有一些问题需要使用「虚拟头结点」，以避免对链表第一个结点的复杂的分类讨论逻辑。这个思想在数组里我们见过，叫「哨兵」。
使用递归函数，避免复杂的更改指针变量指向操作，使得求解问题变得简单。
说明：
题型二：快慢指针技巧
确切地说，叫「同步指针」可能更好一些。
使用两个指针变量，刚开始都位于链表的第一个结点，一个永远一次只走一步，另一个永远一次只走两步，一个在前，一个在后，同时走。这样当快指针走完的时候，慢指针就来到了链表的中间位置。
解决这些问题的共同特点就是使用两个指针变量同步移动。快慢指针的前进方向相同，且它们步伐的「差」是恒定的，根据这种确定性去解决链表中的一些问题。使用这种思想还可以解决链表的以下问题：
说明：
题型三：设计数据结构
第 8 章 栈与队列
一、栈
题型一：基本的使用栈解决的问题
下面的问题非常基础，一定需要掌握：
练习：
题型二：单调栈
单调栈就是普通的栈，在使用的过程中恰好符合了「后进先出」，栈内元素单调的特点。「单调栈」和「单调队列」的问题通常来说很特殊，掌握例题和一些练习就可以了。
经验：单调栈中一般存下标。
说明：
练习：
二、队列
题型一：基本的使用队列解决的问题
所有的使用广度优先遍历解决的问题，都使用了队列。
题型二：单调队列
单调队列就是普通的队列。「力扣」上的单调队列目前就发现这一个问题，关键分析清楚为什么设计的算法恰好使得单调队列。另外，「背包问题」中有使用单调队列进行优化的例子，感兴趣的朋友可以了解一下，是竞赛方面的知识。
经验：单调队列中一般存下标。
第 9 章 优先队列
说明：了解「堆」作为「优先队列」的实现是有必要的，有助于理解 remove() 、replace() 这些编码的细节，使用堆的时候才会更加有效。
应用：动态 选取当前队列中优先级最高的元素，重点理解「动态」的含义。
第 10 章 并查集
并查集知识点的【视频讲解】在第 990 题视频题解里有。基础且常见的问题有：
选做问题：
第 11 章 树（二叉树与二分搜索树）
第 12 章 回溯算法
题型一：基本回溯问题
通过这些问题理解回溯算法的思想，回溯算法的知识点讲解在「力扣」第 46 题的视频题解和文字题解。
回溯就是用深度优先遍历的方式去搜索 树（图）的所有解。深度优先遍历有很明显的递归结构。
做对下面这些问题的技巧：① 画图、画图、画图；② 理解深度优先遍历与递归；③ 多调试、多调试。
题型二：字符串上的回溯问题
重点理解：由于字符串每次都生成新字符，无须状态重置。
题型三：Flood Fill
题型四：一些游戏问题
说明：
第 13 章 动态规划（上）
动态规划的两个重要思想：
动态规划的两个思考方向：
可以使用动态规划的解决问题需要具备的三个条件：
动态规划的两个重要概念：
问题分类参考：
说明：下面给出的典型问题还会添加（2020 年 12 月 2 日）。
一、入门问题
了解「自顶向下」记忆化递归与「自底向上」递推两种动态规划的方式。
二、重复子问题
这部分需要用到「分步计数乘法原理」、「分类计数加法原理」。
第 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 章 图论算法（最小生成树）
第 21 章 图论算法（单源最短路径）
第 22 章 分治算法
分治思想（分而治之）把一个规模较大的问题拆分成为若干个规模较小的相同类型的子问题，然后对这些子问题递归求解，等待每一个子问题完成以后，再得到原问题的解。
分治算法可以并行执行，但是在基础算法领域，分治算法是以 深度优先遍历 的方式执行的。
应用分治思想的典型算法：归并排序、快速排序。
分治思想的典型问题：「剑指 Offer 第 51 题」：《剑指 Offer》 51. 数组中的逆序对（视频讲解）。
其它典型问题（待添加）
还会继续更新，欢迎朋友们多提宝贵意见！
