Leetcode LCR 187. 破冰游戏

1.题目基本信息

1.1.题目描述

社团共有 num 位成员参与破冰游戏，编号为 0 ~ num-1。成员们按照编号顺序围绕圆桌而坐。社长抽取一个数字 target，从 0 号成员起开始计数，排在第 target 位的成员离开圆桌，且成员离开后从下一个成员开始计数。请返回游戏结束时最后一位成员的编号。

1.2.题目地址

https://leetcode.cn/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof/description/

2.解题方法

2.1.解题思路

约瑟夫环问题

递推式：f(n,m)=(f(n-1,m)+m)%n

2.2.解题步骤

递推式证明：

问题：假设有n个元素，从0开始编号，并形成一个环，初始从编号0开始计数，每次将第m个元素从环中剔除，然后从其下一个元素重新开始计数，问最后一个剔除的元素是多少？

假设f(n,m)为上面的(n,m)问题的解；

f(n,m)递推式：

• f(n,m)=(f(n-1,m)+m)%n

• 初始f(1,m)=0

递推式推导：

• 第一次提出的是第m个元素，即编号为(m-1)%n的元素，并且下一个开始计数的元素的编号为m%n，即为t=m%n；

• 对于第一次删除后的元素序列0,1,2,...,t-2,t,...,n-1，将t,...,n-1的子序列移动到前面，得到序列t,...,n-1,0,1,2,...,t-2，记该序列为arr1；

• 将arr1的每个元素加上(n-t)并对n取模，得到序列0,1,...,n-t-1,n-t,...,n-2，记该序列为arr2，可以观察到arr2就是一个f(n-1,m)子问题的对应序列；

• 为了找到子问题与原问题的关系，就需要想办法将arr2映射为arr1，我们可以将arr2的每个元素减去(n-t)再对n求模，即(x-(n-t))/n=(x+t)/n，等价于将arr2的每个元素加上t然后对n取模；

• 所以就有递推式：f(n,m)=(f(n-1,m)+t)%n=(f(n-1,m)+m)%n；

• 通过该递推式即可求出f(n,m)

3.解题代码

Python代码

class Solution:
    def iceBreakingGame(self, num: int, target: int) -> int:
        # 思路：递推式f(n,m)=(f(n-1,m)+m)%n
        f = 0
        for i in range(2, num + 1):
            f = (f + target) % i
        return f

4.执行结果