LeetCode 题解工作台
求出硬币游戏的赢家
给你两个 正 整数 x 和 y ，分别表示价值为 75 和 10 的硬币的数目。 Alice 和 Bob 正在玩一个游戏。每一轮中，Alice 先进行操作，Bob 后操作。每次操作中，玩家需要拿走价值 总和 为 115 的硬币。如果一名玩家无法执行此操作，那么这名玩家 输掉 游戏。 两名玩家都采取 …
3
题型
5
代码语言
3
相关题
当前训练重点
简单 · 数学·结合·模拟
答案摘要
由于每一轮的操作，会消耗 枚价值为 的硬币和 枚价值为 的硬币，因此，我们可以计算得到操作的轮数 $k = \min(x / 2, y / 8)$，然后更新 和 的值，此时 和 就是经过 轮操作后剩余的硬币数目。 如果 $x > 0$ 且 $y \geq 4$，那么 Alice 还可以继续操作，此时 Bob 就输了，返回 "Alice"；否则，返回 "Bob"。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数学·结合·模拟 题型思路
题目描述
给你两个 正 整数 x 和 y ，分别表示价值为 75 和 10 的硬币的数目。
Alice 和 Bob 正在玩一个游戏。每一轮中，Alice 先进行操作，Bob 后操作。每次操作中，玩家需要拿走价值 总和 为 115 的硬币。如果一名玩家无法执行此操作，那么这名玩家 输掉 游戏。
两名玩家都采取 最优 策略，请你返回游戏的赢家。
示例 1：
输入：x = 2, y = 7
输出："Alice"
解释：
游戏一次操作后结束：
- Alice 拿走 1 枚价值为 75 的硬币和 4 枚价值为 10 的硬币。
示例 2：
输入：x = 4, y = 11
输出："Bob"
解释：
游戏 2 次操作后结束：
- Alice 拿走 1 枚价值为 75 的硬币和 4 枚价值为 10 的硬币。
- Bob 拿走 1 枚价值为 75 的硬币和 4 枚价值为 10 的硬币。
提示：
1 <= x, y <= 100
解题思路
方法一：数学
由于每一轮的操作，会消耗 枚价值为 的硬币和 枚价值为 的硬币，因此，我们可以计算得到操作的轮数 ，然后更新 和 的值，此时 和 就是经过 轮操作后剩余的硬币数目。
如果 且 ，那么 Alice 还可以继续操作，此时 Bob 就输了，返回 "Alice"；否则，返回 "Bob"。
时间复杂度 ，空间复杂度 。
class Solution:
def losingPlayer(self, x: int, y: int) -> str:
k = min(x // 2, y // 8)
x -= k * 2
y -= k * 8
return "Alice" if x and y >= 4 else "Bob"
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Look for the candidate's ability to identify the constraints and break the problem into simpler steps like coin usage and turn simulation.
- question_mark
The candidate should be able to recognize the need for simulating the game turn by turn and handling coin depletion correctly.
- question_mark
Check if the candidate optimizes the solution by reducing unnecessary operations and understanding the constraints.
常见陷阱
外企场景- error
Failing to account for the exact coin combination needed to make 115, leading to incorrect assumptions about game moves.
- error
Not simulating each turn properly or missing conditions where a player cannot make a valid move.
- error
Overcomplicating the solution by introducing unnecessary complexity rather than focusing on the simple simulation of each turn.
进阶变体
外企场景- arrow_right_alt
What if the coin values change but the sum remains 115?
- arrow_right_alt
How would the game change if players could take any number of coins per turn instead of just one 75-coin and four 10-coins?
- arrow_right_alt
What if players start with a different number of coins but still must form 115 in each turn?