题目描述

0, 1, ...., n-1 这 n 个数字排成一个圆圈，从数字 0 开始，每次从这个圆圈中删除第 m 个数字
求出这个圆圈里剩下的最后一个数字

题目解读

剑指Offer 300

代码

思路一、用环形链表模拟圆圈，依次剔除第 m 个数字

#include<iostream>
#include<list>
using namespace std;

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

        list<int> circle;
        for(int i=0; i < n; i++){
            circle.push_back(i);
        }

        list<int>::iterator current = circle.begin();
        list<int>::iterator next;
        while(circle.size() > 1){

            // 往后读 m-1 位
            for(int k=1; k < m; k++){
                current ++;
                if(current == circle.end()){
                    current = circle.begin();
                }
            }

            current ++;
            next = current;
            if(next == circle.end()){
                next = circle.begin();
            }
            current --;
            circle.erase(current);
            current = next;
        }
        return *current;
    }
};

int main(){
    Solution ss;
    
    int n = 5;
    int m = 3;
    int result = ss.LastRemaining_Solution(n, m);
    cout<<result<<endl;
}

思路二、找到出圈数字的规律
重点关注思路一吧，这个方法了解就好

#include<iostream>
#include<list>
using namespace std;

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

        int last = 0;
        for(int i=2; i <= n; i++){
            last = (last + m)%i;
        }
        return last;
    }
};

int main(){
    Solution ss;
    
    int n = 5;
    int m = 3;
    int result = ss.LastRemaining_Solution(n, m);
    cout<<result<<endl;
}