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\) 有关，\(n \le 10^5\) 不能模拟到取完。余 \(0\) 不改变当前模，可穿插使用；先手第一枚不能取 \(0\)。

先手选 \(1\) 后，最优序列为 \(1,1,2,1,2,\ldots\)（对称地从 \(2\) 开始）。把余 \(0\) 的个数计入回合长度后，若总回合为奇数且两种非零余数尚未耗尽成平局，则先手胜。

对 \(cnt\) 与对调后的 \((cnt[0],cnt[2],cnt[1])\) 各判定一次，存在一种开局即可。

由于玩家的目标是使得已移除石子的价值总和不能被 \(3\) 整除，因此我们只需要考虑每个石子的价值对 \(3\) 的余数即可。

我们用一个长度为 \(3\) 的数组 \(\textit{cnt}\) 维护当前剩余石子的价值对 \(3\) 的余数的个数，其中 \(\textit{cnt}[0]\) 表示余数为 \(0\) 的个数，而 \(\textit{cnt}[1]\) 和 \(\textit{cnt}[2]\) 分别表示余数为 \(1\) 和 \(2\) 的个数。

在第一回合，Alice 不能移除余数为 \(0\) 的石子，因为这样会使得已移除石子的价值总和能被 \(3\) 整除。因此，Alice 只能移除余数为 \(1\) 或 \(2\) 的石子。

我们首先考虑 Alice 移除余数为 \(1\) 的石子的情况。如果 Alice 移除了一个余数为 \(1\) 的石子，石子 \(0\) 对石子价值总和对 \(3\) 的余数不会改变，因此价值对 \(3\) 的余数为 \(0\) 的石子可以在任意回合被移除，我们暂时不考虑。所以 Bob 也只能移除余数为 \(1\) 的石子，之后 Alice 移除余数为 \(2\) 的石子，依次进行，序列为 \(1, 1, 2, 1, 2, \ldots\)。在这种情况下，如果最终回合数为奇数，且还有剩余石子，那么 Alice 获胜，否则 Bob 获胜。

对于第一回合 Alice 移除余数为 \(2\) 的石子的情况，我们可以得到类似的结论。

时间复杂度 \(O(n)\)，其中 \(n\) 是数组 \(\textit{stones}\) 的长度。空间复杂度 \(O(1)\)。

Python3JavaC++GoTypeScriptJavaScript

class Solution:
    def stoneGameIX(self, stones: List[int]) -> bool:
        def check(cnt: List[int]) -> bool:
            if cnt[1] == 0:
                return False
            cnt[1] -= 1
            r = 1 + min(cnt[1], cnt[2]) * 2 + cnt[0]
            if cnt[1] > cnt[2]:
                cnt[1] -= 1
                r += 1
            return r % 2 == 1 and cnt[1] != cnt[2]

        c1 = [0] * 3
        for x in stones:
            c1[x % 3] += 1
        c2 = [c1[0], c1[2], c1[1]]
        return check(c1) or check(c2)

class Solution {
    public boolean stoneGameIX(int[] stones) {
        int[] c1 = new int[3];
        for (int x : stones) {
            c1[x % 3]++;
        }
        int[] c2 = {c1[0], c1[2], c1[1]};
        return check(c1) || check(c2);
    }

    private boolean check(int[] cnt) {
        if (--cnt[1] < 0) {
            return false;
        }
        int r = 1 + Math.min(cnt[1], cnt[2]) * 2 + cnt[0];
        if (cnt[1] > cnt[2]) {
            --cnt[1];
            ++r;
        }
        return r % 2 == 1 && cnt[1] != cnt[2];
    }
}

class Solution {
public:
    bool stoneGameIX(vector<int>& stones) {
        vector<int> c1(3);
        for (int x : stones) {
            ++c1[x % 3];
        }
        vector<int> c2 = {c1[0], c1[2], c1[1]};
        auto check = [](auto& cnt) -> bool {
            if (--cnt[1] < 0) {
                return false;
            }
            int r = 1 + min(cnt[1], cnt[2]) * 2 + cnt[0];
            if (cnt[1] > cnt[2]) {
                --cnt[1];
                ++r;
            }
            return r % 2 && cnt[1] != cnt[2];
        };
        return check(c1) || check(c2);
    }
};

