62.圆圈中最后剩下的数字
题目
0,1,...,n-1这n个数字排成一个圆圈,从数字0开始,每次从这个圆圈里删除第m个数字。求出这个圆圈里剩下的最后一个数字。
例如,0、1、2、3、4这5个数字组成一个圆圈,从数字0开始每次删除第3个数字,则删除的前4个数字依次是2、0、4、1,因此最后剩下的数字是3。
方法一 环形链表模拟圆圈
思路:用head找要被删除的元素,用temp的指针指向head。当找到该元素时,令head=head.next,temp.next=head将该元素删除。
class Solution:
def lastRemaining(self, n: int, m: int) -> int:
head = temp = ListNode(0)
for i in range(1, n):
temp.next = ListNode(i)
temp = temp.next
temp.next = head
while temp.next != temp:
for i in range(m-1):
head = head.next
temp = temp.next
head = head.next
temp.next = head
return temp.val
结果:超时
方法二 环形列表
思路:与链表类似,自己定义一个列表arr=[0, 1, ..., N-1],每次从i开始计数,数到第m个值将其删除。最后返回列表中仅存的元素。
用%操作使得列表循环遍历。
代码
class Solution:
def lastRemaining(self, n: int, m: int) -> int:
arr = [i for i in range(n)]
i = 0
size = n
while size > 1:
del_index = (i+m-1) % size
arr.remove(arr[del_index])
size -= 1
i = del_index
return arr[0]
结果:超时
方法三 数学
思路:设从0开始计数,共n个人,数到m个依次出局,最后剩下的人编号设为f(n,start=0)。第一次出局的人编号为(m-1)%n,记为k。
第二次从k+1开始数,即f(n-1, start=k+1)=f(n, start=0)。
又因为f(n-1, start=k+1)=(f(n-1, start=0)+k+1)%n。
有f(n-1, start=k+1)这个中间桥梁,可以推出f(n, start=0)=(f(n-1, start=0)+k+1)%n。即 (f(n)=f(n-1)+m)%n.
代码
class Solution:
def lastRemaining(self, n: int, m: int) -> int:
if n < 1 or m < 1:
return None
res = 0
for i in range(2, n+1):
res = (res + m) % i
return res
结果
执行用时 :84 ms, 在所有 Python3 提交中击败了82.30%的用户
内存消耗 :13.6 MB, 在所有 Python3 提交中击败了100.00%的用户
[剑指offer]62.圆圈中最后剩下的数字的更多相关文章
-
剑指 Offer 62. 圆圈中最后剩下的数字 + 约瑟夫环问题
剑指 Offer 62. 圆圈中最后剩下的数字 Offer_62 题目描述 方法一:使用链表模拟 这种方法是暴力方法,时间复杂度为O(nm),在本题中数据量过大会超时. 方法二:递归方法 packag ...
-
【Java】 剑指offer(62) 圆圈中最后剩下的数字
本文参考自<剑指offer>一书,代码采用Java语言. 更多:<剑指Offer>Java实现合集 题目 0, 1, …, n-1这n个数字排成一个圆圈,从数字0开始每 ...
-
剑指offer——72圆圈中最后剩下的数字
题目描述 每年六一儿童节,牛客都会准备一些小礼物去看望孤儿院的小朋友,今年亦是如此.HF作为牛客的资深元老,自然也准备了一些小游戏.其中,有个游戏是这样的:首先,让小朋友们围成一个大圈.然后,他随机指 ...
-
【剑指offer】圆圈中最后剩下的数字(约瑟夫问题),C++实现
原创博文,转载请注明出处! # 题目 # 思路 本题即为典型的约瑟夫问题,通过递推公式倒推出问题的解.原始问题是从n个人中每隔m个数踢出一个人,原始问题变成从n-1个人中每隔m个数踢出一个人-- ...
-
剑指offer46:圆圈中最后剩下的数字(链表,递归)
1 题目描述 每年六一儿童节,牛客都会准备一些小礼物去看望孤儿院的小朋友,今年亦是如此.HF作为牛客的资深元老,自然也准备了一些小游戏.其中,有个游戏是这样的:首先,让小朋友们围成一个大圈.然后,他随 ...
-
Java实现 LeetCode 面试题62. 圆圈中最后剩下的数字(约瑟夫环)
面试题62. 圆圈中最后剩下的数字 0,1,n-1这n个数字排成一个圆圈,从数字0开始,每次从这个圆圈里删除第m个数字.求出这个圆圈里剩下的最后一个数字. 例如,0.1.2.3.4这5个数字组成一个圆 ...
-
【LeetCode】面试题62. 圆圈中最后剩下的数字
题目:面试题62. 圆圈中最后剩下的数字 这题很有意思,也很巧妙,故记录下来. 官方题解思路,是约瑟夫环的数学解法: 我们将上述问题建模为函数 f(n, m),该函数的返回值为最终留下的元素的序号. ...
-
[LeetCode]面试题62. 圆圈中最后剩下的数字(数学)
题目 0,1,,n-1这n个数字排成一个圆圈,从数字0开始,每次从这个圆圈里删除第m个数字.求出这个圆圈里剩下的最后一个数字. 例如,0.1.2.3.4这5个数字组成一个圆圈,从数字0开始每次删除第3 ...
-
【LeetCode】面试题62. 圆圈中最后剩下的数字 解题报告(Python)
作者: 负雪明烛 id: fuxuemingzhu 个人博客:http://fuxuemingzhu.cn/ 目录 题目描述 题目大意 解题方法 约瑟夫环 日期 题目地址:https://leetco ...
随机推荐
-
iOS审核这些坑,腾讯游戏也踩过
作者:Jamie,专项技术测试工程师,在iOS预审和ASO优化领域从事专项测试相关工作,为腾讯游戏近100个产品提供专项服务. WeTest 导读 在App上架苹果应用商店的过程中,相信大多数iOS开 ...
-
TCP/IP详解之:TCP
第17章 TCP:传输控制协议 TCP提供了一种可靠的面向连接的字节流运输层服务 TCP的服务 尽管TCP和UDP都使用相同的网络层(IP),TCP却向应用层提供与UDP完全不同的服务. TCP通过下 ...
-
ethtool命令
用途 显示或修改以太网卡的配置信息. 语法 ethtool [ -a | -c | -g | -i | -d | -k | -r | -S |] ethX ethtool [-A] ethX [aut ...
-
perl的package和module
来源: http://www.cnblogs.com/itech/archive/2010/03/23/1692836.html 一 package 1) package 相当于C++中的namesp ...
-
java第九次学习总结
1. 本周学习总结 2.. 书面作业 1.常用异常 题目5-1 1.1 提交结果(出现学号) 1.2 自己以前编写的代码中经常出现什么异常.需要捕获吗(为什么)?应如何避免? 以前编写的代码经常出现异 ...
-
[leetcode]经典算法题- String to Integer (atoi)
题目描述: 把字符串转化为整数值 原文描述: Implement atoi to convert a string to an integer. Hint: Carefully consider al ...
-
一、Swagger配置
一.Swagger配置 1.注解不显示 SwaggerConfig文件下 //c.IncludeXmlComments(GetXmlCommentsPath()): 内下面添加: c.Inclu ...
-
MD5加密及Hash长度拓展攻击【通俗易懂】
先放一个简单点的利用了Hash长度拓展攻击的题目 if($COOKIE["getmein"] === md5($secret . urldecode($username . $pa ...
-
la3890(半平面交)
蓝书半平面交例题 #include<iostream> #include<cstring> #include<cmath> #include<cstdio&g ...
-
easyui表格,单元格合并
easyui的合并单元格比较麻烦,官网提供一下方法 $('#tt').datagrid({ onLoadSuccess:function(){ var merges = [{ index:2, row ...