admin管理员组文章数量:1621658
题目(中等)
Alice 和 Bob 再次设计了一款新的石子游戏。现有一行 n 个石子,每个石子都有一个关联的数字表示它的价值。给你一个整数数组 stones ,其中 stones[i] 是第 i 个石子的价值。
Alice 和 Bob 轮流进行自己的回合,Alice 先手。每一回合,玩家需要从 stones 中移除任一石子。
如果玩家移除石子后,导致 所有已移除石子 的价值 总和 可以被 3 整除,那么该玩家就 输掉游戏 。
如果不满足上一条,且移除后没有任何剩余的石子,那么 Bob 将会直接获胜(即便是在 Alice 的回合)。
假设两位玩家均采用 最佳 决策。如果 Alice 获胜,返回 true ;如果 Bob 获胜,返回 false 。
示例 1:
输入:stones = [2,1]
输出:true
解释:游戏进行如下:
- 回合 1:Alice 可以移除任意一个石子。
- 回合 2:Bob 移除剩下的石子。
已移除的石子的值总和为 1 + 2 = 3 且可以被 3 整除。因此,Bob 输,Alice 获胜。
示例 2:
输入:stones = [2]
输出:false
解释:Alice 会移除唯一一个石子,已移除石子的值总和为 2 。
由于所有石子都已移除,且值总和无法被 3 整除,Bob 获胜。
示例 3:
输入:stones = [5,1,2,4,3]
输出:false
解释:Bob 总会获胜。其中一种可能的游戏进行方式如下:
- 回合 1:Alice 可以移除值为 1 的第 2 个石子。已移除石子值总和为 1 。
- 回合 2:Bob 可以移除值为 3 的第 5 个石子。已移除石子值总和为 = 1 + 3 = 4 。
- 回合 3:Alices 可以移除值为 4 的第 4 个石子。已移除石子值总和为 = 1 + 3 + 4 = 8 。
- 回合 4:Bob 可以移除值为 2 的第 3 个石子。已移除石子值总和为 = 1 + 3 + 4 + 2 = 10.
- 回合 5:Alice 可以移除值为 5 的第 1 个石子。已移除石子值总和为 = 1 + 3 + 4 + 2 + 5 = 15.
Alice 输掉游戏,因为已移除石子值总和(15)可以被 3 整除,Bob 获胜。
提示:
1 <= stones.length <= 10^5
1 <= stones[i] <= 10^4
解题思路
模3处理,根据个数判断,重点在于取到3的倍数相当于把问题转交给对手,所以偶数个可以抵消;1,2配对也是同理;
选定了1或2后,后续为了不输的策略是固定的,
A:1,2,2,2,2,……
B:1,1,1,1,1,……
或
A:2,1,1,1,1,……
B:2,2,2,2,2,……
A只要选能赢的序列即可,前提是个数足够他挑
代码
class Solution {
public:
bool stoneGameIX(vector<int>& stones) {
bool Awin = true, Bwin = false;
if(stones.size() == 1) return Bwin;
vector<int> cnt(3, 0);
for(auto x : stones) { //模3预处理
cnt[x % 3]++;
}
if(cnt[1] == 0 && cnt[2] == 0) return Bwin; //全是3的倍数,谁先动谁输
//成对的三的倍数大家相互取,相当于可以抵消不用管
if(cnt[0] % 2 == 0) {
//偶数个,相当于没3,如果有1,2A必赢,选定1或2中一个后,后续的保证不输的序列是固定的,哪个能赢用哪个,前提是有1,2可选
return (cnt[1] != 0 && cnt[2] != 0) ? Awin : Bwin;
}
else { //奇数个,相当于可以颠倒先后手
int remain = max(cnt[1], cnt[2]) - min(cnt[1], cnt[2]);
return remain > 2 ? Awin : Bwin;
}
}
};
版权声明:本文标题:力扣2029——石子游戏 IX(博弈) 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://www.elefans.com/xitong/1728851092a1176687.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论