约瑟夫环

第18 题：
题目：n 个数字（0,1,…,n-1）形成一个圆圈，从数字0 开始，
每次从这个圆圈中删除第m 个数字（第一个为当前数字本身，第二个为当前数字的下一个数
字）。
当一个数字删除后，从被删除数字的下一个继续删除第m 个数字。
求出在这个圆圈中剩下的最后一个数字

约瑟夫环问题，第一思路是拿双向链表解决，从链表的头结点开始计数，数到第M个节点时，将该节点删除并从该节点的下一节点开始继续上述逻辑，直到开始节点的prev和next指针指向它自己，说明该节点是最后一个节点，但这种解决方法时间复杂度高，也没什么技术含量。。。。

另一个思路是用数学的方法，估计大家也都学过相应的解决方法，但我的感觉是理解的还是不彻底，可能跟数学逃课太多有关，汗

为了方便理解，我们假设下标从1开始，

初始序列1为 1，2，3，4，5,...,n-1,n 则第一个被删除的假设为K，则K=m%n (取余的目的是防止m大于n)，K被删除后，剩下的n-1个值的序列2为

1,2,3,....k-1,k+1,...n-1,n

将1到k-1移至序列尾部转换为序列3： k+1,k+2,k+3,....,n-2,n-1,n,1,2,3,...,k-1

将序列每个元素减去K，转换为序列4： 1,2,3......,n-2-k, n-1-k, n-k,.......,n-1

　　=> 此处假设通过该序列我们能得到最终退出的元素是x，那么x与序列1最终退出的元素x'之间是不是相差K啊？明白了么同志们？

又因为已知k=m%n

可以得到x'=x+k=x+m%n=(x+m)%n 因为x+m%n有可能大于n 所以转换为(x+m%n)%n也就是(x+m)%n

最终得到x'=(x+m)%n

 1 package com.rui.microsoft;
 2 
 3 public class Test18_Joseph {
 4 
 5     public static void main(String[] args) {
 6         int[] circle = {1,2,3,4,5,6,7,8,9,10};
 7         int m = 3;
 8         int s = 0;
 9         
10         for(int i = 2; i <= circle.length; i++){
11             s = (s + m) % i;
12         }
13         
14         System.out.println(circle[s]);
15     }
16 }

另外双向链表的解法：

 1 package com.rui.microsoft;
 2 
 3 public class Test18_RemoveFromCircle {
 4 
 5     public static void main(String[] args) {
 6         Node node0 = new Node(0);
 7         Node node1 = new Node(1);
 8         Node node2 = new Node(2);
 9         Node node3 = new Node(3);
10         Node node4 = new Node(4);
11         
12         node0.next = node1;
13         node1.pre = node0;
14         node1.next = node2;
15         node2.pre = node1;
16         node2.next = node3;
17         node3.pre = node2;
18         node3.next = node4;
19         node4.pre = node3;
20         node4.next = node0;
21         node0.pre = node4;
22         
23         Test18_RemoveFromCircle.remove(node0, 3);
24     }
25     
26     public static void remove(Node head, int m){
27         if(null == head) return;
28         Node node = head;
29         int start = 1;
30         while(node != node.pre && node != node.next){
31             while(start < m){
32                 node = node.next;
33                 start++;
34             }
35             node = remove(node);
36             start = 1;
37         }
38         System.out.println(node.value);
39     }
40     
41     private static Node remove(Node node){
42         Node next = node.next;
43         node.pre.next = next;
44         next.pre = node.pre;
45         return next;
46     }
47     
48     static class Node{
49         int value;
50         Node pre;
51         Node next;
52         
53         Node(int v){
54             this.value = v;
55         }
56     }
57 }