17、剑指 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^51 <= m <= 10^6
二、解法
2.1、动态规划
核心思路
设 dp[n,m] 表示在 n 个数字序列（0~n-1）中不断删除第 m 个数字后，最后剩下那一个数。
假设 n=5，m=3，则 dp[5,3] 的初始化数组是：
0 1 2 3 4
若 n=4，m=3，则 dp[5-1,3] 也就是 dp[4,3] 的初始化数组是：
0 1 2 3
从初始化数组可以看出，dp[5,3] 和 dp[4,3] 最终的结果是不一样的。而 dp[5,3] 删掉一个数字后的数组应该是：
3 4 0 1
这个数组咱们给他取名为 dp’[4,3]，它是不是跟 dp[4,3] 有一些联系呢？咱们把他俩的初始数组放在一起比较：
dp[4,3]：0 1 2 3
dp’[4,3]：3 4 0 1
从上面可能还是看不出具体区别，因此我们来看 dp[n-1,m] 和 dp’[n-1,m]的初始数组区别：
| dp[n-1,m] | 0 | 1 | … | n-1-m | n-m | … | n-3 | n-2 |
|---|---|---|---|---|---|---|---|---|
| dp’[n-1,m] | m | m+1 | … | n-1 | 0 | … | m-3 | m-2 |
观察上面的表格，我们发现 dp[n-1,m] 和 dp’[n-1,m] 的初始数组有如下规律：
dp'[n-1,m] = ( dp[n-1,m] + m ) % n
因为 dp[n,m] = dp’[n-1,m]，所以咱们就找出了 dp[n,m] 到 dp[n-1,m] 之间的映射关系，也就是：
dp[n,m] = ( dp[n−1,m] + m ) % n
考虑边界条件，n 肯定是要大于1的；此外当 n=1 时，就只剩下一个数了，那就是 0。因此得出状态转移方程为：
dp[n,m]=0, n=1
dp[n,m] = ( dp[n−1,m] + m ) % n, 1<n
观察状态转移方程式，发现 m 是不变的而且 dp[n,m] 只跟 dp[n-1,m] 有关，因此可以直接使用一个变量来代替 dp[n,m]，然后从下往上递推实现。
另外，因为 dp[5,3] 的初始数组是 0 1 2 3 4，值与下标相同，即上述规律适用于数组下标。
复杂度分析
时间复杂度：O(n)
空间复杂度：O(1)
Code
class Solution {
public int lastRemaining(int n, int m) {
int answer = 0;
for (int i = 2; i <= n; i++) {
answer = (answer + m) % i;
}
return answer;
}
}