categories: [Blog,Algorithm]

剑指 Offer 62. 圆圈中最后剩下的数字

难度简单300
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.      public int lastRemaining1(int n, int m) {
  2.         ArrayList<Integer> list = new ArrayList<>(n);
  3.         for (int i = 0; i < n; i++) {
  4.             list.add(i);
  5.         }
  6.         int idx = 0;
  7.         while (n > 1) {
  8.             idx = (idx + m - 1) % n;
  9.             list.remove(idx);
  10.             n--;
  11.         }
  12.         return list.get(0);
  14. // 作者：sweetieeyi
  15. // 链接：https://leetcode-cn.com/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof/solution/javajie-jue-yue-se-fu-huan-wen-ti-gao-su-ni-wei-sh/
  16.     }

假设当前删除的位置是 idx，下一个删除的数字的位置是 idx+m 。但是，由于把当前位置的数字删除了，后面的数字会前移一位，所以实际的下一个位置是 idx+m−1。由于数到末尾会从头继续数，所以最后取模一下，就是
(idx+m−1)(mod n)。

作者：sweetieeyi
链接：https://leetcode-cn.com/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof/solution/javajie-jue-yue-se-fu-huan-wen-ti-gao-su-ni-wei-sh/

动态规划

  1.     public int lastRemaining1(int n, int m) {
  2.         int[] ans = new int[n+1];
  3.         ans[0] = 0;
  4.         // 最后一轮剩下2个人，所以从2开始反推
  5.         for (int i = 1; i <= n; i++) {
  6.             ans[i] = (ans[i-1] + m) % i;
  7.         }
  8.         return ans[n];
  9.     }
  11.     public int lastRemaining(int n, int m) {
  12.         int[] ans = new int[n+1];
  13.         ans[1] = 0;
  14.         // 最后一轮剩下2个人，所以从2开始反推
  15.         for (int i = 2; i <= n; i++) {
  16.             ans[i] = (ans[i-1] + m) % i;
  17.         }
  18.         return ans[n];
  19.     }

动态规划解析：

状态定义： 设「i,m 问题」的解为 dp[i] ；
状态转移方程： 通过以下公式可从 dp[i−1] 递推得到 dp[i] ；dp[i]=(dp[i−1]+m)%i；

初始状态：「1,m 问题」的解恒为 0 ，即 dp[1]=0 ；
返回值： 返回「n,m 问题」的解 dp[n] ；

作者：jyd
链接：https://leetcode-cn.com/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof/solution/jian-zhi-offer-62-yuan-quan-zhong-zui-ho-dcow/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

动态规划优化版

  1.     public int lastRemaining(int n, int m) {
  2.         int ans = 0;
  3.         // 最后一轮剩下2个人，所以从2开始反推
  4.         for (int i = 2; i <= n; i++) {
  5.             ans = (ans + m) % i;
  6.         }
  7.         return ans;
  8.     }
  10. // 作者：sweetieeyi
  11. // 链接：https://leetcode-cn.com/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof/solution/javajie-jue-yue-se-fu-huan-wen-ti-gao-su-ni-wei-sh/