二叉树 BinaryTree

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

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

树的常用术语

BinaryTree

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

二叉树的特点

  • 每个节点最多只能有2个子节点,子节点分为左节点右节点
  • 满二叉树:如果二叉树的所有叶子节点都在最后一层,并且节点总数=2^n-1(n为层数)。
  • 完全二叉树:如果二叉树的所有叶子节点都在最后一层或倒数第二层,最后一层的叶子节点在左边连续,倒数第二层的叶子节点在右边连续。

满二叉树
FullBinaryTree

完全二叉树
CompleteBinaryTree

二叉树的遍历

二叉树可以使用前序中序后序进行遍历。(看父节点输出顺序来确定是前序中序后序。)

前序遍历
先输出父节点,再遍历左子树,最后遍历右子树。

  1. 输出当前节点(初始开始时是root节点
  2. 如果左子树不为空,递归进行前序遍历
  3. 如果右子树不为空,递归进行前序遍历

中序遍历
先遍历左子树,再输出父节点,最后遍历右子树。

  1. 如果左子树不为空,递归进行中序遍历
  2. 输出当前节点
  3. 如果右子树不为空,递归进行中序遍历

后序遍历
先遍历左子树,在遍历右子树,最后输出父节点。

  1. 如果左子树不为空,递归进行后序遍历
  2. 如果右子树不为空,递归进行后序遍历
  3. 输出当前节点

二叉树的查找

二叉树的有三种(前序中序后序)遍历方案,对应查找具体节点也对应有前序查找中序查找后续查找
BinaryTreeDemo.png

下面是二叉树遍历、查找代码:

/**
 * 二叉树节点
 * @author jyoryo
 */
public class BinaryTreeNode {
    private int id;
    private String name;
    private BinaryTreeNode left;
    private BinaryTreeNode right;
    
    public BinaryTreeNode(int id, String name) {
        super();
        this.id = id;
        this.name = name;
    }

    @Override
    public String toString() {
        return "BinaryTreeNode [id=" + id + ", name=" + name + "]";
    }
    /**
     * 前序遍历
     * <pre>
     * 1. 输出当前节点(初始开始时是root节点)
     * 2. 如果左子树不为空,递归进行前序遍历
      * 3. 如果右子树不为空,递归进行前序遍历
     * </pre>
     */
    public void preOrder() {
        // 1、输出当前节点
        System.out.println(this);
        // 2、左子树不为空,递归进行前序遍历
        if(null != left) {
            left.preOrder();
        }
        // 3、右子树不为空,递归进行前序遍历
        if(null != right) {
            right.preOrder();
        }
    }
    /**
     * 中序遍历
     * <pre>
     * 1. 如果左子树不为空,递归进行中序遍历
      * 2. 输出当前节点
      * 3. 如果右子树不为空,递归进行中序遍历
     * </pre>
     */
    public void infixOrder() {
        // 1. 如果左子树不为空,递归进行中序遍历
        if(null != left) {
            left.infixOrder();
        }
        // 2. 输出当前节点
        System.out.println(this);
        // 3. 如果右子树不为空,递归进行中序遍历
        if(null != right) {
            right.infixOrder();
        }
    }
    /**
     * 后序遍历
     * <pre>
     * 1. 如果左子树不为空,递归进行后序遍历
      * 2. 如果右子树不为空,递归进行后序遍历
      * 3. 输出当前节点
     * </pre>
     */
    public void postOrder() {
        // 1. 如果左子树不为空,递归进行后序遍历
        if(null != left) {
            left.postOrder();
        }
        // 2. 如果右子树不为空,递归进行后序遍历
        if(null != right) {
            right.postOrder();
        }
        // 3. 输出当前节点
        System.out.println(this);
    }
    
    /**
     * 前序查找
     * @param id
     * @return
     */
    public BinaryTreeNode preOrderSearch(int id) {
        BinaryTreeNode resultNode = null;
        // 当前节点
        if(id == this.getId()) {
            return this;
        }
        // 遍历左子树进行查找
        if(null != left) {
            resultNode = left.preOrderSearch(id);
        }
        if(null != resultNode) {
            return resultNode;
        }
        // 遍历右子树进行查找
        if(null != right) {
            resultNode = right.preOrderSearch(id);
        }
        return resultNode;
    }
    
    /**
     * 中序查找
     * @param id
     * @return
     */
    public BinaryTreeNode infixOrderSearch(int id) {
        BinaryTreeNode resultNode = null;
        // 遍历左子树进行查找
        if(null != left) {
            resultNode = left.infixOrderSearch(id);
        }
        if(null != resultNode) {
            return resultNode;
        }
        // 当前节点
        if(id == this.getId()) {
            return this;
        }
        // 遍历右子树
        if(null != right) {
            resultNode = right.infixOrderSearch(id);
        }
        return resultNode;
    }
    
    /**
     * 后续查找
     * @param id
     * @return
     */
    public BinaryTreeNode postOrderSearch(int id) {
        BinaryTreeNode resultNode = null;
        // 遍历左子树
        if(null != left) {
            resultNode = left.postOrderSearch(id);
        }
        if(null != resultNode) {
            return resultNode;
        }
        // 遍历右子树
        if(null != right) {
            resultNode = right.postOrderSearch(id);
        }
        if(null != resultNode) {
            return resultNode;
        }
        // 当前节点
        if(id == this.getId()) {
            return this;
        }
        return resultNode;
    }
    
    // getter setter method
}

/**
 * 二叉树
 * @author jyoryo
 */
public class BinaryTree {
    private BinaryTreeNode root;

    public BinaryTree(BinaryTreeNode root) {
        super();
        this.root = root;
    }
    public void setRoot(BinaryTreeNode root) {
        this.root = root;
    }
    // 前序遍历
    public void preOrder() {
        if(null == root) {
            throw new RuntimeException("空二叉树,无法执行该操作!");
        }
        root.preOrder();
    }
    // 中序遍历
    public void infixOrder() {
        if(null == root) {
            throw new RuntimeException("空二叉树,无法执行该操作!");
        }
        root.infixOrder();
    }
    // 后序遍历
    public void postOrder() {
        if(null == root) {
            throw new RuntimeException("空二叉树,无法执行该操作!");
        }
        root.postOrder();
    }
    
    // 前序查找
    public BinaryTreeNode preOrderSearch(int id) {
        return root.preOrderSearch(id);
    }
    
    // 中序查找
    public BinaryTreeNode infixOrderSearch(int id) {
        return root.infixOrderSearch(id);
    }
    
    // 后序查找
    public BinaryTreeNode postOrderSearch(int id) {
        return root.postOrderSearch(id);
    }
}

public class BinaryTreeDemo {
    public static void main(String[] args) {
        BinaryTreeNode node0 = new BinaryTreeNode(0, "零"),
            node1 = new BinaryTreeNode(1, "壹"),
            node2 = new BinaryTreeNode(2, "贰"),
            node3 = new BinaryTreeNode(3, "叁"),
            node4 = new BinaryTreeNode(4, "肆"),
            node5 = new BinaryTreeNode(5, "伍"),
            node6 = new BinaryTreeNode(6, "陆"),
            node7 = new BinaryTreeNode(7, "柒"),
            node8 = new BinaryTreeNode(8, "捌"),
            node9 = new BinaryTreeNode(9, "玖");
        node0.setLeft(node1);    node0.setRight(node2);
        node1.setLeft(node3);    node1.setRight(node4);
        node2.setLeft(node5);    node2.setRight(node6);
        node3.setLeft(node7);    node3.setRight(node8);
        node4.setLeft(node9);
        BinaryTree binaryTree = new BinaryTree(node0);
        // 前序遍历
        System.out.println("前序遍历");
        binaryTree.preOrder();
        // 中序遍历
        System.out.println("中序遍历");
        binaryTree.infixOrder();
        // 后序遍历
        System.out.println("后续遍历");
        binaryTree.postOrder();
        
        int findVal1 = 5, findVal2 = 15;
        // 前序查找
        System.out.println("前序查找");
        System.out.printf("查找%d,结果为:%s\n", findVal1, binaryTree.preOrderSearch(findVal1));
        System.out.printf("查找%d,结果为:%s\n\n", findVal2, binaryTree.preOrderSearch(findVal2));
        // 中序查找
        System.out.println("中序查找");
        System.out.printf("查找%d,结果为:%s\n", findVal1, binaryTree.infixOrderSearch(findVal1));
        System.out.printf("查找%d,结果为:%s\n\n", findVal2, binaryTree.infixOrderSearch(findVal2));
        // 后序查找
        System.out.println("后序查找");
        System.out.printf("查找%d,结果为:%s\n", findVal1, binaryTree.postOrderSearch(findVal1));
        System.out.printf("查找%d,结果为:%s\n\n", findVal2, binaryTree.postOrderSearch(findVal2));
    }
}

顺序存储二叉树

基本说明:从数据存储来看,数组存储方式和树的存储方式可以相互转换,及数组可以转换成树,树也可以转换成数组

顺序存储二叉树的特点

  • 顺序存储二叉树通常只考虑完全二叉树
  • n:表示二叉树中的第几个元素,按0开始编号
  • n个元素的左子节点为2n + 1
  • n个元素的右子节点为2n + 2
  • n个元素的父节点为(n - 1) / 2

比如上面的树以数组方式存储为:array[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
顺序存储二叉树的遍历(前序遍历中序遍历后序遍历):

public class ArrayBinaryTree {
    private int [] array;    // 顺序存储完全二叉树节点值的数组

    public ArrayBinaryTree(int[] array) {
        super();
        this.array = array;
    }
    
    // 前序遍历
    public void preOrder(int index) {
        if(null == array || 0 >= array.length) {
            throw new RuntimeException("数组为空,不允许执行该操作!");
        }
        // 1、输出当前元素
        System.out.println(array[index]);
        // 2、向左递归
        if((2 * index + 1) < array.length) {
            preOrder(2 * index + 1);
        }
        // 3、向右递归
        if((2 * index + 2) < array.length) {
            preOrder(2 * index + 2);
        }
    }
    
    // 中序遍历
    public void infixOrder(int index) {
        if(null == array || 0 >= array.length) {
            throw new RuntimeException("数组为空,不允许执行该操作!");
        }
        // 1、向左递归
        if((2 * index + 1) < array.length) {
            infixOrder(2 * index + 1);
        }
        // 2、输出当前元素
        System.out.println(array[index]);
        // 3、向右递归
        if((2 * index + 2) < array.length) {
            infixOrder(2 * index + 2);
        }
    }
    
    // 后序遍历
    public void postOrder(int index) {
        if(null == array || 0 >= array.length) {
            throw new RuntimeException("数组为空,不允许执行该操作!");
        }
        // 1、向左递归
        if((2 * index + 1) < array.length) {
            postOrder(2 * index + 1);
        }
        // 2、向右递归
        if((2 * index + 2) < array.length) {
            postOrder(2 * index + 2);
        }
        // 3、输入当前元素
        System.out.println(array[index]);
    }
}

public class ArrayBinaryTreeDemo {
    public static void main(String[] args) {
        int [] array = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
        ArrayBinaryTree arrayBinaryTree = new ArrayBinaryTree(array);
        // 前序遍历
        arrayBinaryTree.preOrder(0);
        // 中序遍历
        arrayBinaryTree.infixOrder(0);
        // 后序遍历
        arrayBinaryTree.postOrder(0);
    }
}

哈希表

哈希表(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. 遍历稀疏数组余下行,将读取的数据填充原始的二维数组。

- 阅读剩余部分 -

进程(process)和线程(thread)

实现并发最直接的方式是在操作系统级别使用进程。进程是运行在它自己的地址空间内的自包容的程序。
一个线程就是在进程中的一个单一的顺序控制流,单个进程可以拥有多个并发执行任务。

Runnable和Thread

通过Runnable定义任务

线程可以驱动任务,Java中是由Runnable接口提供,需要实现Runnable接口的run()方法。任务run()方法通常总会有某种形式的循环,使得任务一直运行下去直到不再需要。通常run()被写成无限循环的形式。
例如:

public class LiftOff implements Runnable {
    protected int countDown = 10;    //倒计数
    private static int taskCount;
    private final int id = taskCount ++;
    
    public LiftOff() {
        super();
    }
    public LiftOff(int countDown) {
        super();
        this.countDown = countDown;
    }
    
    public String status() {
        return String.format("#%d(%s).", id, (countDown > 0) ? countDown : "LiftOff!");
    }

    @Override
    public void run() {
        while(countDown-- > 0) {
            System.out.print(status());
            Thread.yield();
        }
    }
}

静态方法Thread.yield()

Thread.yield()线程调度器的一种建议,暗示:我已经执行完生命周期中最重要的部分了,现在正是将CPU资源切换给其他任务执行一段时间的时机。

Thread类

Runnable对象转变为工作任务的传统方式是将它提交给一个Thread的构造器。
使用方法如下:

public class BasicThreads {
    public static void main(String[] args) {
        Thread t = new Thread(new LiftOff());
        t.start();
        System.out.println("Waiting for LiftOff");
    }
}

Executor和线程池

Executor是Java SE5引入的,用来管理Thread对象,从而简化并发编程。Executor是启动任务的优选方法

ExecutorService

ExecutorService是具有生命周期的Executor,会管理如何构建恰当的上下文来执行Runnable对象。非常常见的情况是:单个Executor用来创建和管理系统中所有的任务。
在任何线程池中,在现有的线程的可能情况下,都会被自动复用

CachedThreadPool

CachedThreadPool为每个任务都创建一个线程,使用方法:

public class CachedThreadPool {
    public static void main(String[] args) {
        ExecutorService exec = Executors.newCachedThreadPool();
        for(int i = 0; i < 5; i ++) {
            exec.execute(new LiftOff());
        }
        exec.shutdown();
    }
}

- 阅读剩余部分 -

Docker介绍

Docker是一个应用程序,它简化了在容器中管理应用程序进程的过程。容器允许您在资源隔离的进程中运行应用程序。它们与虚拟机类似,但是容器更可移植、更友好、更依赖于主机操作系统。

Docker安装的要求

系统要求

安装Docker支持如下系统:

  • Debian/Ubuntu Buster 10(stable)
  • Debian/Ubuntu Stretch 9 / Raspbian Stretch

卸载旧的版本(可选)

如果已安装有旧的版本,需要先卸载。卸载命令为:

sudo apt-get remove docker docker-engine docker.io containerd runc

Docker安装

Debian官方中的安装包中的Docker版本不一定是最新的,为了确保我们从Docker官方安装最新的Docker,我们需要添加一个新的包源,从Docker添加GPG密钥以确保下载是有效的,然后安装包。
注:如果是通过root登录的,下面的命令都可以省掉sudo

1. 更新Debian源和安装依赖

sudo apt-get update
sudo apt-get install apt-transport-https ca-certificates curl gnupg-agent software-properties-common

2. 添加GPG Key

curl -fsSL https://download.docker.com/linux/debian/gpg | sudo apt-key add -

3. 将Docker库添加至APT源,注意系统的平台,根据不同平台执行不同的命令

## x86_64 / amd64 平台
sudo add-apt-repository "deb [arch=amd64] https://download.docker.com/linux/debian $(lsb_release -cs) stable"

# armhf 平台
sudo add-apt-repository "deb [arch=armhf] https://download.docker.com/linux/debian $(lsb_release -cs) stable"

# arm64 平台
sudo add-apt-repository "deb [arch=arm64] https://download.docker.com/linux/debian $(lsb_release -cs) stable"

- 阅读剩余部分 -

前言:

备份很重要、备份很重要、备份很重要。(PS:对应备份我也不免入俗了,重要的事情说三遍!!!)
但是我们不用每次都自己操作备份或导出数据文件,可以Shell脚本帮我们自动完成这项重复劳动。

备份数据库前的思考:

  • 确定备份文件存放位置、备份文件名策略、是否自动删除超过指定天数的历史文件。
  • 需要备份哪些数据库还是所有的数据库。
  • 导出备份文件后,是否需要对备份的数据文件进行压缩减小体积。

想清楚上面的几个问题后,就可以着手操作了。

准备条件

使用[mysqldump]配置文件方法

  1. 创建备份专用账号

    CREATE USER 'backupuser'@'localhost' IDENTIFIED BY 'p455w0rd';
    GRANT SELECT, SHOW VIEW, LOCK TABLES, RELOAD, REPLICATION CLIENT ON *.* TO 'backupuser'@'localhost';
    FLUSH PRIVILEGES;
  2. 将1中添加的账号添加至配置文件中

    [mysqldump]
    user=backupuser
    password=p455w0rd

备份脚本

#!/bin/bash

# 直接指定备份数据库使用的用户名、密码。(不建议)
# user="db_username"
# password="db_password"

# 指定备份具体的数据库,多个数据库,中间用空格进分割。如果全部备份可以使用参数 --all-databases
# dbname="db1 db2 db3"

# 指定备份存放目录、备份文件名、备份文件名日期信息
backup_path="/data/bak/db"
backupname="db"
date=$(date "+%Y%m%d")

echo "Backing up mysql databases..."

# 检测是否已存在备份文件,如有,进行删除操作
if [ -f "$backup_path/$backupname-$date.sql.bz2" ]; then
    rm -fv $backup_path/$backupname-$date.sql*
fi

echo "Dumping databases..."

## 直接指定username, password(不推荐)
# mysqldump --user=$user --password=$password --databases $dbname > $backup_path/$backupname-$date.sql

## 将username, password放在配置文件中[mysqldump]下(推荐)
# mysqldump --databases $dbname > $backup_path/$backupname-$date.sql
## 备份所有数据库
mysqldump --all-databases > $backup_path/$backupname-$date.sql

echo "Compressing databases..."
bzip2 $backup_path/$backupname-$date.sql

chmod 600 $backup_path/$backupname-$date.sql.bz2

# Delete files older than 30 days(移除超过30天的历史备份文件)
echo "Checking for old files..."
find $backup_path/* -mtime +30 -exec rm {} \;
echo "Done."

使用Crontab定时执行

进入Crontab编辑模式:

crontab -e

添加定时任务:

# m h  dom mon dow   command
30  1  *   *   *     . /etc/profile; /data/soft/script/mysql_backup.sh > /data/soft/script/mysql_backup.log 2>&1 &

说明:

  • 每天凌晨1:30执行。
  • 由于后台MySQL是使用源码形式安装的,所有MySQL的命令不能直接运行,我在环境变量文件/etc/profile最后添加了export PATH=$PATH:/data/soft/mysql/bin
  • . /etc/profile;,使环境变量生效。
  • 2>&1:如果执行过程中有异常信息,将stderr也重定向标准输出流stdout

Android中常用的应用都会大量使用网络,比如QQ、微信、访问网页等等。通过使用网络,可以展示网页,发起Http请求获取数据或提交数据。

WebView控件

有时我们可能需要让我们自己的应用展示网页,我们可以使用Android内置的控件WebView

public class MainActivity extends AppCompatActivity {

    @Override
    protected void onCreate(Bundle savedInstanceState) {
        super.onCreate(savedInstanceState);
        setContentView(R.layout.activity_main);

        WebView webView = (WebView)findViewById(R.id.web_view);
        webView.getSettings().setJavaScriptEnabled(true);
        webView.setWebViewClient(new WebViewClient());
        webView.loadUrl("http://www.baidu.com");
    }
}

布局文件:

<?xml version="1.0" encoding="utf-8"?>
<LinearLayout xmlns:android="http://schemas.android.com/apk/res/android"
    android:orientation="vertical"
    android:layout_width="match_parent"
    android:layout_height="match_parent">

    <WebView
        android:id="@+id/web_view"
        android:layout_width="match_parent"
        android:layout_height="match_parent" />
</LinearLayout>

由于使用了网络功能,需要声明网络权限。在AndroidManifest.xml添加android.permission.INTERNET:

<?xml version="1.0" encoding="utf-8"?>
<manifest xmlns:android="http://schemas.android.com/apk/res/android"
    package="com.jyoryo.app.android.study">

    <uses-permission android:name="android.permission.INTERNET" />

    <application
        android:allowBackup="true"
        android:icon="@mipmap/ic_launcher"
        android:label="@string/app_name"
        android:roundIcon="@mipmap/ic_launcher_round"
        android:supportsRtl="true"
        android:theme="@style/AppTheme">
        <activity android:name=".MainActivity">
            <intent-filter>
                <action android:name="android.intent.action.MAIN" />
                <category android:name="android.intent.category.LAUNCHER" />
            </intent-filter>
        </activity>
    </application>

</manifest>

- 阅读剩余部分 -