代码仓库的地址:https://gitee.com/JasonsGong/DataStructures

一.经典算法问题

字符串匹配 KMP算法

汉诺塔问题 分治算法

八皇后问题 回溯算法

马踏棋盘问题 图的深度优化遍历算法(DFS)和 贪心算法优化

二.数据结构与算法的概述

2.1 数据结构与算法的关系

（1）数据(data)结构(structure)是一门研究组织数据方式的学科，有了编程语言也就有了数据结构，学好了数据结构可以编写出更加漂亮，更加有效率的代码。

（2）程序=数据结构+算法

（3）数据结构是算法的基础

2.2解决实际的问题

五子棋程序 稀疏数组（压缩存档） 二维数组->转化成稀疏数组->存档 读档反之

约瑟夫问题(丢手帕问题) 单向环形列表

修路问题 求最小生成树 + 普利姆算法

最短路径问题 图+弗洛伊德算法

2.3 数据结构

线性结构:

​ 线性结构作为最常用的数据结构，其特点是数据元素之间存在一对一的线性关系

​ 线性结构有两种不同的存储结构，即顺序存储结构和链式存储结构。顺序存储的线性表称为顺序表，顺序表中的存储元素是连续的

​ 链式存储的线性表称为链表，链表中的存储元素不一定是连续的，元素节点中存放数据元素以及相邻元素的地址信息

​ 线性结构常见的有：数组、队列、链表和栈

非线性结构:

​ 二维数组，多维数组，广义表，树结构，图结构

三.稀疏数组和队列

3.1稀疏数组

3.1.1 基本的介绍

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

稀疏数组的处理方法是:

​ 1)记录数组一共有几行几列，有多少个不同的值

​ 2)把具有不同值的元素的行列及值记录在一个小规模的数组中，从而缩小程序的规模

3.1.2使用的场景

​ 五子棋程序的存档和退出功能的实现

3.1.3图解

第一行记录的是原始的数组有几行几列有几个非零的值 例如下面的数组是一个6行7列有8个非零值的数组

image-20230313124552408

3.1.5实现的思路

image-20230318100138197

3.1.5代码实现

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
package com.atguigu.sparsearray;

/**
 * @author GongChangjiang
 * @version 1.0
 * @Date 2023/3/18
 * @Description 稀疏数组的代码实现  稀疏数组和二维数组之间的互转
 */
public class SparseArray {

    public static void main(String[] args) {
        //创建一个原始的二维数组
        //0:表示没有棋子   1:表示黑子   2:表示白子
        int[][] chessArr1 = new int[11][11];
        chessArr1[1][2] = 1;
        chessArr1[2][3] = 2;
        chessArr1[4][5] = 1;
        //遍历输出
        System.out.println("原始的二维数组");
        for (int[] row : chessArr1) {
            for (int num : row) {
                System.out.print(num + " ");
            }
            System.out.println();
        }


        //将二维数组转化成稀疏数组
        //获取原始二维数组中非零元素的个数
        int sum = 0;
        for (int[] row : chessArr1) {
            for (int num : row) {
                if (num != 0) {
                    sum++;
                }
            }
        }
        System.out.println("非零元素的个数:" + sum);
        //根据非零的元素的个数创建对应的稀疏数组
        int[][] sparseArr2 = new int[sum + 1][3];
        //给稀疏数组赋值
        //第一行的赋值操作
        sparseArr2[0][0] = 11;
        sparseArr2[0][1] = 11;
        sparseArr2[0][2] = sum;
        //其余行的赋值操作
        int row = 1; //充当计数器的作用
        for (int i = 0; i < chessArr1.length; i++) {
            for (int j = 0; j < chessArr1[i].length; j++) {
                if (chessArr1[i][j] != 0) {
                    sparseArr2[row][0] = i;
                    sparseArr2[row][1] = j;
                    sparseArr2[row][2] = chessArr1[i][j];
                    row++;
                }
            }
        }


        //遍历稀疏数组
        System.out.println("得到的稀疏数组如下");
        for (int[] ints : sparseArr2) {
            for (int anInt : ints) {
                System.out.print(anInt + " ");
            }
            System.out.println();
        }


        //将稀疏数组转化成二维数组
        //获取原先的二维数组的大小
        //读取第一行 获取原始二维数组的行列值
        int[][] sparseArr3 = new int[sparseArr2[0][0]][sparseArr2[0][1]];
        //遍历稀疏数组第二行之后的值 赋值给原始的数组 从第二行开始算
        for (int i = 1; i < sparseArr2.length; i++) {
            sparseArr3[sparseArr2[i][0]][sparseArr2[i][1]] = sparseArr2[i][2];
        }

        //遍历还原之后的二维数组
        System.out.println("稀疏数组还原成二维数组");
        for (int[] ints : sparseArr3) {
            for (int anInt : ints) {
                System.out.print(anInt+" ");
            }
            System.out.println();
        }


    }
}

3.2队列

3.2.1基本的介绍

先进先出

队列是一个有序列表，可以通过数组或者链表实现。

遵循先入先出的原则。即：先存入队列的数据，要先取出。后存入队列的数据要后取出。

3.2.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
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
package com.atguigu.queue;

import java.util.Scanner;

/**
 * @author GongChangjiang
 * @version 1.0
 * @Date 2023/3/18
 * @Description 使用数组模拟队列
 */
