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

只想了一个最普通的解法：

public class Solution {
    public int LastRemaining_Solution(int n, int m) {
        if  (n <= 0 || m <= 0) 
            return -1;
        int i = 0;
        int[] a = new int[n];
        for (int left = n, j = m; left > 1; --left, j = m) { // left是剩余人数要大于1，每次重置j为m
            while (j > 0) {
                if (a[i++ % n] == 0) {
                    --j;
                }
            }
            a[(i - 1) % n] = 1; // 上面的写法，i会多走一步
        }
        for (i = 0; i < n; ++i) {
            if (a[i] == 0) {
                break;
            }
        }
        return i;
    }
}

递归

下面是题解中的递归实现：

public class Solution {
    public int LastRemaining_Solution(int n, int m) {
        if  (n <= 0 || m <= 0) 
            return -1;
        return f(n, m);
    }

    private int f(int n, int m) {
        if (n == 1)
            return 0;
        return (f(n-1, m) + m) % n; // 
    }
}

这个递归的解法还是很巧妙的，尤其是f(n, m)是以输入的值作为参数，而输出是下标，对于这种输入是1开始，下标又是0开始的，有一种新的思路。

递推

有了上面的递归，递推的解法实现如下：

public class Solution {
    public int LastRemaining_Solution(int n, int m) {
        if  (n <= 0 || m <= 0) 
            return -1;
        int index = 0;
        for (int i = 2; i <= n; ++i) { // i = 1时，index = 0，因此省略了
            index = (index + m) % i;
        }
        return index;
    }
}