Shepherd's Blog

2682. 找出转圈游戏输家

https://leetcode.cn/problems/find-the-losers-of-the-circular-game/

n 个朋友在玩游戏。这些朋友坐成一个圈，按 顺时针方向 从 1 到 n 编号。从第 i 个朋友的位置开始顺时针移动 1 步会到达第 (i + 1) 个朋友的位置（1 <= i < n），而从第 n 个朋友的位置开始顺时针移动 1 步会回到第 1 个朋友的位置。

游戏规则如下：

第 1 个朋友接球。

  • 接着，第 1 个朋友将球传给距离他顺时针方向 k 步的朋友。
  • 然后，接球的朋友应该把球传给距离他顺时针方向 2 * k 步的朋友。
  • 接着，接球的朋友应该把球传给距离他顺时针方向 3 * k 步的朋友，以此类推。

换句话说，在第 i 轮中持有球的那位朋友需要将球传递给距离他顺时针方向 i * k 步的朋友。

当某个朋友第 2 次接到球时，游戏结束。

在整场游戏中没有接到过球的朋友是 输家 。

给你参与游戏的朋友数量 n 和一个整数 k ，请按升序排列返回包含所有输家编号的数组 answer 作为答案。

示例 1：

1
2
3
4
5
6
7
>输入：n = 5, k = 2
输出：[4,5]
解释：以下为游戏进行情况：
1）第 1 个朋友接球，第 1 个朋友将球传给距离他顺时针方向 2 步的玩家 —— 第 3 个朋友。
2）第 3 个朋友将球传给距离他顺时针方向 4 步的玩家 —— 第 2 个朋友。
3）第 2 个朋友将球传给距离他顺时针方向 6 步的玩家 —— 第 3 个朋友。
4）第 3 个朋友接到两次球，游戏结束。

示例 2：

1
2
3
4
5
输入：n = 4, k = 4
输出：[2,3,4]
解释：以下为游戏进行情况：
1）第 1 个朋友接球，第 1 个朋友将球传给距离他顺时针方向 4 步的玩家 —— 第 1 个朋友。
2）第 1 个朋友接到两次球，游戏结束。

提示：

  • 1 <= k <= n <= 50

题目描述的很复杂，其实就是 n 个人围成一圈，从第一个人开始传球，第 i 次传球的距离为 i * k ，有人第二次接到球时游戏停止。

我们可以定义一个哈希表用来存储是否接到过球，由于游戏是从 1 开始，所以循环取余的时候需要注意边界值，这样做有些麻烦。我们可以直接将所有人的位置号 -1 从 0 开始计数，在最后统计时 +1 即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int[] circularGameLosers(int n, int k) {
        int[] hash = new int[n];
        // 当前球在谁的手里
        int cur = 0;
        // 第几次传球
        int stage = 1;
        while (hash[cur] == 0) {
            hash[cur] = 1;
            cur = (cur + stage * k) % n;
            stage ++;
        }
        // 剩余的人是总人数 - 玩了几次传球
        // 因为有人传到两次，所以 -1
        int[] res = new int[n - stage + 1];
        for (int i = 0, j = 0; i < n; i ++) {
            if (hash[i] == 0) {
                res[j ++] = i + 1;
            }
        }
        return res;
    }
}
0%