现有n个人围坐一圈,顺时针给大家编号,第一个人编号为1,然后顺时针开始报数。第一轮依次报1,2,1,2...没报1的人出局。接着第二轮再从上一轮最后一个报数的人开始依次报1,2,3,1,2,3...没报1的人都出局。以此类推直到剩下以后一个人。现给定一个int n,要求返回最后一个人的编号。
测试样例:
5
返回:5
import java.util.*; public class Joseph { public static int getResult(int n) { // write code here if(n < 0)return -1; //设一个链表集合,存储所有人的编号 LinkedList<Integer> list = new LinkedList<>(); for(int k =1;k<= n;k++){ list.add(k); } int round =2;//确定报数的大小 int flag =0;//作为一个标记 while(list.size()>1){ //第一轮报数不用 将最后一个人作为第一个,所以用flag 作为判断条件 if(flag ==1){ //将当前链表的最后一个元素放入链表的最前面 list.addFirst(list.removeLast()); } //用一个变量记录当前的集合大小,避免循环过程中 判断条件发生变化 int len = list.size(); //由于 链表元素不断变化 ,下标也在变化,所以需要一个数记录删除元素数量 // 来重新确定元素下标 int count=0; for( int i =1 ;i<=len;i++){ if(i % round != 1 ){ list.remove(i-1-count); count++; } } round++; flag =1; } return list.poll(); } }
/** * 约瑟夫问题是一个著名的趣题。这里我们稍稍修改一下规则。有n个人站成一列。 * 并从头到尾给他们编号,第一个人编号为1。然后从头开始报数,第一轮依次报1,2,1,2...然后报到2的人出局。接着第二轮再从上一轮最后一个报数的人开始依次报1,2,3,1,2,3...报到2,3的人出局。以此类推直到剩下以后一个人。现在需要求的即是这个人的编号。 * <p> * 给定一个int n,代表游戏的人数。请返回最后一个人的编号 */ 时间复杂度O(nlog(n)) 空间复杂度n /** * 思路: * 数组连表的思想,将数组当链表使用,删除某一位时将其值置0 * 包含1个属性 * int[] idArr:参与游戏的n个人的编号的数组 * * 每轮报数不等于1的人被淘汰,被淘汰的人对应值置为0,同时计数器减一; * 下一轮直接判断idArr[i]!=0的编号 * 初始开始报数的索引位置是0,下一轮的第一个报数的人的索引为上一轮最后一个报1的人的索引 * 每报一次1,就将begin指向该人的位置索引,这样就可以保证,begin总是指向一轮当中最后一个报1的人的位置索引 * 直到计数器的值为1时结束递归,返回最后一名的索引值+1,即为最后一名的编号 * 例子:1 2 3 4 5 6 7 * 初始: * 1 2 3 4 5 6 7 * begin=0 * count=n * 第一轮结束: * 1 0 3 0 5 0 7 * begin=6 * count=4 * 第二轮结束: * 0 0 0 0 5 0 7 * begin=4 * count=2 * 第三轮结束: * 0 0 0 0 5 0 0 * begin=4 * count=1 * 返回begin+1 */ public int getResult(int n) { GameTable gameTable = new GameTable(n); int begin = 0, count = n, round = 2; int result = getResult(begin, gameTable, count, round, n); return result; } protected int getResult(int begin, GameTable gameTable, int count, int round, int n) { if (count == 1) { return begin + 1; } int k = 0, j = 0, i = begin; while (k < n) { if (gameTable.idArr[i] != 0) { // 马上判断是否被淘汰 if (++j != 1) { gameTable.remove(i); count--; } else { begin = i; } if (j % round == 0) { j = 0; } } i = (i+1) % n; k++; } return getResult(begin, gameTable, count, round + 1, n); } public static class GameTable { private int[] idArr; public GameTable(int n) { this.idArr = new int[n]; initIdArr(); } private void initIdArr() { for (int i = 0; i < idArr.length; i++) { idArr[i] = i + 1; } } /** * @param index 索引,被删除元素的索引 * @return 被删除元素的值 */ public int remove(int index) { int value = idArr[index]; idArr[index] = 0; return value; } }
public int getResult(int n) { // write code here if(n <1){ return -1; } LinkedList<Integer> list = new LinkedList<>(); //第一轮只放奇数 for(int i = 1; i<= n; i++){ if(i%2 != 0){ list.add(i); } } int round = 3; while(list.size() > 1){ int last = list.removeLast(); list.addFirst(last);//最后一个前移 int len = list.size(); //每次删除,list长度都会变 int k = 0;//记录删除的个数 for(int j = 1; j<= len; j++){ if(j % round !=1){ list.remove(j-1-k); k++; } } round ++; } return list.pop(); }
*/public class Joseph {
public int getResult(int n) { Stack<Integer> list = new Stack<Integer>(); LinkedList<Integer> tempList = new LinkedList<Integer>(); for(int i=n;i>=1;i--) { list.push(i); } int k = 1; while(true) { if(list.size()==1) { return list.pop(); } while(!list.isEmpty()) { tempList.push(list.pop()); for(int j=0;j<k;j++) { if(!list.isEmpty()) { list.pop(); } } } int jundge = 0; while(!tempList.isEmpty()) { if(jundge == 0) { jundge = tempList.pollFirst(); } else { list.push(tempList.pollFirst()); } } list.push(jundge); k++; } }
import java.util.*; public class Joseph { public int getResult(int n) { return ysf(n, 2); } public int ysf(int n, int m) { int tmp = n%m==0 ? n/m : n/m+1; if(tmp <= m+1) { return (tmp-1)*m+1; //终止条件 } int path = ysf(tmp, m+1); //m+1次时最后一人编号的位置 return (path-2)*m + 1; } }