由于有笔者实力有限，本篇文章目前包含的内容不足以覆盖八股全部数据结构于算法考点。文章内容会实时更新

1. 常用数据结构详解

1.1 链表

1.1.1 跳跃表

1. 是什么：带有层级结构的链表

2. 为什么：CRUD操作平均时间复杂度为O(logn)

3. 怎么做：

• 数据结构：链表有序排列，但是会划分层级，可以通过层级节点直接抵达

• 增：反复生成随机数得到层级

• 删：直接删

• 改查：先看同层链表，大了就换下一层指针

1. 应用场景：Redis有序集合ZSet的实现

1.2 树

1.2.1 二叉树

1. 二叉树：树状数据结构，每个节点有2个子节点

2. 二叉树的性质：n层二叉树，每一层有$$2^{n-1}$$个，共有$$2^n-1$$个

3. 数组实现二叉树结构：

   1. 数组以层序遍历的性质存储二叉树

   2. index=0处存储根节点

   3. 数组二叉树的性质1：任意节点index=m,其子节点index=[2*m+1],[2*m+2]

   4. 数组二叉树的性质2：任意节点index=m,其父节点index=[(m-1)/2]

1.2.2 平衡二叉树

1. 是什么：任意节点的左右子树高度差不超过1的二叉树

	查/改	增/删
时间复杂度	O(logn)	O(logn)

1. 为什么：

   1. 优点：树的高度为二叉树理论最小值h = logn, 增删改查性能好

   2. 缺点：增删后的旋转操作复杂，时间为O(logn)，效率低

   3. 应用场景：平衡二叉树已被红黑树取代，不常用

2. 怎么做：AVL树通过旋转实现平衡

LL平衡

RR平衡

LR平衡

RL平衡

1.2.3 红黑树

1. 是什么：最大高度<2*最小高度 的弱平衡二叉树，满足搜索二叉树的要求，左侧节点<val<右侧节点

2. 为什么：比平衡二叉树的旋转次数少，增删性能高于AVL树，查找性能略低于理论值，但是可以忽略不计。

3. 怎么做：给节点染红或黑色

   1. 根 和 叶子节点 必须是黑色

   2. 叶子节点是空节点(如果有数据需要new Node(null))

   3. 红色节点的 父节点 和 子节点必须是黑色

   4. 红黑树的任意路径的 黑色节点数 相同

4. 红黑树的插入

   1. 插入节点默认染红，父节点为黑无影响

   2. 父亲辈节点都红，上三角颜色取反

   3. 左左/右右：提起中间，爷孙放两边

   4. 左右/右左：提起底边，爷爹放两边

5. 应用场景

   1. C++STL的实现

   2. Linux的完全公平进程调度程序

   3. Java TreeMap，HashMap的实现

1.2.4 B树

1. 是什么：满足特定条件的m阶多路平衡查找树

   1. 每个节点最多有 m-1 个键值对，有序排列

   2. 根节点至少有 1 个键值对，非根节点至少有 m/2个键值对

   3. 父节点left key < 子节点key < 父节点right key

   4. B树的路径高度必须完全相同

2. 为什么：B树的子树多，树形矮胖，磁盘寻址次数少，读写效率高

1.2.5 B+树

1. 是什么：B树的变体

   1. 满足B树的树形要求

   2. 非叶子节点只存储键值，不存储数据

   3. 叶子节点之间增加链指针

2. 为什么

1. 由于B+树非叶子节点不存储数据，查询的时间复杂度为稳定的O(logn)。B树虽然更快，但是不稳定

2. 由于非叶子节点不存储数据，单个磁盘IO单元可以存储更多的节点，减少磁盘IO次数

3. B+树的链指针实现了范围查找，可以返回一组数据

4. 根据空间局部性原理，将范围查找的数据存放到内存，可以减少磁盘的IO次数，提高查询效率

3. 怎么做

1. 查/改：单个节点间的key二分查找，树间通过key查找

2. 增/删：分裂，合并，旋转

1.2.6 堆

1. 堆：也称优先队列，是部分有序的完全二叉树，堆中的父节点总是 大于/小于 子节点, 不要求同层节点的大小关系的完全二叉树

