3222. 求出硬币游戏的赢家
题目描述¶
关联：https://leetcode.cn/problems/find-the-winning-player-in-coin-game/description/
题目描述
给你两个 正 整数 x 和 y ，分别表示价值为 75 和 10 的硬币的数目。
Alice 和 Bob 正在玩一个游戏。每一轮中，Alice 先进行操作，Bob 后操作。每次操作中，玩家需要拿出价值 总和 为 115 的硬币。如果一名玩家无法执行此操作，那么这名玩家 输掉 游戏。
两名玩家都采取 最优 策略，请你返回游戏的赢家。
本题的范围是 \(1 \leq x, y \leq 100\)。
解题思路¶
所谓的 最优 策略，其实是唯一策略，即 如果能一次拿取 1 个 75 的硬币和 4 个 10 的硬币，那么就拿取。
以下两种情况下均会输掉比赛：
- 没有 75 的硬币了（因为只靠 10 无法凑齐 115）
- 10 的硬币不足 4 个（无论有没有 75 的硬币，都不可能凑齐 115）
在策略唯一的情况下，大家都只能以 1:4 的比例拿取硬币。因此只需要按这个比例推算哪个硬币先被拿完，然后返回最后一次拿取的人，即为赢家。
根据硬币的比例不同，可分为以下几种情况：
- \(C_{75} \times 4 < C_{10}\)：75 元的先被拿完
- \(C_{75} \times 4 > C_{10}\)：10 元的先被拿完
- \(C_{75} \times 4 = C_{10}\)：10 元和 75 元的被同时拿完，这种情况可以包含进上述两种情况中的任一个
边缘情况是 Alice 第一回合就拿不出手：
- \(C_{10} < 4\) ：Alice 输
如果已经可以确定哪一种硬币先被拿完，那么根据对应硬币数量的奇偶性，可以确定最后一次拿取的人。
完整题解¶
class Solution:
def losingPlayer(self, x: int, y: int) -> str:
if y < 4:
return 'Bob'
turns_with_75 = x
turns_with_10 = y // 4
min_turns = min(turns_with_75, turns_with_10)
if min_turns % 2 == 0:
return 'Bob'
else:
return 'Alice'
复杂度分析¶
连个 for 都没有，时间复杂度为 \(O(1)\)。
空间复杂度 \(O(1)\)。