2020年5月

二叉树 BinaryTree

二叉树BinaryTree是每个节点最多只有两个节点的树形结构,两个节点分别称为左子树右子树

为什么要使用树结构?
通过另外一篇文章Hash哈希表 散列表我们可以看到数组链表这两种数据结构的优点和缺点,为了提高读取操作的效率,除了使用Hash表外,我们还可以选择树结构,比如利用二叉树既可以保证读取检索速度同时也能保证插入、删除、修改的速度。

树的常用术语

BinaryTree

  • 节点
  • 根节点(root节点)
  • 父节点
  • 子节点
  • 叶子节点(没有子节点的节点)
  • 节点的权(节点的值)
  • 路径(从root节点找到该节点的路线)
  • 子树
  • 树的高度(树的最大层数)
  • 森林(多颗子树构成森林)

- 阅读剩余部分 -

哈希表

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

为什么要使用哈希表?首先我们来看下数组和链表的特点:

  • 数组:查询(寻址)易,操作(插入、删除)难。
  • 链表:查询(寻址)难,操作(插入、删除)易。

那我们能不能综合这两者的优点,创建一个查询(寻址)容易同时操作(插入、删除)也容易的数据结构?
答案就是哈希表,它能兼顾数组和链表的优点。

哈希表存储数据的结构图:

HashTable

该图左边是一个数组,每个数组存储内容指向一个链表。

散列函数

散列函数,能将一个元素根据该函数转换为哈希表的数组下表。

散列函数的常见实现方式:

  • 除法散列表,即将元素的关键码除以一个固定的数求摩。index = key % p
  • 平方散列法
  • 斐波那契散列法

- 阅读剩余部分 -

查找算法

在上边文章总结了常见的排序算法,本文接着上篇内容来介绍总结常见的查找算法。

  • 线性查找
  • 二分查找BinarySearch
  • 插值查找
  • 斐波那契(黄金分割)查询

线性查找

遍历待查找的数列,逐个比较,直到匹配项介绍。

public static int seqSearch(int[] array, int findVal) {
    int length = array.length;
    for(int i = 0; i < length; i ++) {
        if(findVal == array[i]) {
            return i;
        }
    }
    return -1;
}

二分查找Binary Search

二分查找也称折半查找,搜索的特点是:每经历一次比较,都是搜索范围缩小一半。
查找思路:

  • 从数列的中间开始查找
  • 如果中间元素正好匹配,则查找过程结束
  • 如果目标元素大于中间元素,则接着从大于中间元素那一半查找
  • 如果目标元素小于中间元素,则接着从小于中间元素那一半查找

中值公式:
BinarySearch

- 阅读剩余部分 -

排序算法

排序,给定一组数,按照指定顺序进行排列的过程。
排序算法有很多,一般可以分为二类:

  • 内部排序,即使用内存

    • 插入排序:直接插入排序、希尔排序
    • 选择排序:简单选择排序、堆排序
    • 交换排序:冒泡排序、快速排序
    • 归并排序
    • 基数排序
  • 外部排序,使用内存+外部存储

各个算法时间复杂度比较:
排序算法时间复杂度比较图

术语说明:

  • 稳定:如果a原来就在b前面,而a = b,完成排序后a仍在b的前面。
  • 不稳定:如果a原来就在b前面,而a = b,完成排序后a可能在b的后面。
  • 内排序(In-place):所有操作都在内存中完成。
  • 外排序(Out-place):由于数据太大,因而将数据放在磁盘中,排序操作通过外部存储和内存的数据传输才能进行。
  • 时间复杂度:算法执行所耗费的时间。
  • 空间复杂度:算法运行所需内存大小。

冒泡排序

冒泡排序思想:
通过对待排序序列从前向后,依次比较相邻的元素,逆序则交换,使得值较大的元素逐渐从前移到后部,类似冒泡从底部逐渐冒上来(排好序)。

冒泡排序代码如下:

/**
 * 冒泡排序
 * <pre>
 * 重复地遍历要排序的数列,一次比较两个元素,如果他们的顺序逆序(即排序标准)就把他们交换过来。
 * 走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。
 * </pre>
 * @author jyoryo
 */
