- LeetCode2029:石子游戏IX
- 时间:2022-01-20
- 力扣难度:Medium
- 个人难度:Hard
- 数据结构:数组
- 算法:贪心、博弈论
LeetCode2029.石子游戏IX:「博弈论」&「贪心」
1. 题目描述
题目:原题链接
- Alice 和 Bob 再次设计了一款新的石子游戏。
- 现有一行 n 个石子,每个石子都有一个关联的数字表示它的价值。给你一个整数数组 stones ,其中 stones[i] 是第 i 个石子的价值。
- Alice 和 Bob 轮流进行自己的回合,Alice 先手。每一回合,玩家需要从 stones 中移除任一石子。
- 如果玩家移除石子后,导致所有已移除石子的价值总和可以被 3 整除,那么该玩家就 输掉游戏。
- 如果不满足上一条,且移除后没有任何剩余的石子,那么 Bob 将会直接获胜(即便是在 Alice 的回合)。
- 假设两位玩家均采用最佳决策。如果 Alice 获胜,返回 true ;如果 Bob 获胜,返回 false。
1 <= stones.length <= 10^5
1 <= stones[i] <= 10^4
输入输出规范
- 输入:石子价值的数组 stones
- 输出:布尔值,表示获胜者
输入输出示例
- 输入:stones = [5,1,2,4,3]
- 输出:false
2. 方法一:博弈论分类讨论
思路
- 本题是博弈论模拟类型的问题,主要就是根据题目的规则要求,通过贪心的思想分析不同玩家每次操作的最优策略,本题来自第261场周赛
- 首先,对于只有一个元素的场景,必然是后手的Bob获胜,返回false
- 其次,由于题目规则为
- 玩家移除石子后,已移除石子的价值总和可以被 3 整除时,该玩家输
- 此外,还有一个限制,Alice如果移除的是最后一个石子,Alice也会输掉
- 因此,无论石子价值是多少,都会等价为三种类型:余数为0、1、2,此时对这三种情况分类讨论
- 余数为0:移除这种类型的石子,不会改变已移除的价值总和,相当于交换了先后手
- 情况A:0有偶数个,那么两位玩家都会优先移除0,且各自移除一半0,此时对结果不会有影响
- 情况B:0有奇数个,由于Alice还有一个不能移除最后一个元素的限制,所以这种情况不能简单的视为偶数时的反例,而是应该视为0只有一个,当玩家发现自己无论移除1还是2都无法获胜时,就会移除0来使得自己必胜
- 余数为1 和 余数为2:这两个正好可以凑成一个三的倍数,此时模拟真实的游戏过程来分类讨论(此时先忽略0)
- 情况一:Alice先移除1,那么Bob只能移除1,随后Alice只能移除2,Bob移除1,Alice移除2,以此往复,即移除序列为 112121212…
- 情况二:Alice先移除2,Bob只能移除2,Alice移除1,Bob移除2,Alice移除1,Bob移除2,以此往复,即移除序列为 22121212…
- 也就是说,先手玩家Alice可以选择这两种序列中的一种
- 对于情况一:112121212
- 当1的个数比2的个数少或者相等时,那么Bob会在游戏过程中没有1可以移除,而去移除2,导致移除总和为3的倍数,Alice获胜
- 当1的个数比2的个数多的时候,如果多一个,Alice会由于移除了最后一个元素而输;如果多两个或以上,Alice会因为没有2可以移除而输,Bob获胜
- 特别的,1的个数不能为0,至少要有一个,同时满足小于等于2的个数
- 对于情况二:2212121212
- 当2的个数比1的个数少或者相等时,那么Bob会在游戏过程中没有2可以移除,而去移除1,导致移除总和为3的倍数,Alice获胜
- 当2的个数比1的个数多的时候,如果多一个,Alice会由于移除了最后一个元素而输;如果多两个或以上,Alice会因为没有1可以移除而输,Bob获胜
- 特别的,2的个数不能为0个,至少要有一个,同时满足小于等于1的个数
- 由于Alice可以自己选择情况一的序列还是情况二的序列,所以只要知道了序列中1和2的个数谁多,Alice就会选择使自己获胜的序列,即只要1的个数和2的个数都不为0个
- 此时,再考虑之前讨论的余数为0的两种情况:情况A和情况B
- 情况A:0为偶数个,不影响结果,Alice获胜条件为:只要1的个数和2的个数都不为0个
- 情况B:0为奇数个,相当于一个0,切换先后手,Alice获胜条件为:不考虑0时,Bob获胜且不是因为所有元素被移除,具体而言,就是当1的个数比2多两个以上和2的个数比1多两个以上
题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16public boolean stoneGameIX(int[] stones) {
if (stones == null || stones.length <= 1) return false;
int countZero = 0;
int countOne = 0;
int countTwo = 0;
// 统计三种类型的个数
for (int stone : stones) {
if (stone % 3 == 0) countZero++;
else if (stone % 3 == 1) countOne++;
else countTwo++;
}
if ((countZero & 1) == 0) {
return countOne >= 1 && countTwo >= 1;
}
return Math.abs(countOne - countTwo) > 2;
}复杂度分析:n 是数组的大小
- 时间复杂度:$O(n)$
- 空间复杂度:$O(1)$
本文作者:
Chthollists
发布时间: 2022-01-20 15:11:27
最后更新: 2022-01-27 20:44:38
本文标题: LeetCode2029.石子游戏IX:「博弈论」&「贪心」
本文链接: https://chthollists.github.io/post/a94c0e43.html
版权声明: 本作品采用 CC BY-NC-SA 4.0 许可协议进行许可。转载请注明作者和出处!
发布时间: 2022-01-20 15:11:27
最后更新: 2022-01-27 20:44:38
本文标题: LeetCode2029.石子游戏IX:「博弈论」&「贪心」
本文链接: https://chthollists.github.io/post/a94c0e43.html
版权声明: 本作品采用 CC BY-NC-SA 4.0 许可协议进行许可。转载请注明作者和出处!
![知识共享许可协议](https://i.creativecommons.org/l/by-nc-sa/4.0/88x31.png)