约瑟夫环

公式法循环

class Solution {
public:
    int LastRemaining_Solution(int n, int m)
    {
        if(n<1 || m<1)
            return -1;
        int s=0;
        for(int i=2;i<=n;i++)
        {
            s=(s+m)%i;
        }
        
        return s;
    }
};

公式法递归

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

链表法

class Solution {
public:
    int LastRemaining_Solution(int n, int m)
    {
        if( n<1 || m <1 )//判断边界条件
            return -1;
         
        list<int> number;
        for(int i=0;i<n;i++)//初始化链表
        {
            number.push_back(i);
        }
        list<int>::iterator current = number.begin();
         
        while(number.size()>1)
        {
            for(int i=1;i<m;i++)//找到第m个结点，记住是循环m-1次而不是m次
            {
                current++;
                if(current == number.end())
                    current = number.begin();
            }
             
            list<int>::iterator next = ++current;//保存删除后的起始结点
            if(next == number.end())
                next = number.begin();
             
            current--;
            number.erase(current);
            current = next;
        }
         
        return *current;
    }
};