leetcode 链接：圆圈中最后剩下的数字

题目

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
  2. 输出: 3
输入: n = 10, m = 17
输出: 2

解答 & 代码

参考：剑指 Offer 62. 圆圈中最后剩下的数字（数学 / 动态规划，清晰图解）

动态规划：

  • 设置数组 dp，dp[n] 代表从 n 个数字中每次删除第 m 个数字，最后剩下的一个数字的下标
  • 状态转移方程：dp[n] = (dp[n-1] + m) % n
    • 对于 n 个数字，最先删除下标为 m%n - 1 的元素，剩下 n - 1 个元素，再准备删除下一个元素，此时从第 m%n 个元素开始找第 m 个元素，也就是说，此时下标顺序：m%n, m%n+1,..., 0, 1, ..., m%n-2
    • 而 dp[n-1] 问题下标顺序：0, 1, 2, ..., n-2
    • 因此，dp[n] = (dp[n-1] + m % n) % n = (dp[n-1] + m) % n
  • 初始化：dp[1] = 0

优化：滚动数组

  • 因为 dp[n] 只和上一状态 dp[n-1] 有关，因此不需要使用额外数组，使用一个变量 idx 存储上一状态的值即可
    class Solution {
public:
  int lastRemaining(int n, int m) {
      int idx = 0;
      for(int i = 2; i <= n; ++i)
          idx = (idx + m) % i;
      return idx;
  }
};
    执行结果： ``` 执行结果：通过

执行用时：4 ms, 在所有 C++ 提交中击败了 99.77% 的用户 内存消耗：5.8 MB, 在所有 C++ 提交中击败了 81.32% 的用户 ```