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

第七十六题

方法一：模拟出这个圈，然后遍历和删除

class Solution {
public:
    int LastRemaining_Solution(int n, int m) {
        // 数据结构中就说过 好像叫约瑟夫环
        // 方法1，模拟循环下去，每三个人干掉一个
        vector<int> circle;
        for(int i=0;i<n;i++)
            circle.push_back(i);
        int now=0;
        while(n>1){

            // 循环队列
            now=(now+m-1)%n;
            circle.erase(circle.begin()+now);
            n--;
        }
        return circle[0];
    }
};

方法2：上网找原理讲解吧

class Solution {
public:
    int LastRemaining_Solution(int n, int m) {
        // 数据结构中就说过 好像叫约瑟夫环
        // 方法2 正经的约瑟夫环的算法
        return f(n,m);
    }
    
    // 递归调用求解
    int f(int n,int m)
    {
        if(n == 1)
            return 0;
        else
            return (f(n-1,m) + m) % n;
    }
};