public class ArrayQueueDemo {
    public static void main(String[] args) {
        //测试一把
        //创建一个队列
        ArrayQueue queue = new ArrayQueue(3);
        char key = ' '; //接收用户输入
        Scanner scanner = new Scanner(System.in);//
        boolean loop = true;
        //输出一个菜单
        while (loop) {
            System.out.println("s(show): 显示队列");
            System.out.println("e(exit): 退出程序");
            System.out.println("a(add): 添加数据到队列");
            System.out.println("g(get): 从队列取出数据");
            System.out.println("h(head): 查看队列头的数据");
            key = scanner.next().charAt(0);//接收一个字符
            switch (key) {
                case 's':
                    queue.showQueue();
                    break;
                case 'a':
                    System.out.println("输出一个数");
                    int value = scanner.nextInt();
                    queue.addQueue(value);
                    break;
                case 'g': //取出数据
                    try {
                        int res = queue.getQueue();
                        System.out.printf("取出的数据是%d\n", res);
                    } catch (Exception e) {
                        // TODO: handle exception
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'h': //查看队列头的数据
                    try {
                        int res = queue.headQueue();
                        System.out.printf("队列头的数据是%d\n", res);
                    } catch (Exception e) {
                        // TODO: handle exception
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'e': //退出
                    scanner.close();
                    loop = false;
                    break;
                default:
                    break;
            }
        }

        System.out.println("程序退出~~");
    }

}

// 使用数组模拟队列-编写一个ArrayQueue类
class ArrayQueue {
    private int maxSize; // 表示数组的最大容量
    private int front; // 队列头
    private int rear; // 队列尾
    private int[] arr; // 该数据用于存放数据, 模拟队列

    // 创建队列的构造器
    public ArrayQueue(int arrMaxSize) {
        maxSize = arrMaxSize;
        arr = new int[maxSize];
        front = -1; // 指向队列头部，分析出front是指向队列头的前一个位置.
        rear = -1; // 指向队列尾，指向队列尾的数据(即就是队列最后一个数据)
    }

    // 判断队列是否满
    public boolean isFull() {
        return rear == maxSize - 1;
    }

    // 判断队列是否为空
    public boolean isEmpty() {
        return rear == front;
    }

    // 添加数据到队列
    public void addQueue(int n) {
        // 判断队列是否满
        if (isFull()) {
            System.out.println("队列满，不能加入数据~");
            return;
        }
        rear++; // 让rear 后移
        arr[rear] = n;
    }

    // 获取队列的数据, 出队列
    public int getQueue() {
        // 判断队列是否空
        if (isEmpty()) {
            // 通过抛出异常
            throw new RuntimeException("队列空，不能取数据");
        }
        front++; // front后移
        return arr[front];

    }

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

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

3.2.3 数组模拟环形队列

环形队列的思路分析

  • 环形队列满的条件:(rear + 1) % maxSize == front
  • 环形队列空的条件:rear == front
  • 环形队列中有效数据的个数: (rear + maxSize - front) % maxSize

image-20230428124659873

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
package com.atguigu.queue;

import java.util.Scanner;

/**
 * @author GongChangjiang
 * @version 1.0
 * @Date 2023/4/28
 * @Description 模拟环形队列
 * <p>
 * 环形队列满的条件:(rear + 1) % maxSize == front
 * 环形队列空的条件:rear == front
 * 环形队列中有效数据的个数: (rear + maxSize - front) % maxSize
 */

public class CircleArrayQueueDemo {
    public static void main(String[] args) {
        //创建一个队列
        System.out.println("测试环形队列");
        CircleArray queue = new CircleArray(3);
        char key = ' '; //接收用户输入
        Scanner scanner = new Scanner(System.in);//
        boolean loop = true;
        //输出一个菜单
        while (loop) {
            System.out.println("s(show): 显示队列");
            System.out.println("e(exit): 退出程序");
            System.out.println("a(add): 添加数据到队列");
            System.out.println("g(get): 从队列取出数据");
            System.out.println("h(head): 查看队列头的数据");
            key = scanner.next().charAt(0);//接收一个字符
            switch (key) {
                case 's':
                    queue.showQueue();
                    break;
                case 'a'://添加数据
                    System.out.println("输出一个数");
                    int value = scanner.nextInt();
                    queue.addQueue(value);
                    break;
                case 'g': //取出数据
                    try {
                        int res = queue.getQueue();
                        System.out.printf("取出的数据是%d\n", res);
                    } catch (Exception e) {
                        // TODO: handle exception
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'h': //查看队列头的数据
                    try {
                        int res = queue.headQueue();
                        System.out.printf("队列头的数据是%d\n", res);
                    } catch (Exception e) {
                        // TODO: handle exception
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'e': //退出
                    scanner.close();
                    loop = false;
                    break;
                default:
                    break;
            }
        }

        System.out.println("程序退出~~");
    }
}

class CircleArray {
    private int maxSize; // 表示数组的最大容量 因为预留了一个空间 实际上maxSize=3 只能存储两个元素
    private int front; // 队列头  初始值是0
    //rear 变量的含义做一个调整：rear 指向队列的最后一个元素的后一个位置. 因为希望空出一个空间做为约定
    private int rear; // 队列尾
    private int[] arr; // 该数据用于存放数据, 模拟队列

    /**
     * 构造方法
     *
     * @param arrMaxSize 环形队列的最大容量
     */
    public CircleArray(int arrMaxSize) {
        maxSize = arrMaxSize;
        arr = new int[maxSize];
    }

    /**
     * 判断队列是否为满
     */
    public boolean isFull() {
        //因为是环形队列 如果尾部队列的后一个指向队列的头部 那么我们认为队列是满的
        return (rear + 1) % maxSize == front;   //这里是一个理解点
    }

    /**
     * 判断队列是否为空
     */
    public boolean isEmpty() {
        return rear == front;
    }


    /**
     * 添加数据
     */
    public void addQueue(int n) {
        //先判断队列是否为满  满了就不添加
        if (this.isFull()) {
            System.out.println("队列为满,不能添加数据!");
            return;
        }
        //添加数据
        arr[rear] = n;
        //将人rear向后移
        rear = (rear + 1) % maxSize;  //这里是一个理解点
    }


    /**
     * 取出数据
     */
    public int getQueue() {
        //先判断队列是否为空  空了就无法取出数据
        if (this.isEmpty()) {
            System.out.println("队列为空,无法取出数据!");
            throw new RuntimeException("队列空，不能取数据");
        }
        //不为空 取出数据
        int result = arr[front];
        front = (front + 1) % maxSize; //这里是一个理解点
        return result;
    }


    /**
     * 显示对垒数据的方法
     */
    public void showQueue() {
        //判断队列是否为空 如果队列为空就不遍历
        if (this.isEmpty()) {
            System.out.println("队列为空!");
            return;
        }
        //遍历的方式 从front开始遍历  遍历多少个元素
        int count = this.size();
        for (int i = front; i < front + count; i++) {//主要作用是遍历多少次
            System.out.println("arr[" + i % maxSize + "]=" + arr[i % maxSize]);
        }
    }

    /**
     * 求出当前数列中有效数据的个数
     */
    public int size() {
        return (rear + maxSize - front) % maxSize;  //这是一个理解点
    }

    /**
     * 显示队列的头元素
     */
    public int headQueue() {
        // 判断
        if (isEmpty()) {
            throw new RuntimeException("队列空的，没有数据~~");
        }
        return arr[front];
    }

}

四.链表

4.1 链表(Linked List)介绍

在内存中不是连续存储的

链表的逻辑结构

image-20230428135032883

4.2单链表的应用实例(CRUD)

使用带head头的单向链表实现 –水浒英雄排行榜管理 完成对英雄人物的增删改查操作

4.2.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
68
69
70
71
72
73
74
75
76
77
78
79
80
package com.atguigu.linkedlist;

/**
 * @author GongChangjiang
 * @version 1.0
 * @Date 2023/4/28
 * @Description 单链表的实现
 * 使用带head头的单向链表实现 –水浒英雄排行榜管理
 * 完成对英雄人物的增删改查操作
 */
public class SingleLinkedListDemo {
    public static void main(String[] args) {
        SingleLinkedList singleLinkedList = new SingleLinkedList();
        singleLinkedList.add(new HeroNode(1, "宋江", "及时雨"));
        singleLinkedList.add(new HeroNode(2, "卢俊义", "玉麒麟"));
        singleLinkedList.add(new HeroNode(3, "吴用", "智多星"));
        singleLinkedList.add(new HeroNode(4, "林冲", "豹子头"));
        //显示链表
        singleLinkedList.list();
    }
}

//定义SingleLinkedList来管理我们的英雄任务
class SingleLinkedList {
    //初始化一个头节点 不存储具体的数据
    private HeroNode head = new HeroNode(0, "", "");

    /**
     * 添加节点到单向链表
     */
    public void add(HeroNode heroNode) {
        //找到当前链表的最后一个节点
        HeroNode temp = head;
        while (temp.next != null) {
            temp = temp.next;
        }
        temp.next = heroNode;
    }

    /**
     * 显示链表
     */
    public void list() {
        //先判断链表是否为空
        if (head.next == null) {
            System.out.println("链表为空!");
            return;
        }
        HeroNode temp = head;
        while (temp.next != null) {
            System.out.println(temp.next);
            temp = temp.next;
        }
    }

}

//定义一个heroNode,每个heroNode对象都是一个节点
class HeroNode {
    public int no;
    public String name;
    public String nickname;
    public HeroNode next;  //指向下一个节点

    //构造器
    public HeroNode(int no, String name, String nickname) {
        this.no = no;
        this.name = name;
        this.nickname = nickname;
    }

    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickname='" + nickname + '\'' +
                '}';
    }
}

4.2.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
/**
   * 修改节点的信息
   * 根据新的节点的编号进行修改
   */
  public void update(HeroNode newHeroNode) {
      //判断链表是否为空
      if (head.next == null) {
          System.out.println("链表为空,无法修改该节点!");
          return;
      }
      //找到需要修改的节点
      //首先找到头节点的位置
      HeroNode temp = head.next;
      boolean idFind = false;  //是否找到节点的信息
      while (true) {
          if (temp == null) {
              break;//已经到了链表的结尾,就退出循环
          }
          if (temp.no == newHeroNode.no) {//找到修改的节点
              temp.name = newHeroNode.name;
              temp.nickname = newHeroNode.nickname;
              idFind = true; //找到了节点并且修改了节点的信息
              break;
          }
          temp = temp.next;
      }
      //做出判断,返回结果
      System.out.println(idFind ? "修改成功" : "没有找到该节点的信息");
  }

4.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
29
30
/**
    * 删除链表中的节点
    * 根据节点的编号删除节点的信息
    */
   public void delete(int no) {
       //判断链表是否为空
       if (head.next == null) {
           System.out.println("链表为空,无法删除!");
           return;
       }
       //找到要删除的节点的信息
       HeroNode temp = head;
       boolean isDelete = false;//是否删除
       while (true) {
           if (temp.next == null) {
               break;
           }
           //这里的temp指的是要删除节点的上一个节点  temp.next.next指的是要删除节点的下一个节点
           if (temp.next.no == no) {
               //将要删除的节点的上一个节点指向要删除节点的下一个节点 实现删除的操作
               //这样要删除的节点没有引用指向,会被垃圾回收机制回收
               temp.next = temp.next.next;  
               isDelete = true;
               break;
           }
           temp = temp.next;
       }
       //做出判断,返回结果
       System.out.println(isDelete ? "删除成功" : "没有找到该节点的信息");
   }

4.2.4完整代码

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
package com.atguigu.linkedlist;

/**
 * @author GongChangjiang
 * @version 1.0
 * @Date 2023/4/28
 * @Description 单链表的实现
 * 使用带head头的单向链表实现 –水浒英雄排行榜管理
 * 完成对英雄人物的增删改查操作
 */
public class SingleLinkedListDemo {
    public static void main(String[] args) {
        SingleLinkedList singleLinkedList = new SingleLinkedList();
        singleLinkedList.add(new HeroNode(1, "宋江", "及时雨"));
        singleLinkedList.add(new HeroNode(2, "卢俊义", "玉麒麟"));
        singleLinkedList.add(new HeroNode(3, "吴用", "智多星"));
        singleLinkedList.add(new HeroNode(4, "林冲", "豹子头"));
        //显示链表
        singleLinkedList.list();
        //测试修改节点的功能
        singleLinkedList.update(new HeroNode(2, "卢俊义", "玉麒麟增强版"));
        //显示链表的信息
        singleLinkedList.list();
        //测试删除节点
        singleLinkedList.delete(2);
        //显示链表的信息
        singleLinkedList.list();
    }
}

//定义SingleLinkedList来管理我们的英雄任务
class SingleLinkedList {
    //初始化一个头节点 不存储具体的数据
    private HeroNode head = new HeroNode(0, "", "");


    /**
     * 删除链表中的节点
     * 根据节点的编号删除节点的信息
     */
    public void delete(int no) {
        //判断链表是否为空
        if (head.next == null) {
            System.out.println("链表为空,无法删除!");
            return;
        }
        //找到要删除的节点的信息
        HeroNode temp = head;
        boolean isDelete = false;//是否删除
        while (true) {
            if (temp.next == null) {
                break;
            }
            if (temp.next.no == no) {//这里的temp指的是要删除节点的上一个节点  temp.next.next指的是要删除节点的下一个节点
                //将当前节点的上一个节点指向当前节点的下一个节点
                temp.next = temp.next.next;  //将要删除的节点的上一个节点指向要删除节点的下一个节点  这样要删除的节点没有引用指向 会被垃圾回收机制回收
                isDelete = true;
                break;
            }
            temp = temp.next;
        }
        //做出判断,返回结果
        System.out.println(isDelete ? "删除成功" : "没有找到该节点的信息");
    }


    /**
     * 修改节点的信息
     * 根据新的节点的编号进行修改
     */
    public void update(HeroNode newHeroNode) {
        //判断链表是否为空
        if (head.next == null) {
            System.out.println("链表为空,无法修改该节点!");
            return;
        }
        //找到需要修改的节点
        //首先找到头节点的位置
        HeroNode temp = head.next;
        boolean idFind = false;  //是否找到节点的信息
        while (true) {
            if (temp == null) {
                break;//已经到了链表的结尾,就退出循环
            }
            if (temp.no == newHeroNode.no) {//找到修改的节点
                temp.name = newHeroNode.name;
                temp.nickname = newHeroNode.nickname;
                idFind = true; //找到了节点并且修改了节点的信息
                break;
            }
            temp = temp.next;
        }
        //做出判断,返回结果
        System.out.println(idFind ? "修改成功" : "没有找到该节点的信息");
    }


    /**
     * 添加节点到单向链表
     */
    public void add(HeroNode heroNode) {
        //找到当前链表的最后一个节点
        HeroNode temp = head;
        while (temp.next != null) {
            temp = temp.next;
        }
        temp.next = heroNode;
    }


    /**
     * 显示链表
     */
    public void list() {
        //先判断链表是否为空
        if (head.next == null) {
            System.out.println("链表为空!");
            return;
        }
        HeroNode temp = head;
        while (temp.next != null) {
            System.out.println(temp.next);
            temp = temp.next;
        }
    }

}

//定义一个heroNode,每个heroNode对象都是一个节点
class HeroNode {
    public int no;
    public String name;
    public String nickname;
    public HeroNode next;  //指向下一个节点

    //构造器
    public HeroNode(int no, String name, String nickname) {
        this.no = no;
        this.name = name;
        this.nickname = nickname;
    }

    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickname='" + nickname + '\'' +
                '}';
    }
}

4.2.5 单链表的面试题（新浪，百度，腾讯）

1.求单链表中有效节点的个数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
    * 获取有效节点的个数（如果是带头节点的链表，需求不统计头节点）
    * 注意:这里是有头节点的情况下统计节点的个数 （这里我们去除了头节点）
    * @param heroNode  头节点
    * @return  有效节点的个数
    */
   public int getLength(HeroNode heroNode){
       //先判断节点是否为空
       if(heroNode.next == null){
           return 0;
       }
       //遍历节点进行统计
       int length = 0;//有效节点的个数
       HeroNode temp = heroNode.next;//这里没有统计头节点
       while (temp != null){//遍历 统计个数
           length++;
           temp = temp.next;
       }
       return length;
   }
2.查找单链表中的倒数第K个节点(新浪面试题)
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
/**
     * 查找单链表中的倒数第K个节点
     *
     * @param index    倒数第几
     * @param heroNode 头节点
     * @return 倒数第K个节点的信息
     */
    public HeroNode getHeroNodeByLastIndex(int index, HeroNode heroNode) {
        //先判断节点是否为空
        if (heroNode.next == null) {
            return null;
        }
        //首先获取有效节点的个数
        int length = this.getLength(heroNode);//使用求节点有效个数的方法
        //求倒数第k个节点就是在求正数第（length - index + 1）节点
        index = length - index;  //求出正向的索引位置
        if (index < 0 || index > length) {
            System.out.println("所求的在链表中不存在");
            return null;
        }
        int count = 0;
        HeroNode temp = heroNode.next;
        while (true) {
            if (count == index) {
                return temp;
            }
            count++;
            temp = temp.next;
        }
    }
3.单链表的反转(腾讯面试题)

image-20230506105453269

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
/**
    * 单链表的反转
    * @param heroNode 需要反转单链表的头节点
    */
   public void reverseHeroNode(HeroNode heroNode) {
       //先判断当前的链表是否为空  或者当前的链表只有一个节点
       if(head.next == null || head.next.next == null){
           System.out.println("当前链表为空或者只有一个节点,无需反转");
           return;
       }
       //定义一个辅助的变量  帮助我们遍历原来的链表
       HeroNode cur = head.next;
       HeroNode next = null;//指向当前节点的下一个节点 我们要在挪动当前节点之前帮当前指针 下移
       HeroNode reverseHeroNode = new HeroNode(0, "", "");//新链表的头节点
       //遍历原先的列表 确定每一个链表的指向关系
       while (cur != null){
           next = cur.next;//保存当前节点的下一个节点
           //reverseHeroNode.next表示头节点的下一个节点   我们让cur的下一个节点（cur.next）指向头节点的下一个节点 			   //（reverseHeroNode.next） 就把当前的节点（cur）穿插进去了
           //下一句将头节点和当前节点建立关系reverseHeroNode.next = cur  整个节点就连接起来了
           cur.next = reverseHeroNode.next;//将cur的下一个节点指向新的链表的最前端 相当于在头节点和头节点的下一个节点 										 //之间穿插了一个节点
           reverseHeroNode.next = cur;//将cur连接到新的链表上
           cur = next; //cur像后移动
       }
       //将head.next指向reverseHeroNode.next 实现单链表的反转
       head.next = reverseHeroNode.next;
   }
4.从尾到头打印单链表（百度面试题）

不改变链表本身的结构(不是通过链表的反转之后再打印的)

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
/**
   * （通过栈的方式实现单链表的逆序打印）
   * 栈的特点是先入后出  正好可以满足逆序打印
   * 单链表的逆序打印
   */
  public void reversePrint(HeroNode heroNode) {
      //先判断当前的链表是否为空  或者当前的链表只有一个节点
      if (head.next == null) {
          System.out.println("当前链表为空,无法逆序打印!");
          return;
      }
      //创建一个栈，将各个节点压入栈中
      //先创建一个栈
      Stack<HeroNode> stack = new Stack<>();
      HeroNode cur = heroNode.next;
      //循环将每一个节点添加进栈中
      while (cur != null) {
          stack.push(cur);//将节点压入栈中
          cur = cur.next;//cur后移 压入下一个节点
      }
      //将栈中节点打印
      while (stack.size() > 0) {
          System.out.println(stack.pop());
      }
  }
5.合并两个有序的单链表，合并之后的链表依然有序

以下代码有一些bug 后期修改

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 static void mergeHeroNode(HeroNode oneHead, HeroNode twoHead ,HeroNode head) {
       //先判断两个链表是否为空
       if (oneHead.next == null || twoHead.next == null) {
           System.out.println("其中有一个（两个）链表为空,无法合并");
           return;
       }
       //合并
       HeroNode oneCur = oneHead.next;
       HeroNode twoCur = twoHead.next;
       HeroNode oneNext = null;
       HeroNode twoNext = null;
       HeroNode finalHeroHead = new HeroNode(0, "", "");
       while (oneCur != null && twoCur  != null) {
           oneNext = oneCur.next;
           twoNext = twoCur.next;
           if(oneCur.no <= twoCur.no) {
               oneCur.next = finalHeroHead.next;
               finalHeroHead.next = oneCur;
               oneCur = oneNext;
           }else {
               twoCur.next = finalHeroHead.next;
               finalHeroHead.next = twoCur;
               twoCur = twoNext;
           }
       }
       head.next = finalHeroHead.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
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
316
317
318
319
320
321
322
323
324
325
package com.atguigu.linkedlist;

import java.util.Stack;

/**
 * @author GongChangjiang
 * @version 1.0
 * @Date 2023/4/28
 * @Description 单链表的实现
 * 使用带head头的单向链表实现 –水浒英雄排行榜管理
 * 完成对英雄人物的增删改查操作
 */
public class SingleLinkedListDemo {
    public static void main(String[] args) {
        SingleLinkedList singleLinkedList = new SingleLinkedList();
//        singleLinkedList.add(new HeroNode(1, "宋江", "及时雨"));
//        singleLinkedList.add(new HeroNode(2, "卢俊义", "玉麒麟"));
//        singleLinkedList.add(new HeroNode(3, "吴用", "智多星"));
//        singleLinkedList.add(new HeroNode(4, "林冲", "豹子头"));
//        //显示链表
//        singleLinkedList.list();
//        //测试修改节点的功能
//        singleLinkedList.update(new HeroNode(2, "卢俊义", "玉麒麟增强版"));
//        //显示链表的信息
//        singleLinkedList.list();
//        //测试删除节点
//        singleLinkedList.delete(2);
//        //显示链表的信息
//        singleLinkedList.list();
//        //统计有效节点的个数
//        System.out.println("有效节点的个数" + singleLinkedList.getLength(singleLinkedList.getHead()));
//        //查找单链表中的倒数第K个节点
//        int index = 2;
//        System.out.println("倒数第" + index + "个节点的位置:" + singleLinkedList.getHeroNodeByLastIndex(index, singleLinkedList.getHead()));
//        //测试单链表的反转
//        singleLinkedList.reverseHeroNode(singleLinkedList.getHead());
//        singleLinkedList.list();
//        //测试通过栈的方式逆序打印
//        System.out.println("测试通过栈的方式逆序打印头节点");
//        singleLinkedList.reversePrint(singleLinkedList.getHead());

        //测试合并两个有序的链表
        SingleLinkedList singleLinkedList1 = new SingleLinkedList();
        singleLinkedList1.add(new HeroNode(1, "宋江", "及时雨"));
        singleLinkedList1.add(new HeroNode(3, "卢俊义", "玉麒麟"));
        singleLinkedList1.add(new HeroNode(5, "吴用", "智多星"));
        singleLinkedList1.add(new HeroNode(7, "林冲", "豹子头"));
        SingleLinkedList singleLinkedList2 = new SingleLinkedList();
        singleLinkedList2.add(new HeroNode(2, "宋江", "及时雨"));
        singleLinkedList2.add(new HeroNode(4, "卢俊义", "玉麒麟"));
        singleLinkedList2.add(new HeroNode(6, "吴用", "智多星"));
        singleLinkedList2.add(new HeroNode(8, "林冲", "豹子头"));
        mergeHeroNode(singleLinkedList1.getHead(),singleLinkedList2.getHead(),singleLinkedList.getHead());
        singleLinkedList.list();
    }
    /**
     * 合并两个有序的单链表，合并之后的链表依然有序
     */
    public static void mergeHeroNode(HeroNode oneHead, HeroNode twoHead ,HeroNode head) {
        //先判断两个链表是否为空
        if (oneHead.next == null || twoHead.next == null) {
            System.out.println("其中有一个（两个）链表为空,无法合并");
            return;
        }
        //合并
        HeroNode oneCur = oneHead.next;
        HeroNode twoCur = twoHead.next;
        HeroNode oneNext = null;
        HeroNode twoNext = null;
        HeroNode finalHeroHead = new HeroNode(0, "", "");
        while (oneCur != null && twoCur  != null) {
            oneNext = oneCur.next;
            twoNext = twoCur.next;
            if(oneCur.no <= twoCur.no) {
                oneCur.next = finalHeroHead.next;
                finalHeroHead.next = oneCur;
                oneCur = oneNext;
            }else {
                twoCur.next = finalHeroHead.next;
                finalHeroHead.next = twoCur;
                twoCur = twoNext;
            }
        }
        head.next = finalHeroHead.next;
    }
}

//定义SingleLinkedList来管理我们的英雄任务
class SingleLinkedList {
    //初始化一个头节点 不存储具体的数据
    private HeroNode head = new HeroNode(0, "", "");

    public HeroNode getHead() {
        return head;
    }





    /**
     * （通过栈的方式实现单链表的逆序打印）
     * 栈的特点是先入后出  正好可以满足逆序打印
     * 单链表的逆序打印
     */
    public void reversePrint(HeroNode heroNode) {
        //先判断当前的链表是否为空  或者当前的链表只有一个节点
        if (heroNode.next == null) {
            System.out.println("当前链表为空,无法逆序打印!");
            return;
        }
        //创建一个栈，将各个节点压入栈中
        //先创建一个栈
        Stack<HeroNode> stack = new Stack<>();
        HeroNode cur = heroNode.next;
        //循环将每一个节点添加进栈中
        while (cur != null) {
            stack.push(cur);//将节点压入栈中
            cur = cur.next;//cur后移 压入下一个节点
        }
        //将栈中节点打印
        while (stack.size() > 0) {
            System.out.println(stack.pop());
        }
    }


    /**
     * 单链表的反转
     *
     * @param heroNode 需要反转单链表的头节点
     */
    public void reverseHeroNode(HeroNode heroNode) {
        //先判断当前的链表是否为空  或者当前的链表只有一个节点
        if (heroNode.next == null || heroNode.next.next == null) {
            System.out.println("当前链表为空或者只有一个节点,无需反转");
            return;
        }
        //定义一个辅助的变量  帮助我们遍历原来的链表
        HeroNode cur = heroNode.next;
        HeroNode next = null;//指向当前节点的下一个节点 我们要在挪动当前节点之前帮当前指针 下移
        HeroNode reverseHeroNode = new HeroNode(0, "", "");//新链表的头节点
        //遍历原先的列表 确定每一个链表的指向关系
        while (cur != null) {
            next = cur.next;//保存当前节点的下一个节点
            //reverseHeroNode.next表示头节点的下一个节点   我们让cur的下一个节点（cur.next）指向头节点的下一个节点（reverseHeroNode.next） 就把当前的节点（cur）穿插进去了
            //下一句将头节点和当前节点建立关系reverseHeroNode.next = cur  整个节点就连接起来了
            cur.next = reverseHeroNode.next;//将cur的下一个节点指向新的链表的最前端 相当于在头节点和头节点的下一个节点之间穿插了一个节点
            reverseHeroNode.next = cur;//将cur连接到新的链表上
            cur = next; //cur像后移动
        }
        //将head.next指向reverseHeroNode.next 实现单链表的反转
        heroNode.next = reverseHeroNode.next;
    }


    /**
     * 查找单链表中的倒数第K个节点
     *
     * @param index    倒数第几
     * @param heroNode 头节点
     * @return 倒数第K个节点的信息
     */
    public HeroNode getHeroNodeByLastIndex(int index, HeroNode heroNode) {
        //先判断节点是否为空
        if (heroNode.next == null) {
            return null;
        }
        //首先获取有效节点的个数
        int length = this.getLength(heroNode);//使用求节点有效个数的方法
        //求倒数第k个节点就是在求正数第（length - index + 1）节点
        index = length - index;  //求出正向的索引位置
        if (index < 0 || index > length) {
            System.out.println("所求的在链表中不存在");
            return null;
        }
        int count = 0;
        HeroNode temp = heroNode.next;
        while (true) {
            if (count == index) {
                return temp;
            }
            count++;
            temp = temp.next;
        }
    }

    /**
     * 获取有效节点的个数（如果是带头节点的链表，需求不统计头节点）
     *
     * @param heroNode 头节点
     * @return 有效节点的个数
     */
    public int getLength(HeroNode heroNode) {
        //先判断节点是否为空
        if (heroNode.next == null) {
            return 0;
        }
        //遍历节点进行统计
        int length = 0;//有效节点的个数
        HeroNode temp = heroNode.next;//这里没有统计头节点
        while (temp != null) {//遍历 统计个数
            length++;
            temp = temp.next;
        }
        return length;
    }


    /**
     * 删除链表中的节点
     * 根据节点的编号删除节点的信息
     */
    public void delete(int no) {
        //判断链表是否为空
        if (head.next == null) {
            System.out.println("链表为空,无法删除!");
            return;
        }
        //找到要删除的节点的信息
        HeroNode temp = head;
        boolean isDelete = false;//是否删除
        while (true) {
            if (temp.next == null) {
                break;
            }
            if (temp.next.no == no) {//这里的temp指的是要删除节点的上一个节点  temp.next.next指的是要删除节点的下一个节点
                //将当前节点的上一个节点指向当前节点的下一个节点
                temp.next = temp.next.next;  //将要删除的节点的上一个节点指向要删除节点的下一个节点  这样要删除的节点没有引用指向 会被垃圾回收机制回收
                isDelete = true;
                break;
            }
            temp = temp.next;
        }
        //做出判断,返回结果
        System.out.println(isDelete ? "删除成功" : "没有找到该节点的信息");
    }


    /**
     * 修改节点的信息
     * 根据新的节点的编号进行修改
     */
    public void update(HeroNode newHeroNode) {
        //判断链表是否为空
        if (head.next == null) {
            System.out.println("链表为空,无法修改该节点!");
            return;
        }
        //找到需要修改的节点
        //首先找到头节点的位置
        HeroNode temp = head.next;
        boolean idFind = false;  //是否找到节点的信息
        while (true) {
            if (temp == null) {
                break;//已经到了链表的结尾,就退出循环
            }
            if (temp.no == newHeroNode.no) {//找到修改的节点
                temp.name = newHeroNode.name;
                temp.nickname = newHeroNode.nickname;
                idFind = true; //找到了节点并且修改了节点的信息
                break;
            }
            temp = temp.next;
        }
        //做出判断,返回结果
        System.out.println(idFind ? "修改成功" : "没有找到该节点的信息");
    }


    /**
     * 添加节点到单向链表
     */
    public void add(HeroNode heroNode) {
        //找到当前链表的最后一个节点
        HeroNode temp = head;
        while (temp.next != null) {
            temp = temp.next;
        }
        temp.next = heroNode;
    }


    /**
     * 显示链表
     */
    public void list() {
        //先判断链表是否为空
        if (head.next == null) {
            System.out.println("链表为空!");
            return;
        }
        HeroNode temp = head;
        while (temp.next != null) {
            System.out.println(temp.next);
            temp = temp.next;
        }
    }


}

//定义一个heroNode,每个heroNode对象都是一个节点
class HeroNode {
    public int no;
    public String name;
    public String nickname;
    public HeroNode next;  //指向下一个节点

    //构造器
    public HeroNode(int no, String name, String nickname) {
        this.no = no;
        this.name = name;
        this.nickname = nickname;
    }

    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickname='" + nickname + '\'' +
                '}';
    }
}

4.3 双向链表

双向的链表的CRUD操作于单向链表的CRUD操作类似

image-20230507100730848

完整的增删改查代码

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
package com.atguigu.linkedlist;

/**
 * @author GongChangjiang
 * @version 1.0
 * @Date 2023/5/7
 * @Description 双向链表的使用
 */
public class DoubleLinkedListDemo {
    public static void main(String[] args) {
        DoubleLinkedList doubleLinkedList = new DoubleLinkedList();
        //测试添加链表的功能
        doubleLinkedList.add(new HeroNode2(1, "宋江", "及时雨"));
        doubleLinkedList.add(new HeroNode2(2, "卢俊义", "玉麒麟"));
        doubleLinkedList.add(new HeroNode2(3, "吴用", "智多星"));
        doubleLinkedList.add(new HeroNode2(4, "林冲", "豹子头"));
        //测试显示链表的功能
        doubleLinkedList.list();
        //测试删除双向链表中的节点
        doubleLinkedList.delete(2);
        doubleLinkedList.list();
        //测试修改双向链表中的节点
        doubleLinkedList.update(new HeroNode2(2, "卢俊义修改版", "玉麒麟"));
        doubleLinkedList.list();
        System.out.println("--------------");
        doubleLinkedList.orderAdd(new HeroNode2(3, "小卢", "玉麒麟"));
        doubleLinkedList.list();
    }
}

class DoubleLinkedList {
    //初始化一个头节点 不存储具体的数据
    private HeroNode2 head = new HeroNode2(0, "", "");

    //返回头节点的信息
    public HeroNode2 getHead() {
        return head;
    }


    /**
     * 双向链表的顺序添加
     * 应该有问题  不是参考答案
     */
    public void orderAdd(HeroNode2 heroNode) {
        //找到当前链表的最后一个节点
        HeroNode2 temp = head;
        boolean isSuccess = false;
        while (temp.next != null) {
            if (temp.next.no >= heroNode.no) {
                heroNode.next = temp.next;
                temp.next.pre = heroNode;
                temp.next = heroNode;
                heroNode.pre = temp;
                isSuccess = true;
                break;
            }
            temp = temp.next;
        }
        if (!isSuccess) {//没有添加成功 说明当前链表的序号超过了链表里面已有节点序号的最高值 直接添加到最后
            this.add(heroNode);
        }

    }


    /**
     * 删除双向链表中的一个节点
     */
    public void delete(int no) {
        //判断链表是否为空
        if (head.next == null) {
            System.out.println("链表为空,无法删除!");
            return;
        }
        //找到要删除的节点的信息
        HeroNode2 temp = head.next;
        boolean isDelete = false;//是否删除
        while (true) {
            if (temp == null) {
                break;
            }
            if (temp.no == no) {
                temp.pre.next = temp.next;
                if (temp.next != null) {
                    temp.next.pre = temp.pre;//这句话有个条件  temp不能是最后一个节点
                }
                isDelete = true;
                break;
            }
            temp = temp.next;
        }
        System.out.println(isDelete ? "删除成功" : "没有找到该节点的信息");
    }


    /**
     * 修改双向链表的信息
     */
    public void update(HeroNode2 newHeroNode) {
        //判断链表是否为空
        if (head.next == null) {
            System.out.println("链表为空,无法修改该节点!");
            return;
        }
        //找到需要修改的节点
        //首先找到头节点的位置
        HeroNode2 temp = head.next;
        boolean idFind = false;  //是否找到节点的信息
        while (true) {
            if (temp == null) {
                break;//已经到了链表的结尾,就退出循环
            }
            if (temp.no == newHeroNode.no) {//找到修改的节点
                temp.name = newHeroNode.name;
                temp.nickname = newHeroNode.nickname;
                idFind = true; //找到了节点并且修改了节点的信息
                break;
            }
            temp = temp.next;
        }
        //做出判断,返回结果
        System.out.println(idFind ? "修改成功" : "没有找到该节点的信息");
    }


    /**
     * 向双向链表中添加节点信息
     */
    public void add(HeroNode2 heroNode) {
        //找到当前链表的最后一个节点
        HeroNode2 temp = head;
        while (temp.next != null) {
            temp = temp.next;
        }
        temp.next = heroNode;
        heroNode.pre = temp;
    }


    /**
     * 显示链表
     */
    public void list() {
        //先判断链表是否为空
        if (head.next == null) {
            System.out.println("链表为空!");
            return;
        }
        HeroNode2 temp = head;
        while (temp.next != null) {
            System.out.println(temp.next);
            temp = temp.next;
        }
    }


}

//定义一个heroNode,每个heroNode对象都是一个节点
class HeroNode2 {
    public int no;
    public String name;
    public String nickname;
    public HeroNode2 next;  //指向下一个节点
    public HeroNode2 pre;//指向上一个节点

    //构造器
    public HeroNode2(int no, String name, String nickname) {
        this.no = no;
        this.name = name;
        this.nickname = nickname;
    }

    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickname='" + nickname + '\'' +
                '}';
    }
}

4.4 单向环形链表的应用场景(Josephu问题)

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

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

image-20230508104207815

image-20230508121934697

完整的代码

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
package com.atguigu.linkedlist;

/**
 * @author GongChangjiang
 * @version 1.0
 * @Date 2023/5/8
 * @Description 约瑟夫问题
 */
public class Josephu {
    public static void main(String[] args) {
        //测试构建环形链表
        CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList();
        circleSingleLinkedList.addBoy(5);
        //测试遍历环形单向链表
        circleSingleLinkedList.showBoy();
        //测试生成小孩出圈的序列
        circleSingleLinkedList.countBoy(1,2,5);
    }

}


//创建一个环形的单向链表
class CircleSingleLinkedList {
    //创建一个first节点，当前没有编号
    private Boy first = null;

    /**
     * 根据用户的输入产生一个出队编号的序列
     *
     * @param startNo  表示从第几个小孩开始数
     * @param countNum 表示数几下
     * @param nums     传入几个小孩
     */
    public void countBoy(int startNo, int countNum, int nums) {
        //先对输入的数据进行校验
        if (first == null || startNo < 0 || startNo > nums) {
            System.out.println("参数输入有误,请重新输入!");
            return;
        }
        //创建一个辅助指针
        Boy helper = first;
        //将helper指向环形链表的最后一个节点
        while (true) {
            if (helper.getNext() == first) {
                break;
            }
            helper = helper.getNext();
        }
        //将first和helper移动到指定的位置  考虑从第几个小孩开始数
        //小孩报数前，先让 first 和  helper 移动 k - 1次
        for (int i = 0; i < startNo - 1; i++) {
            first = first.getNext();
            helper = helper.getNext();
        }
        //让first和helper移动 m-1次，然后出圈
        //循环操作  直到圈中只有一个小孩节点
        while (true){
            if(helper == first){//说明圈中只有一个节点
                break;
            }
            //让first和helper移动 countNum - 1
            for (int i = 0; i < countNum - 1; i++) {
                first = first.getNext();
                helper = helper.getNext();
            }
            //这时first指向的节点就是要出圈的小孩
            System.out.printf("小孩%d出圈\n",first.getNo());
            //将first指向的小孩出圈
            first = first.getNext();
            helper.setNext(first);
        }
        System.out.printf("最后留在圈中小孩编号是:%d \n",helper.getNo());
    }


    /**
     * 遍历当前的环形链表
     */
    public void showBoy() {
        //先判断链表是不是为空
        if (first == null) {
            System.out.println("环形链表为空！");
            return;
        }
        //创建一个辅助指针
        Boy curBoy = first;
        while (true) {
            System.out.printf("小孩的编号:%d \n", curBoy.getNo());
            if (curBoy.getNext() == first) {//说明已经循环一圈了  就不在循环  退出了
                break;
            }
            //向后移动
            curBoy = curBoy.getNext();
        }
    }


    /**
     * 添加小孩节点 构建成一个环形的链表
     *
     * @param nums 传入几个小孩
     */
    public void addBoy(int nums) {
        //将传入的数据进行一个校验
        if (nums < 1) {//传入小孩的的数量不能小于一
            System.out.println("输入的值不正确!");
            return;
        }
        Boy curBoy = null;//辅助指针,帮助构建环形链表
        //使用循环创建我们的环形链表
        for (int i = 1; i <= nums; i++) {  //要加入几个小孩 就循环几次
            //根据编号创建小孩节点
            Boy boy = new Boy(i);
            //将小孩加入到环形链表中
            if (i == 1) {//说明是第一个小孩
                first = boy;
                first.setNext(first);//添加的第一个节点 先自己指向自己 构建成一个环
                curBoy = first; //first节点我们不能动 使用辅助节点
            } else {
                //这是在循环里面 每次循环之后  小孩节点都不一样
                curBoy.setNext(boy);
                boy.setNext(first); //形成回路
                curBoy = boy;//curBoy每次指向的都是最后一个小孩节点
            }
        }
    }

}

//创建一个boy类 表示一个节点
class Boy {
    private int no; //编号
    private Boy next;//指向下一个节点  默认是null

    public Boy(int no) {
        this.no = no;
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public Boy getNext() {
        return next;
    }

    public void setNext(Boy next) {
        this.next = next;
    }
}

五.栈

1.介绍

1)栈的英文为(stack)

2)栈是一个先入后出(FILO-First In Last Out)的有序列表。

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

4)根据栈的定义可知，最先放入栈中元素在栈底，最后放入的元素在栈顶，而删除元素刚好相反，最后放入的元素最先删除，最先放入的元素最后删除

