算法与数据结构

2021-03-12

复习入口

Word count: 5.7k | Reading time≈ 24 min

一、树

二叉树的遍历

二叉树的性质

性质1：在二叉树第i层的节点数最多为$2^{i-1}(i>=1)$
性质2：高度为k的二叉树节点总数为$2^k-1(k>=1)$
性质3：对于任意的非空二叉树，如果叶子节点的个数为$n_0$，而其度为2的节点数为$n_2$，则：$n_0=n_2+1$

满二叉树

深度为k，且有$2^k-1$个节点称为满二叉树。

性质4：第i层的节点数为$2^{i-1}$

完全二叉树

最后一层从右左缺，成为完全二叉树。

性质5：有n个节点的完全二叉树的高度是$log_2^n+1$

二叉树的构造和遍历

节点构造

public class TreeNode {
    public int val=0;
    public TreeNode left = null;
    public TreeNode right = null;
    public int getVal() {
        return val;
    }
    public TreeNode(int val) {
        this.val = val;
    }
}

建树与遍历

//主函数
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Stack;

public class BinTreeMain {

    /**
     * @param args
     */
    private int[] array = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
    private static List<TreeNode> nodeList = null;

    public static void main(String[] args) {
        new BinTreeMain().createBinTree();
        TreeNode root = nodeList.get(0);
        System.out.println("递归先序：");
        preOrder(root);
        System.out.println("非递归先序：");
        PreOrder(root);
        System.out.println("递归中序：");
        inOrder(root);
        System.out.println("非递归中序：");
        InOrder(root);
        System.out.println();
        postOrder(root);
        System.out.println();
        levelOrder(root);
        System.out.println();
        System.out.println(Height(root));
        new BinTreeMain().Mirror(root);
        levelOrder(root);
        System.out.println(isSymmetrical(root));

    }

    // 建树
    public void createBinTree() {
        nodeList = new LinkedList<TreeNode>();
        for (int i = 0; i < array.length; i++)
            nodeList.add(new TreeNode(array[i]));
        for (int parentIndex = 0; parentIndex < array.length / 2 - 1; parentIndex++) {
            // 左孩子
            nodeList.get(parentIndex).left = nodeList.get(parentIndex * 2 + 1);
            nodeList.get(parentIndex).right = nodeList.get(parentIndex * 2 + 2);
        }
        int lastparentIndex = array.length / 2 - 1;
        nodeList.get(lastparentIndex).left = nodeList
                .get(lastparentIndex * 2 + 1);
        if (array.length % 2 == 1)
            nodeList.get(lastparentIndex).right = nodeList
                    .get(lastparentIndex * 2 + 2);

    }

    // 先序遍历输出-递归
    public static void preOrder(TreeNode node) {
        if (node != null) {
            System.out.print(node.val + "\t");
            preOrder(node.left);
            preOrder(node.right);

        }
    }

    // 先序遍历输出-非递归
    public static void PreOrder(TreeNode node) {
        Stack<TreeNode> stack = new Stack<TreeNode>();
        if (node != null) {
            TreeNode p = node;
            while (p != null || !stack.isEmpty()) {
                if (p != null) {
                    System.out.print(p.val + "\t");
                    stack.push(p);
                    p = p.left;
                } else {//在刚才那个p的左子树为空，或者p为叶子节点时执行。
                    p = stack.pop();
                    p = p.right;

                }

            }
        }
    }

