LeetCode | 面试题62. 圆圈中最后剩下的数字【剑指Offer】【Python】

妖狐艹你老母 2023-07-18 06:24 15阅读 0赞

> LeetCode 面试题62. 圆圈中最后剩下的数字【剑指Offer】【Easy】【Python】【数学】

### 问题 ###

[力扣][Link 1]

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`

### 思路 ###

**数学**

今天笔试正好考了类似的题目，其实就是约瑟夫环。
    直接给出递推公式:

f ( n , m ) = \{ 0 , n = 1 \[ f ( n − 1 , m ) + m \] % n , n > 1 f(n,m) = \\begin\{cases\} 0,\\quad n = 1 \\\\ \[f(n-1,m)+m\]\\%n,\\quad n > 1 \\end\{cases\} f(n,m)=\{ 0,n=1\[f(n−1,m)\+m\]%n,n>1

##### Python3代码 #####

class Solution:
        def lastRemaining(self, n: int, m: int) -> int:
            if n < 1 or m < 1:
                return None
                
            last = 0
            for i in range(2, n + 1):
                last = (last + m) % i
            return last

### GitHub链接 ###

[Python][]

[Link 1]: https://leetcode-cn.com/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof/
[Python]: https://github.com/Wonz5130/LeetCode-Solutions/blob/master/solutions/Interview-62-yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof/62.py

发表评论取消回复

表情：

评论列表（有 0 条评论，15人围观）

还没有评论，来说两句吧...

相关阅读

相关剑指 Offer 62. 圆圈中最后剩下的数字

[剑指 Offer 62. 圆圈中最后剩下的数字][Offer 62.] 0,1,···,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字（删除

Dear 丶/ 2023年10月02日 15:25/ 0 赞/ 48 阅读

相关剑指 Offer 62. 圆圈中最后剩下的数字【29】

> 难度等级：简单 > 上一篇算法： > > [剑指 Offer 64. 求1+2+…+n【数学】][Offer 64. _1_2_n] > 力扣此题地址： > > [

谁借莪１个温暖的怀抱￠/ 2023年09月27日 12:17/ 0 赞/ 166 阅读

相关 leetcode每日一题.面试题62:圆圈中最后剩下的数字

题目描述： 0,1,,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字。求出这个圆圈里剩下的最后一个数字。例如，0、

忘是亡心i/ 2023年07月19日 10:55/ 0 赞/ 38 阅读

相关 leetcde 面试题62. 圆圈中最后剩下的数字

思路1：模拟，用链表或者一个队列即可实现，但时间复杂度过高。思路2：数学推理设 f(n,m)表示长度为n的序列，每次删除第m个以后，最后剩下的数字。那么，第一个删

骑猪看日落/ 2023年07月19日 08:11/ 0 赞/ 50 阅读

相关 LeetCode | 面试题62. 圆圈中最后剩下的数字【剑指Offer】【Python】

> LeetCode 面试题62. 圆圈中最后剩下的数字【剑指Offer】【Easy】【Python】【数学】问题 [力扣][Link 1] 0,1,n-1这n个数

妖狐艹你老母/ 2023年07月18日 06:24/ 0 赞/ 16 阅读

相关剑指offer--62. 圆圈中最后剩下的数字

题目描述 0,1,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字。求出这个圆圈里剩下的最后一个数字。例如，0、1、2、3、4这5个数字组成

朱雀/ 2023年02月28日 05:37/ 0 赞/ 198 阅读

相关面试题62. 圆圈中最后剩下的数字

题目来源 [leetcode][] 题目描述 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_

川长思鸟来/ 2023年02月11日 03:09/ 0 赞/ 80 阅读

相关剑指 Offer 62. 圆圈中最后剩下的数字

题目重述 0,1,···,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字（删除后从下一个数字开始计数）。求出这个圆圈里剩下的最后一个数字。

深藏阁楼爱情的钟/ 2022年09月15日 13:56/ 0 赞/ 193 阅读

相关剑指offer_圆圈中最后剩下的数字

/ 圆圈中最后剩下的数字思路：循环队列，但队列是线性表，删除需要移动元素对于删除操作多的需求，考虑循环链表

矫情吗；*/ 2022年06月09日 13:41/ 0 赞/ 215 阅读

相关剑指offer-题45：圆圈中最后剩下的数字

题目描述 0,1,……,n-1这n个数字排成一个圆圈，从数字0开始每次从这个圆圈里删除第m个数字。求出这个圆圈里剩下的最后一个数字。实验平台：[牛客网][Link 1

布满荆棘的人生/ 2022年05月27日 08:19/ 0 赞/ 191 阅读