剑指offer62:圆圈中最后剩下的数字 python
程序员文章站
2022-06-17 16:13:59
...
题目描述
解法
- 仿真模拟法,模拟真实情况
利用迭代或者递归,真实模拟该问题
该问题描述的是每次都去掉第m个数字,那么就是pop掉第m%len(nums),其中nums是1,。。。,n-1组成的列表。然后下一轮也是从m%len(nums)开始,因为去除掉了一个数字,后面所有的数字的索引都移动了一位。
class Solution:
def lastRemaining(self, n: int, m: int) -> int:
nums = list(range(n))
i = 0
while len(nums) > 1:
i = (i+m-1) % len(nums) #因为len(nums)一直在缩减,所以其实每次被pop的位置都是下一次开始的位置
nums.pop(i)
return nums[0]
- 数学归纳法
class Solution:
def lastRemaining(self, n: int, m: int) -> int:
def f(m,n):
if n == 0:
return 0
x = f(m,n-1)
return (m+x)%n
return f(m,n)
三级目录
上一篇: CSS实现边框圆角
下一篇: 学习ExtJS 访问容器对象
推荐阅读
-
【剑指 Offer-python】 03. 数组中重复的数字
-
剑指offer 面试题56 python版+解析:数组中只出现一次的两个数字,数组中唯一只出现一次的数字
-
【剑指Offer】 40.数组中只出现一次的数字 python实现
-
【剑指Offer】40. Python实现数组中只出现一次的数字
-
【剑指Offer】40.数组中只出现一次的数字(Python实现)
-
《剑指offer》—— 46. 圆圈中最后剩下的数(Java)
-
剑指offer62:圆圈中最后剩下的数字 python
-
剑指Offer62:圆圈中最后剩下的数字(Java)
-
python--剑指offer--中等--56 - II. 数组中数字出现的次数 II
-
python--剑指offer--中等--56 - I. 数组中数字出现的次数