    // 中序遍历输出
    public static void inOrder(TreeNode node) {
        if (node != null) {
            inOrder(node.left);
            System.out.print(node.val + "\t");
            inOrder(node.right);

        }
    }
    //中序遍历-非递归
    public static void InOrder(TreeNode node){
        Stack<TreeNode> stack = new Stack<TreeNode>();
        if(node!=null){
            TreeNode p = node; 
            while(p!=null||!stack.isEmpty()){
                if(p!=null){
                    stack.push(p);
                    p = p.left;

                }else{
                    p = stack.pop();
                    System.out.print(p.val+"\t");
                    p = p.right;

                }
            }
        }
    }
    // 后序递归遍历输出
    public static void postOrder(TreeNode node) {
        if (node != null) {
            postOrder(node.left);
            postOrder(node.right);
            System.out.print(node.val + "\t");

        }
    }
    //根据先序序列和中序序列唯一建造一棵二叉树，返回二叉树的根
    public TreeNode preAndinCreateTree(char[] pre,char[] in,int i,int j,int m,int n){
        //数组pre存储先序序列，i,j分别表示pre的上标和下标
        //in：中序序列，m，n分别表示in的上标和下标
        //函数返回先序序列和中序序列构成的树的根
        int k;
        TreeNode p=null;
        if(n<0)
            return null;
        p = new TreeNode(pre[i]);
        k = m;
        //在中序中找根
        while((k<=n)&&in[k]!=pre[i])
            k++;
        p.left = preAndinCreateTree(pre,in,i+1,i+k-m,m,k-1);
        p.right = preAndinCreateTree(pre,in,i+k-m+1,j,k+1,n);
        return p;
    }

    // 层次遍历
    public static void levelOrder(TreeNode node) {
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        if (node != null) {
            queue.add(node);
            while (!queue.isEmpty()) {
                TreeNode nnode = queue.poll();
                System.out.print(nnode.val + "\t");
                if (nnode.left != null)
                    queue.add(nnode.left);
                if (nnode.right != null)
                    queue.add(nnode.right);
            }
        }
    }
    // 求二叉树的高度
    public static int Height(TreeNode node) {
        int lh, rh;
        if (node == null)
            return 0;
        else {
            lh = Height(node.left);
            rh = Height(node.right);
            return 1 + (lh > rh ? lh : rh);
        }
    }

    // 操作给定的二叉树，将其变换为源二叉树的镜像。
    public void Mirror(TreeNode root) {
        if (root != null) {
            TreeNode temp = root.left;
            root.left = root.right;
            root.right = temp;
            Mirror(root.left);
            Mirror(root.right);
        }
    }
    /*
     * 二叉树的下一个结点 给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。
     * 注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。
     */
    // 对称的二叉树
    static boolean isSymmetrical(TreeNode pRoot) {
        if (pRoot == null)
            return true;

        return lrSym(pRoot.left, pRoot.right);

    }

    static boolean lrSym(TreeNode left, TreeNode right) {

        if (left == null && right == null)
            return true;
        if (left != null && right != null)
            return left.val == right.val && lrSym(left.left, right.right)
                    && lrSym(left.right, right.left);
        return false;
    }
}

堆

通常可以看做一棵树的数组对象。实际上为二叉树的一种。通常通过一维数组实现的，在数组起始位置为1时：

父节点i的左子节点的位置为$2*i$
父节点i的右子节点所在位置为$2*i+1$
子节点i的父节点位置是$i/2$

哈夫曼树

又称为最优二叉树，是一种带权路径长度最短的二叉树，数的路径长度是树根到每一个节点的长度之和，记作：$WPL=W_1L_1+W_2L_2+…+W_n*L_n$

构造：

根据给定的n个权值(W1,W2...Wn)，使对应节点构成n个二叉树的森林T=(T1,T2...Tn)，其中每个二叉树Ti(1 <= i <= n)中都有一个带权值为Wi的根节点，其左、右子树均为空。
在森林T中选取两个节点权值最小的子树，分别作为左、右子树构造一个新的二叉树，且置新的二叉树的根节点的权值为其左右子树上根节点权值之和。
在森林T中，用新得到的二叉树替代选取的两个二叉树。
重复2和3，直到T只包含一个树为止。这个树就是霍夫曼树。

霍夫曼编码：

对于哈夫曼树，左链取0，右链取1，从树根到叶子的所有编码，常被用作一种压缩算法。

带权路径：

节点的权：节点有值
节点的带权路径：根节点到该节点的路径长度与节点权的乘积
树的带权路径：所有叶子节点的带权路径长度之和，记作WPL

二叉排序树

空数或具备下列性质：

节点左不空，左子树上的节点值均小于根节点
右不空，则根节点小于右
节点的左右子树都是排序树
没有键值相等的节点。

