问题描述

LeetCode LCR 187. 破冰游戏 (opens in a new tab)，难度简单。

社团共有 num 位成员参与破冰游戏，编号为 0 ~ num-1。成员们按照编号顺序围绕圆桌而坐。社长抽取一个数字 target，从 0 号成员起开始计数，排在第 target 位的成员离开圆桌，且成员离开后从下一个成员开始计数。请返回游戏结束时最后一位成员的编号。

示例 1

输入：num = 7, target = 4
输出：1

示例 2

输入：num = 12, target = 5
输出：0

提示：

• 1 <= num <= 10^5
• 1 <= target <= 10^6

牛客网 约瑟夫环 (opens in a new tab)，难度中等。

n个人（0,1,2,3,4...n-1），围成一圈，从编号为k的人开始报数，报数报到m的人出队（报数是1,2,...m这样报的）。下次从出队的人之后开始重新报数，循环往复，当队伍中只剩最后一个人的时候，那个人就是大王。现在给定n，k，m，请你求出大王的编号。

输入描述

输入一行包含三个整数n,k,m

$1 \leq n \leq, 1 \leq k \leq n - 1, 1 \leq m \leq 100$

输出描述

输出一个整数

示例 1

输入：5 1 2
输出：3

题解

数学

参考帖子 (opens in a new tab)

class Solution {
    public int iceBreakingGame(int num, int target) {
        int winner = 0;
        for (int i = 2; i <= num; i++) {
            winner = (winner + target) % i;
        }
        return winner;
    }
}

数学 + 递归

从编号 0 开始计数，公式如下：

$J(n,k) = \begin{cases} 0 & \text{if } n = 1 \\ (J(n-1, k) + k) \mod n & \text{if } n > 1 \end{cases}$

从编号 1 开始计数，公式如下：

$J(n,k) = \begin{cases} 1 & \text{if } n = 1 \\ ((J(n-1, k) + k - 1) \mod n) + 1 & \text{if } n > 1 \end{cases}$

class Solution {
    public int iceBreakingGame(int num, int target) {
        if (num == 1) 
            return 0;
        else
            return (iceBreakingGame(num - 1, target) + target) % num;
    }
}

模拟链表

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

class Solution {
    public int iceBreakingGame(int num, int target) {
        List<Integer> nums = new ArrayList<>();
        for (int i = 0; i < num; ++i) {
            nums.add(i);
        }
        int index = 0;
        while (num > 1) {
            index = (index - 1 + target) % num;
            nums.remove(index);
            num--;
        }
        return nums.get(0);
    }
}