2.应用场景

1)子程序的调用：在跳往子程序前，会先将下个指令的地址存到堆栈中，直到子程序执行完后再将地址取出，以回到原来的程序中。

2)处理递归调用：和子程序的调用类似，只是除了储存下一个指令的地址外，也将参数、区域变量等数据存入堆栈中。

3)表达式的转换[中缀表达式转后缀表达式]与求值(实际解决)。

4)二叉树的遍历。

5)图形的深度优先(depth一first)搜索法。

3.图解

image-20230510101713914

image-20230510101722707

4.使用数组模拟栈

image-20230510101916230

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
package com.atguigu.stack;

/**
 * @author GongChangjiang
 * @version 1.0
 * @Date 2023/5/10
 * @Description 使用数组模拟栈
 */
public class ArrayStackDemo {
    public static void main(String[] args) {
        ArrayStack stack = new ArrayStack(5);
        //入栈
        stack.push(1);
        stack.push(2);
        stack.push(3);
        //出栈
        System.out.println("出栈的数是:"+stack.pop());
        //显示栈中所有的数据
        stack.list();
    }
}

//定义一个ArrayStack表示栈
class ArrayStack {
    private int maxSize;//栈的大小
    private int[] stack;//数组 数组模拟栈 数据放在数组中
    private int top = -1;  //top表示栈顶 初始化为1