二分查找的时间复杂度是：$O(log(n))$，最坏是$O(n)$，相当于顺序查找

二叉平衡树

一种改进的二叉查找树，二叉查找树的查询复杂度和深度有关，因此当深度比较大的时候，查找复杂度会上升。平衡树诞生了。平衡指叶子的深度趋于平衡，广义的指树的可能查找的均摊复杂度偏低。

AVL树

最先发明的平衡二叉查找树，在AVL 树中，任意两个子树的高度差别为1，也称为高度平衡树。

左右子树都是平衡二叉树
左右子树的深度差小于1

增加删除需要一次或多次树旋来重新平衡。

右旋：左节点转到根节点位置
左旋：有节点转到根节点位置

高度为k的AVL树，节点数最多$2^k-1$，即满二叉树。

平衡因子：节点的左子树与右子树的深度差，只能是0，-1,1。

红黑树

是一种自平衡二叉查找树，每个节点都是红色或者黑色，优于AVL树，牺牲了部分平衡性来换取插入/删除操作时少量的旋转，有效的红黑树有如下要求：

节点红黑
根是黑色
叶子都是黑色
红节点必须有两个黑色的子节点
任一节点到其每个叶子的所有简单路径都包含相同的黑色节点。

如果一条路径上的顶点除了起点和终点可以相同外，其他顶点均不相同，则称此路径为一条简单路径；起点和重点相同的简单路径成为回路（环）。

B-树

B+树

Trie树

又称为前缀树，字典树，是一种有序树，用于保存关联数组，其中的键通常是字符串。与查找树不同，键不是直接保存在节点中，而是由节点在树中的位置决定的，一个节点的所有子孙都有相同的前缀，也就是这个节点对应的字符串，一般般情况下，不是所有的节点都有对应的值，只有叶子结点和部分内容节点所对应的键才会有对应的值。

查询和插入的时间复杂度都是O(n)，是一种空间换时间的方法。当节点树较多的时候，占用的内存比较大。

常用于搜索提示。当输入一个网址，可以自动搜索出可能出现的选择，当没有完全匹配的搜索结果，返回前缀最相似的可能。

二、Hash

也叫作散列表，映射关系，主要解决两个问题，哈希冲突和冲突解决。

哈希函数：

也称为散列函数，对不同的输入值得到一个固定长度的消息摘要，理想的哈希函数应该是对不同的输入值产生不同的结构，同时散列结果应该具有同一性（输出值尽量均匀）和雪崩效应（微小的输入值发生巨大的输出变化）。

冲突解决：

开放链地址法：以发生冲突的地址为输入，通过某种哈希冲突得到一个新的空闲的哈希地址：
- 线性探查：以发生冲突的地址开始，一次探查下一个地址。
- 平方探查：假设冲突地址为d0，查探查序列为$d0+1^2,d0-1^2,d0+2^2,,,$
拉链法：把所有的同义词用单链表连接起来，在这种情况下，哈希表的每个单元存放的不再是元素本身，而是相应同义词单链表的头指针。HashMap就是用这种方法解决冲突的。

四、图

这里图的比较重要的算法有：深度优先，广度优先，最短路径算法，拓扑排序，并查集。

queue.offer()是出队，queue.poll()是进队

广度优先搜索

深度优先搜索和广度优先搜索，超详细图文解析_Viper的程序员修炼手册-CSDN博客_深度优先广度优先图解

import java.util.*;

class Solution {
    public List<Integer> BFS(int vexNum,int[][]matrix){
        Queue<Integer> queue = new LinkedList<>();
        List<Integer> resList = new LinkedList<>();
        int[] visited = new int[vexNum];
        //从0节点开始遍历
        visited[0] = 1;
        queue.offer(0);
        //队列不空的时候循环
        while (!queue.isEmpty()){
            int index = queue.poll();
            //加入到结果序列
            resList.add(index);
            for(int i = 0;i<vexNum;i++){
                if(matrix[index][i]==1 && visited[i] == 0){
                    queue.offer(i);
                    visited[i] = 1;
                }
            }
        }
        return resList;
    }
}

