题目

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 代表前进的个数
image.png

  1. class Solution:
  2.     def lastRemaining(self, n: int, m: int) -> int:
  3.         pos = 0 
  4.         for i in range(2, n+1):
  5.             pos = (pos+m)%i
  6.         return pos
  1. class Solution:
  2.     def lastRemaining(self, n: int, m: int) -> int:
  3.         if n == 1:
  4.             return 0
  5.         else:
  6.             return (self.lastRemaining(n-1, m)+m)%n

https://leetcode-cn.com/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof/solution/huan-ge-jiao-du-ju-li-jie-jue-yue-se-fu-huan-by-as/