Java数据结构与算法

前言

1. 稀疏数组和队列

1.1 稀疏数组

使用的场景

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

处理方法:

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

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

image-20220622183934608

转换思路

二维->稀疏数组

  1. 遍历原始的二维数组，得到有效数据的个数sum
  2. 根据sum就可以创建稀疏数组sparseArr int[sum + 1] [3];
  3. 将二维数组的有效数据存入到稀疏数组

稀疏数组->二维数组

  1. 先读取稀疏数组的第一行，根据第一行的数据，创建原始的二维数组
  2. 再读取稀疏数组后几行的数据，并赋给原始的二维数组

代码实现

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

   public static void main(String[] args) {
      //原始的二维数组
      int chessArr1[][] = new int[11][11];
      chessArr1[1][2] = 1;
      chessArr1[2][3] = 2;
      chessArr1[4][5] = 2;//棋子在数组里面的位置

      System.out.println("原始的二维数组~~");
      for (int[] row : chessArr1) {
         for (int data : row) {
            System.out.printf("%d\t", data);
         }
         System.out.println();
      }

       //先遍历一遍，得到意义的数据有哪些
      int sum = 0;
      for (int i = 0; i < 11; i++) {
         for (int j = 0; j < 11; j++) {
            if (chessArr1[i][j] != 0) {
               sum++;
            }
         }
      }

      //根据sum来创建稀疏数组
      int sparseArr[][] = new int[sum + 1][3];
      //赋初值
      sparseArr[0][0] = 11;//11行
      sparseArr[0][1] = 11;//11列
      sparseArr[0][2] = sum;//sum个有意义的数据
      
      // 遍历二维数组，将数据存储到稀疏数组中
      int count = 0; //count用来表示在稀疏数组的第几行
      for (int i = 0; i < 11; i++) {
         for (int j = 0; j < 11; j++) {
            if (chessArr1[i][j] != 0) {
               count++;
               sparseArr[count][0] = i;
               sparseArr[count][1] = j;
               sparseArr[count][2] = chessArr1[i][j];
            }
         }
      }
      
      //输出稀疏数组
      System.out.println();
      System.out.println("稀疏数组~~~~");
      for (int i = 0; i < sparseArr.length; i++) {
         System.out.printf("%d\t%d\t%d\t\n", sparseArr[i][0], sparseArr[i][1], sparseArr[i][2]);
      }
      System.out.println();
      


      // 将稀疏数组恢复为原始的二维数组

      int chessArr2[][] = new int[sparseArr[0][0]][sparseArr[0][1]];//根据第一行的数据创建二维数组
      

      //遍历稀疏数组循环赋值
      for(int i = 1; i < sparseArr.length; i++) {
         chessArr2[sparseArr[i][0]][sparseArr[i][1]] = sparseArr[i][2];
      }
      
      //输出恢复后的二维数组为
      System.out.println();
      System.out.println("恢复后的二维数组为：");
      
      for (int[] row : chessArr2) {
         for (int data : row) {
            System.out.printf("%d\t", data);
         }
         System.out.println();
      }
   }

}

1.2 队列

队列概念

  1. 队列是一个有序列表，可以用数组或是链表来实现。

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

  3. 示意图：(使用数组模拟队列示意图)

    示意图

数组模拟队列思路

  1. 队列本身是有序列表，若使用数组的结构来存储队列的数据，则队列数组的声明如下图, 其中 maxSize 是该队列的最大容量。

  2. 因为队列的输出、输入是分别从前后端来处理，因此需要两个变量 front 及 rear 分别记录队列前后端的下标，front 会随着数据输出而改变，而 rear 则是随着数据输入而改变

  3. 当我们将数据存入队列时称为”addQueue”，addQueue 的处理需要有两个步骤：

  • 将尾指针往后移：rear+1 , 当 front == rear （空） (这里的front是有数据的前一个位置)

  • 若尾指针 rear 小于队列的最大下标 maxSize-1，则将数据存入 rear 所指的数组元素中，否则无法存入数据。rear == maxSize - 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
//使用数组来模拟队列
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; // ָ赋初值为空
		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++; // 将尾指针往后移
		arr[rear] = n; // 从后面入队
	}

	// 获取队首的数据
	public int getQueue() {
		// 还是要判断是否是空的
		if (isEmpty()) {
			// 手写一个异常抛出
			throw new RuntimeException("队列为空，没有数据");
		}
		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];
	}
}

数组模拟环形队列

  • front变量指向队首元素，初值为0
  • rear变量指向队尾元素的下一个元素，初值为0。规定空出一个位置
  • 队列为空的判定条件：front == rear
  • 队列为满的判定条件：(rear + 1) % maxSize == front
  • 队列中有效元素的个数：(rear - front + maxSize) % maxSize
  • 入队和出队时，都需要让标记对maxSize取模

代码实现

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
class CircleArray {
   private int maxSize; //队列的最大容量
   private int front; // 头指针
   private int rear; // 尾指针 这里代表的是有数据的后一个位置
   private int[] arr; // 存放数据
   
   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 (isFull()) {
         System.out.println("队列已满，没有数据~");
         return;
      }
      //ֱ 赋值
      arr[rear] = n;
      // 向后移动指针
      rear = (rear + 1) % maxSize;
   }
   
   // 出队
   public int getQueue() {
      if (isEmpty()) {
         throw new RuntimeException("队列为空，没有数据");
      }

      int value = arr[front];
      front = (front + 1) % maxSize;
      return value;

   }
   
   // 打印队列里面的全部数据
   public void showQueue() {

      if (isEmpty()) {
         System.out.println("队列为空~~");
         return;
      }

      //因为可能大于maxsize，因此也需要取余
      for (int i = front; i < front + size() ; i++) {
         System.out.printf("arr[%d]=%d\n", i % maxSize, arr[i % maxSize]);
      }
   }
   
   // 获取队列中的有效数据有多少个
   public int size() {
      // rear = 2
      // front = 1
      // maxSize = 3 
      return (rear + maxSize - front) % maxSize;   
   }
   
   // 只是查看数据，没有取出，就是没有移动头指针
   public int headQueue() {

      if (isEmpty()) {
         throw new RuntimeException("队列为空~~");
      }
      return arr[front];
   }
}

2. 链表

2.1 单链表

简单的介绍

  • 链表是以节点的方式来存储,是链式存储

  • 每个节点包含 data 域， next 域：指向下一个节点.

  • 链表的各个节点不一定是连续存储.

  • 链表分带头节点的链表和没有头节点的链表，根据实际的需求来确定

链表的逻辑结构示意图如下：

示意图

实现思路

增加

直接添加到尾部，把上一个节点的指针指向新的节点

根据排名添加节点(插入)

先遍历到需要插入夫人地方，将新的节点先连接到下一个节点上，然后再把上一个节点指向这个节点，

heroNode.next = temp.next; //先连接
temp.next = heroNode; //再断开

修改节点

遍历找到需要修改的节点，修改信息即可

删除节点

找到需要删除的节点的上一个节点，把当前节点(要删除节点的上一个节点)指向需要删除节点的一个节点的上一个节点

temp.next = temp.next.next;

逆序打印链表

使用栈的先进后出的特性来实现

查找链表的倒数第几个节点

倒数第几个节点就是顺数第(size-index)个节点，先遍历一遍求得长度，然后求第(size-index)个节点就行

翻转链表

感觉和前面的插入没有什么不同，就是需要一个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
package com.Mercury.linkedlist;

import java.util.Stack;

public class SingleLinkedListDemo {

	public static void main(String[] args) {
		//测试增加
		HeroNode hero1 = new HeroNode(1, "宋江", "及时雨");
		HeroNode hero2 = new HeroNode(2, "卢俊义", "玉麒麟");
		HeroNode hero3 = new HeroNode(3, "吴用", "智多星");
		HeroNode hero4 = new HeroNode(4, "林冲", "豹子头");
		
		//创建一个新的链表
		SingleLinkedList singleLinkedList = new SingleLinkedList();
		
		
		//添加几个节点
		singleLinkedList.add(hero1);
		singleLinkedList.add(hero4);
		singleLinkedList.add(hero2);
		singleLinkedList.add(hero3);

		//输出链表
		System.out.println("链表数据如下~~");
		singleLinkedList.list();


		System.out.println("逆序打印链表, 没有打印链表的结构~~");
		reversePrint(singleLinkedList.getHead());

		//翻转链表，改变了结构
		System.out.println("翻转后的链表为");
		reversetList(singleLinkedList.getHead());
		singleLinkedList.list();


        //创建一个新的链表
		SingleLinkedList singleLinkedList2 = new SingleLinkedList();
		//按照排名添加
		singleLinkedList2.addByOrder(hero1);
		singleLinkedList2.addByOrder(hero4);
		singleLinkedList2.addByOrder(hero2);
		singleLinkedList2.addByOrder(hero3);

		//修改节点的值
		HeroNode newHeroNode = new HeroNode(2, "小卢", "玉麒麟~~");
		singleLinkedList2.update(newHeroNode);

		System.out.println("修改后的~~");
		singleLinkedList2.list();


		singleLinkedList2.del(1);
		singleLinkedList2.del(4);
		System.out.println("删除后的节点为~~");
		singleLinkedList2.list();

		//求有效节点数
		System.out.println("有效节点数=" + getLength(singleLinkedList2.getHead()));


		HeroNode res = findLastIndexNode(singleLinkedList2.getHead(), 2);
		System.out.println("res=" + res);

		
	}
	


	//使用栈来逆序打印
	public static void reversePrint(HeroNode head) {
		if(head.next == null) {
			return;
		}

		Stack<HeroNode> stack = new Stack<HeroNode>();
		HeroNode cur = head.next;
		// 如果不为空就入栈
		while(cur != null) {
			stack.push(cur);
			cur = cur.next;
		}
        //栈不为空就出栈
		while (stack.size() > 0) {
			System.out.println(stack.pop());
		}
	}
	
	//翻转链表
	public static void reversetList(HeroNode head) {
		//链表是空的，或者只有一个节点，那还翻转个什么
		if(head.next == null || head.next.next == null) {
			return ;
		}
		
		//一样的用来遍历节点的临时节点
		HeroNode cur = head.next;
		HeroNode next = null;// ָ用来保存当前节点的下一个节点
		HeroNode reverseHead = new HeroNode(0, "", "");

		//不断的在头部插入遍历的节点以达到翻转的效果
		while(cur != null) { 
			next = cur.next;//暂时保存当前节点的下一个节点
			cur.next = reverseHead.next;//先连接cur和revers的下一个节点
			reverseHead.next = cur; //将头节点指向当前的节点
			cur = next;//cur移到下一位
		}

		head.next = reverseHead.next;//改变头部
	}

	//查找单链表中的倒数第 k 个结点
		//思路
		//1. 编写一个方法，接收 head 节点，同时接收一个 index
		//2. index 表示是倒数第 index 个节点
		//3. 先把链表从头到尾遍历，得到链表的总的长度 getLength
		//4. 得到 size 后，我们从链表的第一个开始遍历 (size-index)个，就可以得到//5. 如果找到了，则返回该节点，否则返回 null
	public static HeroNode findLastIndexNode(HeroNode head, int index) {
		if(head.next == null) {
			return null;
		}

		int size = getLength(head);


		if(index <=0 || index > size) {
			return null; 
		}

		HeroNode cur = head.next; //3 // 3 - 1 = 2
		for(int i =0; i< size - index; i++) {
			cur = cur.next;
		}
		return cur;
		
	}
	
	//获取链表的有效节点数
	public static int getLength(HeroNode head) {
		if(head.next == null) { //带头结点的空链表
			return 0;
		}
		int length = 0;

		HeroNode cur = head.next;
		while(cur != null) {
			length++;
			cur = cur.next; //遍历写一个
		}
		return length;
	}

}


//SingleLinkedList
class SingleLinkedList {

	private HeroNode head = new HeroNode(0, "", "");
	
	
	//获取头部
	public HeroNode getHead() {
		return head;
	}


	public void add(HeroNode heroNode) {
		
		//需要用一个temp来遍历
		HeroNode temp = head;
		//找尾部
		while(true) {
			//找到了尾部
			if(temp.next == null) {
				break;
			}
			//没有找到，继续向下一个遍历
			temp = temp.next;
		}
		//将新节点赋给尾部
		temp.next = heroNode;//Java对象是引用传递
	}
	
	//根据排名将英雄添加到指定位置，如果有这个排名，则添加失败，并且给出提示
	public void addByOrder(HeroNode heroNode) {

		//单链表需要找添加位置的前一个节点
		HeroNode temp = head;
		boolean flag = false; // flag标志添加的编号是否存在，默认为false
		while(true) {
			if(temp.next == null) {//遍历到了尾部了
				break;
			} 
			if(temp.next.no > heroNode.no) { //找到了该添加的位置
				break;
			} else if (temp.next.no == heroNode.no) {//编号已经存在，不能再添加
				
				flag = true; //设置不能再添加的标志
				break;
			}
			temp = temp.next; //都不是以上情况，继续遍历下一个
		}
		//判断flag的值，看看有没有出现上面的那种情况
		if(flag) {
			System.out.printf("准备插入英雄编号 %d 已经存在, 不能再加入\n", heroNode.no);
		} else {
			//进行插入操作
			heroNode.next = temp.next;//先连接
			temp.next = heroNode;//再断开
		}
	}


	//根据no来修改
	public void update(HeroNode newHeroNode) {

		if(head.next == null) {
			System.out.println("链表为空~");
			return;
		}
		//根据no找到需要修改的节点
		HeroNode temp = head.next;
		boolean flag = false;//表示是否找到该节点
		while(true) {
			if (temp == null) {
				break;
			}
			if(temp.no == newHeroNode.no) {
				//找到该节点
				flag = true;
				break;
			}
			temp = temp.next;//没找到，继续找
		}

		if(flag) {
			temp.name = newHeroNode.name;
			temp.nickname = newHeroNode.nickname;//找到了该节点，进行修改
		} else { //没有找到节点
			System.out.printf("没有找到编号为 %d 的节点\n", newHeroNode.no);
		}
	}
	

	public void del(int no) {
		HeroNode temp = head;
		boolean flag = false; // 设置有没有找到的标志
		while(true) {
			if(temp.next == null) {
				break;
			}
			if(temp.next.no == no) {
				//找到待删除的前一个节点temp
				flag = true;
				break;
			}
			temp = temp.next; //temp继续遍历下一个
		}

		if(flag) {
			//找到了待删除的前一个节点，进行删除
			temp.next = temp.next.next;
		}else {
			System.out.printf("没有找到编号为 %d 的节点\n", no);
		}
	}
	
	//输出数据
	public void list() {

		if(head.next == null) {
			System.out.println("链表为空");
			return;
		}
		// 从头部的下一个开始
		HeroNode temp = head.next;
		while(true) {

			if(temp == null) {
				break;
			}
			// 一个个接着打印
			System.out.println(temp);
			// 打印完以后移位
			temp = temp.next;
		}
	}
}

//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;
	}
	//重写toString
	@Override
	public String toString() {
		return "HeroNode [no=" + no + ", name=" + name + ", nickname=" + nickname + "]";
	}
	
}

输出的数据如下

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
链表数据如下~~
HeroNode [no=1, name=宋江, nickname=及时雨]
HeroNode [no=4, name=林冲, nickname=豹子头]
HeroNode [no=2, name=卢俊义, nickname=玉麒麟]
HeroNode [no=3, name=吴用, nickname=智多星]
逆序打印链表, 没有打印链表的结构~~
HeroNode [no=3, name=吴用, nickname=智多星]
HeroNode [no=2, name=卢俊义, nickname=玉麒麟]
HeroNode [no=4, name=林冲, nickname=豹子头]
HeroNode [no=1, name=宋江, nickname=及时雨]
翻转后的链表为
HeroNode [no=3, name=吴用, nickname=智多星]
HeroNode [no=2, name=卢俊义, nickname=玉麒麟]
HeroNode [no=4, name=林冲, nickname=豹子头]
HeroNode [no=1, name=宋江, nickname=及时雨]
修改后的~~
HeroNode [no=1, name=宋江, nickname=及时雨]
HeroNode [no=2, name=小卢, nickname=玉麒麟~~]
HeroNode [no=3, name=吴用, nickname=智多星]
HeroNode [no=4, name=林冲, nickname=豹子头]
删除后的节点为~~
HeroNode [no=2, name=小卢, nickname=玉麒麟~~]
HeroNode [no=3, name=吴用, nickname=智多星]
有效节点数=2
res=HeroNode [no=2, name=小卢, nickname=玉麒麟~~]

