约瑟夫环

---

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();
    }
};

数学方法

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]