剑指 Offer 62. 圆圈中最后剩下的数字
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
来源：力扣（LeetCode）
链接：力扣
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
一解
-
旧编号从第一位开始数
-
新编号，删除 m 后，从 m+1 开始数
两者编号关系为：
-
0, 1,2,…,m, m+1…
-
-m, 1-m, 2-m,…,m,0…
旧编号 = 新编号 + m
可通过递归层层求解旧编号：
class Solution:
def lastRemaining(self, n: int, m: int) -> int:
if n == 1: return 0
# 旧编号 = (新编号 + m)n
return (self.lastRemaining(n - 1, m) + m) % n
二解
与一解思路类似，使用动态规划替换递归：
class Solution:
def lastRemaining(self, n: int, m: int) -> int:
res = 0
for i in range(2, n+1):
res = (res + m) % i
return res