Java教程

圆圈中最后剩下的数字(约瑟夫问题)

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

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;
    }
};
这篇关于圆圈中最后剩下的数字(约瑟夫问题)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!