Java中的数据结构与算法_一个数组　double a[]={63,78,25,85,46,70,36,92,74,68,39}

数据结构

数据结构是一门研究组织数据方式的学科，有了编程语言也就有了数据结构，学好数据结构可以编写出更有效率的代码。数据结构是算法的基础，想要学好算法，就必须把数据结构学到位。

数据结构包括：线性结构、非线性结构。

线性结构作为最常用的数据结构，其特点是数据元素之间存在一对一的线性存储关系。线性结构有两种不同的存储结构，即顺序存储和链式存储。顺序存储的线性表被称为顺序表，顺序表中存储元素的地址是连续的；链式存储的线性表被称为链表，链表中存储元素的地址不一定是连续的，元素结点中存放数据元素以及相邻元素地址信息。

常见的线性结构有：数组、链表、队列、栈；常见非线性结构有：多维数组、广义表、树结构、图结构。

稀疏数组

使用稀疏数组可以用来压缩数据。稀疏数组的第一行依次记录原数组一共有几行几列，有多少个不为零的值，之后的每行记录原数组中不为零的值所在的行数、列数以及数组中元素该值。如图所示：

二维数组转稀疏数组

class TwoDimensionArrayDemo {
  // 将二维数组转换为稀疏数组
  public static int[][] twoDimensionArrayToSparseArray(int[][] array) {
    // 记录棋盘中有效值的数量
    int sum = 0;
    int row = array.length;
    int column = 0;
    for (int[] ints : array) {
      column = ints.length;
      for (int item : ints) {
        if (item != 0) {
          sum++;
        }
      }
    }

    // 创建稀疏数组
    int[][] sparseArray = new int[sum + 1][3];
    sparseArray[0][0] = row;
    sparseArray[0][1] = column;
    sparseArray[0][2] = sum;

    // 给稀疏数组赋值
    int count = 0;
    for (int i = 0; i < array.length; i++) {
      for (int j = 0; j < array[i].length; j++) {
        if (array[i][j] != 0) {
          count++;
          sparseArray[count][0] = i;
          sparseArray[count][1] = j;
          sparseArray[count][2] = array[i][j];
        }
      }
    }

    System.out.println("稀疏数组====》");
    for (int i = 0; i < sparseArray.length; i++) {
      System.out.printf("%d\t%d\t%d\t\n", sparseArray[i][0], sparseArray[i][1], sparseArray[i][2]);
    }
    return sparseArray;
  }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

稀疏数组转二维数组

class TwoDimensionArrayDemo {
  // 稀疏数组转二维数组
  public static int[][] sparseArrayToTwoDimensionArray(int[][] sparseArray) {
    int[][] toTwoDimensionArray = new int[sparseArray[0][0]][sparseArray[0][1]];
    // 给二维数组赋值
    for (int i = 1; i < sparseArray.length; i++) {
      toTwoDimensionArray[sparseArray[i][0]][sparseArray[i][1]] = sparseArray[i][2];
    }

    System.out.println("二维数组====》");
    for (int[] row : toTwoDimensionArray) {
      for (int data : row) {
        System.out.printf("%d\t", data);
      }
      System.out.println();
    }
    return toTwoDimensionArray;
  }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

队列

队列是一个有序列表，可以使用数组或链表来实现。队列遵循先入先出的原则。即，先存入队列的数据，要先取出。后存入的要后取出。

使用数组模拟队列示意图：

数组模拟单向队列

    public class ArrayQueue{

        // 队列容量
        private int capacity;

        // 保存队列中的数据
        private int[] arr;

        // 头部指针
        private int front;

        // 尾部指针
        private int rear;

        public ArrayQueue(int capacity) {
            this.capacity = capacity;
            arr = new int[capacity];
            front = -1;
            rear = -1;
        }

        public boolean isEmpty() {
            return front == rear;
        }

        public boolean isFull() {
            return capacity - 1 == rear;
        }

        public void add(int data) {
            if (isFull()) {
                System.out.println("队列已经满了，不能在继续添加");
                return;
            }
            arr[++rear] = data;
        }

        public int get() {
            if (isEmpty()) {
                System.out.println("队列为空，不能获取元素");
                return -1;
            }
            return arr[++front];
        }

        // 显示队列的所有数据
        public void show() {
            if (isEmpty()) {
                System.out.println("队列空的，没有数据~~");
                return;
            }
            System.out.println("开始遍历队列：");
            for (int i = front + 1; i <= rear; i++) {
                System.out.printf("arr[%d]=%d\n", i, arr[i]);
            }
        }


        // 显示队列的头数据， 注意不是取出数据
        public int peek() {
            if (isEmpty()) {
                throw new RuntimeException("队列空的，没有数据~~");
            }
            return arr[front + 1];
        }

    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67

数组模拟环形队列

    public  class CircleArrayQueue{

        // 队列容量
        private int capacity;

        // 保存队列中的数据
        private int[] arr;

        // 头部指针
        private int front;

        // 尾部指针
        private int rear;

        public CircleArrayQueue(int capacity) {
            this.capacity = capacity;
            arr = new int[capacity];
        }

        public boolean isEmpty() {
            return front == rear;
        }

        public boolean isFull() {
            // 此处+1 是因为存储元素从0算起
            return (rear + 1) % capacity  == front;
        }

        public void add(int data) {
            if (isFull()) {
                System.out.println("队列已经满了，不能在继续添加");
                return;
            }
            arr[rear] = data;
            rear = (rear + 1) % capacity;
        }

        public int get() {
            if (isEmpty()) {
                System.out.println("队列为空，不能获取元素");
                return -1;
            }
            int value = arr[front];
            front = (front + 1) % capacity;
            return value;
        }

        // 显示队列的所有数据
        public void show() {
            if (isEmpty()) {
                System.out.println("队列空的，没有数据~~");
                return;
            }
            System.out.println("开始遍历队列：");
            for (int i = front % capacity; i < front + ((rear + capacity - front) % capacity); i++) {
                System.out.printf("arr[%d]=%d\n", i, arr[i]);
            }
        }

        // 显示队列的头数据， 注意不是取出数据
        public int peek() {
            if (isEmpty()) {
                throw new RuntimeException("队列空的，没有数据~~");
            }
            return arr[front];
        }

    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68

链表

链表属于线性结构，存储空间不连续。

链表特点：

• 链表是以节点的方式来存储，是链式存储；data 域存放数据，next 域指向下一个节点；
• 链表分带头节点的链表和没有头节点的链表，根据实际的需求来确定；

单向链表

操作单向链表：对于插入、删除操作，只能定位至待操作节点的前一个节点，如果定位至当前节点，那么其上一个节点的信息便会丢失。

单向链表，链表的增、删、查、改

class SingleLinkedList{

    // 头结点
    private Node headNode = new Node(0,"");

    // 添加方法
    public  void add(Node node){
        Node tmpNode = headNode;

        while (tmpNode.next != null){
            // 指向下一个结点
            tmpNode = tmpNode.next;
        }
        // 退出循环意味着tmpNode.next == null 即找到最后一个结点了
        tmpNode.next = node;
    }

    // 顺序添加
    public void addByOrder(Node node){
        boolean flag = false;
        Node tmp = headNode;
        while (true){
            if (tmp.next == null) {
                break;
            }

            // 将新插入的结点num跟链表中已经存在的num进行比较，如果 < 链表中的结点 则说明找到了该位置
            if (node.num < tmp.next.num){
                break;
            }
            // 如果num相同则不能添加
            if (node.num == tmp.next.num){
                flag = true;
                break;
            }
            tmp = tmp.next;
        }

        if (!flag){
            node.next = tmp.next;
            tmp.next = node;
            return;
        }
        System.out.printf("需要添加的结点编号：%d已经存在了",node.num);
    }

    // 遍历链表
    public void list() {
        // 遍历除了头结点外的所有结点
        Node tmpNode = headNode.next;
        if (tmpNode == null){
            System.out.println("链表为空！");
            return;
        }

        while (tmpNode != null){
            System.out.println(tmpNode);
            // 指向下一个结点
            tmpNode = tmpNode.next;
        }
    }


}


class Node {

    int num;
    String name;
    Node next;

    public Node(int num,String name){
        this.num = num;
        this.name = name;
    }

