0xCAFEBABE

talk is cheap show me the code

0%

数据结构与算法大赏(java版)

数据结构+算法=程序

数据结构与算法相辅相成 不可分割

数据结构依赖于算法实现

算法能真实反应反应一个人的编程水平 而不是api的调用水平

算法能反应程序的性能

算法服务于数据结构 优秀的算法课提高数据据结构的性能

对于特定问题 需要使用特定的算法

1 数据结构

数据结构是研究 是计算机存储、组织数据的方式

主要分为两大类

  • 线性结构

    数据元素之间存在一对一的线性关系

    线性结构又分为 顺序表和链表

    顺序表的元素在内存的地址是连续的 链表是不连续的

    线性结构常见的有 数组 队列 链表 栈

  • 非线性结构

    主要包含: 二维数组 多维数组 广义表 树 图

1.1 线性结构

1.1.1 稀疏数组

当数组中大部分元素为0时 或者为同一个值时 可以使用稀疏数组对其进行压缩以节省空间

  • 处理方案

    • 记录数组有几行或几列 有多少相同的值
    • 把具有不同值得元素得行列及值记录在一个小规模的数组中 从而缩小规模 如 nn 的二维数组 可以转化为 3\n的二维数组(记录 行 列 值)
  • 基本思路

    1. 遍历计算二维数组中有效值的个数n
    2. 创建(n+1)*3的稀疏数组 第一行存储原二维数组的行列 有效值个数信息
    3. 再次遍历二维数组将有效值存入稀疏数组
  • demo

    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
    // 稀疏
    int[][] arr = new int[10][10];
    arr[0][0] = 1;
    arr[1][1] = 2;
    arr[2][2] = 3;
    int sum = 0;
    int row = arr.length;
    int col = arr[0].length;
    for(int[] i : arr) {
    for(int j : i) {
    if(j!=0) {
    sum++;
    }
    }
    }
    int[][] sparseArr = new int[sum+1][3];
    // 第一行存行 列 有效元素个数
    sparseArr[0][0] = row;
    sparseArr[0][1] = col;
    sparseArr[0][2] = sum;
    int count = 1;
    for (int i = 0; i < arr.length; i++) {
    for (int j = 0; j < arr[i].length; j++) {
    if(arr[i][j]!=0) {
    sparseArr[count][0] = i;
    sparseArr[count][1] = j;
    sparseArr[count][2] = arr[i][j];
    count++;
    }
    }
    }
    // 数组还原
    int[][] arr = new int[sparseArr[0][0]][sparseArr[0][1]];
    for (int i = 1; i < sparseArr.length; i++) {
    arr[sparseArr[i][0]][sparseArr[i][1]] = sparseArr[i][2];
    }

1.1.2 队列

队列是一种有序列表 可用数组或链表实现

遵循先入先出的原则

需要一个队头front和队尾rear指针 初始值为-1

  • 数组实现

    • 思路

      1. 入队时rear+1 出队时fonrt+1
      2. 当rear = capacity -1 时 队列满
      3. 当rear=front 队列空
      4. 初始rear=front=-1
      5. 环形数组优化:
        • front指向第一个节点
        • rear指向最后一个节点的后一位置 空出一个空间作为约定
        • 当队列满时 (rear+1)%maxSize == front
        • rear == front 队列空
        • 初始front=rear=0
        • 队列中的有效元素个数(rear+maxSize-front)%maxSize
    • demo

      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
      public class ArrayQueue<E>{
      // 头节点
      private int front;
      //尾节点
      private int rear;
      // 数组
      private Node<E>[] arr;
      private int maxSize;
      public ArrayQueue() {
      this(17);
      int a = 1;
      }
      public ArrayQueue(int maxSize) {
      this.maxSize = maxSize;
      arr = new Node[maxSize];
      }
      // 入队
      public boolean enQeueue(E e) {
      if(isFull()) return false;
      Node<E> node = new Node<>(e);
      arr[rear] = node;
      rear = (rear+1) % maxSize;
      return true;
      }
      // 出队
      public E deQueue() {
      if(isEmpty()) return null;

      E e = arr[front].item;
      front = (front+1)%maxSize;
      return e;
      }
      public boolean isFull() {
      return (rear+1)%maxSize==front;
      }

      public int size() {
      return (rear+maxSize-front) % maxSize;
      }
      public boolean isEmpty() {
      return rear == front;
      }
      private static class Node<E>{
      E item;
      Node(E e){
      item =e;
      }
      }
      @Override
      public String toString() {
      // TODO Auto-generated method stub

      StringBuilder builder = new StringBuilder();

      builder.append("[ ");
      for (int i = front; i < front+size(); i++) {
      builder.append(arr[i % maxSize].item+", ");
      }
      builder.append("]");
      return builder.toString();
      }
      }

1.1.3 链表

有序列表 每个元素称为节点 每个节点包含数据域(data)和下一节点的引用(next)

在内存空间中地址不一定连续

分为有头节点 和无头节点

1.1.3.1 单向链表

节点之间单向连接 只能单向查找

节点无法自我删除 必须先找到前一个节点作为辅助

1.1.3.2 双向链表

节点之间双向连接 每个节点含有前一节点和后一节点的引用

支持双向查找

  • 带顺序插入

    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
    public void add(E e, int score) {
    Node<E> node = new Node<>(e, score);
    if(head==null) {
    head = node;
    }else {
    Node<E> cur = head;
    while(cur.next!=null && cur.next.score<score) {
    cur = cur.next;
    }
    if(cur.next==null) {
    if(cur==head) {
    if(head.score>score) {
    node.next = head;
    head.prev = node;
    head =node;
    }else {
    node.prev = head;
    head.next = node;
    }
    }else {
    node.prev = cur;
    cur.next =node;
    }
    }else {
    if(cur==head) {
    if(head.score>score) {
    node.next = head;
    head.prev = node;
    head = node;
    size++;
    return;
    }
    }
    cur = cur.next;
    cur.prev.next = node;
    node.next = cur;
    node.prev = cur.prev;
    cur.prev = node;
    }
    }
    size++;
    }
1.1.3.3 循环链表

头节点与尾节点相连就形成了循环链表

1.1.4 链表面试题

1.1.4.1 求链表倒数第k个节点
  • 思路

    1. 先得到链表总长度length
    2. 算出倒序索引k的正序索引 index (length-k)
    3. 从头遍历到index
  • demo

    1
    2
    3
    4
    5
    6
    7
    8
    9
    public E rget(int rindex) {
    int index = size - rindex;
    if(index<0 || index>size) return null;
    Node<E> cur = head;
    for (int i = 1; i < index; i++) {
    cur = cur.next;
    }
    return cur.item;
    }
1.1.4.2 反转链表
  • 思路

    1. 定义一个节点reversedHead
    2. 从头到尾遍历原来的列表 每遍历一个节点 就将其取出 并插入到链表reversed的最前端
    3. 原来的head.next=reversedHead.next
  • demo

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    public void reverse() {
    if(isEmpty() || size==1) return;
    Node<E> cur = head;
    head = null;
    while(cur!=null) {

    insert(cur.item, 0);
    cur = cur.next;
    }
    }
1.1.4.3 逆序打印链表
  • 思路
    1. 先反转再打印
    2. 利用栈结构 将各个节点压入栈中 然后遍历弹出栈 实现逆序
1.1.4.4 合并两个有序单链表
  • 思路
    1. 将两个链表依次遍历 按排序规则添加到一个新的链表
1.1.4.5 约瑟夫环

n个人围坐一圈 设定编号为k(1<=k<=n)的人开始报数 数到m的那个人出列 下一位又从1开始报数 以此类推 直到所有人出列为止

  • 思路

    1. 环形链表

      • 单向链表

        需要一个辅助变量 指向当前节点的一个节点

      • 双向链表

        无需辅助接点

    2. 数组取模

      通过对数组下标取模来模拟环形链表

  • 环链表版

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    public void josephu(int start, int step, @SuppressWarnings("unchecked") E... args) {
    int count = args.length;
    for(E e: args) {
    add(e);
    }
    Node<E> cur = head;
    // 移动到指定位置
    for (int i = 0; i < start; i++) {
    cur = cur.next;
    }
    while(count>0) {
    // 开始报数 遍历到下一个要被删除的元素
    for (int i = 1; i < step; i++) {
    cur = cur.next;
    }
    System.out.println("========>"+cur.item);
    cur.prev.next = cur.next;
    cur.next.prev = cur.prev;
    cur = cur.next;
    count--;
    }
    head = null;
    }
  • 索引取模版

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    public void josephu(int start, int step, E...args) {
    for (E e:args) {
    add(e);
    }
    Node<E> cur = head;
    start = start % size;
    for (int i = 0; i < start; i++) {
    cur = cur.next;
    }
    while(!isEmpty()) {
    // 每次计算新的链表长度
    int size = size();
    // 计算下一个改删除的元素索引
    start = (start + step -1) % size ;
    E e = delete(start);
    System.out.println("==========>"+e);
    }
    }

