对算法的一些理解
算法是什么
算法就是在一些特定数据结构上的应用；巧用数据结构是关键
算法能给我们带来什么
思维方式的转变以及编程功底的加深。
算法所依赖的数据结构
算法所依赖的数据结构大体上分两类
- 线性数据结构
- 非线性数据结构
线性数据结构
数组
数组的随机访问特性，支持O(1)时间复杂度的查询操作，可以充分利用cpu缓存；以及合理使用System.arraycopy移动数组位置（重置数组开始索引），往往在应对一些题目时（比如差分）代码书写起来比较简单； 当然数组也是一些其他数据结构的载体，比如完全二叉树一般来说用数组存储比较合理，再比如并查集；数组的一些基本操作：增、删、改、查
链表
链表不受存储空间限制，支持O(1)时间复杂度的插入、删除操作，操作链表时要先加保护节点（哨兵节点），减少特判；链表的基本操作：插入节点、删除节点、查询节点（删除节点和修改节点值的操作是基于查询的）；链表细分又可以分为
* 单链表
* 循环链表
* 双向链表
* 双向循环列表
栈
栈满足先进后出，凡是最近相关的可以用栈来处理，比如解决逆波兰式（后缀表达式）求值问题，验证括号是否有效，以及前缀最小值问题，浏览器前进后退问题等等，通常栈可以用队列来实现
队列
队列满足先进先出（FIFO）
集合
集合分为有序集合，无序集合，有序集合比如java中的TreeSet，无序集合比如java中的HashSet
非线形数据结构
树形数据结构
抽象来讲树分为多叉树和二叉树； 满足某些特性的树又称为完全二叉树、满二叉树；针对二叉树满足某些特性又可称为二叉搜索树；二叉搜索树的递归定义
满足 （1）节点的左子树只包含小于当前节点的数
（2）节点的右子树只包含大于当前节点的数
（3）所有左右子树自身必须也是二叉搜索树
树的存储方式：可以使用数组也可以使用链表
**更加具体更加贴合实践场景的一些树形数据结构**
（1）平衡二叉树（avl）：
平衡因子（Balance Factory）：一个结点的左子树的高度 减去 它的右子树的高度
Avl规定任意结点的平衡因子的绝对值都不超过1
Avl 一般会存储关键码，左孩子，右孩子，父亲 以及树的高度
超过平衡因子需要旋转，旋转分四个场景
场景1:LL — 左左子树 ： 右旋
场景2:RR — 右右子树：左旋
场景3:LR — 左右子树：先左旋，再右旋
场景4:RL— 右左子树，先右旋，再左旋
（2）红黑树：
是一种近似平衡的二叉搜索树
从根到叶子的最长路径<=2 * 最短路径（简记：高度差在2倍以内）
规则
每个节点要么是红色，要么是黑色
跟节点是黑色
最底层视作有一层空叶结点，是黑色的
不能有两个相邻的红色节点
从任一结点到其每个叶子的所有路径都包含相同数目的黑色结点
规则被打破时 通过变色或者旋转操作来修正
TreeSet TreeMap
AVL和红黑树的比较
红黑树插入删除更快（旋转少，可通过变色替代旋转）
红黑树更省空间（只用存颜色 ：： 颜色 vs 平衡因子）
avl树查询更快 （红黑树不如avl树平衡）
（3）并查集
用于处理不相交集合（disjoint sets）的合并和查询问题，即处理分组问题，维护无序二元关系
使用一维数组存储 fa[j] = i ，j 的 father 是i ，代表元素j 处于 元素i 的集合
涉及到的操作：
MakeSet(s) 建立一个新的并查集，初始化包含s个集合，每个集合只有一个元素
UnionSet(x,y)把元素x和元素y所在的集合合并，如果x和y所在的集合不相交，则无需合并
Find(x) 找到x所在的集合代表
并查集查找过程中可以使用路径压缩优化查询性能 具体实现 fa[x] = find(fa[x])
（4）Trie树（字典树）
字典树是一种由“结点”和“带有字符的边”构成的树形结构
应用场景：统计和排序大量的字符串（不仅限于字符串）
核心思想：空间换时间
优点：最大限度的减少无谓的字符串比较，查询效率比哈希表高
（5）堆
堆是一棵二叉树，并且满足堆性质
大根堆：根比孩子大 （左右孩子无需对比）
小根堆：根小于孩子
二叉堆是堆的一种简易实现；本质上是一棵满足堆性质的完全二叉树；一般使用一个一维数组存储
关于堆和树的异同点：二叉树是一个基本的数据结构，堆是一个特殊的二叉树
（6）树状数组
是一种维护数组前缀和、区间和的数据结构；
思想和跳表类似
跳表 ：添加索引，高效维护链表
树状数组：添加索引，高效维护数组
树状数组的索引数据数量和节点编号的lowbit值相关，lowbit 值为多少，则索引多少个原始节点
性质：
（1）除树根外，每个内部节点 c[x] 的父亲是c[x + lowbit(x)]
（2）每个内部节点c[x]保存以它为根的子树中所有叶节点的和
（7）线段树
线段树是一种基于分治思想的二叉树结构，用于在区间上进行信息统计。
1. 线段树的每个节点都代表一个闭区间
2. 线段树具有唯一的根结点，代表的区间是整个统计的范围，如[1,N]
3. 线段树的每个叶子节点都代表一个长度为1的元区间[X,X]
4. 对于每个内部节点[l,r]，它的左子节点是[l,mid]，右子节点是[mid+1,r]，其中mid =(l + r) / 2 （向下取整）
实际使用线段树处理问题时，递归建树，回溯统计； 对于支持线段树的区间修改，可以采用懒惰修改，bug下传的方式；
线段树的使用场景：求最值，求和，线段覆盖
森林
森林其实就是有多个根节点的树
图
基环树：介于树和图之间的一种数据结构（向一棵树添加一条边形成一个环，叫基环树）
图根据是否有方向大致分为两类：有向图、无向图
根据是否联通分为：联通图、非联通图
点的度数：一个点相连的边的数量
出边数：出度
入边数：入度
如何存一张图（无向图看作是正反两条边的有向图去存储）：
（1）邻接矩阵
（2）邻接表
（3）出边数组 （java ArrayList<ArrayList<>>）
图的遍历方式：
（1）深度优先遍历（dfs）适合无向图找环（通过父节点去假环），当然无向图找环也可以使用并查集来处理（划分连通块）
（2）广度优先遍历（bfs）适用场景拓扑排序（入度配合 bfs-有向图找环）， 求最短距离 ，求层数
关注图的拓扑排序
解任何问题其实就是在由状态构成的图上做一些遍历，看怎么遍历比较高效
搜索就是采用直接遍历整个状态空间的方式寻找答案的一类算法（动归、图论、贪心都是基于搜索）
链表是特殊化的树，树是特殊化的图
哈希表
基于基础数据衍生而来的数据结构
hash函数选取很重要（数组就是一个简单的哈希表，数组的hash函数直接映射为数组下标）
保证在碰撞概率相对较低的前提下，尽量设计比较简单的hash函数（性能考虑）。
hash碰撞之后的解决方式主要有如下几种（包含但不限于）
（1）开散列（拉链法）：哈希冲突之后拉一个列表出来，查询hash值相同的key时直接在链表上查询即可；链表也可以进一步优化，比如优化成红黑树，提升查询性能
（2）开放寻址法
其他。。。
一些常见算法介绍
快慢指针
作用于数组或者链表的数据结构上，常用来解决环路问题
定义两个指针，一快一慢遍历数据结构
前缀和
包含一维数组前缀和，二维数组前缀和
使用场景是子段查询
差分
和前缀后是互逆运算
使用场景涉及修改
双指针扫描
比较简单
单调栈
基于栈的数据结构，维护栈内数据单调递增/递减来处理一些实际问题；比如柱形图中的最大矩形
滑动窗口
基于队列这一数据结构，使队列内数据具有单调的特性（单调队列），实现滑动窗口算法，用来解决类似区间最值问题
滑动窗口的大小可以不固定，只要上下界同时满足单调性质就可以；用单调队列维护max
LRU算法
常见的页面置换算法，使用哈希表加双向链表实现的一种支持O(1) 查询 O(1)修改的数据结构，比较简单，不再赘述
分治算法
一般用递归实现，实现过程中要注意聚焦第一段，第一个子问题
划分子问题标准：第一个子问题，作为不可分割的整体
注意：递归和分治不是一个维度的东西，递归是一种实现形式， 比如用递归实现分治算法。
记忆化搜索
本质上还是搜索，只不过在搜索的基础上做了优化，比如剪枝； 实践：dfs + 记忆化搜索求最长路径
二分
更加一般化的二分要关注：条件满足，限定范围，开始截止，是否加一
从二分扩展三分
二分答案
把最优化问题转换为可行性问题，一般地二分配合贪心实现
排序
核心关注：归并排序(稳定)，快排（不稳定），堆排序 时间复杂度均为 O(n logn)
插入排序，冒泡排序，选择排序 时间复杂度均为 O(n*n)
计数排序，从数值范围入手解决问题
希尔排序
关于快排
（1）快排轴元素选不好会退化成 O(n^2),解决思路 随机选取轴元素
（2）快排可以原地，归并不可以
贪心
一般地，先想分治，搜索，动归； 后想贪心，贪心往往用来和其他算法配合起来解决一些复杂问题，贪心题目是需要被证明的； 证明贪心的思路
（1）决策包容性
（2）决策范围扩展
（3）邻项交换（顺序类题目，即按照什么顺序做最好）
动态规划
注意切题方式，可以先人工模拟，核心是找出状态转移方程；简单来讲，关注题目中变化的信息，将每个变化的信息当作一维放入动规数组；找到状态之间的推导关系，从而确定最优子结构，从最优子结构出发找到状态转移方程（可以使用列表法来推导状态转移方程），最后确定边界和目标，使用递推实现（实现过程中可以从i -1推导i，同样 也可以同i推导i+1）。
具体编码时要注意：先 for 状态（阶段） 再 for决策
动规有几种类型：
（1）线形动规 ： 常规简单动规
（2）区间动规 ： 迭代时 要先处理阶段
（3）树形动规 ： 状态的第一维放树的节点
图论相关算法
求最短路径
Bellman-Ford
算法基于动规和迭代思想，n个点，m条边，时间复杂度O(nm)
不考虑负环
Dijkstra
基于贪心，用堆来维护最小边，每次取最小边进行扩展； 先算小的再算大的
不考虑负边，非负保证取出一个点进行计算时，该点就是目前路径最小的点，前面的点均已算完
Floyd
用来求图中每一对点之间的最短路径 ，本质是动规，时间复杂度 O(nnn)
具体决策中使用中继点
求最小生成树
最小生成树：边权之和最小，把任何一个生成森林扩展为生成树，一定使用了图中剩余边中权值最小的
最小生成树性质：任意一颗最小生成树一定包含无向图中权值最小的边
Kruskal
使用并查集维护无向图的最小生成树
整个过程中的收获
关于如何高效的练习算法
多做题，多思考，前期注重分类刷题，熟练掌握三刷五步法；写算法时要注意以下几点
- 主体思路要和细节分开
- 遇事不决先枚举
- 巧用方向数组
- 要深入理解记忆算法模型，从而可以解决一类题目
|