算法通关之路

　　Github 四万星题解，一书深入算法套路

　　这是一本图文并茂的力扣（LeetCode）题解书，旨在让广大读者理解数据结构和算法的必备知识，掌握解决各类经典题目的基本技能，陪伴读者攻克算法难关。
　　本书通过算法题解的形式讲解了基本数据结构和算法知识，包括分治、贪心、回溯和动态规划等算法思想，二分查找、深度优先遍历和广度优先遍历、双指针、滑动窗口、位运算、并查集等解题思路和技巧，以及通用解题“套路”和解题模板等内容，引导读者了解并掌握解决算法题目的方式、方法，旨在循序渐进地提高读者应对算法题目的能力。
　　本书适合数据结构和算法知识的学习者，希望学习如何解算法题或正在刷题的计算机行业从业者，也可作为大、中专院校相关专业的辅导参考书。

　　本书共有5位作者，他们和另外4名审阅者组建了一个小团队，合作完成此书。团队成员大都毕业于985、211院校计算机专业，他们在解算法题、参加算法竞赛和LeetCode周赛等过程中积攒的丰富经验都汇集于此书当中。本书的主要作者、牵头人路志鹏（lucifer）是一位狂热的算法爱好者，他乐于与大家分享算法知识，在GitHub上的题解仓库几年来积攒了超过4万的Star，同时还创办了知名的算法公众号“力扣加加”。

内容简介
前言
作者序
第1章 预备知识
1.1 学习算法需要数学知识吗
1.2 基础数据结构和算法
1.3 复杂度分析
1.3.1 迭代复杂度分析
1.3.2 递归算法复杂度分析
总结
第2章 数学之美
2.1 两数之和
2.2 三数之和
2.3 四数之和
2.4 四数相加II
2.5 最接近的三数之和
2.6 最大子序列和
2.7 最大数
2.8 分数到小数
2.9 最大整除子集
2.10 质数排列
总结
第3章 回文的艺术
3.1 验证回文字符串Ⅱ
3.2 回文链表
3.3 回文数
3.4 最长回文子串
3.5 最长回文子序列
3.6 超级回文数
总结
第4章 游戏之乐
4.1 外观数列（报数）
4.2 24点
4.3 数独游戏
4.4 生命游戏
总结
第5章 深度优先遍历和广度优先遍历
5.1 深度优先遍历
5.2 广度优先遍历
5.3 路径和系列问题
5.3.1 路径总和
5.3.2 路径总和II
5.3.3 二叉树中的最大路径和
5.4 岛屿问题
5.4.1 岛屿数量
5.4.2 岛屿数量II
总结
第6章 二分法
6.1 二分查找
6.2 寻找旋转排序数组中的最小值
6.3 爱吃香蕉的珂珂
6.4 x 的平方根
6.5 寻找峰值
6.6 分割数组的最大值
总结
第7章 位运算
7.1 位1的个数
7.2 实现加法
7.3 整数替换
7.4 只出现一次的数字
总结
第8章 设计
8.1 最小栈
8.2 实现 Trie（前缀树）
8.3 LRU 缓存机制
8.4 LFU 缓存
8.5 设计跳表
总结
第9章 双指针
9.1 头/尾指针
9.1.1 两数相加II
9.1.2 盛水问题
9.2 快慢指针
9.2.1 环形链表
9.2.2 无重复字符串的最长子串
总结
第10章 动态规划
10.1 爬楼梯
10.2 打家劫舍系列
10.2.1 打家劫舍
10.2.2 打家劫舍II
10.3 不同路径
10.4 零钱兑换
10.4.1 零钱兑换
10.4.2 零钱兑换II
总结
第11章 滑动窗口
11.1 滑动窗口最大值
11.2 最小覆盖子串
11.3 替换后的最长重复字符
11.4 字符串的排列
总结
第12章 博弈问题
12.1 石子游戏
12.2 预测赢家
12.3 Nim 游戏
12.4 猜数字大小II
总结
第13章 股票问题
13.1 买卖股票的最佳时机
13.2 买卖股票的最佳时机II
13.3 买卖股票的最佳时机（含手续费）
13.4 买卖股票的最佳时机（含冷冻期）
13.5 买卖股票的最佳时机IV
总结
第14章 分治法
14.1 合并k个排序链表
14.2 数组中的第k个最大元素
14.3 搜索二维矩阵II
总结
第15章 贪心法
15.1 分发饼干
15.2 跳跃游戏
15.3 任务调度器
15.4 分发糖果
15.5 无重叠区间
总结
第16章 回溯法
16.1 组合总和I
16.2 组合总和II
16.3 子集
16.4 全排列
16.5 解数独
总结
第17章 一些有趣的题目
17.1 求众数II
17.2 柱状图中最大的矩形
17.3 一周中的第几天
17.4 水壶问题
17.5 可怜的小猪
总结
第18章 一些通用解题模板
18.1 二分法
18.2 回溯法
18.3 并查集
18.4 BFS
18.5 滑动窗口
18.6 数学
总结
第19章 融会贯通
19.1 循环移位问题
19.1.1 旋转数组
19.1.2 旋转链表
19.2 编辑距离
19.3 第k问题
19.3.1 堆
19.3.2 二分法
总结
第20章 解题技巧和面试技巧
20.1 看限制条件
20.1.1 数据规模
20.1.2 复杂度
20.2 预处理
20.2.1 顺次数
20.2.2 单词接龙
20.3 不要忽视暴力法
20.3.1 统计全为 1 的正方形子矩阵
20.3.2 子串的最大出现次数
20.4 降维与状态压缩
20.5 猜测tag
总结

