【题目描述】每年六一儿童节,牛客都会准备一些小礼物去看望孤儿院的小朋友,今年亦是如此。HF作为牛客的资深元老,自然也准备了一些小游戏。其中,有个游戏是这样的:首先,让小朋友们围成一个大圈。然后,他随机指定一个数m,让编号为0的小朋友开始报数。每次喊到m-1的那个小朋友要出列唱首歌,然后可以在礼品箱中任意的挑选礼物,并且不再回到圈中,从他的下一个小朋友开始,继续0…m-1报数….这样下去….直到剩下最后一个小朋友,可以不用表演,并且拿到牛客名贵的“名侦探柯南”典藏版(名额有限哦!!^_^)。请你试着想下,哪个小朋友会得到这份礼品呢？(注：小朋友的编号是从0到n-1)
【解题思路1】 //1. 用一个数组标志，记录该位置的小朋友是否不再回到圈中。 //2. 每挑出一位小朋友，就将count–，直到count==0。此时的小朋友就是最后一位。
public class Solution { public int LastRemaining_Solution(int n, int m) { if(n<1||m<1) return -1; int[] array = new int[n]; int i = -1,step = 0, count = n; while(count>0){ i++; if(array[i%n] == -1) continue; step++; if(step==m) { array[i%n]=-1; step = 0; count--; } } return i%n; } }【解题思路2】数学公式递推法–约瑟夫环 //1. 把n个人的编号记为0~n-1，然后对删除的过程进行分析。 //2. 第一个删除的数字是(m-1)%n，记作k，则剩余的编号为(0,1,…,k-1,k+1,…,n-1)。下次开始删除时，新的环为(k+1,…,n-1,0,1,…k-1)。 //3. 用f(n,m)表示从(0~n-1)开始删除的情况下，最后剩下的数。 用q(n-1,m)表示从(k+1,…,n-1,0,1,…k-1)开始删除的情况下，最后剩下的数。因为f(n,m)是整个过程的第一步，q(n-1, m)是第二步，整个过程是一致的，则f(n,m)=q(n-1,m)。 //4. 下面把(k+1,…,n-1,0,1,…k-1)转换为(0~n-2)的形式，对应关系如下：
k+1 <–> 0 k+2 <–> 1 … k-1 <–> n-2 x <–> (x-k-1)%n (y+k+1)%n <–> y
//5.当把左列作为自变量x时，右列p(x)=(x-k-1)%n。当把右列记作自变量y时，左列可以表示为r(y)=(y+k+1)%n。r和p互为逆函数。 //6.有
f(n,m)=q(n-1,m)=r(f(n-1,m))=(f(n-1,m)+k+1)%n。 又因为k=(m-1)%n, 则f(n,m)=(f(n-1,m)+m)%n;
//7.最终的递推关系式为
(n=1)时，f(1,m) = 0; (n>1)时，f(n,m)=(f(n-1,m)+m)%n;
public int LastRemaining_Solution(int n,int m) { if(n < 1 || m < 1) return -1; if(n == 1){ return 0; } return (LastRemaining_Solution(n-1, m)+m)%n; }