深度优先搜索

深度优先遍历(DFS)、广度优先遍历(BFS)、随机游走(Random Walk)_Moer_hou的博客-CSDN博客

import java.util.*;

class Solution {
    public List<Integer> DFS(int vexNum, int[][]matrix){
        Stack<Integer> stack = new Stack<>();
        int[] visited = new int[vexNum];
        List<Integer> resList = new LinkedList<>();
        //从0节点开始遍历
        stack.push(0);
        visited[0] = 1;
        for(int i = 0;i<vexNum;i++){
            int index = stack.pop();
            if(matrix[index][i]==1 && visited[i]==0){
                stack.push(i);
                visited[i] = 1;
            }
        }
        return resList;
    }
}

例题—矩阵中的最长递增路径

给定一个整数矩阵，找出最长递增路径的长度，对于每个单元格，可以上下左右四个方向移动。不能往对角线移动。

思路是在两个循环里，调用dfs，值得注意的是，本题不需要visited数组，因为要求递增，所以要求访问的下一个节点比上一个大，所以不会出现死循环。、

对于给定的定点nums[i][j]，在调用dfs的时候，需要向上下左右四个方向访问，四个防线，每个方向都需要判断边界是否溢出，不溢出的情况下判断下一个节点是否大于当前节点，因此需要进行四次递归，写出来的DFS是这样的

public static int find(int row,int col,int[][]matrix,Map<String,Integer> map){
    int up = 0,down = 0,left = 0,right =0;
    if(row-1>=0 && col<matrix[0].length && col>=0 && col<matrix[0].length && matrix[row][col]<matrix[row+1][col]){
        down = find(row-1,col,matrix,map);
    }
    //***
    return Math.max(Math.max(Math.max(up,down),left),right)+1;
}

拓扑排序

算法步骤：

构造一个队列Q和拓扑排序的结果队列T
把所有没有依赖顶点的节点放入Q
当Q还有顶点的时候，执行以下步骤：
- 从Q中取出一个顶点n，放入T
- 对n每一个临接点m
  - 去掉边<n,m>
  - 如果m没有依赖顶点，把m放入Q

public int[] findOrder(int numCourses,int[][]preOrders){
    Queue<Integer> resQueue = new LinkedList<>();
    int[] countArr = new int[numCourses];
    //统计每个节点的入度
    for(int[] entry:preOrders){
        countArr[entry[0]]++;
    }
    Queue<Integer> queue = new LinkedList<>();
    //没有入度的定点入栈
    for(int i = 0;i<numCourses;i++){
        if(countArr[i]==0){
            queue.offer(i);
            numCourses--;
        }
    }
    //开始广度优先遍历
    while (!queue.isEmpty()){
        int index = queue.poll();
        resQueue.offer(index);
        for(int[] entry:preOrders){
            if(entry[1]==index){
                if(--countArr[entry[0]]==0){
                    numCourses--;
                    queue.offer(entry[0]);
                }
            }
        }
    }
    if(numCourses==0){
        int[] res = new int[numCourses];
        for(int i = 0;i<numCourses;i++){
            res[i] = resQueue.poll();
        }
        return res;
    }else {
        return new int[0];
    }
}

并查集

并查集详解及底层实现| 记路心晴

并查集主要用于描述集合，如可以将一对相关点划分成几个独立的集合以及某个元素是否属于某个集合，两个元素是否在一个集合中。

基本并查集

基于数组实现的并查集，最基本的思想是，数组下标为当前元素标号，元素值是下标所在的集合，当两个严肃合并的时候，以较大元素为大哥，将另一组元素的值全部更新。

import java.util.*;
//下标为元素，值为所在集合
public class Union {
    private int size;
    private int[] id;
    //构造函数
    public Union(int size){
        this.size = size;
        id = new int[size];
        for(int i = 0;i<size;i++){
            id[i] = i;
        }
    }
    //查找某个元素属于哪一个集合
    public int find(int element){
        return id[element];
    }

    //判断两个严肃是否属于同一个集合
    public boolean isConnected(int first,int second){
        return find(first)==find(second);
    }