2.2 双向链表

简单的介绍

管理单向链表的缺点分析:

  1. 单向链表，查找的方向只能是一个方向，而双向链表可以向前或者向后查找。

  2. 单向链表不能自我删除，需要靠辅助节点 ，而双向链表，则可以自我删除，所以前面我们单链表删除时节点，总是找到 temp,temp 是待删除节点的前一个节点(认真体会).

思路实现

  1. 遍历 方和 单链表一样，只是可以向前，也可以向后查找

  2. 添加 (默认添加到双向链表的最后)

​ 先找到双向链表的最后这个节点

​ temp.next = newHeroNode

​ newHeroNode.pre = temp;

  1. 修改 思路和 原来的单向链表一样.

  2. 删除

  • 因为是双向链表，因此，我们可以实现自我删除某个节点直接找到要删除的这个节点，比如 temp

  • temp.pre.next = temp.next

  • temp.next.pre = temp.pre;

    • 如果这里是最后一个节点的话需要额外判断一下，否则会出现空指针异常
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
package com.Mercury.linkedlist;

public class DoubleLinkedListDemo {

	public static void main(String[] args) {

		HeroNode2 hero1 = new HeroNode2(1, "宋江", "及时雨");
		HeroNode2 hero2 = new HeroNode2(2, "卢俊义", "玉麒麟");
		HeroNode2 hero3 = new HeroNode2(3, "吴用", "智多星");
		HeroNode2 hero4 = new HeroNode2(4, "林冲", "豹子头");
		// 添加节点
		DoubleLinkedList doubleLinkedList = new DoubleLinkedList();
		doubleLinkedList.add(hero1);
		doubleLinkedList.add(hero2);
		doubleLinkedList.add(hero3);
		doubleLinkedList.add(hero4);
		
		doubleLinkedList.list();
		
        //修改节点
		HeroNode2 newHeroNode = new HeroNode2(4, "公孙胜", "入云龙");
		doubleLinkedList.update(newHeroNode);
		System.out.println("修改后的链表情况");
		doubleLinkedList.list();
		
		// 删除
		doubleLinkedList.del(3);
		System.out.println("删除后的链表情况~~");
		doubleLinkedList.list();

	}

}

// 双向链表
class DoubleLinkedList {


	private HeroNode2 head = new HeroNode2(0, "", "");


	public HeroNode2 getHead() {
		return head;
	}

    //链表遍历没有什么变化
	public void list() {

		if (head.next == null) {
			System.out.println("双向链表为空");
			return;
		}

		HeroNode2 temp = head.next;
		while (true) {

			if (temp == null) {
				break;
			}

			System.out.println(temp);
			temp = temp.next;
		}
	}

	// 添加方法
	public void add(HeroNode2 heroNode) {


		HeroNode2 temp = head;

		while (true) {

			if (temp.next == null) {
				break;
			}

			temp = temp.next;
		}
		//就多了一句话
		temp.next = heroNode;
		heroNode.pre = temp;
	}


	// 没有什么变化就只是类型变为了 HeroNode2
	public void update(HeroNode2 newHeroNode) {

		if (head.next == null) {
			System.out.println("链表为空~");
			return;
		}

		HeroNode2 temp = head.next;
		boolean flag = false;
		while (true) {
			if (temp == null) {
				break;
			}
			if (temp.no == newHeroNode.no) {
				flag = true;
				break;
			}
			temp = temp.next;
		}
		if (flag) {
			temp.name = newHeroNode.name;
			temp.nickname = newHeroNode.nickname;
		} else {
			System.out.printf("没有找到编号为 %d 的节点\n", newHeroNode.no);
		}
	}

	// 双向链表的删除这里有着较大的区别
	public void del(int no) {

		// 熟悉的判断是否为空
		if (head.next == null) {
			System.out.println("双向链表为空");
			return;
		}

		HeroNode2 temp = head.next; // 熟悉的temp指针
		boolean flag = false; // 熟悉的判断有没有找到
		while (true) {
			if (temp == null) { // 因为双向的链表的删除不需要找节点的前一个节点了，所以这里直接判断temp是否为空就行
				break;
			}
			if (temp.no == no) {
				// 同样的道理，这里也是直接判断temp的编号
				flag = true;
				break;
			}
			temp = temp.next; // temp后移
		}
		// 判断flag
		if (flag) {
			//以前单链表的删除操作
			// temp.next = temp.next.next;
			temp.pre.next = temp.next;
			// 这里有一个问题，如果要删除的temp是链表的最后一个元素的话，下面的这一句话就会出现空指针异常
			// 所以这里需要再判断一下，如果是最后一个元素就不需要执行下面一句话
			if (temp.next != null) {
				temp.next.pre = temp.pre;
			}
		} else {
			System.out.printf("没有找到编号为 %d 的节点\n", no);
		}
	}

}


class HeroNode2 {
	public int no;
	public String name;
	public String nickname;
	public HeroNode2 next; // 指向下一个节点null
	public HeroNode2 pre; // ָ指向上一个节点null

    //构造函数
	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 + "]";
	}

}

2.3 约瑟夫环

问题介绍

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

思路实现

使用单向环形链表实现，每报到一个数的时候就让这个节点打印出来，然后删除节点，直到只有最后一个节点

出去的顺序

代码

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


//约瑟夫环问题
public class Josepfu {


   public static void main(String[] args) {

      CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList();
      circleSingleLinkedList.addBoy(5);// 添加小孩
      //circleSingleLinkedList.showBoy();
      
      //测试
      circleSingleLinkedList.countBoy(1, 2, 5); // 2->4->1->5->3
   }

}


class CircleSingleLinkedList {

   private Boy first = null;

   // 添加小孩，构造环形链表
   public void addBoy(int nums) {
      // nums < 1那还添加个啥，总不能添加半个小孩吧
      if (nums < 1) {
         System.out.println("nums 输入有误，请重新输入");
         return;
      }
      Boy curBoy = null; // curboy用来指向当前的节点
      // 以循环添加
      for (int i = 1; i <= nums; i++) {
         // 构造新小孩
         Boy boy = new Boy(i);
         //如果是第一个小孩
         if (i == 1) {
            first = boy;
            first.setNext(first); // 构成环状
            curBoy = first; //cur 当前也在第一个的位置
         } else {
            curBoy.setNext(boy);// 添加到尾部
            boy.setNext(first);// 指向头部，形成环状
            curBoy = boy;// 移动到新添加的位置
         }
      }
   }

   // 一个展示的函数
   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(); // curBoy后移
      }
   }


   /**
    *
    * @param startNo  表示从第几个小孩开始数数
    * @param countNum  表示数几下
    * @param nums   表示最初有几个小孩在圈中
    */
   public void countBoy(int startNo, int countNum, int nums) {

      if (first == null || startNo < 1 || startNo > nums) {
         System.out.println("链表为空或输入的编号有误");
         return;
      }
      // 定义一个辅助的变量用来删除出去的节点
      Boy helper = first;
      // helper
      while (true) {
         if (helper.getNext() == first) { // 移动helper到第一个节点
            break;
         }
         helper = helper.getNext();
      }
      // 移动到开始报数的位置
      for(int j = 0; j < startNo - 1; j++) {
         first = first.getNext();
         helper = helper.getNext();
      }

      while(true) {
         if(helper == first) { // 说明只剩下了一个节点，结束循环
            break;
         }
         // 要报数几个节点就是 first 和 helper 移动 countNum - 1 位
         for(int j = 0; j < countNum - 1; j++) {
            first = first.getNext();
            helper = helper.getNext();
         }

         System.out.printf("出环的孩子编号为 %d \n", first.getNo());
         // first移动到下一位，以便删除
         first = first.getNext();
         helper.setNext(first); //helper指向现在的位置，之前first指向的元素即被舍弃，会被GC回收
         
      }
      System.out.printf("最后出环的孩子编号为 %d \n", first.getNo());
      
   }
}

// boy实体类
class Boy {
   private int no;// 数据域
   private Boy next; // 指针域

   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;
   }

}

3. 栈

3.1 初识栈

什么是栈

栈是一种先进后出的有序列表，限制删除和增加的操作只能在同一端的特殊线性表，变化的一端就是栈顶，另一端被我们称为栈底。

栈的应用场景

  • 子程序的调用
  • 处理递归调用
  • 表达式的求值
  • 二叉树的遍历
  • 图的深度优先搜索

实现思路

  • 使用数组来模拟栈
  • 栈顶定义为top，初始值设为-1
  • 入栈 top++ ; stack[top] = data;
  • 出栈 int value = stack[top]; top–;

代码

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
//用数组来模拟栈
class ArrayStack{
	private int maxSize;
	private int[] stack;
	private int top = -1;//栈顶

	//构造器
	public ArrayStack(int maxSize){
		this.maxSize  = maxSize;
		stack = new int[this.maxSize];
	}

	//判断栈满
	public boolean isFull(){
		return top == maxSize - 1;//wc 简直机智
	}

	//判断栈空
	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()){
			throw new RuntimeException("栈为空");
		}
		for(int i = top; i >= 0 ; i--) {
		   System.out.printf("stack[%d]=%d\n", i, stack[i]);
		}
	}

}

public class ArrayStackDemo {
	public static void main(String[] args) {
		ArrayStack arrayStack = new ArrayStack(4);
		arrayStack.push(10);
		arrayStack.push(9);
		arrayStack.push(4);
		System.out.println(arrayStack.pop());
		System.out.println(arrayStack.pop());
		System.out.println(arrayStack.pop());
	}
}
1
2
3
4
9
10

3.2 表达式求值

表达式求值是栈的经典的应用之一,简单的来说，就是把一长串的数学表达式，通过程序计算出来，实现一个计算机的功能

实现的思路

  • 建立两个栈来分别存储数字和运算符号，并使用一个索引遍历表达式
  • 遇到数字直接就进入数栈
  • 遇到符号
    • 如果符号栈是空的，直接入符号栈
    • 如果不是空的，当前的符号的优先级小于或等于栈顶的元素，符号栈弹出一个符号，数字栈弹出两个数字计算，运算结果进入数字栈，然后当前的符号入符号栈
    • 如果不是空的，当前的符号的优先级大于栈顶的元素，当前的元素直接入符号栈

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
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
package com.Mercury.stack;

public class Calculator {

	public static void main(String[] args) {

		String expression = "7*2*2-5+1-5+3-4"; // 18

		ArrayStack2 numStack = new ArrayStack2(10);
		ArrayStack2 operStack = new ArrayStack2(10);

		int index = 0;
		int num1 = 0; 
		int num2 = 0;
		int oper = 0;
		int res = 0;
		char ch = ' ';
		String keepNum = "";

		while(true) {
			ch = expression.substring(index, index+1).charAt(0);//取出表达式里面的字符
			if(operStack.isOper(ch)) {//判断是否是符号
				if(!operStack.isEmpty()) {//如果栈没有空
					if(operStack.priority(ch) <= operStack.priority(operStack.peek())) {//新的符号没有栈顶的符号优先级高
						num1 = numStack.pop();
						num2 = numStack.pop();//弹两个数字出来
						oper = operStack.pop();//弹一个符号出来
						res = numStack.cal(num1, num2, oper);//计算结果
						numStack.push(res);//结果入栈
						operStack.push(ch);//新的符号入栈
					} else {//新的符号比栈顶的符号优先级高，直接入栈
						operStack.push(ch);
					}
				}else {
					operStack.push(ch); //符号栈是空的，直接入栈
				}
			} else {//是数字
				keepNum += 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 = "";//入栈后，清空原来的字符串
					}
					//如果没有进上面那个if分支，keepNum就会一直加，直到后面一位是符号后才入栈
				}
			}
			index++;
			if (index >= expression.length()) {
				break;
			}
		}
		//全部入栈后
		while(true) {
			if(operStack.isEmpty()) {
				break;
			}
			num1 = numStack.pop();
			num2 = numStack.pop();
			oper = operStack.pop();
			res = numStack.cal(num1, num2, oper);//依次弹出栈，进行运算
			numStack.push(res);
		}
		int res2 = numStack.pop();//得到最后的结果
		System.out.printf(" %s = %d", expression, res2);
	}
}
class ArrayStack2 {
	private int maxSize;
	private int[] stack;
	private int top = -1;
	

	public ArrayStack2(int maxSize) {
		this.maxSize = maxSize;
		stack = new int[this.maxSize];
	}
	

	public int peek() {
		return stack[top];
	}
	

	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 res = 0; 
		switch (oper) {
		case '+':
			res = num1 + num2;
			break;
		case '-':
			res = num2 - num1; //后弹出栈的减先弹出栈的数字
			break;
		case '*':
			res = num1 * num2;
			break;
		case '/':
			res = num2 / num1;
			break;
		default:
			break;
		}
		return res;
	}
	
}

3.3 中缀转后缀

后缀表达式(逆波兰表达式)的计算

从左到右扫描后缀表达式，遇到数字入栈，遇到符号，弹出两个数字计算，将结果入栈，最后得出最后结果，

实现思路

  • 初始化一个符号栈s1，一个存储中间结果的栈s2，从左到右扫描表达式
  • 遇到数字，直接压入s2
  • 遇到运算符
    • s1为空，s1栈顶为左括号’ ( ',当前符号比栈顶运算符优先级高，直接入栈s1
    • 否则(s1栈顶的元素优先级小于或等于当前的元素的优先级)将s1栈顶的运算符弹出并压入s2中，再次与s1中的栈顶元素比较
  • 遇到括号
    • 遇到左括号’(’ 直接压入s1
    • 遇到右括号 ‘)’ 依次弹出s1栈顶的运算符并压入s2,直到遇到左括号为止，然后将这一对括号丢弃
  • 将s1中剩余的运算符依次弹出并压入s2
  • 依次弹出s2中的元素并输出，结果的逆序就是结果

1+( ( 2 + 3 ) * 4 ) - 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
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
public class PolandNotation {


	//中缀表达式转后缀表达式
	public static void main(String[] args) {
		

		
		String expression = "1+((2+3)*4)-5";
		List<String> infixExpressionList = toInfixExpressionList(expression);
		System.out.println("中缀表达式 List=" + infixExpressionList); // ArrayList [1,+,(,(,2,+,3,),*,4,),-,5]
		List<String> suffixExpreesionList = parseSuffixExpreesionList(infixExpressionList);
		System.out.println("后缀表达式 List" + suffixExpreesionList); //ArrayList [1,2,3,+,4,*,+,5,-]
		System.out.printf("expression=%d", calculate(suffixExpreesionList)); // 最后的计算结果

	}

	// 将表达式装入集合
	public static List<String> toInfixExpressionList(String s) {

		List<String> ls = new ArrayList<String>();
		int i = 0;
		String str;
		char c;
		do {
			//如果是数字
			if((c=s.charAt(i)) < 48 ||  (c=s.charAt(i)) > 57) {
				ls.add("" + c);
				i++;
			} else {
				str = "";
				while(i < s.length() && (c=s.charAt(i)) >= 48 && (c=s.charAt(i)) <= 57) {
					str += c;
					i++;
				}
				ls.add(str);
			}
		}while(i < s.length());
		return ls;
	}
	
	//中缀转换为后缀的函数
	public static List<String> parseSuffixExpreesionList(List<String> ls) {

		Stack<String> s1 = new Stack<String>();
		List<String> s2 = new ArrayList<String>();

		for(String item: ls) {
			if(item.matches("\\d+")) {
				s2.add(item);
			} else if (item.equals("(")) {
				s1.push(item);
			} else if (item.equals(")")) {
				while(!s1.peek().equals("(")) {
					s2.add(s1.pop());
				}
				s1.pop();
			} else {
				while(s1.size() != 0 && Operation.getValue(s1.peek()) >= Operation.getValue(item) ) {
					s2.add(s1.pop());
				}
				s1.push(item);
			}
		}

		while(s1.size() != 0) {
			s2.add(s1.pop());
		}
		return s2;
		
	}
	

	

	public static List<String> getListString(String suffixExpression) {
		// suffixExpression
		String[] split = suffixExpression.split(" ");
		List<String> list = new ArrayList<String>();
		for(String ele: split) {
			list.add(ele);
		}
		return list;
		
	}

	
	public static int calculate(List<String> ls) {

		Stack<String> stack = new Stack<String>();

		for (String item : ls) {

			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);//计算结果入栈
			}
			
		}
		return Integer.parseInt(stack.pop());//最后留在栈中的，就是最后的结果
	}

}


