LeetCode 题解工作台
找出转圈游戏输家
n 个朋友在玩游戏。这些朋友坐成一个圈，按 顺时针方向 从 1 到 n 编号。准确的说，从第 i 个朋友的位置开始顺时针移动 1 步会到达第 (i + 1) 个朋友的位置（ 1 ），而从第 n 个朋友的位置开始顺时针移动 1 步会回到第 1 个朋友的位置。 游戏规则如下： 第 1 个朋友接球。 接着…
3
题型
6
代码语言
3
相关题
当前训练重点
简单 · 数组·哈希·扫描
答案摘要
我们用一个数组 `vis` 记录每个朋友是否接到过球，初始时所有朋友都没有接到过球。然后我们按照题目描述的规则模拟游戏的过程，直到某个朋友第二次接到球为止。 在模拟过程中，我们用两个变量 和 分别表示当前持球的朋友编号和当前传球的步长。初始时 ，表示第一个朋友接到球。每次传球时，我们将 更新为 $(i+p \times k) \bmod n$，表示下一个接球的朋友编号，然后将 更新为 ，表…
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
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
解题思路
方法一：模拟
我们用一个数组 vis 记录每个朋友是否接到过球，初始时所有朋友都没有接到过球。然后我们按照题目描述的规则模拟游戏的过程，直到某个朋友第二次接到球为止。
在模拟过程中，我们用两个变量 和 分别表示当前持球的朋友编号和当前传球的步长。初始时 ，表示第一个朋友接到球。每次传球时，我们将 更新为 ，表示下一个接球的朋友编号，然后将 更新为 ，表示下一次传球的步长。当某个朋友第二次接到球时，游戏结束。
最后我们遍历数组 vis，将没有接到过球的朋友编号加入答案数组中即可。
时间复杂度 ，空间复杂度 。其中 是朋友的数量。
class Solution:
def circularGameLosers(self, n: int, k: int) -> List[int]:
vis = [False] * n
i, p = 0, 1
while not vis[i]:
vis[i] = True
i = (i + p * k) % n
p += 1
return [i + 1 for i in range(n) if not vis[i]]
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n) since each friend is visited at most once during simulation. Space complexity is O(n) due to the set storing which friends received the ball. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Emphasize simulation over mathematical shortcuts.
- question_mark
Check that modulo arithmetic correctly wraps around the circle.
- question_mark
Ensure the set correctly detects repeated ball receipt.
常见陷阱
外企场景- error
Forgetting to wrap around using modulo can cause index errors.
- error
Adding a friend to the losers list who actually received the ball.
- error
Incorrectly stopping the simulation before a friend receives the ball twice.
进阶变体
外企场景- arrow_right_alt
Change k dynamically on each pass to increase simulation complexity.
- arrow_right_alt
Return the order in which losers would have received the ball if the game continued.
- arrow_right_alt
Simulate the game with multiple balls passed simultaneously.