剑指offer62:圆圈中最后剩下的数字 python
题目描述解法三级目录
题目描述
解法
仿真模拟法，模拟真实情况 利用迭代或者递归，真实模拟该问题 该问题描述的是每次都去掉第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)
三级目录