2. java实现最小堆：根节点是最小的

class MinHeap{
    private int size;
    private int heap[];
    
    private void swap(int a,int b){
        int tmp = heap[a];
        heap[a] = heap[b];
        heap[b] = tmp;
    }
    
    //堆化函数：如果root的子节点均符合堆，那么堆化后root也成为堆
    private void heapify(int root){
        int left = root*2+1;
        int right = root*2+2;
        //寻找root,root->left,root->right中最小的元素，和root替换
        int minIndex = root;
        if(left<size && heap[left]<heap[right]){
            minIndex = left;
        }
        if(right<size && heap[right]<heap[minIndex]){
            minIndex = right;
        }
        //如果当前root不符合堆，那么交换元素，递归堆化
        if(minIndex!=root){
            swap(root,minIndex);
            heapify(minIndex);
        }
    }
    
    //构造函数：将一个普通数组堆化
    public MinHeap(int[] init){
        size = init.length;
        heap = new int[size];
        for(int i=0;i<size;i++){
            heap[i] = init[i];
        }
        //遍历非叶子节点，自底向上堆化
        for(int i=size/2-1;i>=0;i--){
            heapify(i);
        }
    }
    
    //poll+add:保持size不变，弹出堆顶，再添加一个
    public int add(int x){
        if(x<=heap[0]){
            return x;
        }
        else{
            int res = heap[0];
            heap[0] = x;
            heapify(0);
            return res;
        }
    }
}

2. 常用算法相详解

2.1 数组排序

2.1.1 冒泡排序

1. 时间复杂度O(n^2)

2. 核心思想：每次交换一组数字

3. Java实现冒泡排序

public int[] bubble(int[] nums){
    for(int i=0;i<nums.length;i++){
        for(int j=0;j<nums.length-1;j++){
            if(nums[j]>nums[j+1]){
                int tmp = nums[j];
                nums[j] = nums[j+1];
                nums[j+1] = tmp;
            }
        }
    }
    return nums;
}

2.1.2 插入排序

1. 时间复杂度O(n^2)

2. 核心思想：每次确认一个数字位置

3. Java实现插入排序

public int[] insert(int[] nums){
    for(int i=0;i<nums.length;i++){
        int min_index = i;
        for(int j=i+1;j<nums.length;j++){
            if(nums[j]<nums[min_index]){
                min_index = j;
            }
        }   
        int tmp = nums[i];
        nums[i] = nums[min_index];
        nums[min_index] = tmp;
    }
    return nums;
}

2.1.3 快速排序

1. 快速排序的时间复杂度：O(nlogn)

2. 快速排序的稳定性：不稳定

3. 快速排序的核心思想：分治法

4. Java实现快速排序：

class Solution{
    public int[] sortArray(int[] nums){
        quickSort(nums,0,nums.length-1);
        return nums;
    }
    
    public void quickSort(int[] nums,int left,int right){
        //递归终止条件
        if(left>=right){return;}
        //随机找出基准元素,置于左侧
        Random random = new Random();
        int stan_index = left + random.nextInt(right-left+1);
        int standard = nums[stan_index];
        swap(nums,left,stan_index);
        //双指针快速排序
        int lptr = left+1;
        int rptr = right;
        while(lptr<rptr){
            while(nums[lptr]<standard && lptr<rptr){
                lptr++;
            }
            while(nums[rptr]>=standard && lptr<rptr){
                rptr--;
            }
            swap(nums,lptr,rptr);
        }
        //找出基准元素排序后的位置,换回基准元素
        if(standard<=nums[lptr]){
            lptr--;
        }
        swap(nums,left,lptr);
        //递归调用
        quickSort(nums,left,lptr-1);
        quickSort(nums,lptr+1,right);
    }
}

• 代码理解：lptr<rptr这里是否需要等于号？

答：用不用都可以。

• 如果不用等号，当循环跳出时，两个指针相交时，不能确认standard的位置，需要再迭代调整

• 如果用等号，当循环跳出时，两个指针交错，此时必定左侧位置为standard，不需迭代。但是使用等号会将原本有序的数组swap

