「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
微信扫一扫 
支付宝扫一扫 相关推荐
-
「LeetCode每日一题」——LCCI 10.01. 合并排序的数组
LCCI 10.01. 合并排序的数组 链接：https://leetcode-cn.com/problems/sorted-merge-lcci/难度：简单 题目 给定两个排序后…
-
「LeetCode每日一题」——LCOF.59 – II. 队列的最大值
链接：https://leetcode-cn.com/problems/dui-lie-de-zui-da-zhi-lcof/难度：中等 题目 请定义一个队列并实现函数 max_v…
-
「LeetCode每日一题」—— 1111. 有效括号的嵌套深度
1111. 有效括号的嵌套深度 链接：https://leetcode-cn.com/problems/maximum-nesting-depth-of-two-valid-par…
-
「LeetCode每日一题」—— 33. 搜索旋转排序数组
33. 搜索旋转排序数组 链接：https://leetcode-cn.com/problems/search-in-rotated-sorted-array/难度：中等 题目 点…
-
「LeetCode每日一题」—— 8. 字符串转换整数 (atoi)
8. 字符串转换整数 (atoi) 链接：https://leetcode-cn.com/problems/string-to-integer-atoi/难度：中等 题目 请你来实…
-
「LeetCode每日一题」—— 445. 两数相加 II
445. 两数相加 II 链接：https://leetcode-cn.com/problems/add-two-numbers-ii/难度：中等 题目 点击原文链接跳转查看题目 …
-
「LeetCode每日一题」——LCCI.17.16. 按摩师
LCCI.17.16. 按摩师 链接：https://leetcode-cn.com/problems/the-masseuse-lcci/难度：简单 题目 一个有名的按摩师会收到…
-
「LeetCode每日一题」——1162. 地图分析
1162. 地图分析 链接：https://leetcode-cn.com/problems/as-far-from-land-as-possible/难度：中等 题目 你现在手里…
-
「LeetCode每日一题」——409. 最长回文串
409. 最长回文串 链接：https://leetcode-cn.com/problems/longest-palindrome/难度：简单 题目 给定一个包含大写字母和小写字母…
-
「LeetCode每日一题」——1013. 将数组分成和相等的三个部分
1013. 将数组分成和相等的三个部分 链接：https://leetcode-cn.com/problems/partition-array-into-three-parts-w…
您必须登录才能发表评论。