Easy

题目描述

给你两个正整数 x 和 y，分别表示价值为 75 和 10 的硬币数量。

Alice 和 Bob 正在玩一个游戏。每一轮中，从 Alice 开始，玩家必须拿取总价值为 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

提示：

  • 凑成 115 的唯一方法是使用 1 个价值 75 的硬币和 4 个价值 10 的硬币。每一轮都会消耗这么多硬币。
  • 因此轮数为 min(x, y / 4)。
  • 根据轮数的奇偶性确定获胜者。

解题思路

这是一个数学游戏问题。通过分析题目我们可以发现：

  1. 游戏规则分析：每轮玩家必须拿取总价值 115 的硬币。由于只有价值 75 和 10 的硬币，唯一的组合方式是：1 个价值 75 的硬币 + 4 个价值 10 的硬币。

  2. 游戏轮数计算：每轮需要消耗 1 个价值 75 的硬币和 4 个价值 10 的硬币。因此游戏最多能进行 min(x, y // 4) 轮，其中 x 是价值 75 硬币的数量，y // 4 是价值 10 硬币能支持的轮数。

  3. 获胜者判断：由于 Alice 先手，如果总轮数为奇数，Alice 获胜；如果总轮数为偶数，Bob 获胜。

  4. 边界情况：如果计算出的轮数为 0，说明无法进行任何一轮游戏，此时 Alice 无法完成第一轮，Bob 获胜。

这个解法的核心是理解游戏的数学本质：每轮的消耗是固定的，问题转化为计算能进行多少轮，再根据轮数奇偶性判断获胜者。

代码实现

class Solution {
public:
    string winningPlayer(int x, int y) {
        int turns = min(x, y / 4);
        return turns % 2 == 1 ? "Alice" : "Bob";
    }
};

class Solution:
    def winningPlayer(self, x: int, y: int) -> str:
        turns = min(x, y // 4)
        return "Alice" if turns % 2 == 1 else "Bob"

public class Solution {
    public string WinningPlayer(int x, int y) {
        int turns = Math.Min(x, y / 4);
        return turns % 2 == 1 ? "Alice" : "Bob";
    }
}

/**
 * @param {number} x
 * @param {number} y
 * @return {string}
 */
var winningPlayer = function(x, y) {
    const turns = Math.min(x, Math.floor(y / 4));
    return turns % 2 === 1 ? "Alice" : "Bob";
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(1)只需要进行常数次数学运算
空间复杂度O(1)只使用常数额外空间

相关题目