欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

剑指offer - 62.圆圈中最后剩下的数字

程序员文章站 2024-03-07 20:49:33
...

(今天特别开心,拿到了一个心仪的offer,之前一直不太顺利,恭喜,但浪费了一下午,逛b站去了。。)
先还是把基础的算法题还是刷一下吧,这类型的博客网上有很多很多,不过大多是抄书上的代码,我想自己写一下。可能不一定严谨,但基本功能会实现。
慢慢的尝试有思路后能够自己写出代码来。
(这个题目原本想直接用链表写的,但是因为输入n个数构成n个节点后不好链接,每个节点需要一个对象名,没写成,以后再改)

剑指offer - 62.圆圈中最后剩下的数字

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