圆圈中最后剩下的数字（约瑟夫问题）

本文主要是介绍圆圈中最后剩下的数字（约瑟夫问题），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

0,1,…,n−1 这 n 个数字 (n>0) 排成一个圆圈，从数字 0 开始每次从这个圆圈里删除第 m 个数字。

求出这个圆圈里剩下的最后一个数字。

样例
输入：n=5 , m=3

输出：3

循环队列：

class Solution {
public:
    int lastRemaining(int n, int m){
        queue<int> q;
        for(int i = 0; i < n; i++) q.push(i);
        int cnt = 0;
        while(q.size() > 1){
            int t = q.front();
            q.pop();
            cnt++;
            if(cnt == m){
                cnt = 0;
                continue;
            }
            q.push(t);
        }
        return q.front();
    }
};

递推：

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

这篇关于圆圈中最后剩下的数字（约瑟夫问题）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！