LeetCode每日一题——2682. 找出转圈游戏输家-Toy模板网

这篇具有很好参考价值的文章主要介绍了LeetCode每日一题——2682. 找出转圈游戏输家。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

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：

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

示例 2：

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

提示：

1 <= k <= n <= 50

这个题目其实直接模拟游戏过程即可。主要可能每一次跳的 k * i需要关注下，并且还需要进行取余操作。

思路：

记录起始位置start，每一次的跳跃步长 step * k，其中step是第几次跳。然后记录遍历过的玩家数量cnt，用于后面答案数组的初始化长度 n - cnt，vis标记为是否遍历过的玩家。

ac code：文章来源地址https://www.toymoban.com/news/detail-652464.html

class Solution {
    public int[] circularGameLosers(int n, int k) {
        boolean[] vis = new boolean[n+1];
        int start = 1;
        int step = 0;
        int cnt = 0;
        while (!vis[(start + step * k) % n]) {
            vis[(start + step * k) % n] = true;
            start = start + step * k;
            step += 1;
            cnt += 1;
        }
        int[] ans = new int[n - cnt];
        int index = 0;
        for (int i=1;i<=n;i++) {
            if (!vis[i % n]) {
                ans[index++] = i;
            }
        }
        return ans;
    }
}

到了这里，关于LeetCode每日一题——2682. 找出转圈游戏输家的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！