## 1 总览

算法总览



### 1.1 数据结构分类

* 一维
  * 基础：数组 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

### 1.2 算法

算法最终基于下面三个基本单元、也就是基石：

* 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

### 1.3 如何练习

* 拆分知识点

* 刻意练习 - 过遍数（五毒神掌）、练习缺陷、弱点地方
* 即时反馈（主动、被动）

### 1.4 切题四件套

* 仔细看题目、明白多看几遍、明白题目的意思
* 想所有可能的解法 -> 找最优
* 写代码
* 测试

### 1.5 五毒神掌

#### 第一遍

* 5分钟：读题 + 思考
* 如果没有思路，直接看解法，比较优劣
* 背诵、默写好的解法

#### 第二遍

* 写代码测试 -> 最优

#### 第三遍

* 过一天，重复做题

#### 第四遍

* 过一周，重复做题

#### 第五遍

* 过一个星期，恢复性训练

## 2 复杂度分析

常见的时间复杂度：

* O(1) — 常数复杂度

* O(log n) — 对数复杂度

* O(n) — 线性复杂度

* O(n log n) — 对数线性复杂度
* O(nᵏ) — 多项式复杂度
* O(kⁿ) — 指数复杂度
* O(n!) — 阶乘复杂度

## 3 数组、链表、跳表

### ArrayList

增删慢，时间复杂度 O(n)

查询快，时间复杂度 O(1)

### LinkedList -> LRU Cache

增删快，时间复杂度 O(1)

查询慢，时间复杂度 O(n)

### 跳表 Skip List -> Redis 中使用

为了补足链表的缺陷而设计出来。

解决方法：**升维、空间换时间**

链表：增加索引，时间复杂度 O(log n)、空间复杂度 O(n)

## 4 栈、队列、优先队列、双端队列

* Stack：先入后出；添加、删除为 O(1)
* Queue：先入后出；添加、删除为 O(1)

Stack 推荐使用：

```java
Deque<Integer> stack = new ArrayDeque<>();
```

* empty()
* peek()
* pop()
* push()
* search()

Queue ：

```java
会抛异常        不会抛异常
add(e)         offer(e)
remove()       poll() 
element()      peek()
```

Deque：双端队列

### Priority Queue ：优先队列

* 插入操作：O(1)

* 取出操作：O(log n) - 按照元素的优先级取出

* 底层具体实现的数据结构仅为多样和复杂：heap、bst、treap

Java 实现：PriorityQueue，基于优先堆的一个无界队列

### 练习题 LeetCode：

```java
20、155、84、239（滑动窗口用队列）、622、42
```

## 5 哈希表、映射、集合

哈希表，也叫散列表，是根据关键码值而直接进行访问的数据结构。通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度，这个映射函数叫做散列函数，存放记录的数组叫作哈希表。

map：键值对

set：不重复

### 练习题 LeetCode：

```java
242、49、1
```

## 6 树、二叉树、二叉搜索树

树（通常用递归）：

```java
public class TreeNode {
    public int val;
    public TreeNode left, right;
    public TreeNode(int val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}
```

遍历：

* 前序：根左右

* 中序：左根右

* 后序：左右根

二叉树：左右节点

二叉搜索树：BST

* 左子树上所有结点的值均小于它的根结点的值
* 右子树上所有结点的值均大于它的根结点的值
* 中序遍历 - 升序

### 练习题 LeetCode

```java
94、144、590、589、429
```

## 7 泛型递归、树的递归

递归的本质就是**循环**：通过函数体来进行循环。

模板代码

```python
def recursion (level, parma1, param2):
    # 递归终止条件
    if(level > MAX_LEVEL):
        process_result;
        return
    # 处理当前层逻辑
    process(level,data...)
    
    # 下探到下一层
    self.recursion(level + 1,p1...)
    
    # 清理当前层的一些数据 -> 有时候不需要
    
```

解决递归的思维：

* 不要人肉进行递归
* 重复子问题
* 数学归纳法思维

### 练习题 LeetCode

```java
70、22、226、98、104、111、297、47、46、77、105、236
```

## 8 分治、回溯

本质就是递归。

分治：

```python
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...)
    
    # 清理当前层的一些数据 -> 有时候不需要
```

回溯:

不断每一层去试一试，不合适退一步。

* 找到一个可能存在的正确的答案
* 尝试所有可能的分步方法宣告该问题没有答案

### 练习题 LeetCode

```java
17、50、78、169、51
```

## 9 深度优先搜索和广度优先搜索

搜索-遍历

* 每个节点都要访问一次
* 每个节点仅访问一次
* 对于节点的访问顺序不同：深度优先 dfs、广度优先 bfs

```python
# 深度优先 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; 
    }
}
```

## 练习题 LeetCode

```java
102、515、22、433
```

## 10 贪心算法

贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解  。

贪心：局部最优，不能回退

回溯：能够回退

动态规划：最优判断保存结果 + 回退

```java
练习题 ：322、860、122、455、874、55、45
```

## 11 二分查找

前提：

* 目标函数的单调性
* 存在上下界
* 能够通过索引访问

```java
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;
    }
}

```



```java
练习题 ：69、367、33、74、153
```

## 12 动态规划

复杂问题分解成子问题：分治 + **最优子结构（淘汰次优解）**

思路：

* 最优子结构 opt[n] = best_of(opt[n-1],opt[n-2])
* 存储中间状态：opt[i]
* 递推公式（状态转移方程或者DP方程）
  * Fib：opt[i] = opt[n - 1] + opt[n - 2]

```java
练习题 ：62、1143
```



## 13 字典树和并查集

字典树：又称单词查找树，Trie 树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。

```java
练习题 ：208、212
```

并查集：组团、配对

* makeSet(s)：建立一个新的并查集，其中包含s 个单元素集合。
* unionSet(x,y)：把元素x和元素y所在的集合合并，要求去x和y所在的集合不相交，如果相交则不合并。
* find(x)：找到元素x所在的集合的代表，该操作也可以用于判断两个元素是否位于同一个集合，只要将它们各自的代表比较一个就可以了。

```java
练习题：130、200、
```



## 14 高级搜索

### 剪枝

### 双向BFS

### 启发式搜索

## 15 红黑树和AVL树

平衡二叉树（AVL）：是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。这个方案很好的解决了二叉查找树退化成链表的问题，把插入，查找，删除的时间复杂度最好情况和最坏情况都维持在O(logN)。但是频繁旋转会使插入和删除牺牲掉O(logN)左右的时间。

旋转操作：左旋、右旋、左右旋、右左旋

红黑树是一种近似平衡的二叉搜索树，它能够确保任何一个结点的左右子树的高度差小于两倍。

* 每个结点红色、黑色
* 根结点是黑色
* 每个叶结点（NIL空结点）是黑色
* 不能有相邻接的两个红色结点
* 从任一结点到其每个叶子的所有路径都包含相同数目的黑色结点

## 16 位运算

```java
判断奇偶
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    
```



```java
练习题：338、52、51、190、231、191
```



## 17 布隆过滤器和 LRU 缓存

布隆过滤器：只是检索元素在还是不在，简化版 HashMap。

一个很长的二进制向量和一系列随机映射函数，用于检索一个元素是否（可能存在）在一个集合中。

## 18 排序算法



## 19 高级动态规划



## 20 字符串算法

```java
练习题：709、58、8、387、771、344、438
```



KMP 算法

```java
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;
    }
}
```

