3222. 求出硬币游戏的赢家

题目描述

给你两个正整数 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

解法

方法一：数学

由于每一轮的操作，会消耗 $2$ 枚价值为 $75$ 的硬币和 $8$ 枚价值为 $10$ 的硬币，因此，我们可以计算得到操作的轮数 $k = \min(x / 2, y / 8)$，然后更新 $x$ 和 $y$ 的值，此时 $x$ 和 $y$ 就是经过 $k$ 轮操作后剩余的硬币数目。

如果 $x > 0$ 且 $y \geq 4$，那么 Alice 还可以继续操作，此时 Bob 就输了，返回 "Alice"；否则，返回 "Bob"。

时间复杂度 $O(1)$，空间复杂度 $O(1)$。

Python3JavaC++GoTypeScript

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"

class Solution {
    public String losingPlayer(int x, int y) {
        int k = Math.min(x / 2, y / 8);
        x -= k * 2;
        y -= k * 8;
        return x > 0 && y >= 4 ? "Alice" : "Bob";
    }
}

class Solution {
public:
    string losingPlayer(int x, int y) {
        int k = min(x / 2, y / 8);
        x -= k * 2;
        y -= k * 8;
        return x && y >= 4 ? "Alice" : "Bob";
    }
};

func losingPlayer(x int, y int) string {
    k := min(x/2, y/8)
    x -= 2 * k
    y -= 8 * k
    if x > 0 && y >= 4 {
        return "Alice"
    }
    return "Bob"
}

function losingPlayer(x: number, y: number): string {
    const k = Math.min((x / 2) | 0, (y / 8) | 0);
    x -= k * 2;
    y -= k * 8;
    return x && y >= 4 ? 'Alice' : 'Bob';
}

3222. 求出硬币游戏的赢家

题目描述

解法

方法一：数学

评论