    //构造器
    public ArrayStack(int maxSize) {
        this.maxSize = maxSize;
        //完成数组的初始化
        stack = new int[maxSize];
    }

    /**
     * 判断是否栈满
     */
    public boolean isFull() {
        return top == maxSize - 1;
    }

    /**
     * 判断栈是否为空
     */
    public boolean isEmpty() {
        return top == -1;
    }


    /**
     * 入栈的操作
     */
    public void push(int value) {
        //先判断栈是否为满
        if (isFull()) {
            System.out.println("栈满,无法添加数据!");
            return;
        }
        top++;
        stack[top] = value;
    }

    /**
     * 出栈的操作
     * 将栈顶的数据返回
     */
    public int pop() {
        //先判断栈是否为空
        if (isEmpty()) {
            throw new RuntimeException("栈空,无法取出数据!");
        }
        //取出数据
        int value = stack[top];
        top--;
        return value;
    }

    /**
     * 显示栈的情况
     */
    public void list() {
        //先判断栈是否为空
        if (isEmpty()) {
            System.out.println("栈空,无法取出数据!");
            return;
        }
        for (int i = top; i >= 0; i--) {
            System.out.printf("stack[%d] = %d \n", i, stack[i]);
        }
    }

}

5.栈实现综合计算器

中缀表达式

image-20230510105251076

image-20230510110403055

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
package com.atguigu.stack;

/**
 * @author GongChangjiang
 * @version 1.0
 * @Date 2023/5/10
 * @Description 综合计算器
 */
public class Calculator {
    public static void main(String[] args) {
        /**
         * 1. 通过一个 index  值（索引），来遍历我们的表达式
         * 2. 如果我们发现是一个数字, 就直接入数栈
         * 3. 如果发现扫描到的是一个符号,  就分如下情况
         * 3.1 如果发现当前的符号栈为 空，就直接入栈
         * 3.2 如果符号栈有操作符，就进行比较,如果当前的操作符的优先级小于或者等于栈中的操作符， 就需要从数栈中pop出两个数,在从符号栈中pop出一个符号，进行运算，将得到结果，入数栈，然后将当前的操作符入符号栈， 如果当前的操作符的优先级大于栈中的操作符， 就直接入符号栈.
         * 4. 当表达式扫描完毕，就顺序的从 数栈和符号栈中pop出相应的数和符号，并运行.
         * 5. 最后在数栈只有一个数字，就是表达式的结果
         */
        String expression = "30+2*6-2";
        //创建两个栈 一个是数栈  一个是符号栈
        ArrayStack2 numStack = new ArrayStack2(10);
        ArrayStack2 operStack = new ArrayStack2(10);
        //定义需要的相关变量
        int index = 0;//用于扫描
        int num1 = 0;
        int num2 = 0;
        int oper = 0;
        int result = 0;
        char ch = ' '; //将每次扫描得到的char保存在ch中
        String keepNum = "";//用于拼接多位数的
        while (true) {
            //得到expression的每一个字符
            ch = expression.substring(index, index + 1).charAt(0);
            //判断ch是什么 做相应的处理
            if (operStack.isOper(ch)) {
                //先符号栈判断是不是为空
                if (!operStack.isEmpty()) { //判断符号栈是否为空
                    //不为空的情况
                    if (operStack.priority(ch) <= operStack.priority(operStack.peek())) {
                        //如果当前的操作符的优先级小于或者等于栈中的操作符， 就需要从数栈中pop出两个数,
                        // 在从符号栈中pop出一个符号，进行运算，将得到结果，入数栈
                        num1 = numStack.pop();
                        num2 = numStack.pop();
                        oper = operStack.pop();
                        result = numStack.cal(num1, num2, oper);
                        //将运算的结果入数栈
                        numStack.push(result);
                        //将当前的操作符入符号栈
                        operStack.push(ch);
                    } else {
                        //如果当前的操作符的优先级大于栈中的操作符， 就直接入符号栈.
                        operStack.push(ch);
                    }
                } else {
                    //如果为空  直接入栈
                    operStack.push(ch);
                }
            } else {
                //如果是数字 就直接入数栈
                //要考虑是多位数的情况
                keepNum += ch;
                //如果ch是表达式的最后一位 就直接入栈
                if (index == expression.length() - 1) {
                    numStack.push(Integer.parseInt(keepNum));
                } else {
                    //判断下一个字符是不是数字  如果是数字 就继续扫描 如果是运算符 则入栈
                    if (operStack.isOper(expression.substring(index + 1, index + 2).charAt(0))) {//下一位是操作符
                        //直接将当前为添加到数栈
                        numStack.push(Integer.parseInt(keepNum));
                        //清空keepNum
                        keepNum = "";
                    }
                }
            }
            //让index + 1 ，并判断是否扫描到表达式的最后
            index++;
            if (index >= expression.length()) {
                break;
            }
        }
        //当表达式扫描完毕，就顺序的从 数栈和符号栈中pop出相应的数和符号，并运行.
        while (true) {
            //如果符号栈为空 则计算结束 数栈中只有 一个数字
            if (operStack.isEmpty()) {
                break;
            }
            num1 = numStack.pop();
            num2 = numStack.pop();
            oper = operStack.pop();
            result = numStack.cal(num1, num2, oper);
            numStack.push(result);
        }
        System.out.printf("表达式:%s = %d", expression, numStack.pop());
    }
}

