LeetCode2029.石子游戏IX：「博弈论」&「贪心」

浏览次数 : 次 2022-01-20

博文字数统计 : 1.4k字 | 阅读所需时长 : 5分

× 文章目录

1. LeetCode2029.石子游戏IX：「博弈论」&「贪心」
1. 1.1. 1. 题目描述
2. 1.2. 2. 方法一：博弈论分类讨论

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多两个以上

题解

public 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 许可协议进行许可。转载请注明作者和出处！