Leetcode-2029-石子游戏 IX

题目

2029.石子游戏 IX 难度：中等

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⁵
1 <= stones[i] <= 10⁴

题解

根据规则和题目，可以有这些小结论：

所谓石子的价值真正有用的是对3取模后的值，我们将移除石子价值总数记为x，每个石子的价值记为s=0,1,2；
Alice想要赢，只有一种情况，就是让Bob移除石子后使得移除石子总数是3的倍数；
为了保证自己不输，自己要移除的石子s不能等于3-x，也就是如果现在x=1，“我”现在能选的石子s只能是1或0；
偶数个s=0相当于没有x=0，因为都是最优走法；
没有s=0，大致情况是：
1,1,2,1,2,1…或2,2,1,2,1,2,1…;

讨论s=0偶数个的情况：

如果全是s=1,Alice必败；
如果全是s=2,Alice也必败；
如果既有s=1，也有s=2，因为A第一手之后，1和2交替进行，所以，
1. 两个数量相等。无论Alice选哪个，Bob最后选的和Alice一开始选的构成三的倍数，所以Alice都赢；
2. s=1和s=2不一样多。
  1. Alice第一步选少的那个，这样，Bob就会一路选和Alice第一次一样的，直到没了Bob只好选另一个，这时候就构成了三的倍数，Bob输掉，Alice必胜；
  2. 但如果Alice选较多的那一个（假设是s=2），一顿交替之后，较少的s=1没了，
    1. 如果s=2比s=1只多一个，Alice是最后一个，Alice输掉；
    2. 如果s=2比s=1多两个，Bob最后是s=1，根据规则，依然是Bob胜利；
    3. 如果s=2比s=1多超过两个，当s=1没了，Bob选s=2，Alice只能再选s=2，构成3的倍数，Alice输掉—就相当于前面全是s=2的情况。
所以，Alice要选少的那个，一样多就都行。
综合一下：
如果相同，只有一种，Alice完了；
两种都有，选少的，一样就都可以选；
也就是说，只要s=1或s=2有一个没有，就完了。

讨论s=0奇数的情况：

Alice第一步肯定不拿s=0;
奇数个s=0有起到转换先手的作用；
那Bob第一步也就是整个的第二回合用不用这个s=0呢？
也先考虑全是s=1或s=2的情况，因为这两其实等价，所以假设全是s=1：
1. 如果数量只有1个或2个，那Alice必输
  她都没机会让Bob取了之后构成3的倍数啊。
2. 如果数量大于2个
  1. Bob首先就选了s=0，那现在的Alice就相当于之前讨论的s=0个数是偶数且全是s=1这种情况下的Bob，Alice赢；
  2. Bob先不选s=0，那Alice不选s=0就输了，所以肯定会选s=0。。。Bob输了。
所以，如果这数量超过2，Alice必胜，不然就必败
现在考虑既有s=1也有s=2：
非常多的s=2或s=1意义不大，就用三个以内的数量来代表；
s=1和s=1各一个（代表一样多）：Alice必输啊；
s=11个，s=22个（代表两个数量相差1）：
1. Alice选s=1，Bob选s=0，Alice最后回选到s=2而输掉，Bob为了赢那肯定会选s=0：
2. Alice选s=2，
  1. Bob不选s=0,而是选了和Alice一样的s=2，那Alice接下来选s=1输，选s=0，也是输；
  2. Bob选s=0,那Alice接下来只能接着选s=2，最终还是输。
所以这种情况Alice必输。
换个角度理解这种Alice必输的情况，因为总的数量是个偶数（1个s=1，2个s=2，奇数个s=0），而Alice要赢就要让Bob自己构成3的倍数，他俩又都是高手，能撑到最后，而最后走完，总和不可能是3的倍数，所以Alice必输。
其实不用接着讨论数量差更大的情况了，对之前讨论的只有一种的情况，往里加一对s=1和s=2就好了，效果是一样的。
所以综合一下：
其中一个没有，得相差超过2，能赢；
两个都有，相差两个之内，Alice输；
所以，只要两个数量相差超过2Alice就能赢。

代码

class Solution:
    def stoneGameIX(self, stones) -> bool:
        a = [0, 0, 0]
        for i in stones:
            a[i % 3] += 1
        if a[0] % 2 == 0:
            # if a[1]*a[2]==0:
            #     return False
            return a[1] * a[2] != 0
        else:
            return abs(a[1] - a[2]) > 2

盛日辉的博客

Leetcode-2029-石子游戏 IX

题目

题解

代码

提交记录