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