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

lastRemaining(n - 1, m) 是 n - 1 个数，即 0, 1, …, n - 2，从数字 0 开始，每次从这个圆圈里删除第 m 个数字（删除后从下一个数字开始计数）。和真实的序列 m, m + 1, …, n - 2, 0, …, m - 2 做一个影射。x -> (m + x) % n。

方法一：递归

class Solution:
    # Python 默认的递归深度不够，需要手动设置
    sys.setrecursionlimit(100000)

    def lastRemaining(self, n: int, m: int) -> int:        
        if n == 0: return 0
        x = self.lastRemaining(n - 1, m)
        return (m + x) % n

class Solution {
    
    public int lastRemaining(int n, int m) {
    
        if(n == 1) return 0;
        int index = lastRemaining(n - 1, m); // x 是按 0, 1, 2 ... n - 2 计算的结果
        return (index + m) % n; // 和实际的作一个影射
    }
}

方法二：迭代

规律：每一轮删掉第 m 个数都是将前 m - 1 个数移到数组末尾以供循环，每次 i 相当于左移了 m 个位置。
追本溯源：从最后一次 index 为 0 开始溯源，依次让 index 处的 i 右移 m 个位置，即加上 m。
倒序每一次 index + m 就能找到上一轮那个 i 所在的 index，同时防止越界要取余该轮数组 size

class Solution {
    
    public int lastRemaining(int n, int m) {
    
        int index = 0; // 从最后剩下的一个数反推，最后得到 0, 1, ... , n - 1 中的索引。
        for (int i = 2; i <= n; ++i) {
    
            index = (m + index) % i;
        }
        return index;
    }
}

方法三：模拟法，用 ArrayList 模拟：时间复杂度 O(n^2)

class Solution {
    
    public int lastRemaining(int n, int m) {
    
        List<Integer> list = new ArrayList<>(); // LinkedList 超时
        for (int i = 0; i < n; i++) {
     list.add(i);}
        int index = 0;        
        while (n > 1) {
    
            index = (index + m - 1) % n;
            list.remove(index);
            n--;
        }
        return list.get(0);
    }
}

1823. 找出游戏的获胜者

方法一：递归

class Solution {
    
    public int findTheWinner(int n, int k) {
    
        if(n == 1) return 1;
        int x = findTheWinner(n - 1, k); // x 转换成索引
        return (k + x - 1) % n + 1;
    }
}

方法二：迭代

class Solution {
    
    public int findTheWinner(int n, int k) {
    
        int winner = 1;
        for (int i = 2; i <= n; i++) {
    
            winner = (k + winner - 1) % i + 1;
        }
        return winner;
    }
}

方法三：队列模拟

class Solution {
    
    public int findTheWinner(int n, int k) {
    
        Deque<Integer> q = new ArrayDeque<>();
        for(int i = 1; i <= n; i++) q.add(i);
        while(q.size() > 1){
    
            for(int i = 0; i < k - 1; i++){
    
                q.offer(q.pop());
            }
            q.pop();
        }
        return q.peek();
    }
}