LeetCode 3222.求出硬币游戏的赢家：伪博弈真思维O(1)

【LetMeFly】3222.求出硬币游戏的赢家：伪博弈真思维O(1)

力扣题目链接：https://leetcode.cn/problems/find-the-winning-player-in-coin-game/

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

Alice 和 Bob 正在玩一个游戏。每一轮中，Alice 先进行操作，Bob 后操作。每次操作中，玩家需要拿出价值 总和 为 115 的硬币。如果一名玩家无法执行此操作，那么这名玩家 输掉 游戏。

两名玩家都采取 最优 策略，请你返回游戏的赢家。

 

示例 1：

输出："Alice"

解释：

游戏一次操作后结束：

• Alice 拿走 1 枚价值为 75 的硬币和 4 枚价值为 10 的硬币。

示例 2：

输出："Bob"

解释：

游戏 2 次操作后结束：

• Alice 拿走 1 枚价值为 75 的硬币和 4 枚价值为 10 的硬币。
• Bob 拿走 1 枚价值为 75 的硬币和 4 枚价值为 10 的硬币。

 

提示：

• 1 <= x, y <= 100

解题方法：计算

价值75和10的硬币组成价值115的硬币只有一种方法：1枚75的硬币和4枚10的硬币：

首先115就要求硬币里面一定有75，因为个位的5是没法用10组成的。

其次75只能有1枚，因为$75\times 2>115$。

所以其实只有一种方案。

所以根本不是什么博弈，也没有什么“最优”策略。两个人只能按照单一的方式轮换拿硬币，如果有奇数份“75+4*10”则Alice获胜否则Bob获胜。

• 时间复杂度$O(1)$
• 空间复杂度$O(1)$

BTW. 今日每日一题没有官方题解诶。

AC代码

C++

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

Python

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

Java

class Solution {public String losingPlayer(int x, int y) {return Math.min(x, y / 4) % 2 == 1 ? "Alice" : "Bob";}
}

Go

package mainfunc losingPlayer(x int, y int) string {if min(x, y / 4) % 2 == 1 {return "Alice"}return "Bob"
}

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

Tisfy：https://letmefly.blog.csdn.net/article/details/143501415