public class BubbleSort {
    public static void main(String[] args) {
        int size = 100000;
        int array[] = new int[size];
        for(int i = 0; i < size; i++) {
            array[i] = (int)(Math.random() * size * 1000);
        }
        // System.out.println(Arrays.toString(array));
        long current = System.nanoTime();

        // bubbleSort(array);
        bubbleSort2(array);
        
        System.out.println(System.nanoTime() - current);
        // System.out.println(Arrays.toString(array));
    }
    
    // 冒泡排序
    public static void bubbleSort(int[] array) {
        int length = array.length;
        for(int i = 0; i < length; i ++) {
            for(int j = 0; j < (length - i - 1); j ++) {
                if(array[j] > array[j + 1]) {
                    int tmp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = tmp;
                }
            }
        }
    }
    
    // 冒泡排序(优化过)
    public static void bubbleSort2(int [] array) {
        int length = array.length;
        boolean flag = false;    //标志是否经过交换
        for(int i = 0;  i < length; i++) {
            for(int j = 0; j < (length - i - 1); j++) {
                if(array[j] > array[j + 1]) {
                    flag = true;
                    int tmp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = tmp;
                }
            }
            // 在一趟排序中未发生交换
            if(!flag) {
                break ;
            }
            // 重置标志
            flag = false;
        }
    }
}

- 阅读剩余部分 -

递归

递归,简单地说就是方法自己调用自己,每次调用时传入不同的变量

使用递归,可以有助于我们解决复杂问题,同时可以使代码保持简洁。

递归解决问题:

  • 复杂的数学问题。如:迷宫问题、八皇后问题、阶乘问题、汉诺塔等。
  • 很多算法也会用到递归。如:快速排序、归并排序、二分查找、分治算法等。

使用递归注意事项:

  1. 每次递归调用执行一个方法,就创建一个新的受保护的独立的栈空间;
  2. 方法局部变量都是独立的,不会互相影响;
  3. 如果方法中传参使用的是引用类型变量(如数组、链表、队列、栈、List),就会共享该引用类型的数据;
  4. 递归调用必须逐步逼近退出递归的条件,否则会无限递归,虚拟机会抛出StackOverflowError异常,退出程序;
  5. 当一个方法调用完成后或遇到return,就会返回发起调用它的方法,谁调用,就将返回结果返回给谁

递归的应用

迷宫问题

该问题是一个小球从迷宫的起点出发,怎么走才能到达终点。
实现代码:

/**
 * 小球走迷宫
 * <br />
 * 一个小球充下面的地图"S"点开始出发,走到"E"到达终点
 * S:起点
 * E:终点
 * <pre>
 * 1   1   1   1   1   1   1
 * 1   S   0   0   0   0   1
 * 1   0   0   0   0   0   1
 * 1   1   1   0   0   0   1
 * 1   0   0   0   0   0   1
 * 1   0   0   0   0   0   1
 * 1   0   0   0   0   E   1
 * 1   1   1   1   1   1   1
 * </pre>
 * @author jyoryo
 */
public class Maze {
    public static void main(String[] args) {
        // 迷宫地图
        int [][] map = new int[8][7];
        // 上下墙
        for(int i = 0; i < 7; i++)  {
            map[0][i] = 1;
            map[7][i] = 1;
        }
        // 左右墙
        for(int i = 0; i < 8; i++) {
            map[i][0] = 1;
            map[i][6] = 1;
        }
        // 障碍物
        map[3][1] = 1;
        map[3][2] = 1;
        
        print(map);
        
        run(map, 1, 1);
        
        System.out.println("~~~完成迷宫~~~");
        print(map);
    }
    
    /**
     * 走法
     * 地图上每个点值说明:0:表示该点没有走过; 1:表示墙; 2:表示通路可以走; 3:表示该点走过,但是走不通
     * @param map   地图
     * @param i   出发点行索引
     * @param j   出发点列索引
     * @return
     */
    public static boolean run(int[][] map, int i, int j) {
        // 到终点
        if(map[6][5] == 2) {
            print(map);
            return true;
        }
        // 该点没有走过,开始走
        if(map[i][j] == 0) {
            /*
             * 走的策略:下→右→上→左
             */
            map[i][j] = 2;
            // 下走
            if(run(map, i + 1, j)) {
                return true;
            }
            // 右走
            else if(run(map, i, j + 1)) {
                return true;
            }
            // 上走
            else if(run(map, i - 1, j)) {
                return true;
            }
            // 左走
            else if(run(map, i, j - 1)){
                return true;
            }
            // 走不通,回溯更改
            else {
                map[i][j] = 3;
                return false;
            }
        }
        return false;
    }

