1. FlyPython首页
  2. 数据结构与算法
  3. leetcode题解

「LeetCode每日一题」——LCOF.62. 圆圈中最后剩下的数字

LCOF.62. 圆圈中最后剩下的数字

链接:https://leetcode-cn.com/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof/
难度:简单

题目

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

思路

这个题的思路,应该是递归。

开始有n个数字时,数到m个数字然后删除,那删除的其实是 m % n个的数字,然后数字变成了n-1个,继续删除m个数字,循环。

f(n, m) 递归开始
f(n-1,m)
...
f(1,m) 递归终点

如果 x = f(n-1,m),那么 f(n-1, m ) = (m%n+x)%n = (m+x)%n

递归的表达式有了,代码见解决方案。

方案代码

解决方案:

class Solution:
    def lastRemaining(self, n: int, m: int) -> int:
        def f(n,m):
            if n == 0:
                return  0
            x = f(n-1,m)
            return (m+x) % n
        
        return f(n, m)

原创文章,作者:flypython,如若转载,请注明出处:http://flypython.com/algorithm/leetcode/264.html