class Operation {
	private static int ADD = 1;
	private static int SUB = 1;
	private static int MUL = 2;
	private static int DIV = 2;
	

	public static int getValue(String operation) {
		int result = 0;
		switch (operation) {
		case "+":
			result = ADD;
			break;
		case "-":
			result = SUB;
			break;
		case "*":
			result = MUL;
			break;
		case "/":
			result = DIV;
			break;
		default:
			break;
		}
		return result;
	}
	
}
1
2
3
中缀表达式 List=[1, +, (, (, 2, +, 3, ), *, 4, ), -, 5]
后缀表达式 List[1, 2, 3, +, 4, *, +, 5, -]
expression=16

4. 递归

4.1 初识递归

递归的简单介绍

简单的来说就是自己调用自己，每次调用的时候都传入不同的变量，递归有助于解决，复杂的问题，虽然他自己空间复杂度太高有时会导致算法的效率不高

递归需要遵守的规则

  • 执行一个方法的时候，就创建一个新的受保护的独立空间(栈空间)
  • 方法的局部变量是独立的
  • 如果方法中使用的是引用类型的变量(比如数组)，就会共享该类型的的数据
  • 递归必须向退出递归的条件逼近，否则就是无限递归，出现StackOverflowError
  • 当一个方法执行完毕，或者遇到return的时候，就会返回，遵守谁调用就返回给谁的原则

4.2 迷宫问题

从迷宫的左上角走到右下角，问你路径(这里还不是最短路径)

实现思路

  • 使用1标记墙，0代表没有走过的路，2代表走过可行的路，3代表走不通的路
  • 使用递归依次遍历下，右，上，左四个方向，如果走不通则标记当前为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
public  class MiGong{
	public static void main(String[] args) {
		int[][] map =  new int[8][7];

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

		for(int i = 0;i<8;i++){
			map[i][0] = 1;
			map[i][6] = 1;
		}

		map[3][1] = 1;
		map[3][2] = 1;

		setway(map,1,1);

		for (int i = 0; i < 8; i++) {
			for (int j = 0; j < 7; j++) {
				System.out.print(map[i][j] + " ");
			}
			System.out.println();
		}
	}


	public static boolean setway(int map[][], int i, int j){
		if(map[6][5] == 2){
			return true;//递归出口
		}

		if(map[i][j] == 0){
			map[i][j] = 2;//先假设走得通，做个标记，表示已经走过
			if(setway(map,i+1,j)){//向下
				return true;
			}else if(setway(map,i,j+1)){//向右
				return true;
			}else if(setway(map,i-1,j)){//向上
				return true;
			}else if(setway(map,i,j-1)){//向左
				return true;
			}else{
				map[i][j] = 3;//这个点走不通
				return false;
			}
		}else{// map[i][j] == 1,2,3
			return false;
		}
	}



}
1
2
3
4
5
6
7
8
1 1 1 1 1 1 1 
1 2 0 0 0 0 1 
1 2 2 2 0 0 1 
1 1 1 2 0 0 1 
1 0 0 2 0 0 1 
1 0 0 2 0 0 1 
1 0 0 2 2 2 1 
1 1 1 1 1 1 1

4.3 八皇后问题

问题描述

这个问题是一个经典的问题，回溯算法的经典案例，即在一个8*8的棋盘上面，摆放8个皇后棋子，这8个棋子不能在同一行，不能再同一列，也不能在同一条斜线上，问一共有几种摆放的方法

实现思路

  • 第一个棋子先放在第一行第一列
  • 第二个棋子放在第二行第一列，判断是不是可行，不可行就放在第二行第二列，继续判断
  • 继续上述步骤，直到摆放完8个棋子，得到一个可行的结果，如果都不可行，就返回上一个步骤，放在下一个位置
  • 一直回溯，直到找到全部的解

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
public class Queue8 {
	int max = 8;
	int[] array = new int[max];//数组是引用类型
	static int  count = 0;

	public static void main(String[] args) {
		Queue8 queue = new Queue8();
		queue.cheak(0);
		System.out.println("总数为 ："+count);
	}


	//摆放棋子的函数

	/**
	 *
	 *
	 * @param x   在第几行摆放，也就是横坐标
	 */
	public void  cheak(int x){
		//递归的出口
		if(x == 8){
			print(array);
			count++;
			return;
		}
		//i 代表在第几列摆放棋子
		for (int i = 0; i < max; i++) {
			array[x] = i;
			if(judge(x)){//如果在这一列成功摆放
				cheak(x+1);
			}
		}
	}


	public boolean judge(int n){
		//如果在同一列或者同一条斜线上，则不成立,后面斜线的判断其实就是类似 斜率的判断
		for(int i = 0; i < n; i++) {
			if(array[i] == array[n] || Math.abs(n-i) == Math.abs(array[n] - array[i]) ) {
				return false;
			}
		}
		return true;
	}


	public void print(int[] array){
		for (int i = 0; i < 8; i++) {
			System.out.print(" "+ array[i]);
		}
		System.out.println();
	}
}

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

5. 排序算法

5.1 算法的时间复杂度

我们一般使用O()来表示算法的时间复杂度

推导时间复杂度

  1. 用1取代所有的加法常数
  2. 只保留最高阶项
  3. 去掉最高阶项的常数(非常数的时候)

常数阶

比如一般的分支结构都是O(1)

1
2
int sum = 0;
System.out.println(sum);

线性阶

循环结构就是O(n)

1
2
3
for(int i = 0;i<n;i++){
    System.out.println(i);
}

对数阶

下面的这写代码，每次循环count就变为两倍，则运行的次数就是2x=n2^x=n,所以x=log2nx=log_2 n,时间复杂度就是O(log n)

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

平方阶

简单来说就是双重循环就是平方阶了，当然还是得按照推导方法来推导

常见的时间度

O(1) < O(logn)< O(n)< O(nlogn)< O(n2n^2)< O(n3n^3)< O(2n2^n)< O(n!)< O(nnn^n)

算法的空间复杂度

衡量算法性能的另一个指示标准，算法的空间复杂度的计算公式记作S(n) = O(f(n)); n为问题的规模，f(n)为语句关于n所占存储空间的函数

各个算法的动画演示

由于这个博客系统的原因，动图显示不出来，因此在这里贴一个动图连接数据结构与算法系列–十大排序（附动态图解） - 知乎 (zhihu.com)

5.2 冒泡排序

冒泡简介

冒泡排序应该说是程序员的入门排序算法了，他的基本的思想就是，从数组的较小的元素开始，依次比较相邻的两个元素的值，如果是逆序，则把两个值交换，

因为需要比较很多次，因此效率很低。

优化

如果一趟比较下来没有进行过交换，就说明序列有序，因此可以通过设置一个flag来判断，用来减少不必要的交换

代码

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
//冒泡排序
public class BubbleSort{

   public static void main(String[] args) {
      int arr[] = {3,9,-1,10,20};
      bubblesort(arr);
      System.out.println(Arrays.toString(arr));

      //测试性能
      int[] testArr = new int[80000];
      for(int i =0; i < 80000;i++) {
         testArr[i] = (int)(Math.random() * 8000000);
      }//生成80000万个数据
      long startTime=System.currentTimeMillis(); //获取开始时间

      bubblesort(testArr);

      long endTime=System.currentTimeMillis(); //获取结束时间
      System.out.println("程序运行时间： "+(endTime-startTime)+"ms");

   }


   public static void bubblesort(int[] arr){
      int temp = 0;
      boolean flag = false;//加flag优化
      
      for (int i = 0; i < arr.length-1; i++) {
         for (int j = i+1; j < arr.length; j++) {
            if(arr[i]<arr[j]){
               flag = true;
               temp = arr[i];
               arr[i] = arr[j];
               arr[j] = temp;
            }
         }
          
         if(!flag){
            break;
         }else{
            flag = false;
         }
      }


   }

}
1
2
[20, 10, 9, 3, -1]
八万个随机数据程序运行时间： 7760ms

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
//选择排序
public class SelectSort{

	public static void main(String[] args) {
		int[] arr = {101, 34, 119, 1, -1, 90, 123};
		selectsort(arr);
		System.out.println(Arrays.toString(arr));

		//测试性能
		int[] testArr = new int[80000];
		for(int i =0; i < 80000;i++) {
			testArr[i] = (int)(Math.random() * 8000000);
		}//生成80000个数据
		long startTime=System.currentTimeMillis(); //获取开始时间

		selectsort(testArr);

		long endTime=System.currentTimeMillis(); //获取结束时间
		System.out.println("程序运行时间： "+(endTime-startTime)+"ms");


	}

	public static void selectsort(int arr[]){

		int min;//熟悉的交换排序
		int minIndex;

		for (int i = 0; i < arr.length-1; i++) {
			min = arr[i];
			minIndex = i;
			for (int j = i+1; j < arr.length; j++) {//寻找后面位置没有进行排序的最小的数字
				if(min > arr[j]){
					min = arr[j];
					minIndex = j;
				}
			}
			if(min != arr[i]){//发现了有更小的数字就交换
				arr[minIndex] = arr[i];
				arr[i] = min;
			}
		}
	}

}
1
2
[-1, 1, 34, 90, 101, 119, 123]
八万个随机数据程序运行时间：  1999ms

5.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
//插入排序
public class InsertSort {
    public static void main(String[] args) {
        int[] arr = {101, 34, 119, 1, -1, 89};
        insertsort(arr);
        System.out.println(Arrays.toString(arr));

        //测试性能
        int[] testArr = new int[80000];
        for (int i = 0; i < 80000; i++) {
            testArr[i] = (int) (Math.random() * 8000000);
        }//生成80000个数据
        long startTime=System.currentTimeMillis(); //获取开始时间

        insertsort(testArr);

        long endTime=System.currentTimeMillis(); //获取结束时间
        System.out.println("程序运行时间： "+(endTime-startTime)+"ms");

    }


    public static void insertsort(int[] arr) {
        int insertVal;
        int insertIndex;

        for (int i = 1; i < arr.length; i++) {
            insertVal = arr[i];
            insertIndex = i - 1;//此时指向前面待插入的最后一位
            while (insertIndex >= 0 && insertVal < arr[insertIndex]) {
                arr[insertIndex + 1] = arr[insertIndex];
                insertIndex--;
            }
            //这时候就找到了应该插入的位置

            if (insertIndex + 1 != i) {//优化
                arr[insertIndex + 1] = insertVal;//这里的索引是多移动了一位的  所以需要加上一个 1
            }

        }

//        //另一种写法
//        for (int i = gap; i < arr.length; i++) {
//            int insertVal = arr[i];
//            int insertIndex = i ;
//            if(arr[insertIndex]<arr[insertIndex-gap]) {
//                while (insertIndex- gap >= 0 && insertVal < arr[insertIndex-gap]) {
//                    arr[insertIndex ] = arr[insertIndex- gap];
//                    insertIndex -= gap;//不断的向前移动找寻待插入的位置
//                }
//            }
//            arr[insertIndex] = insertVal;
//        }
    }


}
1
2
[-1, 1, 34, 89, 101, 119]
八万个随机数据程序运行时间： 437ms

5.5 希尔排序

希尔排序简介

很明显，希尔排序是由希尔这个人提出来的，他是简单插入排序的经过改进后的一个更高效的版本，也被称为缩小增量排序。他的基本思想就是，把数组数据按照下标的一些分组，不断进行插入排序，分组逐渐减少，当减少到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
//shell排序
public class ShellSort {

    public static void main(String[] args) {
        int[] arr = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
        shellsortSwap(arr);
        System.out.println(Arrays.toString(arr));

        int[] arr2 = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
        shellsortInsert(arr2);
        System.out.println(Arrays.toString(arr2));

        //测试性能
        int[] testArr = new int[80000];
        for (int i = 0; i < 80000; i++) {
            testArr[i] = (int) (Math.random() * 8000000);
        }//生成80000个数据
        long startTime=System.currentTimeMillis(); //获取开始时间

        shellsortInsert(testArr);

        long endTime=System.currentTimeMillis(); //获取结束时间
        System.out.println("程序运行时间： "+(endTime-startTime)+"ms");

    }


    //希尔排序交换法
    public static void shellsortSwap(int[] arr) {
        int temp;
        for (int gap = arr.length / 2; gap > 0; gap /= 2) {
            //交换法的希尔排序其实这里面的这一层就是加了步长的冒泡
            //所以效率低下
            for (int i = 0; i < arr.length; i++) {
                for (int j = i - gap; j >= 0; j -= gap) {
                    if (arr[j] > arr[j + gap]) {
                        temp = arr[j + gap];
                        arr[j + gap] = arr[j];
                        arr[j] = temp;
                    }
                }
            }
        }

    }

    //这里才是正宗的shell排序
    public static void shellsortInsert(int[] arr) {
        for (int gap = arr.length / 2; gap > 0; gap /= 2) {//步长逐渐减少
            //里面使用直接插入排序
            for (int i = gap; i < arr.length; i++) {
                int insertVal = arr[i];
                int insertIndex = i;
                if (arr[insertIndex] < arr[insertIndex - gap]) {
                    while (insertIndex - gap >= 0 && insertVal < arr[insertIndex - gap]) {
                        arr[insertIndex] = arr[insertIndex - gap];
                        insertIndex -= gap;//不断的向前移动找寻待插入的位置
                    }
                }
                arr[insertIndex] = insertVal;
            }
        }

    }
1
2
3
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
程序运行时间： 17ms

5.6 快速排序

快速排序简介

快速排序是对冒泡排序的一种改进，基本思想就是把将要排序的数据分为两组，其中一部分的数据比另外的一部分都要小，然后把这两组数据分别再次进行相同的操作，直到排序完成，整个过程通过递归实现。快排是一种不稳定排序

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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
//快速排序
public class QuickSort {


    public static void main(String[] args) {
        int[] arr = {-9, 78, 0, 23, -567, 70, -1, 900, 4561};
        quicksort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));

        //测试性能
        int[] testArr = new int[80000];
        for (int i = 0; i < 80000; i++) {
            testArr[i] = (int) (Math.random() * 8000000);
        }//生成80000个数据
        long startTime = System.currentTimeMillis(); //获取开始时间

        quicksort(testArr, 0, testArr.length - 1);

        long endTime = System.currentTimeMillis(); //获取结束时间
        System.out.println("程序运行时间： " + (endTime - startTime) + "ms");

    }


    public static void quicksort(int[] arr, int low, int high) {
        int pivot;
        if (low < high) {
            pivot = Partition(arr, low, high);
            quicksort(arr, low, pivot - 1);//对左边快排
            quicksort(arr, pivot + 1, high);//对右边快排
        }
    }

    public static int Partition(int[] arr, int low, int high) {
        int pivotkey;
        pivotkey = arr[low];//把低位的数当作中轴
        while (low < high) {
            while (low < high && arr[high] >= pivotkey) {
                high--;
            }
            Swap(arr, low, high);//不断寻找比中轴大的数，交换到右边
            while (low < high && arr[low] <= pivotkey) {
                low++;
            }
            Swap(arr, low, high);//不断寻找比中轴小的数，交换到左边
        }//low==high了，退出循环，中轴数已经被环岛路中间
        return low;//返回下标
    }

    public static void Swap(int[] arr, int a, int b) {
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }


}

1
2
[-567, -9, -1, 0, 23, 70, 78, 900, 4561]
程序运行时间： 11ms