5. Arrays.sort(): 该方法基于快排实现

• 如果输入是基本类型数组：使用双轴快排，使用2个轴把数组分为3部分

• 如果输入是对象类型数组：使用归并排序

2.1.4 归并排序

1. 快速排序的时间复杂度：O(nlogn)

2. 快速排序的稳定性：稳定

3. 快速排序的核心思想：分治法

4. java实现归并排序：

public void mergesort(int[] nums,int ll,int rr){
        if(ll>=rr){
            return;
        }
        int mid = (ll+rr)/2;
        //递归
        mergesort(nums,ll,mid);
        mergesort(nums,mid+1,rr);
        int[] tmp = new int[rr-ll+1];
        int left = ll;
        int right = mid+1;
        //双链表合并
        for(int i=0;i<rr-ll+1;i++){
            if(left>mid){
                tmp[i] = nums[right];
                right++;
            }
            else if(right>rr){
                tmp[i] = nums[left];
                left++;
            }
            else if(nums[left]<nums[right]){
                tmp[i] = nums[left];
                left++;
            }
            else{
                tmp[i] = nums[right];
                right++;
            }
        }
        //数组赋值
        for(int i=ll;i<=rr;i++){
            nums[i] = tmp[i-ll];
        }
    }

1. 循环实现归并：自底向上

2.1.5 拓扑排序

1. 什么是拓扑排序：对有向无环图的节点进行排序的过程

2. 怎么进行拓扑排序：

   1. 找到入度为 0 的点，作为起点

   2. 使用队列+广度优先搜索，完成排序

3. C++实现拓扑排序

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>> &prerequisites) {
        // 用于存储每门课的后继课程
        vector<vector<int>> sub(numCourses);
        // 存储每门课的入度
        vector<int> in_degree(numCourses, 0);
        // 构建图和入度表
        for (auto &e: prerequisites) {
            sub[e[1]].push_back(e[0]);
            in_degree[e[0]]++;
        }
        // 将所有入度为0的课程加入队列
        queue<int> q;
        for (int i = 0; i < numCourses; i++) {
            if (in_degree[i] == 0) {
                q.push(i);
            }
        }
        int cnt = 0;  // 计数器，统计可以完成的课程数量
        // 拓扑排序
        while (!q.empty()) {
            int t = q.front();
            q.pop();
            cnt++;
            for (auto j: sub[t]) {
                if (--in_degree[j] == 0) {
                    q.push(j);
                }
            }
        }
        
        // 如果可以完成的课程数量等于总课程数量，返回true
        return cnt == numCourses;
    }
};

2.2 图算法

2.2.1 Dijkstra算法

1. Dijkstra算法：最短路径算法

   1. 原理：bfs + 贪心

   2. 时间复杂度：O(n2)

2.2.2 Floyd算法

1. Floyd算法：最短路径算法

   1. 原理：动态规划

   2. 时间复杂度：O(n3)

2.3 哈希算法

2.3.1 MD5算法

1. 什么是MD5算法：一种散列算法/摘要算法

   1. MD5算法是单向的，哈希值不可逆

   2. MD5运算后的长度是固定的

md5通过指定hash映射为一串字符，然后提取部分字符作为md5结果。因为md5不包含全部信息，所以不能用于信息加密传输，只能用于检验。md5狭义上不算加密算法，是有损的。只不过实现了加密功能。

2. MD5算法的应用

1. 校验文件完整性：和完整文件的MD5哈希值进行比较

2. 鉴别用户：和数据库的哈希值和MD5变换后的用户信息进行比较

2.3.2 RSA算法

1. 什么是RSA算法：一种公开密钥加密算法

   1. 非对称加密，加密和解密的密钥不同

   2. 加密使用公开密钥，解密使用私有密钥

2. RSA算法的数学原理：利用大素数，欧拉函数与欧拉定理

   1. 欧拉函数φ(n): 小于n且与n互质的正整数的个数

   2. 欧拉定理：任意正整数n和与n互质整数a，有a^φ(n) mod n = 1

