石子游戏 IX

难度: Medium

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⁴

Submission

运行时间: 85 ms

内存: 26.6 MB

class Solution:
    def stoneGameIX(self, stones: List[int]) -> bool:
        s = sum(stones)
        n = len(stones)
        cnt = [0]*3
        for s in stones:
            cnt[s%3]+=1
        
        if cnt[0]%2==0:
            one = False
            if cnt[1]>=1 and cnt[2]>=cnt[1]:
                one = True
            # 11 21 21 21 22 (2222)
            two = False
            if cnt[2]>=1 and cnt[1]>=cnt[2]:
                two = True
            return one or two
        else:
            one = False
            if cnt[1]>=1 and cnt[2]+2<cnt[1]:
                one = True
            # 不可
            # 11 21 21 21 2 ()
            # 11 21 21 21 21 ()
            two = False
            if cnt[2]>=1 and cnt[1]+2<cnt[2]:
                two = True
            return one or two

Explain

题解主要通过计算各个石子对3取模的结果，根据其频率来确定Alice是否能够获胜。首先，石子的值对3的余数被分为三类：0, 1, 2。用数组cnt来计数每个类别的石子数量。接下来，根据cnt[0]（余数为0的石子数量）是否为偶数，分两种情况考虑：1. 如果cnt[0]是偶数，则分别检查：当选择余数为1的石子开始时，余数为2的石子数量至少要不少于余数为1的石子数量；当选择余数为2的石子开始时，余数为1的石子数量至少要不少于余数为2的石子数量。2. 如果cnt[0]是奇数，则分别检查：当选择余数为1的石子开始时，余数为1的石子数量至少要比余数为2的石子多2；当选择余数为2的石子开始时，余数为2的石子数量至少要比余数为1的石子多2。最后，根据以上条件返回Alice是否可能赢得游戏。

时间复杂度: O(n)

空间复杂度: O(1)

class Solution:
    def stoneGameIX(self, stones: List[int]) -> bool:
        cnt = [0]*3
        for stone in stones:
            cnt[stone % 3] += 1
        
        if cnt[0] % 2 == 0:
            # cnt[0]为偶数的情况
            one = cnt[1] >= 1 and cnt[2] >= cnt[1]
            two = cnt[2] >= 1 and cnt[1] >= cnt[2]
            return one or two
        else:
            # cnt[0]为奇数的情况
            one = cnt[1] >= 1 and cnt[2] + 2 < cnt[1]
            two = cnt[2] >= 1 and cnt[1] + 2 < cnt[2]
            return one or two

Explore

在石子游戏IX中，将石子的值对3取模并分成三类0, 1, 2是因为这与游戏的基本规则有关，规则涉及到石子数值的累加和对3的余数。当两名玩家轮流取石子时，他们的目标是避免使得累积的石子数值之和被3整除，因为这将导致游戏立即结束并判输。因此，通过分类这些余数，我们可以更好地分析和预测各种取石子策略的结果，并制定相应的策略来优化胜算。

在石子游戏IX中，余数为0的石子特别重要，因为它们直接影响游戏的输赢条件——导致累积和被3整除。当cnt[0]为偶数时，这些石子在游戏中被取走后，不会改变当前的取石子序列对3的总余数，从而保持游戏状态稳定。然而，如果cnt[0]为奇数，每次取一个余数为0的石子，都会使得状态在奇数和偶数之间切换，增加了游戏的不确定性和复杂性。因此，判断cnt[0]的奇偶性是分析Alice是否有赢得可能性的关键步骤。

当cnt[0]为偶数时，余数为0的石子不会对游戏的总状态产生影响，因此游戏的胜负主要取决于余数为1和2的石子。检查`cnt[1] >= 1 and cnt[2] >= cnt[1]`的条件意味着Alice可以开始选择余数为1的石子，并且她能够继续游戏直到所有的石子都被选完。这个条件确保了即使Bob尝试通过选择余数为2的石子来改变游戏状态，Alice仍有足够的余数为1的石子来应对，避免使累积和被3整除，从而保持赢面。