数据结构和算法

数据结构

数据结构包括

• 线性结构(数据元素之间存在一对一的线性关系)
  • 顺序存储结构(数组)
    • 顺序存储的线性表为顺序表，顺序表中的元素是连续的
  • 链式存储结构 (链表)
    • 链式存储的线性表为链表，链表存储元素不一定连续，元素节点中存储数据元素以及相邻元素的地址信息
  • 数组
  • 队列
  • 链表
  • 栈
• 非线性结构
  • 二维数组
  • 多维数组
  • 广义表
  • 树结构
  • 图结构

稀疏数组

实际的一个需求：

编写的五子棋程序中，有存盘退出和续上盘的功能

使用二维数组记录棋盘

分析问题

因为该二维数组的很多值是默认值0，因此记录了很多没有意义的数据

由此引申出稀疏数组

• 稀疏数组

当一个数组中大部分元素为0，或者为同一个值的数组时，可以使用稀疏数组来保存该数组

稀疏数组处理的方法是：

1. 记录数组一共有几行几列，有多少不同的值
2. 把具有不同值得元素的行列及值记录在一个小规模的数组中，从而缩小程序的规模

举例

原始的二维数组：

0 0 0 22 0 0 15
0 11 0 0 0 17 0
0 0 0 -6 0 0 0
0 0 0 0 0 39 0
91 0 0 0 0 0 0
0 0 28 0 0 0 0 

转换后:

	行	列	值
[0]	6(这里记录了该数组有多少行)	7(这里记录了该数组有多少列)	8(这里记录的是有多少值)
[1]	0	3	22
[2]	0	6	15
[3]	1	1	11
[4]	1	5	17
[5]	2	3	-6
[6]	3	5	39
[7]	4	0	91
[8]	5	2	28

二维数组转稀疏数组的思路：

• 遍历原始的二维数组，得到有效数据的个数sum
• 根据sum就可以创建稀疏数组sparseArr int[sum + 1][3]
• 将二维数组的有效数据存入稀疏数组

稀疏数组转原始的二维数组的思路：

• 先读取稀疏数组的第一行，根据第一行的数据，创建原始的二维数组，比如上面的 chessArr = int[6][7]
• 在读取稀疏数组后几行的数据，并赋值给原始的二维数组即可

代码实现

/**
 * @description：稀疏数组和二维数组
 * @author ：virus
 * @date ：2020/4/18 18:09
 */

package structAndComputed;

public class SparseArr {
    public static void main(String[] args) {
        // 1. 创建一个原始的二维数组 11 * 11
        // 0：表示没有棋子 1表示黑子 2表示白子
        int chessArr1[][] = new int[11][11];
        chessArr1[1][2] = 1;
        chessArr1[2][3] = 2;
        // 输出原始的二维数组
        System.out.println("原始的二维数组：");
        for (int[] row : chessArr1) {
            for (int data : row) {
                System.out.printf("%d\t", data);
            }
            System.out.println();
        }

        // 将二维数组  转  稀疏数组
        // 1. 得到非0的数据的个数
        int sum = 0;
        for (int i = 0; i < 11; i++) {
            for (int j = 0; j < 11; j++) {
                if (chessArr1[i][j] != 0) {
                    sum++;
                }
            }
        }

        // 2. 创建一个对应的稀疏数组
        int sparseArr[][] = new int[sum + 1][3];
        // 给稀疏数组赋值
        sparseArr[0][0] = 11;
        sparseArr[0][1] = 11;
        sparseArr[0][2] = sum;

        // 遍历二维数组，将非0的值存放到稀疏数组中
        int count = 0; // 用于记录是第几个非0数据
        for (int i = 0; i < 11; i++) {
            for (int j = 0; j < 11; j++) {
                if (chessArr1[i][j] != 0) {
                    count++;
                    sparseArr[count][0] = i;
                    sparseArr[count][1] = j;
                    sparseArr[count][2] = chessArr1[i][j];
                }
            }
        }

        // 输出稀疏数组的形式
        System.out.println("稀疏数组的输出:");
        for (int i = 0; i < sparseArr.length; i++) {
            System.out.printf("%d\t%d\t%d\t\n", sparseArr[i][0], sparseArr[i][1], sparseArr[i][2]);
        }
        System.out.println();

        // 将稀疏数组 恢复成 二维数组
        // 1. 先读取稀疏数组的第一行，创建原始的二维数组
        int chessArr2[][] = new int[sparseArr[0][1]][sparseArr[0][1]];

        // 2. 读取稀疏数组的后几行的数据(从第2行开始)，并赋值给二维数组即可
        for (int i = 1; i < sparseArr.length; i++) {
            chessArr2[sparseArr[i][0]][sparseArr[i][1]] = sparseArr[i][2];
        }

        // 输出恢复后的二维数组
        System.out.println("恢复后的二维数组");

        for (int[] row : chessArr2) {
            for (int data : row) {
                System.out.printf("%d\t", data);
            }
            System.out.println();
        }
    }
}