3. RSA算法的实现方法：

   1. 生成密钥

      1. 选取大素数p,q

      2. 令n = p*q, 基于欧拉函数可知φ(n)=(p-1)*(q-1)

      3. 选取整数e, 1<e<φ(n)，且与φ(n)互质

      4. 计算整数d, 使的 d*e mod φ(n) = 1

      5. 生成公钥(n,e), 密钥(n,d)

   2. 生成密文

      1. 生成密文C = 明文P^e mod n

      2. 发布公开密钥(e,n)

   3. 解密密文

      1. 明文P = 密文C^d mod n

4. RSA算法的实现原理

   1. 接受方生成公开密钥和私有密钥

   2. 接收方发布公开密钥

   3. 发送方根据公开密钥进行加密，发送给接收方

   4. 接收方根据私有密钥进行解密

2.4 并发算法

2.4.1 CAS

1. 什么是CAS：Compare And Set比较替换算法

2. CAS算法的应用：一切基于乐观锁思想实现的数据结构与算法

   1. C.A.U的所有数据结构

3. CAS算法的实现

   1. 读取内存

   2. 比较内存

   3. 交换内存

CAS是硬件操作，默认保证整个流程的原子性

1. CAS算法的问题

• ABA问题：

  • 在A操作期间，B的操作如果对修改的值没有变化，由于不对其他共享资源进行检测，A不会认为有B操作的存在

  • 影响：对于需要追溯流程的业务，会引发流程缺失

  • 版本号机制：每次修改CAS操作的值版本号+1

举例：CAS维护一个文档，如果线程A操作了文档，但是没有修改，线程B检测不到线程A的操作，没有记录，可能引发安全性问题。

版本号溢出问题：时间戳+计数器

• 循环时间开销问题

• 多原子操作问题

2.5 回溯法

回溯法：回溯算法本质是一种暴力枚举，回溯算法通过遍历状态空间，得到最终结果。

2.5.1 幂集

针对于事件状态空间，我们可以把事件的状态分为：0(未发生), 1(发生), 所以整个时间复杂度为O(2^n)

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        backtrack(nums, 0, new ArrayList<>(), res);
        return res;
    }

    private void backtrack(int[] nums, int start, List<Integer> path, List<List<Integer>> res) {
        res.add(new ArrayList<>(path));
        for (int i = start; i < nums.length; i++) {
            path.add(nums[i]);
            backtrack(nums, i + 1, path, res);
            path.remove(path.size() - 1);
        }
    }
}

2.6 动态规划

1. 动态规划：解决离散有限状态空间最优化问题。数学依据：Bellman方程

2. 回溯角度看动态规划：从回溯算法的角度来看，动态规划是一种记忆化回溯法，DP通过从存储中间状态的信息，使得回溯检索的效率提到到O(1), 使得整个算法的时间复杂度优化到O(n^2)

2.6.1 0-1背包问题

1. 问题描述：存在n种物品，每种物品只有1个，收益为r，重量为m，背包容量M，求背包的最大收益

我们定义每种物品选择数量为w，则问题可以描述为：

1. 解决方案：dp[i][w]：考虑前 i 个物品，背包容量为 w 时的最大价值

     如果不选当前物品，那么最优结果和上一个相同。如果选择当前物品，需要决定是否选择当前物品能够达到最优解

     这里选择物品情况是，第一项使用i-1, 保证当前第 i 行的所有数据只可能选用 1 次当前物品。

   1. 初始状态: dp[0][k] = 0, dp[k][0] = 0

   2. 状态转移方程:

2.6.2 完全背包问题

1. 问题描述：存在n种物品，每种物品数量无限，收益为r，重量为m，背包容量M，求背包的最大收益

我们定义每种物品选择数量为w，则问题可以描述为：

1. 解决方案：以背包容量为状态空间，dp[M]描述大小为M背包的最大收益

   1. 初始状态: dp[0] = 0

   2. 状态转移方程:

如果不选当前物品，那么最优结果和上一个相同。如果选择当前物品，需要决定是否选择当前物品能够达到最优解

这里选择物品情况是，第一项使用 i , 保证当前第 i 行的所有数据只可能选用 1 次当前物品。