1.1.5 栈

栈(stack) 是一种先入后出(FILO)的有序列表

只能在一端操作数据 变化的一段称为栈顶 不变的一端称为栈底 有出栈(pop)和入栈(push)两种操作

应用:

  • 子程序的调用 跳往子程序前 将下一个指令存于堆栈 直到返子程序执行完毕后取出 继续执行
  • 递归调用 除了存储下一个地址之外 也将参数 局部变量加入其中
  • 表达式转换
  • 二叉树的遍历
  • 图的深度优先搜索
  • 数组实现

    1
    2
    3
    4
    5
    6
    7
    public void push(E e) {
    if(top == maxSize-1) return;
    value[++top] = e;
    }
    public E pop() {
    return (E) value[top--];
    }
  • 链表实现

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    public void push(E e) {
    Node<E> node = new Node<>(e);
    node.next = head;
    head = node;
    }
    public E pop() {
    E e = head.item;
    head = head.next;
    return e;
    }
1.1.5.1 栈实现综合计算器 (中缀表达式)

通过栈实现一连串的数学表达式计算

中缀表达式 操作符位于操作数之间

  • 思路

    1. 通过索引 遍历表达式
    2. 如果是数字 放入操作数栈 如果是操作符 放入操作符栈
    3. 如果操作符栈为空直接入栈 如果不为空 需要与栈顶的操作符进行比较 如果当前操作符优先级小于或等于栈顶的操作符 需要将操作数栈中弹出两个数 从操作符栈顶中弹出一个符号进行运算 并将结果放回操作数栈 然后将当前操作符入栈 如果当前操作符优先级大于栈顶的操作符 直接入操作符栈
    4. 当表达式扫描完毕时 按顺序从操作数栈和符号栈取出数和符号 并计算后结果压入栈 最后在数栈中仅存的数字即为运算结果
    5. 优化:
      • 处理多位数时 需要再往后扫描 直到扫描到符号时才入栈
  • demo

    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
    SingleLinkedList<Integer> numStack = new SingleLinkedList<>();
    SingleLinkedList<String> opStack = new SingleLinkedList<>();
    String[] nums = expression.split("[\\+\\-\\*/]");
    String[] ops = expression.split("\\d+");
    ops = Arrays.copyOfRange(ops, 1, ops.length);
    for (int i = 0; i < nums.length; i++) {
    if (i < nums.length - 1) {
    int num = Integer.parseInt(nums[i]);
    String op = ops[i];
    numStack.push(num);
    if (opStack.isEmpty()) {
    opStack.push(op);
    } else {
    String topOp = opStack.peek();
    if (priority(op) <= priority(topOp)) {
    int num1 = numStack.pop();
    int num2 = numStack.pop();
    topOp = opStack.pop();
    int result = result(num1, num2, topOp);
    numStack.push(result);
    opStack.push(op);
    } else {
    opStack.push(op);
    }
    }
    } else {
    // 将最后一个数入栈 操作数数量=操作符数量+1
    numStack.push(Integer.parseInt(nums[i]));
    }
    }
    while(!opStack.isEmpty()) {
    int num1 = numStack.pop();
    int num2 = numStack.pop();
    String op = opStack.pop();
    int result = result(num1, num2, op);
    numStack.push(result);
    }
    return numStack.pop();
1.1.5.2 计算器(前缀表达式)

前缀表达式(又称波兰式) 运算符位于操作数之前

运算符顺序倒转

可解决小括号优先级问题

流程: 从右至左扫描表达式 遇到数字时 弹出栈顶的两个数 用运算符对它们做相应的运算(栈顶元素和次顶元素) 并将结果压入栈 重复上述过程直到表达式最左端 最后运算得出的值即为表达式的结果

1.1.5.3 后缀表达式

又称逆波兰式 运算符位于两个操作数之后

