-
Notifications
You must be signed in to change notification settings - Fork 299
/
Code05_JosephusProblem.java
120 lines (107 loc) · 2.7 KB
/
Code05_JosephusProblem.java
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
package class16;
// 本题测试链接 : https://leetcode-cn.com/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof/
public class Code05_JosephusProblem {
// 提交直接通过
// 给定的编号是0~n-1的情况下,数到m就杀
// 返回谁会活?
public int lastRemaining1(int n, int m) {
return getLive(n, m) - 1;
}
// 课上题目的设定是,给定的编号是1~n的情况下,数到m就杀
// 返回谁会活?
public static int getLive(int n, int m) {
if (n == 1) {
return 1;
}
return (getLive(n - 1, m) + m - 1) % n + 1;
}
// 提交直接通过
// 给定的编号是0~n-1的情况下,数到m就杀
// 返回谁会活?
// 这个版本是迭代版
public int lastRemaining2(int n, int m) {
int ans = 1;
int r = 1;
while (r <= n) {
ans = (ans + m - 1) % (r++) + 1;
}
return ans - 1;
}
// 以下的code针对单链表,不要提交
public static class Node {
public int value;
public Node next;
public Node(int data) {
this.value = data;
}
}
public static Node josephusKill1(Node head, int m) {
if (head == null || head.next == head || m < 1) {
return head;
}
Node last = head;
while (last.next != head) {
last = last.next;
}
int count = 0;
while (head != last) {
if (++count == m) {
last.next = head.next;
count = 0;
} else {
last = last.next;
}
head = last.next;
}
return head;
}
public static Node josephusKill2(Node head, int m) {
if (head == null || head.next == head || m < 1) {
return head;
}
Node cur = head.next;
int size = 1; // tmp -> list size
while (cur != head) {
size++;
cur = cur.next;
}
int live = getLive(size, m); // tmp -> service node position
while (--live != 0) {
head = head.next;
}
head.next = head;
return head;
}
public static void printCircularList(Node head) {
if (head == null) {
return;
}
System.out.print("Circular List: " + head.value + " ");
Node cur = head.next;
while (cur != head) {
System.out.print(cur.value + " ");
cur = cur.next;
}
System.out.println("-> " + head.value);
}
public static void main(String[] args) {
Node head1 = new Node(1);
head1.next = new Node(2);
head1.next.next = new Node(3);
head1.next.next.next = new Node(4);
head1.next.next.next.next = new Node(5);
head1.next.next.next.next.next = head1;
printCircularList(head1);
head1 = josephusKill1(head1, 3);
printCircularList(head1);
Node head2 = new Node(1);
head2.next = new Node(2);
head2.next.next = new Node(3);
head2.next.next.next = new Node(4);
head2.next.next.next.next = new Node(5);
head2.next.next.next.next.next = head2;
printCircularList(head2);
head2 = josephusKill2(head2, 3);
printCircularList(head2);
}
}