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