每日一题-30

题目描述

圆圈中最后剩下的数字 - 约瑟夫环
0,1,,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字。求出这个圆圈里剩下的最后一个数字。

例如，0、1、2、3、4这5个数字组成一个圆圈，从数字0开始每次删除第3个数字，则删除的前4个数字依次是2、0、4、1，因此最后剩下的数字是3。

示例 1：

输入: n = 5, m = 3
输出: 3
示例 2：

输入: n = 10, m = 17
输出: 2

限制：

1 <= n <= 10^5
1 <= m <= 10^6

解题思路

1.暴力破解，勉强过测试。直接创建一个[0...n-1]的列表，每次计算需要删除的元素索引，然后从列表中删除这个元素。一直到列表中只剩下一个元素
2.从最后一个逆推。

• 由于最后只剩下一个元素，所以此时它的索引一定为0
• 倒推到倒数第二轮，由于每一轮的开头都是上一轮的开头移动了m次得到的，所以上一次的开头(0+m)%(倒数第二轮的长度）
• 详细推理参考-https://leetcode-cn.com/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof/solution/javajie-jue-yue-se-fu-huan-wen-ti-gao-su-ni-wei-sh/

3.递归公式-直接参考吧，没看懂
https://leetcode-cn.com/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof/solution/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-by-lee/

代码

class Solution:
    def lastRemaining(self, n: int, m: int) -> int:
        # res = 0
        # for i in range(2, n+1):#倒着逆推
        #     res = (res+m)%i
        # return res
        ls = [i for i in range(n)]
        index = 0
        while len(ls)>1:
            index = (index+m-1)%len(ls)
            ls.pop(index)
        return ls[0]