//定义一个ArrayStack表示栈
class ArrayStack2 {
    private int maxSize;//栈的大小
    private int[] stack;//数组 数组模拟栈 数据放在数组中
    private int top = -1;  //top表示栈顶 初始化为1

    //构造器
    public ArrayStack2(int maxSize) {
        this.maxSize = maxSize;
        //完成数组的初始化
        stack = new int[maxSize];
    }

    /**
     * 判断是否栈满
     */
    public boolean isFull() {
        return top == maxSize - 1;
    }

    /**
     * 判断栈是否为空
     */
    public boolean isEmpty() {
        return top == -1;
    }


    /**
     * 入栈的操作
     */
    public void push(int value) {
        //先判断栈是否为满
        if (isFull()) {
            System.out.println("栈满,无法添加数据!");
            return;
        }
        top++;
        stack[top] = value;
    }

    /**
     * 出栈的操作
     * 将栈顶的数据返回
     */
    public int pop() {
        //先判断栈是否为空
        if (isEmpty()) {
            throw new RuntimeException("栈空,无法取出数据!");
        }
        //取出数据
        int value = stack[top];
        top--;
        return value;
    }

    /**
     * 显示栈的情况
     */
    public void list() {
        //先判断栈是否为空
        if (isEmpty()) {
            System.out.println("栈空,无法取出数据!");
            return;
        }
        for (int i = top; i >= 0; i--) {
            System.out.printf("stack[%d] = %d \n", i, stack[i]);
        }
    }


    /**
     * 返回运算符的优先级
     * 优先级由数字表示
     * 数字大 优先级高
     */
    public int priority(int oper) {
        if (oper == '*' || oper == '/') {
            return 1;
        } else if (oper == '+' || oper == '-') {
            return 0;
        } else {
            return -1;
        }
    }


    /**
     * 判断是不是一个运算符
     */
    public boolean isOper(char val) {
        return val == '+' || val == '-' || val == '*' || val == '/';
    }

    /**
     * 计算方法
     */
    public int cal(int num1, int num2, int oper) {
        int result = 0;
        switch (oper) {
            case '+':
                result = num1 + num2;
                break;
            case '-':
                result = num2 - num1;  //注意顺序
                break;
            case '*':
                result = num1 * num2;
                break;
            case '/':
                result = num2 / num1;
        }
        return result;
    }

    /**
     * 查看栈顶数据的方法
     * 返回栈顶的值  不是pop出来
     */
    public int peek() {
        return stack[top];
    }


}

6.逆波兰计算器的设计与实现

逆波兰表达式(后缀表达式)

1)输入一个逆波兰表达式(后缀表达式)，使用栈(Stack),计算其结果

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
package com.atguigu.stack;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @author GongChangjiang
 * @version 1.0
 * @Date 2023/5/11
 * @Description 逆波兰计算器的设计与实现
 */
public class PolandNotation {
    public static void main(String[] args) {
        //先定义一个逆波兰表达式
        //(3+4)×5-6 的逆波兰表达式是 3 4 + 5 × 6 -
        //为了方便 逆波兰表达式的数字和符号有空格隔开
        String suffixExpression = "3 4 + 5 * 6 -";//中间有空格隔开
        //1.先将suffixExpression放入到List集合中
        //2.将List集合传递给一个方法 配合栈 完成计算
        List<String> rpnList = getListString(suffixExpression);
        System.out.println("计算的结果是:"+calculate(rpnList));


    }

    //将一个逆波兰表达式依次将数据和运算符放入到List集合中
    public static List<String> getListString(String suffixExpression) {
        //将suffixExpression按照空格分割
        String[] strings = suffixExpression.split(" ");
        List<String> list = new ArrayList<>();
        for (String string : strings) {
            list.add(string);
        }
        return list;
    }

    /**
     * 从左至右扫描，将3和4压入堆栈；
     * 遇到+运算符，因此弹出4和3（4为栈顶元素，3为次顶元素），计算出3+4的值，得7，再将7入栈；
     * 将5入栈；
     * 接下来是×运算符，因此弹出5和7，计算出7×5=35，将35入栈；
     * 将6入栈；
     * 最后是-运算符，计算出35-6的值，即29，由此得出最终结果
     */
    public static int calculate(List<String> list) {
        //创建一个栈
        Stack<String> stack = new Stack<>();
        //遍历list
        for (String item : list) {
            //使用正则表达式取出数字
            if (item.matches("\\d+")) { //匹配的是多位数
                //入栈
                stack.push(item);
            } else {
                //弹出两个数 并运算 再入栈
                int num2 = Integer.parseInt(stack.pop());
                int num1 = Integer.parseInt(stack.pop());
                //运算
                int res = 0;
                if (item.equals("+")) {
                    res = num1 + num2;
                } else if (item.equals("-")) {
                    res = num1 - num2;
                } else if (item.equals("*")) {
                    res = num1 * num2;
                } else if (item.equals("/")) {
                    res = num1 / num2;
                }else {
                    throw new RuntimeException("运算符有误!");
                }
                //把结果入栈
                stack.push(res + "");
            }
        }
        //最后留在stack中的数就是运算结果
        return Integer.parseInt(stack.pop());
    }
}

将中缀表达式转化为后缀表达式（逆波兰表达式）

解题的步骤:

1)初始化两个栈：运算符栈s1和储存中间结果的栈s2；

2)从左至右扫描中缀表达式；

3)遇到操作数时，将其压s2；

4)遇到运算符时，比较其与s1栈顶运算符的优先级：

​ (1)如果s1为空，或栈顶运算符为左括号“(”，则直接将此运算符入栈；

​ (2)否则，若优先级比栈顶运算符的高，也将运算符压入s1；

​ (3)否则，将s1栈顶的运算符弹出并压入到s2中，再次转到(4-1)与s1中新的栈顶运算符相比较

5)遇到括号时：
(1) 如果是左括号“(”，则直接压入s1
(2) 如果是右括号“)”，则依次弹出s1栈顶的运算符，并压入s2，直到遇到左括号为止，此时将这一对括号丢弃

6)重复步骤2至5，直到表达式的最右边

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

8)依次弹出s2中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式

image-20230511094011546

先将中缀表达式转化成list集合

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
/**
    * 将中缀表达式转化成对应的list
    * @param expression 中缀表达式
    * @return 中缀表达式转化成的一个list集合
    */
   public static List<String> toInfixExpressionList(String expression) {
       //定义一个集合，存储中缀表达式对应的list集合
       List<String> list = new ArrayList<>();
       int i = 0;//这个是一个指针 用于遍历中缀表达式的字符串
       String str;//做多位数的拼接工作 ,因为我们要考虑多位数的情况
       char c;//每遍历一个字符就放入到c中
       do {
           if ((c = expression.charAt(i)) < 48 || (c = expression.charAt(i)) > 57) { //如果c是一个非数字的字符需要加入到ls中
               list.add(c + ""); //直接将这个字符添加到list集合中
               i++;
           } else {//如果是一个数 要考虑多位数的问题
               str = "";//先将str置空
               while (i < expression.length() && (c = expression.charAt(i)) >= 48 && (c = expression.charAt(i)) <= 57) {
                   str += c;
                   i++;
               }
               list.add(str);
           }
       } while (i < expression.length());
       return list;
   }