    // 打印地图
    private static void print(int [][] array) {
        for(int i = 0; i < array.length; i++) {
            for(int j = 0; j < array[i].length; j++) {
                System.out.printf("%d\t", array[i][j]);
            }
            System.out.println();
        }
    }
}

汉诺塔问题

汉诺塔算法的思路:

  • 把第n-1个盘子由A移到B
  • 把第n个盘子由A移到C
  • 把第n-1个盘子由B移到C

实现代码如下:

public class TowerOfHanoi {
    private static int counter = 0;    // 计数器

    public static void main(String[] args) {
        char a = 'A', b = 'B', c = 'C';
        System.out.println("请输入圆盘数:");
        Scanner scanner = new Scanner(System.in);
        int number = scanner.nextInt();
        
        hanoi(number, a, b, c);
        
        scanner.close();
    }
    
    public static void hanoi(int n, char a, char b, char c) {
        if(1 == n) {
            move(1, a, c);
            return ;
        }
        // 递归,将A上的编号{n - 1}盘移动到B, C为辅助塔
        hanoi(n - 1, a, c, b);
        // 将编号为{n}盘移动到C
        move(n, a, c);
        // 递归,将B上的编号{n - 1}盘移动到C, A为辅助塔
        hanoi(n - 1, b, a, c);
    }
    
    public static void move(int diskNo, char from, char to) {
        System.out.printf("第%d次移动,将%d号盘从%s→%s。\n", ++counter, diskNo, from, to);
    }
}

八皇后问题

public class EightQueensPuzzle {
    // 使用一维数组表示,数组索引表示所在行;对应值为该行皇后排放的列
    int max = 8;
    int [] array = new int[max];
    int counter = 0;
    
    public static void main(String[] args) {
        EightQueensPuzzle queensPuzzle = new EightQueensPuzzle();
        queensPuzzle.queue(0);
        System.out.printf("一共由%d种摆法!", queensPuzzle.counter);
    }
    
    // 排放第n个皇后
    private void queue(int n) {
        // 8皇后都已摆放好
        if(n == max) {
            print();
            return ;
        }
        for(int i = 0; i < max; i++) {
            array[n] = i;
            // 不冲突
            if(valid(n)) {
                queue(n + 1);
            }
        }
    }
    
    // 当放置第n个皇后,检测是否与前已排的有冲突(同一行、同一列、同一斜线)
    private  boolean valid(int n) {
        for(int i = 0; i < n; i++) {
            // array[i] == array[n] 表示在同一列
            // Math.abs(n - 1) == Math.abs(array[n] - array[i]) 表示在同一斜线上
            if(array[i] == array[n] || (Math.abs(n - i) == Math.abs(array[n] - array[i]))) {
                return false;
            }
        }
        return true;
    }
    
    // 打印
    private void print() {
        counter ++;
        for(int i = 0; i < array.length; i++) {
            System.out.printf("%d\t", array[i]);
        }
        System.out.println();
    }
}

参考文章

汉诺塔的图解递归算法

数据结构

数据结构是算法的基础,一般数据结构可以分为:线性结构非线性结构
本文章主要是对于常用的线性数据结构进行总结。
常见的线性数据结构有:

  • 数组 Array
  • 链表 LinkedList
  • 队列 Queue
  • Stack

稀疏数组SparseArray

稀疏数组:如果数组中大部分的元素值都未被使用(或都为0),在数组中仅有少部分的空间使用,因此造成内存空间的浪费,为了解决这问题,并且不影响数组中原有的元素值,采用的一种压缩的方式来表示原数组的内容。

稀疏数组处理方法:

  1. 统计出原数组一共有多少行多少列多少个值(原数组使用的值)
  2. 把具有值的元素所在,记录在一个小规模数组中。

二维数组转稀疏数组

  • 二维数组转稀疏数组

    1. 遍历二维数组,统计有效数据的个数count
    2. 根据有效个数count创建稀疏数组sparseArray[count + 1][3]
    3. 将二维数组有效数据存入稀疏数组。
  • 稀疏数组还原原始二维数组

    1. 读取稀疏数组第一行,根据第一行数据创建原始的二维数组。
    2. 遍历稀疏数组余下行,将读取的数据填充原始的二维数组。

- 阅读剩余部分 -