约瑟夫环问题

• 题目描述：
  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
  链接：https://leetcode-cn.com/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof

• 解题思路：

1. 没看清题意时，以为删除后从头开始数，结果发现是继续从删除元素后一个元素开始计数
2. 将原问题拆分成子问题解决，原问题可表述为：给定一个长度为 n 的序列，每次向后数 m 个元素并删除，那么最终留下的是第几个元素？
3. 先假设函数f(n,m)，return最后剩余元素的索引
4. f(n)先删除第 m % n 个元素，剩下f(n-1)
5. 递归求解f(n-1)
6. 假设f(n-1,m) = x，则 x 是f(n-1)最后剩余元素，也是f(n)最后删除元素
7. 由于f(n)从0开始排列，而f(n-1)从 m % n 后一个元素开始排列，所以f(n)最后删除的元素位置，也就是x的位置，是从 m % n 开始计数后的第x个元素
8. 得到f(n-1,m) = (m + x) % n，递归计算

• Python版：

# Python 默认的递归深度不够，需要手动设置
sys.setrecursionlimit(100000)

def f(n, m):
    if n == 0:
        return 0
    x = f(n - 1, m)
    return (m + x) % n

class Solution:
    def lastRemaining(self, n: int, m: int) -> int:
        return f(n, m)

• C++版：

class Solution {
    int f(int n, int m) {
        if (n == 1)
            return 0;
        int x = f(n - 1, m);
        return (m + x) % n;
    }
public:
    int lastRemaining(int n, int m) {
        return f(n, m);
    }
};

• 解题思路2：
  上面的递归可以改写为迭代，避免递归使用栈空间

• Python版：

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

Tips:

• 从 [2,n+1] 内遍历，因为计算的是f(n-1)，n>=1

• C++版：

class Solution {
public:
    int lastRemaining(int n, int m) {
        int f = 0;
        for (int i = 2; i != n + 1; ++i)
            f = (m + f) % i;
        return f;
    }
};