　　前言
　　作为计算机科学永恒的主题之一，数据结构和算法被誉为程序的灵魂，对其掌握程度往往是衡量一个软件工程师内功的标准。但驾驭数据结构和算法并非易事，除了反复阅读理论知识，借助算法题目进行训练也是学习的必经之路。
　　1.本书的特点
　　本书围绕“做最好的力扣（LeetCode）题解”的指导思想，对力扣（LeetCode）中的经典题目及背后的知识体系进行系统的梳理，依次展开讲解，由浅入深，力求全书内容系统而扼要，分析过程条理清晰，代码实现易读、易学。本书总计20章内容，在深入剖析近百道经典算法题目的过程中，带领读者理解算法知识、总结解题“套路”、掌握通关技巧。希望读者可以通过阅读本书并动手练习，让知识和技能得到质的提升。
　　作为专门针对力扣（LeetCode）题目的题解书，本书对数据结构和算法知识的讲解存在一定的局限性：为了不影响阅读的流畅性，不得不舍弃过于详细的解释证明，对部分知识点的讲解进行精简压缩，力求让内容通俗易懂。我们希望帮助读者奠定数据结构和算法知识的基础，指明方向。在本书的基础上，期望对算法理论进行深入学习的读者可以通过诸如《算法》等工具书，继续探索算法的奥妙。我们也会在第1章详细阐述学习路线。
　　2.读者对象
　　本书适用于如下类型的读者对象。
　　●　你正在学习数据结构和算法，希望边学边实践知识。
　　●　你没有刷过题，但具备一定的数据结构和算法的基础知识。
　　●　你刚开始刷题，希望极大地提升自己的学习效率。
　　●　你在刷题过程中遇到瓶颈，希望得到指引。
　　●　算法爱好者，希望了解更多不一样的思路。
　　对于完全没有接触过数据结构和算法的读者，作者强烈建议你先学习一下基础知识，比如数组、链表、二叉树，以及基础的排序、递归算法，等等。这个过程不需要很长时间，用几天时间了解一下即可。尽管越深入的理论学习对解题的帮助越大，但它们两者的关系是相辅相成的，解题对于巩固理论知识也会很有帮助，千万不要等到认为理论都完全掌握了才开始练习。
　　3.内容介绍
　　作为一本追求覆盖尽量多经典场景、经典问题的算法题解书，制定一种完美的题目编排顺序几乎是不可能的，不同的题目和不同的解题思路构成了网状的联系，很难做出取舍，因此，本书根据题目场景、算法思想、解题“套路”等主要特点将近百道算法题分散在了20章内容之中，它们并没有按照特定的顺序进行编排，读者可以根据自己的兴趣来挑选阅读。对于希望由易到难、循序渐进进行阅读的读者来说，下面的介绍可以作为一个阅读参考。
　　本书的20章内容总体可以被分为四大类别。
　　第一类是算法基础知识，包括第1章预备知识、第2章数学之美，旨在进行知识铺垫，解答一些读者关注较多的问题。
　　第二类是算法思想和算法技巧，这是涉及内容最多的一个类别。第6章二分法和第14章分治法可以被看作对分治思想的实践；第9章双指针和第11章滑动窗口主要讲解了使用指针的技巧；第7章位运算旨在引导读者从二进制的角度思考问题；还有一些非常经典的算法思想，由易到难来看，包括第15章贪心法、第5章深度优先遍历和广度优先遍历、第16章回溯法、第10章动态规划。
　　第三类是经典算法问题，这些题目可能与某种具体的算法无关，但这些解题场景可以帮助读者在解答类似题目时拓展思路。其主要包括第3章回文的艺术、第4章游戏之乐、第8章设计、第12章博弈问题、第13章股票问题和第17章一些有趣的题目。
　　最后一类是解题“套路”，顾名思义，这一类内容为读者总结了不少解题的模板和“套路”，包括第18章一些通用解题模板、第19章融会贯通、第20章解题技巧和面试技巧。
　　4.配套资源
　　本书中的源码使用Python语言编写，但为了方便读者学习、参考，书中每一段代码都给出了多种语言的实现，请通过本书的官方网站leetcode-solution（cn域名）访问查看，目前已涵盖Java语言、Python语言和C++语言相关的版本，我们会根据读者的反馈增加更多具体实现。
　　本书也提供了读者交流群，读者之间及读者和作者之间能够在这里进行有意义的交流，获得远超图书内容本身的学习体验。本书还在相应位置提供了参考链接以方便读者更好地了解书中提到的相关技术。
　　请在本书封底的“读者服务”处获取官方网站的地址、读者交流群二维码及相关参考链接。
　　5.本书的约定
　　本书使用不同的字体区分代码和一般正文内容，对重要的概念会进行加粗。
　　本书章节之间并没有逻辑上的先后顺序，读者可以根据自己的实际情况进行选择阅读。对于知识间有依赖关系的章节，我们会在具体位置给出指引，便于读者查阅其他相关章节的内容。每一章会尽量使用本章所要论述的算法来解题，但这也导致针对部分题目给出的解法有可能并不是最优的，这一点需要特别注意。
　　除个别证明过程较为复杂的解法没有进行说明外，大多数题目会有复杂度说明，另外，提交可能会超时的题解会在标题上注明。
　　6.写在最后
　　为了让读者深入理解基本知识，掌握基本技能，在撰写本书的过程中，每一道题解都经过多位作者和审阅者的把关，他们不仅在专业性方面下足了功夫，更是从读者的角度反复揣摩。希望本书对读者的学习有所帮助，成为读者掌握数据结构和算法知识的奠基石、解题过程中的助推器。能够帮助读者解决学习和工作中遇到的问题，将是作者的荣幸。由于作者能力有限，本书难免存在不足之处，希望读者不吝赐教。
　　7.致谢
　　为本书做出直接贡献的人很多，除几位作者外，还要感谢侯佳琳、李荣新、樊恒岩和王一村的耐心审阅。没有你们，就没有本书的出版。
　　感谢本书的编辑，你每次审稿都非常耐心，让我们一点点看到了出版的希望。
　　最后，感谢我们的家人，没有你们的支持，我们可能无法坚持下来。