5.7 归并排序

归并排序简介

这是一种利用归并思想实现的排序算法，该算法采用经典的分治思想，(分)先把数据分成很小的部分，(治)然后分别排序，即分而治之。

代码

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

	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));


		//测试性能
		int[] testArr = new int[80000];
		for (int i = 0; i < 80000; i++) {
			testArr[i] = (int) (Math.random() * 8000000);
		}//生成80000个数据
		int testTemp[] = new int[testArr.length];//需要额外的空间

		long startTime = System.currentTimeMillis(); //获取开始时间

		mergeSort(testArr, 0, testArr.length - 1,testTemp);

		long endTime = System.currentTimeMillis(); //获取结束时间
		System.out.println("程序运行时间： " + (endTime - startTime) + "ms");


	}
	
	

	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);//治
		}
	}

    //将小的部分合成有序的大部分的函数，即治
	public static void merge(int[] arr, int left, int mid, int right, int[] temp) {
		
		int i = left;
		int j = mid + 1;
		int t = 0;
		

		while (i <= mid && j <= right) {
			if(arr[i] <= arr[j]) {
				temp[t] = arr[i];
				t += 1;
				i += 1;
			} else {
				temp[t] = arr[j];
				t += 1;
				j += 1;
			}
		}//分别在临时数组中放入两个之中较小的数

		while( i <= mid) {
			temp[t] = arr[i];
			t += 1;
			i += 1;	
		}//将前面剩余的数放入数组
		
		while( j <= right) {
			temp[t] = arr[j];
			t += 1;
			j += 1;	
		}//将后面剩余的数放入数组

		t = 0;
		int tempLeft = left;
		while(tempLeft <= right) {
			arr[tempLeft] = temp[t];
			t += 1;
			tempLeft += 1;//将数据倒腾回去
		}
		
	}

}
1
2
[1, 2, 3, 4, 5, 6, 7, 8]
程序运行时间： 12ms

5.8 基数排序

基数排序简介

基数排序是稳定的排序算法，是桶排序的拓展。基本的思想就是把每个数字切割出来，然后将他们按照个位大小放入桶中，排完之后，取出放入数组，然后比较十位大小，直到排序完。

代码

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

	public static void main(String[] args) {
		int arr[] = { 53, 3, 542, 748, 14, 214};
		radixSort(arr);
		System.out.println(Arrays.toString(arr));

		//测试性能
		int[] testArr = new int[80000];
		for (int i = 0; i < 80000; i++) {
			testArr[i] = (int) (Math.random() * 8000000);
		}//生成80000个数据
		int testTemp[] = new int[testArr.length];//需要额外的空间

		long startTime = System.currentTimeMillis(); //获取开始时间

		radixSort(testArr);

		long endTime = System.currentTimeMillis(); //获取结束时间
		System.out.println("程序运行时间： " + (endTime - startTime) + "ms");
	}


	public static void radixSort(int[] arr) {

		int max = arr[0];
		for(int i = 1; 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]++;//该桶放的数字数量加一
			}

			int index = 0;

			for(int k = 0; k < bucketElementCounts.length; k++) {//遍历每个桶
				if(bucketElementCounts[k] != 0) {
					for(int l = 0; l < bucketElementCounts[k]; l++) {
						arr[index++] = bucket[k][l];//将桶内的数据拿出来放在数组里面
					}
				}
				bucketElementCounts[k] = 0;
				
			}
			
		}
	}
}
1
2
[3, 14, 53, 214, 542, 748]
程序运行时间： 16ms

5.9 排序算法总结

排序算法

相关属术语解释：

  • 稳定：如果 a 原本在 b 前面，而 a == b ，排序之后 a 仍然在 b 的前面；
  • 不稳定：如果 a 原本在 b 的前面，而 a == b ，排序之后 a 可能会出现在 b 的后面；
  • 内排序：所有排序操作都在内存中完成；
  • 外排序：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行；
  • 时间复杂度：一个算法执行所耗费的时间。
  • 空间复杂度：运行完一个程序所需内存的大小。
  • n :数据规模
  • k :“桶”的个数
  • In - place : 不占用额外内存
  • Out - place ：占用额外内存

6. 查找

6.1 二分查找

实现思路

  • 首先通过左右两个索引确定数组的下标，即mid

    • $ mid = low + F(k - 1) -1 $

  • 让target与中间值对比，如果target大于该值，则继续往前二分查找，否则，就往后继续二分查找

  • 如果中间值==target说明目标找到，结束递归，或者左边的索引已经大于了右边的索引，说明没有找到，结束递归

  • 特别注意：二分查找的前提是这一系列的数据都已经排序好，后续的几个查找，都需要排序好

代码

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

    public static void main(String[] args) {
        int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20};
        int resIndex = binarySearch(arr, 0, arr.length - 1, 17);
        System.out.println("resIndex=" + resIndex);

        int arr2[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 20, 20, 20};
        List<Integer> resIndexList = binarySearch2(arr2, 0, arr.length - 1, 20);
        System.out.println("resIndex=" + resIndexList);


    }

    
    //查找单一的值，找到就返回下标
    public static int binarySearch(int[] arr, int low, int high, int target) {
        if (low > high || target > arr[arr.length - 1] || target < arr[0]) {
            return -1;
        }
        int mid = (low + high) / 2;
        if (arr[mid] > target) {
            return binarySearch(arr, low, mid - 1, target);
        } else if (arr[mid] < target) {
            return binarySearch(arr, mid + 1, high, target);
        } else {
            return mid;
        }

    }

    //找寻等于该值的所有下标
    public static List<Integer> binarySearch2(int[] arr, int low, int high, int target) {
        if (low > high || target > arr[arr.length - 1] || target < arr[0]) {
            return new ArrayList<Integer>();
        }
        int mid = (low + high) / 2;
        if (arr[mid] > target) {
            return binarySearch2(arr, low, mid - 1, target);
        } else if (arr[mid] < target) {
            return binarySearch2(arr, mid + 1, high, target);
        } else {
            //找到下标之后，向两边遍历
            ArrayList<Integer> resIndexlist = new ArrayList<>();
            int temp = mid - 1;
            while(true) {
                if (temp < 0 || arr[temp] != target) {
                    break;
                }
                resIndexlist.add(temp);
                temp -= 1;
            }
            resIndexlist.add(mid);

            temp = mid +1;
            while(true) {
                if (temp >= arr.length || arr[temp] != target) {
                    break;
                }
                resIndexlist.add(temp);
                temp += 1;
            }
            return resIndexlist;

        }
    }
}
1
2
resIndex=16
resIndex=[17, 18, 19]

6.2 插值查找

实现思路

简单的来说，就是把上述二分查找的mid索引，换成了一个新的公式算出来的新索引，其他的都一样

$ mid = low + \frac{target - arr[low]}{arr[high] - arr[low]} * (high - low) $

代码

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 class InsertValueSearch {


    public static void main(String[] args) {
        int arr[] = {1, 8, 10, 89, 1000, 1234};
        int resIndex = insertvalueSearch(arr,0, arr.length-1,1234);
        System.out.println(resIndex);
    }


    public static int insertvalueSearch(int[] arr, int low, int high, int target) {
        if (target < arr[0] || target > arr[arr.length - 1] || low > high) {
            return -1;
        }

        int mid = low + (high - low) * (target - arr[low]) / (arr[high] - arr[low]);//精髓在于这个公式
        if (target > arr[mid]) {
            return insertvalueSearch(arr, mid + 1, high, target);
        } else if (target < arr[mid]) {
            return insertvalueSearch(arr, low, mid - 1, target);
        } else {
            return mid;
        }
    }
}
1
该数据下标是5

6.3 斐波那契查找

实现思路

斐波那契查找与前面两种查找类似，仅仅只是改变了中间索引mid的位置，这个索引现在位于黄金分割点附近，即

$ mid = low + F(k - 1) -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
public class FibonacciSearch {
    static int massize = 20;

    public static void main(String[] args) {
        int[] arr = {1, 8, 10, 89, 1000, 1234};
        int resIndex = fibonaccisearch(arr, 1000);
        System.out.println(resIndex);
    }

    //先构造一个斐波那契数列
    public static int[] creatfibnacci() {
        int[] f = new int[massize];
        f[0] = 0;
        f[1] = 1;
        for (int i = 2; i < massize; i++) {
            f[i] = f[i - 1] + f[i - 2];
        }
        return f;
    }


    public static int fibonaccisearch(int[] arr, int target) {
        int f[] = creatfibnacci();
        int low = 0;
        int high = arr.length - 1;
        int k = 0;
        int mid = 0;
        while (high > f[k] - 1) {
            k++;
        }//找到大于数组最大小标的最小fibonacci数

        int[] temp = Arrays.copyOf(arr, f[k]);
        //创造一个长度为f[k]的包含arr数组的临时数组
        for (int i = high + 1; i < f[k]; i++) {
            temp[i] = arr[high];
        }//将数组后面空出的部分用最大值填满


        while (low <= high) {
            mid = low + f[k - 1] - 1;
            if (temp[mid] > target) {
                high = mid - 1;
                k -= 1;
                //前一段是f[k-1]，f[k-1]再分一次 ，就是 f[k-2]+f[k-3] 所以这里减1
            } else if (temp[mid] < target) {
                low = mid + 1;
                k -= 2;//后一段是f[k-2]，f[k-2]再分一次，就是 f[k-3]+f[k-4] 所以这里减2
            } else {

                //因为数组是补充后的，可能查到后面重复的数字，所以这里返回两者中较小的数字
                if (mid < high) {
                    return mid;
                } else {
                    return high;
                }
            }
        }
        return -1;//没有找到
    }

}

7. 哈希表

7.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
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
public class HashTabDemo {

	public static void main(String[] args) {
		
		//创建新的哈希表
		HashTab hashTab = new HashTab(7);
		

		String key = "";
		Scanner scanner = new Scanner(System.in);
		while(true) {
			System.out.println("add:  添加数据");
			System.out.println("list: 展示");
			System.out.println("find: 查找");
			System.out.println("exit: 退出");
			
			key = scanner.next();
			switch (key) {
			case "add":
				System.out.println("输入id");
				int id = scanner.nextInt();
				System.out.println("输入姓名");
				String name = scanner.next();

				Emp emp = new Emp(id, name);
				hashTab.add(emp);
				break;
			case "list":
				hashTab.list();
				break;
			case "find":
				System.out.println("输入查找id");
				id = scanner.nextInt();
				hashTab.findEmpById(id);
				break;
			case "exit":
				scanner.close();
				System.exit(0);
			default:
				break;
			}
		}
		
	}

}


class HashTab {
	private EmpLinkedList[] empLinkedListArray;//散列表
	private int size;
	
	//初始化
	public HashTab(int size) {
		this.size = size;
		//初始化empLinkedListArray
		empLinkedListArray = new EmpLinkedList[size];
		//在每个后面初始化一个链表
		for(int i = 0; i < size; i++) {
			empLinkedListArray[i] = new EmpLinkedList();
		}
	}
	
	//添加函数
	public void add(Emp emp) {
		int empLinkedListNO = hashFun(emp.id);
		empLinkedListArray[empLinkedListNO].add(emp);
		
	}
	//展示hashtab
	public void list() {
		for(int i = 0; i < size; i++) {
			empLinkedListArray[i].list(i);
		}
	}
	
	//根据id来寻找节点
	public void findEmpById(int id) {
		int empLinkedListNO = hashFun(id);
		Emp emp = empLinkedListArray[empLinkedListNO].findEmpById(id);
		if(emp != null) {
			System.out.printf("在第%d条链表找到id = %d\n", (empLinkedListNO + 1), id);
		}else{
			System.out.println("没有找到该雇员");
		}
	}
	

	public int hashFun(int id) {
		return id % size;
	}
	
	
}

//雇员节点
class Emp {
	public int id;
	public String name;
	public Emp next; //next 初始null
	public Emp(int id, String name) {
		super();
		this.id = id;
		this.name = name;
	}
}

//EmpLinkedList
class EmpLinkedList {

	private Emp head; //null

	public void add(Emp emp) {
		if(head == null) {
			head = emp;
			return;
		}

		Emp curEmp = head;
		while(true) {
			if(curEmp.next == null) {
				break;
			}
			curEmp = curEmp.next;
		}

		curEmp.next = emp;
	}
	
	//展示的函数
	public void list(int no) {
		if(head == null) { 
			System.out.println("第"+(no+1)+"链表为空");
			return;
		}
		System.out.print("第"+(no+1)+"条链表 信息为");
		Emp curEmp = head;
		while(true) {
			System.out.printf(" => id=%d name=%s\t", curEmp.id, curEmp.name);
			if(curEmp.next == null) {
				break;
			}
			curEmp = curEmp.next;
		}
		System.out.println();
	}
	

	public Emp findEmpById(int id) {

		if(head == null) {
			System.out.println("空表");
			return null;
		}

		Emp curEmp = head;
		while(true) {
			if(curEmp.id == id) {
				break;
			}

			if(curEmp.next == null) {
				curEmp = null;
				break;
			}
			curEmp = curEmp.next;
		}
		
		return curEmp;
	}
	
}

8. 树

8.1 树的基本介绍

树的基本介绍，在另一篇博客中有详细的介绍，这里不在详述

8.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
//BinaryTree 
class BinaryTree {
	private HeroNode root;

	public void setRoot(HeroNode root) {
		this.root = root;
	}
	
	
	public void preOrder() {
		if(this.root != null) {
			this.root.preOrder();
		}else {
			System.out.println("该树为空");
		}
	}
	

	public void infixOrder() {
		if(this.root != null) {
			this.root.infixOrder();
		}else {
			System.out.println("该树为空");
		}
	}

	public void postOrder() {
		if(this.root != null) {
			this.root.postOrder();
		}else {
			System.out.println("该树为空");
		}
	}
	
	
}