将中缀表达式的集合转化成逆波兰表达式（后缀表达式）的集合

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
/**
    * 将中缀表达式对应的List转化成后缀表达式对应的list
    * tips:
    * 1)初始化两个栈：运算符栈s1和储存中间结果的栈s2；
    * 2)从左至右扫描中缀表达式；
    * 3)遇到操作数时，将其压s2；
    * 4)遇到运算符时，比较其与s1栈顶运算符的优先级：
    * (1)如果s1为空，或栈顶运算符为左括号“(”，则直接将此运算符入栈；
    * (2)否则，若优先级比栈顶运算符的高，也将运算符压入s1；
    * (3)否则，将s1栈顶的运算符弹出并压入到s2中，再次转到(4-1)与s1中新的栈顶运算符相比较
    * 5)遇到括号时：
    * (1) 如果是左括号“(”，则直接压入s1
    * (2) 如果是右括号“)”，则依次弹出s1栈顶的运算符，并压入s2，直到遇到左括号为止，此时将这一对括号丢弃
    * 6)重复步骤2至5，直到表达式的最右边
    * 7)将s1中剩余的运算符依次弹出并压入s2
    * 8)依次弹出s2中的元素并输出，**结果的逆序即为中缀表达式对应的后缀表达式**
    *
    * @param ls 中缀表达式对应的list
    * @return 后缀表达式对应的list
    */
   public static List<String> parseSuffixExpressionList(List<String> ls) {
       //定义栈
       Stack<String> s1 = new Stack<>();//符号栈 s1栈
       //说明:因为思路分析中使用的s2的栈在整个的运算的过程中没有进行pop的操作  我们直接使用list集合代替s2栈 （同时也为了方便后面逆序的输出）
       ArrayList<String> s2 = new ArrayList<>();//用于存储中间结果的list
       //遍历ls
       for (String item : ls) {
           //如果是一个数 就加入到s2栈
           if (item.matches("\\d+")) {//正则匹配
               s2.add(item);
           } else if (item.equals("(")) { //如果是s1的话就直接入符号栈
               s1.push(item);
           } else if (item.equals(")")) {
               //如果是右括号“)”，则依次弹出s1栈顶的运算符，并压入s2，直到遇到左括号为止，此时将这一对括号丢弃
               while (!s1.peek().equals("(")) {
                   s2.add(s1.pop());
               }
               s1.pop();//将（弹出s1栈,这里的操作就是消除括号
           } else {//加减乘除的操作
               //当item的优先级小于栈顶的优先级，
               // 将s1栈顶的运算符弹出并加入到s2中，再次转到(4.1)与s1中新的栈顶运算符相比较
               while (s1.size() != 0 && getVal(s1.peek()) >= getVal(item)) {
                   s2.add(s1.pop());
               }
               //还需要将item压入栈中
               s1.push(item);
           }
       }
       //将s1中剩余的运算符依次弹出并加入s2
       while (s1.size() != 0) {
           s2.add(s1.pop());
       }
       return 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
31
32
33
34
35
36
37
38
/**
     * 通过一个后缀表达式的list集合得到表达式最终的计算结果
     * @param list 后缀表达式的list集合
     * @return 根据后缀表达式的集合计算出的表达式的结果信息
     */
    public static int calculate(List<String> list) {
        //创建一个栈
        Stack<String> stack = new Stack<>();
        //遍历list
        for (String item : list) {
            //使用正则表达式取出数字
            if (item.matches("\\d+")) { //匹配的是多位数
                //入栈
                stack.push(item);
            } else {
                //弹出两个数 并运算 再入栈
                int num2 = Integer.parseInt(stack.pop());
                int num1 = Integer.parseInt(stack.pop());
                //运算
                int res = 0;
                if (item.equals("+")) {
                    res = num1 + num2;
                } else if (item.equals("-")) {
                    res = num1 - num2;
                } else if (item.equals("*")) {
                    res = num1 * num2;
                } else if (item.equals("/")) {
                    res = num1 / num2;
                } else {
                    throw new RuntimeException("运算符有误!");
                }
                //把结果入栈
                stack.push(res + "");
            }
        }
        //最后留在stack中的数就是运算结果
        return Integer.parseInt(stack.pop());
    }

完整的代码

(不支持小数)

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
package com.atguigu.stack;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @author GongChangjiang
 * @version 1.0
 * @Date 2023/5/11
 * @Description 逆波兰计算器的设计与实现
 */
public class PolandNotation {
    public static void main(String[] args) {
        //先定义一个逆波兰表达式
        //(3+4)×5-6 的逆波兰表达式是 3 4 + 5 × 6 -
        //为了方便 逆波兰表达式的数字和符号有空格隔开
        String suffixExpression = "3 4 + 5 * 6 -";//中间有空格隔开
        //1.先将suffixExpression放入到List集合中
        //2.将List集合传递给一个方法 配合栈 完成计算
        List<String> rpnList = getListString(suffixExpression);
        System.out.println("计算的结果是:" + calculate(rpnList));

        //测试将中缀表达式转化成逆波兰表达式
        //完成一个将中缀表达式 转换为一个后缀表达式
        //1.  1+((2+3)×4)-5(中缀表达式) -> 1 2 3 + 4 × + 5 –(后缀表达式)
        //2.  将中缀表达式转化成List集合
        String expression = "1+((2+3)*4)-5";
        List<String> list = toInfixExpressionList(expression);
        System.out.println("中缀表达式对应的List:" + list);
        //3.将得到的中缀表达式对应的List 转换成一个逆波兰表达式(后缀表达式)对应的List
        List<String> stringList = parseSuffixExpressionList(list);
        System.out.println("中缀表达式对应的List:" + stringList);
        System.out.println("计算的结果:" + calculate(stringList));


    }

    /**
     * 输入一个运算符 返回对应的优先级
     */
    public static int getVal(String operation) {
        int res = 0;
        switch (operation) {
            case "+":
            case "-":
                res = 1;
                break;
            case "/":
            case "*":
                res = 2;
                break;
            default:
                break;
        }
        return res;
    }

    /**
     * 将中缀表达式对应的List转化成后缀表达式对应的list
     * tips:
     * 1)初始化两个栈：运算符栈s1和储存中间结果的栈s2；
     * 2)从左至右扫描中缀表达式；
     * 3)遇到操作数时，将其压s2；
     * 4)遇到运算符时，比较其与s1栈顶运算符的优先级：
     * (1)如果s1为空，或栈顶运算符为左括号“(”，则直接将此运算符入栈；
     * (2)否则，若优先级比栈顶运算符的高，也将运算符压入s1；
     * (3)否则，将s1栈顶的运算符弹出并压入到s2中，再次转到(4-1)与s1中新的栈顶运算符相比较
     * 5)遇到括号时：
     * (1) 如果是左括号“(”，则直接压入s1
     * (2) 如果是右括号“)”，则依次弹出s1栈顶的运算符，并压入s2，直到遇到左括号为止，此时将这一对括号丢弃
     * 6)重复步骤2至5，直到表达式的最右边
     * 7)将s1中剩余的运算符依次弹出并压入s2
     * 8)依次弹出s2中的元素并输出，**结果的逆序即为中缀表达式对应的后缀表达式**
     *
     * @param ls 中缀表达式对应的list
     * @return 后缀表达式对应的list
     */
    public static List<String> parseSuffixExpressionList(List<String> ls) {
        //定义栈
        Stack<String> s1 = new Stack<>();//符号栈 s1栈
        //说明:因为思路分析中使用的s2的栈在整个的运算的过程中没有进行pop的操作  我们直接使用list集合代替s2栈 （同时也为了方便后面逆序的输出）
        ArrayList<String> s2 = new ArrayList<>();//用于存储中间结果的list
        //遍历ls
        for (String item : ls) {
            //如果是一个数 就加入到s2栈
            if (item.matches("\\d+")) {//正则匹配
                s2.add(item);
            } else if (item.equals("(")) { //如果是s1的话就直接入符号栈
                s1.push(item);
            } else if (item.equals(")")) {
                //如果是右括号“)”，则依次弹出s1栈顶的运算符，并压入s2，直到遇到左括号为止，此时将这一对括号丢弃
                while (!s1.peek().equals("(")) {
                    s2.add(s1.pop());
                }
                s1.pop();//将（弹出s1栈,这里的操作就是消除括号
            } else {//加减乘除的操作
                //当item的优先级小于栈顶的优先级，
                // 将s1栈顶的运算符弹出并加入到s2中，再次转到(4.1)与s1中新的栈顶运算符相比较
                while (s1.size() != 0 && getVal(s1.peek()) >= getVal(item)) {
                    s2.add(s1.pop());
                }
                //还需要将item压入栈中
                s1.push(item);
            }
        }
        //将s1中剩余的运算符依次弹出并加入s2
        while (s1.size() != 0) {
            s2.add(s1.pop());
        }
        return s2;
    }

    /**
     * 将中缀表达式转化成对应的list
     *
     * @param expression 中缀表达式
     * @return 中缀表达式转化成的一个list集合
     */
    public static List<String> toInfixExpressionList(String expression) {
        //定义一个集合，存储中缀表达式对应的list集合
        List<String> list = new ArrayList<>();
        int i = 0;//这个是一个指针 用于遍历中缀表达式的字符串
        String str;//做多位数的拼接工作 ,因为我们要考虑多位数的情况
        char c;//每遍历一个字符就放入到c中
        do {
            if ((c = expression.charAt(i)) < 48 || (c = expression.charAt(i)) > 57) { //如果c是一个非数字的字符需要加入到ls中
                list.add(c + ""); //直接将这个字符添加到list集合中
                i++;
            } else {//如果是一个数 要考虑多位数的问题
                str = "";//先将str置空
                //这个只要遍历的有一个字符不是数字 就会退出while循环
                while (i < expression.length() && (c = expression.charAt(i)) >= 48 && (c = expression.charAt(i)) <= 57) {
                    str += c;
                    i++;
                }
                list.add(str);
            }
        } while (i < expression.length());
        return list;
    }


    //将一个逆波兰表达式依次将数据和运算符放入到List集合中
    public static List<String> getListString(String suffixExpression) {
        //将suffixExpression按照空格分割
        String[] strings = suffixExpression.split(" ");
        List<String> list = new ArrayList<>();
        for (String string : strings) {
            list.add(string);
        }
        return list;
    }

    /**
     * 通过一个后缀表达式的list集合得到表达式最终的计算结果
     *
     * @param list 后缀表达式的list集合
     * @return 根据后缀表达式的集合计算出的表达式的结果信息
     */
    public static int calculate(List<String> list) {
        //创建一个栈
        Stack<String> stack = new Stack<>();
        //遍历list
        for (String item : list) {
            //使用正则表达式取出数字
            if (item.matches("\\d+")) { //匹配的是多位数
                //入栈
                stack.push(item);
            } else {
                //弹出两个数 并运算 再入栈
                int num2 = Integer.parseInt(stack.pop());
                int num1 = Integer.parseInt(stack.pop());
                //运算
                int res = 0;
                if (item.equals("+")) {
                    res = num1 + num2;
                } else if (item.equals("-")) {
                    res = num1 - num2;
                } else if (item.equals("*")) {
                    res = num1 * num2;
                } else if (item.equals("/")) {
                    res = num1 / num2;
                } else {
                    throw new RuntimeException("运算符有误!");
                }
                //把结果入栈
                stack.push(res + "");
            }
        }
        //最后留在stack中的数就是运算结果
        return Integer.parseInt(stack.pop());
    }
}

完整的逆波兰计算器，含小数点的计算

(老师的代码)

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
package com.atguigu.stack;


import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Stack;
import java.util.regex.Pattern;

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
     * @throws Exception
     */
    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.简单介绍

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

image-20230511123527496

2.入门案例

image-20230511123245408

3.递归解决的问题

1)各种数学问题如: 8皇后问题 , 汉诺塔, 阶乘问题, 迷宫问题, 球和篮子的问题(google编程大赛)

2)各种算法中也会使用到递归，比如快排，归并排序，二分查找，分治算法等.

3)将用栈解决的问题–>第归代码比较简洁

4.递归遵循的规则

1)执行一个方法时，就创建一个新的受保护的独立空间(栈空间)

2)方法的局部变量是独立的，不会相互影响, 比如n变量

3)如果方法中使用的是引用类型变量(比如数组)，就会共享该引用类型的数据.

4)递归必须向退出递归的条件逼近，否则就是无限递归,出现StackOverflowError，死龟了:)

5)当一个方法执行完毕，或者遇到return，就会返回，遵守谁调用，就将结果返回给谁，同时当方法执行完毕或者返回时，该方法也就执行完毕。

5.递归的实际应用

5.1递归解决迷宫问题

image-20230512092144712

代码实现

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
package com.atguigu.recursion;

/**
 * @author GongChangjiang
 * @version 1.0
 * @Date 2023/5/12
 * @Description 递归解决迷宫问题
 */
public class MiGong {
    public static void main(String[] args) {
        //创建一个二维数组模拟迷宫
        //地图
        int[][] map = new int[8][7];
        //使用1表示墙的位置
        //把四周变成墙
        //将上下变成墙
        for (int i = 0; i < 7; i++) {
            map[0][i] = 1;
            map[7][i] = 1;
        }
        //将左右变成墙
        for (int i = 0; i < 8; i++) {
            map[i][0] = 1;
            map[i][6] = 1;
        }
        //设置自定义的墙的位置
        map[3][1] = 1;
        map[3][2] = 1;

        //输出地图
        showMap(map);
        //使用递归回溯给小球找路
        getWay(map, 1, 1);
        System.out.println("标识过的路");
        showMap(map);


    }

    /**
     * 遍历输出地图的信息
     *
     * @param map 地图组成的二维数组
     */
    public static void showMap(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.表示该位置已经走过 但是走不通
     * 在就走迷宫的时候我们要确定一个策略  比如下->右->上->左  如果该点走不通  再回溯
     * 使用递归的方法给小球找路
     *
     * @param map 传进来的地图信息
     * @param i   从哪个位置开始找
     * @param j   从哪个位置开始找
     * @return 是否找到路
     */
    public static boolean getWay(int[][] map, int i, int j) {
        if (map[6][5] == 2) { //说明通路已经找到了 就直接退出
            return true;
        } else {
            if (map[i][j] == 0) {//如果当前这个点还没有走过
                //按照策略走 下->右->上->左
                map[i][j] = 2;//先假定这个点可以走通
                if (getWay(map, i + 1, j)) { //向下走
                    return true;
                } else if (getWay(map, i, j + 1)) {//向右走
                    return true;
                } else if (getWay(map, i - 1, j)) {//向上走
                    return true;
                } else if (getWay(map, i, j - 1)) {//向左走
                    return true;
                } else {//四个方向都走不通的话说明不是一个通路 设置成false
                    map[i][j] = 3;
                    return false;
                }
            } else {//不为0 可以是1,2,3
                //可以理解为只走没有走过的
                return false;
            }

        }
    }


}

5.2 递归解决八皇后问题

使用回溯算法解决 类似于穷举法 后期使用别的算法优化

问题介绍

image-20230512112050729

思路分析

image-20230512112456731

代码实现

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
package com.atguigu.recursion;

/**
 * @author GongChangjiang
 * @version 1.0
 * @Date 2023/5/13
 * @Description 八皇后问题的解题思路及代码实现
 */
public class Queue8 {
    public static void main(String[] args) {
        Queue8 queue8 = new Queue8();
        queue8.check(0);
    }

    //定义一个max表示共有多少个皇后
    int max = 8;
    //定义一个一维数组 记录皇后在列上的位置 arr[8] = {0 , 4, 7, 5, 2, 6, 1, 3}
    int[] array = new int[max];
    //记录摆法的次数
    int count = 0;

    /**
     * 编写一个方法  放置n个皇后
     * 会自己回溯
     */
    public void check(int n) {
        if (n == max) { //说明已经放到了第九个皇后了
            print(); //打印
            return;
        }
        //依次放入皇后 判断是否冲突
        for (int i = 0; i < max; i++) {
            //先把当前的这个皇后n，放到该行的第i列
            array[n] = i;
            //判断当前放置第n个皇后到i列时，与前面放置的皇后是否冲突
            if (judge(n)) { //不冲突
                //接着放n+1个皇后
                check(n + 1);
            }
            //如果冲突 就继续执行 array[n] = i  就皇后在本行后移一个位置
            //因为在循环里面  i++会自增 n会后移
        }
    }

    /**
     * 当我们放置了n个皇后之后 就去检测
     * 该皇后是否和前面已经摆放的皇后冲突
     *
     * @param n 表示第n个皇后
     */
    public boolean judge(int n) {
        for (int i = 0; i < n; i++) {
            // array[8] = {0 , 4, 7, 5, 2, 6, 1, 3}   再次注意这里数组记录的是每个皇后在列上的值
            //array[i] == array[i] 判断是不是在同一列
            //Math.abs(n - i) == Math.abs(array[n] - array[i]) 判断是不是在同一斜线上
            //自己的理解:(n -i) 相当于在行上的距离   array[n] - array[i]相当于在列上的距离  行距离等于列距离 说明二者在同一斜线上
            if (array[i] == array[n] || Math.abs(n - i) == Math.abs(array[n] - array[i])) {//与前面放置的位置是否冲突
                return false;
            }
        }
        return true;
    }