　　第1章　预备知识
　　在正式开始学习本书之前，需要一点预备知识，来帮助我们更好地学习。这些知识包括如下内容。
　　●　一门编程语言，最好对Python语言有所了解。本书的代码采用Python语言编写，当然不了解Python语言也没关系，书中的每一段代码，作者都使用了多种语言来实现，读者可以到本书的官方网站（leetcode-solution，cn域名）免费查看和获取。另外，本书只用到了Python语言的一小部分，并且尽量不使用语言特有的API，以减轻读者的语言认知负担。
　　●　基础的数据结构和算法知识。本书主要围绕力扣（LeetCode）上那些经典、高频的题目进行讲解，帮助读者建立系统的知识体系，更有效率地刷题，因此读者需要提前掌握基础的数据结构和算法知识，了解数组、链表、队列、栈、树等数据结构，对二分法、分治法、动态规划、回溯法等要有一个简单的认识。本书将在1.2节对基础的数据结构和算法知识进行梳理。
　　●　对算法复杂度的分析。要想真正分析透一道算法题目，一定要对其复杂度了如指掌。关于如何分析一个算法的复杂度，本书将在1.3节复杂度分析部分进行讲解。
　　1.1　学习算法需要数学知识吗
　　首先来看一个读者问的比较多的问题，学习算法需要数学知识吗？
　　不得不承认学习算法确实需要一些数学知识。除了实现某种具体的算法，后面讲到的复杂度分析也需要一些数学知识。
　　不过这些内容涉及的数学知识大多比较简单，一般不会涉及高等数学的内容。其实学习大部分的算法知识，尤其是解力扣（LeetCode）题目，并不需要你在高等数学、几何学、概率统计等方面有多深的造诣，掌握基础的数学知识，具备逻辑分析的能力足矣。当然如果你要从事算法岗位或者进行理论研究，情况会有所不同，不过这不在本书的讨论范围内。
　　个别题目的复杂度分析特别难，比如本书个别回溯类型的题目，通常对于这种题目的复杂度，大家只需要知道大致量级即可。
　　退一步讲，面对一道数学题目，即便我们无法借助数学思维解决，通常来说，也可以采用变通的方式来解决，比如力扣（LeetCode）有一道水壶倒水的问题：
　　给你一个 8L 的装满水的水壶和两个分别是5L、3L的空壶，请想出一个“优雅”的办法，使其中一个水壶恰好装4L水，每一步操作只能是倒空或倒满。
　　这道题可以运用最大公约数（Greatest Common Divisor，GCD）定理解决，想不到这一点也没有关系，我们也可以通过广度优先遍历（Breadth First Search，BFS）来解决。
　　1.2　基础数据结构和算法
　　力扣（LeetCode）是世界上最知名的编程技能练习网站，支持用户在线使用C、C++、Java、Python、JavaScript等十几种编程语言解决超过1000道编程题目。除了考查对编程语言的掌握程度，力扣（LeetCode）题目的核心目的是对答题者数据结构和算法水平的考验。掌握基础的数据结构和算法，是刷题的必要条件。
　　从广义上来说，数据结构是数据的存储结构，算法是操作数据的方法。平时我们探讨时使用的是更为狭义的概念，特指某些具体种类的数据结构和算法，例如数组、链表、栈、队列等数据结构，又如二分法、动态规划、快速排序等经典算法。
　　数据结构是为算法服务的，算法通常也要建立在某一种或几种数据结构之上才可以发挥作用，两者之间是相辅相成的关系。相信读完本书后，你会对这句话有更为深刻的理解。
　　下面罗列了常见的数据结构、算法思想和算法技巧。牢固地掌握这些基础的数据结构和算法知识，可以让你刷题时事半功倍，学习更为复杂的算法时也能得心应手。
　　●　常见的数据结构：数组、栈、队列、链表、二叉树、散列表、图。
　　●　常见的算法思想：分治、贪心、回溯、动态规划。
　　●　常见的算法技巧：二分法、排序、双指针、滑动窗口、并查集、深度优先遍历和广度优先遍历等。
　　相信通过阅读、学习本书，读者将逐渐掌握和巩固这些知识。牢固掌握这些基础的数据结构和算法，刷题才会事半功倍，学习更为复杂的算法也能得心应手。力扣（LeetCode）的题目虽然不断出新，但是最终用到的算法思想永远是那么几个，很多题目都是“新壶装旧酒”，即在原有的题目基础上做适当的扩展（比如两数和、两数和II、三数和、四数和，等等）或者改造，使你不能一下子看出问题的本质。
　　希望读者对以上内容有一个初步的认知，然后结合本书所讲的知识进行加强与巩固。