//HeroNode
class HeroNode {
	private int no;
	private String name;
	private HeroNode left; //null
	private HeroNode right; //null
	public HeroNode(int no, String name) {
		this.no = no;
		this.name = name;
	}
	public int getNo() {
		return no;
	}
	public void setNo(int no) {
		this.no = no;
	}
	public String getName() {
		return name;
	}
	public void setName(String name) {
		this.name = name;
	}
	public HeroNode getLeft() {
		return left;
	}
	public void setLeft(HeroNode left) {
		this.left = left;
	}
	public HeroNode getRight() {
		return right;
	}
	public void setRight(HeroNode right) {
		this.right = right;
	}
	@Override
	public String toString() {
		return "HeroNode [no=" + no + ", name=" + name + "]";
	}
		
	
	//前序遍历
	public void preOrder() {
		System.out.println(this);
		if(this.left != null) {
			this.left.preOrder();
		}
		if(this.right != null) {
			this.right.preOrder();
		}
	}
	//中序遍历
	public void infixOrder() {
		
		if(this.left != null) {
			this.left.infixOrder();
		}

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

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
public HeroNode preOrderSearch(int no) {
		//一遇到的就是，直接返回
		if(this.no == no) {
			return this;
		}
		HeroNode resNode = null;
		if(this.left != null) {
			resNode = this.left.preOrderSearch(no);//向左继续前序遍历
		}
		if(resNode != null) {//左子树找到
			return resNode;
		}
		//前面没有返回，继续执行到了这一步，说明左边没有找到
		if(this.right != null) {
			resNode = this.right.preOrderSearch(no);//向右继续遍历
		}
		return resNode;
	}
	
	//中序搜索
	public HeroNode infixOrderSearch(int no) {
		HeroNode resNode = null;
		if(this.left != null) {
			resNode = this.left.infixOrderSearch(no);//向左继续中序遍历
		}
		if(resNode != null) {
			return resNode;//找到了就返回
		}
		//对比号码找到了就返回
		if(this.no == no) {
			return this;
		}
		//否则继续向右边搜索
		if(this.right != null) {
			resNode = this.right.infixOrderSearch(no);
		}
		return resNode;
		
	}
	
	//后序搜索
	public HeroNode postOrderSearch(int no) {
		//流程都差不多
		HeroNode resNode = null;
		if(this.left != null) {
			resNode = this.left.postOrderSearch(no);
		}
		if(resNode != null) {
			return resNode;
		}
		
		if(this.right != null) {
			resNode = this.right.postOrderSearch(no);
		}
		if(resNode != null) {
			return resNode;
		}
		if(this.no == no) {
			return this;
		}
		return resNode;
	}

8.4 二叉树删除相应的节点

实现思路

  • 如果是空树root，如果只有一个root节点，则等价于将二叉树置空
  • 因为是单项的树，所以删除的时候需要寻找待删除节点的上一个节点
  • 在每个节点里写好删除的方法，如果下一个节点不为空并且数字符合，那么就置空，然后返回
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
class binaryTree中：

public void delNode(int no) {
		if(root != null) {
			if(root.getNo() == no) {
				root = null;
			} else {
				root.delNode(no);
			}
		}else{
			System.out.println("空树，不能删除");
		}
	}




class node中：

public void delNode(int no) {

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

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

8.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
public class HeapSort {

	public static void main(String[] args) {
		int arr[] = {3,9,-1,10,20};
		heapSort(arr);
		System.out.println(Arrays.toString(arr));
		//测试性能
		int[] testArr = new int[80000];
		for(int i =0; i < 80000;i++) {
			testArr[i] = (int)(Math.random() * 8000000);
		}//生成80000万个数据
		long startTime=System.currentTimeMillis(); //获取开始时间

		heapSort(testArr);

		long endTime=System.currentTimeMillis(); //获取结束时间
		System.out.println("八万个随机数据程序运行时间： "+(endTime-startTime)+"ms");

	}


	public static void heapSort(int arr[]) {
		int temp = 0;
		

		//调整为大顶堆
		for(int i = arr.length / 2 -1; i >=0; i--) {
			adjustHeap(arr, i, arr.length);
		}

		//将最后一个交换后继续调整为大顶堆
		for(int j = arr.length-1;j >0; j--) {

			temp = arr[j];
			arr[j] = arr[0];
			arr[0] = temp;
			adjustHeap(arr, 0, j); 
		}

		
	}
	

	//调整为大顶堆的函数
	public  static void adjustHeap(int arr[], int i, int lenght) {

		//保存当前的变量
		int temp = arr[i];


		for(int k = i * 2 + 1; k < lenght; k = k * 2 + 1) {
			if(k+1 < lenght && arr[k] < arr[k+1]) {//说明左子节点小于右子节点
				k++;//指向右子节点(较大的节点
			}
			if(arr[k] > temp) {//如果子节点大于父节点
				arr[i] = arr[k];//将较大的值赋给当前节点
				i = k;//继续循环比较
			} else {
				break;
			}
		}
		//将小的那位置赋为小的值，完成交换
		arr[i] = temp;
	}
	
}

8.6 赫夫曼树

基本介绍

给定n个权值作为n个叶子节点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的树为最优二叉树，也称赫夫曼树

实现思路

将每个数据看作是一棵最简单的二叉树，不断取出根节点权值最小的两颗二叉树，组成一棵新的二叉树，该颗二叉树根节点的权值是前面两颗二叉树根节点权值的和，然后再将这颗新的二叉树放回去，再次排序，不断选出最小的两棵二叉树组合。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
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
public class HuffmanTree {

	public static void main(String[] args) {
		int arr[] = { 13, 7, 8, 3, 29, 6, 1 };
		Node root = createHuffmanTree(arr);	
		preOrder(root); 
		
	}
		
	public static void preOrder(Node root) {
		if(root != null) {
			root.preOrder();
		}else{
			System.out.println("kono空树da~~");
		}
	}

	
	public static Node createHuffmanTree(int[] arr) {
		
		List<Node> nodes = new ArrayList<Node>();
		for (int value : arr) {
			nodes.add(new Node(value));
		}
		
		
		
		while(nodes.size() > 1) {
				
			Collections.sort(nodes);		
			System.out.println("nodes =" + nodes);		
			Node leftNode = nodes.get(0);			
			Node rightNode = nodes.get(1);
						
			Node parent = new Node(leftNode.value + rightNode.value);
			parent.left = leftNode;
			parent.right = rightNode;
					
			nodes.remove(leftNode);
			nodes.remove(rightNode);	
			nodes.add(parent);
		}
		
		//���ع���������root���
		return nodes.get(0);
		
	}
}

//为了实现排序，需要实现这个排序的接口，里面重写这个compareTo的方法
class Node implements Comparable<Node> {
	int value;
	char c; 
	Node left; 
	Node right; 


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

	@Override
	public String toString() {
		return "Node [value=" + value + "]";
	}

	@Override
	public int compareTo(Node o) {
		// TODO Auto-generated method stub

		return this.value - o.value;//从小到大排序
	}

}

8.7 二叉排序树

二叉排序树介绍

二叉排序数(BST : Binary Sort Tree) 对于二叉排序树的任何一个非叶子节点，要求左子节点的值比当前节点的值小，右子节点的值比当前节点的值要大

二叉排序树的实现思路

  • 创建

    • 在创建的时候不断比较，比节点小的就不断去左边，直到找到合适的位置，右边同理

  • 删除

    • 需要找到待删除节点的父节点

    • 删除叶子节点

    • 删除只有一棵子树的节点（四种情况：target左右 * child左右）

    • 删除有两棵子树的节点（就是从targetNode里面找到最小的节点赋值给target节点，然后删除那个最小的节点的位置）

代码实现

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
public class BinarySortTreeDemo {

	public static void main(String[] args) {
		int[] arr = {7, 3, 10, 12, 5, 1, 9, 2};
		BinarySortTree binarySortTree = new BinarySortTree();
		for(int i = 0; i< arr.length; i++) {
			binarySortTree.add(new Node(arr[i]));
		}
		
		
		System.out.println("中序遍历~");
		binarySortTree.infixOrder(); // 1, 3, 5, 7, 9, 10, 12
		
	    
	   
	    binarySortTree.delNode(12);
	   
	 
	    binarySortTree.delNode(5);
	    binarySortTree.delNode(10);
	    binarySortTree.delNode(2);
	    binarySortTree.delNode(3);
		   
	    binarySortTree.delNode(9);
	    binarySortTree.delNode(1);
	    binarySortTree.delNode(7);
	    
		
		System.out.println("root=" + binarySortTree.getRoot());
		
		
		System.out.println("中序遍历");
		binarySortTree.infixOrder();
	}

}


class BinarySortTree {
	private Node root;
	
		
	public Node getRoot() {
		return root;
	}

	public Node search(int value) {
		if(root == null) {
			return null;
		} else {
			return root.search(value);
		}
	}
	
	public Node searchParent(int value) {
		if(root == null) {
			return null;
		} else {
			return root.searchParent(value);
		}
	}

	/**
	 *
	 * @param node  传入的根节点
	 * @return 返回最小的额node
	 */
	public int delRightTreeMin(Node node) {
		Node target = node;
		while(target.left != null) {
			target = target.left;
		//循环的查找左节点，就会找到最小值，因为小的放在左边
		}
		delNode(target.value);//删除最小的节点
		return target.value;//返回最小的值
	}
	
	
	//删除节点
	public void delNode(int value) {
		if(root == null) {
			return;
		}else {
			//targetNode
			Node targetNode = search(value);
			//没有找到target
			if(targetNode == null) {
				return;
			}
			//该科书只有一个节点
			if(root.left == null && root.right == null) {
				root = null;
				return;
			}
			

			Node parent = searchParent(value);
			//删除叶子节点
			if(targetNode.left == null && targetNode.right == null) {
				//说明这个节点是叶子节点
				if(parent.left != null && parent.left.value == value) {
					parent.left = null;
				} else if (parent.right != null && parent.right.value == value) {
					parent.right = null;
				}
			} else if (targetNode.left != null && targetNode.right != null) { //说明target有两个节点
				int minVal = delRightTreeMin(targetNode.right);
				targetNode.value = minVal;//返回右子树的最小值
				
				
			} else { // 剩下的情况就是只有一个子树的节点
				if(targetNode.left != null) {//说明这个待删除节点有左子节点
					if(parent != null) {
						//target是parent的左节点
						if(parent.left.value == value) {
							parent.left = targetNode.left;
						} else { //  target是parent的右节点
							parent.right = targetNode.left;
						} 
					} else {//待删除的节点没有父节点
						root = targetNode.left;
					}
				} else { //说明target有右子节点
					if(parent != null) {
						//target是parent的左节点
						if(parent.left.value == value) {
							parent.left = targetNode.right;
						} else { //target是parent的右节点
							parent.right = targetNode.right;
						}
					} else {//待删除的节点没有父节点
						root = targetNode.right;
					}
				}
				
			}
			
		}
	}

	public void add(Node node) {
		if(root == null) {
			root = node;
		} else {
			root.add(node);
		}
	}

	public void infixOrder() {
		if(root != null) {
			root.infixOrder();
		} else {
			System.out.println("kono空树da~");
		}
	}
}

//Node
class Node {
	int value;
	Node left;
	Node right;
	public Node(int value) {
		
		this.value = value;
	}
	
	
	
	public Node search(int value) {
		if(value == this.value) { 
			return this;
		} else if(value < this.value) {
			if(this.left  == null) {
				return null;
			}
			return this.left.search(value);
		} else {
			if(this.right == null) {
				return null;
			}
			return this.right.search(value);
		}
		
	}

	public Node searchParent(int value) {
		
		if((this.left != null && this.left.value == value) || 
				(this.right != null && this.right.value == value)) {
			return this;
		} else {
			if(value < this.value && this.left != null) {
				return this.left.searchParent(value); 
			} else if (value >= this.value && this.right != null) {
				return this.right.searchParent(value);
			} else {
				return null; 
			}
		}
		
	}
	
	@Override
	public String toString() {
		return "Node [value=" + value + "]";
	}


	public void add(Node node) {
		if(node == null) {
			return;
		}

		if(node.value < this.value) {
			if(this.left == null) {
				this.left = node;
			} else {

				this.left.add(node);
			}
		} else {
			if(this.right == null) {
				this.right = node;
			} else {

				this.right.add(node);
			}
			
		}
	}
	

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

8.8 平衡二叉树

简单的介绍

平衡二叉树(AVL树)也叫二叉搜索树，可以保证查询的效率高，平衡二叉树具有以下特点：他是一棵空树或者他的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是平衡二叉树，平衡二叉树的实现方法有 红黑树，AVL,替罪羊树，Treap，伸展树等。

实现思路

平衡二叉树可以通过上面的二叉排序树旋转而来，通常有左旋转，右旋转，双旋转。

左旋转

当则右子树的高度大于左子树的高度的时候，我们就需要左旋转来换个根节点，将右子树的高度压下去。

右旋转

当左子树的高度大于右子树的高度的时候，这个时候就需要进行右旋转，用来把左子树的高度压下去

双旋转

有时候，你进行上述两个操作之后，发现仍然没有达到平衡二叉树的要求，这个时候就需要双旋转的出场了，出现这个问题就是因为它的左子树的右子树的高度大于了它左子树左子树的高度，或者相反，都会导致这种情况的发生。解决的思路就是先对当前这个节点进行左旋转(或者右旋转)，再对当前节点进行右旋转(或者相反)

代码实现

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
public class AVLTreeDemo {

    public static void main(String[] args) {
        int[] arr = {10, 11, 7, 6, 8, 9};
        AVLTree avlTree = new AVLTree();

        for (int i = 0; i < arr.length; i++) {
            avlTree.add(new Node(arr[i]));
        }


        System.out.println("中序遍历");
        avlTree.infixOrder();

        System.out.println("在平衡处理后：");
        System.out.println("树的高度=" + avlTree.getRoot().height()); //3
        System.out.println("左子树的高度=" + avlTree.getRoot().leftHeight()); // 2
        System.out.println("右子树的高度=" + avlTree.getRoot().rightHeight()); // 2
        System.out.println("当前的根节点=" + avlTree.getRoot());//8


    }

}

// AVLTree
class AVLTree {

    //下面这一些部分都是跟前面的二叉搜索树是差不多的
    private Node root;

    public Node getRoot() {
        return root;
    }


    public Node search(int value) {
        if (root == null) {
            return null;
        } else {
            return root.search(value);
        }
    }

    public Node searchParent(int value) {
        if (root == null) {
            return null;
        } else {
            return root.searchParent(value);
        }
    }


    public int delRightTreeMin(Node node) {
        Node target = node;

        while (target.left != null) {
            target = target.left;
        }

        delNode(target.value);
        return target.value;
    }


    public void delNode(int value) {
        if (root == null) {
            return;
        } else {

            Node targetNode = search(value);

            if (targetNode == null) {
                return;
            }

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


            Node parent = searchParent(value);

            if (targetNode.left == null && targetNode.right == null) {

                if (parent.left != null && parent.left.value == value) {
                    parent.left = null;
                } else if (parent.right != null && parent.right.value == value) {
                    parent.right = null;
                }
            } else if (targetNode.left != null && targetNode.right != null) {
                int minVal = delRightTreeMin(targetNode.right);
                targetNode.value = minVal;

            } else {

                if (targetNode.left != null) {
                    if (parent != null) {

                        if (parent.left.value == value) {
                            parent.left = targetNode.left;
                        } else {
                            parent.right = targetNode.left;
                        }
                    } else {
                        root = targetNode.left;
                    }
                } else {
                    if (parent != null) {

                        if (parent.left.value == value) {
                            parent.left = targetNode.right;
                        } else {
                            parent.right = targetNode.right;
                        }
                    } else {
                        root = targetNode.right;
                    }
                }

            }

        }
    }


    public void add(Node node) {
        if (root == null) {
            root = node;
        } else {
            root.add(node);
        }
    }


    public void infixOrder() {
        if (root != null) {
            root.infixOrder();
        } else {
            System.out.println("这怕是个空树");
        }
    }
}

// Node
class Node {
    int value;
    Node left;
    Node right;

    public Node(int value) {

        this.value = value;
    }

    //左子树的高度
    public int leftHeight() {
        if (left == null) {
            return 0;
        }
        return left.height();
    }

    //右子树的高度
    public int rightHeight() {
        if (right == null) {
            return 0;
        }
        return right.height();
    }

    //返回以该节点为根节点的树的高度
    //简直是牛逼
    public int height() {
        return Math.max(left == null ? 0 : left.height(), right == null ? 0 : right.height()) + 1;//最后还需要加上当前这个节点
    }//递归的去寻找左右子树的高度最大值，就是这棵树的高度

    //左旋转的方法
    private void leftRotate() {
        //六步走的方法

        //以当前节点的值，创建新节点
        Node newNode = new Node(value);
        //把新节点的左子树设置为当前节点的左子树
        newNode.left = left;
        //把新节点的右子树设置为当前节点右子树的左子树
        newNode.right = right.left;
        //把当前节点的值替换成右子点的值
        value = right.value;
        //把当前的右子树设置成右子树的右子树
        right = right.right;
        //把当前节点的左子树(左子节点)设置成新的节点
        left = newNode;
        //剩余的没有指向的节点会被Java的垃圾回收机制给回收掉

    }

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


    public Node search(int value) {
        if (value == this.value) { 
            return this;
        } else if (value < this.value) {
            if (this.left == null) {
                return null;
            }
            return this.left.search(value);
        } else { 
            if (this.right == null) {
                return null;
            }
            return this.right.search(value);
        }

    }

    public Node searchParent(int value) {

        if ((this.left != null && this.left.value == value) || (this.right != null && this.right.value == value)) {
            return this;
        } else {

            if (value < this.value && this.left != null) {
                return this.left.searchParent(value);
            } else if (value >= this.value && this.right != null) {
                return this.right.searchParent(value);
            } else {
                return null;
            }
        }

    }

    @Override
    public String toString() {
        return "Node [value=" + value + "]";
    }

    public void add(Node node) {
        if (node == null) {
            return;
        }


        if (node.value < this.value) {

            if (this.left == null) {
                this.left = node;
            } else {

                this.left.add(node);
            }
        } else {
            if (this.right == null) {
                this.right = node;
            } else {

                this.right.add(node);
            }

        }

        //当添加稳一个节点后，右子树的高度大于左子树的高度  左旋转
        if (rightHeight() - leftHeight() > 1) {

            //如果右子树的左子树高度大于右子树的右子树高度 就先要对右子树进行右旋转 然后再对当前节点进行左旋转
            if (right != null && right.leftHeight() > right.rightHeight()) {
                right.rightRotate();
                leftRotate();
            } else {
                leftRotate();
            }
            return;
        }

        //当添加稳一个节点后，左子树的高度大于右子树的高度  右旋转
        if (leftHeight() - rightHeight() > 1) {
            //如果左子树的右子树高度大于左子树的左子树高度 就先要对左子树进行左旋转 然后再对当前节点进行右旋转
            if (left != null && left.rightHeight() > left.leftHeight()) {
                left.leftRotate();
                rightRotate();
            } else {
                rightRotate();
            }
        }
    }


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

}

8.9 多路查找树

B树

B树通过重新组织节点，降低了树的高度，文件系统及数据库系统设计者利用了磁盘预读原理，将一个节点的大小设为等于一个页(页得大小通常为4k)这样每个节点只需要一次I/O就可以完全载入，将树得度M设置1024，在600亿个元素最多只需要4次I/O操作就可以读取到想要得元素，B树(B+)广泛应用于文件存储系统以及数据库系统中，B树得阶就是节点最多子节点个数

image-20220725212038044

B+树

B+树是B树得变种，也是一种多路查找树。B+树得搜索与b树基本相同，区别是B+树只有达到叶子节点才命中，所有关键字都出现在叶子节点得链表中(也叫做稠密索引)，且链表中的关键字恰好是有序的，非叶子节点相当于是叶子节点的索引(稀疏索引)，叶子节点相当于是存储数据的数据层，更适合文件索引系统

image-20220725212139781

B *树

B *树是B+树的变体，在B+树的非根和非叶子节点再增加指向兄弟的指针，B *树定义了非叶子节点关键字至少为(2/3) * M,即块的最低使用率为2/3，而B+树的块的最低使用率为1/2

image-20220725212609444

9. 图

简单的介绍

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

image-20220725213128120

图的其他术语不再详细介绍，在这里，我们采用邻接矩阵的方式来表示图，其中1表示连接，0表示没有连接

image-20220725213242391

图的深度优先遍历(DFS)

主要是可以递归(栈)实现，从初识节点初识访问节点开始，接着访问它的第一个邻接节点，接着再以这个被访问的节点为初始节点，接着访问下一个邻接节点，如果这个邻接节点不存在(不相连)，就退回上一个节点，访问和它相连的第二个邻接节点

图的广度优先遍历(BFS)

主要通过队列实现，类似于一个分层搜索的过程，将第一个节点(root)入队，然后将和它相连所有节点入队，一个接着一个访问，并且把所有未访问的并且和该节点相连的节点都入队，进行访问，直到访问完毕。

代码实现

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
public class Graph {

	private ArrayList<String> vertexList; //存储顶点的集合
	private int[][] edges; // 存储邻接矩阵
	private int numOfEdges; // 表示边的数目
	//记录某个节点是否被访问过
	private boolean[] isVisited;
	
	public static void main(String[] args) {

		int n = 8;  // 节点的个数
		//String Vertexs[] = {"A", "B", "C", "D", "E"};
		String Vertexs[] = {"1", "2", "3", "4", "5", "6", "7", "8"};
		
		//创建图对象
		Graph graph = new Graph(n);
		// 循环添加顶点
		for(String vertex: Vertexs) {
			graph.insertVertex(vertex);
		}

		
		//添加边
		graph.insertEdge(0, 1, 1);
		graph.insertEdge(0, 2, 1);
		graph.insertEdge(1, 3, 1);
		graph.insertEdge(1, 4, 1);
		graph.insertEdge(3, 7, 1);
		graph.insertEdge(4, 7, 1);
		graph.insertEdge(2, 5, 1);
		graph.insertEdge(2, 6, 1);
		graph.insertEdge(5, 6, 1);

		
		

		graph.showGraph();
		
		//dfs
		System.out.println("dfs");
		graph.dfs(); // A->B->C->D->E [1->2->4->8->5->3->6->7]
		System.out.println();
		System.out.println("bfs");
		graph.bfs(); // A->B->C->D-E [1->2->3->4->5->6->7->8]
		
	}
	
	// 构造器
	public Graph(int n) {
		// 初始化vertexList
		edges = new int[n][n];
		vertexList = new ArrayList<String>(n);
		numOfEdges = 0;
		
	}
	
	//得到第一个邻接节点的下标
	/**
	 * 
	 * @param index 
	 * @return 如果存在返回对应的下标，否则返回-1
	 */
	public int getFirstNeighbor(int index) {
		for(int j = 0; j < vertexList.size(); j++) {
			if(edges[index][j] > 0) {
				return j;
			}
		}
		return -1;
	}


	//根据前一个邻接节点的下标来获取下一个节点的下标
	public int getNextNeighbor(int v1, int v2) {
		for(int j = v2 + 1; j < vertexList.size(); j++) {
			if(edges[v1][j] > 0) {
				return j;
			}
		}
		return -1;
	}
	

	private void dfs(boolean[] isVisited, int i) {
		//访问节点 输出
		System.out.print(getValueByIndex(i) + "->");
		//标记为已经访问
		isVisited[i] = true;
		//查找i的第一个节点
		int w = getFirstNeighbor(i);
		while(w != -1) {//说明有临接节点
			if(!isVisited[w]) {//判断是否访问过
				dfs(isVisited, w);
			}
			//
			w = getNextNeighbor(i, w);
		}
		
	}
	
	//对dfs重载 解决非连通图
	public void dfs() {
		isVisited = new boolean[vertexList.size()];
		//遍历所有的节点 进行回溯
		for(int i = 0; i < getNumOfVertex(); i++) {
			if(!isVisited[i]) {
				dfs(isVisited, i);
			}
		}
	}
	

	private void bfs(boolean[] isVisited, int i) {
		int u ; // 队列头节点对应的下标
		int w ; // 邻接节点w
		// 队列记录节点的访问顺序
		LinkedList queue = new LinkedList();
		// 输出这个节点的信息
		System.out.print(getValueByIndex(i) + "=>");
		// 标记为已访问
		isVisited[i] = true;
		// 把这个节点加入队列
		queue.addLast(i);
		
		while( !queue.isEmpty()) {
			// 取出队列头节点
			u = (Integer)queue.removeFirst();
			// 取出下一个下标
			w = getFirstNeighbor(u);
			while(w != -1) {//可以连
				//没有访问过
				if(!isVisited[w]) {
					System.out.print(getValueByIndex(w) + "=>");
					// 标记为已经访问
					isVisited[w] = true;
					//入队列
					queue.addLast(w);
				}
				//
				w = getNextNeighbor(u, w); //以这个为前驱，继续找下一个
			}
		}
		
	} 
	
	// 解决非连通图
	public void bfs() {
		isVisited = new boolean[vertexList.size()];
		for(int i = 0; i < getNumOfVertex(); i++) {
			if(!isVisited[i]) {
				bfs(isVisited, i);
			}
		}
	}
	
	// 返回节点的个数
	public int getNumOfVertex() {
		return vertexList.size();
	}
	// 显示图对应的矩阵
	public void showGraph() {
		for(int[] link : edges) {
			System.err.println(Arrays.toString(link));
		}
	}
	// 得到边的个数
	public int getNumOfEdges() {
		return numOfEdges;
	}
	// 返回节点的值
	public String getValueByIndex(int i) {
		return vertexList.get(i);
	}
	//返回v1 v2的权值
	public int getWeight(int v1, int v2) {
		return edges[v1][v2];
	}


	//插入节点
	public void insertVertex(String vertex) {
		vertexList.add(vertex);
	}

	// 添加边
	/**
	 * 
	 * @param v1 点的下标  "A"-"B" "A"->0 "B"->1
	 * @param v2 表示第二个顶点对应的下标
	 * @param weight 表示权重
	 */

	public void insertEdge(int v1, int v2, int weight) {
		edges[v1][v2] = weight;
		edges[v2][v1] = weight;
		numOfEdges++;
	}
}

10. 常用(大概吧)算法

这里写的算法以及示例都是相对比较浅的，就看一遍的话，是不可能掌握的，要想真正的掌握，成竹在胸，必须要多刷题！！！

二分查找非递归

相比较之前的递归，这里采用的是使用循环实现二分查找，原理都是一样的，关键是mid值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public static int binarySearch(int[] arr, int target) {
		
		int left = 0;
		int right = arr.length - 1;
		while(left <= right) { //说明继续查找
			int mid = (left + right) / 2;
			if(arr[mid] == target) {
				return mid;
			} else if ( arr[mid] > target) {
				right = mid - 1;//需要向左边查找
			} else {
				left = mid + 1; //需要向右边查找
			}
		}
		return -1;
	}

分治算法

分治算法的核心就是分和治两个部分，即先把问题分解成一个一个小的问题，然后通过解决一个一个的小的问题，合成大的解，最后解决整个问题，这里使用汉诺塔问题作为示例

汉诺塔问题，经典问题，简单的来说就是，有A，B，C三根柱子，其中A柱子上面有n个圆盘，每次移动一个圆盘并且不能把大圆盘放在小圆盘的上面，问一共需要多少步能把圆盘全部移动到C柱子上。

实现思路

首先我们一步一步的逆着思考，要想把n个圆盘移动到C上，把上面的n-1个圆盘看作一个整体，我们就需要把n-1个圆盘移动到B上面，然后把第n个圆盘移动到C柱上，再将n-1移动到C柱上面，完成最后一步移动，再往前想，要移动n-1个圆盘到B柱上，就需要把n-2个圆盘先移动到C柱上，然后把第n-1个圆盘移动到B柱上，然后把第n-2个圆盘移动到B柱上，完成移动，再往前推，我们可以发现他们的实现过程都是类似的，直到n最后是1的时候就可以移动了,完全可以使用递归实现

代码如下

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

	public static void main(String[] args) {
		hanoiTower(3, 'A', 'B', 'C');
	}
	
	//汉诺塔的移动的方法
	//使用分治算法
	
	public static void hanoiTower(int num, char a, char b, char c) {
		//如果只有一个盘
		if(num == 1) {
			System.out.println("第1个盘从 " + a + "->" + c);
		} else {
			//如果我们有 n >= 2 情况，我们总是可以看做是两个盘 1.最下边的一个盘 2. 上面的所有盘
			//1. 先把 最上面的所有盘 A->B， 移动过程会使用到 c
			hanoiTower(num - 1, a, c, b);
			//2. 把最下边的盘 A->C
			System.out.println("第" + num + "个盘从 " + a + "->" + c);
			//3. 把B塔的所有盘 从 B->C , 移动过程使用到 a塔  
			hanoiTower(num - 1, b, a, c);
			
		}
	}

}

动态规划

动态规划算法是我们的老朋友了，动态规划的算法的核心就是需要将以前的状态存储起来，然后再根据之前的状态推导出之后的状态，最后得到我们的最终答案，其中核心便是动态规划的动态转移方程。下面以背包问题举例说明

背包问题：

有一个背包，容量为4磅，现在有如下物品，要求使装入背包的总价值最大，并且重量不超出背包的最大容量，要求装入的物品不重复image-20220809181739427这里的背包问题是01背包问题(01背包，每个物品最多放一个，完全背包问题则是每种物品都有无限件可以使用)

实现思路

利用动态规划，每次遍历到第i个物品，根据w[i] 和G[i] 来确定是否需要放入该物品，

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

	//需要特别注意每个数组的含义
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] w = {1, 4, 3};//物品的重量
		int[] val = {1500, 3000, 2000}; //物品的价值 这里val[i] 就是前面讲的v[i]
		int m = 4; //背包的容量
		int n = val.length; //物品的个数
		
		
		
		//创建二维数组，
		//v[i][j] 表示在前i个物品中能够装入容量为j的背包中的最大价值
		int[][] v = new int[n+1][m+1];
		//为了记录放入商品的情况，我们定一个二维数组
		int[][] path = new int[n+1][m+1];
		
		//初始化第一行和第一列, 这里在本程序中，可以不去处理，因为默认就是0
		for(int i = 0; i < v.length; i++) {
			v[i][0] = 0; //将第一列设置为0
		}
		for(int i=0; i < v[0].length; i++) {
			v[0][i] = 0; //将第一行设置0
		}
		
		//动规的思想是最重要的
		//根据前面得到公式来动态规划处理
		for(int i = 1; i < v.length; i++) { //不处理第一行 i是从1开始的
			for(int j=1; j < v[0].length; j++) {//不处理第一列, j是从1开始的
				//当物品的所需的容量大于背包容量的时候
				if(w[i-1]> j) { // 因为我们程序i 是从1开始的，因此原来公式中的 w[i] 修改成 w[i-1]
					v[i][j]=v[i-1][j];//当前空间能装的最大价值就和不能装这个东西的同等容量的背包一致
				} else {
					//因为我们的i 从1开始的， 因此公式里面的w[i]调整成w[i-1]
					//v[i-1][j-w[i]] 就是没装当前这个东西前剩余空间的价值最大值  求Max相当于就是在决定要不要装这个东西
					//v[i][j]=Math.max(v[i-1][j], val[i]+v[i-1][j-w[i]]) => v[i][j] = Math.max(v[i-1][j], val[i-1]+v[i-1][j-w[i-1]]);
					//为了记录商品存放到背包的情况，我们不能直接的使用上面的公式，需要使用if-else来体现公式
					if(v[i - 1][j] < val[i - 1] + v[i - 1][j - w[i - 1]]) {
						v[i][j] = val[i - 1] + v[i - 1][j - w[i - 1]];
						//把当前的情况记录到path
						path[i][j] = 1;
					} else {
						v[i][j] = v[i - 1][j];
					}
					
				}
			}
		}
		
		//输出一下v 看看目前的情况
		for(int i =0; i < v.length;i++) {
			for(int j = 0; j < v[i].length;j++) {
				System.out.print(v[i][j] + " ");
			}
			System.out.println();
		}
		
		System.out.println("============================");
		
		//动脑筋
		int i = path.length - 1; //行的最大下标
		int j = path[0].length - 1;  //列的最大下标
		while(i > 0 && j > 0 ) { //从path的最后开始找
			if(path[i][j] == 1) {
				System.out.printf("第%d个商品放入到背包\n", i);
				j -= w[i - 1]; //把当前物品的重量减掉 就能求出所剩空间放入的价值最大的商品
			}
			i--;
		}
		
	}

}

