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;
        }
}