算法基础扫盲
Damoncai 4/22/2022 算法
# 位运算
拿int类型举例：java中int类型由32未二进制位组成
# 查看二进制组成代码
/**
* 输出32为二进制数
* @param num
*/
private static void bitOperation(int num) {
for (int i = 31; i >= 0 ; i--) {
System.out.print((num & (1 << i)) == 0 ? "0" : "1");
}
System.out.println();
}
1
2
3
4
5
6
7
8
9
10
2
3
4
5
6
7
8
9
10
当bitOperation方法中传递3和-3时输出的结果分别为
00000000000000000000000000000011 // 3
11111111111111111111111111111101 // -3
1
2
3
2
3
可以发现：
- 32位中，最高位用来表示数字的正负，0正1复
- 负数以补码的方式进行存储(取反、加一)
# 左移、右移运算符、无符号右移
public class Code01_bit_operation {
/**
* 位运算
*/
public static void main(String[] args) {
System.out.println(1024 << 1); // 相当于乘 2
System.out.println();
bitOperation(3);
System.out.println("========");
bitOperation(-3);
System.out.println("========");
int num = 5;
bitOperation(num);
bitOperation(-num);
bitOperation(~num);
bitOperation( ~ num + 1);
System.out.println("========");
bitOperation(3);
bitOperation(3 >> 1);
bitOperation(3 >>> 1);
System.out.println("========");
bitOperation(-3);
bitOperation(-3 >> 1); // 右移运算符
bitOperation(-3 >>> 1); // 无符号右移
}
/**
* 输出32为二进制数
* @param num
*/
private static void bitOperation(int num) {
for (int i = 31; i >= 0 ; i--) {
System.out.print((num & (1 << i)) == 0 ? "0" : "1");
}
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
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
# 排序
# 选择排序
public class Code01_SelectionSort {
/**
* 选择排序
* 4 1 3
*
*
* @param args
*/
public static void main(String[] args) {
int[] arrs = generateRandomArray(10,100);
for (int i = 0 ; i < arrs.length -1 ; i++) {
int minIndex = i;
for(int j = i + 1 ; j < arrs.length ; j ++) {
if(arrs[minIndex] > arrs[j]) minIndex = j;
}
swap(arrs,i,minIndex);
}
System.out.println(Arrays.toString(arrs));
}
private static void swap(int[] arrs, int i, int j) {
int temp = arrs[i];
arrs[i] = arrs[j];
arrs[j] = temp;
}
// for test
public static int[] generateRandomArray(int maxSize, int maxValue) {
// Math.random() [0,1)
// Math.random() * N [0,N)
// (int)(Math.random() * N) [0, N-1]
int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
for (int i = 0; i < arr.length; i++) {
// [-? , +?]
arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
}
return arr;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
# 冒泡排序
public class Code02_BubbleSort {
/**
* 冒泡排序
* 0 ~ N-1
* 0 ~ N-2
* 0 ~ N-3
* @param args
*/
public static void main(String[] args) {
int[] arrs = {4,5,3,1,2};
for (int i = 0 ; i < arrs.length -1 ; i++) {
for(int j = 0 ; j < arrs.length - i - 1 ; j ++) {
if(arrs[j] > arrs[j + 1]) swap(arrs,j,j+1);
}
}
System.out.println(Arrays.toString(arrs));
}
private static void swap(int[] arrs, int i, int j) {
int temp = arrs[i];
arrs[i] = arrs[j];
arrs[j] = temp;
}
// for test
public static int[] generateRandomArray(int maxSize, int maxValue) {
// Math.random() [0,1)
// Math.random() * N [0,N)
// (int)(Math.random() * N) [0, N-1]
int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
for (int i = 0; i < arr.length; i++) {
// [-? , +?]
arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
}
return arr;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
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
# 插入排序
public class Code03_InsertionSort {
/**
* 插入排序
* 4,5,3,1,2
*
* @param args
*/
public static void main(String[] args) {
int[] arrs = {4,5,3,1,2};
for (int i = 1 ; i < arrs.length ; i++) {
int minIndex = i;
for(int j = 0 ; j < i ; j ++) {
if(arrs[j] > arrs[i]) swap(arrs,i,j);;
}
}
System.out.println(Arrays.toString(arrs));
}
private static void swap(int[] arrs, int i, int j) {
int temp = arrs[i];
arrs[i] = arrs[j];
arrs[j] = temp;
}
// for test
public static int[] generateRandomArray(int maxSize, int maxValue) {
// Math.random() [0,1)
// Math.random() * N [0,N)
// (int)(Math.random() * N) [0, N-1]
int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
for (int i = 0; i < arr.length; i++) {
// [-? , +?]
arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
}
return arr;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
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
# Math.random()
Math.random()生成的数据范围是 [0, 1)
Math.random()生成的数据是等概率的
public static void main(String[] args) { int times = 100000; int[] arr = new int[8]; for (int i = 0; i < times; i++) { int ans = f1(); arr[ans] ++; } printAvgAssignRes(arr); } /** * 1 - 5的随机 * @return */ public static int f1() { return (int) (Math.random() * 5) + 1; } /** * 打印平均分配测试结果 * @param arr */ public static void printAvgAssignRes(int[] arr) { for (int i = 0; i < arr.length; i++) { System.out.println(i + "出现次数：" + arr[i]); } }1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
# 从1-5随机 到 1-7随机
给出函数fn生成1-5随机数据并等概率，求提供一个函数fx使1-7随机并等概率
实现思路 1-5随机 - 0-1 随机 1-7随机
public class Code01_Avg_Random {
/**
* 从1-5随机 到 1-7随机
* 实现思路 1-5随机 - 0-1 随机 1-7随机
* @param args
*/
public static void main(String[] args) {
int times = 100000;
int[] arr = new int[8];
for (int i = 0; i < times; i++) {
int ans = f4();
arr[ans] ++;
}
printAvgAssignRes(arr);
}
/**
* 1 - 5的随机
* @return
*/
public static int f1() {
return (int) (Math.random() * 5) + 1;
}
/**
* 返回0或1随机
* @return
*/
public static int f2() {
int ans;
do {
ans = f1();
}while (ans == 3);
return ans < 3 ? 0 : 1;
}
public static int f3() {
int ans1 = f2();
int ans2 = f2();
int ans3 = f2();
return (ans1 << 2) + (ans2 << 1) + (ans3) << 0;
}
public static int f4() {
int num;
do{
num = f3();
}while (num == 0);
return num;
}
/**
* 打印平均分配测试结果
* @param arr
*/
public static void printAvgAssignRes(int[] arr) {
for (int i = 0; i < arr.length; i++) {
System.out.println(i + "出现次数：" + arr[i]);
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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
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
# 不等概率随机01到等概率
不等概率的随机：[0 ~ 1) 0~0.3 概率为百分之五十 0.3到1为百分之五十
public class Code02_No_Avg_Random {
/**
* 不等概率随机01到等概率
* 不等概率的随机：[0 ~ 1) 0~0.3 概率为百分之五十 0.3到1为百分之五十
*/
public static void main(String[] args) {
int times = 100000;
int[] arr = new int[2];
System.out.println("===========不等概率0，1随机===========");
for (int i = 0; i < times; i++) {
int ans = f1();
arr[ans] ++;
}
printAvgAssignRes(arr);
System.out.println("===========等概率0，1随机===========");
arr = new int[2];
for (int i = 0; i < times; i++) {
int ans = f2();
arr[ans] ++;
}
printAvgAssignRes(arr);
}
/**
* 1 - 5的随机
* @return
*/
public static int f1() {
return Math.random() < 0.3 ? 0 : 1;
}
/**
* 返回0或1随机
* @return
*/
public static int f2() {
int ans;
do {
ans = f1();
}while (ans == f1()); // 两次函数调用结果不等时(0,1)或(1,0)才返回
return ans;
}
/**
* 打印平均分配测试结果
* @param arr
*/
public static void printAvgAssignRes(int[] arr) {
double sum = (double)Arrays.stream(arr).sum();
for (int i = 0; i < arr.length; i++) {
System.out.println(i + "出现次数：" + arr[i] + ", 占比：" + ((double)arr[i] / sum));
}
}
}
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
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
# 二分、复杂度、动态数组、哈希表、有序表
# 有序数组中查找num
public class Code04_BSExist {
public static void main(String[] args) {
int[] arrs = {1,2,3,4,5,9,11};
int target = 5;
binarySearch(arrs,target);
}
/**
* 二分查找
* @param arrs
* @param target
*/
private static void binarySearch(int[] arrs, int target) {
int L = 0;
int R = arrs.length -1;
int mid = 0;
while (L <= R) {
mid = (L + R) / 2;
int midNum = arrs[mid];
if(midNum > target) {
R = mid - 1;
}else if (midNum < target){
L = mid + 1;
}else{
System.out.println("Exist~~ " + mid);
return;
}
}
}
}
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
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
# 有序数组中找到=num最左的位置
public class Code05_BSNearLeft {
// 在arr上，找满足>=value的最左位置
public static int nearestIndex(int[] arr, int value) {
int L = 0;
int R = arr.length - 1;
int index = -1; // 记录最左的对号
while (L <= R) { // 至少一个数的时候
int mid = L + ((R - L) >> 1);
if (arr[mid] >= value) {
index = mid;
R = mid - 1;
} else {
L = mid + 1;
}
}
return index;
}
// for test
public static int test(int[] arr, int value) {
for (int i = 0; i < arr.length; i++) {
if (arr[i] >= value) {
return i;
}
}
return -1;
}
// for test
public static int[] generateRandomArray(int maxSize, int maxValue) {
int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
for (int i = 0; i < arr.length; i++) {
arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
}
return arr;
}
// for test
public static void printArray(int[] arr) {
if (arr == null) {
return;
}
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
public static void main(String[] args) {
int testTime = 500000;
int maxSize = 10;
int maxValue = 100;
boolean succeed = true;
for (int i = 0; i < testTime; i++) {
int[] arr = generateRandomArray(maxSize, maxValue);
Arrays.sort(arr);
int value = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
if (test(arr, value) != nearestIndex(arr, value)) {
printArray(arr);
System.out.println(value);
System.out.println(test(arr, value));
System.out.println(nearestIndex(arr, value));
succeed = false;
break;
}
}
System.out.println(succeed ? "Nice!" : "Fucking fucked!");
}
}
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
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
# 局部最小值问题（任意一个）
- 无序
- 任意两个相邻的数不相等
例子：
0位置小于1位置数 -> 0位置为局部最小
N-1小于位置N-2位置 -> N-2为局部最小
N小于N-1和N-2位置的数 -> N为局部最小
public class Code06_BSAwesome {
public static int getLessIndex(int[] arr) {
if (arr == null || arr.length == 0) {
return -1; // no exist
}
if (arr.length == 1 || arr[0] < arr[1]) {
return 0;
}
if (arr[arr.length - 1] < arr[arr.length - 2]) {
return arr.length - 1;
}
int left = 1;
int right = arr.length - 2;
int mid = 0;
while (left < right) {
mid = (left + right) / 2;
if (arr[mid] > arr[mid - 1]) {
right = mid - 1;
} else if (arr[mid] > arr[mid + 1]) {
left = mid + 1;
} else {
return mid;
}
}
return left;
}
}
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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
# 等差数列求和
# 单链表及其简单题目
# 单链表反转
/**
* 单链表反转
*/
public class Code01_Singly_List_Reverse {
public static void main(String[] args) {
// 创建单链表
Node node = createSinglyListNode();
// 打印输出
print(node);
// 反转单链表
node = reverse(node);
// 打印输出
print(node);
}
/**
* 反转单链表
* 1 -> 2 -> 3 -> null
* null <- 1 <- 2 <- 3
* @param head
*/
private static Node reverse(Node head) {
Node per = null;
Node next = null;
while (head != null ) {
next = head.next;
head.next = per;
per = head;
head = next;
}
return per;
}
/**
* 创建单链表
* @return
*/
private static Node createSinglyListNode() {
Node n1 = new Node(1);
n1.next = new Node(2);
n1.next.next = new Node(3);
return n1;
}
/**
* 打印链表
* @param node
*/
private static void print(Node node) {
Node cur = node;
while (cur != null) {
System.out.print(cur.value + " ");
cur = cur.next;
}
System.out.println();
}
public static class Node<V> {
public Integer value;
public Node<V> next;
public Node(Integer value) {
this.value = value;
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
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
# 双链表反转
/**
* 双链表反转
*/
public class Code02_Double_List_Reverse {
public static void main(String[] args) {
// 创建双链表
Node node = createDoubleListNode();
// 打印输出
print(node);
// 反转单链表
node = reverse(node);
// 打印输出
print(node);
}
/**
* 反转双链表
* 1 -> 2 -> 3 -> null
* null <- 1 <- 2 <- 3
* @param head
*/
private static Node reverse(Node head) {
Node pre = null;
Node next = null;
while (head != null ) {
next = head.next;
head.next = pre;
head.last = next;
pre = head;
head = next;
}
return pre;
}
/**
* 创建单链表
* @return
*/
private static Node createDoubleListNode() {
// 1 2 3
Node n1 = new Node(1);
n1.next = new Node(2);
n1.next.next = new Node(3);
// 3 2 1
n1.next.next.last = n1.next;
n1.next.last = n1;
return n1;
}
/**
* 打印链表
* @param node
*/
private static void print(Node node) {
Node cur = node;
Node last = null;
while (cur != null) {
System.out.print(cur.value + " ");
last = cur;
cur = cur.next;
}
System.out.println();
cur = last;
while (cur != null) {
System.out.print(cur.value + " ");
cur = cur.last;
}
System.out.println();
}
public static class Node<V> {
public Integer value;
public Node<V> next;
public Node<V> last;
public Node(Integer value) {
this.value = value;
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
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
# 单链表实现队列
/**
* 单列 实现队列
*/
public class Code03_Singly_List_To_Queue {
public static void main(String[] args) {
}
public static class Queue<V> {
Node<V> head = null;
Node<V> tail = null;
Integer size = 0;
/**
* 添加元素
* @param v
*/
public void offer(V v) {
Node<V> cur = new Node(v);
if(head == null) {
head = cur;
tail = cur;
}else {
tail.next = cur;
tail = cur;
}
size ++;
}
/**
* 获取但不删除元素
* @return
*/
public V peek() {
V ans = null;
if(head != null) {
ans = head.value;
}
return ans;
}
/**
* 获取并删除元素
* @return
*/
public V poll() {
V ans = null;
if(head != null) {
ans = head.value;
head = head.next;
size --;
}
if(head == null) {
tail = null;
}
return ans;
}
}
public static class Node<V> {
public V value;
public Node<V> next;
public Node(V value) {
this.value = value;
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
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 Code04_Singly_List_To_Stack {
public static void main(String[] args) {
}
public static class Queue<V> {
Node<V> head = null;
Integer size = 0;
/**
* 添加元素
* @return
*/
public void push(V v) {
Node cur = new Node(v);
if(head == null) {
head = cur;
}else {
cur.next = head;
head = cur;
}
size ++;
}
/**
* 获取并删除元素
* @return
*/
public V pop() {
V ans = null;
if(head != null) {
ans = head.value;
head = head.next;
size --;
}
return ans;
}
}
public static class Node<V> {
public V value;
public Node<V> next;
public Node(V value) {
this.value = value;
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
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
# 用双链表实现双端队列
/**
* 双向链表实现双端队列
*/
public class Code05_Double_List_To_Queue {
public static void main(String[] args) {
}
public static class Queue<V> {
Node<V> head = null;
Node<V> tail = null;
Integer size = 0;
/**
* 头部添加
* @param v
*/
public void headPush(V v) {
Node<V> cur = new Node<V>(v);
if(head == null) {
head = cur;
tail = cur;
}else {
head.last = cur;
head = cur;
}
size ++;
}
/**
* 尾部添加
* @param v
*/
public void tailPush(V v) {
Node<V> cur = new Node<V>(v);
if(head == null) {
head = cur;
tail = cur;
}else {
tail.next = cur;
tail = cur;
}
size ++;
}
/**
* 头部取出
* @return
*/
public V headPop() {
V ans = null;
if(head == null) return ans;
ans = head.value;
size -- ;
if(head == tail) {
head = null;
tail = null;
}else {
head = head.next;
head.last = null;
}
return ans;
}
/**
* 尾部取出
* @return
*/
public V tailPop() {
V ans = null;
if(tail == null) return ans;
ans = tail.value;
size -- ;
if(head == tail) {
head = null;
tail = null;
}else {
tail = head.last;
tail.next = null;
}
return ans;
}
}
public static class Node<V> {
public V value;
public Node<V> next;
public Node<V> last;
public Node(V value) {
this.value = value;
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
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
# K个节点的组内逆序调整
/**
* K个节点组内逆序调整
* 1 2 3 4 5 6 7 8 k=3
* 3 2 1 6 5 4 7 8 不够k 就不调整
*/
public class Code06_K_Node_Reverse {
public static void main(String[] args) {
// 创建单链表
Node node = createSinglyListNode();
// 定于 K系数
int k = 3;
// 打印输出
print(node);
// 反转单链表
node = reverseKgroup(node,k);
// 打印输出
print(node);
}
/**
* 反转单链表
* 1 -> 2 -> 3 -> null
* null <- 1 <- 2 <- 3
* @param head
*/
private static Node reverseKgroup(Node head, int k) {
Node start = head;
Node end = getEnd(head,k);
if(end == null) return head;
head = end;
reverse(start,end);
Node lastEnd = start;
while (lastEnd.next != null) {
start = lastEnd.next;
end = getEnd(start,k);
if(end == null) break;
reverse(start,end);
lastEnd.next = end;
lastEnd = start;
}
return head;
}
/**
* 反转
* @param start
* @param end
*/
private static void reverse(Node start, Node end) {
end = end.next;
Node pre = null;
Node next = null;
Node cur = start;
while (cur != end) {
next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
start.next = end;
}
/**
* 获取借宿节点
* @param head
* @param k
* @return
*/
private static Node getEnd(Node head, int k) {
Node end = head;
while (end != null && --k != 0) {
end = end.next;
}
return end;
}
/**
* 创建单链表
* @return
*/
private static Node createSinglyListNode() {
Node n1 = new Node(1);
n1.next = new Node(2);
n1.next.next = new Node(3);
n1.next.next.next = new Node(4);
n1.next.next.next.next = new Node(5);
n1.next.next.next.next.next = new Node(6);
n1.next.next.next.next.next.next = new Node(7);
n1.next.next.next.next.next.next.next = new Node(8);
return n1;
}
/**
* 打印链表
* @param node
*/
private static void print(Node node) {
Node cur = node;
while (cur != null) {
System.out.print(cur.value + " ");
cur = cur.next;
}
System.out.println();
}
public static class Node<V> {
public V value;
public Node<V> next;
public Node(V value) {
this.value = value;
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
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
# 两列表相加
/**
* 两个单链表相加
*/
public class Code07_Two_Singly_List_Add {
public static void main(String[] args) {
// 创建单链表
Node node1 = createSinglyListNode();
Node node2 = createSinglyListNode2();
// 打印输出
print(node1);
print(node2);
Node res = add(node1,node2);
print(res);
}
/**
* 添加
* @param node1
* @param node2
* @return
*/
private static Node add(Node node1, Node node2) {
int len1 = getNodeLen(node1);
int len2 = getNodeLen(node2);
Node nodeL = null;
Node nodeS = null;
if(len1 > len2) {
nodeL = node1;
nodeS = node2;
}else {
nodeL = node2;
nodeS = node1;
}
doAdd(nodeL,nodeS);
return nodeL;
}
/**
* 添加
* @param nodeL
* @param nodeS
*/
private static void doAdd(Node nodeL, Node nodeS) {
Node pre = nodeL; // 防止只有一个元素
int tmp = 0;
while (nodeL != null) {
int sum = nodeL.value + (nodeS == null ? 0 : nodeS.value) + tmp;
tmp = sum / 10;
nodeL.value = sum % 10;
pre = nodeL;
nodeL = nodeL.next;
if(nodeS != null) nodeS = nodeS.next;
}
if(tmp != 0) {
pre.next = new Node(tmp);
}
}
/**
* 获取node长度
* @param node
* @return
*/
private static int getNodeLen(Node node) {
int len = 0;
if(node != null) {
while (node != null) {
node = node.next;
len ++;
}
}
return len;
}
/**
* 创建单链表
* @return
*/
private static Node createSinglyListNode() {
Node n1 = new Node(4);
n1.next = new Node(3);
n1.next.next = new Node(6);
return n1;
}
/**
* 创建单链表
* @return
*/
private static Node createSinglyListNode2() {
Node n1 = new Node(2);
n1.next = new Node(5);
n1.next.next = new Node(3);
return n1;
}
/**
* 打印链表
* @param node
*/
private static void print(Node node) {
Node cur = node;
while (cur != null) {
System.out.print(cur.value + " ");
cur = cur.next;
}
System.out.println();
}
public static class Node<V> {
public Integer value;
public Node<V> next;
public Node(Integer value) {
this.value = value;
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
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
# 两个有序链表合并
/**
* 两个有序列表合并
*/
public class Code08_Two_Orderly_Singly_List_To_One_Orderly_Singly_List {
public static void main(String[] args) {
// 创建单链表
Node node1 = createSinglyListNode();
Node node2 = createSinglyListNode2();
// 打印输出
print(node1);
print(node2);
// 整合
Node head = combine(node1,node2);
print(head);
}
/**
* 整合
* @param node1
* @param node2
* @return
*/
private static Node combine(Node node1, Node node2) {
if(node1 == null) return node2;
if(node2 == null) return node1;
Node head = node1.value <= node2.value ? node1 : node2;
Node cur1 = head.next;
Node cur2 = head == node1 ? node2 : node1;
Node pre = head;
while (cur1 != null && cur2 != null) {
if(cur1.value <= cur2.value) {
pre.next = cur1;
cur1 = cur1.next;
}else {
pre.next = cur2;
cur2 = cur2.next;
}
pre = pre.next;
}
pre.next = cur1 == null? cur1 : cur2;
return head;
}
/**
* 创建单链表
* @return
*/
private static Node createSinglyListNode() {
Node n1 = new Node(1);
n1.next = new Node(3);
n1.next.next = new Node(3);
n1.next.next.next = new Node(5);
n1.next.next.next.next = new Node(7);
return n1;
}
/**
* 创建单链表
* @return
*/
private static Node createSinglyListNode2() {
Node n1 = new Node(2);
n1.next = new Node(2);
n1.next.next = new Node(3);
n1.next.next.next = new Node(3);
n1.next.next.next.next = new Node(7);
return n1;
}
/**
* 打印链表
* @param node
*/
private static void print(Node node) {
Node cur = node;
while (cur != null) {
System.out.print(cur.value + " ");
cur = cur.next;
}
System.out.println();
}
public static class Node<V> {
public Integer value;
public Node<V> next;
public Node(Integer value) {
this.value = value;
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
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
# 合并K个升序链表
public class LeetCode_23_mergeKLists {
public static void main(String[] args) {
ListNode node1 = new ListNode(3);
ListNode node2 = new ListNode(5);
ListNode node3 = new ListNode(7);
node1.next = node2;
node1.next.next = node3;
ListNode node4 = new ListNode(4);
ListNode node5 = new ListNode(8);
ListNode node6 = new ListNode(8);
node4.next = node5;
node4.next.next = node6;
ListNode[] arr = new ListNode[0];
ListNode node = mergeKLists(arr);
System.out.println(node);
}
public static ListNode mergeKLists(ListNode[] lists) {
PriorityQueue<ListNode> queue = new PriorityQueue<ListNode>(new Comparator<ListNode>() {
@Override
public int compare(ListNode o1, ListNode o2) {
return o1.val - o2.val;
}
});
if(lists == null || lists.length == 0) return null;
for (ListNode node : lists) {
if(node != null)
queue.add(node);
}
ListNode head = queue.poll();
ListNode pre = head;
if(head.next != null) {
queue.add(head.next);
}
while (queue.size() > 0) {
ListNode node = queue.poll();
pre.next = node;
pre = node;
if(node.next != null) queue.add(node.next);
}
return head;
}
}
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
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