KMP算法

字符串匹配问题,这个算法常用于在一个文本串S内查找一个模式串P的位置，字符串的匹配问题就是:有一个字符串str1 = “BBC ABCDAB ABCDABCDABDE”和一个子串 str2 = “ABCDABD” 现在要判断str1是否含有str2，如果存在，就返回第一次出现的位置，如果没有，就返回-1，KMP算法的核心就在于部分匹配值的应用

image-20220809213116344

这个部分匹配值指的就是以这个节点前面的字符串为一个全新的字符串，他的前缀和后缀的重复长度，而KMP需要回溯移动的位数指的就是已匹配的字符数-对应的部分匹配值

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
public class KMPAlgorithm {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		String str1 = "BBC ABCDAB ABCDABCDABDE";//需要匹配匹配的串
		String str2 = "ABCDABD";//子串
		//String str2 = "BBC";
		
		int[] next = kmpNext("ABCDABD"); //[0，0，0，0, 1, 2, 0]
		System.out.println("next=" + Arrays.toString(next));
		
		int index = kmpSearch(str1, str2, next);
		System.out.println("index=" + index); // 15了
		
		
	}
	
	//写出我们的kmp搜索算法
	/**
	 * 
	 * @param str1 源字符串
	 * @param str2 子串
	 * @param next 部分匹配表, 是子串对应的部分匹配表
	 * @return 如果是-1就是没有匹配到，否则返回第一个匹配的位置
	 */
	public static int kmpSearch(String str1, String str2, int[] next) {
		
		//遍历 
		for(int i = 0, j = 0; i < str1.length(); i++) {
			
			//需要处理 str1.charAt(i) ！= str2.charAt(j), 去调整j的大小
			//KMP算法核心点, 可以验证...
			while( j > 0 && str1.charAt(i) != str2.charAt(j)) {
				j = next[j-1]; 
			}
			
			if(str1.charAt(i) == str2.charAt(j)) {
				j++;
			}			
			if(j == str2.length()) {//找到了 // j = 3 i 
				return i - j + 1;
			}
		}
		return  -1;
	}

	//获取到一个字符串(子串) 的部分匹配值表
	public static  int[] kmpNext(String dest) {
		//创建一个next 数组保存部分匹配值
		int[] next = new int[dest.length()];
		next[0] = 0; //如果字符串是长度为1 部分匹配值就是0
		for(int i = 1, j = 0; i < dest.length(); i++) {
			//当dest.charAt(i) != dest.charAt(j) ，我们需要从next[j-1]获取新的j
			//直到我们发现 有  dest.charAt(i) == dest.charAt(j)成立才退出
			//这时kmp算法的核心点
			while(j > 0 && dest.charAt(i) != dest.charAt(j)) {
				j = next[j-1];
			}
			
			//当dest.charAt(i) == dest.charAt(j) 满足时，部分匹配值就是+1
			if(dest.charAt(i) == dest.charAt(j)) {
				j++;
			}
			next[i] = j;
		}
		return next;
	}
}

