题目描述：
每年六一儿童节,牛客都会准备一些小礼物去看望孤儿院的小朋友,今年亦是如此。HF作为牛客的资深元老,自然也准备了一些小游戏。其中,有个游戏是这样的:首先,让小朋友们围成一个大圈。然后,他随机指定一个数m,让编号为0的小朋友开始报数。每次喊到m-1的那个小朋友要出列唱首歌,然后可以在礼品箱中任意的挑选礼物,并且不再回到圈中,从他的下一个小朋友开始,继续0…m-1报数….这样下去….直到剩下最后一个小朋友,可以不用表演,并且拿到牛客名贵的“名侦探柯南”典藏版(名额有限哦!!^_^)。请你试着想下,哪个小朋友会得到这份礼品呢？(注：小朋友的编号是从0到n-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/*public class Node_List {
int val;
Node_List next = null;
Node_List(int val){
this.val = val;
}
}*/
public static int LastRemaining_Solution(int n, int m) {
Node_List cur = new Node_List(0);
Node_List head = cur;
for (int i = 1; i < n; i++) {
Node_List node= new Node_List(i);
cur.next = node;
cur = node;
}
cur.next = head;
Node_List p = cur;
Node_List q = head;
while (q.next.val!=q.val) {
for (int i = 0; i < m-1; i++) {
p = p.next;
q = q.next;
}
p.next = q.next;
q = q.next;
}
return q.val;
}
方法2：
链表选用LinkedList实现，较方法1可以提高一定效率。
public static int LastRemaining_Solution(int n, int m) {
LinkedList<Integer> list = new LinkedList<Integer>();
for (int i = 0; i < n; i++)
list.add(i);
int p = 0;
while (list.size()>1) {
p = (p+m-1)%list.size();//注意这里使得可以从尾部跳回到头部
list.remove(p);
}
return list.size()==1?list.get(0):-1;
}
方法3：
当数据量比较大时，以上两种方法时间和空间都比较大，因此用归纳法找到规律然后利用递归。
0，1，2，3，……，m-2，m-1，m，……，n-1 (总共n个数，删除第m-1个数)
下次删的时候从下面第一行这个序列开始往后数，我们把这个序列用第二行的序列进行重新标号，根据第二行的标号来找对应第一行的标号，从第二行看很容易看出要删除的是m-1，那么第二行的m-1对应第一行的哪个数呢？
| m | m+1 | m+2 | … | … | n-1 | 0 | 1 | 2 | … | m-2 | |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 1 | 2 | … | … | n-1-m | n-m | n-m+1 | n-m+2 | … | n-1 |
也就是第二行的任意一个数p对应第一行哪个数？
如果p <= n-m，第二行的m-1对应第一行的 p+m；
如果p> n-m，第二行的m-1对应第一行的 (p+m)%n；
综上，合并以上两种情况，若第二行的数是p，则对应的第一行数是(p+m)%n。
public static int LastRemaining_Solution(int n, int m) {
if(n == 0)
return -1;
else if(n == 1)
return 0;
else
return (LastRemaining_Solution(n-1,m)+m)%n;
}
