剑指offer - 62.圆圈中最后剩下的数字
程序员文章站
2024-03-07 20:49:33
...
(今天特别开心,拿到了一个心仪的offer,之前一直不太顺利,恭喜,但浪费了一下午,逛b站去了。。)
先还是把基础的算法题还是刷一下吧,这类型的博客网上有很多很多,不过大多是抄书上的代码,我想自己写一下。可能不一定严谨,但基本功能会实现。
慢慢的尝试有思路后能够自己写出代码来。
(这个题目原本想直接用链表写的,但是因为输入n个数构成n个节点后不好链接,每个节点需要一个对象名,没写成,以后再改)
#include <iostream>
#include <vector>
#include<algorithm>
#include<list>
using namespace std;
int main()
{
int n, m;
cin >> n >> m;
list<int> num;
for (int i = 0; i < n; i++) {
num.push_back(i);
}
int i = 1;
list<int>::iterator cur = num.begin();
while (num.size() > 1) {
cur++;
if (cur == num.end()) cur = num.begin(); //这里要在cur++下面,否则cur已经到end了(就应该跳到第0个位置),但后面却要把它删掉,结果找不到元素。
i++;
if (i%m == 0) {
list<int>::iterator to_delete = cur;
list<int>::iterator next = ++cur;
if (next == num.end()) next = num.begin();
num.erase(to_delete);
cur = next;
i = 1;
}
}
cout << num.front();
return 0;
}