贪心算法

贪心算法即在当前情况下寻找最优的那个解，因此最终得到的结果不一定是最优解，下面以集合覆盖问题为例，假设存在下面需要付费的广播台，以及广播台信号可以覆盖的地区，如何选择最少的广播台，让所有的地区都可以接收到信号

image-20220809214343947

代码如下

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
public class GreedyAlgorithm {

	public static void main(String[] args) {
		//创建广播电台,放入到Map
		HashMap<String,HashSet<String>> broadcasts = new HashMap<String, HashSet<String>>();
		//将各个电台放入到broadcasts
		HashSet<String> hashSet1 = new HashSet<String>();
		hashSet1.add("北京");
		hashSet1.add("上海");
		hashSet1.add("天津");
		
		HashSet<String> hashSet2 = new HashSet<String>();
		hashSet2.add("广州");
		hashSet2.add("北京");
		hashSet2.add("深圳");
		
		HashSet<String> hashSet3 = new HashSet<String>();
		hashSet3.add("成都");
		hashSet3.add("上海");
		hashSet3.add("杭州");
		
		
		HashSet<String> hashSet4 = new HashSet<String>();
		hashSet4.add("上海");
		hashSet4.add("天津");
		
		HashSet<String> hashSet5 = new HashSet<String>();
		hashSet5.add("杭州");
		hashSet5.add("大连");
	
		//加入到map
		broadcasts.put("K1", hashSet1);
		broadcasts.put("K2", hashSet2);
		broadcasts.put("K3", hashSet3);
		broadcasts.put("K4", hashSet4);
		broadcasts.put("K5", hashSet5);
		
		//allAreas 存放所有的地区
		HashSet<String> allAreas = new HashSet<String>();
		allAreas.add("北京");
		allAreas.add("上海");
		allAreas.add("天津");
		allAreas.add("广州");
		allAreas.add("深圳");
		allAreas.add("成都");
		allAreas.add("杭州");
		allAreas.add("大连");
		
		//创建ArrayList, 存放选择的电台集合
		ArrayList<String> selects = new ArrayList<String>();
		
		//定义一个临时的集合， 在遍历的过程中，存放遍历过程中的电台覆盖的地区和当前还没有覆盖的地区的交集
		HashSet<String> tempSet = new HashSet<String>();
		
		//定义给maxKey ， 保存在一次遍历过程中，能够覆盖最大未覆盖的地区对应的电台的key
		//如果maxKey 不为null , 则会加入到 selects
		String maxKey = null;
		while(allAreas.size() != 0) { // 如果allAreas 不为0, 则表示还没有覆盖到所有的地区
			//每进行一次while,需要
			maxKey = null;
			
			//遍历 broadcasts, 取出对应key
			for(String key : broadcasts.keySet()) {
				//每进行一次for
				tempSet.clear();
				//当前这个key能够覆盖的地区
				HashSet<String> areas = broadcasts.get(key);
				tempSet.addAll(areas);
				//求出tempSet 和   allAreas 集合的交集, 交集会赋给 tempSet
				tempSet.retainAll(allAreas);
				//如果当前这个集合包含的未覆盖地区的数量，比maxKey指向的集合地区还多
				//就需要重置maxKey
				// tempSet.size() >broadcasts.get(maxKey).size()) 体现出贪心算法的特点,每次都选择最优的
				//就是选出最大的
				if(tempSet.size() > 0 && 
						(maxKey == null || tempSet.size() >broadcasts.get(maxKey).size())){
					maxKey = key;
				}
			}
			//maxKey != null, 就应该将maxKey 加入selects
			if(maxKey != null) {
				selects.add(maxKey);
				//将maxKey指向的广播电台覆盖的地区，从 allAreas 去掉
				allAreas.removeAll(broadcasts.get(maxKey));
			}
			
		}
		
		System.out.println("得到的选择结果是" + selects);//[K1,K2,K3,K5]
		
		
		
	}

}

最小生成树算法

先例举一个问题，有下图所示的7个村庄，现在需要修路把7个村庄联通，问如何修路保证各个村庄都能联通，并且总的修建公路的总里程最短image-20220809214857788

这个问题的实质就是怎么生成最小生成树的问题，而解决这个问题的算法主要 有两个，分别从两个不同的方向对怎么生成最小生成树做出了解释

普里姆算法

普里姆算法主要看的是点，依次寻找该点到另一个点的最短路径是哪条，不断重复，最终找到最小生成树

代码如下

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
public class PrimAlgorithm {

	public static void main(String[] args) {
		//测试看看图是否创建ok
		char[] data = new char[]{'A','B','C','D','E','F','G'};
		int verxs = data.length;
		//邻接矩阵的关系使用二维数组表示,10000这个大数，表示两个点不联通
		int [][]weight=new int[][]{
            {10000,5,7,10000,10000,10000,2},
            {5,10000,10000,9,10000,10000,3},
            {7,10000,10000,10000,8,10000,10000},
            {10000,9,10000,10000,10000,4,10000},
            {10000,10000,8,10000,10000,5,4},
            {10000,10000,10000,4,5,10000,6},
            {2,3,10000,10000,4,6,10000},};
            
        //创建MGraph对象
        MGraph graph = new MGraph(verxs);
        //创建一个MinTree对象
        MinTree minTree = new MinTree();
        minTree.createGraph(graph, verxs, data, weight);
        //输出
        minTree.showGraph(graph);
        //测试普利姆算法 生成最小生成树
        minTree.prim(graph, 1);
	}

}

//创建最小生成树->村庄的图
class MinTree {
	//创建图的邻接矩阵
	/**
	 * 
	 * @param graph 图对象
	 * @param verxs 图对应的顶点个数
	 * @param data 图的各个顶点的值
	 * @param weight 图的邻接矩阵
	 */
	public void createGraph(MGraph graph, int verxs, char data[], int[][] weight) {
		int i, j;
		//初始化
		for(i = 0; i < verxs; i++) {//顶点
			graph.data[i] = data[i];
			for(j = 0; j < verxs; j++) {
				graph.weight[i][j] = weight[i][j];//初始化邻接矩阵
			}
		}
	}
	
	//显示图的邻接矩阵
	public void showGraph(MGraph graph) {
		for(int[] link: graph.weight) {
			System.out.println(Arrays.toString(link));
		}
	}
	
	//编写prim算法，得到最小生成树
	/**
	 * 
	 * @param graph 图
	 * @param v 表示从图的第几个顶点开始生成'A'->0 'B'->1...
	 */
	public void prim(MGraph graph, int v) {
		//visited[] 标记结点(顶点)是否被访问过
		int visited[] = new int[graph.verxs];
		//visited[] 默认元素的值都是0, 表示没有访问过
		
		//把当前这个结点标记为已访问
		visited[v] = 1;
		//h1 和 h2 记录两个顶点的下标
		int h1 = -1;
		int h2 = -1;
		int minWeight = 10000; //将 minWeight 初始成一个大数，后面在遍历过程中，会被替换
		for(int k = 1; k < graph.verxs; k++) {//因为有 graph.verxs顶点，普利姆算法结束后，有 graph.verxs-1边
			
			//这个是确定每一次生成的子图 ，和哪个结点的距离最近
			for(int i = 0; i < graph.verxs; i++) {// i结点表示被访问过的结点
				for(int j = 0; j< graph.verxs;j++) {//j结点表示还没有访问过的结点
					if(visited[i] == 1 && visited[j] == 0 && graph.weight[i][j] < minWeight) {
						//替换minWeight(寻找已经访问过的结点和未访问过的结点间的权值最小的边)
						minWeight = graph.weight[i][j];
						h1 = i;
						h2 = j;
					}
				}
			}
			//找到一条边是最小
			System.out.println("边<" + graph.data[h1] + "," + graph.data[h2] + "> 权值:" + minWeight);
			//将当前这个结点标记为已经访问
			visited[h2] = 1;
			//minWeight 重新设置为最大值 10000
			minWeight = 10000;
		}
		
	}
}

class MGraph {
	int verxs; //表示图的节点个数
	char[] data;//存放结点数据 A B C D ....
	int[][] weight; //存放边权重，就是我们的邻接矩阵
	
	public MGraph(int verxs) {
		this.verxs = verxs;
		data = new char[verxs];
		weight = new int[verxs][verxs];
	}
}

克鲁斯卡尔算法

这个算法相比于上一个普里姆算法，主要突出的特点就是，克鲁斯卡尔算法是先将边排序，不断寻找最短的边，并一直判断这些边是否是联通的联通的就不行(判断的方法使用了并查集的思想)，直到这些点全部都联通

代码如下

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
public class KruskalCase {

	private int edgeNum; //边的个数
	private char[] vertexs; //顶点数组
	private int[][] matrix; //邻接矩阵
	//使用 INF 表示两个顶点不能连通
	private static final int INF = Integer.MAX_VALUE;
	
	public static void main(String[] args) {
		char[] vertexs = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
		//克鲁斯卡尔算法的邻接矩阵  
	      int matrix[][] = {
	      /*A*//*B*//*C*//*D*//*E*//*F*//*G*/
	/*A*/ {   0,  12, INF, INF, INF,  16,  14},
	/*B*/ {  12,   0,  10, INF, INF,   7, INF},
	/*C*/ { INF,  10,   0,   3,   5,   6, INF},
	/*D*/ { INF, INF,   3,   0,   4, INF, INF},
	/*E*/ { INF, INF,   5,   4,   0,   2,   8},
	/*F*/ {  16,   7,   6, INF,   2,   0,   9},
	/*G*/ {  14, INF, INF, INF,   8,   9,   0}}; 
	      //大家可以在去测试其它的邻接矩阵，结果都可以得到最小生成树.
	      
	      //创建KruskalCase 对象实例
	      KruskalCase kruskalCase = new KruskalCase(vertexs, matrix);
	      //输出构建的
	      kruskalCase.print();
	      kruskalCase.kruskal();
	      
	}
	
	//构造器
	public KruskalCase(char[] vertexs, int[][] matrix) {
		//初始化顶点数和边的个数
		int vlen = vertexs.length;
		
		//初始化顶点, 复制拷贝的方式
		this.vertexs = new char[vlen];
		for(int i = 0; i < vertexs.length; i++) {
			this.vertexs[i] = vertexs[i];
		}
		
		//初始化边, 使用的是复制拷贝的方式
		this.matrix = new int[vlen][vlen];
		for(int i = 0; i < vlen; i++) {
			for(int j= 0; j < vlen; j++) {
				this.matrix[i][j] = matrix[i][j];
			}
		}
		//统计边的条数
		for(int i =0; i < vlen; i++) {
			for(int j = i+1; j < vlen; j++) {
				if(this.matrix[i][j] != INF) {
					edgeNum++;
				}
			}
		}
		
	}
	public void kruskal() {
		int index = 0; //表示最后结果数组的索引
		int[] ends = new int[edgeNum]; //用于保存"已有最小生成树" 中的每个顶点在最小生成树中的终点
		//创建结果数组, 保存最后的最小生成树
		EData[] rets = new EData[edgeNum];
		
		//获取图中 所有的边的集合 ， 一共有12边
		EData[] edges = getEdges();
		System.out.println("图的边的集合=" + Arrays.toString(edges) + " 共"+ edges.length); //12
		
		//按照边的权值大小进行排序(从小到大)
		sortEdges(edges);
		
		//遍历edges 数组，将边添加到最小生成树中时，判断是准备加入的边否形成了回路，如果没有，就加入 rets, 否则不能加入
		for(int i=0; i < edgeNum; i++) {
			//获取到第i条边的第一个顶点(起点)
			int p1 = getPosition(edges[i].start); //p1=4
			//获取到第i条边的第2个顶点
			int p2 = getPosition(edges[i].end); //p2 = 5
			
			//获取p1这个顶点在已有最小生成树中的终点
			int m = getEnd(ends, p1); //m = 4
			//获取p2这个顶点在已有最小生成树中的终点
			int n = getEnd(ends, p2); // n = 5
			//是否构成回路 类似于并查集
			if(m != n) { //没有构成回路
				ends[m] = n; // 设置m 在"已有最小生成树"中的终点 <E,F> [0,0,0,0,5,0,0]
				rets[index++] = edges[i]; //有一条边加入到rets数组
			}
		}
		//<E,F> <C,D> <D,E> <B,F> <E,G> <A,B>。
		//统计并打印 "最小生成树", 输出  rets
		System.out.println("最小生成树为");
		for(int i = 0; i < index; i++) {
			System.out.println(rets[i]);
		}
		
		
	}
	
	//打印邻接矩阵
	public void print() {
		System.out.println("邻接矩阵为: \n");
		for(int i = 0; i < vertexs.length; i++) {
			for(int j=0; j < vertexs.length; j++) {
				System.out.printf("%12d", matrix[i][j]);
			}
			System.out.println();//换行
		}
	}

	/**
	 * 功能：对边进行排序处理, 冒泡排序
	 * @param edges 边的集合
	 */
	private void sortEdges(EData[] edges) {
		for(int i = 0; i < edges.length - 1; i++) {
			for(int j = 0; j < edges.length - 1 - i; j++) {
				if(edges[j].weight > edges[j+1].weight) {//交换
					EData tmp = edges[j];
					edges[j] = edges[j+1];
					edges[j+1] = tmp;
				}
			}
 		}
	}
	/**
	 * 
	 * @param ch 顶点的值，比如'A','B'
	 * @return 返回ch顶点对应的下标，如果找不到，返回-1
	 */
	private int getPosition(char ch) {
		for(int i = 0; i < vertexs.length; i++) {
			if(vertexs[i] == ch) {//找到
				return i;
			}
		}
		//找不到,返回-1
		return -1;
	}
	/**
	 * 功能: 获取图中边，放到EData[] 数组中，后面我们需要遍历该数组
	 * 是通过matrix 邻接矩阵来获取
	 * EData[] 形式 [['A','B', 12], ['B','F',7], .....]
	 * @return
	 */
	private EData[] getEdges() {
		int index = 0;
		EData[] edges = new EData[edgeNum];
		for(int i = 0; i < vertexs.length; i++) {
			for(int j=i+1; j <vertexs.length; j++) {
				if(matrix[i][j] != INF) {
					edges[index++] = new EData(vertexs[i], vertexs[j], matrix[i][j]);
				}
			}
		}
		return edges;
	}
	/**
	 * 功能: 获取下标为i的顶点的终点(), 用于后面判断两个顶点的终点是否相同
	 * @param ends ： 数组就是记录了各个顶点对应的终点是哪个,ends 数组是在遍历过程中，逐步形成
	 * @param i : 表示传入的顶点对应的下标
	 * @return 返回的就是 下标为i的这个顶点对应的终点的下标, 一会回头还有来理解
	 */
	//类似于并查集
	private int getEnd(int[] ends, int i) { // i = 4 [0,0,0,0,5,0,0]
		while(ends[i] != 0) {
			i = ends[i];
		}
		return i;
	}
 
}