func stoneGameIX(stones []int) bool {
    c1 := [3]int{}
    for _, x := range stones {
        c1[x%3]++
    }
    c2 := [3]int{c1[0], c1[2], c1[1]}
    check := func(cnt [3]int) bool {
        if cnt[1] == 0 {
            return false
        }
        cnt[1]--
        r := 1 + min(cnt[1], cnt[2])*2 + cnt[0]
        if cnt[1] > cnt[2] {
            cnt[1]--
            r++
        }
        return r%2 == 1 && cnt[1] != cnt[2]
    }
    return check(c1) || check(c2)
}

function stoneGameIX(stones: number[]): boolean {
    const c1: number[] = Array(3).fill(0);
    for (const x of stones) {
        ++c1[x % 3];
    }
    const c2: number[] = [c1[0], c1[2], c1[1]];
    const check = (cnt: number[]): boolean => {
        if (--cnt[1] < 0) {
            return false;
        }
        let r = 1 + Math.min(cnt[1], cnt[2]) * 2 + cnt[0];
        if (cnt[1] > cnt[2]) {
            --cnt[1];
            ++r;
        }
        return r % 2 === 1 && cnt[1] !== cnt[2];
    };
    return check(c1) || check(c2);
}

function stoneGameIX(stones) {
    const c1 = Array(3).fill(0);
    for (const x of stones) {
        ++c1[x % 3];
    }
    const c2 = [c1[0], c1[2], c1[1]];
    const check = cnt => {
        if (--cnt[1] < 0) {
            return false;
        }
        let r = 1 + Math.min(cnt[1], cnt[2]) * 2 + cnt[0];
        if (cnt[1] > cnt[2]) {
            --cnt[1];
            ++r;
        }
        return r % 2 === 1 && cnt[1] !== cnt[2];
    };
    return check(c1) || check(c2);
}

方法二：模拟

思考

方法一用闭式判断回合奇偶，推导较长。同一余数计数下，也可按序列逐步扣减，在所需余数耗尽时再看余 \(0\) 能否把当前回合变成奇数。

实现仍是 \(O(n)\) 统计加常数次模拟，便于核对边界。题面第二种写法与第一种共用同一计数框架。

与方法一相同，先统计每个石子价值对 \(3\) 的余数个数。Alice 第一手只能取余数为 \(1\) 或 \(2\) 的石子。

对每种开局，双方按最优策略交替取当前需要的余数：若第一手取 \(1\)，后续序列为 \(1, 1, 2, 1, 2, \ldots\)；若第一手取 \(2\)，则对称。当所需余数取完时，再看余数为 \(0\) 的石子能否让当前回合数为奇数——若可以，则 Alice 获胜。

只要存在一种开局使 Alice 获胜，就返回 \(\text{true}\)。

时间复杂度 \(O(n)\)，空间复杂度 \(O(1)\)。其中 \(n\) 是数组 \(\textit{stones}\) 的长度。

TypeScriptJavaScript

function stoneGameIX(stones: number[]): boolean {
    if (stones.length === 1) return false;

    const cnt = Array(3).fill(0);
    for (const x of stones) cnt[x % 3]++;

    const check = (x: number, cnt: number[]): boolean => {
        let c = 1;
        if (--cnt[x] < 0) return false;

        while (cnt[1] || cnt[2]) {
            if (cnt[x]) {
                cnt[x]--;
                x = x === 1 ? 2 : 1;
            } else return (c + cnt[0]) % 2 === 1;
            c++;
        }

        return false;
    };

    return check(1, [...cnt]) || check(2, [...cnt]);
}

function stoneGameIX(stones) {
    if (stones.length === 1) return false;

    const cnt = Array(3).fill(0);
    for (const x of stones) cnt[x % 3]++;

    const check = (x, cnt) => {
        let c = 1;
        if (--cnt[x] < 0) return false;

        while (cnt[1] || cnt[2]) {
            if (cnt[x]) {
                cnt[x]--;
                x = x === 1 ? 2 : 1;
            } else return (c + cnt[0]) % 2 === 1;
            c++;
        }

        return false;
    };

    return check(1, [...cnt]) || check(2, [...cnt]);
}

2029. 石子游戏 IX

题目描述

解法

方法一：贪心 + 分情况讨论

方法二：模拟

评论