题解 | #孩子们的游戏(圆圈中最后剩下的数)#

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param n int整型 
# @param m int整型 
# @return int整型
#
class Solution:
    def LastRemaining_Solution(self , n: int, m: int) -> int:
        result = 0
        # 
        for i in range(2, n + 1):
            # 重新编号 
            # 为甚么叫重新编号呢
            # 假设 n = 9 m = 3 =>f(9,3) array =  1 2 3 4 5 6 7 8 9
            # 去掉 3 array = 4 5 6 7 8 9 1 2 ==编号==> 1 2 3 4 5 6 7 8
            # 编号的关系其实就是 1+3,2+3,...(7+3)%9,(8+3)%9
            # 再去去掉3 array = 4 5 6 7 8 1 2 ==编号==> 1 2 3 4 5 6 7
            # 编号的关系是 1+3,2+3 ... (6+3)%8 (7+3)%8
            # 此时 n = 8 m = 3 => f(8,3) 其实f(8,3)就是f(9,3)去掉一个数后剩下来的
            # 所以 f(8,3)游戏的结果就是f(9,3)唯一不同的其实是编号的不同,原来的编号加上m
            # 故需要重新编号 f(9,3) = (f(8,3) + 3) % 9
            # 一般的 f(n,m) = (f(n-1,m) + m)% n  
            # n指的是当前共有多少个人 每循环一轮少一个 本质上是每一次圈的人数不一致
            # f(1,m) = 1 所以从2开始
            result = (result + m) % i
        return result