总结
- 先熟悉数据结构再理解算法套路
- 刷leetcode并结合题解理解，如果有意向大厂可以刷对应的企业题库加快速度
- 如果你是idea编辑器，强烈推荐安装leetcode插件
参考
https://github.com/labuladong/fucking-algorithm
思路
滑动窗口-双指针
- 我们在字符串 S 中使用双指针中的左右指针技巧，初始化 left = right = 0，把索引闭区间 [left, right] 称为一个「窗口」。
- 我们先不断地增加 right 指针扩大窗口 [left, right]，直到窗口中的字符串符合要求（包含了 T 中的所有字符）。
- 此时，我们停止增加 right，转而不断增加 left 指针缩小窗口 [left, right]，直到窗口中的字符串不再符合要求（不包含 T 中的所有字符了）。同时，每次增加 left，我们都要更新一轮结果。
- 重复第 2 和第 3 步，直到 right 到达字符串 S 的尽头。
动态规划
核心思想
穷举求最值，正确的「状态转移方程」
三要素
重叠子问题、最优子结构、状态转移方程
思维框架
==明确「状态」 -> 定义 dp 数组/函数的含义 -> 明确「选择」-> 明确 base case==
区别：递归自顶向下，动归自底向上
动态规划一般可分为线性动规，区域动规，树形动规，背包动规四类。
举例：
- 线性动规：拦截导弹，合唱队形，挖地雷，建学校，剑客决斗等；
- 区域动规：石子合并， 加分二叉树，统计单词个数，炮兵布阵等；
- 树形动规：贪吃的九头龙，二分查找树，聚会的欢乐，数字三角形等；
- 背包问题：01背包问题，完全背包问题，分组背包问题，二维背包，装箱问题，挤牛奶（同济ACM第1132题）等； 应用实例： 最短路径问题 ，项目管理，网络流优化等；
回溯
回溯问题，实际上就是一个决策树的遍历过程。你只需要思考 3 个问题：
- 路径：也就是已经做出的选择。
- 选择列表：也就是你当前可以做的选择。
- 结束条件：也就是到达决策树底层，无法再做选择的条件。
result = []
def backtrack(路径, 选择列表):
if 满足结束条件:
result.add(路径)
return
for 选择 in 选择列表:
做选择
backtrack(路径, 选择列表)
撤销选择
其核心就是 for 循环里面的递归，在递归调用之前「做选择」，在递归调用之后「撤销选择」
分治
分治算法可以分三步走：分解 -> 解决 -> 合并
- 分解原问题为结构相同的子问题。
- 分解到某个容易求解的边界之后，进行第归求解。
- 将子问题的解合并成原问题的解。
二分
最基本的二分查找算法：
因为我们初始化 right = nums.length - 1 所以决定了我们的「搜索区间」是 [left, right] 所以决定了 while (left <= right) 同时也决定了 left = mid+1 和 right = mid-1
- 分析二分查找代码时，不要出现 else，全部展开成 else if 方便理解。
- 注意「搜索区间」和 while 的终止条件，如果存在漏掉的元素，记得在最后检查。
- 如需定义左闭右开的「搜索区间」搜索左右边界，只要在 nums[mid] == target 时做修改即可，搜索右侧时需要减一。
- 如果将「搜索区间」全都统一成两端都闭，好记，只要稍改 nums[mid] == target 条件处的代码和返回的逻辑即可。
贪心算法
概念：
在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。
适用前提：局部最优策略能导致产生全局最优解。
思路：
- 建立数学模型来描述问题。
- 把求解的问题分成若干个子问题。
- 对每一子问题求解，得到子问题的局部最优解。
- 把子问题的解局部最优解合成原来解问题的一个解。
排序
常见的稳定排序算法有：
- 冒泡排序（Bubble Sort） — O(n²)
- 插入排序（Insertion Sort）— O(n²)
- 桶排序（Bucket Sort）— O(n); 需要 O(k) 额外空间
- 计数排序 (Counting Sort) — O(n+k); 需要 O(n+k) 额外空间
- 合并排序（Merge Sort）— O(nlogn); 需要 O(n) 额外空间
- 二叉排序树排序 （Binary tree sort） — O(n log n) 期望时间; O(n²)最坏时间; 需要 O(n) 额外空间
- 基数排序（Radix sort）— O(n·k); 需要 O(n) 额外空间
常见的不稳定排序算法有：
- 选择排序（Selection Sort）— O(n²)
- 希尔排序（Shell Sort）— O(nlogn)
- 堆排序（Heapsort）— O(nlogn)
- 快速排序（Quicksort）— O(nlogn) 期望时间, O(n²) 最坏情况; 对于大的、乱数串行一般相信是最快的已知排序
冒泡: 一次比较两个元素，如果它们的顺序错误就把它们交换过来
选择: 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾
插入: 构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入
希尔: 缩小增量排序，也是一种插入排序，会优先比较距离较远的元素
归并: 分治法-将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。
快速: 分治法-来把一个串（list）分为两个子串（sub-lists）
堆: 堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点
计数: 计数排序使用一个额外的数组C，其中第i个元素是待排序数组A中值等于i的元素的个数。然后根据数组C来将A中的元素排到正确的位置。它只能对整数进行排序
桶: 假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排
基数: 按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位
技巧/概念
- 基础技巧：分治、二分、贪心
- 排序算法：快速排序、归并排序、计数排序
- 搜索算法：回溯、递归、深度优先遍历，广度优先遍历，二叉搜索树等
- 图论：最短路径、最小生成树
- 动态规划：背包问题、最长子序列
遍历
关注父节点顺序
- 前序遍历：先输出父节点，在遍历左子树和右子树（中左右）
- 中序遍历：先输出左子树，再输出父节点，再遍历右子树（左中右）
- 后序遍历：先遍历左子树，再遍历右子树，最后输出父节点（左右中）
线索二叉树
概念： 1）n个节点的二叉链表中含有(n+1)个空指针域，利用空指针域存放指向该节点下某种遍历
赫夫曼树
路径：从树中一个结点到另一个结点之间的分支构成两个结点之间的路径，路径上的分支数目称作路径长度。 树的路径长度：从树根到每一个结点的路径长度之和。 定义：带权路径长度WDL最小的二叉树称作赫夫曼树，权值较大的结点离根较近。
红黑树
五个限定条件
- 节点是红色或黑色
- 根节点是黑色
- 每个叶子节点都是黑色的空节点（NIL节点）
- 每个红色节点的两个子节点都是黑色的（从每个叶子到根的所有路径上不能有两个连续的红色节点）
- 从任意节点到其每个叶子的所有路径都包含相同数目的黑色节点