    //合并两个集合
    public void merge(int firstEle,int secondEle){
        //本来就是一个集合，直接返回
        if(find(firstEle)==find(secondEle)){
            return;
        }else {
            int firRoot = find(firstEle);
            int secRoot = find(secondEle);
            if(firRoot<secRoot){
                for(int i = 0;i<size;i++){
                    if(id[i]==firRoot)id[i] = secRoot;
                }
            }else {
                for(int i = 0;i<size;i++){
                    if(id[i] == secRoot)id[i] = firRoot;
                }
            }
        }
    }
}

上述方法在查找元素的时候很快，但是union很慢。因为每次union都需要遍历整个数组。

快Union，慢find

在上面的例子中，每次merge都需要遍历整个数组，我们现在每次只更新一个数据，形成一个链，但是这样查找就比较慢了。

//查找某个元素属于哪一个集合
public int find(int element){
    while (id[element]!=element){
        element = id[element];
    }
    return id[element];
}
  
//合并两个集合
public void merge(int firstEle,int secondEle){
    //本来就是一个集合，直接返回
    if(find(firstEle)==find(secondEle)){
        return;
    }else {
        int firRoot = find(firstEle);
        int secRoot = find(secondEle);
        if(firRoot<secRoot){
            id[firRoot] = secRoot;
        }else {
            id[secRoot] = firRoot;
        }
    }
}

迪杰斯特拉算法

迪杰斯特拉(Dijkstra)算法_xiaoxi_hahaha的博客-CSDN博客

求解单源点最短路径。

public static int[] d(int[][]weight,int start){
    //求解的是source到各个顶点的最短路径
    boolean[] visited = new boolean[weight.length];
    int[] res = new int[weight.length];
    //初始化结果矩阵
    for(int i = 0;i<weight.length;i++){
        res[i] = weight[start][i];
    }
    //查找n-1次，每次确定一个点
    for(int i = 1;i< weight.length;i++){
        int min = Integer.MAX_VALUE;
        int p = 0;
        //找出一个未标记并且离出发点最近的节点
        for(int j = 0;j< weight.length;j++){
            if(j!=start && !visited[j] && res[j]<min){
                min = res[j];
                p = j;
            }
        }
        //标记节点已经访问过
        visited[p] = true;
        for(int j = 0;j<weight.length;j++){
            if(j==p || weight[p][j]==Integer.MAX_VALUE){
                //P点不能到达
                continue;
            }
            if(res[p]+weight[p][j]<res[j]){
                res[j] = res[p]+weight[p][j];
            }
        }
    }
    return res;
}

弗洛伊德算法

采用动态规划的思想对路径距离进行N此更新，N是顶点数，其中顶点(i,j)之间的以K更新的条件是：dis[i][j]>dis[i][k]+dis[k][j]，更新完成之后，我们得到的是图上任意两点之间的最短距离。如何通过path矩阵得到最短路径呢？需要初始化一个记录两点之间的路径的矩阵path[][]，在path矩阵更新的时候，将该对应成功更新两点间距离的点记录在path矩阵对应的位置上。

public static void floyd(int[][]arr,int[][]path){
        int num = arr.length;
        //节点轮流坐庄
        for(int k = 0;k<num;k++){
            for(int i = 0;i<num;i++){
                for(int j = 0; j<num;j++ ){
                    int tmp = arr[i][k]+arr[k][j];
                    if(tmp<arr[i][j]){
                        arr[i][j] = tmp;
                        path[i][j] = k;
                    }
                }
            }
        }
    }

//通过递归的方式寻找路径
    public static String findPath(int start,int end,int[][] path){
        return "点"+start+"到点"+end+"的路径是："+start+"->"+findPath(start,end,path)+end;
    }
    private static String find(int start,int end,int[][] path){
        int mid = path[start][end];
        if(mid==-1){
            return "";
        }
        return find(start,mid,path)+""+mid+"->"+find(mid,end,path);
    }

五、查找算法

1、ASL