    /**
     * 定义一个数组 打印皇后拜访的位置
     */
    public void print() {
        System.out.println("第" + (++count) + "中摆法");
        int[][] arr = new int[max][max];
        for (int i = 0; i < array.length; i++) {
            arr[i][array[i]] = 1;
        }
        for (int[] ints : arr) {
            for (int i : ints) {
                System.out.print(i + "  ");
            }
            System.out.println();
        }
    }
}

七.排序算法

十大经典的排序算法：菜鸟教程排序算法

1.介绍

image-20230513115319799

2.时间复杂度

度量时间复杂度的两种方法

事后统计法的不足：

  • 需要实际的运行程序 比较耗时
  • 受计算机硬件和软件的影响

image-20230513115606521

时间频度

​ 基本的介绍:一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)

时间复杂度介绍

image-20230515093520587

常见的时间复杂度

image-20230515093753893

3.空间复杂度

image-20230515095247319

排序算法的时间和空间复杂度

image-20230516083738747

4.冒泡排序

冒泡排序的时间复杂度:o(n^2)

同一台电脑 8万个数据 十几秒左右

4.1 基本介绍

image-20230515100345339

4.2 图解

image-20230515100754827

4.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
package com.atguigu.sort;

import java.util.Arrays;

/**
 * @author GongChangjiang
 * @version 1.0
 * @Date 2023/5/15
 * @Description 冒泡排序
 */
public class BubbleSort {
    public static void main(String[] args) {
        int arr[] = {3, 9, -1, 10, -2};
        BubbleSort.sort(arr);
    }

    public static void sort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            int temp = 0; //临时变量
            for (int j = 0; j < arr.length - 1 - i; j++) {
                //如果前面的数字大于后面的数字就交换
                if (arr[j] > arr[j + 1]) {
                    temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
            System.out.println("第" + (i + 1) + "次排序:" + Arrays.toString(arr));
        }
        System.out.println("排序之后的数组:" + Arrays.toString(arr));
    }
}

优化之后的代码（如果排序的过程中代码有序就不在排序）

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
package com.atguigu.sort;

import java.util.Arrays;

/**
 * @author GongChangjiang
 * @version 1.0
 * @Date 2023/5/15
 * @Description 冒泡排序
 */
public class BubbleSort {
    public static void main(String[] args) {
        int arr[] = {3, 9, -1, 10, -2};
        BubbleSort.sort(arr);
    }

    /**
     * 冒泡排序
     * @param arr  需要排序的数组
     */
    public static void sort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            int temp = 0; //临时变量
            boolean flag = false; //表示是否进行过排序
            for (int j = 0; j < arr.length - 1 - i; j++) {
                //如果前面的数字大于后面的数字就交换
                if (arr[j] > arr[j + 1]) {
                    flag = true;
                    temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
            System.out.println("第" + (i + 1) + "次排序:" + Arrays.toString(arr));
            if(!flag){ //说明一次都没有交换  说明已经有序
                break;
            }
        }
        System.out.println("排序之后的数组:" + Arrays.toString(arr));
    }
}

image-20230516091218716

5.选择排序

5.1 基本介绍

同一台电脑 8万个数据 两秒左右

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

image-20230515105359552

5.2图解

img

image-20230516083148055

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
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
package com.atguigu.sort;

import java.util.Arrays;

/**
 * @author GongChangjiang
 * @version 1.0
 * @Date 2023/5/16
 * @Description 选择排序
 */
public class SelectSort {
    public static void main(String[] args) {
        int[] arr = {101,34,119,1};
        int[] arr1 = {3, 9, -1, 10, -2};
        int[] arr2 = {3, 9, -1, 10, -2};
        System.out.println("自己的代码");
        SelectSort.selectSort(arr2);
        System.out.println("老师的代码");
        SelectSort.selectSortByTeacher(arr1);
    }

    /**
     * 选择排序
     * 自己写的 中间的过程和老师的不一样 不确定是不是选择排序
     */
    public static void selectSort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = i + 1; j < arr.length; j++) {//从第一个数字开始 依次找到最小值
                int temp = 0;
                if(arr[i] > arr[j]) {
                    temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
            }
            System.out.println("第次"+(i+1)+"排序的结果:"+Arrays.toString(arr));
        }
        System.out.println("最终的结果:"+Arrays.toString(arr));
    }

    /**
     * 老师的代码
     */
    public static void selectSortByTeacher(int[] arr){

        for (int i = 0; i < arr.length - 1; i++) {
            int minIndex = i;
            int min = arr[i];
            for (int j = i + 1; j < arr.length; j++) {//从第一个数字开始 依次找到最小值
                if(min > arr[j]){
                    min = arr[j];
                    minIndex = j;
                }
            }
            //交换
            arr[minIndex] = arr[i];
            arr[i] = min;
            System.out.println("第次"+(i+1)+"排序的结果:"+Arrays.toString(arr));
        }
        System.out.println("最终的结果:"+Arrays.toString(arr));
    }
}

image-20230516093143656

6.插入排序

6.1 基本介绍

同一台电脑 8万个数据 五秒左右

插入式排序属于内部排序法，是对于欲排序的元素以插入的方式找寻该元素的适当位置，以达到排序的目的。

image-20230516100256880

6.2 图解

img

6.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
package com.atguigu.sort;

import java.util.Arrays;

/**
 * @author GongChangjiang
 * @version 1.0
 * @Date 2023/5/16
 * @Description 插入排序
 */
public class InsertSort {
    public static void main(String[] args) {
        int[] arr = {101, 34, 119, 1,-1,89};
        System.out.println("插入前的数组:"+Arrays.toString(arr));
        InsertSort.insertSort(arr);
    }

    /**
     * 插入排序
     */
    public static void insertSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            //定义待插入的数
            int insertVal = arr[i];
            //待插入的数的前一个数的下标
            int insertIndex = i - 1;
            while (insertIndex >= 0 && insertVal < arr[insertIndex]) {
                arr[insertIndex + 1] = arr[insertIndex];
                insertIndex--;
            }
            //退出循环之后 代表找到了要插入数据的位置
            //插入数据
            arr[insertIndex + 1] = insertVal;
            System.out.println("第" + i  + "次插入的结果:" + Arrays.toString(arr));
        }
        System.out.println("最终的结果:" + Arrays.toString(arr));
    }
}

image-20230516105517026

7.希尔排序

7.1基本介绍

同一台电脑 8万个数据 十七秒左右（交换法）

同一台电脑 8万个数据 一秒左右(移动法)

image-20230517091741355

image-20230517091841366

7.2.图解

img

image-20230517102649272

7.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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
package com.atguigu.sort;

import java.util.Arrays;

/**
 * @author GongChangjiang
 * @version 1.0
 * @Date 2023/5/17
 * @Description 希尔排序
 */
public class ShellSort {
    public static void main(String[] args) {
        int[] arr = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
        //shellSort(arr);
        shellSort2(arr);
    }

    /**
     * 希尔排序 使用的是交换法 这个很慢  比直接的插入排序还慢
     */
    public static void shellSort(int[] arr) {
        int temp = 0;
        int count = 0;
        //用于分组  10个数据  第一次分5组 第二次分2组  第三次分1组  每组分别插入排序
        for (int gap = arr.length / 2; gap > 0; gap /= 2) {
            for (int i = gap; i < arr.length; i++) {
                for (int j = i - gap; j >= 0; j -= gap) {
                    //如果当前的那个元素大于加上步长后的那个元素，就交换
                    if (arr[j] > arr[j + gap]) {
                        temp = arr[j];
                        arr[j] = arr[j + gap];
                        arr[j + gap] = temp;
                    }
                }
            }
            System.out.println("排序第" + (++count) + "轮的结果:" + Arrays.toString(arr));
        }
        System.out.println("最终的结果:" + Arrays.toString(arr));
    }

    /**
     * 使用移动法的希尔排序  这个更快 
     */
    public static void shellSort2(int[] arr) {
        //用于分组  10个数据  第一次分5组 第二次分2组  第三次分1组  每组分别插入排序
        int count = 0;
        for (int gap = arr.length / 2; gap > 0; gap /= 2) {
            for (int i = gap; i < arr.length; i++) {
                int j = i;
                int temp = arr[j];
                if (arr[j] < arr[j - gap]) {
                    while (j - gap >= 0 && temp < arr[j - gap]) {
                        arr[j] = arr[j - gap];
                        j -= gap;
                    }
                   arr[j] = temp;                }
            }
            System.out.println("排序第" + (++count) + "轮的结果:" + Arrays.toString(arr));
        }
        System.out.println("最终的结果:" + Arrays.toString(arr));
    }
}

8.快速排序

8.1 基本介绍

同一台电脑 8万个数据 不到一秒 800万个数据两秒钟

​ 快速排序（Quicksort）是对冒泡排序的一种改进。基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列

8.2 图解

img image-20230517103139900

8.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
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
package com.atguigu.sort;

import java.util.Arrays;

/**
 * @author GongChangjiang
 * @version 1.0
 * @Date 2023/5/17
 * @Description 快速排序
 */
public class QuickSort {
    public static void main(String[] args) {
        int[] arr = {-9, 78, 0, 23, -567, 70};
        quickSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }

    /**
     * @param arr   需要排序的数组
     * @param left  左下标
     * @param right 右下标
     */
    public static void quickSort(int[] arr, int left, int right) {
        int l = left;
        int r = right;
        //pivot 中轴
        int pivot = arr[(left + right) / 2];
        int temp = 0;
        //while循环的目的是让比pivot小的放到左边  大的放在右边
        while (l < r) {
            //在pivot的左边一直找 找到大于等于pivot的值 才退出
            while (arr[l] < pivot) {
                l += 1;
            }
            //在pivot的左边一直找 找到大于等于pivot的值 才退出
            while (arr[r] > pivot) {
                r -= 1;
            }
            //如果l >= r成立  说明pivot的左右两边的值 已经是按照左边全部是
            //小于等于pivot值 右边全部是大于等于pivot值
            if (l >= r) {
                break;
            }
            //交换
            temp = arr[l];
            arr[l] = arr[r];
            arr[r] = temp;
            //如果交换完之后发现arr[l] = pivot值
            if (arr[l] == pivot) {
                r--;
            }
            //如果交换完之后发现arr[r] = pivot值
            if (arr[r] == pivot) {
                l++;
            }
        }

        //如果l == r 必须l++ r--
        if (l == r) {
            l += 1;
            r -= 1;
        }
        //向左递归
        if (left < r) {//左边的数全部有序
            quickSort(arr, left, r);
        }
        //向右递归
        if (right > l) {
            quickSort(arr, l, right);
        }
    }
}

9. 归并排序

9.1基本介绍

同一台电脑 8万个数据 大约一秒钟 800万个数据三秒

image-20230518111233009

9.2 图解

img

image-20230518111454775

image-20230518111536026

9.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
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
package com.atguigu.sort;

import java.util.Arrays;

/**
 * @author GongChangjiang
 * @version 1.0
 * @Date 2023/5/18
 * @Description 归并排序
 */
public class MergeSort {
    public static void main(String[] args) {
        int[] arr = {8, 4, 5, 7, 1, 3, 6, 2};
        int[] temp = new int[arr.length];
        mergeSort(arr,0, arr.length -1,temp);
        System.out.println("归并排序之后的数组:"+ Arrays.toString(arr));
    }

    /**
     * 分治的过程
     */
    public static void mergeSort(int[] arr, int left, int right, int[] temp){
        if(left < right){
            int mid = (left + right) / 2;
            //向左递归分解
            mergeSort(arr,left,mid,temp);
            //向右递归分解
            mergeSort(arr,mid+1,right,temp);
            //合并
            merge(arr,left,mid,right,temp);
        }
    }

    /**
     * 合并的方法  治
     *
     * @param arr   需要排序的数组
     * @param left  右边有序序列的初始索引
     * @param mid   中间索引
     * @param right 右边索引
     * @param temp  中转的数组
     */
    public static void merge(int[] arr, int left, int mid, int right, int[] temp) {
        int i = left;//左边有序序列的初始索引
        int j = mid + 1;//右边有序序列的初始化索引
        int t = 0;//指向temp数组的当前索引

        //1.
        //先把左右两边（有序）的数据填充到temp数组
        //直到左右两边的数据有一边处理完毕为止
        while (i <= mid && j <= right) {//相当于左右两边的数组都有一个指针
            if (arr[i] <= arr[j]) {
                temp[t] = arr[i];
                t++;
                i++;
            } else {//反之将右边有序序列的当前元素 填充到temp数组
                temp[t] = arr[j];
                t++;
                j++;
            }
        }
        //2.
        //把有剩余数据的一边的数据依次全部填充到temp
        while (i <= mid) {//说明左边的有序序列还有剩余的元素
            temp[t] = arr[i];
            t++;
            i++;
        }
        while (j <= right) {
            temp[t] = arr[j];
            t++;
            j++;
        }

        //3.
        //将temp数组的元素拷贝到arr
        //并不是每次都拷贝
        t = 0;
        int tempLeft = left;
        while (tempLeft <= right) {
            arr[tempLeft] = temp[t];
            t++;
            tempLeft++;
        }
    }
}

