算法分类

常见算法
1.贪心
2.动态规划
3.数学知识
4.搜索与图论
5.数据结构
6.字符串
7.二叉树
8.排序算法
9.二分算法
10.双指针/滑动窗口
11.位运算
12.模拟
13.枚举
14.递推与递归
15.算法技巧：高精度、前缀和与差分、离散化、区间合并、方向数组
16.杂题
17.总结

经验之谈

1.数组/单链表系列算法

双指针
二分搜索
滑动窗口
回文串
前缀和与差分数组

先学习像数组、链表这种基本数据结构的常用算法，比如单链表翻转，前缀和数组，二分搜索等

因为这些算法属于会者不难难者不会的类型，难度不大，学习它们不会花费太多时间。而且这些小而美的算法经常让你大呼精妙，能够有效培养你对算法的兴趣。

单链表常考的技巧就是双指针，后文单链表六大技巧全给你总结好了，这些技巧就是会者不难，难者不会。

比如判断单链表是否成环，拍脑袋的暴力解是什么？就是用一个 HashSet 之类的数据结构来缓存走过的节点，遇到重复的就说明有环对吧。但我们用快慢指针可以避免使用额外的空间，这就是聪明地穷举嘛。

当然，对于找链表中点这种问题，使用双指针技巧只是显示你学过这个技巧，和遍历两次链表的常规解法从时间空间复杂度的角度来说都是差不多的。

首先说二分搜索技巧，可以归为两端向中心的双指针。如果让你在数组中搜索元素，一个 for 循环穷举肯定能搞定对吧，但如果数组是有序的，二分搜索不就是一种更聪明的搜索方式么。

后文二分搜索框架详解给你总结了二分搜索代码模板，保证不会出现搜索边界的问题。后文二分搜索算法运用给你总结了二分搜索相关题目的共性以及如何将二分搜索思想运用到实际算法中。

类似的两端向中心的双指针技巧还有力扣上的 N 数之和系列问题，后文一个函数秒杀所有 nSum 问题讲了这些题目的共性，甭管几数之和，解法肯定要穷举所有的数字组合，然后看看那个数字组合的和等于目标和嘛。比较聪明的方式是先排序，利用双指针技巧快速计算结果。

**再说滑动窗口算法技巧**，典型的快慢双指针，快慢指针中间就是滑动的「窗口」，主要用于解决子串问题。

文中最小覆盖子串这道题，让你寻找包含特定字符的最短子串，常规拍脑袋解法是什么？那肯定是类似字符串暴力匹配算法，用嵌套 for 循环穷举呗，平方级的复杂度。

而滑动窗口技巧告诉你不用这么麻烦，可以用快慢指针遍历一次就求出答案，这就是教你聪明的穷举技巧。

但是，就好像二分搜索只能运用在有序数组上一样，滑动窗口也是有其限制的，就是你必须明确的知道什么时候应该扩大窗口，什么时候该收缩窗口。

比如后文最大子数组问题面对的问题就没办法用滑动窗口，因为数组中的元素存在负数，扩大或缩小窗口并不能保证窗口中的元素之和就会随着增大和减小，所以无法使用滑动窗口技巧，只能用动态规划技巧穷举了。

还有回文串相关技巧，如果判断一个串是否是回文串，使用双指针从两端向中心检查，如果寻找回文子串，就从中心向两端扩散。后文最长回文子串使用了一种技巧同时处理了回文串长度为奇数或偶数的情况。

当然，寻找最长回文子串可以有更精妙的马拉车算法（Manacher 算法），不过，学习这个算法的性价比不高，没什么必要掌握。

**最后说说前缀和技巧和差分数组技巧**。

如果频繁地让你计算子数组的和，每次用 for 循环去遍历肯定没问题，但前缀和技巧预计算一个 preSum 数组，就可以避免循环。

类似的，如果频繁地让你对子数组进行增减操作，也可以每次用 for 循环去操作，但差分数组技巧维护一个 diff 数组，也可以避免循环。数组链表的技巧差不多就这些了，都比较固定，只要你都见过，运用出来的难度不算大，下面来说一说稍微有些难度的算法。

2.二叉树系列算法

二叉树
回溯/DFS（遍历一遍二叉树得到答案）
动态规划（通过分解问题计算出答案）
分治
BFS
剪枝/备忘录（减少冗余计算、提高效率）

