美文网首页
约瑟夫环

约瑟夫环

作者: 小幸运Q | 来源:发表于2021-04-24 17:47 被阅读0次

image.png

暴力

class Solution {
public:
    int lastRemaining(int n, int m) {
        list<int>l;
        for(int i=0;i<n;i++){
            l.push_back(i);
        }
        list<int>::iterator start=l.begin();
        while(l.size()>1){
            for(int i=0;i<m-1;i++){
                if(start==l.end()){
                    start=l.begin();
                }
                start++;
            }
            if(start==l.end()){
                start=l.begin();
            }            
            start=l.erase(start);
        }
        return *l.begin();
    }
};

数学方法

f(n,m) = [f(n-1, m) + m] % n

class Solution:
    def lastRemaining(self, n: int, m: int) -> int:
        dp={}
        dp[2,m]=m%2
        for i in range(3,n+1):
            dp[i,m]=(dp[i-1,m]+m)%i
        # print(dp)
        return dp[n,m]

相关文章

  • 约瑟夫环问题

    约瑟夫环问题约瑟夫环描述:约瑟夫环(约瑟夫问题)是一个数学的应用问题:已知n个人(以编号1,2,3…n分别表示)围...

  • 循环单链表实现约瑟夫环(C语言)

    约瑟夫环

  • 约瑟夫环

    题目:100名学生围成一个圈, 编号从1到100,从第一名学生开始报数,从1-9报数 每报出9就退出,直到所有学生...

  • 约瑟夫环

  • 约瑟夫环

    问题:1~n个人围成一圈,从1开始报数,每次数到m这个人就出列,问最后剩下的是几号? 做法:递归。 假设剩下的是f...

  • 约瑟夫环

    解法一 用一个list模拟删除过程 解法二 数学公式,推到过程还没看懂

  • 约瑟夫环

    之前去面试的时候遇到这个问题,作为一只算法渣渣,自然带着恐惧的心情,然后自己瞎捣鼓了好长时间终于拼凑出来了一个很菜...

  • 约瑟夫环

  • 约瑟夫环

    复习一下关于约瑟夫环的实现原理: 如果用C来写的话,也会有许多的方法,比如1:采用链表(双向链表)2:递归3:队列...

  • 约瑟夫环

    公式法循环 公式法递归 链表法

网友评论

      本文标题:约瑟夫环

      本文链接:https://www.haomeiwen.com/subject/lidwlltx.html