平均查找长度，$\mathrm{ASL}=\sum(\mathrm{n}, \mathrm{i}=1) \mathrm{Pi} * \mathrm{Ci}$，其中n为元素个数，Pi是查找第I个元素的概率，一般为$P_i=1/n$，Ci是找到第I个元素所需要的比较次数。

2、顺序查找

让关键字与队列中的数从最后一个开始逐个比较，直到找出与给定关键字相同的数为止，它的缺点是效率低下。**时间复杂度o(n)**。

3、折半查找

折半查找要求线性表示有序表。搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。折半搜索每次把搜索区域减少一半，时间复杂度为O(log n)。

可以借助二叉判定树求得折半查找的平均查找长度：log2(n+1)-1。
折半查找在失败时所需比较的关键字个数不超过判定树的深度，n个元素的判定树的深度和n个元素的完全二叉树的深度相同log2(n)+1。

public int binarySearchStandard(int[] num, int target){
    int start = 0;
    int end = num.length - 1;
    while(start <= end){ //注意1
        int mid = start + ((end - start) >> 1);
        if(num[mid] == target)
            return mid;
        else if(num[mid] > target){
            end = mid - 1; //注意2
        }
        else{
            start = mid + 1; //注意3
        }
    }
    return -1;
}

4、分块查找

分块查找又称索引顺序查找，它是一种性能介于顺序查找和折半查找之间的查找方法。分块查找由于只要求索引表是有序的，对块内节点没有排序要求，因此特别适合于节点动态变化的情况。

六、排序算法

总结

插入类：直接插入，折半插入，希尔排序
选择类：简单选择，堆排序，
交换类：冒泡，快排
归并排序，基数排序，外部排序
$o(nlog_2n)$：快些归队(堆)，快排在有序的情况下最坏是$o(n^2)$
不稳定：快些(希)选一堆

从小到大

冒泡排序

每次两两比较，把剩余最大或者最小的移动到一端。

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

插入排序

public void insert(int[] nums){
    int n = nums.length;
    for(int i = 1;i<n;i++){
        int j = i;
        int temp = nums[i];
        while (nums[j]<nums[j-1] && j>0){
            nums[j] = nums[j-1];
            j--;
        }
        nums[j] = temp;
    }
}

插入排序

简单选择

public void select(int[] nums){
    //每次找到最小的元素和前面进行交换
    for(int i = 0;i<nums.length;i++){
        int index = i;
        for(int j = i+1;j<nums.length;j++){
            if(nums[j]<nums[index])index = j;
        }
        int temp = nums[i];
        nums[i] = nums[index];
        nums[index] = temp;
    }
}

选择排序

快排

public void quick_sort(int[] nums,int low,int high){
    int i = low;
    int j = high;
    if(low<high){
        int temp = nums[high];
        while (i<j){
            while (i<j && nums[j]<=temp) j--;
            if(i<j){
                nums[i] = nums[j];
                i++;
            }
            while (i<j && nums[i]>temp) i++;
            if(i<j){
                nums[j] = nums[i];
                j--;
            }
        }
        nums[i] = temp;
        quick_sort(nums,low,i-1);
        quick_sort(nums,i+1,high);
    }
}

七、跳跃表

一种数据结构，用于快速查询一个有序连续元素的数据链表。平均查找和插入的时间复杂度是$O(log_n)$。

维护了一个多层次的链表，每一层链表的元素是上一层链表元素的子集。开始算法在最稀疏的层次搜索，直到需要查找的元素在该层两个元素之间，算法跳跃到下一个层次，重复刚刚的搜索，直到找到需要查找的元素。跳过的元素的方法可以是 随机性选择 或 确定性选择，其中前者更为常见。

在查找目标元素时，从顶层列表、头元素起步。算法沿着每层链表搜索，直至找到一个大于或等于目标的元素，或者到达当前层列表末尾。如果该元素等于目标元素，则表明该元素已被找到；如果该元素大于目标元素或已到达链表末尾，则退回到当前层的上一个元素，然后转入下一层进行搜索。

Copyright： Copyright is owned by the author. For commercial reprints, please contact the author for authorization. For non-commercial reprints, please indicate the source.