    @Override
    public String toString() {
        return "Node{" +
                "num=" + num +
                ", name='" + name + '\'' +
                '}';
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85

反转单向链表

class LinkedListDemo{
    // 反转链表
    public void reserve(Node head) {
      if (head.next == null || head.next.next == null) {
        return;
      }

      Node reserve = new Node(0, "");
      Node cur = head.next;
      Node next = null;
      // 遍历链表
      // 遍历原来的链表，每遍历一个节点，就将其取出，并放在新的链表reverseHead 的最前端
      while (cur != null) {

        // 保存当前结点的下一个结点
        next = cur.next;

        // 将cur的下一个节点指向新的链表的最前端（覆盖掉）保证将最新的结点放到reseve的最前面
        cur.next = reserve.next;

        // 将cur 连接到新的链表上
        reserve.next = cur;

        // 将之前保存好的结点赋值给当前结点
        cur = next;
      }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

利用栈逆序打印单向链表

class LinkedListDemo {
  public void reservePrint(Node head) {
    if (head.next == null || head.next.next == null) {
      return;
    }

    Stack<Node> nodes = new Stack<>();
    Node tmp = head.next;
    while (tmp != null) {
      nodes.push(tmp);
      tmp = tmp.next;
    }

    // 从stack中取出结点
    while (nodes.size() > 0) {
      System.out.println(nodes.pop());
    }
  }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

双向链表

对比单向链表：

• 单向链表，查找的方向只能是一个方向，而双向链表可以向前或者向后查找；
• 单向链表不能自我删除，需要靠辅助节点，而双向链表，则可以自我删除；

双向链表，增、删、改、查

class DoubleLinkedList{

    // 头结点
    private Node headNode = new Node(0,"");


    public Node getHeadNode() {
        return headNode;
    }


    // 添加方法
    public  void add(Node node){
        Node tmpNode = headNode;

        while (tmpNode.next != null){
            // 指向下一个结点
            tmpNode = tmpNode.next;
        }
        // 退出循环意味着tmpNode.next == null 即找到最后一个结点了
        tmpNode.next = node;
        node.prev = tmpNode;
    }


    // 双向链表修改
    public void update(Node node){
        if (headNode == null) {
            return;
        }

        Node tmp = headNode.next;
        while (true){
            if (tmp == null){
                break;
            }
            if (node.num == tmp.num){
                tmp.name = node.name;
                break;
            }
            tmp = tmp.next;
        }
    }

    // 双向链表删除
    public void remove(int num){
        if (headNode.next == null){
            System.out.println("链表为空，无法删除！");
            return;
        }
        Node tmp = headNode.next;
        while (tmp != null){
            if (num == tmp.num){
                tmp.prev.next = tmp.next;

                // 最后一个结点的next 为null null.pre会出现空指针异常
                if(tmp.next != null) {
                    tmp.next.prev = tmp.prev;
                }
                break;
            }
            tmp = tmp.next;
        }
    }

    // 遍历链表
    public void list() {
        // 遍历除了头结点外的所有结点
        Node tmpNode = headNode.next;
        if (tmpNode == null){
            System.out.println("链表为空！");
            return;
        }

        while (tmpNode != null){
            System.out.println(tmpNode);
            // 指向下一个结点
            tmpNode = tmpNode.next;
        }
    }


}


class Node {

    int num;
    String name;
    Node next;
    Node prev;

    public Node(int num,String name){
        this.num = num;
        this.name = name;
    }

    @Override
    public String toString() {
        return "Node{" +
                "num=" + num +
                ", name='" + name + '\'' +
                '}';
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105

约瑟夫问题

约瑟夫问题为：设编号为 1，2，…n的n个人围坐一圈，约定编号为 k（1<=k<=n） 的人从 1 开始报数,数到 m 的那个人出列，它的下一位又从 1 开始报数，数到 m 的那个人又出列， 依次类推，直到所有人出列为止，由此产生一个出队编号的序列。

用一个不带头结点的循环链表来处理约瑟夫问题：先构成一个有 n 个结点的单循环链表，然后由 k 结点起从 1 开始计数，计到 m 时，对应结点从链表中删除，然后再从被删除结点的下一个结点又从 1 开始计数，直到最后一个结点从链表中删除算法结束。

class JoesphSingletonLinkedList {

    private Node first = null;


    // 向单向链表添加数据
    public void add(int nums) {
        if (nums < 1) {
            System.out.println("nums的值不正确");
            return;
        }
        Node cur = null;
        for (int i = 1; i <= nums; i++) {
            Node node = new Node(i);
            if (i == 1) {
                first = node;
                first.next = first;
                cur = first;
            } else {
                cur.next = node;
                node.next = first;
                cur = node;
            }
        }
    }


    // 遍历单向循环链表
    public void list() {
        Node tmp = first;
        while (true){
            System.out.printf("当前结点为：%d\n",tmp.num);
            if (tmp.next == first){
                break;
            }
            tmp = tmp.next;
        }
    }


    // 约瑟夫问题
    public void joseph(int startNum,int countNum,int sum){
        if (startNum > sum || startNum < 0 || countNum < 0) {
            System.out.println("输入的参数不正确！");
            return;
        }
        // 创建辅助指针，将该指针指向 first 的前一个
        Node helper = first;
        while (helper.next != first) {
            helper = helper.next;
        }

        // 将first 和 help指针循环 （startNum - 1）次；因为从startNum开始，需要减一
        for (int i = 0; i < startNum - 1; i++) {
            first = first.next;
            helper = helper.next;
        }

        while (true){
            // 当环形链表中只存在一个结点
            if (first == helper){
                break;
            }

            // 因为是环形链表，所以需要循环挨个出链表
            for (int i = 0; i < countNum - 1; i++) {
                first = first.next;
                helper = helper.next;
            }

            // 当前 first 就是出圈的结点
            System.out.printf("当前出队列的结点编号为：%d\n",first.num);
            first = first.next;
            helper.next = first;
        }
        System.out.printf("最后的结点为：%d\n",first.num);
    }

}


class Node {

    int num;
    Node next;

    public Node(int num){
        this.num = num;
    }

    @Override
    public String toString() {
        return "Node{" +
                "num=" + num +
                '}';
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97

栈

栈的英文为stack，是一个先入后出(FILO-First In Last Out)的有序列表，最先放入栈中元素在栈底，最后放入的元素在栈顶，而删除元素刚好相反，最后放入的元素最先删除，最先放入的元素最后删除。

栈是限制线性表中元素的插入和删除只能在线性表的同一端进行的一种特殊线性表。允许插入和删除的一端，为变化的一端，称为栈顶(Top)，另一端为固定的一端，称为栈底(Bottom)。

下图是出栈和入栈

栈的应用场景：

• 子程序的调用： 在跳往子程序前， 会先将下个指令的地址存到堆栈中， 直到子程序执行完后再将地址取出， 以回到原来的程序中；
• 处理递归调用： 和子程序的调用类似， 只是除了储存下一个指令的地址外， 也将参数、 区域变量等数据存入栈中；
• 表达式的转换：中缀表达式转后缀表达式与求值；
• 二叉树的遍历；
• 图形的深度优先(depth 一 first)搜索法；

数组模拟栈

class ArrayStack<T>{

    private int size;
    private int top;
    private Object[] stack;

    public ArrayStack(int size) {
        this.size = size;
        this.stack = new String[size];
        top = -1;
    }

    public boolean isFull(){
        return top == size -1;
    }

    public boolean isEmpty() {
        return top == -1;
    }

    // 入栈
    public void push(T item) {
        if (isFull()) {
            System.out.println("栈已经满了，不能继续添加！");
            return;
        }
        top++;
        this.stack[top] = item;
    }

    // 出栈操作
    public T pop() {
        if (isEmpty()) {
            throw new RuntimeException("栈已经为空，不能继续pop");
        }
        T val = (T)this.stack[top];
        top--;
        return val;
    }

    // 遍历栈
    public void list() {
        if (isEmpty()) {
            System.out.println("栈为空不能继续遍历！");
            return;
        }

        System.out.println("遍历栈==》");
        for (int i = top; i >=0; i--){
            System.out.println(this.stack[i]);
        }
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

栈实现中缀表达式

class CalcInfixExpressions {


    public int calcInfixExpressions(String expression) {
        // 定义变量
        char[] chars = expression.toCharArray();
        int len = chars.length;
        Stack<Integer> numStack = new Stack<>();
        Stack<Character> oprStack = new Stack<>();
        int index = 0;

        for (int j = 0; j < len; j++) {

            char ch = chars[j];

            index++;

            // 判断字符是否为数字,如果是数字就放入数栈中
            if (Character.isDigit(ch)) {

                // 接收多位数
                int num = ch;
                boolean flag = false;

                // 从当前字符开始遍历，如果下一位字符不是数字，则将该数字压入栈中并退出循环，如果是数字，则需要拼接起来
                for (int i = index; i < len; i++) {
                    if (Character.isDigit(expression.charAt(i))) {
                        String strNum = String.valueOf(ch) + expression.charAt(i);
                        num = Integer.parseInt(strNum);
                        flag = true;
                        index++;
                        j++;
                    }else {
                        break;
                    }
                }
                if (!flag) {
                    num -= 48;
                }
                numStack.push(num);
                continue;
            }

            // 非数字，即运算符,如果为空直接加入栈中
            if (oprStack.isEmpty()) {
                oprStack.push(ch);
                continue;
            }

            // 如果运算符栈不为空，需要比较运算符的优先级，如果当前运算符的优先级 <= 栈顶的运算符的优先级，需要计算在压入栈中
            if (oprPriority(oprStack.peek()) >= oprPriority(ch)) {
                numStack.push(calc(numStack.pop(), numStack.pop(), oprStack.pop()));
            }

            // 将字符压入操作符栈中
            oprStack.push(ch);
        }


        // 将处理好的数据按照顺序弹出，进行计算，得到数栈中最后一个数就是最终的结果
        while (!oprStack.isEmpty()){
            numStack.push(calc(numStack.pop(), numStack.pop(), oprStack.pop()));
        }

        return numStack.pop();
    }


    // 获取字符的优先级
    private int oprPriority(int ch) {
        if (ch == '*' || ch == '/') {
            return 2;
        }
        if (ch == '+' || ch == '-') {
            return 1;
        }
        return -1;
    }


    // 计算
    private int calc(int num1, int num2, int opr) {
        int res = 0;
        switch (opr) {
            case '+':
                res = num1 + num2;
                break;
            case '-':
                res = num2 - num1;
                break;
            case '*':
                res = num1 * num2;
                break;
            case '/':
                res = num2 / num1;
                break;
        }
        return res;
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101

栈实现后缀表达式

后缀表达式又称逆波兰表达式，与前缀表达式相似，只是运算符位于操作数之后。例如： (3+4)×5-6 对应的后缀表达式就是 3 4 + 5 × 6 –

思路：从左至右扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算（次顶元素 和 栈顶元素），并将结果入栈；重复上述过程直到表达式最右端，最后运算得出的值即为表达式的结果。

class PolandNotation{

    // 计算后缀表达式
    public int calcSuffixExceptions(String suffixExpres) {
        char[] chars = suffixExpres.toCharArray();
        Stack<Integer> stack = new Stack<>();
        int res =0;

        for (int i = 0; i < chars.length; i++) {
            char ch = suffixExpres.charAt(i);
            if (!Character.isDigit(ch)) {
                res = calc(stack.pop(),stack.pop(),ch);
                stack.push(res);
            }else {
                stack.push(ch - 48);
            }
        }
        return res;
    }

    // 计算
    private int calc(int num1, int num2, int opr) {
        int res = 0;
        switch (opr) {
            case '+':
                res = num1 + num2;
                break;
            case '-':
                res = num2 - num1;
                break;
            case '*':
                res = num1 * num2;
                break;
            case '/':
                res = num2 / num1;
                break;
            default:
                throw new RuntimeException("运算符有误");
        }
        return res;
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

中缀表达式转后缀表达式

中缀表达式转后缀表达式代码实现

class InfixToPolandNotation{

    // 根据ASCII 判断是否为数字
    private boolean isNumber(char ch){
        return ch >=48 && ch <= 57;
    }

    // 获取字符的优先级
    private int oprPriority(String opr) {
        if (opr.equals("*") || opr.equals("/")) {
            return 2;
        }
        if (opr.equals("+") || opr.equals("-")) {
            return 2;
        }
        return -1;
    }

    // 将中缀表达式字符串转成中缀表达式集合
    public List<String> toInfixExceptionList(String str) {
        ArrayList<String> list = new ArrayList<>();
        int index = 0;
        StringBuilder number;
        char c;

        while (index < str.length()){
            if (!isNumber((c = str.charAt(index)))){
                list.add(String.valueOf(c));
                index++;
            }else {
                number = new StringBuilder();
                while (index < str.length() && isNumber((c = str.charAt(index)))){
                    index++;
                    number.append(c);
                }
                list.add(number.toString());
            }
        }
        return list;
    }


    // 将中缀表达式转为后缀表达式
    public List<String> infixExpressionToSuffixExpress(List<String> list) {
        Stack<String> stack = new Stack<>();
        ArrayList<String> finalList = new ArrayList<>();

        for (String item : list) {
            // 如果是数字或者为（ 将该值压入栈中
            if (item.matches("\\d+")){
                finalList.add(item);
                continue;
            }

            if (item.equals("(")){
                stack.push(item);
                continue;
            }

            // 如果是 ）则将 ()中间的数重新压入list中，最后将 ） 移除掉
            if (item.equals(")")){
                while (!stack.peek().equals("(")) {
                    finalList.add(stack.pop());
                }
                stack.pop();
            }else {
                // 如果不是 ）则判断运算符的优先级，如果符号栈栈顶的优先级 >= 当前的优先级，则将该运算符加入数字栈中
                while (stack.size() > 0 && oprPriority(stack.peek()) >= oprPriority(item)){
                    finalList.add(stack.pop());
                }
                stack.push(item);
            }
        }

        // 将operStack中剩余的运算符依次弹出并加入tempList
        while (stack.size() != 0) {
            finalList.add(stack.pop());
        }
        return finalList;
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82

完整逆波兰表达式代码，支持小数、支持消除空格

public class ReversePolishMultiCalc {

	 /**
     * 匹配 + - * / ( ) 运算符
     */
    static final String SYMBOL = "\\+|-|\\*|/|\\(|\\)";

    static final String LEFT = "(";
    static final String RIGHT = ")";
    static final String ADD = "+";
    static final String MINUS= "-";
    static final String TIMES = "*";
    static final String DIVISION = "/";

    /**
     * 加減 + -
     */
    static final int LEVEL_01 = 1;
    /**
     * 乘除 * /
     */
    static final int LEVEL_02 = 2;

    /**
     * 括号
     */
    static final int LEVEL_HIGH = Integer.MAX_VALUE;


    static Stack<String> stack = new Stack<>();
    static List<String> data = Collections.synchronizedList(new ArrayList<String>());

    /**
     * 去除所有空白符
     * @param s
     * @return
     */
    public static String replaceAllBlank(String s ){
        // \\s+ 匹配任何空白字符，包括空格、制表符、换页符等等, 等价于[ \f\n\r\t\v]
        return s.replaceAll("\\s+","");
    }

    /**
     * 判断是不是数字 int double long float
     * @param s
     * @return
     */
    public static boolean isNumber(String s){
        Pattern pattern = Pattern.compile("^[-\\+]?[.\\d]*$");
        return pattern.matcher(s).matches();
    }

    /**
     * 判断是不是运算符
     * @param s
     * @return
     */
    public static boolean isSymbol(String s){
        return s.matches(SYMBOL);
    }

    /**
     * 匹配运算等级
     * @param s
     * @return
     */
    public static int calcLevel(String s){
        if("+".equals(s) || "-".equals(s)){
            return LEVEL_01;
        } else if("*".equals(s) || "/".equals(s)){
            return LEVEL_02;
        }
        return LEVEL_HIGH;
    }

    /**
     * 匹配
     * @param s
     */
    public static List<String> doMatch (String s) throws Exception{
        if(s == null || "".equals(s.trim())) throw new RuntimeException("data is empty");
        if(!isNumber(s.charAt(0)+"")) throw new RuntimeException("data illeagle,start not with a number");

        s = replaceAllBlank(s);

        String each;
        int start = 0;

        for (int i = 0; i < s.length(); i++) {
            if(isSymbol(s.charAt(i)+"")){
                each = s.charAt(i)+"";
                //栈为空，(操作符，或者 操作符优先级大于栈顶优先级 && 操作符优先级不是( )的优先级 及是 ) 不能直接入栈
                if(stack.isEmpty() || LEFT.equals(each)
                        || ((calcLevel(each) > calcLevel(stack.peek())) && calcLevel(each) < LEVEL_HIGH)){
                    stack.push(each);
                }else if( !stack.isEmpty() && calcLevel(each) <= calcLevel(stack.peek())){
                    //栈非空，操作符优先级小于等于栈顶优先级时出栈入列，直到栈为空，或者遇到了(，最后操作符入栈
                    while (!stack.isEmpty() && calcLevel(each) <= calcLevel(stack.peek()) ){
                        if(calcLevel(stack.peek()) == LEVEL_HIGH){
                            break;
                        }
                        data.add(stack.pop());
                    }
                    stack.push(each);
                }else if(RIGHT.equals(each)){
                    // ) 操作符，依次出栈入列直到空栈或者遇到了第一个)操作符，此时)出栈
                    while (!stack.isEmpty() && LEVEL_HIGH >= calcLevel(stack.peek())){
                        if(LEVEL_HIGH == calcLevel(stack.peek())){
                            stack.pop();
                            break;
                        }
                        data.add(stack.pop());
                    }
                }
                start = i ;    //前一个运算符的位置
            }else if( i == s.length()-1 || isSymbol(s.charAt(i+1)+"") ){
                each = start == 0 ? s.substring(start,i+1) : s.substring(start+1,i+1);
                if(isNumber(each)) {
                    data.add(each);
                    continue;
                }
                throw new RuntimeException("data not match number");
            }
        }
        //如果栈里还有元素，此时元素需要依次出栈入列，可以想象栈里剩下栈顶为/，栈底为+，应该依次出栈入列，可以直接翻转整个stack 添加到队列
        Collections.reverse(stack);
        data.addAll(new ArrayList<>(stack));

        System.out.println(data);
        return data;
    }

    /**
     * 算出结果
     * @param list
     * @return
     */
    public static Double doCalc(List<String> list){
        Double d = 0d;
        if(list == null || list.isEmpty()){
            return null;
        }
        if (list.size() == 1){
            System.out.println(list);
            d = Double.valueOf(list.get(0));
            return d;
        }
        ArrayList<String> list1 = new ArrayList<>();
        for (int i = 0; i < list.size(); i++) {
            list1.add(list.get(i));
            if(isSymbol(list.get(i))){
                Double d1 = doTheMath(list.get(i - 2), list.get(i - 1), list.get(i));
                list1.remove(i);
                list1.remove(i-1);
                list1.set(i-2,d1+"");
                list1.addAll(list.subList(i+1,list.size()));
                break;
            }
        }
        doCalc(list1);
        return d;
    }

    /**
     * 运算
     * @param s1
     * @param s2
     * @param symbol
     * @return
     */
    public static Double doTheMath(String s1,String s2,String symbol){
        Double result ;
        switch (symbol){
            case ADD : result = Double.valueOf(s1) + Double.valueOf(s2); break;
            case MINUS : result = Double.valueOf(s1) - Double.valueOf(s2); break;
            case TIMES : result = Double.valueOf(s1) * Double.valueOf(s2); break;
            case DIVISION : result = Double.valueOf(s1) / Double.valueOf(s2); break;
            default : result = null;
        }
        return result;

    }

    public static void main(String[] args) {
        //String math = "9+(3-1)*3+10/2";
        String math = "12.8 + (2 - 3.55)*4+10/5.0";
        try {
            doCalc(doMatch(math));
        } catch (Exception e) {
            e.printStackTrace();
        }
    }

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195

哈希表

哈希表也叫散列表，是根据关键码值(Key value)而直接进行访问的数据结构。

它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

手写模拟哈希表

public class HashTableDemo {

    public static void main(String[] args) {
        HashTab hashTab = new HashTab(3);
        Node node1 = new Node(1, "zs");
        Node node2 = new Node(2, "lx");
        Node node3 = new Node(3, "ex");
        Node node4 = new Node(4, "as");
        Node node5 = new Node(7, "we");

        hashTab.put(node1);
        hashTab.put(node2);
        hashTab.put(node3);
        hashTab.put(node4);
        hashTab.put(node5);

        System.out.println("添加元素后===》");
        System.out.println(hashTab.toString());

        System.out.println("删除后===》");
        hashTab.remove(4);
        System.out.println(hashTab.toString());
    }
}

class HashTab {

    private NodeList[] nodes;
    private int size;

    public HashTab(int size) {
        this.size = size;
        nodes = new NodeList[size];
        for (int i = 0; i < size; i++) {
            nodes[i] = new NodeList();
        }
    }

    public void put(Node node) {
        // 放入hash表的位置
        nodes[getPosition(node.id)].add(node);
    }

    public void remove(int id) {
        nodes[getPosition(id)].delete(id);
    }


    private int getPosition(int id) {
        return id % size;
    }

    @Override
    public String toString() {
        return "HashTab{" +
                "nodes=\n" + Arrays.toString(nodes) +
                "}";
    }
}

class NodeList {
    // 头结点
    Node head = null;

    // 添加结点方法
    public void add(Node node) {
        if (head == null) {
            head = node;
            return;
        }

        // 头结点不要动，将添加的结点放到链表的最后一个位置
        Node tmp = head;
        // 当下一个结点等于null时，找到最后一个结点
        while (tmp.next != null) {
            tmp = tmp.next;
        }
        tmp.next = node;
    }


    // 展示当前链表
    public void list() {
        if (head == null) {
            System.out.println("当前链表为空");
            return;
        }
        // 辅助结点
        Node tmp = head;
        while (true) {
            System.out.println(tmp);
            if (tmp.next == null) {
                break;
            }
            tmp = tmp.next;
        }
    }

    // 根据ID删除链表中的某个结点
    public void delete(int id) {
        if (head == null) {
            System.out.println("当前链表为空");
            return;
        }
        // 判断删除的是否是头结点
        if (head.id == id) {
            head = head.next;
            return;
        }

        Node preNode = head;
        Node curNode = preNode.next;
        while (curNode != null) {
            if (curNode.id == id) {
                preNode.next = curNode.next;
                System.out.println("删除成功，删除的是: " + curNode.id + "," + curNode.name);
                curNode = null;
                return;
            }
            preNode = preNode.next;
            curNode = curNode.next;
        }
        System.out.println("删除失败，节点不存在");
    }


    @Override
    public String toString() {
        return "NodeList{" +
                "head=" + head +
                "}\n";
    }
}

class Node {
    int id;
    String name;
    Node next;

    public Node(int id, String name) {
        this.id = id;
        this.name = name;
    }

    @Override
    public String toString() {
        return "Node{" +
                "id=" + id +
                ", name='" + name + '\'' +
                ", next=" + next +
                "}";
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153

二叉树

二叉树（Binary tree）是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。二叉树特点是每个结点最多只能有两棵子树，且有左右之分。

二叉树是n个有限元素的集合，该集合或者为空、或者由一个称为根的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成，是有序树。当集合为空时，称该二叉树为空二叉树。在二叉树中，一个元素也称作一个结点。

如果该二叉树的所有叶子节点都在最后一层，并且结点总数为 2^n -1， n 为层数，则称为满二叉树。

如果该二叉树的所有叶子节点都在最后一层或者倒数第二层，而且最后一层的叶子节点在左边连续，倒数第二层的叶子节点在右边连续，我们称为完全二叉树。

PS: 二叉树中结点等价于节点

二叉树的遍历及查找

对于二叉树来讲最主要、最基本的运算是遍历。遍历二叉树 是指以一定的次序访问二叉树中的每个结点。所谓访问结点是指对结点进行各种操作的简称。

例如，查询结点数据域的内容，或输出它的值，或找出结点位置，或是执行对结点的其他操作。遍历二叉树的过程实质是把二叉树的结点进行线性排列的过程。

二叉树的遍历方法：

• 前序遍历：先访问根结点，然后前序遍历左子树，在前序遍历右子树；
• 中序遍历：中序遍历根结点的左子树，然后访问根结点，最后遍历右子树；
• 后序遍历：后序遍历左子树，然后后序遍历右子树，最后访问根结点；

public class BinaryTreeDemo {

    public static void main(String[] args) {
        BinaryTreeObj root = new BinaryTreeObj(1,"zs");
        BinaryTreeObj binaryTreeObj2 = new BinaryTreeObj(2,"ls");
        BinaryTreeObj binaryTreeObj3 = new BinaryTreeObj(3,"ww");
        BinaryTreeObj binaryTreeObj4 = new BinaryTreeObj(4,"zq");
        BinaryTreeObj binaryTreeObj5 = new BinaryTreeObj(5,"111");

        root.setLeft(binaryTreeObj2);
        root.setRight(binaryTreeObj3);
        binaryTreeObj3.setLeft(binaryTreeObj4);
        binaryTreeObj3.setRight(binaryTreeObj5);

        BinaryTree binaryTree = new BinaryTree();
        binaryTree.setRoot(root);
        binaryTree.preOrderShow();

        BinaryTreeObj binaryTreeObj = binaryTree.preOrderSearch(11);
        if (binaryTreeObj == null) {
            System.out.println("没有找到该结点～");
            return;
        }
        System.out.printf("找到当前结点：id: %d, name: %s",binaryTreeObj.getId(),binaryTreeObj.getName());
    }
}


class BinaryTree {

    private BinaryTreeObj root;

    public void setRoot(BinaryTreeObj root) {
        this.root = root;
    }

    public void preOrderShow() {
        if (this.root != null) {
            this.root.preOrder();
        }
    }


    public void postOrderShow() {
        if (this.root != null) {
            this.root.postOrder();
        }
    }


    public void midOrderShow() {
        if (this.root != null) {
            this.root.midOrder();
        }
    }

    public BinaryTreeObj preOrderSearch(int id){
        if (this.root != null) {
            return this.root.preOrderSearch(id);
        }
        return null;
    }

    public BinaryTreeObj infixOrderSearch(int id){
        if (this.root != null) {
            return this.root.infixOrderSearch(id);
        }
        return null;
    }

    public BinaryTreeObj postOrderSearch(int id){
        if (this.root != null) {
            return this.root.postOrderSearch(id);
        }
        return null;
    }

}


class BinaryTreeObj {

    private Integer id;
    private String name;

    public BinaryTreeObj(Integer id,String name){
        this.id = id;
        this.name = name;
    }

    public String getName() {
        return name;
    }

    public Integer getId() {
        return id;
    }

    private BinaryTreeObj left;
    private BinaryTreeObj right;

    public void setLeft(BinaryTreeObj left) {
        this.left = left;
    }

    public void setRight(BinaryTreeObj right) {
        this.right = right;
    }

    // 前序遍历：根结点 =》 左结点 =》 右结点
    public void preOrder(){
        System.out.println(this);
        if (this.left != null){
            this.left.preOrder();
        }

        if (this.right != null){
            this.right.preOrder();
        }
    }

    // 后序遍历： 左结点 =》 右结点 =》 根结点
    public void postOrder(){

        if (this.left != null){
            this.left.postOrder();
        }

        if (this.right != null){
            this.right.postOrder();
        }
        System.out.println(this);
    }

    // 中序遍历： 左结点 =》 根结点 =》 右结点
    public void midOrder(){

        if (this.left != null){
            this.left.midOrder();
        }
        System.out.println(this);

        if (this.right != null){
            this.right.midOrder();
        }
    }

    // 前序查找
    public BinaryTreeObj preOrderSearch(int id) {
        if (id == this.id){
            return this;
        }

        BinaryTreeObj binaryTreeObj = null;
        if (this.left != null){
            binaryTreeObj = this.left.preOrderSearch(id);
        }

        if (binaryTreeObj != null){
            return binaryTreeObj;
        }

        if (this.right != null){
            binaryTreeObj = this.right.preOrderSearch(id);
        }
        return binaryTreeObj;
    }

    // 中序查找
    public BinaryTreeObj infixOrderSearch(int id) {

        BinaryTreeObj binaryTreeObj = null;
        if (this.left != null){
            binaryTreeObj = this.left.infixOrderSearch(id);
        }

        if (id == this.id){
            return this;
        }

        if (binaryTreeObj != null){
            return binaryTreeObj;
        }

        if (this.right != null){
            binaryTreeObj = this.right.infixOrderSearch(id);
        }
        return binaryTreeObj;
    }

    // 后序查找
    public BinaryTreeObj postOrderSearch(int id) {

        BinaryTreeObj binaryTreeObj = null;
        if (this.left != null){
            binaryTreeObj = this.left.postOrderSearch(id);
        }

        if (binaryTreeObj != null){
            return binaryTreeObj;
        }

        if (this.right != null){
            binaryTreeObj = this.right.postOrderSearch(id);
        }
        if (id == this.id){
            return this;
        }
        return binaryTreeObj;
    }

    @Override
    public String toString() {
        return "BinaryTreeObj{" +
                "id=" + id +
                ", name='" + name + '\'' +
                '}';
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219

二叉树的删除

class BinaryTree {
    public void del(int id){
        if (this.root == null){
            return;
        }
        if (this.root.getId() == id){
            this.root = null;
            return;
        }
        this.root.delNo(id);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

class BinaryTreeObj {
    // 根据ID删除结点
    public void delNo(int id){
        // 找到当前结点的左子树结点是否为指定结点，如果是则将其置空
        if (this.left != null && this.left.id == id){
            this.left = null;
            return;
        }

        // 与上面同理删除右子树结点
        if (this.right != null && this.right.id == id){
            this.right = null;
            return;
        }


        if (this.left == null && this.right == null){
            return;
        }

        // 如果当前左结点或右结点 不是要删除的结点 则进行递归删除
        if (this.left != null){
            this.left.delNo(id);
        }

        if (this.right != null) {
            this.right.delNo(id);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

顺序存储二叉树

二叉树的顺序存储，指的是使用顺序表（数组）存储二叉树。

需要注意的是，顺序存储只适用于完全二叉树。换句话说，只有完全二叉树才可以使用顺序表存储。因此，如果我们想顺序存储普通二叉树，需要提前将普通二叉树转化为完全二叉树。

顺序存储二叉树应用实例：八大排序算法中的堆排序，就会使用到顺序存储二叉树。

public class ArrBinaryTreeDemo {
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5, 6, 7};
        ArrBinaryTree arrBinaryTree = new ArrBinaryTree();
        arrBinaryTree.setArrayTree(arr);
        arrBinaryTree.preArrBinaryTree(0);
    }
}

class ArrBinaryTree {

    private int[] arr = null;

    public void setArrayTree(int[] arr) {
        this.arr = arr;
    }

    public void preArrBinaryTree(int index) {
        if (arr == null || arr.length == 0) {
            return;
        }
        System.out.println(arr[index]);

        int nextLeftIndex = (index << 1) + 1;
        int nextRightIndex = (index << 1) + 2;

        if (nextLeftIndex < arr.length) {
            preArrBinaryTree(nextLeftIndex);
        }

        if (nextRightIndex < arr.length) {
            preArrBinaryTree(nextRightIndex);
        }
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

线索化二叉树

n 个结点的二叉链表中含有 n+1【公式 2n-(n-1)=n+1】个空指针域。利用二叉链表中的空指针域，存放指向该结点在 某种遍历次序 下的前驱和后继结点的指针，这种附加的指针称为"线索"。这种加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树。

根据线索性质的不同，线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种。

如图，按照前序遍历可以得到数组 {1, 2, 4, 5, 3, 6} 其中

• 【2】的前驱结点为【1】，后继结点为【4】
• 【6】的前驱结点为【3】，后继结点为 null

中序线索化二叉树示意图

public class ThreadedBinaryTreeDemo {

    public static void main(String[] args) {
        BinaryTreeObj root = new BinaryTreeObj(1,"zs");
        BinaryTreeObj binaryTreeObj2 = new BinaryTreeObj(2,"ls");
        BinaryTreeObj binaryTreeObj3 = new BinaryTreeObj(3,"ww");
        BinaryTreeObj binaryTreeObj4 = new BinaryTreeObj(4,"zq");
        BinaryTreeObj binaryTreeObj5 = new BinaryTreeObj(5,"111");

        root.setLeft(binaryTreeObj2);
        root.setRight(binaryTreeObj3);
        binaryTreeObj3.setLeft(binaryTreeObj4);
        binaryTreeObj3.setRight(binaryTreeObj5);

        // 中序线索化二叉树
        ThreadedBinaryTree threadedBinaryTree = new ThreadedBinaryTree();
        threadedBinaryTree.infixThreadedBinaryTree(root);

        // 遍历中序线索化二叉树
        threadedBinaryTree.forEachInfixThreadedBinaryTree(root); // 2,1,4,3,5
    }
}


class ThreadedBinaryTree{

    private BinaryTreeObj pre;

    // 中序线索化二叉树
    public void infixThreadedBinaryTree(BinaryTreeObj node){
        if (node == null){
            return;
        }
        // 左递归线索化二叉树
        infixThreadedBinaryTree(node.getLeft());

        // 线索化核心代码 将左结点线索化
        if (node.getLeft() == null){
            node.setLeft(pre);
            node.setLeftType(1);
        }
        // 将右结点线索化
        if (pre != null && pre.getRight() == null) {
            pre.setRight(node);
            pre.setRightType(1);
        }
        // 使辅助结点指针指向当前结点
        pre = node;

        // 右递归线索化二叉树
        infixThreadedBinaryTree(node.getRight());
    }

    // 遍历中序线索二叉树
    public void forEachInfixThreadedBinaryTree(BinaryTreeObj root) {
        // 用辅助结点保存根结点
        BinaryTreeObj node = root;

        while (node != null){

            // 向左子树遍历,直到找到 leftType=1 的结点，等于1代表该结点为前驱结点
            while (node.getLeftType() == 0){
                node = node.getLeft();
            }
            System.out.println(node);

            // 向右子树遍历，直到找到 rightType=0 的结点， 等于0代表该结点为右子树
            while (node.getRightType() == 1){
                node = node.getRight();
                System.out.println(node);
            }

            // node 结点向右边找
            node = node.getRight();
        }
    }
}

class BinaryTreeObj {

    private Integer id;
    private String name;

    private BinaryTreeObj left;
    private BinaryTreeObj right;

    // 如果leftType == 0 表示指向的是左子树, 如果 1 则表示指向前驱结点
    // 如果rightType == 0 表示指向是右子树, 如果 1 表示指向后继结点
    private int leftType;
    private int rightType;

    public BinaryTreeObj(Integer id,String name){
        this.id = id;
        this.name = name;
    }
    public String getName() {
        return name;
    }
    public Integer getId() {
        return id;
    }
    public BinaryTreeObj getLeft() {
        return left;
    }
    public BinaryTreeObj getRight() {
        return right;
    }
    public void setLeft(BinaryTreeObj left) {
        this.left = left;
    }
    public void setRight(BinaryTreeObj right) {
        this.right = right;
    }
    public void setLeftType(int leftType) {
        this.leftType = leftType;
    }
    public void setRightType(int rightType) {
        this.rightType = rightType;
    }
    public int getLeftType() {
        return leftType;
    }
    public int getRightType() {
        return rightType;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126

哈夫曼树

哈夫曼树重要概念：

• 路径和路径长度：在一棵树中，从一个结点往下可以达到的孩子或孙子结点之间的通路，称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为 1，则从根结点到第 L 层结点的路径长度为 L-1；
• 结点的权及带权路径长度：若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积；
• 树的带权路径长度：树的带权路径长度规定为所有叶子结点的带权路径长度之和，记为WPL(weighted path length) ，权值越大的结点离根结点越近的二叉树才是最优二叉树。WPL 最小的就是赫夫曼树；

给定n个权值作为n个叶子结点，构造一棵二叉树，若该树的带权路径长度(wpl)达到最小，称这样的二叉树为最优二叉树，称为哈夫曼树，有些资料也译为赫夫曼树。

WPL最小的就是哈夫曼树，如上图，中间的树就是哈夫曼树。

public class HuffmanTreeDemo {
    public static void main(String[] args) {
        HuffmanTree huffmanTree = new HuffmanTree();
        HuffmanTreeNode root = huffmanTree.buildHuffmanTree(new int[]{13, 7, 8, 3, 29, 6, 1});
        System.out.println("前序遍历huffman树：");
        huffmanTree.preOrder(root);
    }
}

class HuffmanTree{

    public void preOrder(HuffmanTreeNode root){
        if (root != null){
            root.preOrder();
        }
    }

    public HuffmanTreeNode buildHuffmanTree(int[] arr){

        List<HuffmanTreeNode> list = new ArrayList<>();
        for (int value : arr) {
            list.add(new HuffmanTreeNode(value));
        }

        // 如果集合中的元素大于1则继续循环
        while (list.size() > 1){
            // 从大到小进行排序
            Collections.sort(list);

            // 获取集合中两个较小的元素进行构建 huffman 树
            HuffmanTreeNode leftNode = list.get(0);
            HuffmanTreeNode rightNode = list.get(1);
            HuffmanTreeNode parentNode = new HuffmanTreeNode(leftNode.value + rightNode.value);
            parentNode.left = leftNode;
            parentNode.right = rightNode;

            // 构建后将 leftNode， rightNode 移除集合；将parentNode加入集合；然后重新排序
            list.remove(leftNode);
            list.remove(rightNode);
            list.add(parentNode);
        }
        return list.get(0);
    }

}


class HuffmanTreeNode implements Comparable<HuffmanTreeNode>{
    int value;
    HuffmanTreeNode left;
    HuffmanTreeNode right;

    public HuffmanTreeNode(int value){
        this.value = value;
    }

    public void preOrder(){
        System.out.println(this);
        if (this.left != null){
            this.left.preOrder();
        }
        if (this.right != null){
            this.right.preOrder();
        }
    }

    @Override
    public int compareTo(HuffmanTreeNode o) {
        // 从小到大排序
        return this.value - o.value;
    }

    @Override
    public String toString() {
        return "HuffmanTreeNode{" +
                "value=" + value +
                '}';
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79

二叉排序树

二叉排序树（Binary Sort Tree），又称二叉查找树（Binary Search Tree），亦称二叉搜索树。是数据结构中的一类。在一般情况下，查询效率比链表结构要高。

对于二叉排序树的任何一个非叶子节点，要求左子节点的值比当前节点的值小，右子节点的值比当前节点的值大。如果有相同的值，可以将该节点放在左子节点或右子节点，二叉排序树的中序遍历为有序数列。

class BinarySortTree {

    private Node root;

    public void setRoot(Node root) {
        this.root = root;
    }

    // 添加结点
    public void add(Node node) {
        if (this.root == null) {
            this.root = node;
        } else {
            this.root.add(node);
        }
    }

    // 中序遍历
    public void infixOrder() {
        if (this.root != null) {
            this.root.infixOrder();
        }
    }

    // 查找结点
    public Node search(int target) {
        if (this.root == null) {
            return null;
        }
        return this.root.search(target);
    }

    // 查找当前结点的父结点
    public Node searchParentNode(int target) {
        if (this.root == null) {
            return null;
        }
        return this.root.searchParentNode(target);
    }

    // 删除结点
    public void delNode(int target) {
        if (this.root == null) {
            return;
        }
        // 如果删除的结点是根结点
        if (this.root.left == null && this.root.right == null) {
            this.root = null;
            return;
        }
        Node targetNode = search(target);
        if (targetNode == null) {
            return;
        }
        // 获取当前结点的父结点
        Node parentNode = searchParentNode(target);
        // 删除的结点是叶子结点
        if (targetNode.left == null && targetNode.right == null) {
            // 判断是左结点还是右结点
            if (parentNode.left != null && parentNode.left.val == target) {
                parentNode.left = null;
            } else {
                parentNode.right = null;
            }
            return;
        }

        // 删除的结点有两个结点
        if (targetNode.left != null && targetNode.right != null) {
            // 从右子树找到最小的值并删除，将该值赋值给targetNode
            targetNode.val = delRightTreeMin(targetNode.right);
            return;
        }

        // 删除只有一颗子树的结点
        if (targetNode.left != null) {
            if(parentNode == null){
                root = targetNode.left;
                return;
            }
            // 当前结点存在左子树
            if (parentNode.left.val == target) {
                parentNode.left = targetNode.left;
            } else {
                parentNode.right = targetNode.left;
            }
        }
        if (targetNode.right != null) {
            if(parentNode == null){
                root = targetNode.right;
                return;
            }
            // 当前结点存在右子树
            if (parentNode.right.val == target) {
                parentNode.left = targetNode.right;
            } else {
                parentNode.right = targetNode.right;
            }
        }
    }

    private int delRightTreeMin(Node node) {
        Node target = node;
        // 循环的查找左子节点，就会找到最小值
        while (target.left != null) {
            target = target.left;
        }
        // 此时 target就指向了最小结点 删除最小结点（该节点肯定是左叶子节点）
        delNode(target.val);
        return target.val;
    }

}

class Node {
    int val;
    Node left;
    Node right;

    public Node(int val) {
        this.val = val;
    }

    // 查找结点
    public Node search(int target) {
        if (this.val == target) {
            return this;
        } else if (this.val > target) {
            if (this.left == null) {
                return null;
            }
            return this.left.search(target);
        } else {
            if (this.right == null) {
                return null;
            }
            return this.right.search(target);
        }
    }

    // 查找当前结点的父结点
    public Node searchParentNode(int target) {
        if ((this.left != null && this.left.val == target) || (this.right != null && this.right.val == target)) {
            return this;
        } else if (this.left != null && this.val > target) {
            return this.left.searchParentNode(target);
        } else if (this.right != null && this.val <= target) {
            return this.right.searchParentNode(target);
        } else {
            return null;
        }
    }

    // 添加结点
    public void add(Node node) {
        if (node == null) {
            return;
        }
        // 如果当前待插入结点的值小于当前结点，将其插入在左子树中
        if (node.val < this.val) {
            if (this.left == null) {
                this.left = node;
            } else {
                this.left.add(node);
            }
        } else {
            // 将当前结点插入右子树
            if (this.right == null) {
                this.right = node;
            } else {
                this.right.add(node);
            }
        }
    }

    // 中序遍历
    public void infixOrder() {
        if (this.left != null) {
            this.left.infixOrder();
        }
        System.out.println(this);
        if (this.right != null) {
            this.right.infixOrder();
        }
    }

    @Override
    public String toString() {
        return "Node{" +
                "val=" + val +
                '}';
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193

平衡二叉树

二叉搜索树一定程度上可以提高搜索效率，但是当序列构造二叉搜索树，可能会将二叉树退化成单链表，从而降低搜索效率。

平衡二叉树也叫平衡二叉搜索树（Self-balancing binary search tree）又被称为AVL树，可以保证查询效率较高。

平衡二叉树的特点：

• 平衡二叉树一定是二叉排序；
• 是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树；

将有序二叉树变为平衡二叉树代码

public class AVLTreeDemo {
    public static void main(String[] args) {
        AVLTree avlTree = new AVLTree();
        int[] arr = {10, 11, 7, 6, 8, 9 };
        for (int i = 0; i < arr.length; i++) {
            Node node = new Node(arr[i]);
            avlTree.add(node);
        }
        System.out.println("当前树高度："+ avlTree.height());
        System.out.println("当前根结点：" + avlTree.getRoot());
        System.out.println("当前左子树高度："+ avlTree.getRoot().leftHeight());
        System.out.println("当前右子树高度："+ avlTree.getRoot().rightHeight());
    }
}

class AVLTree{
    private Node root;

    public void setRoot(Node root) {
        this.root = root;
    }

    public Node getRoot() {
        return root;
    }

    public int height(){
        if (root == null){
            return 0;
        }
        return this.root.height();
    }

    // 添加结点
    public void add(Node node) {
        if (this.root == null) {
            this.root = node;
        } else {
            this.root.add(node);
        }
    }

    // 中序遍历
    public void infixOrder() {
        if (this.root != null) {
            this.root.infixOrder();
        }
    }

}

class Node {

    int value;
    Node left;
    Node right;

    public Node(int value) {
        this.value = value;
    }
    
    // 获取当前左子树的高度
    public int leftHeight(){
        if (this.left == null){
            return 0;
        }
        return this.left.height();
    }
    
    // 获取当前结点右子树的高度
    public int rightHeight(){
        if (this.right == null){
            return 0;
        }
        return this.right.height();
    }

    // 获取当前结点的高度
    public int height() {
        return Math.max(
                (this.left == null ? 0 : this.left.height()),
                (this.right == null ? 0 : this.right.height())
        ) + 1;
    }

    // 左旋转
    public void leftRote(){
        // 创建一个新结点，并设置值等于当前结点的值
        Node newNode = new Node(value);
        // 使新结点的左结点指向当前结点的左结点
        newNode.left = left;
        // 新结点的右结点指向当前结点的右结点的左结点
        newNode.right = right.left;
        // 使当前结点的值指向新结点
        value = right.value;
        // 使当前结点的右结点指向当前结点的右结点的右结点
        right = right.right;
        // 使当前结点的左结点指向新结点
        left = newNode;
    }

    // 右旋转
    public void rightRote(){
        Node newNode = new Node(value);
        newNode.right = right;
        newNode.left = left.right;
        value = left.value;
        left = left.left;
        right = newNode;
    }

    // 添加结点
    public void add(Node node) {
        if (node == null) {
            return;
        }
        // 如果当前待插入结点的值小于当前结点，将其插入在左子树中
        if (node.value < this.value) {
            if (this.left == null) {
                this.left = node;
            } else {
                this.left.add(node);
            }
        } else {
            // 将当前结点插入右子树
            if (this.right == null) {
                this.right = node;
            } else {
                this.right.add(node);
            }
        }
        // 如果左子树的高度-右子树的高度 > 1 进行右旋转 反之进行左旋转
        if (this.leftHeight() - this.rightHeight() > 1){
            // 如果当前结点的左子树的右子树的高度>当前结点左子树的左子树的高度 则进行左旋转
            if (this.left != null && this.left.rightHeight() > this.left.leftHeight()){
                // 对当前结点的左结点进行左旋转
                this.left.leftRote();
                // 对当前结点右旋转
                this.rightRote();
            }else {
                this.rightRote();
            }
            return;
        }
        if (this.rightHeight() - this.leftHeight() > 1) {
            if (this.right != null && this.right.leftHeight() > this.right.rightHeight()){
                // 对当前结点的右结点进行右旋转
                this.right.rightRote();
                // 对当前结点进行左旋转
                this.leftRote();
            }else {
                this.leftRote();
            }
        }
    }

    // 中序遍历
    public void infixOrder() {
        if (this.left != null) {
            this.left.infixOrder();
        }
        System.out.println(this);
        if (this.right != null) {
            this.right.infixOrder();
        }
    }

    @Override
    public String toString() {
        return "Node{" +
                "value=" + value +
                '}';
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174

多路查找树

在二叉树中，每个节点有数据项，最多有两个子节点。如果允许每个节点可以有更多的数据项和更多的子节点，就是多叉树（multiway tree）。多叉树通过重新组织节点，减少树的高度，能对二叉树进行优化。典型的多叉树有：2-3树、2-3-4树、红黑树和B树。

多叉树的前提是有序二叉树。

2-3树

2-3树是由二节点和三节点构成的树，是最简单的B树结构，2-3树的所有叶子节点都在同一层(只要是B树都满足这个条件)。

• 有两个子节点的节点叫二节点，二节点要么没有子节点，要么有两个子节点；
• 有三个子节点的节点叫三节点，三节点要么没有子节点，要么有三个子节点；

2-3-4树，与2-3树类似。

B树

B-tree 树即 B 树，B 即 Balanced ，平衡的意思。 B树通过重新组织节点，降低树的高度，并且减少i/o读写次数来提升效率。

文件系统及数据库系统的设计者利用了磁盘预读原理，将一个节点的大小设为等于一个页(页的大小通常为4k)，这样每个节点只需要一次I/O就可以完全载入。

B树的阶（度）：节点的最多子节点个数。比如2-3树的阶是3，2-3-4树的阶是4。

B树的搜索，从根结点开始，对结点内的关键字（有序）序列进行二分查找，如果命中则结束，否则进入查询关键字所属范围的儿子结点；重复，直到所对应的儿子指针为空，或已经是叶子结点。

B树的关键字集合分布在整颗树中，即叶子节点和非叶子节点都存放数据，搜索有可能在非叶子结点结束，其搜索性能等价于在关键字全集内做一次二分查找。

B+树

B+树是B树的变体，也是一种多路搜索树。

B+树的搜索与B树也基本相同，区别是B+树只有达到叶子结点才命中（B树可以在非叶子结点命中），其性能也等价于在关键字全集做一次二分查找。

B+树所有关键字都出现在叶子结点的链表中（即数据只能在叶子节点【也叫稠密索引】），且链表中的关键字(数据)恰好是有序的。所以不可能在非叶子结点命中。

B+树的所有叶结点构成一个有序链表，可以按照关键码排序的次序遍历全部记录， B+树更适合文件索引系统，B树和B+树各有自己的应用场景，不能说B+树完全比B树好，反之亦然。

B*树

B* 树是B+树的变体，在B+树的非根和非叶子结点再增加指向兄弟的指针。

图

图是一种数据结构，其中结点可以具有零个或多个相邻元素。两个结点之间的连接称为边。结点也可以称为顶点。

如果给图的每条边规定一个方向，那么得到的图称为有向图。在有向图中，与一个节点相关联的边有出边和入边之分。相反，边没有方向的图称为无向图。

可用二维数组表示图（邻接矩阵）；或链表表示（邻接表）。

用java模拟图，包括图的深度遍历，广度遍历。

public class GraphDemo {
  public static void main(String[] args) {
    String[] vertexes = {"A", "B", "C", "D", "E"};
    int n = vertexes.length;
    Graph graph = new Graph(n);
    for (String vertex : vertexes) {
      graph.addVertex(vertex);
    }
    graph.addEdge(0, 1, 1); // A-B
    graph.addEdge(0, 2, 1); // A-C
    graph.addEdge(1, 2, 1); // B-C
    graph.addEdge(1, 3, 1); // B-D
    graph.addEdge(1, 4, 1); // B-E
    // 展示图转换的矩阵
    graph.showEdges();
    // 图的深度遍历
    graph.dfs();
    System.out.println();
    // 图的广度遍历
    graph.bfs();
  }
}

class Graph {

  // 保存顶点
  private List<String> vertexList;

  // 保存边的数量
  private int sideNums;

  // 保存图的矩阵
  private int[][] edges;

  private boolean[] isVisited;

  public Graph(int n) {
    vertexList = new ArrayList<>(n);
    edges = new int[n][n];
    sideNums = 0;
  }

  // 获取第一个结点的下一个结点
  private int getFirstNeighbor(int index) {
    for (int i = 0; i < vertexList.size(); i++) {
      if (edges[index][i] > 1) {
        return i;
      }
    }
    return -1;
  }

  // 获取当前结点的下一个结点
  private int getNextNeighbor(int vertex, int index) {
    for (int i = vertex + 1; i < vertexList.size(); i++) {
      if (edges[index][i] > 1) {
        return i;
      }
    }
    return -1;
  }

  // 图的深度遍历
  private void dfs(boolean[] isVisited, int i) {
    System.out.print(getVertexValByIndex(i) + "->");
    // 将当前遍历后的顶点标记为true
    isVisited[i] = true;
    // 获取当前结点的下一个结点的索引位置
    int firstNeighborIndex = getFirstNeighbor(i);
    // 如果 ！= -1 代表当前结点没有找到下一个结点，需要向下移动
    while (firstNeighborIndex != -1) {
      // 判断该结点是否被遍历过
      if (!isVisited[firstNeighborIndex]) {
        dfs(isVisited, firstNeighborIndex);
      }
      // 当前结点向后移动，否则是死循环
      firstNeighborIndex = getNextNeighbor(firstNeighborIndex, i);
    }
  }

  public void dfs() {
    isVisited = new boolean[vertexList.size()];
    for (int i = 0; i < getVertexCount(); i++) {
      if (!isVisited[i]) {
        dfs(isVisited, i);
      }
    }
  }

  // 一个结点的广度优先遍历
  private void bfs(boolean[] isVisited, int i) {
    // 队列头结点下标索引
    int headIndex;
    // 相邻结点下标索引
    int neighborIndex;
    LinkedList<Integer> queue = new LinkedList<>();

    System.out.print(getVertexValByIndex(i) + "->");
    isVisited[i] = true;
    queue.addLast(i);

    // 如果队列不等于空 则需要遍历循环查找
    while (!queue.isEmpty()) {
      headIndex = queue.removeFirst();
      // 得到第一个邻接结点的下标
      neighborIndex = getFirstNeighbor(headIndex);
      while (neighborIndex != -1) {
        // 是否访问过
        if (!isVisited[neighborIndex]) {
          System.out.print(getVertexValByIndex(neighborIndex) + "->");
          isVisited[neighborIndex] = true;
          queue.addLast(neighborIndex);
        }
        // neighborIndex 向下找
        neighborIndex = getNextNeighbor(headIndex, neighborIndex);
      }
    }
  }

  // 广度优先遍历
  public void bfs() {
    isVisited = new boolean[vertexList.size()];
    for (int i = 0; i < getVertexCount(); i++) {
      if (!isVisited[i]) {
        bfs(isVisited, i);
      }
    }
  }

  // 添加顶点
  public void addVertex(String vertex) {
    vertexList.add(vertex);
  }

  // 添加边
  public void addEdge(int vertex1, int vertex2, int weight) {
    edges[vertex1][vertex2] = weight;
    edges[vertex2][vertex1] = weight;
    sideNums++;
  }

  // 获取边的数量
  public int getSideNums() {
    return sideNums;
  }

  // 遍历矩阵
  public void showEdges() {
    for (int[] edge : edges) {
      System.out.println(Arrays.toString(edge));
    }
  }

  // 获取顶点数量
  public int getVertexCount() {
    return vertexList.size();
  }

  // 获取边之间的权值
  public int getVertexWeight(int vertex1, int vertex2) {
    return edges[vertex1][vertex2];
  }

  // 根据下标获取结点的值
  public String getVertexValByIndex(int index) {
    return vertexList.get(index);
  }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169

算法

英文对应的单词是Algorithm，它的本意为：解决问题的方法，所以算法的直接理解就是解决问题的方法。在计算机领域定义的话就是：一系列解决问题的、清晰、可执行的计算机指令。

一个算法的优劣可以用空间复杂度与时间复杂度来衡量。

算法复杂度

时间复杂度

度量一个算法执行时间的两种方法：

• 事后统计法：即直接运行程序，统计需要的时间和空间。但是，这种方法有两个问题：

  1. 结果非常依赖于测试环境。比如，用i3和用i8运行程序所需的时间是不同的;
  2. 结果受测试规模的影响特别大。比如，对有序数组进行排序的时间比对逆序数组排序的时间短；对于小规模数据而言，插入排序所需时间比快速排序要短;

  所以，就需要有一种不用具体测试数据，也能估计算法执行效率的方法，就是算法复杂度分析，包括时间、空间复杂度分析。

• 事前估算法：通过分析某个算法的时间复杂度来判断那个算法更优;

一般情况下，算法中的基本操作语句的重复执行次数是问题规模 n 的某个函数， 用T(n)表示，若有某个辅助函数f(n)，使得当 n 趋近于无穷大时，T(n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作 T(n)=Ｏ(f(n))， 称Ｏ(f(n))为算法的渐进时间复杂度，简称时间复杂度。

例如，T(n) = n + 1 与 T(n) = n 就是同数量级函数，因为 n+1/n 的极限值为不等于零的常数。
T(n) 不同，但时间复杂度可能相同: T(n)=n²+7n+6 与 T(n)=3n²+2n+2 它们的 T(n) 不同， 但时间复杂度相同，都为 O(n²)。

计算时间复杂度的方法：

• 用常数 1 代替运行时间中的所有加法常数： T(n)=n²+7n+6 => T(n)=n²+7n+1
• 修改后的运行次数函数中，只保留最高阶项： T(n)=n²+7n+1 => T(n) = n²
• 去除最高阶项的系数：T(n) = n² => T(n) = n² => O(n²)

---

时间频度

一个算法花费的时间与算法中的语句的执行次数成正比例,哪个算法执行次数多,他花费的时间就多.一个算法中的语句执行次数称为语句频度或时间频度.记为T(n)。

随着时间的推移，一些复杂度花费时间无限接近：

1. 忽略常数项:

• 2n+20 和 2n 随着 n 变大，执行曲线无限接近,20 可以忽略
• 3n+10 和 3n 随着 n 变大，执行曲线无限接近,10 可以忽略

2. 忽略低次项:

• 2n²+3n+10 和 2n² 随着 n 变大, 执行曲线无限接近,可以忽略 3n+10
• n²+5n+20 和 n² 随着 n 变大,执行曲线无限接近,可以忽略 5n+20

3. 忽略系数:

• 随着 n 值变大， 5n²+7n 和 3n² + 2n ，执行曲线重合, 说明这种情况下, 5 和 3 可以忽略
• 对于 n^3+5n 和 6n^3+4n，执行曲线分离，不能忽略系数，说明多少次方是关键

---

常见的时间复杂度

• 常数阶 O(1): 无论代码执行了多少行，只要是没有循环等复杂结构，这个代码的时间复杂度就都是O(1)；

  int i = 1;
  int j = 2;
  ++i;
  j++;
  int m = i + j;
  1
  2
  3
  4
  5

• 对数阶 O(log2n)

  

  int i = 1;
  while(i<n){
      i = i*2;
  }
  1
  2
  3
  4

• 线性阶 O(n): 它消耗的时间是随着n的变化而变化的,与n成正比或反比；

  for(int i=1; i<=n; ++i){
      j = i;
      j++;
  }
  1
  2
  3
  4

• 线性对数阶 O(nlog2n): 将时间复杂度为O(logn)的代码循环n遍，那么它的时间复杂度就是 n * O(logN)，也就是了O(nlogN);

  for(int m=1; m<=n; ++m){
      int i = 1;
      while(i<n){
          i = i*2;
      }
  }
  1
  2
  3
  4
  5
  6

• 平方阶 O(n^2): 如果把 O(n) 的代码再嵌套循环一遍，它的时间复杂度就是 O(n²)，这段代码其实就是嵌套了2层n循环，它的时间复杂度就是 O(n*n)，即 O(n²) 如果将其中一层循环的n改成m，那它的时间复杂度就变成了 O(m*n);

  for(int i=1; i<=n; ++i){
      for(int j=1; j<=n; ++j){
          j=i;
      }
  }
  1
  2
  3
  4
  5

• 立方阶 O(n^3)

  for(int i=1; i<=n; ++i){
      for(int j=1; j<=n; ++j){
          for(int x=1; x<=n; ++x){
              int m = 0;
              i = x+j;
          }
      }
  }
  1
  2
  3
  4
  5
  6
  7
  8

• k 次方阶 O(n^k)

• 指数阶 O(2^n)

常见的算法时间复杂度由小到大依次为：

Ο (1)＜Ο (log2n)＜Ο (n)＜Ο (nlog2n)＜Ο (n2)＜Ο (n3)＜ Ο (nk) ＜ Ο (2n)
1

随着问题规模 n 的不断增大，上述时间复杂度不断增大，算法的执行效率越低。

空间复杂度

类似于时间复杂度的讨论，一个算法的空间复杂度(Space Complexity)定义为该算法所耗费的存储空间，它也是问题规模 n 的函数。

空间复杂度全称为渐进空间复杂度，是对一个算法在运行过程中临时占用存储空间大小的量度。 有的算法需要占用的临时工作单元数与解决问题的规模 n 有关， 它随着 n 的增大而增大， 当 n 较大时， 将占用较多的存储单元， 例如快速排序和归并排序算法, 基数排序就属于这种情况
在做算法分析时， 主要讨论的是时间复杂度。 从用户使用体验上看， 更看重的程序执行的速度。 一些缓存产品(redis, memcache)和算法(基数排序)本质就是用空间换时间

空间复杂度较为简单，常见的空间复杂度为 O(1)，O(n) 和 O(n ^ 2)。

递归

递归就是方法自己调用自己，每次调用时传入不同的变量，递归有助于编程者解决复杂的问题，同时可以让代码变得简洁。

递归能解决什么问题？

• 各种数学问题如: 8 皇后问题，汉诺塔，阶乘问题，迷宫问题，球和篮子的问题(google 编程大赛)；
• 各种算法中也会使用到递归， 比如快排， 归并排序， 二分查找， 分治算法等；
• 用栈解决的问题，使用递归替换代码更佳简洁；

使用递归遵守的规则：

• 执行一个方法时，就创建一个新的受保护的独立空间(一个线程有自己独立的一个栈空间，每个方法调用对应着一个栈帧)；
• 方法的局部变量是独立的，不会相互影响；
• 如果方法中使用的是引用类型变量，就会共享该引用类型的数据，比如数组；
• 递归必须向退出递归的条件逼近，否则就是无限递归，出现 StackOverflowError；
• 当一个方法执行完毕，或者遇到return，就会返回，遵守谁调用，就将结果返回给谁，同时当方法执行完毕或者返回时，该方法也就执行完毕；

迷宫回溯

迷宫回溯问题，寻找最短路径可以通过改变策略，将每个策略都经过的路保存在集合中，最后看哪个集合最小即最小路径。

public class MyTest {

    public static void main(String[] args) {
        Mazeback mazeback = new Mazeback();

        int[][] map = mazeback.createMap();
        mazeback.list(map);

        System.out.println("自动寻找路线：");

        mazeback.setWay(map, 1, 1);
        mazeback.list(map);
    }

}


class Mazeback {

    // 创建地图
    public int[][] createMap() {
        // 地图
        int[][] map = new int[7][8];

        for (int i = 0; i < 7; i++) {
            map[i][0] = 1;
            map[i][7] = 1;
            map[6][i] = 1;
            map[0][i] = 1;
        }
        map[3][1] = 1;
        map[3][2] = 1;
        return map;
    }

    // 遍历地图
    public void list(int[][] map) {
        for (int i = 0; i < map.length; i++) {
            for (int j = 0; j < map[i].length; j++) {
                System.out.print(map[i][j] + "");
            }
            System.out.println();
        }
    }

    // 寻找路径
    // 1：墙；2：通路，3：死路
    public boolean setWay(int[][] map, int row, int column) {
        if (map[5][6] == 2) {
            return true;
        }
        if (map[row][column] == 0) {

            // 先假设是通路
            map[row][column] = 2;

            // 寻找路径顺序：下，右，上，左
            if (setWay(map, row + 1, column)) {
                return true;
            } else if (setWay(map, row, column + 1)) {
                return true;
            } else if (setWay(map, row - 1, column)) {
                return true;
            } else if (setWay(map, row, column - 1)) {
                return true;
            } else {
                // 当标记为3时，说明是死路走不通
                map[row][column] = 3;
                return false;
            }
        }
        return false;
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75

八皇后问题

八皇后问题，是一个古老而著名的问题，是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848 年提出：在 8 × 8 格的国际象棋上摆放八个皇后，使其不能互相攻击， 即： 任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。

八皇后问题共92中解法

public class MyTest {

    public static void main(String[] args) {
        EightQueens eightQueens = new EightQueens();
        eightQueens.exec(0);
    }

}


class EightQueens {

    private int[] arr;

    private int max;

    public EightQueens() {
        this.max = 8;
        this.arr = new int[max];
    }


    // 算法
    public void exec(int position) {
        // 如果当前位置等于max说明解法成立，需要回溯
        if (position == max) {
            print();
            return;
        }
        for (int i = 0; i < max; i++) {
            arr[position] = i;
            if (check(position)){
                exec(position + 1);
            }
        }
    }


    // 判断皇后位置是否冲突
    private boolean check(int position) {
        for (int j = 0; j < position; j++) {
            // 判断是否在同一列或在同一斜线上
            if (arr[position] == arr[j] || Math.abs(position - j) == Math.abs(arr[position] - arr[j])) {
               return false;
            }
        }
        return true;
    }


    // 打印数组
    private void print() {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + "");
        }
        System.out.println();
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

排序算法

排序也称排序算法，是将一组数据，依指定的顺序进行排列的过程。

排序算法分类：

• 内部排序：指将需要处理的所有数据都加载到内部存储器(内存)中进行排序；
• 外部排序法：数据量过大，无法全部加载到内存中，需要借助外部存储(文件等)进行排序；

常见内排序算法复杂度比较

名词解释：

• n：数据规模
• k："桶"的个数
• In-place：占用常数内存，不占用额外内存
• Out-place：占用额外内存
• 稳定性：排序后两个相等键值的顺序和排序之前它们的顺序相同，不稳定性则相反
• 时间复杂度：一个算法执行所耗费的时间
• 空间复杂度：运行完一个程序所需内存的大小

冒泡排序

冒泡排序的基本思想是：通过对待排序序列从前向后（从下标较小的元素开始），依次比较相邻元素的值，若发现逆序（当前值大于比较的值）则交换，使值较大的元素逐渐从前移向后部，就像水底下的气泡一样逐渐向上冒。

优化：因为排序的过程中， 各元素不断接近自己的位置，如果一趟比较下来没有进行过交换，就说明序列有序，因此要在排序过程中设置一个标志 flag 判断元素是否进行过交换。 从而减少不必要的比较。

class BubbleSorting {

    public int[] sort(int[] data) {
        int len = data.length - 1;
        int tmp;
        boolean flag = false;

        for (int i = 0; i <len; i++){
            for (int j = 0; j < len - i; j++) {
                // 将当前值与next值进行比较，如果当前值大于next值则交换两者之间的位置
                if (data[j] > data[j+1]){
                    flag = true;
                    tmp = data[j];
                    data[j] = data[j+1];
                    data[j+1] = tmp;
                }
            }

            // 加入标志为进行判断，如果整个循环下啦都没有交换位置，说明该数组是有序的，所以直接退出循环
            if (!flag){
                break;
            }else {
                flag = false;
            }
        }
        return data;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

选择排序

选择式排序也属于内部排序法，是从欲排序的数据中，按指定的规则选出某一元素，再依规定交换位置后达到排序的目的。

首先在未排序序列中找到最小元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小元素，然后放到排序序列末尾。以此类推，直到所有元素均排序完毕。

class SelectSorting{

    public int[] sort(int[] data) {
        for (int i = 0; i < data.length; i++){

            int min = i;

            for (int j = i+1; j < data.length; j++) {
                // 如果next值大于当前值，则记录该值和该值的位置，等全部比较完毕后，将最大的一个与数据的末尾进行替换
                if (data[i] > data[j]){
                    min = j;
                }
            }

            // 将每次循环中的最小的值，调整到最前面
            if (min != i){
                int tmp = data[i];
                data[i] = data[min];
                data[min] = tmp;
            }
        }
        return data;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

插入排序

插入排序（Insertion Sorting） 的基本思想是：把 n 个待排序的元素看成为一个有序表和一个无序表;

开始时有序表中只包含一个元素，无序表中包含有 n-1 个元素，排序过程中每次从无序表中取出第一个元素，把它的排序码依次与有序表元素的排序码进行比较， 将它插入到有序表中的适当位置，使之成为新的有序表。

对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

class InsertSorting{

    public int[] sort(int[] data) {
        for (int i = 1; i < data.length; i++){
            // 如果当前要插入的值 data[i] > 有序队列中最后一个，则将其直接插入到最后一个
            if (data[i] > data[i - 1]){
                continue;
            }

            int tmp = data[i];
            int index = i - 1;
            // 如果当前位置的值【tmp】小于 上一个位置的值【data[index]】说明当前值需要插入到有序队列中
            while (index >= 0 && tmp < data[index]){
                data[index + 1] = data[index];
                index--;
            }
            data[index + 1] = tmp;
        }
        return data;
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

希尔排序

希尔排序是希尔（Donald Shell） 于1959年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序。

希尔排序按照增量将数组进行分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

class ShellSorting{

    // 希尔排序，交换法
    public void sortSwap(int[] data){
        int size = data.length;
        int tmp = 0;

        // 将数据分组，分组数量：data.length/2
        for (int gap = size >> 1; gap > 0; gap >>= 1){

            for (int i = gap; i < size; i++) {
                // 遍历每组中的元素
                for (int j = i - gap; j >= 0; j -= gap) {
                    // 将每组中的元素进行排序（交换元素）
                    if (data[j] > data[j + gap]){
                        tmp = data[j];
                        data[j] = data[j+gap];
                        data[j+gap] = tmp;
                    }
                }
            }
        }
    }

    // 插入法，融入 插入排序 思想
    public void sort(int[] data){
        int size = data.length;
        int tmp = 0;

        // 将数据分组，分组数量：data.length/2
        for (int gap = size >> 1; gap > 0; gap >>= 1) {
            for (int i = gap; i < size; i++) {

                tmp = data[i];
                int index = i;

                // 如果当前位置的值【tmp】小于 上一个位置的值【data[index]】说明当前值需要插入到有序队列中
                while (index - gap >= 0 && tmp < data[index - gap]){
                    data[index] = data[index - gap];
                    index -= gap;
                }
                data[index] = tmp;
            }
        }
    }
    
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

快速排序

快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序n个项目要 Ο(nlogn) 次比较。在最坏状况下则需要 Ο(n2) 次比较，但这种状况并不常见。事实上，快速排序通常明显比其他 Ο(nlogn) 算法更快，因为它的内部循环可以在大部分的架构上很有效率地被实现出来。

快速排序又是一种分而治之思想在排序算法上的典型应用。本质上来看，快速排序应该算是在冒泡排序基础上的递归分治法。快速排序思路：

• 选定pivot基准数
• 将大于pivot基准数放在基准数右边
• 将小于pivot基准数放在基准数左边

class QuickSorting {

    public void sort(int[] data, int l, int r) {

        // 如果开始的位置大于等于结束的位置则不用进行比较直接退出
        if (l >= r){
            return;
        }

        int left = l;
        int right = r;

        // 基准数值，将小于该数值的放在该数字的左边，大于该数值的放在右边
        int pivot = data[left];

        while (left < right) {

            // 从右向左开始比较，如果此数大于等于基准数则将right索引向前移动，否则，将该值覆盖到对应的 data[left] 中
            while (left < right && data[right] >= pivot) {
                --right;
            }
            data[left] = data[right];

            // 从左向右开始比较，如果此数小于等于基准数则将left索引向后移动，否则，将该值覆盖到对应的 data[right] 中
            while (left < right && data[left] <= pivot) {
                ++left;
            }
            data[right] = data[left];
        }

        // 此时left与right指向重合的位置为基准所在的位置，需要将该位置覆盖掉为基准的值
        data[left] = pivot;

        // 递归排序
        sort(data, l, left);
        sort(data, right+1,r);
    }
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

归并排序

归并排序是利用归并的思想实现的排序方法， 该算法采用经典的分治（divide-and-conquer）策略；分治法将问题分成一些小的问题然后递归求解， 而治的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之。

归并排序算法思路：采用分治算法思想，首先将序列使用递归进行拆分，然后进行合并；合并思路，将两个有序队列中的元素分别按顺序进行比较，将结果保存在一个临时数组中，最后将临时数组合并到最后的队列中。

class MergeSorting {

    // 递归拆分算法
    public void divide(int[] arr, int start, int end, int[] tmpArr) {
        if (start >= end) {
            return;
        }
        int mid = (start + end) >> 1;

        // 分别向左向右递归
        divide(arr, start, mid, tmpArr);
        divide(arr, mid + 1, end, tmpArr);

        // 拆分一次合并一次
        merge(arr, start, mid, end, tmpArr);

    }

    // 合并算法
    public void merge(int[] arr, int start, int mid, int end, int[] tmpArr) {
        int leftIndex = start;
        int rightIndex = mid + 1;
        int tmpArrIndex = 0;

        // 判断是否超出范围
        while (leftIndex <= mid && rightIndex <= end) {

            // 将两组数据进行比较，按照从小到大的顺序将两组数据填入 tmpArr 中
            if (arr[leftIndex] <= arr[rightIndex]) {
                tmpArr[tmpArrIndex] = arr[leftIndex];
                ++leftIndex;
            } else {
                tmpArr[tmpArrIndex] = arr[rightIndex];
                ++rightIndex;
            }
            ++tmpArrIndex;
        }

        // 判断两组数据是否还有剩余，如果有剩余数据，则直接将数据追加到 tmpArr 数组后边
        while (leftIndex <= mid) {
            tmpArr[tmpArrIndex] = arr[leftIndex];
            ++leftIndex;
            ++tmpArrIndex;
        }

        while (rightIndex <= end) {
            tmpArr[tmpArrIndex] = arr[rightIndex];
            ++rightIndex;
            ++tmpArrIndex;
        }

        // 将两组数据进行合并
        tmpArrIndex = 0;
        int tmpLeftIndex = leftIndex;
        while (tmpLeftIndex <= end) {
            arr[tmpLeftIndex] = tmpArr[tmpArrIndex];
            ++tmpLeftIndex;
            ++tmpArrIndex;
        }
    }
    
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

基数排序

基数排序是 1887 年赫尔曼·何乐礼发明的。基数排序属于“分配式排序”，又称“桶子法”或 bin sort，顾名思义，它是通过键值的各个位的值，将要排序的元素分配至某些“桶”中，达到排序的作用,基数排序法是属于稳定性的排序， 基数排序法的是效率高的稳定性排序法。

基数排序是桶排序的扩展，它是这样实现的： 将所有待比较数值统一为同样的数位长度，数位较短的数前面补零；然后， 从最低位开始， 依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。

class BucketSorting {

    public void sort(int[] arr) {
        // 求数组中最大数的长度
        int maxNum = arr[0];
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] > maxNum) {
                maxNum = arr[i];
            }
        }
        int maxNumLen = String.valueOf(maxNum).length();

        // 桶，用于保存数据
        int[][] buckets = new int[10][arr.length];

        // 存放每个桶的保存数据的索引
        int[] bucketElementIndex = new int[10];

        // 将数组中的元素 按照 个、十、百、千 …… 的顺序依次放入桶中
        for (int i = 0, n = 1; i < maxNumLen; i++, n *= 10) {

            // 遍历二维数组
            for (int j = 0; j < arr.length; j++) {
                // 计算放入的桶的下标
                int index = arr[j] / n % 10;
                buckets[index][bucketElementIndex[index]] = arr[j];
                bucketElementIndex[index]++;
            }

            // 从桶中依次取出元素并放入原数组中
            int index = 0;
            for (int f = 0; f < bucketElementIndex.length; f++) {
                // 判断桶中是否保存数据
                if (bucketElementIndex[f] == 0) {
                    continue;
                }
                for (int h = 0; h < bucketElementIndex[f]; h++) {
                    arr[index] = buckets[f][h];
                    index++;
                }
                bucketElementIndex[f] = 0;
            }
        }

    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

堆排序

堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，它的最坏、最好、平均时间复杂度均为O(nlogn)，它也是不稳定排序。

堆排序的基本思想是：将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了。

大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列；
小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列；

class HeapSorting {

    public void sort(int[] arr) {
        // 计算树中的叶子结点位置
        int leafNode = (arr.length >> 1) - 1;

        // 构建大顶堆，此处需要注意 i >= 0 需要算根结点
        for (int i = leafNode; i >= 0; i--) {
            buildMaxHeap(arr, i, arr.length);
        }

        // 构建大顶堆后，将根元素与树中的最后一个进行交换，再循环构建大顶堆
        int tmp;
        for (int i = arr.length - 1; i > 0; i--) {
            tmp = arr[i];
            arr[i] = arr[0];
            arr[0] = tmp;
            buildMaxHeap(arr, 0, i);
        }
    }

    /**
     * 堆排序核心代码 构建大顶堆
     *
     * @param arr 需要调整的数组
     * @param i   非叶子结点的索引位置
     * @param len 每次调整的长度
     */
    public void buildMaxHeap(int[] arr, int i, int len) {
        // 保存非叶子结点的位置如果该结点的值小于子结点的值，则需要进行交换
        int tmp = arr[i];

        // 从上至下，从左至右 遍历. 从第一个左子结点开始遍历
        for (int n = (i << 1) + 1; n < len; n = (n << 1) + 1) {
            // 如果左子结点 < 右结点，则需要将 n 指向右结点，即后移
            if (n + 1 < len && arr[n] < arr[n + 1]) {
                n++;
            }
            // 当前非叶子结点 < 当前子结点
            if (arr[n] > tmp) {
                // 将当前非叶子结点指向叶子结点
                arr[i] = arr[n];
                // 将i指向当前叶子结点，待最后将其变为 非叶子结点的值 即tmp的值
                i = n;
            } else {
                break;
            }
        }
        // 与前面互相呼应
        arr[i] = tmp;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

查找算法

线性查找

线性查找又称顺序查找，是一种最简单的查找方法，它的基本思想是从第一个记录开始，逐个比较记录的关键字，直到和给定的K值相等，则查找成功；若比较结果与文件中n个记录的关键字都不等，则查找失败。

class LinearSearch{

    public int search(int[] arr, int value){
        for (int i = 0; i < arr.length; i++){
            if (arr[i] == value) {
                return i;
            }
        }
        return - 1;
    }

}
1
2
3
4
5
6
7
8
9
10
11
12

二分查找

二分查找也称折半查找，它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。

二分查找算法的前提，数组必须是有序数组，如果没有有序列表，请使用排序算法对列表进行排序。

递归实现二分查找

class BinarySearch {

    // 使用二分查找时，arr必须为有序列表
    public int search(int start, int end, int[] arr, int value) {
        // 在 {@param arr} 中 没有查到 {@param value}
        if (start > end || value > arr[end] || value < arr[start]) {
            return -1;
        }

        // 获取中间值，用于分割列表
        int mid = (start + end) >> 1;
        int midVal = arr[mid];

        // 如果 查找的值< 中间值，说明该值可能在mid的左边
        if (value < midVal) {
            return search(start, mid - 1, arr, value);
        }

        // 相反如果 查找的值 > 中间值，说明该值可能在mid的右边
        if (value > midVal) {
            return search(mid + 1, end, arr, value);
        }

        // 使用递归不停的向下细分，当 value == arr[mid] 时 返回该值，说明此时已经找到了
        return mid;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

非递归实现二分查找

public class BinarySearchDemo {
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        System.out.println(new BinarySearch().search(arr, 3));
    }
}

class BinarySearch {

    // 使用二分查找时，arr必须为有序列表
    public int search(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;
        while (left <= right) {
            int mid = (left + right) >> 1;
            if (arr[mid] == target) {
                return mid;
            }
            // 如果目标值小于中间值则向左边找，反之向右边找
            if (target < arr[mid]) {
                right = mid - 1;
            }

            if (target > arr[mid]) {
                left = mid + 1;
            }
        }
        return -1;
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

插值查找

插值查找算法类似于二分查找，与二分查找不同的是插值查找每次从自适应 mid 处开始查找，而不是像二分查找那样每次都从中间开始找。

注意：对于数据量较大，关键字分布比较均匀（最好是线性分布）的查找表来说，采用插值查找，速度较快；对于关键字分布不均匀的情况下，该方法不一定比二分查找要好。

class InsertValueSearch {

    // 与二分查找基本相同，只是查找 mid 值发生了变动
    public int search(int start, int end, int[] arr, int value) {
        // 在 {@param arr} 中 没有查到 {@param value}
        if (start > end || value > arr[end] || value < arr[start]) {
            return -1;
        }

        int mid = start + (value - arr[start]) / (arr[end] - arr[start]) * (end - start);
        int midVal = arr[mid];

        if (value < midVal) {
            return search(start, mid - 1, arr, value);
        }

        if (value > midVal) {
            return search(mid + 1, end, arr, value);
        }
        return mid;
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

斐波那契查找

斐波那契查找是基于【黄金分割】的二分查找。即在斐波那契队列中，将二分查找中的分割点替换为黄金分割点，来查找。

黄金分割是指将整体一分为二，较大部分与整体部分的比值等于较小部分与较大部分的比值，其 比值 约为 0.618。这个比例被公认为是最能引起美感的 比例，因此被称为黄金分割。

斐波那契查找特点：

• 平均性能「斐波那契查找」好于「二分查找」；
• 「斐波那契查找」计算 mid 的时候 使用加减法而不是除法，会微弱提升效率；

class FibonacciSearch{
    // lookupTable,需要传入斐波那契数列,例如：{1,1,2,3,5,8,13,21,34,55};
    public static int search(int[] lookupTable,int[] f,int target){

        int low = 0;
        int high = lookupTable.length - 1;

        // k 是 Fibonacci 分割数组下标
        int k = 0;
        int middle = 0;

        while (f[k] < high){
            k ++;
        }

        //利用 java 工具类构造 f[k] 长度的查找表，解决原有查找表元素不够的问题
        int[] temp = Arrays.copyOf(lookupTable,f[k]);
        while (low <= high){
            middle = low + f[k - 1];
            if (target < lookupTable[middle]){
                high = middle -1;
                k --;
            }else if (target > lookupTable[middle]){
                low = middle + 1;
                k -= 2;
            }else{
                return Math.min(middle,high);
            }
        }
        return -1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

哈夫曼编码

赫夫曼编码也翻译为哈夫曼编码(Huffman Coding)，又称霍夫曼编码，是一种编码方式，属于一种程序算法。

哈夫曼编码是哈夫曼树在电讯通信中的经典的应用之一。哈夫曼编码广泛地用于数据文件压缩。其压缩率通常在20%～90%之间。哈夫曼码是可变字长编码的一种。Huffman于1952年提出一种编码方法，称之为最佳编码。

定长编码与变长编码，以字符串like like为例：

• 定长编码：

1. 将上述字符串转换对应的ASCII： 108 105 107 101 32 108 105 107 101
2. ASCII转换为二进制：01101100 01101001 01101011 01100101 00100000 01101100 01101001 01101011 01100101
   
   

• 变长编码：

1. 统计上述字符串出现的各字符出现的次数：l：2 i：2 k：2 e：2 ：1
2. 按照各个字符出现的次数进行编码，原则是出现次数越多的，则编码越小：0=l 1=i 10=k 11=e 100=
3. 最终转换为变长编码为：011011100011011

上述的变长编码 011011100011011 在解码的时候会出现多意现象，比如当匹配到数字1，是把1解成i还是按照10来进行解码。因为这种现象的存在，所以在进行变长编码时，编码要符合前缀编码。

字符的编码都不能是其他字符编码的前缀，符合此要求的编码叫做前缀编码， 即不能匹配到重复的编码。

构建哈夫曼编码思路：

1. 统计字节数组中各个数据的权重,即字符出现的次数；
2. 将统计好的字符出现的次数，构建成哈夫曼树；
3. 根据上面创建的哈夫曼树获得每个数值对应的可变长编码值，规定结点的左边为0 ，右边为1；
4. 以每个数值新的编码重新对字符数组进行编码，即可得到赫夫曼编码后的值；

假如一段信息里只有A，B，C，D，E，F这6个字符，他们出现的次数依次是2次，3次，7次，9次，18次，25次，最终构建成哈夫曼编树为下图所示：

得到哈夫曼编码：

A=11100 B=11101 C=1111 D=110 E=10 F=0
1

利用哈夫曼编码，压缩解压文件：

public class HuffmanCodeTest {

    public static void main(String[] args) {

        // 测试压缩文件
        String srcFile = "/Users/whitepure/Desktop/1.png";
        String dstFile = "/Users/whitepure/Desktop/1.zip";

        zipFile(srcFile, dstFile);
        System.out.println("压缩文件成功");

        // 测试解压文件
        srcFile = "/Users/whitepure/Desktop/1.zip";
        dstFile = "/Users/whitepure/Desktop/1copy.png";
        unZipFile(srcFile, dstFile);
        System.out.println("解压成功!");
    }


    // 将一个文件进行压缩
    public static void zipFile(String srcFile, String dstFile) {
        // 创建输出流
        OutputStream os = null;
        ObjectOutputStream oos = null;
        // 创建文件的输入流
        FileInputStream is = null;
        try {
            // 创建文件的输入流
            is = new FileInputStream(srcFile);
            // 创建一个和源文件大小一样的byte[]
            byte[] b = new byte[is.available()];
            // 读取文件
            is.read(b);
            HuffmanCode huffmanCode = new HuffmanCode();
            // 直接对源文件压缩
            byte[] huffmanBytes = huffmanCode.encode(b);
            // 创建文件的输出流, 存放压缩文件
            os = new FileOutputStream(dstFile);
            // 创建一个和文件输出流关联的ObjectOutputStream
            oos = new ObjectOutputStream(os);
            // 把 赫夫曼编码后的字节数组写入压缩文件
            oos.writeObject(huffmanBytes); // 我们是把
            // 这里我们以对象流的方式写入 赫夫曼编码，是为了以后我们恢复源文件时使用
            // 注意一定要把赫夫曼编码 写入压缩文件
            oos.writeObject(huffmanCode.getHuffmanCodes());

        } catch (Exception e) {
            // TODO: handle exception
            System.out.println(e.getMessage());
        } finally {
            try {
                is.close();
                oos.close();
                os.close();
            } catch (Exception e) {
                // TODO: handle exception
                System.out.println(e.getMessage());
            }
        }

    }


    // 完成对压缩文件的解压
    public static void unZipFile(String zipFile, String dstFile) {

        // 定义文件输入流
        InputStream is = null;
        // 定义一个对象输入流
        ObjectInputStream ois = null;
        // 定义文件的输出流
        OutputStream os = null;
        try {
            // 创建文件输入流
            is = new FileInputStream(zipFile);
            // 创建一个和 is关联的对象输入流
            ois = new ObjectInputStream(is);
            // 读取byte数组 huffmanBytes
            byte[] huffmanBytes = (byte[]) ois.readObject();
            // 读取赫夫曼编码表
            Map<Byte, String> huffmanCodes = (Map<Byte, String>) ois.readObject();
            HuffmanCode huffmanCode = new HuffmanCode();
            // 解码
            byte[] bytes = huffmanCode.decode(huffmanCodes, huffmanBytes);
            // 将bytes 数组写入到目标文件
            os = new FileOutputStream(dstFile);
            // 写数据到 dstFile 文件
            os.write(bytes);
        } catch (Exception e) {
            // TODO: handle exception
            System.out.println(e.getMessage());
        } finally {

            try {
                os.close();
                ois.close();
                is.close();
            } catch (Exception e2) {
                // TODO: handle exception
                System.out.println(e2.getMessage());
            }

        }
    }
}

class HuffmanCode {

    private final Map<Byte, String> huffmanCodes = new HashMap<>();

    public Map<Byte, String> getHuffmanCodes() {
        return huffmanCodes;
    }

    // 生成 huffman 编码 压缩
    public byte[] encode(byte[] bytes) {
        List<Node> nodes = buildHuffmanNodes(bytes);
        Node huffmanTreeRoot = buildHuffmanTree(nodes);
        Map<Byte, String> huffmanCodes = buildHuffmanCodeTab(huffmanTreeRoot);
        return zip(bytes, huffmanCodes);
    }

    // 将 huffman编码 解码 解压缩
    public byte[] decode(Map<Byte, String> huffmanCodes, byte[] huffmanBytes) {
        StringBuilder stringBuilder = new StringBuilder();

        // 将byte数组转成二进制的字符串
        for (int i = 0; i < huffmanBytes.length - 1; i++) {
            byte b = huffmanBytes[i];
            String strToAppend = byteToBitString(b);
            // 判断是不是最后一个字节
            boolean isLastByte = (i == huffmanBytes.length - 2);
            if (isLastByte) {
                // 得到最后一个字节的有效位数
                byte validBits = huffmanBytes[huffmanBytes.length - 1];
                strToAppend = strToAppend.substring(0, validBits);
            }
            stringBuilder.append(strToAppend);
        }

        // 把字符串按照指定的赫夫曼编码进行解码
        // 把赫夫曼编码表进行调换，因为反向查询 a->100 100->a
        Map<String, Byte> map = new HashMap<>();
        huffmanCodes.forEach((key, value) -> map.put(value, key));

        // 创建要给集合，存放byte
        List<Byte> list = new ArrayList<>();
        // i 可以理解成就是索引,扫描 stringBuilder
        for (int i = 0; i < stringBuilder.length(); ) {
            int count = 1;
            boolean flag = true;
            Byte b = null;

            while (flag) {
                // 递增的取出 key
                String key = stringBuilder.substring(i, i + count);
                b = map.get(key);
                if (b == null) {
                    // 没有匹配到
                    count++;
                } else {
                    // 匹配到
                    flag = false;
                }
            }
            list.add(b);
            i += count;
        }
        byte[] b = new byte[list.size()];
        IntStream.range(0, b.length).forEach(i -> b[i] = list.get(i));
        return b;
    }

    // 计算字符串中每个字符出现的次数
    private List<Node> buildHuffmanNodes(byte[] bytes) {
        ArrayList<Node> nodes = new ArrayList<>();

        // 利用map记录集合中元素出现的次数
        Map<Byte, Integer> counts = new HashMap<>();
        for (byte b : bytes) {
            counts.merge(b, 1, Integer::sum);
        }

        // 把每一个键值对转成一个Node 对象，并加入到nodes集合
        counts.forEach((key, value) -> nodes.add(new Node(key, value)));
        return nodes;
    }

    // 构建Huffman树
    private Node buildHuffmanTree(List<Node> nodes) {
        while (nodes.size() > 1) {
            // 排序, 从小到大
            Collections.sort(nodes);
            // 取出第一颗最小的二叉树
            Node leftNode = nodes.get(0);
            // 取出第二颗最小的二叉树
            Node rightNode = nodes.get(1);
            // 创建一颗新的二叉树,它的根节点 没有data, 只有权值
            Node parent = new Node(null, leftNode.weight + rightNode.weight);
            parent.left = leftNode;
            parent.right = rightNode;

            // 将已经处理的两颗二叉树从nodes删除
            nodes.remove(leftNode);
            nodes.remove(rightNode);
            // 将新的二叉树，加入到nodes
            nodes.add(parent);
        }
        // nodes 最后的结点，就是赫夫曼树的根结点
        return nodes.get(0);
    }

    // 重载 getCodes
    private Map<Byte, String> buildHuffmanCodeTab(Node root) {
        if (root == null) {
            return null;
        }
        // 处理root的左子树
        buildHuffmanCodeTab(root.left, "0", new StringBuilder());
        // 处理root的右子树
        buildHuffmanCodeTab(root.right, "1", new StringBuilder());
        return huffmanCodes;
    }

    // 获取huffman编码表
    private void buildHuffmanCodeTab(Node node, String code, StringBuilder stringBuilder) {
        StringBuilder curNodeCode = new StringBuilder(stringBuilder);
        curNodeCode.append(code);
        if (node == null) {
            return;
        }
        // 判断当前node 是叶子结点还是非叶子结点
        if (node.data == null) { // 非叶子结点
            // 向左递归
            buildHuffmanCodeTab(node.left, "0", curNodeCode);
            // 向右递归
            buildHuffmanCodeTab(node.right, "1", curNodeCode);
        } else {
            // 表示找到某个叶子结点的最后
            huffmanCodes.put(node.data, curNodeCode.toString());
        }
    }

    // 压缩传入字节（将传入字符串转成字节类型）将待压缩字节转换为字节数组
    private byte[] zip(byte[] bytes, Map<Byte, String> huffmanCodes) {
        // 利用 huffmanCodes 将 bytes 转成 赫夫曼编码对应的字符串
        StringBuilder stringBuilder = new StringBuilder();
        // 遍历bytes 数组
        for (byte b : bytes) {
            stringBuilder.append(huffmanCodes.get(b));
        }

        // 统计返回 byte[] huffmanCodeBytes 长度
        int len;
        // 等同于 int len = (stringBuilder.length() + 7) / 8;
        byte countToEight = (byte) (stringBuilder.length() & 7);
        if (countToEight == 0) {
            len = stringBuilder.length() >> 3;
        } else {
            len = (stringBuilder.length() >> 3) + 1;
            // 后面补零
            for (int i = countToEight; i < 8; i++) {
                stringBuilder.append("0");
            }
        }

        // 创建 存储压缩后的 byte数组，huffmanCodeBytes[len]记录赫夫曼编码最后一个字节的有效位数
        byte[] huffmanCodeBytes = new byte[len + 1];
        huffmanCodeBytes[len] = countToEight;
        int index = 0;
        // 因为是每8位对应一个byte,所以步长 +8
        for (int i = 0; i < stringBuilder.length(); i += 8) {
            String strByte;
            strByte = stringBuilder.substring(i, i + 8);
            // 将strByte 转成一个byte,放入到 huffmanCodeBytes
            huffmanCodeBytes[index] = (byte) Integer.parseInt(strByte, 2);
            index++;
        }
        return huffmanCodeBytes;
    }

    // 将 byte 转换为对应的字符串
    private String byteToBitString(byte b) {
        int temp = b;
        // 如果是正数我们需要将高位补零
        temp |= 0x100;
        // 转换为二进制字符串，正数：高位补 0 即可，然后截取低八位即可；负数直接截取低八位即可
        // 负数在计算机内存储的是补码，补码转原码：先 -1 ，再取反
        String binaryStr = Integer.toBinaryString(temp);
        return binaryStr.substring(binaryStr.length() - 8);
    }

}

class Node implements Comparable<Node> {
    Byte data;
    int weight;
    Node left;
    Node right;

    public Node(Byte data, int weight) {
        this.data = data;
        this.weight = weight;
    }

    @Override
    public int compareTo(Node o) {
        // 从小到大排序
        return this.weight - o.weight;
    }

    public String toString() {
        return "Node [data = " + data + " weight=" + weight + "]";
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315

分治算法

分治法是一种很重要的算法。字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。这个技巧是很多高效算法的基础，如排序算法(快速排序，归并排序)，傅立叶变换(快速傅立叶变换)……

分治法的设计思想是：将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。

使用分治算饭解决汉诺塔问题

汉诺塔（又称河内塔）问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。

public class HanoiTowerDemo {
    public static void main(String[] args) {
        HanoiTower hanoiTower = new HanoiTower();
        hanoiTower.hanoiTower(3, 'A', 'B', 'C');
    }
}

class HanoiTower {

    public void hanoiTower(int n, char a, char b, char c) {
        if (n <= 0) {
            return;
        }
        if (n == 1) {
            System.out.println(a + "->" + c);
            return;
        }
        // 将a塔上面除了底盘外的所有盘移动到b塔
        hanoiTower(n - 1, a, c, b);

        // 将a塔遗留的底盘移动到c塔
        System.out.println(a + "->" + c);

        // 将b塔上面的所有盘移动到c塔
        hanoiTower(n - 1, b, a, c);
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

动态规划算法

动态规划(Dynamic Programming)算法的核心思想是：将大问题划分为小问题进行解决，从而一步步获取最优解的处理算法。

动态规划算法与分治算法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。 ( 即下一个子阶段的求解是建立在上一个子阶段的解的基础上，进行进一步的求解 )

关于动态规划最经典的问题当属背包问题。

背包问题主要是指一个给定容量的背包、若干具有一定价值和重量的物品，如何选择物品放入背包使物品的价值最大。其中又分01背包和完全背包(完全背包指的是：每种物品都有无限件可用)这里的问题属于01背包，即每个物品最多放一个。而无限背包可以转化为01背包。
| 物品 | 重量 | 价格 |
|-----|-----|-----|
| 吉他(G) | 1 | 1500 |
| 音响(S) | 4 | 3000 |
| 电脑(L) | 3 | 2000 |

public class KnapsackProblemDemo {
    public static void main(String[] args) {
        KnapsackProblem knapsackProblem = new KnapsackProblem();
        System.out.println(knapsackProblem.knapsackProblem());
    }
}

class KnapsackProblem {

    public int knapsackProblem() {
        // 物品的重量
        int[] w = {1, 4, 3};
        // 物品的价值
        int[] val = {1500, 3000, 2000};
        // 背包的容量
        int m = 4;
        // 物品的个数
        int n = val.length;
        // 物品规划表
        int[][] v = new int[n + 1][m + 1];

        // 将v[][] 第一列和第一行重置为0
        for (int i = 0; i < v.length; i++) {
            v[i][0] = 0;
        }
        for (int i = 0; i < v[0].length; i++) {
            v[0][i] = 0;
        }

        // 处理 生成物品价格表
        for (int i = 1; i < v.length; i++) {
            for (int j = 1; j < v[0].length; j++) {
                // 如果当前商品的重量 是否能写入当前表格中
                if (w[i - 1] > j) {
                    v[i][j] = v[i - 1][j];
                } else {
                    v[i][j] = Math.max(v[i - 1][j], val[i - 1] + v[i - 1][j - w[i - 1]]);
                }
            }
        }

        // 处理完后 v[][] 表中数值最大的就是最后的结果
        int max = 0;
        for (int[] ints : v) {
            System.out.println(Arrays.toString(ints));
            for (int anInt : ints) {
                if (anInt > max) {
                    max = anInt;
                }
            }
        }
        return max;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

KMP算法

KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt提出的，因此人们称它为克努特—莫里斯—普拉特操作（简称KMP算法）。KMP算法的核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个next()函数实现，函数本身包含了模式串的局部匹配信息。KMP算法的时间复杂度O(m+n)。

• 常规算法匹配字符串

  

  从主串的起始位置（或指定位置）开始与模式串的第一个字符比较，若相等，则继续逐个比较后续字符；否则从主串的下一个字符再重新和模式串的字符比较。依次类推，直到模式串成功匹配，返回主串中第一次出现模式串字符的位置，或者模式串匹配不成功，这里约定返回-1。

• KMP算法匹配字符串

  

  主要就是改进了暴力匹配中i回溯的操作，KMP算法中当一趟匹配过程中出现字符比较不等时，不直接回溯i，而是利用已经得到的“部分匹配”的结果将模式串向右移动（j-next[j-1]）的距离。

  public class KMPDemo {
      public static void main(String[] args) {
          KMP kmp = new KMP();
          String str1 = "BBC ABCDAB ABCDABCDABDE";
          String str2 = "ABCDABD";
          int[] next = kmp.getMatchTab(str2);
          System.out.println(Arrays.toString(next));
          System.out.println(kmp.kmpSearch(str1, str2, next));
      }
  }
  
  class KMP {
  
      // 获取KMP 部分匹配表
      public int[] getMatchTab(String dest) {
          int[] result = new int[dest.length()];
          // 部分匹配表第一个值始终为0
          result[0] = 0;
          for (int i = 1, j = 0; i < result.length; i++) {
              // KMP 核心（特点，公式）
              while (j > 0 && dest.charAt(i) != dest.charAt(j)) {
                  j = result[j - 1];
              }
              if (dest.charAt(j) == dest.charAt(i)) {
                  j++;
              }
              result[i] = j;
          }
          return result;
      }
  
      /**
       * KMP查找算法
       *
       * @param str1 原字符串
       * @param str2 子字符串
       * @param next 部分匹配表
       * @return 匹配到字符串的第一个索引位置
       */
      public int kmpSearch(String str1, String str2, int[] next) {
          for (int i = 0, j = 0; i < str1.length(); i++) {
              while (j > 0 && str1.charAt(i) != str2.charAt(j)) {
                  j = next[j - 1];
              }
              if (str1.charAt(i) == str2.charAt(j)) {
                  j++;
              }
              if (j == str2.length()) {
                  return i - j + 1;
              }
          }
          return -1;
      }
  
  }
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  25
  26
  27
  28
  29
  30
  31
  32
  33
  34
  35
  36
  37
  38
  39
  40
  41
  42
  43
  44
  45
  46
  47
  48
  49
  50
  51
  52
  53
  54
  55

贪心算法

贪心算法又称贪婪算法，是指在对问题进行求解时，在每一步选择中都采取最好或者最优(即最有利)的选择，从而希望能够导致结果是最好或者最优的算法。贪婪算法所得到的结果不一定是最优的结果(有时候会是最优解)，但是都是相对近似(接近)最优解的结果。

举例，假设存在下面需要付费的广播台，以及广播台信号可以覆盖的地区。 如何选择最少的广播台，让所有的地区都可以接收到信号。

public class GreedyAlgorithmDemo {
    public static void main(String[] args) {
        HashMap<String, HashSet<String>> broadcasts = new HashMap<>();
        HashSet<String> hashSet1 = new HashSet<>();
        hashSet1.add("北京");
        hashSet1.add("上海");
        hashSet1.add("天津");

        HashSet<String> hashSet2 = new HashSet<>();
        hashSet2.add("广州");
        hashSet2.add("北京");
        hashSet2.add("深圳");

        HashSet<String> hashSet3 = new HashSet<>();
        hashSet3.add("成都");
        hashSet3.add("上海");
        hashSet3.add("杭州");

        HashSet<String> hashSet4 = new HashSet<>();
        hashSet4.add("上海");
        hashSet4.add("天津");

        HashSet<String> hashSet5 = new HashSet<>();
        hashSet5.add("杭州");
        hashSet5.add("大连");

        broadcasts.put("K1", hashSet1);
        broadcasts.put("K2", hashSet2);
        broadcasts.put("K3", hashSet3);
        broadcasts.put("K4", hashSet4);
        broadcasts.put("K5", hashSet5);

        // allAreas 存放所有的地区
        HashSet<String> allAreas = new HashSet<>();
        for (Map.Entry<String, HashSet<String>> broadcast : broadcasts.entrySet()) {
            allAreas.addAll(broadcast.getValue());
        }

        System.out.println(new GreedyAlgorithm().getRadioByGreedyAlgorithm(allAreas, broadcasts));
    }
}

class GreedyAlgorithm {

    public List<String> getRadioByGreedyAlgorithm(HashSet<String> allAreas, HashMap<String, HashSet<String>> broadcasts) {
        // 存放选择的电台
        ArrayList<String> selects = new ArrayList<>();

        // 存放每次选择最优的电台
        String maxKey = null;

        // 临时集合 从 broadcasts 中选出能覆盖的电台，即存放 allAreas 与 broadcasts 的交集
        HashSet<String> tmpSet = new HashSet<>();

        while (allAreas.size() > 0) {
            // 每次需要清空
            maxKey = null;

            for (String key : broadcasts.keySet()) {
                tmpSet.clear();
                tmpSet.addAll(broadcasts.get(key));

                // 计算覆盖的电台 并赋值给tmpSet
                tmpSet.retainAll(allAreas);

                // 此处进行比较 体现贪心算法
                if (tmpSet.size() > 0 && (maxKey == null || tmpSet.size() > broadcasts.get(maxKey).size())) {
                    maxKey = key;
                }
            }

            // 每进行一次循环最后需要移除选中的maxKey对应的电台城市
            if (maxKey != null) {
                selects.add(maxKey);
                allAreas.removeAll(broadcasts.get(maxKey));
            }
        }
        return selects;
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81

普里姆算法

普里姆算法（Prim算法），图论中的一种算法，可在加权连通图里搜索最小生成树。意即由此算法搜索到的边子集所构成的树中，不但包括了连通图里的所有顶点，且其所有边的权值之和亦为最小。

最小生成树：给定一个带权的无向连通图，如何选取一棵生成树，使树上所有边上权的总和为最小，这叫最小生成树。简称MST。
求最小生成树的算法主要是普里姆算法和克鲁斯卡尔算法。

• 普里姆算法：O(n^2),适合稠密图（边多的图）
• 克鲁斯卡尔算法:O,适合稀疏图（边少的图）

普利姆(Prim)算法求最小生成树，也就是在包含n个顶点的连通图中，找出只有(n-1)条边包含所有n个顶点的连通子图，也就是所谓的极小连通子图。

public class PrimAlgorithmDemo {
    public static void main(String[] args) {
        char[] data = new char[]{'A', 'B', 'C', 'D', 'E', 'F', 'G'};
        int vertex = data.length;
        //邻接矩阵的关系使用二维数组表示,10000这个大数，表示两个点不联通
        int[][] weight = new int[][]{
                {10000, 5, 7, 10000, 10000, 10000, 2},
                {5, 10000, 10000, 9, 10000, 10000, 3},
                {7, 10000, 10000, 10000, 8, 10000, 10000},
                {10000, 9, 10000, 10000, 10000, 4, 10000},
                {10000, 10000, 8, 10000, 10000, 5, 4},
                {10000, 10000, 10000, 4, 5, 10000, 6},
                {2, 3, 10000, 10000, 4, 6, 10000}
        };

        MGraph graph = new MGraph(vertex);
        PrimAlgorithm minTree = new PrimAlgorithm();
        graph.create(graph, vertex, data, weight);
        graph.show(graph);
        minTree.prim(graph, 0);
    }
}

class PrimAlgorithm {

    /**
     * 最小生成树问题 prim算法
     *
     * @param graph  图对象
     * @param vertex 开始的顶点
     */
    public void prim(MGraph graph, int vertex) {
        int i = 0, j = 0;
        int row = -1, column = -1;
        // 存放已经访问过的顶点
        int[] visited = new int[graph.vertex];
        // 用1表示两点之间已经连接， 0表示未连接
        visited[vertex] = 1;
        int minWeight = 10000;

        for (int k = 1; k < graph.vertex; k++){
            // 比较两点之间的权值，每次都获取最小的权值
            for (i = 0; i < graph.vertex; i++) {
                for(j = 0; j < graph.vertex; j++){
                    if (visited[i] == 1 && visited[j] == 0 && graph.weight[i][j] < minWeight){
                        minWeight = graph.weight[i][j];
                        row = i;
                        column = j;
                    }
                }
            }
            System.out.println("边<" + graph.data[row] + "," + graph.data[column] + "> 权值:" + minWeight);
            // 将顶点标记为已经访问过
            visited[column] = 1;

            // 每次比较完后需要将minWeight重置
            minWeight = 10000;
        }

    }

}

class MGraph {
    int vertex;
    char[] data;
    int[][] weight;

    public MGraph(int vertex) {
        this.vertex = vertex;
        data = new char[vertex];
        weight = new int[vertex][vertex];
    }

    /**
     * 创建图的邻接矩阵
     *
     * @param graph  图对象
     * @param vertex 图对应的顶点个数
     * @param data   图的各个顶点的值
     * @param weight 图的邻接矩阵
     */
    public void create(MGraph graph, int vertex, char[] data, int[][] weight) {
        int i, j;
        for (i = 0; i < vertex; i++) {
            graph.data[i] = data[i];
            for (j = 0; j < vertex; j++) {
                graph.weight[i][j] = weight[i][j];
            }
        }
    }

    // 显示图的邻接矩阵
    public void show(MGraph graph) {
        for (int[] link : graph.weight) {
            System.out.println(Arrays.toString(link));
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99

克鲁斯卡尔算法

克鲁斯卡尔算法是求连通网的最小生成树的另一种方法。基本思想是， 将所有边按照权值的大小进行升序排序，然后从小到大一一判断，条件为：如果这个边不会与之前选择的所有边组成回路，就可以作为最小生成树的一部分；反之，舍去。 直到具有 n 个顶点的连通网筛选出来 n-1（n为顶点个数） 条边为止。

判断是否构成回路: 当每次需要将一条边添加到最小生成树时，判断该边的两个顶点终点是否相同，相同就会构成回路。

关于终点的说明：就是将所有顶点按照从小到大的顺序排列好之后；某个顶点的终点就是与它连通的最大顶点。 就是将所有顶点按照从小到大的顺序排列好之后；某个顶点的终点就是与它连通的最大顶点。

举例

• 首先ABCDEFG这7个顶点，在顶点集合中是按照顺序存放的；
• 第一次选择的是EF，毫无疑问这一条边的终点是F；
• 第二次选择的CD的终点D；
• 第三次选择的DE，终点是F，因为此时D和E相连，D又和F相连，所以D的终点是F。而且，因为C和D是相连的，D和E相连，E和F也是相连的，所以C的终点此时变成了F。也就是说，当选择了EF、CD、DE这三条边后，C、D、E的终点都是F。当然F的终点也是F，因为F还没和后面的哪个顶点连接。
• 本来接下来应该选择CE的，但是由于C和E的终点都是F，所以就会形成回路；

public class KruskalCaseDemo {

    //使用 INF 表示两个顶点不能连通
    private static final int INF = Integer.MAX_VALUE;

    public static void main(String[] args) {
        char[] vertexs = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
        int matrix[][] = {
                /*A*//*B*//*C*//*D*//*E*//*F*//*G*/
                /*A*/ {0, 12, INF, INF, INF, 16, 14},
                /*B*/ {12, 0, 10, INF, INF, 7, INF},
                /*C*/ {INF, 10, 0, 3, 5, 6, INF},
                /*D*/ {INF, INF, 3, 0, 4, INF, INF},
                /*E*/ {INF, INF, 5, 4, 0, 2, 8},
                /*F*/ {16, 7, 6, INF, 2, 0, 9},
                /*G*/ {14, INF, INF, INF, 8, 9, 0}};

        KruskalCase kruskalCase = new KruskalCase(vertexs, matrix);
        kruskalCase.print();
        kruskalCase.kruskal();
    }

}

class KruskalCase {
    //使用 INF 表示两个顶点不能连通
    private static final int INF = Integer.MAX_VALUE;
    private int edgeNum; //边的个数
    private char[] vertexs; //顶点数组
    private int[][] matrix; //邻接矩阵

    // 构造器
    public KruskalCase(char[] vertexs, int[][] matrix) {
        // 初始化顶点数和边的个数
        int vlen = vertexs.length;

        // 初始化顶点, 复制拷贝的方式
        this.vertexs = new char[vlen];
        for (int i = 0; i < vertexs.length; i++) {
            this.vertexs[i] = vertexs[i];
        }

        // 初始化边, 使用的是复制拷贝的方式
        this.matrix = new int[vlen][vlen];
        for (int i = 0; i < vlen; i++) {
            for (int j = 0; j < vlen; j++) {
                this.matrix[i][j] = matrix[i][j];
            }
        }
        // 统计边的条数
        for (int i = 0; i < vlen; i++) {
            for (int j = i + 1; j < vlen; j++) {
                if (this.matrix[i][j] != INF) {
                    edgeNum++;
                }
            }
        }
    }

    public void print() {
        System.out.println("邻接矩阵为: \n");
        for (int i = 0; i < vertexs.length; i++) {
            for (int j = 0; j < vertexs.length; j++) {
                System.out.printf("%12d", matrix[i][j]);
            }
            System.out.println();
        }
    }

    /**
     * 功能：对边进行排序处理, 冒泡排序
     *
     * @param edges 边的集合
     */
    private void sortEdges(EdgeData[] edges) {
        for (int i = 0; i < edges.length - 1; i++) {
            for (int j = 0; j < edges.length - 1 - i; j++) {
                if (edges[j].weight > edges[j + 1].weight) {
                    EdgeData tmp = edges[j];
                    edges[j] = edges[j + 1];
                    edges[j + 1] = tmp;
                }
            }
        }
    }

    /**
     * @param ch 顶点的值，比如'A','B'
     * @return 返回ch顶点对应的下标，如果找不到，返回-1
     */
    private int getPosition(char ch) {
        for (int i = 0; i < vertexs.length; i++) {
            if (vertexs[i] == ch) {
                return i;
            }
        }
        // 找不到,返回-1
        return -1;
    }

    /**
     * 功能: 获取图中边，放到EData[] 数组中，后面我们需要遍历该数组
     * 是通过matrix 邻接矩阵来获取
     * EData[] 形式 [['A','B', 12], ['B','F',7], .....]
     */
    private EdgeData[] getEdges() {
        int index = 0;
        EdgeData[] edges = new EdgeData[edgeNum];
        for (int i = 0; i < vertexs.length; i++) {
            for (int j = i + 1; j < vertexs.length; j++) {
                if (matrix[i][j] != INF) {
                    edges[index++] = new EdgeData(vertexs[i], vertexs[j], matrix[i][j]);
                }
            }
        }
        return edges;
    }

    /**
     * 功能: 获取下标为i的顶点的终点, 用于后面判断两个顶点的终点是否相同
     *
     * @param ends ： 数组就是记录了各个顶点对应的终点是哪个,ends 数组是在遍历过程中，逐步形成
     * @param i    : 表示传入的顶点对应的下标
     * @return 返回的就是 下标为i的这个顶点对应的终点的下标, 一会回头还有来理解
     */
    private int getEnd(int[] ends, int i) { // i = 4 [0,0,0,0,5,0,0,0,0,0,0,0]
        while (ends[i] != 0) {
            i = ends[i];
        }
        return i;
    }

    public void kruskal() {
        int index = 0;
        // 用于保存"已有最小生成树" 中的每个顶点在最小生成树中的终点
        int[] ends = new int[vertexs.length];
        // 创建结果数组, 保存最后的最小生成树
        EdgeData[] rets = new EdgeData[edgeNum];

        // 获取图中 所有的边的集合 ， 一共有12边
        EdgeData[] edges = getEdges();

        // 按照边的权值大小进行排序(从小到大)
        sortEdges(edges);

        // 遍历edges 数组，将边添加到最小生成树中时，判断是准备加入的边否形成了回路，如果没有，就加入 rets, 否则不能加入
        for (int i = 0; i < edgeNum; i++) {
            // 获取到第i条边的第一个顶点(起点)
            int point1 = getPosition(edges[i].start);
            // 获取到第i条边的第2个顶点
            int point2 = getPosition(edges[i].end);
            // 获取p1这个顶点在已有最小生成树中的终点
            int endPointOfPoint1 = getEnd(ends, point1);
            // 获取p2这个顶点在已有最小生成树中的终点
            int endPointOfPoint2 = getEnd(ends, point2);

            // 克鲁斯卡尔核心点：判断是否构成回路
            if (endPointOfPoint1 != endPointOfPoint2) {
                // 假设没有构成回路
                // 将该边上终点上的值赋值给起点位置的值
                ends[endPointOfPoint1] = endPointOfPoint2;
                // 将该边保存起来
                rets[index++] = edges[i];
            }
        }
        System.out.println("最小生成树为");
        for (int i = 0; i < index; i++) {
            System.out.println(rets[i]);
        }
    }

}

class EdgeData {
    char start; // 边的一个点
    char end; // 边的另外一个点
    int weight; // 边的权值

    public EdgeData(char start, char end, int weight) {
        this.start = start;
        this.end = end;
        this.weight = weight;
    }

    // 重写toString, 便于输出边信息
    @Override
    public String toString() {
        return "EData [<" + start + ", " + end + ">= " + weight + "]";
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190

迪杰斯特拉算法

迪杰斯特拉算法是典型最短路径算法，用于计算一个结点到其他结点的最短路径。迪杰斯特拉算法是基于贪心思想，从起始位置触发，每次寻找与起点位置距离且未访问过的顶点，以该顶点作为中间结点，更新从起点到其他顶点的距离，直到全部顶点都作为了中间结点，并完成了路径更新，算法结束。 它的主要特点是以起始点为中心向外层层扩展，即图的广度优先搜索思想，直到扩展到终点为止。

视频讲解：bilibili

public class DijkstraAlgorithmDemo {
    public static void main(String[] args) {
        char[] vertex = { 'A', 'B', 'C', 'D', 'E', 'F', 'G' };
        int[][] matrix = new int[vertex.length][vertex.length];
        // 表示不可以连接
        final int N = 65535;
        matrix[0] = new int[] { N, 5, 7, N, N, N, 2 };
        matrix[1] = new int[] { 5, N, N, 9, N, N, 3 };
        matrix[2] = new int[] { 7, N, N, N, 8, N, N };
        matrix[3] = new int[] { N, 9, N, N, N, 4, N };
        matrix[4] = new int[] { N, N, 8, N, N, 5, 4 };
        matrix[5] = new int[] { N, N, N, 4, 5, N, 6 };
        matrix[6] = new int[] { 2, 3, N, N, 4, 6, N };
        Graph graph = new Graph(vertex, matrix);
        graph.showGraph();
        graph.dsj(6);
    }
}

class Graph {
    private char[] vertex;
    private int[][] matrix;
    private VisitedVertex vv;

    // 构造器
    public Graph(char[] vertex, int[][] matrix) {
        this.vertex = vertex;
        this.matrix = matrix;
    }

    // 显示结果
    public void showDijkstra() {
        vv.showArrays();
    }

    // 显示图
    public void showGraph() {
        for (int[] link : matrix) {
            for (int i : link) {
                System.out.printf("%8d", i);
            }
            System.out.println();
        }
    }

    /**
     * 迪杰斯特拉算法实现
     * @param index 表示出发顶点对应的下标
     */
    public void dsj(int index) {
        vv = new VisitedVertex(vertex.length, index);
        update(index);
        vv.showArrays();
        for (int j = 1; j < vertex.length; j++) {
            index = vv.findNextStartPoint();
            update(index);
            vv.showArrays();
        }
    }

    // 更新index下标顶点到周围顶点的距离和周围顶点的前驱顶点,
    private void update(int index) {
        int len = 0;
        // 根据遍历我们的邻接矩阵的 matrix[index]行
        for (int j = 0; j < matrix[index].length; j++) {
            // len 含义是 : 出发顶点到index顶点的距离 + 从index顶点到j顶点的距离的和
            len = vv.getDis(index) + matrix[index][j];
            // 如果j顶点没有被访问过，并且 len 小于出发顶点到j顶点的距离，就需要更新
            if (!vv.isVisited(j) && len < vv.getDis(j)) {
                vv.updatePre(j, index);
                vv.updateDis(j, len);
            }
        }
    }
}

class VisitedVertex {
    public int[] alreadyArr;
    public int[] preVisited;
    public int[] dis;

    /**
     *
     * @param length :表示顶点的个数
     * @param index: 出发顶点对应的下标, 比如G顶点，下标就是6
     */
    public VisitedVertex(int length, int index) {
        this.alreadyArr = new int[length];
        this.preVisited = new int[length];
        this.dis = new int[length];
        // 初始化 dis数组
        Arrays.fill(dis, 65535);
        this.dis[index] = 0;
        this.alreadyArr[index] = 1;

    }

    /**
     * 功能: 判断index顶点是否被访问过
     * @return 如果访问过，就返回true, 否则访问false
     */
    public boolean isVisited(int index) {
        return alreadyArr[index] == 1;
    }

    /**
     * 功能: 更新出发顶点到index顶点的距离
     */
    public void updateDis(int index, int len) {
        dis[index] = len;
    }

    /**
     * 功能: 更新pre这个顶点的前驱顶点为index顶点
     */
    public void updatePre(int pre, int index) {
        preVisited[pre] = index;
    }

    /**
     * 功能:返回出发顶点到index顶点的距离
     */
    public int getDis(int index) {
        return dis[index];
    }


    /**
     * 继续选择并返回新的访问顶点， 比如这里的G 完后，就是 A点作为新的访问顶点(注意不是出发顶点)
     */
    public int findNextStartPoint() {
        int min = 65535, index = 0;
        for (int i = 0; i < alreadyArr.length; i++) {
            if (alreadyArr[i] == 0 && dis[i] < min) {
                min = dis[i];
                index = i;
            }
        }
        // 更新 index 顶点被访问过
        alreadyArr[index] = 1;
        return index;
    }

    //显示最后的结果
    public void showArrays() {
        System.out.println("核心数组的值如下：");
        for (int i : alreadyArr) {
            System.out.print(i + " ");
        }
        System.out.println();
        for (int i : dis) {
            System.out.print(i + " ");
        }
        System.out.println();
        for (int i : preVisited) {
            System.out.print(i + " ");
        }
        System.out.println();

        char[] vertex = { 'A', 'B', 'C', 'D', 'E', 'F', 'G' };
        int count = 0;
        for (int i : dis) {
            if (i != 65535) {
                System.out.print(vertex[count] + "(" + i + ") ");
            } else {
                System.out.print("N ");
            }
            count++;
        }
        System.out.println();
        System.out.println();
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174

弗洛伊德算法

弗洛伊德算法又称为插点法，是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法，与迪杰斯特拉算法类似。

迪杰斯特拉算法对比弗洛伊德算法：
迪杰斯特拉算法通过选定的被访问顶点，求出从出发访问顶点到其他顶点的最短路径；弗洛伊德算法中每一个顶点都是出发访问点，所以需要将每一个顶点看做被访问顶点，求出从每一个顶点到其他顶点的最短路径。

• 弗洛伊德算法计算图中各个顶点之间的最短路径
• 迪杰斯特拉算法用于计算图中某一个顶点到其他顶点的最短路径

public class FloydAlgorithmDemo {
    public static void main(String[] args) {
        char[] vertex = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
        int[][] matrix = new int[vertex.length][vertex.length];
        final int N = 65535;
        matrix[0] = new int[]{0, 5, 7, N, N, N, 2};
        matrix[1] = new int[]{5, 0, N, 9, N, N, 3};
        matrix[2] = new int[]{7, N, 0, N, 8, N, N};
        matrix[3] = new int[]{N, 9, N, 0, N, 4, N};
        matrix[4] = new int[]{N, N, 8, N, 0, 5, 4};
        matrix[5] = new int[]{N, N, N, 4, 5, 0, 6};
        matrix[6] = new int[]{2, 3, N, N, 4, 6, 0};

        FloydGraph graph = new FloydGraph(vertex, vertex.length, matrix);
        graph.floyd();
        graph.show();
    }
}

class FloydGraph {
    private char[] vertex;
    private int[][] pre;
    private int[][] dis;

    public FloydGraph(char[] vertex, int length, int[][] dis) {
        this.vertex = vertex;
        this.dis = dis;
        this.pre = new int[length][length];
        for (int i = 0; i < length; i++) {
            Arrays.fill(pre[i], i);
        }
    }

    public void show() {
        for (int k = 0; k < dis.length; k++) {
            // 先将pre数组输出的一行
            for (int i = 0; i < dis.length; i++) {
                System.out.print(vertex[pre[k][i]] + " ");
            }
            System.out.println();
            // 输出dis数组的一行数据
            for (int i = 0; i < dis.length; i++) {
                System.out.print("(" + vertex[k] + "到" + vertex[i] + "的最短路径是" + dis[k][i] + ") ");
            }
            System.out.println();
            System.out.println();
        }
    }

    public void floyd(){
        int len;
        for (int m = 0; m < dis.length; m++) {
            for (int a = 0; a < dis.length; a++) {
                for (int b = 0; b < dis.length; b++) {
                    len = dis[a][m] + dis[m][b];
                    if (len < dis[a][b]){
                        dis[a][b] = len;
                        pre[a][b] = pre[m][b];
                    }
                }
            }
        }
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

马踏棋盘算法

马踏棋盘算法也被称为骑士周游问题。将马随机放在国际象棋的8×8棋盘0～7的某个方格中，马按走棋规则(马走日字)进行移动。要求每个方格只进入一次，走遍棋盘上全部64个方格。

马踏棋盘问题实际上是图的深度优先搜索(DFS)的应用。

public class HouseChessBoardDemo {
    public static void main(String[] args) {
        HouseChessBoard houseChessBoard = new HouseChessBoard(7, 7, 2, 4);
        houseChessBoard.showChessBoard();
    }
}

class HouseChessBoard {

    /**
     * 表示棋盘的列
     */
    private int x;
    /**
     * 表示棋盘的行
     */
    private int y;
    /**
     * 创建一个数组，标记棋盘的各个位置是否被访问过，true表示已经访问过
     */
    private boolean visited[];
    /**
     * 使用一个属性，标记是否棋盘的所有位置都被访问 如果为true,表示成功
     */
    private boolean finished;

    private int[][] chessboard;

    public HouseChessBoard(int x, int y, int row, int column) {
        this.x = x;
        this.y = y;
        this.visited = new boolean[x * y];
        this.chessboard = new int[x][y];
        traversalChess(this.chessboard, row-1, column-1, 1);
    }

    public void showChessBoard(){
        for (int[] ints : this.chessboard) {
            for (int anInt : ints) {
                System.out.print(anInt + "\t");
            }
            System.out.println();
        }
    }

    public void traversalChess(int[][] chessboard, int row, int column, int step) {
        chessboard[row][column] = step;

        // 将当前位置标记为已经访问过
        visited[row * x + column] = true;

        // 获取当前位置的下一个可走通的位置的集合
        ArrayList<Point> nextPos = getNext(new Point(column, row));

        sort(nextPos);

        while (nextPos.size() > 0) {
            // 获取当前可走通的位置
            Point current = nextPos.remove(0);
            // 判断当前该点是否被访问过,如果没有被访问过则继续向下访问
            if (!visited[current.y * x + current.x]) {
                traversalChess(chessboard, current.y, current.x, step + 1);
            }
        }

        // 当遍历完可走的位置集合后，如果发现该路不通，则进行回溯，否则标记为完成
        if (step < x * y && !finished) {
            chessboard[row][column] = 0;
            visited[row * x + column] = false;
        } else {
            finished = true;
        }
    }

    // 将可走通路根据回溯次数进行从小到大排序
    public void sort(ArrayList<Point> points){
        points.sort((o1, o2) -> {
            int next1 = getNext(o1).size();
            int next2 = getNext(o2).size();
            return next1 - next2;
        });
    }



    // 获取下一个可走的位置
    public ArrayList<Point> getNext(Point current) {
        ArrayList<Point> ps = new ArrayList<Point>();
        Point p1 = new Point();
        // 表示马儿可以走5这个位置
        if ((p1.x = current.x - 2) >= 0 && (p1.y = current.y - 1) >= 0) {
            ps.add(new Point(p1));
        }
        // 判断马儿可以走6这个位置
        if ((p1.x = current.x - 1) >= 0 && (p1.y = current.y - 2) >= 0) {
            ps.add(new Point(p1));
        }
        // 判断马儿可以走7这个位置
        if ((p1.x = current.x + 1) < x && (p1.y = current.y - 2) >= 0) {
            ps.add(new Point(p1));
        }
        // 判断马儿可以走0这个位置
        if ((p1.x = current.x + 2) < x && (p1.y = current.y - 1) >= 0) {
            ps.add(new Point(p1));
        }
        // 判断马儿可以走1这个位置
        if ((p1.x = current.x + 2) < x && (p1.y = current.y + 1) < y) {
            ps.add(new Point(p1));
        }
        // 判断马儿可以走2这个位置
        if ((p1.x = current.x + 1) < x && (p1.y = current.y + 2) < y) {
            ps.add(new Point(p1));
        }
        // 判断马儿可以走3这个位置
        if ((p1.x = current.x - 1) >= 0 && (p1.y = current.y + 2) < y) {
            ps.add(new Point(p1));
        }
        // 判断马儿可以走4这个位置
        if ((p1.x = current.x - 2) >= 0 && (p1.y = current.y + 1) < y) {
            ps.add(new Point(p1));
        }
        return ps;
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125