二叉树的各种计算公式

1. n个节点的二叉树一共有((2n)!)/(n! * (n+1)!)种

2. n层二叉树的第n层最多为2^(n-1)个

3. 二叉树节点计算公式 N = n0+n1+n2，度为0的叶子节点比度为2的节点数多一个。N=1*n1+2*n2+1

4. 对任何一棵二叉树T，如果其终端节点数为n0，度为2的节点数为n2，则n0=n2+1

5. 具有n个节点的完全二叉树的深度为log2(n) + 1

排序算法

常见的冒泡排序

PHP版本

/**
 * 冒泡排序
 * @param array $arr
 * @return array
 */
function bubble($arr = [])
{
    $c = count($arr);
    for ($i = 0; $i < $c - 1; $i++) {
        for ($j = 0; $j < $c - 1 - $i; $j++) {
            if ($arr[$j] > $arr[$j + 1]) {
                $temp        = $arr[$j];
                $arr[$j]     = $arr[$j + 1];
                $arr[$j + 1] = $temp;
            }
        }
    }

    return $arr;
}

数组元素反转

思路：

就是对称位置的元素反转，表示对称位置需要两个索引

需要用第三个变量进行交换

min代表最左边的索引，max代表最右边的索引

当min < max时，代表反转完成，停止循环，这是条件

min从左往右 ，为++

max从右往左，为–

Java

public class Demo03ArrayReverse {

    public static void main(String[] args) {
        int[] array = { 10, 20, 30, 40, 50 };

        for (int i = 0; i < array.length; i++) {
            System.out.println(array[i]);
        }

        System.out.println("===============");

        for (int min = 0, max = array.length - 1;min < max; min++, max--) {
            int temp = array[min];
            array[min] = array[max];
            array[max] = temp;
        }

        for (int i = 0; i < array.length; i++) {
            System.out.println(array[i]);
        }
    }
}

比较数组元素的最大值

看过的一个很好的例子，比武招亲

意思就是说很多选手组成了一个数组 => int array = {X,X,X,X}

比如设定第一个为当前擂主 => int max = arrary[0]

然后依次上擂台比试，就是循环，依次留下最大的，最后留下的就是最大的

Java

public class Demo02ArrayMax {

    public static void main(String[] args) {

        // 5个选手
        int[] array = { 5, 15, 30, 20, 10000};

        int max = array[0];    // 比武擂台

        for (int i = 1; i < array.length; i++) {
            // 如果当前元素，比max更大，则换人
            if (array[i] > max) {
                max = array[i];
            }
        }

        // 谁最后最厉害，就能咋max当中留下最大值
        System.out.println("最大值:" + max);
    }
}

字符串匹配问题

问题描述：

有一个字符串str1 = “abceddededqw”和一个子串str2="dde"

现在要判断str1是否含有str2，如果存在，就返回第一次出现的位置，如果没有，就返回-1

要求用最快的速度来完成匹配

• 常见思维：暴力匹配
• KMP算法：《部分匹配表》

马踏棋盘

方法：图的深度优先遍历算法DFS + 贪心算法