孩子們的遊戲(java)

每年六一兒童節,牛客都會準備一些小禮物去看望孤兒院的小朋友,今年亦是如此。HF作為牛客的資深元老,自然也準備了一些小遊戲。其中,有個遊戲是這樣的:首先,讓小朋友們圍成一個大圈。然後,他随機指定一個數m,讓編号為0的小朋友開始報數。每次喊到m-1的那個小朋友要出列唱首歌,然後可以在禮品箱中任意的挑選禮物,并且不再回到圈中,從他的下一個小朋友開始,繼續0…m-1報數…這樣下去…直到剩下最後一個小朋友,可以不用表演,并且拿到牛客名貴的“名偵探柯南”典藏版(名額有限哦!!_)。請你試着想下,哪個小朋友會得到這份禮品呢？(注：小朋友的編号是從0到n-1)

這不就是約瑟夫環麼！！！

小劉想偷個懶，解釋都在代碼裡?。

我解釋一下最後一個循環，計算機模拟的相當于，現實中每個孩子都在一個隔間中，牛客的資深元老HF，雖然他是牛客的資深元老，但他還是沒有孫大聖的火眼金睛?，他要找到遊戲勝出者，就隻能一個一個隔間的去檢視最後的勝出者是誰。

本代碼的亮點在于 i=++i % n

不能了解的同學要好好看一下%模運算喲！！！計算機底層源碼在擴容時候好多都是%模運算呀，要好好掌握。

public class Solution {
    public static int LastRemaining_Solution(int n, int m) {
        if(n < 1 || m < 1){
            return -1;
        }
        //将孩子模拟成一個數組
        int[] arr = new int[n];
        int count = 0;  //孩子們報的數
        int j = n;  //留在圈圈中孩子的個數
        for(int i = 0; j > 1 ; i=++i % n){
        //這塊是不是有人她才報數！！！
            if(arr[i] != -1){
                count++;
            }
        //她如果報的數剛好等于m，她是不是要退出，下一位從0開始重新報數
            if(count == m){
                arr[i] = -1;
                j--;
                count = 0;
            }
      }
        //周遊數組找到那個幸運的孩子鴨。
        for(int b = 0; b < n-1 ;b++){
            if(arr[b] == 0){
                return b;
            }
        }
        return -1;
    }
    //遞歸思想，目前還沒參透
    public int LastRemaining_Solution1(int n, int m){
  	if(n < 1 || m < 1){
        	return -1;
    	}
    	int last = 0;
    	for(int i = 2;i <= n;i++){
        	last = (last + m) % i;
    	}
    	return last;
	}
}