JZ62 孩子们的游戏(圆圈中最后剩下的数)

题目

每年六一儿童节  
  
  
  
  
  
，牛客都会准备一些小礼物和小游戏去看望孤儿院的孩子们  
  
  
  
  
  
。 其中 
  
  
  
  
  
 ，有个游戏是这样的：首先


 


 


 


 


 


 ，让 n 个小朋友们围成一个大圈 
 
 
 
 
 
，小朋友们的编号是0~n-1 
  
  
  
  
  
 。 然后  
   
   
   
   
   
 ，随机指定一个数m

 

 

 

 

 

 ，让编号为0的小朋友开始报数


 


 


 


 


 


 。每次喊到 m-1 的那个小朋友要出列唱首歌
 

 

 

 

 

 
， 然后可以在礼品箱中任意的挑选礼物            ，并且不再回到圈中
 

 
 

 
 

 
 

 
 

 
 

 ，从他的下一个小朋友开始











， 继续0... m-1报数....这样下去....直到剩下最后一个小朋友                  ，可以不用表演
 
 
 
 
 
 
 
 
 
 
 
 ，并且拿到牛客礼品

















，请你试着想下            ， 哪个小朋友会得到这份礼品呢？

方法1 暴力算法

思路

算法实现

用数组模拟循环列表
 
  
 
  
 
  
 
  
 
  
 
  ，从0开始喊到m个数后











，就将其值置为-1 
 
 
 
 
 
。直到数组剩下最后一个数（非-1）  
   
   
   
   
   
 。

代码

package mid.JZ62孩子们的游戏; import java.util.ArrayList; public class Solution { public int LastRemaining_Solution(int n, int m) { if (m == 0) return -1; int num = 0, k = 0; int[] child = new int[n]; for (int i = 0; k != n - 1; i = (++i) % n) {//i=(++i) % n这里是一个特殊操作  
  
  
  
  
  
，使遍历自动再数组内循环

 

 

 

 

 

 。 if (child[i] == 0) { num++; if (num == m) { num = 0; child[i] = 1; k++; }//此位置小孩退圈 } } for (int i = 0; i < child.length; i++) { if (child[i] == 0) { return i; } } return -1; } }

方法2 约瑟夫问题递推公式

思路

算法实现 利用约瑟夫问题的递推公式 f(n,m) = ( f(n-1,m) +m)%n ) 重新编号之前 m, m+1,m+2,....重新编号之后 0  
  
  
  
  
  
 ，1


 


 


 


 


 


 ，2 
 
 
 
 
 
，....

代码

package mid.JZ62孩子们的游戏; import java.util.ArrayList; public class Solution { public int LastRemaining_Solution(int n, int m) { if(n <= 0) return -1; return (LastRemaining_Solution(n-1,m)+m)%n; } }