学会基础算法之后，不要急着上来就刷回溯算法、动态规划这类笔试常考题，而应该先刷二叉树，先刷二叉树，先刷二叉树，重要的事情说三遍。对于畏惧算法的同学来说，可以先刷树的相关题目，试着从框架上看问题，而不要纠结于细节问题。

学完基本算法之后，建议从「二叉树」系列问题开始刷，结合框架思维，把树结构理解到位，然后再去看回溯、动规、分治等算法专题，对思路的理解就会更加深刻。

为什么要先刷二叉树呢，因为二叉树是最容易培养框架思维的，而且大部分算法技巧，本质上都是树的遍历问题。

对于一个理解二叉树的人来说，刷一道二叉树的题目花不了多长时间。那么如果你对刷题无从下手或者有畏惧心理，不妨从二叉树下手，前 10 道也许有点难受；结合框架再做 20 道，也许你就有点自己的理解了；刷完整个专题，再去做什么回溯动规分治专题，你就会发现只要涉及递归的问题，都是树的问题。

老读者都知道，二叉树的重要性我之前说了无数次，因为二叉树模型几乎是所有高级算法的基础，尤其是那么多人说对递归的理解不到位，更应该好好刷二叉树相关题目。

**二叉树题目的递归解法可以分两类思路，第一类是遍历一遍二叉树得出答案，第二类是通过分解问题计算出答案，这两类思路分别对应着回溯算法核心框架和动态规划核心框架**。

什么叫通过遍历一遍二叉树得出答案？

前文讲回溯算法的时候就告诉你回溯算法本质就是遍历一棵多叉树，连代码实现都如出一辙有没有？

而且我之前经常说，回溯算法虽然简单粗暴效率低，但特别有用，因为如果你对一道题无计可施，回溯算法起码能帮你写一个暴力解捞点分对吧。

那什么叫通过分解问题计算答案？

同样是计算二叉树最大深度这个问题，你也可以写出下面这样的解法：

你看这段代码，有没有觉得很熟悉？有没有觉得有点动态规划解法代码的形式？

不信你看动态规划核心框架中凑零钱问题的暴力穷举解法：

当然，动态规划系列问题有「最优子结构」和「重叠子问题」两个特性，而且大多是让你求最值的。很多算法虽然不属于动态规划，但也符合分解问题的思维模式。

比如分治算法详解中说到的运算表达式优先级问题，其核心依然是大问题分解成子问题，只不过没有重叠子问题，不能用备忘录去优化效率罢了。

当然，除了动归、回溯（DFS）、分治，还有一个常用算法就是 BFS 了，后文 BFS 算法核心框架就是根据下面这段二叉树的层序遍历代码改装出来的：

更进一步，图论相关的算法也是二叉树算法的延续。

比如图论基础，环判断和拓扑排序和二分图判定算法就用到了 DFS 算法；再比如 Dijkstra 算法模板，就是改造版 BFS 算法加上一个类似 dp table 的数组。

好了，说的差不多了，上述这些算法的本质都是穷举二（多）叉树，有机会的话通过剪枝或者备忘录的方式减少冗余计算，提高效率，就这么点事儿。

3.最后总结

说到底我还是希望爱思考的读者能培养出成体系的算法思维，最好能爱上算法，而不是单纯地看题解去做题，授人以鱼不如授人以渔嘛。

算法真的没啥难的，只要有心谁都可以学好。分享是一种美德，如果本文对你有启发欢迎分享给需要的朋友。

做题规划

剑指offer专项突击

题目数量：

001~006（5）：整数
007~013（7）：数组
014~020（7）：字符串
021~029（9）：链表
030~035（6）：哈希表
036~040（5）：栈
041~046（6）：队列
047~058（12）：树
059~061（3）：堆
062~067（6）：前缀树
068~073（6）：二分查找
074~078（5）：排序
079~087（9）：回溯法
088~104（17）：动态规划
105~119（15）：图

题目评分：

难度1：简单题、难度2：有点意思、难度3：特殊值得注意、难度4：多解法

时间	题目清单	考勤
2023.7.13		完成
2023.7.14
2023.7.15
2023.7.16
2023.7.17
2023.7.18
2023.7.19
2023.7.20
2023.7.21
2023.7.22
2023.7.23
2023.7.24
2023.7.25
2023.7.26
2023.7.27
2023.7.28
2023.7.29
2023.7.30
2023.7.31
2023.8.1
2023.8.2
2023.8.3
2023.8.4
2023.8.5
2023.8.6
2023.8.7
2023.8.8
2023.8.9
2023.8.10
2023.8.11
2023.8.12
2023.8.13
2023.8.14