【剑指】56，圆圈最后剩的数字(链表）

╰+攻爆jí腚メ 2023-07-13 12:17 13阅读 0赞

**题目描述**  
抽象后，n个数字，一开始给一个m(m<n),从0开始到m-1.第m-1个需要被移除。然后，从m-1的下一个开始又0~m-1，第m-1的那个继续被移除，问：最后剩下来的数字是？（没有返回-1)  
思路：  
因为需要频繁地修改节点，所以我们采用list链表来作为数据结构。首先存入节点，然后找到第m个节点，同时记录下一个开始的节点，这两步都要注意不能越界要做end判断。然后擦除节点，继续m-1，终止条件：size==1

代码：

class Solution { 
    public:
        int LastRemaining_Solution(int n, int m)
        { 
        	if(n<1 || m <1)	//没有第零位因为要到m-1
        		return -1;
        	unsigned int i=0;
        	list<int> boys;
        	while(i<n)
        		boys.push_back(i++);
        	list<int> ::iterator curboy=boys.begin();
        	//迭代器的定义
        	while(boys.size()>1)	//==1 终止
        	{ 
        		for(i=1;i <m;	++i)
        			{ 
        				curboy++;
        				if(curboy==boys.end())
        					curboy=boys.begin();
        			}
        		list<int> ::itetator nextboy=++curboy;
        		curboy--;
        		if(nextboyboy==boys.end())
        					nextboy=boys.begin();
        		curboy--;
        		boys.erase(curboy);
        		curboy=nextboy;
        	}
        	return *boys.begin();
        }

发表评论取消回复

表情：

评论列表（有 0 条评论，13人围观）

还没有评论，来说两句吧...

相关阅读

相关剑指 Offer 62. 圆圈中最后剩下的数字

[剑指 Offer 62. 圆圈中最后剩下的数字][Offer 62.] 0,1,···,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字（删除

Dear 丶/ 2023年10月02日 15:25/ 0 赞/ 87 阅读

相关剑指 Offer 62. 圆圈中最后剩下的数字【29】

> 难度等级：简单 > 上一篇算法： > > [剑指 Offer 64. 求1+2+…+n【数学】][Offer 64. _1_2_n] > 力扣此题地址： > > [

谁借莪１个温暖的怀抱￠/ 2023年09月27日 12:17/ 0 赞/ 215 阅读

相关【剑指】56，圆圈最后剩的数字(链表）

题目描述抽象后，n个数字，一开始给一个m(m<n),从0开始到m-1.第m-1个需要被移除。然后，从m-1的下一个开始又0~m-1，第m-1的那个继续被移除，问：最后剩下

╰+攻爆jí腚メ/ 2023年07月13日 12:17/ 0 赞/ 14 阅读

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

题目描述 0,1,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字。求出这个圆圈里剩下的最后一个数字。例如，0、1、2、3、4这5个数字组成

朱雀/ 2023年02月28日 05:37/ 0 赞/ 245 阅读

相关剑指 Offer 62. 圆圈中最后剩下的数字

题目重述 0,1,···,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字（删除后从下一个数字开始计数）。求出这个圆圈里剩下的最后一个数字。

深藏阁楼爱情的钟/ 2022年09月15日 13:56/ 0 赞/ 238 阅读

相关【剑指offer-Java版】45圆圈中最后剩下的数字

圆圈中最后剩余的数字:约瑟夫环问题 0-n这n个数字排成一圈，从数字零开始每次从这个圆圈中删除第m个数字，求出剩余的最后一个数字 public class _Q4

川长思鸟来/ 2022年08月21日 10:46/ 0 赞/ 205 阅读

相关剑指offer之面试题45圆圈中最后剩下的数字

问题描述： 0,1,2,3……，n-1这n个数字排成一个圆圈，从数字0开始每次从这个圆圈里删除第m个数字。求最后这个圆圈里剩下的最后一个数字。实现代码如下： i

怼烎@/ 2022年07月24日 04:14/ 0 赞/ 198 阅读

相关剑指offer_圆圈中最后剩下的数字

/ 圆圈中最后剩下的数字思路：循环队列，但队列是线性表，删除需要移动元素对于删除操作多的需求，考虑循环链表

矫情吗；*/ 2022年06月09日 13:41/ 0 赞/ 260 阅读

相关剑指offer-题45：圆圈中最后剩下的数字

题目描述 0,1,……,n-1这n个数字排成一个圆圈，从数字0开始每次从这个圆圈里删除第m个数字。求出这个圆圈里剩下的最后一个数字。实验平台：[牛客网][Link 1

布满荆棘的人生/ 2022年05月27日 08:19/ 0 赞/ 232 阅读

相关剑指offer 圆圈中最后剩下的数

\题目描述每年六一儿童节,牛客都会准备一些小礼物去看望孤儿院的小朋友,今年亦是如此。HF作为牛客的资深元老,自然也准备了一些小游戏。其中,有个游戏是这样的:首先,让小朋友

布满荆棘的人生/ 2022年05月21日 05:17/ 0 赞/ 662 阅读