算法总览
- 一维
- 基础：数组 array（string）、链表 linked list
- 高级：栈 stack、队列 queue、双端队列 deque、集合 set、映射 map（hash or map）
- 二维
- 基础：树 tree、图 graph
- 高级：二叉搜索树 binary search tree（red - black tree）、堆 heap、并查集 disjoint set、字典树 trie
- 三维
- 位运算 Bitwise、布隆过滤器 BloomFilter
- LRU Cache
算法最终基于下面三个基本单元、也就是基石：
- if - else、switch -> branch
- for、while loop -> Iteration
- 递归 Recursion（Divide & Conquer、Backtrace）
基于上面的三个基本单元，衍生高级的算法，其实都有一套模板变来变去：
- 搜索 Search：深度优先搜索（DFS） Depth first search、广度优先搜索 Breadth first search（BFS）
- 动态规划（DP） Dynamic Programming
- 二分查找 Binary Search
- 贪心 Greedy
- 数学 Math、几何 Geometry
-
拆分知识点
-
刻意练习 - 过遍数（五毒神掌）、练习缺陷、弱点地方
-
即时反馈（主动、被动）
- 仔细看题目、明白多看几遍、明白题目的意思
- 想所有可能的解法 -> 找最优
- 写代码
- 测试
- 5分钟：读题 + 思考
- 如果没有思路，直接看解法，比较优劣
- 背诵、默写好的解法
- 写代码测试 -> 最优
- 过一天，重复做题
- 过一周，重复做题
- 过一个星期，恢复性训练
常见的时间复杂度：
-
O(1) — 常数复杂度
-
O(log n) — 对数复杂度
-
O(n) — 线性复杂度
-
O(n log n) — 对数线性复杂度
-
O(nᵏ) — 多项式复杂度
-
O(kⁿ) — 指数复杂度
-
O(n!) — 阶乘复杂度
增删慢，时间复杂度 O(n)
查询快，时间复杂度 O(1)
增删快，时间复杂度 O(1)
查询慢，时间复杂度 O(n)
为了补足链表的缺陷而设计出来。
解决方法：升维、空间换时间
链表：增加索引，时间复杂度 O(log n)、空间复杂度 O(n)
- Stack：先入后出；添加、删除为 O(1)
- Queue：先入后出；添加、删除为 O(1)
Stack 推荐使用：
Deque<Integer> stack = new ArrayDeque<>();- empty()
- peek()
- pop()
- push()
- search()
Queue ：
会抛异常 不会抛异常
add(e) offer(e)
remove() poll()
element() peek()Deque：双端队列
-
插入操作：O(1)
-
取出操作：O(log n) - 按照元素的优先级取出
-
底层具体实现的数据结构仅为多样和复杂：heap、bst、treap
Java 实现：PriorityQueue，基于优先堆的一个无界队列
20、155、84、239（滑动窗口用队列）、622、42哈希表，也叫散列表，是根据关键码值而直接进行访问的数据结构。通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度，这个映射函数叫做散列函数，存放记录的数组叫作哈希表。
map：键值对
set：不重复
242、49、1树（通常用递归）：
public class TreeNode {
public int val;
public TreeNode left, right;
public TreeNode(int val) {
this.val = val;
this.left = null;
this.right = null;
}
}遍历：
-
前序：根左右
-
中序：左根右
-
后序：左右根
二叉树：左右节点
二叉搜索树：BST
- 左子树上所有结点的值均小于它的根结点的值
- 右子树上所有结点的值均大于它的根结点的值
- 中序遍历 - 升序
94、144、590、589、429递归的本质就是循环：通过函数体来进行循环。
模板代码
def recursion (level, parma1, param2):
# 递归终止条件
if(level > MAX_LEVEL):
process_result;
return
# 处理当前层逻辑
process(level,data...)
# 下探到下一层
self.recursion(level + 1,p1...)
# 清理当前层的一些数据 -> 有时候不需要
解决递归的思维：
- 不要人肉进行递归
- 重复子问题
- 数学归纳法思维
70、22、226、98、104、111、297、47、46、77、105、236本质就是递归。
分治：
def divide_conquer(problem, param1, param2...):
# 递归终止条件
if problem is None:
print_result
return
# 拆分子问题
data = prepare_data(problem)
sub = split_problem(problem, data)
# 下探到下一层
sub1 = self.divide_conquer(sub[0],p1...)
sub2 = self.divide_conquer(sub[1],p1...)
...
# 组装结果
return process_result(sub1,sub2...)
# 清理当前层的一些数据 -> 有时候不需要回溯:
不断每一层去试一试，不合适退一步。
- 找到一个可能存在的正确的答案
- 尝试所有可能的分步方法宣告该问题没有答案
17、50、78、169、51搜索-遍历
- 每个节点都要访问一次
- 每个节点仅访问一次
- 对于节点的访问顺序不同：深度优先 dfs、广度优先 bfs
# 深度优先 dfs
def dfs(node):
if node in visited:
return
visited.add(node)
dfs(node.left)
dfs(node.right)
def dfs(node, visited):
visited.add(node)
for next_node in node.chirlder():
if not next_node in visited:
dfs(next_node, visited)
# 广度优先 bfs
# 102
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
if(root == null) return new ArrayList<>();
List<List<Integer>> ret = new ArrayList<>();
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while(!queue.isEmpty()){
int size = queue.size();
List<Integer> temp = new ArrayList<>();
for(int i = 0; i < size; i++){
TreeNode tn = queue.poll();
temp.add(tn.val);
if(tn.left != null){
queue.add(tn.left);
}
if(tn.right != null){
queue.add(tn.right);
}
}
ret.add(temp);
}
return ret;
}
}102、515、22、433贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解 。
贪心：局部最优，不能回退
回溯：能够回退
动态规划：最优判断保存结果 + 回退
练习题 ：322、860、122、455、874、55、45前提：
- 目标函数的单调性
- 存在上下界
- 能够通过索引访问
int left = 0;
int right = length - 1;
while(left < right) {
int mid = (left + right) >> 1;
if(arr[mid] == target) {
return result;
} else if (array[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}练习题 ：69、367、33、74、153复杂问题分解成子问题：分治 + 最优子结构（淘汰次优解）
思路：
- 最优子结构 opt[n] = best_of(opt[n-1],opt[n-2])
- 存储中间状态：opt[i]
- 递推公式（状态转移方程或者DP方程）
- Fib：opt[i] = opt[n - 1] + opt[n - 2]
练习题 ：62、1143字典树：又称单词查找树，Trie 树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。
练习题 ：208、212并查集：组团、配对
- makeSet(s)：建立一个新的并查集，其中包含s 个单元素集合。
- unionSet(x,y)：把元素x和元素y所在的集合合并，要求去x和y所在的集合不相交，如果相交则不合并。
- find(x)：找到元素x所在的集合的代表，该操作也可以用于判断两个元素是否位于同一个集合，只要将它们各自的代表比较一个就可以了。
练习题：130、200、平衡二叉树（AVL）：是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。这个方案很好的解决了二叉查找树退化成链表的问题，把插入，查找，删除的时间复杂度最好情况和最坏情况都维持在O(logN)。但是频繁旋转会使插入和删除牺牲掉O(logN)左右的时间。
旋转操作：左旋、右旋、左右旋、右左旋
红黑树是一种近似平衡的二叉搜索树，它能够确保任何一个结点的左右子树的高度差小于两倍。
- 每个结点红色、黑色
- 根结点是黑色
- 每个叶结点（NIL空结点）是黑色
- 不能有相邻接的两个红色结点
- 从任一结点到其每个叶子的所有路径都包含相同数目的黑色结点
判断奇偶
x % 2 == 1 -> (x & 1) == 1
x % 2 == 0 -> (x & 1) == 0
x >> 1 -> x / 2
x & (x -1) 清零最低位的 1
x & -x => 得到最低位的 1
x & -x => 0 练习题：338、52、51、190、231、191布隆过滤器：只是检索元素在还是不在，简化版 HashMap。
一个很长的二进制向量和一系列随机映射函数，用于检索一个元素是否（可能存在）在一个集合中。
练习题：709、58、8、387、771、344、438KMP 算法
public class KMP {
public int kmp(String ts, String ps) {
char[] t = ts.toCharArray();
char[] p = ps.toCharArray();
int[] next = next(ps);
int i = 0;
int j = 0;
while (i < t.length && j < p.length) {
if (j == -1 || t[i] == p[j]) {
i++;
j++;
} else {
j = next[j];
}
}
if (j == ps.length()) {
return i - j;
} else {
return -1;
}
}
private int[] next(String ps) {
char[] p = ps.toCharArray();
int[] next = new int[p.length];
next[0] = -1;
int i = 0;
int j = -1;
while (i < p.length - 1) {
if (j == -1 || p[i] == p[j]) {
next[++i] = ++j;
} else {
j = next[j];
}
}
return next;
}
}