约瑟夫问题1
题目描述
约瑟夫问题是一个非常著名的趣题，即由n个人坐成一圈，按顺时针由1开始给他们编号。然后由第一个人开始报数，数到m的人出局。现在需要求的是最后一个出局的人的编号。
给定两个int n和m，代表游戏的人数。请返回最后一个出局的人的编号。保证n和m小于等于1000。
测试样例：
5 3
返回：4
主要思路
参考链接：https://blog.nowcoder.net/n/81a858b422804183a1a51dbfd4084ebc
代码如下
//递归实现 class Joseph { public: int getResult(int n, int m) { if(n < 1 || m < 1){ return 0; } return lastInCycle(n, m) + 1; } int lastInCycle(int n, int m){ if(n == 1){ return 0; } return (lastInCycle(n - 1, m) + m) % n; } }; //迭代逆推实现 public int getResult(int n, int m) { // write code here /* * 存在递推公式： * f(n,m)表示n个人报数m的离开，最后留下来的人的初始号码 * f(n,m) = (f(n-1,m)+m)%n; */ if(n < 1 || m < 1){ return -1; } int last = 0; if(n == 1){ return last;//最后一轮出局的人肯定是最后轮的第0个，要找到其初始号码 } for(int i = 2; i <= n; i++){ last = (last + m) % i;//最后出来的人在倒数第i轮的号码是last } return last+1;//注意编号是1-n编号的，而算法是从0~n-1排序的 }
约瑟夫问题2
题目描述
约瑟夫问题是一个著名的趣题。这里我们稍稍修改一下规则。有n个人站成一列。并从头到尾给他们编号，第一个人编号为1。然后从头开始报数，第一轮依次报1，2，1，2…然后报到2的人出局。接着第二轮再从上一轮最后一个报数的人开始依次报1，2，3，1，2，3…报到2，3的人出局。以此类推直到剩下以后一个人。现在需要求的即是这个人的编号。
给定一个int n，代表游戏的人数。请返回最后一个人的编号
测试样例：
5
返回：5
主要思路一（数学推导实现）
比较难以想到
数学推导得出：参考链接
代码如下
//递归实现 class Joseph { public: int getResult(int n) { // write code here if(n < 1){ return 0; } int result = lastInCycle(n, 2); return result + 1; } int lastInCycle(int n, int m){ if(n <= m){ return 0; } int temp = n % m == 0 ? n / m : n / m + 1; return (lastInCycle(temp, m + 1) + temp - 1) % temp * m; } };
主要思路二（链表实现）
链表实现：参考链接
解题思路例子：
- 由于涉及到频繁的删除操作，故数据结构应该选择链表，这里选择LinkedList，其底层实现是循环双链表。
- 每一轮报数完毕之后，将链表尾部节点移动到链表首部，开始新一轮的报数。
- 链表中仅剩一个节点，程序结束。
- 举个例子：假设n = 24，第一个人编号为1。
（1）第一轮：依次报1，2，1，2…然后报到2的人出局，则第一轮过后未出局的编号为1、3、5、7、9、11、13、15、17、19、21、23；
（2）第二轮：从上一轮最后一个报数的人开始依次报1，2，3，1，2，3…报到2，3的人出局。我这里做的处理是，先将上一轮最后一个报数的编号移动到最前面，即23、1、3、5、7、9、11、13、15、17、19、21；然后开始第二轮报数，未出局的编号为23、5、11、17；
（3）第三轮：从上一轮最后一个报数的人开始依次报1，2，3，4，1，2，3，4…报到2，3，4的人出局。同样，我这里做的处理是，先将上一轮最后一个报数的编号移动到最前面，即17、23、5、11；然后开始第三轮报数，未出局的编号为17，此时链表中仅剩一个节点，故程序结束。
代码如下
/** * 核心数据结构：双链表 */ public int getResult(int n) { if (n < 1) return -1; LinkedList<Integer> list = new LinkedList<Integer>(); int round = 2, i, curr = 0; for (i = 1; i <= n; i++) { list.add(i); } while (list.size() > 1) { i = 0; while (list.size() > 1 && i < list.size()) { //当还有大于1个人存活的时候游戏继续 curr = (curr + 1) % round; //每一轮的round都会+1，从2开始递增 if (curr != 1) { //筛选数据 list.remove(i); } else { i++; } } round++; // 下一轮的最大报数 curr = 0; // 表示还未开始报数 if (list.size() > 1) {// 将最后报数的元素移动到链表首部，即确保每次报数从链表首部开始。 int last = list.removeLast(); list.addFirst(last); } } return list.pop();// 返回最后一个元素 }