//创建一个类EData ，它的对象实例就表示一条边
class EData {
	char start; //边的一个点
	char end; //边的另外一个点
	int weight; //边的权值
	//构造器
	public EData(char start, char end, int weight) {
		this.start = start;
		this.end = end;
		this.weight = weight;
	}
	//重写toString, 便于输出边信息
	@Override
	public String toString() {
		return "EData [<" + start + ", " + end + ">= " + weight + "]";
	}
	
	
}

最短路径算法

最短路径，故名思意，就是寻找从起点到终点的最短的路径，解决这个问题的，同样有两种算法，

迪杰斯特拉算法

这个算法的主要特点就是以起始点为中心向外层层扩展（就是广度优先搜索的思想），直到扩展到终点为止

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

	public static void main(String[] args) {
		char[] vertex = { 'A', 'B', 'C', 'D', 'E', 'F', 'G' };//顶点数组
		//邻接矩阵
		int[][] matrix = new int[vertex.length][vertex.length];
		final int N = 65535;// 表示不可以连接
		matrix[0]=new int[]{N,5,7,N,N,N,2};  
        matrix[1]=new int[]{5,N,N,9,N,N,3};  
        matrix[2]=new int[]{7,N,N,N,8,N,N};  
        matrix[3]=new int[]{N,9,N,N,N,4,N};  
        matrix[4]=new int[]{N,N,8,N,N,5,4};  
        matrix[5]=new int[]{N,N,N,4,5,N,6};  
        matrix[6]=new int[]{2,3,N,N,4,6,N};
        //创建 Graph对象
        Graph graph = new Graph(vertex, matrix);
        //测试, 看看图的邻接矩阵是否ok
        graph.showGraph();
        //测试迪杰斯特拉算法
        graph.dsj(2);//C
        graph.showDijkstra();
        
        
	}

}

class Graph {
	private char[] vertex; // 顶点数组
	private int[][] matrix; // 邻接矩阵
	private VisitedVertex vv; //已经访问的顶点的集合

	// 构造器
	public Graph(char[] vertex, int[][] matrix) {
		this.vertex = vertex;
		this.matrix = matrix;
	}
	
	//显示结果
	public void showDijkstra() {
		vv.show();
	}

	// 显示图
	public void showGraph() {
		for (int[] link : matrix) {
			System.out.println(Arrays.toString(link));
		}
	}
	
	//迪杰斯特拉算法实现
	/**
	 * 
	 * @param index 表示出发顶点对应的下标
	 */
	public void dsj(int index) {
		vv = new VisitedVertex(vertex.length, index);
		update(index);//更新index顶点到周围顶点的距离和前驱顶点
		for(int j = 1; j <vertex.length; j++) {
			index = vv.updateArr();// 选择并返回新的访问顶点
			update(index); // 更新index顶点到周围顶点的距离和前驱顶点
		} 
	}
	
	
	
	//更新index下标顶点到周围顶点的距离和周围顶点的前驱顶点,
	private void update(int index) {
		int len = 0;
		//根据遍历我们的邻接矩阵的  matrix[index]行
		for(int j = 0; j < matrix[index].length; j++) {
			// len 含义是 : 出发顶点到index顶点的距离 + 从index顶点到j顶点的距离的和 
			len = vv.getDis(index) + matrix[index][j];
			// 如果j顶点没有被访问过，并且 len 小于出发顶点到j顶点的距离，就需要更新
			if(!vv.in(j) && len < vv.getDis(j)) {
				vv.updatePre(j, index); //更新j顶点的前驱为index顶点
				vv.updateDis(j, len); //更新出发顶点到j顶点的距离
			}
		}
	}
}

// 已访问顶点集合
class VisitedVertex {
	// 记录各个顶点是否访问过 1表示访问过,0未访问,会动态更新
	public int[] already_arr;
	// 每个下标对应的值为前一个顶点下标, 会动态更新
	public int[] pre_visited;
	// 记录出发顶点到其他所有顶点的距离,比如G为出发顶点，就会记录G到其它顶点的距离，会动态更新，求的最短距离就会存放到dis
	public int[] dis;
	
	//构造器
	/**
	 * 
	 * @param length :表示顶点的个数 
	 * @param index: 出发顶点对应的下标, 比如G顶点，下标就是6
	 */
	public VisitedVertex(int length, int index) {
		this.already_arr = new int[length];
		this.pre_visited = new int[length];
		this.dis = new int[length];
		//初始化 dis数组
		Arrays.fill(dis, 65535);
		this.already_arr[index] = 1; //设置出发顶点被访问过
		this.dis[index] = 0;//设置出发顶点的访问距离为0
				
	}
	/**
	 * 功能: 判断index顶点是否被访问过
	 * @param index
	 * @return 如果访问过，就返回true, 否则访问false
	 */
	public boolean in(int index) {
		return already_arr[index] == 1;
	}
	
	/**
	 * 功能: 更新出发顶点到index顶点的距离
	 * @param index
	 * @param len
	 */
	public void updateDis(int index, int len) {
		dis[index] = len;
	}
	/**
	 * 功能: 更新pre这个顶点的前驱顶点为index顶点
	 * @param pre
	 * @param index
	 */
	public void updatePre(int pre, int index) {
		pre_visited[pre] = index;
	}
	/**
	 * 功能:返回出发顶点到index顶点的距离
	 * @param index
	 */
	public int getDis(int index) {
		return dis[index];
	}
	
	
	/**
	 * 继续选择并返回新的访问顶点， 比如这里的G 完后，就是 A点作为新的访问顶点(注意不是出发顶点)
	 * @return
	 */
	public int updateArr() {
		int min = 65535, index = 0;
		for(int i = 0; i < already_arr.length; i++) {
			if(already_arr[i] == 0 && dis[i] < min ) {
				min = dis[i];
				index = i;
			}
		}
		//更新 index 顶点被访问过
		already_arr[index] = 1;
		return index;
	}
	
	//显示最后的结果
	//即将三个数组的情况输出
	public void show() {
		
		System.out.println("==========================");
		//输出already_arr
		for(int i : already_arr) {
			System.out.print(i + " ");
		}
		System.out.println();
		//输出pre_visited
		for(int i : pre_visited) {
			System.out.print(i + " ");
		}
		System.out.println();
		//输出dis
		for(int i : dis) {
			System.out.print(i + " ");
		}
		System.out.println();
		//为了好看最后的最短距离，我们处理
		char[] vertex = { 'A', 'B', 'C', 'D', 'E', 'F', 'G' };
		int count = 0;
		for (int i : dis) {
			if (i != 65535) {
				System.out.print(vertex[count] + "("+i+") ");
			} else {
				System.out.println("N ");
			}
			count++;
		}
		System.out.println();
		
	}

}


弗洛伊德算法

弗洛伊德算法使用的是类似于上面的额动态规划的思想，不断刷新各个节点之间最短值

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

	public static void main(String[] args) {
		// 测试看看图是否创建成功
		char[] vertex = { 'A', 'B', 'C', 'D', 'E', 'F', 'G' };
		//创建邻接矩阵
		int[][] matrix = new int[vertex.length][vertex.length];
		final int N = 65535;
		matrix[0] = new int[] { 0, 5, 7, N, N, N, 2 };
		matrix[1] = new int[] { 5, 0, N, 9, N, N, 3 };
		matrix[2] = new int[] { 7, N, 0, N, 8, N, N };
		matrix[3] = new int[] { N, 9, N, 0, N, 4, N };
		matrix[4] = new int[] { N, N, 8, N, 0, 5, 4 };
		matrix[5] = new int[] { N, N, N, 4, 5, 0, 6 };
		matrix[6] = new int[] { 2, 3, N, N, 4, 6, 0 };
		
		//创建 Graph 对象
		Graph graph = new Graph(vertex.length, matrix, vertex);
		//调用弗洛伊德算法
		graph.floyd();
		graph.show();
	}

}

// 创建图
class Graph {
	private char[] vertex; // 存放顶点的数组
	private int[][] dis; // 保存，从各个顶点出发到其它顶点的距离，最后的结果，也是保留在该数组
	private int[][] pre;// 保存到达目标顶点的前驱顶点

	// 构造器
	/**
	 * 
	 * @param length
	 *            大小
	 * @param matrix
	 *            邻接矩阵
	 * @param vertex
	 *            顶点数组
	 */
	public Graph(int length, int[][] matrix, char[] vertex) {
		this.vertex = vertex;
		this.dis = matrix;
		this.pre = new int[length][length];
		// 对pre数组初始化, 注意存放的是前驱顶点的下标
		for (int i = 0; i < length; i++) {
			Arrays.fill(pre[i], i);
		}
	}

	// 显示pre数组和dis数组
	public void show() {

		//为了显示便于阅读，我们优化一下输出
		char[] vertex = { 'A', 'B', 'C', 'D', 'E', 'F', 'G' };
		for (int k = 0; k < dis.length; k++) {
			// 先将pre数组输出的一行
			for (int i = 0; i < dis.length; i++) {
				System.out.print(vertex[pre[k][i]] + " ");
			}
			System.out.println();
			// 输出dis数组的一行数据
			for (int i = 0; i < dis.length; i++) {
				System.out.print("("+vertex[k]+"到"+vertex[i]+"的最短路径是" + dis[k][i] + ") ");
			}
			System.out.println();
			System.out.println();

		}

	}
	
	//弗洛伊德算法, 比较容易理解，而且容易实现
	public void floyd() {
		int len = 0; //变量保存距离
		//对中间顶点遍历， k 就是中间顶点的下标 [A, B, C, D, E, F, G] 
		for(int k = 0; k < dis.length; k++) { // 
			//从i顶点开始出发 [A, B, C, D, E, F, G]
			for(int i = 0; i < dis.length; i++) {
				//到达j顶点 // [A, B, C, D, E, F, G]
				for(int j = 0; j < dis.length; j++) {
					len = dis[i][k] + dis[k][j];// => 求出从i 顶点出发，经过 k中间顶点，到达 j 顶点距离
					if(len < dis[i][j]) {//如果len小于 dis[i][j]
						dis[i][j] = len;//更新距离
						pre[i][j] = pre[k][j];//更新前驱顶点
					}
				}
			}
		}
	}
}

马踏棋盘算法

将马随机放在国际象棋的8*8的某个方格中，按照马走日字的规则进行移动，每个方格只进入一次，走遍棋盘上的全部64个方格image-20220809220907942

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
//这里采用的是回溯（深度优先的思想）实现
public class HorseChessboard {

	private static int X; // 棋盘的列数
	private static int Y; // 棋盘的行数
	//创建一个数组，标记棋盘的各个位置是否被访问过
	private static boolean visited[];
	//使用一个属性，标记是否棋盘的所有位置都被访问
	private static boolean finished; // 如果为true,表示成功
	
	public static void main(String[] args) {
		System.out.println("骑士周游算法，开始运行~~");
		//测试骑士周游算法是否正确
		X = 8;
		Y = 8;
		int row = 1; //马儿初始位置的行，从1开始编号
		int column = 1; //马儿初始位置的列，从1开始编号
		//创建棋盘
		int[][] chessboard = new int[X][Y];
		visited = new boolean[X * Y];//初始值都是false
		//测试一下耗时
		long start = System.currentTimeMillis();
		traversalChessboard(chessboard, row - 1, column - 1, 1);
		long end = System.currentTimeMillis();
		System.out.println("共耗时: " + (end - start) + " 毫秒");
		
		//输出棋盘的最后情况
		for(int[] rows : chessboard) {
			for(int step: rows) {
				System.out.print(step + "\t");
			}
			System.out.println();
		}
	}
	
	/**
	 * 完成骑士周游问题的算法
	 * @param chessboard 棋盘
	 * @param row 马儿当前的位置的行 从0开始 
	 * @param column 马儿当前的位置的列  从0开始
	 * @param step 是第几步 ,初始位置就是第1步 
	 */
	public static void traversalChessboard(int[][] chessboard, int row, int column, int step) {
		chessboard[row][column] = step;
		//row = 4 X = 8 column = 4 = 4 * 8 + 4 = 36
		visited[row * X + column] = true; //标记该位置已经访问
		//获取当前位置可以走的下一个位置的集合 
		ArrayList<Point> ps = next(new Point(column, row));
		//对ps进行排序,排序的规则就是对ps的所有的Point对象的下一步的位置的数目，进行非递减排序
		sort(ps);
		//遍历 ps
		while(!ps.isEmpty()) {
			Point p = ps.remove(0);//取出下一个可以走的位置
			//判断该点是否已经访问过
			if(!visited[p.y * X + p.x]) {//说明还没有访问过
				traversalChessboard(chessboard, p.y, p.x, step + 1);
			}
		}
		//判断马儿是否完成了任务，使用   step 和应该走的步数比较 ， 
		//如果没有达到数量，则表示没有完成任务，将整个棋盘置0
		//说明: step < X * Y  成立的情况有两种
		//1. 棋盘到目前位置,仍然没有走完
		//2. 棋盘处于一个回溯过程
		if(step < X * Y && !finished ) {
			chessboard[row][column] = 0;
			visited[row * X + column] = false;
		} else {
			finished = true;
		}
		
	}
	
	/**
	 * 功能： 根据当前位置(Point对象)，计算马儿还能走哪些位置(Point)，并放入到一个集合中(ArrayList), 最多有8个位置
	 * @param curPoint
	 * @return
	 */
	public static ArrayList<Point> next(Point curPoint) {//java居然还有point类
		//创建一个ArrayList
		ArrayList<Point> ps = new ArrayList<Point>();
		//创建一个Point
		Point p1 = new Point();
		//表示马儿可以走5这个位置
		if((p1.x = curPoint.x - 2) >= 0 && (p1.y = curPoint.y -1) >= 0) {
			ps.add(new Point(p1));
		}
		//判断马儿可以走6这个位置
		if((p1.x = curPoint.x - 1) >=0 && (p1.y=curPoint.y-2)>=0) {
			ps.add(new Point(p1));
		}
		//判断马儿可以走7这个位置
		if ((p1.x = curPoint.x + 1) < X && (p1.y = curPoint.y - 2) >= 0) {
			ps.add(new Point(p1));
		}
		//判断马儿可以走0这个位置
		if ((p1.x = curPoint.x + 2) < X && (p1.y = curPoint.y - 1) >= 0) {
			ps.add(new Point(p1));
		}
		//判断马儿可以走1这个位置
		if ((p1.x = curPoint.x + 2) < X && (p1.y = curPoint.y + 1) < Y) {
			ps.add(new Point(p1));
		}
		//判断马儿可以走2这个位置
		if ((p1.x = curPoint.x + 1) < X && (p1.y = curPoint.y + 2) < Y) {
			ps.add(new Point(p1));
		}
		//判断马儿可以走3这个位置
		if ((p1.x = curPoint.x - 1) >= 0 && (p1.y = curPoint.y + 2) < Y) {
			ps.add(new Point(p1));
		}
		//判断马儿可以走4这个位置
		if ((p1.x = curPoint.x - 2) >= 0 && (p1.y = curPoint.y + 1) < Y) {
			ps.add(new Point(p1));
		}
		return ps;
	}

	//根据当前这个一步的所有的下一步的选择位置，进行非递减排序, 减少回溯的次数
	public static void sort(ArrayList<Point> ps) {
		ps.sort(new Comparator<Point>() {

			@Override
			public int compare(Point o1, Point o2) {
				// TODO Auto-generated method stub
				//获取到o1的下一步的所有位置个数
				int count1 = next(o1).size();
				//获取到o2的下一步的所有位置个数
				int count2 = next(o2).size();
				if(count1 < count2) {
					return -1;
				} else if (count1 == count2) {
					return 0;
				} else {
					return 1;
				}
			}
			
		});
	}
}

11. 并查集

//todo

计算机基础
#data structure
Java数据结构与算法
http://example.com/2022/06/20/Java数据结构与算法/
作者
Mercury
发布于
2022年6月20日
许可协议