0 九阳神功入门:十大排序算法 程序员内功
排序算法是基础中的基础，所以必须得掌握
速记口诀:
快选堆归希
桶记泡插基
不稳定排序4个
希尔快速选择堆
这十大排序要搞清楚，也非常不容易:需要下苦功夫
二分查找 树的中序遍历，树的前序，树的后续
0.1 排序题引论
思路:手写快速排序，然后使用数学定义来判断是不是等差数列
快排的注意点:
While()嵌套while,记得弄完需要自减和自加，非常重要
0.2 快速排序 树的前序 (重点)
0.3 归并排序 树的后续排列 (重点)
0.4
0.5 冒泡排序 (简单排序)
0.6 插入排序
0.7 选择排序
0.8 非递归实现前序遍历
1 九阳神功入门:递归思想
1.1 递归介绍
递归是一种编程技巧，一种解决问题的思维方式:严格来说，递归并不是一种算法。简单的说，就是如果在函数中存在着调用函数本身的情况，这种现象就叫递归
递归的思想就是，将大问题分解得足够小，不用继续分解，可以直接计算结果为止
如果把这个一层一层的分解过程画成图，它其实就是一棵树。我们给这棵树起一个名字，叫作递归树。以斐波那契数列为例
public class solution{
public int fib(int N){
if(N <= 1){
return N;
}
return fib(N-1)+fib(N-2);
}
}
1.2 基本步骤
- 定义一个函数，明确函数功能
- 寻找问题与子问题之间的关系(递推公式)
- 将地推公式在定义的函数中实现
- 推导时间复杂度，判断是否可以接受，无法接受更换算法
1.3 代表题目
1.3.1 爬楼梯(#70)
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。
示例 1：
输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶
示例 2：
输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶
解题思路：
我们用 f(x)f(x)f(x) 表示爬到第 xxx 级台阶的方案数，考虑最后一步可能跨了一级台阶，也可能跨了两级台阶，所以我们可以列出如下式子：
f(x)=f(x−1)+f(x−2)f(x) = f(x - 1) + f(x - 2) f(x)=f(x−1)+f(x−2)
它意味着爬到第 xxx 级台阶的方案数是爬到第 x−1x - 1x−1 级台阶的方案数和爬到第 x−2x - 2x−2 级台阶的方案数的和。很好理解，因为每次只能爬 111 级或 222 级，所以 f(x)f(x)f(x) 只能从 f(x−1)f(x - 1)f(x−1) 和 f(x−2)f(x - 2)f(x−2) 转移过来，而这里要统计方案总数，我们就需要对这两项的贡献求和。
以上是动态规划的转移方程，下面我们来讨论边界条件。我们是从第 000 级开始爬的，所以从第 000 级爬到第 000 级我们可以看作只有一种方案，即 f(0)=1f(0) = 1f(0)=1；从第 000 级到第 111 级也只有一种方案，即爬一级，f(1)=1f(1) = 1f(1)=1。这两个作为边界条件就可以继续向后推导出第 nnn 级的正确结果。我们不妨写几项来验证一下，根据转移方程得到 f(2)=2f(2) = 2f(2)=2，f(3)=3f(3) = 3f(3)=3，f(4)=5f(4) = 5f(4)=5，……，我们把这些情况都枚举出来，发现计算的结果是正确的。
我们不难通过转移方程和边界条件给出一个时间复杂度和空间复杂度都是 O(n)O(n)O(n) 的实现，但是由于这里的 f(x)f(x)f(x) 只和 f(x−1)f(x - 1)f(x−1) 与 f(x−2)f(x - 2)f(x−2) 有关，所以我们可以用「滚动数组思想」把空间复杂度优化成 O(1)O(1)O(1)。下面的代码中给出的就是这种实现
class Solution {
public int climbStairs(int n) {
int p = 0, q = 0, r = 1;
for (int i = 1; i <= n; ++i) {
p = q;
q = r;
r = p + q;
}
return r;
}
}
1.3.2 青蛙跳台阶(#面试题10-II)
1.3.3 斐波那契数列(#509)
1.4 触类旁通
1.4.1 反转二叉树
1.4.2 路径总和
给你二叉树的根节点 root 和一个表示目标和的整数 targetSum ，判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。
叶子节点 是指没有子节点的节点。
示例 1：
输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
输出：true
示例 2：
输入：root = [1,2,3], targetSum = 5
输出：false
示例 3：
输入：root = [1,2], targetSum = 0
输出：false
1.4.3 细胞分裂
2 九阳神功入门:分治策略(递归的孪生兄弟)
3 九阳神功第一式:单调栈
3.1 单调栈介绍
https://www.jianshu.com/p/43bb5204bc6f
单调栈是一种理解起来很容易，但是运用起来并不那么容易的数据结构。一句话解释单调栈，就是一个堆栈，里面的元素的大小按照他们所在栈内的位置，满足一定的单调性，说直白点，就是递增存储元素或者递减存储元素，当该单调性(递增性或者递减性)被打破时要进行适当出栈，这是该算法的关键。那么到底什么时候用这个单调栈，怎么用单调栈呢。下面我们看几个例子
3.1.1 开胃菜-
谷歌面试题
3.1.2 单调栈的性质
- 单调栈里的元素具有单调性，栈中元素只能单调递增或者单调递减
- 元素加入栈前。会在栈顶端把破坏栈单调性元素都删除;
- 使用单调栈可以找到元素向左遍历第一个比它小的元素，也可以找到元素向右遍历第一个比它大的元素。
最后总结一下单调栈。单调栈这种数据结构，通常应用在一维数组上。如果遇到问题，和前后元素之间的大小关系有关系的话，（例如第一题中我们要找比某个元素大的元素，第二个题目中，前后bar的高低影响了最终矩形的计算），我们可以试图用单调栈来解决。在思考如何使用单调栈的时候，可以回忆一下这两题的解题套路，然后想清楚，如果使用单调栈，每个元素出栈时候的意义。最后的时间复杂度，因为每个元素都出栈入栈各一次，所以是线性时间的复杂度。
3.2 代表题目
3.2.1 柱状图中最大的矩形(#84)
3.2.3 最大的矩形面积(#85)
3.3 触类旁通
每日温度(#739)
思路:该题使用单调栈能够更好的解题
遍历每日温度，维护一个单调栈
1.若栈为空或者当日温度小于栈顶温度则直接入栈；
2.反之，若当日温度小于栈顶温度，说明栈顶元素的升温日已经扎到了，则将栈顶元素出栈，计算其与当日相差的天数即可
此题目要求的是升温的天数，而不是升温后的温度，因此栈中应该存储下标，而不是温度
下一个更大元素II（#503_中等）
接雨水(#42_困难 性能敏感)
股票价格跨度(#901 中等)
滑动窗口最大值(#239_困难)
最大宽度坡(#962)
4 九阳神功第二式:并查集(DSU)
4.1 并查集介绍
武功出处：
并查集顾名思义就是具有”合并集合”和”查找集合中元素”两种操作的一种算法。但是，实际并查集的基本操作有三个:
makeSet(size):建立一个新的并查集，其中包含size个单元素集合。通常该操作比较隐晦，用一句int[] parent = new int[size];直接替换了make set的过程
unionSet(x,y):把元素x和元素y所在的集合合并，要求x和y所在的集合不想交，如果相交则不合并。
Find（x）：找到元素x所在的集合的代表，该操作也可以判断两个元素是否位于同一个集合，只要它们各自的代表比较一下就可以了。Find(x)有两种实现方法，一种是递归，一种是非递归形式。
算法:
用集合中的某个元素来这个集合，该元素称为集合的代表元。一个集合内的所有元素组织成以代表元为根的树形结构。对于每一个元素x来说，parent[x]指向x在树形结构上的父节点，如果x是根节点，则令parent[x] = x.对于查找操作，假设需要确定x所在的集合，也就是确定集合的代表元。可以沿着parent[x]不断在树形结构中向上移动，直到到达根节点。因为创建的树可能会严重不平衡，并查集可以用两种办法优化
并查集两种优化策略:
- 按秩合并 Union by Rank
- 路径压缩
4.2 代表题目:朋友圈(#547)
4.3 触类旁通
5 九阳神功第三式:滑动窗口
6 九阳神功第四式:前缀和&[&哈希表优化]
1.1 前缀和介绍
前缀和(prefix Sum)定义:前缀和是一种重要的预处理，能大大降低查询的时间复杂度。结合Hash缓存，能够进一步提升算法执行效率。
对数组nums进行前缀和初始化需要时间O(n)时间：
新建数组prefixSum,数组长度定义为nums.length+1,确保第nums.length个元素存储了前面0到nums.length-1个元素和。将数组nums的累加依次放入数组prefixSum中
PrefixSum[0] = 0[备注：此处不要定义prefix[0]=nums[0,这种定义违背前缀和的意义]
prefixSum[1] = prefixSum[0] + nums[0] = 0 + nums[0];
…
prefixSum[i] = prefixSum[i-1] + nums[i].
由此推导出两个变换公式:
(1) nums[某一项] = 两个相邻 前缀和 之差
nums[x] = prefixSum[x] – prefixSum[x-1];
(2) 从left到right的元素和等于refixSum[right+1] -prefix[left];
前缀和推导过程:
preSum[0] = 0
preSum[1] = nums[0] = preSum[0] + nums[0];
见上面
前缀和数组初始化过程伪代码示例:
划重点:
(1) 按照for循环的正常边界进行初始化，避免int I = 1或者<= len等等可能的各种调整
(2) 前缀和长度比数据长度多一个，前缀和第0个元素要初始化为0
拓展解惑:另外一种前缀和初始化方法:前缀和长度为nums.length,第0个元素存储自己的和
划重点:
(1) 预处理过程看似简单，但是考试计算容易出现混乱；
(2) prefixSum[i] – prefixSum[i-1];容易出现错误理解和计算丢失。
示例：prefixSum[1] – prefixSum[0] = nums[1],造成nums[0]丢失，出现后续错误
1.2 代表题目:和为K的子数组(#560中等)
6.3 触类旁通
6.3.1 连续的子数组和(#523)
6.3.2 和可被K整除的子数组(#974)
7 九阳神功第五式:差分
7.1差分介绍 基本套路
差分，是一种和前缀和相对的策略。这种策略是，令Bi=Ai-Ai-1，即相邻两数的差。在每一个点上记录变化数值，因为有增加有减少，通过求和和判断是否有超过指定容量的情况发生，超过则代表无法满足要求。
对于数组array[N]中的某一段进行增减操作，通过差分可在O(n)时间内完成。如
Trips=[[2,1,5],[3,3,7]]
第一步:更新array[1] = 2,array[5]=-2;
第一个站点上车2人占用两个座位，第5个站点下车2人，空出两个座位
第二步:更新array[3]=3,array[7]=-3
{0,2,0,3,0,-2,0,0,-3}
第三步:进行求和，得到结果array[]={0,2,2,5,5,3,3,0};
7.2代表题目:拼车(#1094)
代码实现
class Solution {
private static final int MAX_TRIP = 1001;
public boolean carPooling(int[][] trips, int capacity) {
// 差分经典题目
int[] changes = new int[1001];
for (int[] trip : trips) {
int passages = trip[0];
// 上车乘客数量
changes[trip[1]] += passages;
// 下车乘客数量
changes[trip[2]] -= passages;
}
int total = 0;
for (int i = 0; i < MAX_TRIP; i++) {
total += changes[i];
if (total > capacity) {
return false;
}
}
return true;
}
}
7.3触类旁通
航班预订统计(#1109)
思路与其代码实现
1.换一种思路理解题意，将问题转换为：某公交车共有 n 站，第 i 条记录 bookings[i] = [i, j, k] 表示在 i 站上车 k 人，乘坐到 j 站，在 j+1 站下车，需要按照车站顺序返回每一站车上的人数
2.根据 1 的思路，定义 counter[] 数组记录每站的人数变化，counter[i] 表示第 i+1 站。遍历 bookings[]：bookings[i] = [i, j, k] 表示在 i 站增加 k 人即 counters[i-1] += k，在 j+1 站减少 k 人即 counters[j] -= k
3.遍历（整理）counter[] 数组，得到每站总人数： 每站的人数为前一站人数加上当前人数变化 counters[i] += counters[i - 1]
买卖股票的最佳时机(#121)
买卖股票的最佳时机II(#122)
会议室(#253)
8 九阳神功第六式:拓扑排序(专业级)
8.1 拓扑排序介绍
https://blog.csdn.net/lisonglisonglisong/article/details/45543451
一、什么是拓扑排序
在图论中，拓扑排序(topological Sorting)是一个有向无环图(DAG,directed Acyclic graph)的所有顶点的线性序列。且该序列必须满足下面两个条件。
每个顶点出现且出现一次。
若存在一条从顶点A到顶点B的路径,那么在序列中顶点A出现在顶点B的前面
有向无环图(DAG)才有拓扑排序，非DAG图没有拓扑排序一说
8.1.1序列重建(#444会员)
8.2 代表题目
课程表II (#210)
8.3 触类旁通
8.3.1 火星词典(#269)
9 九阳神功第七式:字符串(高频 20~50)
10 九阳神功第八式:二分查找 (高频 10~20)
https://leetcode-cn.com/leetbook/detail/binary-search/
10.1 二分查找介绍
二分查找也称折半查找(Binary Search),它是一种效率较高的查找方法，前提是数据结构必须排好序，可以在数据规模的对数时间复杂度内完成查找，二分查找要求线性表具有随机访问的特点(例如数组)，也要求线性表能够根据中间元素的特点推测它两侧元素的性质，以达到缩减问题规模的效果
二分查找问题也是经常考到的问题，虽然它的思想很简单，但写好二分查找算法并不是一件很容易的事情
关键点:
(1) 二分查找的关键变量是low,high,mid三个元素，根据目标值和mid所在索引的数值和target目标值进行比对，根据[mid]中间值得大小重新确定查找区间
(2) 用途:二分法的基础是分治策略的基础，分治用的最多的是二分拆解计算
二分查找法有更安全的写法
mid = (l+r)/2; 可能整型溢出，上亿的数据
mid=l+(r-l)/2;
记录三个经典模板(必须掌握)
详情见leetcode：
10.1.1 模板一:
注意点:
- right是长度-1，而且左边小于右边
- mid的处理
10.1.2 模板二
10.1.3 模板三
10.2 代表题目:搜索二维矩阵II(#240)
https://leetcode-cn.com/problems/search-a-2d-matrix/solution/yi-wen-dai-ni-gao-ding-duo-ge-er-fen-cha-2hl9/
搞死所有的二分法
该题的难点在于二分查找法的处理过程
搜索二维矩阵(#240)
主要思路及难点:
- 二分法模板
- 二维数组到一维数组的降维
- 二分法中如果不降维，会出现问题
10.3 触类旁通
10.3.1寻找两个有序数组的中位数(#4)
10.3.2搜索旋转排序数组(#33)
#33题 :搜索旋转排序数组
#81题 :搜索旋转排序数组-ii
#153题: 寻找旋转排序数组中的最小值
#154题: 寻找旋转排序数组的最小值-ii
https://leetcode-cn.com/problems/search-in-rotated-sorted-array/solution/yi-wen-jie-jue-4-dao-sou-suo-xuan-zhuan-pai-xu-s-2/
该题是二分查找的变种，题型非常经典
10.3.2计算二分数组的上下边界条件(#34 )
11 九阳神功第十式:BFS广搜
11.1 BFS介绍
DFS(深度优先搜索)和BFS(广度优先搜索)就像孪生兄弟，提到一个总是想起另一个，然后在实际使用中，我们用DFS的时候远远多于BFS,那么，是不是BFS就没有用呢？
如果我们使用DFS/BFS知识为了遍历一棵树、一张图上所有结点的话，那么DFS和BFS的能力没什么差别，我们当然更倾向于更方便写、空间复杂度更低的DFS遍历。不过，某些使用场景是DFS做不到的，只能使用BFS遍历，这就是本文要介绍的两个场景:[层序遍历]、[最短路径]。
DFS与BFS
让我们先看看在二叉树上进行DFS遍历和BFS遍历的代码比较。
DFS遍历使用递归:
Java：
实际编码中，有的童学会增加一个!=null的判空，不太推荐这种写法，因为递归的终止条件已经进行了判断。只有在BFS外队列中添加元素时才会进行判空处理，避免后续从队列中取出来的数据存在空指针。
BFS遍历使用队列数据结构：
Java
只是比较两段代码的话，最直观的感受就是:DFS遍历代码比BFS简洁太多了！这是因为递归的方式隐藏含地使用了系统的栈，我们不需要自己维护一个数据结构。如果只是简单的将二叉树遍历一遍，那么DFS显然是更方便的选择
总结:
可以看到。BFS遍历，层序遍历，最短路径实际上是递进的关系。在BFS遍历的基础上区分遍历的每一层，就得到了层序遍历。在层序遍历的基础上记录层数，就得到了最短路径。
BFS遍历时一类很值得反复体会和练习的题目。一方面，BFS遍历时一个很经典的算法，需要重点掌握。另一方面，我们需要根据题意分析出题目是求最短路径，知道要做BFS遍历
BFS的几个步骤
1.肯定会用到 deque 的结构用来模拟队列，BFS精髓也在这里。
2.队列里肯定是有一个初始点
3.然后每次处理从队列中出队一个元素
4．对元素进行扩张(具体如何扩张需要根据题目要求，一般是上下左右四个方向，本题是算上斜向共8个方向)
5.对于扩张后满足某条件的点再进行处理，根据需要进入队列，进入队列的点就是扩到下一层的点(不同题目需要处理的方法不同，大家灵活运用)
6.然后接着循环处理 deque 中的元素，直到 deque 为空，则代表所有点都已经完成扩张
7.最后根据题目要求输出结果(当然这已经不属于 BFS 模板的范围了)
11.2 代表题目:单词接龙(#127)
11.3 触类旁通
11.3.1 单词拆分(#139)
11.3.2 打开转盘所(#752)
11.3.3 被围绕的区域(#130)
11.3.4 离建筑物最近的距离(#317)
11.3.5 迷宫II (#505)
11.3.6 扫雷游戏(#529)
11.3.7 推箱子（#1263）
11.3.8 进击的骑士(#1197)
11.3.9 公交路线(#1197)
11.3.10 最短的桥(#934)
11.3.11 腐烂的橘子(#994)
12 九阳神功第十一式:DFS深搜&回溯
12.1 DFS介绍
深度优先搜索算法(英语:Depth-First-Search,DFS)是一种用于遍历或者搜索树或者图的算法。这个算法会尽可能深的搜索树的分支。深度优先搜索是图论中的经典算法，利用深度优先搜索算法可以产生目标图的拓扑排序表，利用拓扑排序表可以方便的解决很多有关的图论问题，如无权最长路径问题等等。DFS基于递归思想，DFS实质就是一种枚举，不过借助递归实现
回溯搜索是深度优先搜索(DFS)的一种。对于某一个搜索树来说(搜索树是起记录路径和状态判断的作用)，回溯和DFS,其主要的区别是，回溯法在求解过程中不保留完整的树结构，而深度优先搜索则记下完整的搜索树。回溯就是通过不同的尝试来生成问题的解，有点类似于穷举，但是和穷举不同的是回溯会”剪枝”.为了减少存储空间，在深度优先搜索中，用标志的方法记录访问过的状态，这种处理方法使得深度优先搜索法与回溯法没什么区别
DFS的基本模板:
回溯的一般结构:
12.2代表题目:最短的桥(#934)
结题思路:
- 通过深度优先遍历，将两个岛屿中的一个岛屿进行染色处理，打上标签2
- 通过广度优先遍历查找岛屿1，找出最短路径
- 关键点：广度优先遍历时，要用visited数组记录访问过的节点，避免重复访问造成超时TLE
编程细节:
class Solution {
public int shortestBridge(int[][] A) {
int R = A.length, C = A[0].length;
int[][] colors = getComponents(A);
Queue<Node> queue = new LinkedList();
Set<Integer> target = new HashSet();
for (int r = 0; r < R; ++r)
for (int c = 0; c < C; ++c) {
if (colors[r][c] == 1) {
queue.add(new Node(r, c, 0));
} else if (colors[r][c] == 2) {
target.add(r * C + c);
}
}
while (!queue.isEmpty()) {
Node node = queue.poll();
if (target.contains(node.r * C + node.c))
return node.depth - 1;
for (int nei: neighbors(A, node.r, node.c)) {
int nr = nei / C, nc = nei % C;
if (colors[nr][nc] != 1) {
queue.add(new Node(nr, nc, node.depth + 1));
colors[nr][nc] = 1;
}
}
}
throw null;
}
public int[][] getComponents(int[][] A) {
int R = A.length, C = A[0].length;
int[][] colors = new int[R][C];
int t = 0;
for (int r0 = 0; r0 < R; ++r0)
for (int c0 = 0; c0 < C; ++c0)
if (colors[r0][c0] == 0 && A[r0][c0] == 1) {
// Start dfs
Stack<Integer> stack = new Stack();
stack.push(r0 * C + c0);
colors[r0][c0] = ++t;
while (!stack.isEmpty()) {
int node = stack.pop();
int r = node / C, c = node % C;
for (int nei: neighbors(A, r, c)) {
int nr = nei / C, nc = nei % C;
if (A[nr][nc] == 1 && colors[nr][nc] == 0) {
colors[nr][nc] = t;
stack.push(nr * C + nc);
}
}
}
}
return colors;
}
public List<Integer> neighbors(int[][] A, int r, int c) {
int R = A.length, C = A[0].length;
List<Integer> ans = new ArrayList();
if (0 <= r-1) ans.add((r-1) * R + c);
if (0 <= c-1) ans.add(r * R + (c-1));
if (r+1 < R) ans.add((r+1) * R + c);
if (c+1 < C) ans.add(r * R + (c+1));
return ans;
}
}
class Node {
int r, c, depth;
Node(int r, int c, int d) {
this.r = r;
this.c = c;
depth = d;
}
}
12.3 触类旁通
12.3.1 路径总和II(#113中等 重点看)
思路及算法
我们可以采用深度优先搜索的方式，枚举每一条从根节点到叶子节点的路径。当我们遍历到叶子节点，且此时路径和恰为目标和时，我们就找到了一条满足条件的路径。
class Solution {
List<List> ret = new LinkedList<List>();
Deque path = new LinkedList();
public List<List<Integer>> pathSum(TreeNode root, int sum) {
dfs(root, sum);
return ret;
}
public void dfs(TreeNode root, int sum) {
if (root == null) {
return;
}
path.offerLast(root.val);
sum -= root.val;
if (root.left == null && root.right == null && sum == 0) {
ret.add(new LinkedList<Integer>(path));
}
dfs(root.left, sum);
dfs(root.right, sum);
path.pollLast();
}
}
12.3.2 二叉树中的最大路径和(#124 困难)
12.3.3 得分最高的路径(#1102 中等)
12.3.4 冗余连接II(#685困难)
12.3.5 孤独像素I(#531 中等)
12.3.6 孤独像素II(#533 中等)
12.3.7 重新安排行程(#332 中等)
12.3.8 打家劫舍III (#337 中等)
12.3.9 岛屿数量(#200 中等 重点琢磨)
杀光岛屿数量问题，一次搞定，该问题考的很多
• L200. 岛屿数量 （Easy）
• 463. 岛屿的周长 （Easy）
• 695. 岛屿的最大面积 （Medium）
• 827. 最大人工岛 （Hard）
https://leetcode-cn.com/problems/number-of-islands/solution/dao-yu-lei-wen-ti-de-tong-yong-jie-fa-dfs-bian-li-/
思路很重要:
岛屿的最大面积 695
见题目
12.4 树的其它题型
12.4.1二叉树遍历问题 (递归+非递归方式实现)
二叉树的前序遍历 (#144)
二叉树的中序遍历 (#94)
二叉树的后续遍历 (#145)
二叉树的层序遍历
上述题目都是一类题
二叉树遍历速记歌:
栈的方式来实现
- 二叉树返list,辅助正规dfs来救场
- 主要区别根节点前中后，返回全搞定
后续遍历基本方法，里面只需要调动一下根节点的位置即可
非栈的方式来实现
前序遍历
13 九阳神功第十二式:动态规划 （共计11道母题）
13.1 动态规划介绍
Leetcode上有专门的章节来描述
https://blog.csdn.net/qq_37763204/article/details/79394397
https://blog.csdn.net/u013309870/article/details/75193592
13.2 代表题目:打家劫舍II(#213)
基本思路:
13.3 触类旁通
13.3.1 分隔数组以得到最大和(#1043)
13.3.2 分隔等和子集(#416)
13.3.3 买股票的最佳时机 III (#123)
13.3.4 不同路径(#62)
思路一:
思路二:
本题是个高中数据题
13.3.5 不同路径II(#63)
13.3.6 4键键盘(#651会员)
13.3.7 最小路径和
这道题很典型:
13.3.8 轰炸敌人(#361)
13.3.9 校园的自行车分配 II(#1066会员)
13.3.10 角矩阵的数量(#750会员)
13.3.11 抛掷硬币(#1230)
14 九阳神功第十三式:贪心算法
14.1 贪心算法介绍
所谓贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，它所做出的仅是在某种意义上的局部最优解。也就是说在每一步中，选择当前最优的策略，而不是考虑全局是不是最优解的
贪心算法的前提:
- 原问题复杂度过高
- 求全局最优解的数学模型难以建立
- 求全局最优解的计算量过大
- 没有太大必要一定要求出全局最优解，”比较优”就可以。
贪心算法没有固定的算法框架，算法设计的关键是贪心策略的选择。必须注意的是，贪心算法不是对所有问题都能得到整体最优解，选择的贪心策略必须具备无后效性，即某个状态以后的过程不会影响以前的状态，只与当前状态有关。所以对所采取的贪心策略一定要仔细分析其是否满足无后效性
贪心算法实现步骤
- 建立数学模型来描述问题
- 把求解的问题分成若干个子问题
- 对每一个子问题求解，得到子问题的局部最优解
- 把子问题的解局部最优解合成原来解问题的一个接
实现该算法的过程:
从问题的某一初始解出发:
While(能朝给定总目标前进一步)
{
利用可行的决策，求出可行解的一个元素;
}
由所有解元素组合成问题的一个可行解
虽然没有固定模板提供贪心算法解决方案，但是可以参考一种可能的理解贪心算法的代码示例，进行学习和理解；
14.2 代表题目:用最少数量的箭引爆气球(#452)
基本思路
https://leetcode-cn.com/problems/minimum-number-of-arrows-to-burst-balloons/solution/yong-zui-shao-shu-liang-de-jian-yin-bao-qi-qiu-1-2/
14.3 触类旁通
14.3.1 两地掉地（#1029）
14.3.2 0/1背包问题
14.3.3 分享巧克力(#1231会员 困难)
14.3.4 交换字符使得字符串相同(#1247)
14.3.5 跳跃游戏II (#45)
14.3.6 任务调度器(#621)
14.3.7 摆动序列(#376)
15 九阳神功第十四式:字典树
15.1 字典树介绍
Trie（发音“TRY”,但是坐着称之为Tree）或者前缀树是一种数据结构，用于检索字符串数据集中的键。Trie树优于哈希表的另一个理由是，随着哈希表大小增加，会出现大量的冲突，时间复杂度可能会增加到O(n),其中n是插入的键的数量。与哈希表相比，Trie树存储多个具有相同前缀的键时可以使用较少的空间。此时Trie树只需要O(m)的时间复杂度，其中m为键长。而在平衡树种查找键值需要O(mlogn)时间复杂
Trie树的节点结构
Trie是一个有根的树，Trie树种最常见的两个操作是键的插入和查找。其节点具有以下字段:
最多R个指向子节点的链接，其中每个链接对应字母表数据集中的一个字母
本文中假定R为26，小写拉丁字母的数量
希尔字段，以指定节点是对应键的结尾还是只是键前缀
这一高效的数据结构有多种应用
- 自动补全
- 拼写检查
- IP路由(最长前缀匹配)
15.2 代表题目：单词的压缩编码(#820)
15.3 触类旁通
15.3.1 实现Trie前缀树(#208)
15.3.2 单词替换(#648)
16 九阳神功第十五式:位运算
16.1位运算介绍
https://www.zhihu.com/question/38206659
总结一些常用的位运算技巧
1.异或的特性
2.构造特殊 Mask，将特殊位置放 0 或 1。
3.有特殊意义的 & 位操作运算
16.2代表题目
异或类题目(#136)
主要用到了异或性质 思路
1.任何数和 000 做异或运算，结果仍然是原来的数，即 a⊕0=aa \oplus 0=aa⊕0=a。
2.任何数和其自身做异或运算，结果是 000，即 a⊕a=0a \oplus a=0a⊕a=0。
3.异或运算满足交换律和结合律，即 a⊕b⊕a=b⊕a⊕a=b⊕(a⊕a)=b⊕0=ba \oplus b \oplus a=b \oplus a \oplus a=b \oplus (a \oplus a)=b \oplus0=ba⊕b⊕a=b⊕a⊕a=b⊕(a⊕a)=b⊕0=b。
16.3触类旁通
17 专题强化
17.1 ASCII专题
17.1.1 最长回文子串(#409简单)
17.2 子序列问题
17.3 子数组专题
17.4 计算器专题
17.5 与或非位运算专题(二进制计算)
17.5.1 只出现一次的数字II(#137)
17.5.2 只出现一次的数字III
17.5.3 数组中两个数的最大异或值
17.5.4 重复的DNA序列
17.5.5 最大单词长度乘积
17.5.6 数字信号处理
17.6 打家劫舍专题
17.6.1 打家劫舍(#198)
思路:通过该问题可以看出，应该是有状态方程的
17.6.2 打家劫舍II (#213)
17.6.3 打家劫舍III(#337)
17.7 背包问题专题
17.7.1 0/1背包问题
17.7.2 完全背包问题
17.7.3 多重背包问题
17.7.4 实战练习
17.7.5 栈与队列的问题
用栈实现队列
主要是使用栈实现队列
用队列实现栈
17.8股票买卖的最佳时机专题
17.8.1买卖股票的最佳时机
基本思路:使用动态规划进行出路该题，非常清晰明了，建议背诵该题
17.8.2 买卖股票的最佳时机II
18 设计者模式思考
https://www.cnblogs.com/hongmoshui/p/10438719.html
https://blog.csdn.net/srk950606/article/details/50187721?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522160628694119725264553504%2522%252C%2522scm%2522%253A%252220140713.130102334.pc%255Fall.%2522%257D&request_id=160628694119725264553504&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2allfirst_rank_v2~rank_v28-14-50187721.first_rank_ecpm_v3_pc_rank_v2&utm_term=%E4%B9%9D%E9%98%B3%E7%A5%9E%E5%8A%9F&spm=1018.2118.3001.4449
18.1 设计者模式的分类
速记口诀:
创建型模式:建造者按照工厂单例原型进行工厂方法抽象
结构型模式:代理组合适配，享元装饰桥(接)外观
行为型模式:
总体来说设计模式分为三大类：
创建型模式，共五种：工厂方法模式、抽象工厂模式、单例模式、建造者模式、原型模式。
结构型模式，共七种：适配器模式、装饰器模式、代理模式、外观模式、桥接模式、组合模式、享元模式。
行为型模式，共十一种：策略模式、模板方法模式、观察者模式、迭代子模式、责任链模式、命令模式、备忘录模式、状态模式、访问者模式、中介者模式、解释器模式。
18.2 设计模式的六大原则
口诀辅助记忆::
一个单身的吕氏拿着颠倒的半开半合的扇子，正在分析接口隔离问题，旁边站着米老鼠
1.
2
3
4
5
6
18.3 常见的几种设计模式(重点)
18.4 设计原则与设计模式的概念:
目的:所有的设计原则和设计模式都是为了更容易的实现高内聚低耦合
软件设计->设计模式->SOLID原则->正交四原则->高内聚低耦合
为了更容易达成高内聚低耦合，利用互相交互的维度独立设计一个事半功倍的方式，由此提出来正交四原则:
1.最小化重复
2.分离变化
3.缩小依赖范围
4向稳定方向依赖
每个原则都是和其他原则独立发展，互不重复
在面向对象发展过程中，提出更具体的SOLID原则:
1.单一职责(SRP)
2.向扩展开发/向修改封闭(OCP)
3.子类要能替换父类(LSP)
4.接口隔离/最小化接口依赖(ISP)
5.依赖倒置/只依赖接口(DIP)
19.2.1 反转链表
更新三个引用:主要理解清楚整个过程
19.3栈
19.4 堆
19.5 树