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

这个问题就是约瑟夫环问题。
显然这个可以用链表实现，除了链表之外，可以观察其规律。
n个人，需要报的数为m，那么被挑出的人就是(m-1)%n,下一个开始的人就是m%n,这是圆圈还有n-1个人。我们可以发现这不就是n-1个人，需要报的数为m的版本吗。所以我们需要看一看两者编号之间有无规律，m%n为开始，在n-1中为0，再考虑环，我们不妨试一下(0+m%n)%n可不可以复原，发现是可以的，ok，规律找到了。那么我们把大问题拆分，到最后为n=1的情况，即最后存活的人，用递归来做。

class Solution {
public:
    int LastRemaining_Solution(int n, int m) {
        if(n == 0) return -1;
        if(n == 1) return 0;
        int k = m%n;
        return (LastRemaining_Solution(n-1, m) + k)%n;
    }
};

另外补充一个非递归的版本吧。

class Solution {
public:
    int LastRemaining_Solution(int n, int m) {
        if(n == 0) return -1;
        int number = 0;
        for(int i=1;i<n;i++){
            number += m%(i+1);
            number %= i+1;
        }
        return number;
    }
};