圆圈中最后剩下的数字

题目：

0,1,···,n-1 这 n 个数字排成一个圆圈，从数字 0 开始，每次从这个圆圈里删除第 m 个数字（删除后从下一个数字开始计数）。求出这个圆圈里剩下的最后一个数字。

例如，0、1、2、3、4 这 5 个数字组成一个圆圈，从数字 0 开始每次删除第 3 个数字，则删除的前 4 个数字依次是 2、0、4、1，因此最后剩下的数字是 3。

示例

输入: n = 5, m = 3
输出: 3

输入: n = 10, m = 17
输出: 2

思考：

提示

• 本题为著名的 "约瑟夫环" 问题：

• n 个数字，每次删除第 m 个，用已知解求未知解，可以使用动态规划

• 第一次删除：删除第 m 个，则删除索引为 m-1 的数，但因为 m 可能大于 n，所以删除 (m - 1) % n 索引的数

• 第二次删除：从下一个元素开始，即索引 m % n 的数开始，删除索引为 (m % n + m - 1) % n 的数

• 已知当只有一个元素时，留下的就是他，所以初始值 dp[1] = 0

题解：

class Solution {
    public int lastRemaining(int n, int m) {
        //dp[1] = 0
        int x = 0;

        for (int i = 2; i <= n; i++) {
            x = (x + m) % i;
        }
        //dp[n]
        return x;
    }
}

附：模拟链表做法，效率较低

class Solution {
    public int lastRemaining(int n, int m) {
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < n; i++) list.add(i);

        int cur = 0;
        while (list.size() > 1) {
            cur = (cur + m - 1) % list.size();
            list.remove(cur);
        }
        return list.get(0);
    }
}