LeetCode 题解工作台
移除石头游戏
Alice 和 Bob 在玩一个游戏，他们俩轮流从一堆石头中移除石头，Alice 先进行操作。 Alice 在第一次操作中移除 恰好 10 个石头。 接下来的每次操作中，每位玩家移除的石头数 恰好 为另一位玩家上一次操作的石头数减 1 。 第一位没法进行操作的玩家输掉这个游戏。 给你一个正整数 n …
2
题型
5
代码语言
3
相关题
当前训练重点
简单 · 数学·结合·模拟
答案摘要
我们根据题意模拟游戏的过程，直到无法继续游戏为止。 具体地，我们维护两个变量 和 ，分别表示当前可以移除的石头数和已经进行的操作次数。初始时 $x = 10$, $k = 0$。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数学·结合·模拟 题型思路
题目描述
Alice 和 Bob 在玩一个游戏，他们俩轮流从一堆石头中移除石头，Alice 先进行操作。
- Alice 在第一次操作中移除 恰好 10 个石头。
- 接下来的每次操作中，每位玩家移除的石头数 恰好 为另一位玩家上一次操作的石头数减 1 。
第一位没法进行操作的玩家输掉这个游戏。
给你一个正整数 n 表示一开始石头的数目，如果 Alice 赢下这个游戏，请你返回 true ，否则返回 false 。
示例 1：
输入：n = 12
输出：true
解释：
- Alice 第一次操作中移除 10 个石头，剩下 2 个石头给 Bob 。
- Bob 无法移除 9 个石头，所以 Alice 赢下游戏。
示例 2：
输入：n = 1
输出：false
解释：
- Alice 无法移除 10 个石头，所以 Alice 输掉游戏。
提示：
1 <= n <= 50
解题思路
方法一：模拟
我们根据题意模拟游戏的过程，直到无法继续游戏为止。
具体地，我们维护两个变量 和 ，分别表示当前可以移除的石头数和已经进行的操作次数。初始时 , 。
在每一轮操作中，如果当前可以移除的石头数 不超过剩余的石头数 ，那么我们移除 个石头，并将 减小 ，然后将 增加 。否则，我们无法进行操作，游戏结束。
最后，我们判断 的奇偶性，如果 是奇数，那么 Alice 赢得了游戏，否则 Bob 赢得了游戏。
时间复杂度 。其中 是石头的数目。空间复杂度 。
class Solution:
def canAliceWin(self, n: int) -> bool:
x, k = 10, 0
while n >= x:
n -= x
x -= 1
k += 1
return k % 2 == 1
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Ability to simulate game mechanics
- question_mark
Understanding of memoization for optimization
- question_mark
Recognizing patterns in game theory
常见陷阱
外企场景- error
Overcomplicating the solution
- error
Neglecting to simulate the game properly
- error
Not recognizing simple patterns in the game mechanics
进阶变体
外企场景- arrow_right_alt
Allow different removal rules or turn patterns
- arrow_right_alt
Increase the upper limit of n
- arrow_right_alt
Change the starting player