流程: 从左至右扫描表达式 遇到数字时 将数压入栈 遇到运算符时 弹出栈顶的两个数 用运算符进行运算(次顶元素和栈顶元素) 并将结果压入栈 重复上述过程直到表达式最右端 最后运算得出的值即为表达式的结果

  • 逆波兰计算器

    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
    List<String> infix = expressionToList(expression);  // 字符串转列表
    List<String> suffix = infixToSuffix(infix); // 中缀转后缀
    SingleLinkedList<String> stack = new SingleLinkedList<>();
    for(String s : suffix) {
    if(s.matches("\\d+")) {
    stack.push(s);
    }else {
    int num2 = Integer.parseInt(stack.pop());
    int num1 = Integer.parseInt(stack.pop());
    int result = 0;
    switch(s) {
    case "+":
    result = num1+ num2;
    break;
    case "-":
    result = num1 - num2;
    break;
    case "*":
    result = num1 * num2;
    break;
    case "/":
    result = num1 / num2;
    break;
    }
    stack.push(result+"");
    }
    }
    return Integer.parseInt(stack.pop());
  • 中缀转后缀

    1. 初始化两个栈 运算符栈s1与存储中间结果栈s2

    2. 从左至右扫描表达式

    3. 遇到操作数时 将其压入s2

    4. 遇到运算符 比较其与s1栈顶运算符的优先级

      1. 如果s1为空 或栈顶符号为 ( 则直接将此运算符入栈)

      2. 否则 若优先级比栈顶优先级高 也将运算符压入s1

      3. 否则 将s1栈顶的运算符弹出并压入s2中 再次转到4.1与s1中新的栈顶运算符相比较 直到遇到优先级低的才入栈

    5. 遇到括号时

      • 如果是 ( 则直接压入s1
      • 如果是 ) 则依次弹出s1栈顶的运算符 并压入s2 直到遇到 ( 为止 此时将这一对括号丢弃
    6. 重复步骤2至5 直到表达式的最右边

    7. 将s1中剩余的运算符一次弹出并压入s2

    8. 依次弹出s2 结果的逆序即为中缀表达式的后缀表达式

    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
    List<String> infixToSuffix(List<String> expLs){
    SingleLinkedList<String> s1 = new SingleLinkedList<>();
    List<String> s2 = new ArrayList<>(); // 可用列表模拟栈 s2只有添加操作
    for (String item : expLs) {
    // 数字直接入s2
    if(item.charAt(0) >=48 && item.charAt(0) <=57) {
    s2.add(item);
    }else {
    // s1 为空 或栈顶为( 或 操作符为( 直接入栈
    if(s1.isEmpty() || "(".equals(s1.peek()) || "(".equals(item)) {
    s1.push(item);
    }else if(")".equals(item)) {
    while(!"(".equals(s1.peek())) {
    s2.add(s1.pop());
    }
    s1.pop();
    }else {
    // 转移所有优先级大于当前操作符的操作符
    while(!s1.isEmpty() && priority(s1.peek())>=priority(item)) {
    s2.add(s1.pop());
    }
    s1.push(item);
    }
    }
    }
    while(!s1.isEmpty()) {
    s2.add(s1.pop());
    }
    return s2;
    }

1.2 哈希表

通过键值对查找数据 通过散列算法计算出数据的存放索引

常见搭配:

数组+链表

数组+树

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
public class HashTab<K, V> {
private static final int INITIAL_CAPACITY = 16;
private Node<K, V>[] elements;
private int size;
public HashTab() {
this(INITIAL_CAPACITY);
}
@SuppressWarnings("unchecked")
public HashTab(int size) {
this.size = size;
elements = new Node[size];
}
private int hash(K key) {
return key.hashCode() & size-1;
}
public V remove(K key) {
int index = hash(key);
if(elements[index]!=null) {
Node<K, V> node = elements[index];
if(node.key.hashCode() == key.hashCode()) {
V v = node.value;
elements[index] = node.next;
return v;
}else {
while(node.next!=null) {
if(node.next.key.hashCode()==key.hashCode()) {
V value = node.next.value;
node.next = node.next.next;
return value;
}
node = node.next;
}
}
}
return null;
}
@Override
public String toString() {
// TODO Auto-generated method stub
StringBuilder builder = new StringBuilder();
builder.append("{");
for (int i = 0; i < elements.length; i++) {
Node<K, V> node = elements[i];
if(node!=null) {
while(node!=null) {
builder.append(node.key+"="+node.value+", ");
node = node.next;
}
}
}
builder.append("}");
return builder.toString();
}
public void put(K key, V value) {
int index = hash(key);
if(elements[index]==null) {
elements[index] = new Node<>(key, value);
}else {
Node<K, V> node = elements[index];
if(node.key.hashCode() == key.hashCode()) {
node.value = value;
}else {
boolean isExist = false;
while(node.next!=null) {
Node<K, V> cur = node.next;
if(cur.key.hashCode() == key.hashCode()) {
cur.value = value;
isExist = true;
break;
}
node = node.next;
}
if(!isExist) {
node.next = new Node<>(key, value);
}
}
}
}
public V get(K key) {
int index = hash(key);
if(elements[index]!=null) {
Node<K, V> cur = elements[index];
while(cur!=null) {
if(cur.key.hashCode() == key.hashCode()) {
return cur.value;
}
cur = cur.next;
}
}
return null;
}
private static class Node<K, V>{
K key;
V value;
Node<K, V> next;
Node(K key, V value){
this.key = key;
this.value = value;
}
}
}

1.3 二叉树

与链表类似 每个节点含左子节点和右子节点的引用

如果所有的叶子节点都在最后一层 期额节点总数为2^n -1 n为层数 则称为满二叉树

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

常用术语:

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

1.3.1 遍历

二叉树遍历分为前序 后序 中序遍历 取决于 根节点的位置

  • 前序遍历

    1
    2
    3
    4
    5
    6
    7
    8
    9
    void preOrderPrint(Node<E> node) {
    System.out.print(node.item+", ");
    if(node.left!=null) {
    preOrderPrint(node.left);
    }
    if(node.right!=null) {
    preOrderPrint(node.right);
    }
    }
  • 中序遍历

    1
    2
    3
    4
    5
    6
    7
    8
    9
    void midOrderPrint(Node<E> node) {
    if(node.left!=null) {
    midOrderPrint(node.left);
    }
    System.out.print(node.item+", ");
    if(node.right!=null) {
    midOrderPrint(node.right);
    }
    }
  • 后序遍历

    1
    2
    3
    4
    5
    6
    7
    8
    9
    void postOrderPrint(Node<E> node) {
    if(node.left!=null) {
    postOrderPrint(node.left);
    }
    if(node.right!=null) {
    postOrderPrint(node.right);
    }
    System.out.print(node.item+", ");
    }

1.3.2 查找

  • 二分查找

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    E search0(Node<E> node, E e) {
    if(node!=null) {
    if(node.item==e) {
    return e;
    }else {
    if(node.item.compareTo(e)<0) {
    return search0(node.right, e);
    }else {
    return search0(node.left, e);
    }
    }
    }
    return null;
    }
  • 前序查找

  • 后续查找

  • 中序查找

1.3.3 删除

  • 删除子树节点

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    E remove(Node<E> node, E e) {
    if(node.item.compareTo(e)<0) {
    if(node.right!=null) {
    if(node.right.item == e) {
    node.right=null;
    return e;
    }else {
    return remove(node.right, e);
    }
    }
    }else {
    if(node.left!=null) {
    if(node.left.item==e) {
    node.left=null;
    return e;
    }else {
    return remove(node.left, e);
    }
    }
    }
    return null;
    }

1.3.4 顺序二叉树

二叉树与数组可相互转换 由数组转换来的二叉树叫做 顺序二叉树

可用数组模拟顺序二叉树 只考虑完全二叉树

第n个元素的左子节点为2*n+1

第n个元素的右子节点为2*n+2

第n个元素的父节点为(n-1)/2

  • 前序遍历

    1
    2
    3
    4
    5
    6
    7
    8
    9
    void preOrderPrint(int i) {
    System.out.print(arr[i]+", ");
    if(2*i+1<arr.length) {
    preOrderPrint(2*i+1);
    }
    if(2*i+2<arr.length) {
    preOrderPrint(2*i+2);
    }
    }

1.3.5 线索化二叉树

利用空指针 存放某种次序遍历下的前驱和后继节点的指针 这种指针称为线索

加上线的二叉链表称为线索链表 相应的二叉树称为线索二叉树

left节点可能指向左子树(记为0) 也可能指向前驱节点(记为1)

right节点可能指向右子树(0) 也可能指向后继节点(1)

  • 线索化前序

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    void preThreaded(Node<E> node) {
    if(node==null) return;
    if(node.left==null) {
    node.leftType = 1;
    }
    if(prev!=null && prev.right==null && prev!=root) {
    prev.right = node;
    prev.rightType = 1;
    }
    prev = node;
    preThreaded(node.left);
    preThreaded(node.right);
    }
  • 线索化中序

    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
    // 线索化
    void midThreaded(Node<E> node) {
    if(node==null) return;
    midThreaded(node.left);
    // 让左子节点指向前驱节点
    if(node.left==null) {
    node.left = prev;
    node.leftType = 1;
    }
    // 右子节点指向后继节点
    if(prev!=null && prev.right==null) {
    prev.right = node;
    prev.rightType = 1;
    }
    prev = node;
    midThreaded(node.right);
    }
    // 遍历
    void midThreadedPrint() {
    Node<E> node = root;
    System.out.print("[ ");
    while(node!=null) {
    while(node.leftType==0) {
    node = node.left;
    }
    System.out.print(node.item+", ");
    while(node.rightType==1) {
    node = node.right;
    System.out.print(node.item+", ");
    }
    node = node.right;
    }
    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
    // 后序线索化
    void postOrderThreaded(Node<E> node) {
    if(node==null) return;
    postOrderThreaded(node.left);
    postOrderThreaded(node.right);
    if(node.left==null) {
    node.leftType = 1;
    }
    if(prev!=null) {
    prev.right = node;
    prev.rightType = 1;
    }
    prev = node;
    }
    // 线索化遍历
    void postOrderThreadedPrint() {
    Node<E> node = root;
    System.out.print("[ ");
    while(node!=root.right) {
    while(node.leftType==0) {
    node = node.left;
    }
    System.out.print(node.item+", ");
    while(node.rightType==1) {
    node = node.right;
    System.out.print(node.item+", ");
    }
    node = node.right;
    }
    System.out.print("]");
    }

1.3.6 霍夫曼树

给定n个权值作为n个节点 构造一棵二叉树 若该树得带权路径长度达到最小 则成为最优二叉树 称为Huffman Tree

在树中 从一个节点往下可以达到得孩子节点或孙子节点之间的通路 称为路径 乘以每个节点得权得到的结果称为带权路径(wpl)

数据存储在叶子节点

1.3.6.1 构建霍夫曼树

将数组构建为霍夫曼树

基本思路

  1. 从小到大进行排序 将每一个数据当时是一个节点 每个节点可当作一颗二叉树
  2. 取出根节点权值最小的两颗二叉树
  3. 组成一颗新的二叉树 将新的二叉树的根节点的权值设为前面两颗二叉树根节点权值之和
  4. 再将新的二叉树 以节点权值大小再次排序 不断重复 步骤1 2 3 知道数列中所有的数据都被处理
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 <E extends Comparable<E>> HuffmanTree<E> createHuffmanTree(E[] args, int[] weights) {
List<Node<E>> nodes = new ArrayList<>();
for (int i = 0; i < args.length; i++) {
nodes.add(new Node<E>(args[i], weights[i]));
}
while(nodes.size() > 1) {
Collections.sort(nodes);
Node<E> left = nodes.get(0);
Node<E> right = nodes.get(1);
Node<E> parent = new Node<>(null,left.weight + right.weight);
parent.left = left;
parent.right = right;
nodes.remove(left);
nodes.remove(right);
nodes.add(parent);
}
return new HuffmanTree<>(nodes.get(0));
}

1.3.7 二叉排序树

对于任何一个非子叶节点 要求左子节点的值比右子节点的值小 右子节点比当前节点的值大

如果有相同的值 放在左或右子节点

1.3.7.1 删除节点

分三种情况

  1. 删除的节点是叶子节点
  2. 删除的节点含有一个叶子节点
  3. 删除的节点有两个子树节点
    • 先找到目标节点targetNode
    • 再找到父节点parent
    • 从targetNode的右子树找到最小的节点 temp (最左叶子节点) 或从左子树找到最大叶子节点(最右叶子节点)
    • 删除temp
    • targetNode.value = temp
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
E remove(E e) {
if(root==null) return null;
Node<E> targetNode = search0(root, e);
if(targetNode==null) return null;
Node<E> parent = root.item.compareTo(e) ==0 ? null : findParentNode(root, e);
E value = targetNode.item;
//删除的是叶子节点
if(targetNode.left==null && targetNode.right==null && parent!=null) {
if(targetNode==root) {
root =null;
}else if(parent.left==targetNode) {
parent.left = null;
}else {
parent.right = null;
}
// 删除的有两个子节点
}else if(targetNode.left!=null && targetNode.right!=null) {
targetNode.item = removeMin(targetNode.right); // 删除最左子节点
// 删除的有一个子节点
}else {
if(targetNode.left!=null) {
if(targetNode==root) {
root = root.left;
}else if(parent.left == targetNode) {
parent.left = targetNode.left;
}else {
parent.right = targetNode.left;
}
}else{
if(targetNode==root) {
root = root.right;
}else if(parent.left == targetNode) {
parent.left = targetNode.right;
}else {
parent.right = targetNode.right;
}
}
}
return value;
}

1.3.8 平衡二叉树(AVL)

解决二叉排序树可能退化为单链表的问题

一颗空树 或左右两个子树的高度差绝对值不超过1 左右两个子树都是一颗平衡二叉树 主要实现有 红黑树 AVL 替罪羊树 Treap 伸展树等

1.3.8.1 左旋

右子树高度大于左子树时

  1. 创建一个新节点, 值等于当前的根节点的值
  2. 将新节点的左子树设为当前节点的左子树
  3. 将新节点的右子树设为当前节点的右子树的左子树
  4. 将当前节点的值换成右子节点的值
  5. 将当前节点的右子树设为右子树的右子树
  6. 将当前节点的左子树设为新节点
1
2
3
4
5
6
7
8
void leftRotate() {
Node<E> newNode = new Node<>(root.item);
newNode.left = root.left;
newNode.right = root.right.left;
root.item = root.right.item;
root.right = root.right.right;
root.left = newNode;
}
1.3.8.2 右旋

左子树高度大于右子树时

  1. 创建新节点 值等于当前根节点的值
  2. 将新节点的右子树设置为当前节点的右子树
  3. 将新节点的左子树设为当前节点的左子树的右子树
  4. 把当前节点的值换为左子节点的值
  5. 把当前节点的左子树设置成左子树的左子树
  6. 将当前节点的右子树设为新节点
1
2
3
4
5
6
7
8
void rightRotate() {
Node<E> newNode = new Node<>(root.item);
newNode.right = root.right;
newNode.left = root.left.right;
root.item = root.left.item;
root.left = root.left.left;
root.right = newNode;
}
1.3.8.3 双旋

解决特殊情况下左旋和右旋不能平衡的问题

如果达到右旋条件

如果其左子树的的右子树高度大于左子树的左子树的高度

先对其左子树进行左旋

如果达到左旋条件

如果右子树的左子树的高度大于右子树的右子树

先对右子树进行右旋

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 添加新节点后自平衡
if(leftHeight() - rightHeight() >1) {
// 如果根节点的左子节点的右子节点的高度大于左子节点的左子节点 先对左子节点进行左旋
if(root.left!=null && height(root.left.right) > height(root.left.left)) {
leftRotate(root.left);
rightRotate(root);
}else {
rightRotate(root);
}
return;
}
if(rightHeight() - leftHeight() > 1) {
// 如果右子树的左子树大于右子树的右子树高度 先对右子树进行右旋
if(root.right!=null && height(root.right.left) > height(root.right.right)) {
rightRotate(root.right);
leftRotate(root);
}else {
leftRotate(root);
}
}

1.4 多叉树

在面对海量数据时 使用二叉树存储会出现高度太大的问题 使用多叉树可降低高度

多叉树允许一个节点存储多个数据和节点

1.4.1 2-3树

B树的一种

2-3树的所有叶子节点都在同一层

有两个子节点的节点叫二节点 有三个的叫三节点 要求子节点非空即满 任然遵循二叉排序树的规则

插入规则

当一个元素插入到某个节点时

不能满足要求 则需要拆分 先向上拆 如果上层满 则拆本层 拆后

1.4.2 B树

MySql 底层所使用的数据结构

B树的阶 节点最多的子节点个数

搜索: 从根节点开始 对节点内的关键字序列进行二分查找 如果命中则结束 否则进入查询关键字所属的范围的子节点 重复 直到所对应的子节点指针为空 或是叶子节点

关键字集合分布在整棵树中 即叶子节点和非叶子节点都存放数据

搜索性能等价于在关键字全集内做一次二分查找

B+树与B树的改进在于B+树数据存储在叶子节点 将数据分段 更适合文件系统

B*树是B+树的变体 在B+的非根和非叶子节点上增加了指向兄弟节点的指针 空间使用率更高 新节点分配效率较低

1.5 图

节点可以有0个或多个相邻元素 两个节点之间的连接称为边 节点可称作顶点 从一个顶点到另一个顶点的连线称为路径

无向图: 顶点之间的连线没有方向 有方向称为有向图

带权图: 边带有权值的图 也称为网

可用于表示多对多的关系

图有两种表示方式:二维数组(邻接矩阵) 和数组+链表(邻接表)

1.5.1 深度优先搜索

从初始访问点出发 首先访问第一个邻接节点 再以该节点作为初始节点 访问它的第一个邻接节点 以此递归

基本思路:

  1. 访问初始节点 并标记节点v为已访问
  2. 查找节点v的第一个邻接节点w
  3. 若w存在 则继续执行4 如果不存在 则回到第一步 将从v的下一节点继续
  4. 若w未被访问 对w进行深度优先遍历递归 继续步骤123
  5. 查找结点v的w邻接节点的下一邻接节点 转到步骤3
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
void depthFirstSearch() {
// 遍历每个节点
for (int i = 0; i < graph.length; i++) {
if(!visited[i]) {
depthFirstSearch(i);
}
}
}
void depthFirstSearch(int i) {
System.out.print(vertex.get(i)+"=>");
// 将节点标记为已经过
visited[i] = true;
// 获取第一个相邻节点
int neighbor = getFirstNeighbor(i);
while(neighbor>0) {
// 如果该节点未遍历 则以该节点为初始节点进行递归遍历
if(!visited[neighbor]) {
depthFirstSearch(neighbor);
}
// 获取下一相邻节点
neighbor =getNextNeighbor(i, neighbor);
}
}
// 获取第一个相邻节点
int getFirstNeighbor(int i) {
for (int j = 0; j < vertex.size(); j++) {

if(graph[i][j]>0) {
return j;
}
}
return -1;
}
// 获取下一相邻节点
int getNextNeighbor(int a, int b) {
for (int i = b+1; i < vertex.size(); i++) {
if(graph[a][i]>0) {
return i;
}
}
return -1;
}

1.5.2 广度优先搜索

类似分层搜索 广度优先需要使用一个队列以保持访问过的节点的顺序 以便按这个顺序来访问这些节点的邻接节点

步骤:

  1. 访问初始节点v并标记为节点v为以访问
  2. 节点v入队
  3. 当队列非空时 继续执行 否则算法结束
  4. 出队列 获得头节点u
  5. 查找节点u的第一个邻接节点w
  6. 若节点u的邻接节点w不存在 则转到步骤3 否则循环执行以下步骤
    • 若节点w未被访问 则访问节点w并标记为已访问
    • 节点w入队列
    • 查找节点u的继w邻接节点后的下一邻接节点w转到步骤6
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
void broadFirstSearch() {
for (int i = 0; i < vertex.size(); i++) {
if(!visited[i]) {
broadFirstSearch(i);
}
}
}
void broadFirstSearch(int i) {
LinkedList<Integer> queue = new LinkedList<>();
System.out.print(vertex.get(i)+"==>");
visited[i] = true;
int u = 0, w = 0;
queue.addLast(i);
while(!queue.isEmpty()) {
u = queue.removeFirst();
w = getFirstNeighbor(u);
while(w>0) {
if(!visited[w]) {
queue.addLast(w);
System.out.print(vertex.get(w)+"==>");
visited[w] = true;
}
w = getNextNeighbor(u, w);
}
}
}

2 算法

衡量一个算法的效率有两种方法

  1. 事后统计

    运行程序然后计算耗费的时间 不能排除环境的影响

  2. 事前估算

    通过分析算法的时间复杂度判断优秀的算法

    一个算法花费的时间与算法中的语句执行次数成正比例

    一个算法中语句的执行次数称为语句频度或时间频度 记为T(n) 当n趋于无穷大 常数项 低次项 和系数可以忽略

    时间频度的同数量级函数称为时间复杂度 用O(n)表示

    • 平均时间复杂度

      输入到算法的实例均以等概率出现的情况下 该算法的运行时间

    • 最坏时间复杂度

      任何输入实例的运行时间的界限

  3. 常见时间复杂度

    • 常数阶 O(1)
    • 对数阶 O(logn)
    • 线性阶 O(n)
    • 线性对数阶 O(nlogn)
    • 平方阶 O(n²)
    • 立方阶 O(n³)
    • k次方阶 O(n^k)
    • 指数阶 O(2^n)
  4. 空间复杂度

    衡量一个算法运行时所占的空间 n越大占用的空间越大

    从用户体验看 更注重程序的运行速度

2.1 递归

方法调用自己 每次传入不同的变量 有助于解决复杂问题 同时可让代码变得简洁

递归第一个执行的是 末端方法

递归回溯: 当达到退出条件时 会回到上一个方法栈 发生回溯

递归使用规则:

  1. 执行一个方法时 就创建一个受保护的独立空间(栈空间)
  2. 方法的局部变量是独立的 不会相互影响
  3. 递归必须向退出递归的条件逼近 否则会造成栈溢出StackOverFlow
  4. 当方法执行完毕 或遇到return就会返回 遵守谁调用 就将结果返回给谁 同时当方法执行完毕或返回时 该方法执行完毕
  5. 如果方法中使用引用类型的变量 就会共享该引用类型的数据

2.1.1 迷宫问题

二维数组表示迷宫 设有障碍(非元素)

计算小球从迷宫的左上角 走到出口(右下角)的最短路径

寻路策略会影响路径长短

  • 思路
    1. 可通过递归回溯解决
    2. 将未走过的为止标记为0 墙标记为1 已走过的位置标记为2 死路标记为3
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
boolean wander(int[][] map, int i, int j){
if(map[map.length-2][map[0].length-2]==2) {
// 如果经过终点 返回true 结束递归
return true;
}else {
if(map[i][j]==0) {
map[i][j] =2;
// 上 右 下 左
// 0 未经过 1 墙 2 已经过 3 死路
if(wander(map, i-1, j)) {
return true;
}else if(wander(map, i, j+1)) {
return true;
}else if(wander(map, i+1, j)) {
return true;
}else if(wander(map, i, j-1)) {
return true;
}else {
// 如果从该点起四个方向都无路可走 则标记为思路 在此回溯到上一个点
map[i][j] = 3;
return false;
}
}else {
// 如果已经走过 直接返回false 不走回头路
return false;
}
}
}

2.1.2 八皇后问题

在8*8的国际象棋盘上拜访八个皇后 使其互相不能攻击

任意两个皇后不能处于同一行 同一列或同一斜线上

  • 思路
    1. 第一个皇后先放在第一行第一列
    2. 第二个皇后放在第二行第一列 然后判断是否ok 如果不ok 继续放在第二列 第三列 依次把所有的列都放完 直到找到一个合适的位置
    3. 继续递归放剩下的皇后 直到所有皇后找到一个互不冲突的位置 即得到一个正确解
    4. 当得到一个正确解时 此时到达了末尾 触发退出条件 回溯到最后一个皇后 继续尝试剩下的列 当所有列试完 回溯到上一个皇后 以此类推
    5. 回头继续第一个皇后放第二列 继续从步骤2开开始循环
    6. 理论上要创建二维数组 但可通过算法使用一维数组解决 索引表示第几个皇后 每个皇后占据一行 元素表示皇后所在的列 当在同一列时 arr[n] == arr[i] 在同一斜线时 abs(arr[n-i]) == abs(abs(arr[n]) - abs(arr[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
void place(int n) {
if(n==MAX) {
// 找到一个正确解
print();
count++;
return;
}
for (int i = 0; i < MAX; i++) {
arr[n] = i; // 在尝试每一行的所有列
if(judge(n)) {
place(n+1);
}
}
}
boolean judge(int n) {
for (int i = 0; i < n; i++) {
// arr[i]==arr[n]是否处于同一列
// Math.abs(n-i) ==Math.abs(arr[n] - arr[i]) 判断是否处在同一斜线上
if(arr[i]==arr[n] || Math.abs(n-i) ==Math.abs(arr[n] - arr[i]) ) {
return false;
}
}
return true;
}

2.2 排序

排序算法是将一组数据 以指定的顺序进行排列

分为

  • 内部排序

    将数据都加载到内存中进行排序

  • 外部排序

    用于数据量太大 需要借助外部存储进行排序

2.2.1 插入排序

2.2.1.1 直接插入排序

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

1
2
3
4
5
6
7
8
9
10
11
12
for (int i = 1; i < arr.length; i++) {
int insertVal = arr[i];
int insertIndex = i-1;
for (; insertIndex >= 0; insertIndex--) {
if(insertVal<arr[insertIndex]) {
arr[insertIndex+1] = arr[insertIndex];
}else {
break;
}
}
arr[insertIndex+1] = insertVal;
}
2.2.1.2 希尔排序

插入排序的改进版 将下标按步长分组 每组使用插入排序

每次缩小步长直到1

解决普通插入排序 要插入的是较小的数时 后移次数较多的问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int insertValue = 0, insertIndex = 0;
// 每次缩小步长为原来的为二分之一
for (int step = arr.length / 2; step > 0; step /=2) {
for (int i = step; i < arr.length; i+=step) {
insertValue = arr[i];
insertIndex = i - step;
for (; insertIndex >= 0; insertIndex-=step) {
if(insertValue<arr[insertIndex]) {
arr[insertIndex+step] = arr[insertIndex];
}else {
break;
}
}
// 如果发生了移位将元素插入到指定位置
if(insertIndex+step!=i) {
arr[insertIndex+step] = insertValue;
}
}
}

2.2.2 选择排序

2.2.2.1 简单选择排序

第一次从arr[0] - arr[n-1]中选取最小值 与arr[0]交换

第二次从arr[1] - arr[n-1] 中选取最小值与arr[1]交换

以此类推

一共有数组长度-1轮排序

1
2
3
4
5
6
7
8
9
10
11
12
13
for (int i = 0; i < arr.length-1; i++) {
int minIndex = i;
for (int j = i; j < arr.length-1; j++) {
if(arr[minIndex]>arr[j+1]) {
minIndex = j+1;
}
}
if(minIndex!=i) {
int temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
}
}
2.2.2.2 堆排序

利用堆的数据结构完成排序

堆是一种特殊的二叉树

每个节点的值都大于或等于其左右子节点的值 称为大顶堆

每个节点的值都小于或等于其左右子节点的值 称为小顶堆 arr[i]>=arr[2*i+1] && arr[i]>=arr[2*i+2]

大顶堆完成升序 小顶堆完成降序

基本思想:

  1. 将待排序序列构造成一个大顶堆 最大值便是根节点
  2. 将最大值与末尾元素进行交换
  3. 将剩余n-1个元素重新构造成一个大顶堆 并反复执行步骤2 最后得到一个有序序列
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
void heapSort(int arr[]) {
// 构建一个顶堆 数组末尾即为最大/最小元素
for (int i = arr.length / 2 - 1; i >=0; i--) {
adjustHeap(arr, i, arr.length);
}

// 将最大元素依次提到数组末端 并重新调整堆
int temp = 0;
for (int i = arr.length- 1; i >0; i--) {
temp = arr[i];
arr[i] = arr[0];
arr[0] = temp;
adjustHeap(arr, 0, i);
}
}
// 每找到一个最大值时调整堆
void adjustHeap(int[] arr, int i, int length) {
int temp =arr[i];
for (int j = i* 2+1; j < length; j=j*2+1) {
if(j+1 < length && arr[j]<arr[j+1]) {
j++; // 切换到右子节点
}
// 如果左右子节点的其中一个大于父节点 则于父节点交换 否则 无需交换
if(arr[j]>temp) {
arr[i] = arr[j];
i = j;
}else {
break;
}
}
arr[i] = temp;
}

2.2.3 交换排序

2.2.3.1 冒泡排序

通过对待排序序列从前向后遍历 依次比较相邻元素的值 若发现逆序则交换 使值较大的元素逐渐移动到后部 就像水中的气泡逐渐往上冒

一共要进行数组长度-1循环

每次循环的比较次数逐渐减少

优化: 如果下一趟比较么没有进行交换 就说明序列有序 可提前结束

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
boolean flag = false; // 记录是否发生过交换
for (int i = 0; i < arr.length-1; i++) {
for (int j = 0; j < arr.length-1-i; j++) {
if(arr[j]>arr[j+1]) {
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
flag = true;
}
}
if(!flag) {
break;
}else {
flag = false; // 重置标记
}
}
2.2.3.2 快速排序

对冒泡排序的改进

通过一次排序将要排序的数据分割成两部分 以此类推对两部分数据再次分割排序 可递归进行 空间换时间

通过头索引和尾索引相向遍历 以pivot为基准 将大于pivot的值放到右边 小于放到左边

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
void quickSort0(int[] arr, int left, int right) {
int l = left;
int r = right;
int pivot = arr[(right+left)/2];
int temp = 0;
while(l < r) {
while(arr[l]<pivot) {
l++;
}
while(arr[r]>pivot) {
r--;
}
if(l>=r) {
break;
}
temp = arr[l];
arr[l] = arr[r];
arr[r] = temp;
// 如果对方交换过来的是pivot让对方向前一步以跳过pivot
if(arr[l]==pivot) {
r--;
}
if(arr[r]==pivot) {
l++;
}
}
// 当l和r相等时 各向前一步
if(l==r) {
l++;
r--;
}
if(left<r) {
quickSort0(arr, left, r);
}
if(right>l) {
quickSort0(arr, l, right);
}
}

2.2.4 归并排序

利用归并思想实现 采用分治法 将数组拆分成一个个小数组 对这些小数组排序 然后添加到一个临时数组

需要一个临时数组 时间换空间

总归并次数=数组长度-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
void mergeSort0(int[] arr, int left, int right, int[] temp) {
if(left<right) {
int mid = (left+right) / 2;
mergeSort0(arr, left, mid, temp);
mergeSort0(arr, mid+1, right, temp);
merge(arr, left, right, mid, temp);
}
}
void merge(int[] arr, int left, int right, int mid, int[] temp) {
int l = left;
int r = mid+1;
int t = 0;
while(l <=mid && r <=right) {
if(arr[l]<arr[r]) {
temp[t] = arr[l];
l++;
}else {
temp[t] = arr[r];
r++;
}
t++;
}
// 将剩余数组填充到临时数组
while(l<=mid) {
temp[t] = arr[l];
t++;
l++;
}
while(r<=right) {
temp[t] = arr[r];
t++;
r++;
}
// 将排序好的片段填回原数组
t = 0;
for (int i = left; i <=right; i++) {
arr[i] = temp[t++];
}
}

2.2.5 基数排序

通过键值的各个位的值 将要排序的元素分配至某些bucket(桶)中 达到排序的作用 典型的空间换时间算法

将所有待比较的数值统一为同样的数位长度 数位较短的数前面补0 放入相应的桶 然后遍历所有桶 完成一次排序

当数据量较大时 会出现OOM 负数需要特殊处理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void radixSort(int[] arr) {
// 计算最大位数
int maxLenth = (Arrays.stream(arr).max().getAsInt()+"").length();
// 创建10个桶 0-9
int[][] bucket = new int[10][arr.length];
// 记录每个桶的元素数量
int[] bucketElCount = new int[10];
int n = 1;
for (int i = 0; i < maxLenth; i++, n*=10) {
for (int j = 0; j < arr.length; j++) {
int bucketIndex = arr[j] / n % 10;
bucket[bucketIndex][bucketElCount[bucketIndex]] = arr[j];
bucketElCount[bucketIndex]++;
}
int index = 0;
for (int j = 0; j < bucket.length; j++) {
if(bucketElCount[j]>0) {
for (int j2 = 0; j2 < bucketElCount[j]; j2++) {
arr[index++] = bucket[j][j2];
}
}
bucketElCount[j] = 0;
}
}

2.3 查找

2.3.1 线性查找

从头遍历数组 直到找到该值为止

1
2
3
4
5
6
7
8
int linearSearch(int[] arr, int val) {
for (int i = 0; i < arr.length; i++) {
if(arr[i]==val) {
return i;
}
}
return -1;
}

2.3.2 二分查找

需要有序列表 每次与中数组间值比较 如果大 递归向右查询 如果小 递归向左查询

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int binarySearch0(int[] arr, int left, int right, int val) {
if(left>right) {
return -1;
}
int mid = (left+right) / 2;
int midVal = arr[mid];
if(val>midVal) {
return binarySearch0(arr, mid+1, right, val);
}else if(val<midVal) {
return binarySearch0(arr, left, mid-1, val);
}else {
return mid;
}
}

2.3.3 插值查找

类似于二分查找 每次以自适应的mid开始查找 将折半查找中的求mid公式 改为
$$
mid = low+(key-arr[low])*(high-low)/arr[hign]-arr[low]
$$
在数据量特别大时可能会遇到IndexOutOfBounds 和StackOverFlow

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int insertValueSearch0(int[] arr, int left, int right, int val) {
if(left>right || arr[0]>val || arr[arr.length-1]<val) {
return -1;
}
int mid = left +(right-left) * (val-arr[left]) / (arr[right] - arr[left]);
int midVal = arr[mid];
if(midVal > val) {
return insertValueSearch0(arr, left, mid-1, val);
}else if(midVal<val) {
return insertValueSearch0(arr, mid+1, right, val);
}else {
return mid;
}
}

2.3.4 斐波那契(黄金分割)查找

将数组按黄金分割比分为两部分

中间节点计算公式

mid=low+F[k-1]-1

F(k-1)= (F[k-1]-1) + (F[k-2]-1)+1

只要顺序表长度为F[k]-1 可以将该表分成长度为F[k-1]和F[K-2]的两段

如果长度不等于F[k]-1 所以需要将原来的顺序表长度增加至F[k]-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
int fibonacciSearch(int[] arr, int val) {
int low = 0, high = arr.length-1;
int k = 0;
int mid = 0;
int[] f = fibonacci(); // 获取斐波那契数列
while(high>f[k]-1) {k++;}
// 扩增数组至斐波那契数列中某个元素的长度
int[] temp = Arrays.copyOf(arr, f[k]);
for (int i = high+1; i < f[k]; i++) {
temp[i] = arr[high]; // 用最高位补齐
}
while(low<=high) {
mid = low +f[k-1]-1;
if(temp[mid]<val) {
low = mid+1;
// 找出右半段的黄金分割点
k-=2;
}else if(temp[mid]>val) {
high = mid-1;
// 找到左半段的黄金分割点
k--;
}else {
if(mid<=high) {
return mid;
}else {
return high;
}
}
}
return -1;
}

2.4 编码

2.4.1 霍夫曼编码

利用霍夫曼树 对数据进行编码

将数据的主成分提取 生成一颗霍夫曼树

一个根节点与左子节点的距离为0 与右子节点的距离为1

各个编码互不为前缀

可对数据进行无损压缩

对重复数据多的压缩率较高

  • 构建霍夫曼编码表

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    void getHuffmanCode(Node<E> node, String code, StringBuilder sb, Map<E, String> map ){
    StringBuilder builder = new StringBuilder(sb);
    builder.append(code);
    if(node!=null) {
    if(node.value==null) {
    // 左子树编码为0 右子树编码为1 依次递归查找子叶节点 查找过程经过路径即为改数据的编码
    getHuffmanCode(node.left, "0", builder, map);
    getHuffmanCode(node.right, "1", builder, map);
    }else {
    map.put(node.value, builder.toString());
    }
    }
    }
  • 编码

    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
    byte[] compress(@NotNull Map<Character, String> map, @NotNull String content) {
    StringBuilder huffmanCodeStr = new StringBuilder();
    for(char c : content.toCharArray()) {
    huffmanCodeStr.append(map.get(c));
    }
    int len = (huffmanCodeStr.length() + 7) / 8; // 计算需要的字节数组长度
    byte[] huffmanCode = new byte[len+1];
    int index = 0;
    String str = null;
    for (int i = 0; i < huffmanCodeStr.length(); i+=8) {
    if(i+8>huffmanCodeStr.length()) {
    str = huffmanCodeStr.substring(i);
    huffmanCode[index] = (byte) Integer.parseInt(str, 2);
    huffmanCode[index+1] = (byte) str.length(); // 末尾追加一个字节 存储最后不足一字节的二进制位长度
    break;
    }else {
    str = huffmanCodeStr.substring(i, i+8);
    huffmanCode[index] = (byte) Integer.parseInt(str, 2);
    // 最后一字节如果长度刚好为8
    if(i+8==huffmanCodeStr.length()) {
    huffmanCode[index+1] = (byte) str.length();
    break;
    }

    }
    index++;
    }
    return huffmanCode;
    }
  • 解码

    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
    String  decompress(HuffmanTree<Character> tree, @NotNull byte[] code) {
    StringBuilder huffmanStr = new StringBuilder();
    String binaryString = null;
    for(int i = 0; i<code.length-2;i++) {
    byte b = code[i];
    binaryString = Integer.toBinaryString(b | 256); // 不足8位时补位
    binaryString = binaryString.substring(binaryString.length()-8); // 截取1字节 最后8位
    huffmanStr.append(binaryString);
    }
    // 末尾字节需要特殊处理
    byte len = code[code.length-1]; // 获取末尾长度标记字节
    byte b = code[code.length-2]; // 末尾字节
    String string = Integer.toBinaryString(b | 256);
    // 长度刚好或等于指定长度
    binaryString = len < 8 ? string.substring(string.length() - len) : string.substring(string.length()-8);
    huffmanStr.append(binaryString);
    char[] charArray = huffmanStr.toString().toCharArray();
    huffmanStr = new StringBuilder();
    int i = 0;
    Node<Character> node = tree.getRoot();
    // bi
    for (; i < charArray.length;) {
    node = tree.getRoot();
    while(true) {
    if(node.value==null) {
    switch(charArray[i]) {
    case '0':
    node = node.left;
    break;
    case '1':
    node = node.right;
    break;
    }
    i++;
    }else {
    huffmanStr.append(node.value);
    break;
    }
    }
    }
    return huffmanStr.toString();
    }

2.5 分治法

分而治之 思想的体现 将一个大问题拆分成若干个相似的小问题 再把小问题拆成更小的的问题 直到最后可以拆分成直接求解的问题 原问题的解就是小问题的解的合并

基本步骤:

  1. 分解
  2. 解决
  3. 合并

2.5.1 汉诺塔

设三个柱A B C

盘数 n

当n=1 A -> C

当n>=2

A->B

A->C

B->C

1
2
3
4
5
6
7
8
9
10
11
void move(int num, String a, String b, String c) {
if(num==1) {
System.out.println(a+"==>"+c);
}else {
// 借助c 将 a 移动到b
move(num-1, a, c, b);
System.out.println(a+"==>"+c);
// 借助a 将 b 移动到c
move(num-1, b, a, c);
}
}

2.6 动态规划

将大问题划分为小问题进行解决 从而进一步获取最优解的处理算法

与分治算法类似 先求解子问题 然后从这些子问题的解得到原问题的解

与分治法不同的是 适合用于动态规划求解的问题 经分解后得到的子问题 往往不是相互独立的 下一阶段的求解是建立在上一阶段的解的基础上 进行进一步的求解

动态规划可通过填表的方式来逐步推进 得到最优解

2.6.1 背包问题

给定一容量有限的背包 若干具有一定价值和重量的物品 如何选取物品是的放入背包的物品价值最大

又分为01背包(物品不能重复)和完全背包(物品可重复)

思路:

每次遍历到第i个物品 根据w[i]和v[i]来确定是否需要将该物品放入背包中 即对于给定的n个物品 设w[i] v[i] 分别为物品的重量 价格 c为背包容量 再令v[i][j]表示前i个物品中能够装入容量为j的背包的最大价值

v[i][0]=v[0][j]=0 第一行第一列 0

当w[i]>j时 v[i][j] = v[i-1][j] (准备加入背包的物品大于当前背包的容量 直接将上一个单元个的数据装入)

当j>=w[i]时 v[i][j] = max(v[i-1][j], v[i-1][j-w[i]]+v[i]) 当准备加入背包的物品小于等于当前背包的容量 求上一单元格 v[i-1][j-w[i]] 表示装入i-1个商品的总价值(j-w[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
void resolve() {
int[] w = {1, 2, 3, 4}; // 物品重量
int[] v = {500, 1000, 1500, 3000}; // 物品价值
int max = 6; // 背包容量
// 物品与各个容量的背包与价格关系对应表
int[][] table = new int[w.length+1][max+1];
// 物品存放路径
int[][] path = new int[w.length+1][max+1];
for (int i = 1; i < table.length; i++) {
for (int j = 1; j < table[0].length; j++) {
// 如果要存放的物品大于当前背包的容量 则在该单元格内复制上一物品的价格
if(w[i-1] > j) {
table[i][j] = table[i-1][j];
}else {
if(table[i-1][j]< v[i-1]+table[i-1][j-w[i-1]] ) {
// 如果要存放的物品重量小于当前背包重量 且在加入该被背包后剩余容量所对应物品价值 大于上一单元格价值
// 则为当前单元格赋值 且记录路径
table[i][j] = v[i-1]+table[i-1][j-w[i-1]];
path[i][j] = 1;
}else {
table[i][j] = table[i-1][j];
}
}
}
}
for (int[] arr : table) {
System.out.println(Arrays.toString(arr));
}
int i = path.length-1, j = path[0].length-1;
while(i>0 && j > 0) {
if(path[i][j] == 1) {
System.out.println("put "+i+" in");
j -= w[i-1]; // 在找到一件物品后 减去该物品的重量 定位到下一物品所在的位置
}
i--;
}
}

2.7 KMP

字符串查找匹配算法 用于在一个文本内 查找一个字符串出现的位置 相比于传统的暴力匹配算法 效率更高

利用之前判断过的信息 通过一个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
int[] kmpNext(String str) {
int[] next = new int[str.length()];
next[0] = 0;
for (int i = 1,j=0 ; i < str.length(); i++) {
// 如果该位置不匹配 则通过部分匹配表向前查找
while(j > 0 && str.charAt(i)!=str.charAt(j)) {
j = next[j-1];
}
// 如果匹配 移到下一个位置
if(str.charAt(i)==str.charAt(j)) {
j++;
}
next[i] = j;
}
return next;
}
int kmpMatch(String str1, String str2) {
int [] next = kmpNext(str2);
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;
}

2.8 贪心算法

指在对问题进行求解时 在每一步选择中都采取最好或最优的选择 从而希望能够导致结果是最好或最优的算法

最后得到的结果不一定是最优解

2.8.1 集合覆盖问题

假设有n个广播电台 每个广播电台可覆盖一些城市

求用最少的广播电台覆盖全部城市

思路:

  1. 遍历所有广播电台 找到一个覆盖了最多未覆盖地区的电台
  2. 将该电台加入到一个集合 并把该电台覆盖的地区在下次比较时去掉
  3. 重复第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
Map<String, HashSet<String>> broadcast = new HashMap<>();

HashSet<String> b1 = new HashSet<>();
b1.add("A");
b1.add("B");
b1.add("C");

HashSet<String> b2 = new HashSet<>();
b2.add("C");
b2.add("D");

HashSet<String> b3 = new HashSet<>();
b3.add("B");
b3.add("C");

HashSet<String> b4 = new HashSet<>();
b4.add("D");
b4.add("E");

broadcast.put("B1", b1);
broadcast.put("B2", b2);
broadcast.put("B3", b3);
broadcast.put("B4", b4);

HashSet<String> allAreas = new HashSet<>();
allAreas.addAll(Arrays.asList("A", "B", "C", "D", "E"));

System.out.println(allAreas);
List<String> selects = new ArrayList<>();

HashSet<String> tempSet = new HashSet<>();

String sKey = null;

while(allAreas.size()>0) {
sKey = null;
// 遍历所有电台
for(String k : broadcast.keySet()) {
tempSet.clear();
tempSet.addAll(broadcast.get(k));
// 获得当前电台可覆盖区域与所有未覆盖区域的交集
// broadcast.get(k).retainAll(allAreas);
tempSet.retainAll(allAreas);
// System.out.println(k+"==>"+tempSet);
// System.exit(0);
// 从所有电台中获得可覆盖未覆盖区域最多的电台 贪婪的体现
int a = tempSet.size();
int b = sKey == null ? 0: broadcast.get(sKey).size();
if(tempSet.size()>0 && a > b) {
sKey = k;
}
}
if(sKey!=null) {
selects.add(sKey);
// 从未覆盖区域中移除 一次比较后可覆盖区域最多的电台的覆盖区域
allAreas.removeAll(broadcast.get(sKey));
}
}
System.out.println(selects);

2.9 Prim算法

可解决图中可以连通各个节点的总路径最短问题

最小生成树

  • 给定一个带权的无向连通图使树上所有边上权的总和最小 称为最小生成树
  • N个顶点 一定有N-1条边
  • 包含全部顶点
  • N-1条边都在图中

在包含n个顶点的连通图中 找出只有(n-1)条边包含所有n个顶点的联通子图 称为极小联通子图

基本思路:

  1. 设G=(V, E)是联通网 T=(U,D) 为最小生成树 V, U 是顶点集合 E,D 是边的集合
  2. 若集合U中顶点ui与集合V-U中的顶点vj存在边 则寻找这些边中权值最小的边 但不能构成回路 将顶点vj加入集合D中 将边(ui, uj)加入集合中 标记visited[vj]=1
  3. 重复步骤2 直到所有顶点都标记为为访问过 此时D中有n-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
int verxs = 6;
int[] visited = new int[verxs];
char[] site = {'A', 'B', 'C', 'D', 'E', 'F'};
int[][] weights = new int[verxs][verxs];
for (int i = 0; i < weights.length; i++) {
for (int j = 0; j < weights[i].length; j++) {
weights[i][j] = 10000;
}
}
// 双向设置路径权值
weights[0][1] = 2;
weights[0][2] = 4;
weights[1][3] = 5;
weights[2][4] = 6;
weights[3][5] = 3;
weights[4][5] = 7;
weights[1][4] = 4;
weights[1][5] = 9;

weights[1][0] = 2;
weights[2][0] = 4;
weights[3][1] = 5;
weights[4][2] = 6;
weights[5][3] = 3;
weights[5][4] = 7;
weights[4][1] = 4;
weights[5][1] = 9;
// 起始点
int start = 0;
visited[start] = 1;
int minWeight = 10000;
int a = -1, b =-1;
for (int i = 1; i < verxs; i++) {
// 已访问的节点
for (int j = 0; j < verxs; j++) {
// 从当前已访问的节点开始找到权值最小的相邻节点
for (int k = 0; k < verxs; k++) {
if(visited[j] == 1 && visited[k]==0 && weights[j][k] < minWeight) {
minWeight = weights[j][k];
// 标记已找到的点
a = j;
b = k;
}
}
}
System.out.println("<"+site[a]+","+site[b]+"> ==>"+minWeight);
// 将找到的节点标记为已访问
visited[b] = 1;
// 重置最小权值
minWeight=10000;
}

3.0 Kruskal算法

解决最小生成树问题

基本思路

按照权值 从大到小选择n-1条边 并保证n-1条边不构成回路

构造一个只含n个顶点的森林 然后按权值从小到大从连通网中选择边加入到森林中 并使森林不产生回路 直到森林变成一棵树为止

判断回路:

最大顶点: 将所有顶点按升序排列好之后 某个顶点的终点即为最大顶点

加入森林的两个顶点不能都指向同一顶点 否则将构成回路

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
int getIndex(char node) {
for (int i = 0; i < nodes.length; i++) {
if(nodes[i]==node) {
return i;
}
}
return -1;
}
int getEnd(int[] ends, int i) {
while(ends[i]!=0) {
// 指向该顶点的下一邻接顶点 直到指向终点(ends[i]=0)
i = ends[i];
}
return i;
}
void kruskal() {
List<Edge> res = new ArrayList<>();
// 保存所有顶点的终点
int[] ends = new int[edgeNum];
for (int i = 0; i < edgeNum; i++) {
// 获取起始顶点位置
int start = getIndex(edges[i].start);
// 获取起始顶点位置
int end = getIndex(edges[i].end);
// 获取两个位置的终点
int a = getEnd(ends, start);
int b = getEnd(ends, end);
// 如果终点不同 则找到一条边
if(a!=b) {
ends[a] = b;
res.add(edges[i]);
}
}
for(Edge e : res) {
System.out.println(e.weight);
}
}

3.1 Dijkstra算法

解决 从一个顶点到其他顶点的最短路径问题

主要特点是以七十点为中心向外层层扩散 直到扩展到终点为止

设置出发点为v 顶点集合为V{v1, v2…vj} v到V中各顶点的距离构成集合Dis Dis集合记录看v到图中各个顶点的距离(到自身可以看作0, v到vi距离对应为di)

  1. 从Dis中选择值最小的di并移出Dis集合 同时移出V集合中对应的顶点vi 此时的v到vi即为最短路径
  2. 更新Dis集合 更新规则为 比较v到V集合中顶点的距离值 与v通过vi到V集合中顶点的距离值 保留较小的一个(同时更新节点的前驱节点为vi 表示已访问)
  3. 重复执行以上步骤 直到最短路径顶点为目标顶点即可结束
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
int[] visited;  // 已访问过的节点
int[] preVisited; // 已访问过的节点的前驱节点
int[] dis; // 初始节点与其他各个节点的距离
void dijkstra(int index) {
visited[index] = 1;
dis[index] = 0;
update(index);
// 更新剩余顶点
for (int i = 1; i < dis.length; i++) {
index = updateIndex();
update(index);
}
}
void update(int index) {
int len = 0;
for (int i = 0; i < dis.length ; i++) {
// 计算当前起始节点与当前节点和当前节点与下一邻接节点的距离之和 并与起始节点与该邻接节点的直接距离比较 取最小值 得到新的起始节点与其他节点的距离最小值
len = dis[index] + weights[index][i];
if(visited[i]==0 && len < dis[i]) {
preVisited[i] = index; // 记录前驱节点
dis[i] = len;
}
}
}
int updateIndex() {
int index = 0, min = 65535;
for (int i = 0; i < dis.length; i++) {
// 找到与起始顶点距离最短的顶点作为下一顶点
if(visited[i]==0 && dis[i] < min) {
min = dis[i];
index = i;
}
}
visited[index] = 1;
return index;
}

3.2 Floyd算法

求各个顶点到其他顶点的最短路径

基本思路

找一个中心点 并以这个中心点的为基准 求 相邻两点经过该点的路径 与两点直接路径的最小值 所有情况进行遍历 从而更新 距离关系 和前驱关系

1
2
3
4
5
6
7
8
9
10
11
12
int len = 0;
for (int k = 0; k < nodes.length; k++) {
for (int i = 0; i < nodes.length; i++) {
for (int j = 0; j < nodes.length; j++) {
len = weights[i][k] + weights[k][j];
if(len < weights[i][j]) {
weights[i][j] = len;
pre[i][j] = pre[k][j];
}
}
}
}

3.3 马踏棋盘问题

在8 * 8的国际象棋盘上 马按照马走日字进行移动 要求每个放个只走一次 并踏遍所有方格

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
void travelBoard(int[][] chessBoard, int x, int y, int step){
Point p = new Point(x, y);
visited[x][y] = true;
List<Point> ps = nextPoints(p); // 查找该点周围可以走的点
chessBoard[x][y] = step;
sort(ps); // 贪心算法优化 从邻点最少的点开始遍历(非降序排序)
while(!ps.isEmpty()) {
Point point = ps.remove(0);
if(!visited[point.x][point.y]) {
// 以下一个点为中心递归继续查找 深度优先遍历
travelBoard(chessBoard, point.x, point.y, step+1);
}
}
// 如果没有走完 说明该点行不通
if(step < X * Y && !finished) {
chessBoard[x][y] = 0;
visited[x][y] = false;
}else {
finished = true;
}
}
// 查找点周围的8个可移动的位置
List<Point> nextPoints(Point p){
List<Point> ps = new ArrayList<>();
if(p.x - 2 >= 0 && p.y-1>=0) {
ps.add(new Point(p.x-2, p.y-1));
}
if(p.x-1>=0 && p.y-2>=0) {
ps.add(new Point(p.x-1, p.y-2));
}
if(p.x+2<X && p.y-1>=0) {
ps.add(new Point(p.x+2, p.y-1));
}

if(p.x+1<X && p.y-2>=0) {
ps.add(new Point(p.x+1, p.y-2));
}


if(p.x-2>=0 && p.y+1<Y) {
ps.add(new Point(p.x-2, p.y+1));
}

if(p.x-1>=0 && p.y+2<Y) {
ps.add(new Point(p.x-1, p.y+2));
}

if(p.x+1 < X && p.y+2<Y) {
ps.add(new Point(p.x+1, p.y+2));
}
if(p.x+2 < X && p.y+1<Y) {
ps.add(new Point(p.x+2, p.y+1));
}
return ps;
}