10.基数排序

同一台电脑8万个数据 一秒左右 8千万个数据会报内存不足

10.1 基本介绍

image-20230525195008102

image-20230526094945578

image-20230526113739081

10.2 图解

img

10.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
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
package com.atguigu.sort;

import java.util.Arrays;

/**
 * @author GongChangjiang
 * @version 1.0
 * @Date 2023/5/26
 * @Description 基数排序
 */
public class RadixSort {
    public static void main(String[] args) {
        //定义一个待排序的数组
        int arr[] = {53, 3, 542, 748, 14, 214};
        RadixSort.radixSort(arr);
    }

    //基数排序
    public static void radixSort(int[] arr) {
        //1.第一轮(针对每个元素的个位进行排序处理)
        //定义一个二维数组，表示十个桶，每个桶就是一个一维数组
        //为了防止数据的溢出，这里每个桶的大小我们设置的大一些 大小定为arr.length
        int[][] bucket = new int[10][arr.length];
        //为了记录每个桶中实际存放了多少个数据，我们定义一个一维数组来记录每个桶中依次放入数据的个数
        //bucketElementCounts[0]记录的就是第0个桶的数据的个数
        int[] bucketElementCounts = new int[10];
        for (int j = 0; j < arr.length; j++) {
            //取出每个元素的个位数的值
            int digitOfElement = arr[j] % 10;
            //放入对应的桶中
            bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
            //[bucketElementCounts[digitOfElement]]++的意思是在digitOfElement对应的桶中数据个数加一
            bucketElementCounts[digitOfElement]++;
        }
        //按照这个桶中顺序取出数据
        int index = 0;
        for (int k = 0; k < bucketElementCounts.length; k++) {
            //如果桶中有数据，我们才放入到原数组
            if (bucketElementCounts[k] != 0) {
                //循环该桶即第K个桶，放入
                for (int l = 0; l < bucketElementCounts[k]; l++) {
                    arr[index++] = bucket[k][l];
                }
            }
            bucketElementCounts[k] = 0;
        }
        System.out.println("第一轮:" + Arrays.toString(arr));

        //2.第2轮
        for (int j = 0; j < arr.length; j++) {
            //取出每个元素的十位数的值
            int digitOfElement = arr[j] / 10 % 10;
            //放入对应的桶中
            bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
            //[bucketElementCounts[digitOfElement]]++的意思是在digitOfElement对应的桶中数据个数加一
            bucketElementCounts[digitOfElement]++;
        }
        //按照这个桶中顺序取出数据
        index = 0;
        for (int k = 0; k < bucketElementCounts.length; k++) {
            //如果桶中有数据，我们才放入到原数组
            if (bucketElementCounts[k] != 0) {
                //循环该桶即第K个桶，放入
                for (int l = 0; l < bucketElementCounts[k]; l++) {
                    arr[index++] = bucket[k][l];
                }
            }
            bucketElementCounts[k] = 0;
        }
        System.out.println("第2轮:" + Arrays.toString(arr));

        //3.第3轮
        for (int j = 0; j < arr.length; j++) {
            //取出每个元素的百位数的值
            int digitOfElement = arr[j] / 100 % 10;
            //放入对应的桶中
            bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
            //[bucketElementCounts[digitOfElement]]++的意思是在digitOfElement对应的桶中数据个数加一
            bucketElementCounts[digitOfElement]++;
        }
        //按照这个桶中顺序取出数据
        index = 0;
        for (int k = 0; k < bucketElementCounts.length; k++) {
            //如果桶中有数据，我们才放入到原数组
            if (bucketElementCounts[k] != 0) {
                //循环该桶即第K个桶，放入
                for (int l = 0; l < bucketElementCounts[k]; l++) {
                    arr[index++] = bucket[k][l];
                }
            }
        }
        System.out.println("第3轮:" + Arrays.toString(arr));

    }
}

最终代码

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
package com.atguigu.sort;

import java.util.Arrays;

/**
 * @author GongChangjiang
 * @version 1.0
 * @Date 2023/5/26
 * @Description 基数排序
 */
public class RadixSort {
    public static void main(String[] args) {
        //定义一个待排序的数组
        int arr[] = {53, 3, 542, 748, 14, 214};
        RadixSort.radixSort(arr);
    }

    //基数排序
    public static void radixSort(int[] arr) {
        //得到数组中最大数的位数
        int max = arr[0];
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] > max) {
                max = arr[i];
            }
        }
        //最大数的位数
        int maxLength = (max + "").length();
        //定义一个二维数组，表示十个桶，每个桶就是一个一维数组
        int[][] bucket = new int[10][arr.length];
        //为了记录每个桶中实际存放了多少个数据，我们定义一个一维数组来记录每个桶中依次放入数据的个数
        int[] bucketElementCounts = new int[10];
        for (int i = 0, n = 1; i < maxLength; i++, n *= 10) {//循环的是每一轮，第一次是个位。第二次是百位
            for (int j = 0; j < arr.length; j++) {
                //取出每个元素的对应位数的值
                int digitOfElement = arr[j] / n % 10;
                //放入对应的桶中
                bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
                //[bucketElementCounts[digitOfElement]]++的意思是在digitOfElement对应的桶中数据个数加一
                bucketElementCounts[digitOfElement]++;
            }
            //按照这个桶中顺序取出数据
            int index = 0;
            for (int k = 0; k < bucketElementCounts.length; k++) {
                //如果桶中有数据，我们才放入到原数组
                if (bucketElementCounts[k] != 0) {
                    //循环该桶即第K个桶，放入
                    for (int l = 0; l < bucketElementCounts[k]; l++) {
                        arr[index++] = bucket[k][l];
                    }
                }
                bucketElementCounts[k] = 0;
            }
            System.out.println("第" + (i + 1) + "轮:" + Arrays.toString(arr));
        }
    }
}

11.常用排序算法总结和对比

image-20230526114127402

八.查找算法

1.简单介绍

image-20230526115027518

2.线性查找算法

2.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
package com.atguigu.search;

/**
 * @author GongChangjiang
 * @version 1.0
 * @Date 2023/5/29
 * @Description 线性查找
 */
public class SeqSearch {
    public static void main(String[] args) {
        int[] arr = {1,9,11,-1,34,89};//没有顺序的数组
        System.out.println("目标值的下标:"+seqSearch(arr, 11));
    }

    /**
     * 找到一个满足条件的值就返回
     * 线性查找是逐一比对，发现有相同的值时就返回这个值的下标
     * @param arr 需要在这里面找目标值的数组
     * @param value 目标值
     * @return 目标值的下标
     */
    public static int seqSearch(int[] arr,int value){
        for (int i = 0; i < arr.length; i++) {
            if(arr[i] == value){
                return i;
            }
        }
        return -1;
    }
}

3.二分查找算法

3.1 图解

image-20230529104112317

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
package com.atguigu.search;

/**
 * @author GongChangjiang
 * @version 1.0
 * @Date 2023/5/29
 * @Description 二分查找
 */
public class BinarySearch {
    public static void main(String[] args) {
        int[] arr = {1, 8, 10, 89, 1000, 1234};
        System.out.println("目标值的下标:" + binarySearch(arr, 0, arr.length - 1, 3));
    }

    /**
     * 二分查找
     *
     * @param arr     需要在这里面查找目标值的数组
     * @param left    左边的索引
     * @param right   右边的索引
     * @param findVal 要查找的值
     * @return 目标值在数组中的下标，找到就返回下标，没有就返回-1
     */
    public static int binarySearch(int[] arr, int left, int right, int findVal) {
        //结束递归的条件
        if (left > right) {
            return -1;
        }
        int mid = (left + right) / 2;
        int midVal = arr[mid];
        if (findVal > midVal) {//向右递归
            return binarySearch(arr, mid + 1, right, findVal);
        } else if (findVal < midVal) {//向左递归
            return binarySearch(arr, left, mid - 1, findVal);
        } else {
            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
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
package com.atguigu.search;

import java.util.ArrayList;
import java.util.List;

/**
 * @author GongChangjiang
 * @version 1.0
 * @Date 2023/5/29
 * @Description 二分查找
 */
public class BinarySearch {
    public static void main(String[] args) {
        int[] arr = {1, 8, 10, 89, 1000, 1234};
        System.out.println("目标值的下标:" + binarySearch(arr, 0, arr.length - 1, 3));
        int[] arr2 = {1, 8, 10, 89, 89, 89, 1000, 1234};
        System.out.println("目标值在数组中下标的集合:" + binarySearch2(arr2, 0, arr2.length - 1, 89));
    }

    /**
     * 二分查找
     *
     * @param arr     需要在这里面查找目标值的数组
     * @param left    左边的索引
     * @param right   右边的索引
     * @param findVal 要查找的值
     * @return 目标值在数组中的下标，找到就返回下标，没有就返回-1
     */
    public static int binarySearch(int[] arr, int left, int right, int findVal) {
        //结束递归的条件
        if (left > right) {
            return -1;
        }
        int mid = (left + right) / 2;
        int midVal = arr[mid];
        if (findVal > midVal) {//向右递归
            return binarySearch(arr, mid + 1, right, findVal);
        } else if (findVal < midVal) {//向左递归
            return binarySearch(arr, left, mid - 1, findVal);
        } else {
            return mid;
        }
    }

    /**
     * 二分查找查找出所有与目标值相同的数组的下标
     *
     * @param arr     需要在这里面查找目标值的数组
     * @param left    左边的索引
     * @param right   右边的索引
     * @param findVal 要查找的的值
     * @return 目标值在数组中的下标的集合
     */
    public static List<Integer> binarySearch2(int[] arr, int left, int right, int findVal) {
        //结束递归的条件
        if (left > right) {
            return new ArrayList<>();
        }
        int mid = (left + right) / 2;
        int midVal = arr[mid];
        if (findVal > midVal) {//向右递归
            return binarySearch2(arr, mid + 1, right, findVal);
        } else if (findVal < midVal) {//向左递归
            return binarySearch2(arr, left, mid - 1, findVal);
        } else {
            List<Integer> resList = new ArrayList<>();
            int temp = mid - 1;
            while (true) { //向左边探测相同值的元素
                if (temp < 0 || arr[temp] != findVal) {
                    break;
                }
                //否则就把temp放入到集合中
                resList.add(temp);
                temp--;//左移
            }
            resList.add(mid);
            //向右边探测
            temp = mid + 1;
            while (true) { //向右边探测相同值的元素
                if (temp > arr.length - 1 || arr[temp] != findVal) {
                    break;
                }
                //否则就把temp放入到集合中
                resList.add(temp);
                temp++;//右移
            }
            return resList;
        }
    }

}

4.插值查找算法

4.1 图解

image-20230530101803392

4.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
package com.atguigu.search;

import java.util.Arrays;

/**
 * @author GongChangjiang
 * @version 1.0
 * @Date 2023/5/30
 * @Description 插值查找算法
 */
public class InsertValueSearch {
    public static void main(String[] args) {
        //创建一个数组 用于模拟需要查找数据的数组
        int[] arr = new int[100];
        for (int i = 0; i < 100; i++) {
            arr[i] = i + 1;
        }
        System.out.println(Arrays.toString(arr));
        System.out.println("查找的数的下标为:" + insertValueSearch(arr, 0, arr.length - 1, 30));
    }

    /**
     * 插值查找算法
     *
     * @param arr     目标数组(有序的)等差序列的最好，1-100有序的数组，找一个数只用找一次就行了
     * @param left    左边索引
     * @param right   右边索引
     * @param findVal 需要查找的值
     * @return 查找的值在数组中的索引
     */
    public static int insertValueSearch(int[] arr, int left, int right, int findVal) {
        System.out.println("方法被调用了");
        //退出的条件和防止数组越界
        if (left > right || findVal < arr[0] || findVal > arr[arr.length - 1]) {
            return -1;
        }
        //求出mid,这个是插值查找算法的灵魂,自适应的查找
        int mid = left + (right - left) * (findVal - arr[left]) / (arr[right] - arr[left]);
        int midVal = arr[mid];
        if (findVal > midVal) { //应向右递归
            return insertValueSearch(arr, mid + 1, right, findVal);
        } else if (findVal < midVal) {//向左边递归
            return insertValueSearch(arr, left, mid - 1, findVal);
        } else {
            return mid;
        }
    }
}

4.3 注意事项

image-20230530105652529

5.斐波那契（黄金分割法）查找算法

5.1 基本介绍

image-20230530110145048

5.2 原理介绍

image-20230530110511769

PDF笔记