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

矫情吗；* 2022-06-09 13:41 126阅读 0赞

/*
    圆圈中最后剩下的数字
    
    思路：
    循环队列，但队列是线性表，删除需要移动元素
    对于删除操作多的需求，考虑循环链表
    
    */
    class ListNode 
    {
    	int val;
    	ListNode next = null;
    
    	ListNode(int val) {
    		this.val = val;
    	}
    }
    
    class LastRemaining
    {
    	//O(mn)
    	public static int lastRemaining(int n, int m) {
    
    		if (n<1||m<1)
    		{
    			return -1;
    		}
            //创建循环链表将0~n-1放进去
    		ListNode head=new ListNode(0);
    		ListNode temp=head;
    		for (int i=1; i<n;i++ )
    		{
    			ListNode ln=new ListNode(i);
    			temp.next=ln;
    			temp=temp.next;
    		}
    		temp.next=head;
    
    		//从前到后依次删除第m个
    		temp=head;
    
    		while (temp.next!=temp)//只剩一个元素时终止
    		{
    			int count=1;
    			while (count<m-1)//temp走到待删除结点的前一个
    			{
    				temp=temp.next;
    				count++;
    			}
    			temp.next=temp.next.next;
    			temp=temp.next;
    		}
    
    		return temp.val;
    		
        }
    
    	//剑指offer，利用映射推倒递推公式，O(n)
    	public static int lastRemaining2(int n, int m) 
    	{
    		if (n<1||m<1)
    		{
    			return -1;
    		}
    
    		if (n==1)
    		{
    			return 0;
    		}
    
    		return (lastRema54ining2(n-1,m)+m)%n;
    
    	}
    
    	public static void main(String[] args) 
    	{
    		System.out.println(lastRemaining2(5,3));
    	}
    }

发表评论取消回复

表情：

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

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

相关阅读

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

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

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

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

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

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

相关《剑指Offer》62：圆圈中最后剩下的数字（约瑟夫环）

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

╰+攻爆jí腚メ/ 2022年12月12日 13:38/ 0 赞/ 89 阅读

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

相关剑指offer—孩子们的游戏圆圈中最后剩下的数字（Java）

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

痛定思痛。/ 2021年12月11日 06:17/ 0 赞/ 178 阅读