难度: Easy
社团共有 num 位成员参与破冰游戏，编号为 0 ~ num-1。成员们按照编号顺序围绕圆桌而坐。社长抽取一个数字 target，从 0 号成员起开始计数，排在第 target 位的成员离开圆桌，且成员离开后从下一个成员开始计数。请返回游戏结束时最后一位成员的编号。
示例 1：
输入：num = 7, target = 4 输出：1
示例 2：
输入：num = 12, target = 5 输出：0
提示：
1 <= num <= 10^51 <= target <= 10^6运行时间: 2168 ms
内存: 18.1 MB
class Solution:
def lastRemaining(self, n: int, m: int) -> int:
__import__('sys').setrecursionlimit(100000)
if n == 1:
return 0
return (m + self.lastRemaining(n-1,m)) % n
该题解使用了经典的约瑟夫环问题的递归解法。在约瑟夫环问题中，我们要从n个人中每次计数到m，然后移除那个人，直到只剩下一个人。这个题解的递归思想基于这样一个观察：如果我们知道了n-1个人时的解（即最后存活的人的序号），我们可以推导出n个人时的解。具体来说，当我们从n个人中移除了一个人后，新问题就变成了一个n-1人的约瑟夫环问题，但是由于移除的位置影响了编号，我们需要将解调整回原来的编号范围。这可以通过将n-1人时的解加上m（步长），再对n取模来实现。递归终止条件是当只剩一个人时，其编号显然是0。
时间复杂度: O(n)
空间复杂度: O(n)
class Solution:
def lastRemaining(self, n: int, m: int) -> int:
__import__('sys').setrecursionlimit(100000) # 提高Python的默认递归深度限制
if n == 1:
return 0 # 递归基，当只有一个人时，返回编号0
return (m + self.lastRemaining(n-1, m)) % n # 递归关系：当前n的解可以通过n-1的解推导
这个递归终止条件是基于约瑟夫环问题的定义。当圆桌上只剩下一个人时，这个人的编号自然是0，因为他是唯一的存活者，不存在被移除的可能性。这种情况下，问题已经简化到最基本的情景，即只有一个人时，他是最后的胜利者，因此返回他的编号0。
在约瑟夫环问题中，每次从圆桌移除一个人后，计数将从被移除人的下一个人开始。因此，当从n个人中移除一个人后，问题转化为一个新的约瑟夫环问题，但这次是n-1个人。如果我们知道在n-1人的情形中最后剩下的人的编号是`self.lastRemaining(n-1, m)`，则在原来的n个人的圆桌中，这个人的位置相对于被移除的人的位置偏移了m位。因此，为了得到在原始n人圈中的位置，我们需要将这个偏移量加到n-1人圈中最后剩下的人的编号上，并通过取余n来确保编号不会超出范围。这样可以正确地将n-1人问题的解调整到n人问题的环境中。
在实际应用中，虽然提高递归深度限制可以解决一些问题，但这并不总是安全的。递归深度过深可能导致程序崩溃或者系统资源耗尽，尤其是在处理非常大的输入数据时。在工业级应用或需要处理大数据的情况下，更推荐使用迭代方法或其他非递归技术来避免栈溢出的风险。例如，可以通过使用循环和数据结构（如链表）来模拟递归过程，从而避免递归带来的栈空间问题。