1927. 求和游戏

题目描述

Alice 和 Bob 玩一个游戏，两人轮流行动，Alice 先手 。

给你一个 偶数长度 的字符串 num ，每一个字符为数字字符或者 '?' 。每一次操作中，如果 num 中至少有一个 '?' ，那么玩家可以执行以下操作：

选择一个下标 i 满足 num[i] == '?' 。
将 num[i] 用 '0' 到 '9' 之间的一个数字字符替代。

当 num 中没有 '?' 时，游戏结束。

Bob 获胜的条件是 num 中前一半数字的和等于后一半数字的和。Alice 获胜的条件是前一半的和与后一半的和 不相等 。

比方说，游戏结束时 num = "243801" ，那么 Bob 获胜，因为 2+4+3 = 8+0+1 。如果游戏结束时 num = "243803" ，那么 Alice 获胜，因为 2+4+3 != 8+0+3 。

在 Alice 和 Bob 都采取最优策略的前提下，如果 Alice 获胜，请返回 true ，如果 Bob 获胜，请返回 false 。

示例 1：

输入：num = "5023"
输出：false
解释：num 中没有 '?' ，没法进行任何操作。
前一半的和等于后一半的和：5 + 0 = 2 + 3 。

示例 2：

输入：num = "25??"
输出：true
解释：Alice 可以将两个 '?' 中的一个替换为 '9' ，Bob 无论如何都无法使前一半的和等于后一半的和。

示例 3：

输入：num = "?3295???"
输出：false
解释：Bob 总是能赢。一种可能的结果是：
- Alice 将第一个 '?' 用 '9' 替换。num = "93295???" 。
- Bob 将后面一半中的一个 '?' 替换为 '9' 。num = "932959??" 。
- Alice 将后面一半中的一个 '?' 替换为 '2' 。num = "9329592?" 。
- Bob 将后面一半中最后一个 '?' 替换为 '7' 。num = "93295927" 。
Bob 获胜，因为 9 + 3 + 2 + 9 = 5 + 9 + 2 + 7 。

提示：

2 <= num.length <= 10⁵
num.length 是偶数。
num 只包含数字字符和 '?' 。

解法

方法一：分类讨论

思考

双方交替填 ?，Alice 要使左右半和不同。完整博弈树随问号个数指数增长，但最优策略可归结为问号奇偶与两侧已有数字之差。

问号总数为奇数时 Alice 先手多填一次，必能使两侧不等。偶数时双方总能把剩余问号对冲到同一侧，Bob 能逼平当且仅当已有和之差恰好等于 \(9\) 乘以两侧问号数之差的一半。

因此扫描左右半的问号个数与数字和，按上述等式判断即可，无需模拟对局。

如果 '?' 的个数为奇数，那么 Alice 一定会获胜，因为她可以选择将最后一个 '?' 替换为任何一个数字，使得前一半的和与后一半的和不相等。

如果 '?' 的个数为偶数，Alice 为了使得前一半的和与后一半的和不相等，那么会选择在当前和较大的一半数字中放置 \(9\)，在当前和较小的一半数字中放置 \(0\)，而 Bob 为了使得前后两半的和相等，那么会选择在 Alice 替换数字的另一半放置一个与 Alice 替换数字相同的数字。

因此，最终会使得剩下的所有偶数个 '?' 集中在其中一半。假设当前两半的数字差值为 \(d\)。

我们先考虑，如果剩下两个 '?'，差值为 \(x\)，此时：

如果 \(x \lt 9\)，那么 Alice 必胜，因为 Alice 可以将其中一个 '?' 替换为 \(9\)，使得前一半的和与后一半的和不相等；
如果 \(x \gt 9\)，那么 Alice 必胜，因为 Alice 可以将其中一个 '?' 替换为 \(0\)，使得前一半的和与后一半的和不相等；
如果 \(x = 9\)，那么 Bob 必胜，假设 Alice 替换的数字为 \(a\)，那么 Bob 可以将另一个 '?' 替换为 \(9 - a\)，使得前后两半的和相等。

因此，如果两半数字差值为 \(d= \frac{9 \times cnt}{2}\)，其中 \(cnt\) 为剩下的 '?' 的个数，那么 Bob 必胜，否则 Alice 必胜。

时间复杂度 \(O(n)\)，其中 \(n\) 为字符串的长度。空间复杂度 \(O(1)\)。

Python3JavaC++GoTypeScript

class Solution:
    def sumGame(self, num: str) -> bool:
        n = len(num)
        cnt1 = num[: n // 2].count("?")
        cnt2 = num[n // 2 :].count("?")
        s1 = sum(int(x) for x in num[: n // 2] if x != "?")
        s2 = sum(int(x) for x in num[n // 2 :] if x != "?")
        return (cnt1 + cnt2) % 2 == 1 or s1 - s2 != 9 * (cnt2 - cnt1) // 2

class Solution {
    public boolean sumGame(String num) {
        int n = num.length();
        int cnt1 = 0, cnt2 = 0;
        int s1 = 0, s2 = 0;
        for (int i = 0; i < n / 2; ++i) {
            if (num.charAt(i) == '?') {
                cnt1++;
            } else {
                s1 += num.charAt(i) - '0';
            }
        }
        for (int i = n / 2; i < n; ++i) {
            if (num.charAt(i) == '?') {
                cnt2++;
            } else {
                s2 += num.charAt(i) - '0';
            }
        }
        return (cnt1 + cnt2) % 2 == 1 || s1 - s2 != 9 * (cnt2 - cnt1) / 2;
    }
}

class Solution {
public:
    bool sumGame(string num) {
        int n = num.size();
        int cnt1 = 0, cnt2 = 0;
        int s1 = 0, s2 = 0;
        for (int i = 0; i < n / 2; ++i) {
            if (num[i] == '?') {
                cnt1++;
            } else {
                s1 += num[i] - '0';
            }
        }
        for (int i = n / 2; i < n; ++i) {
            if (num[i] == '?') {
                cnt2++;
            } else {
                s2 += num[i] - '0';
            }
        }
        return (cnt1 + cnt2) % 2 == 1 || (s1 - s2) != 9 * (cnt2 - cnt1) / 2;
    }
};

func sumGame(num string) bool {
    n := len(num)
    var cnt1, cnt2, s1, s2 int
    for i := 0; i < n/2; i++ {
        if num[i] == '?' {
            cnt1++
        } else {
            s1 += int(num[i] - '0')
        }
    }
    for i := n / 2; i < n; i++ {
        if num[i] == '?' {
            cnt2++
        } else {
            s2 += int(num[i] - '0')
        }
    }
    return (cnt1+cnt2)%2 == 1 || s1-s2 != (cnt2-cnt1)*9/2
}

function sumGame(num: string): boolean {
    const n = num.length;
    let [cnt1, cnt2, s1, s2] = [0, 0, 0, 0];
    for (let i = 0; i < n >> 1; ++i) {
        if (num[i] === '?') {
            ++cnt1;
        } else {
            s1 += num[i].charCodeAt(0) - '0'.charCodeAt(0);
        }
    }
    for (let i = n >> 1; i < n; ++i) {
        if (num[i] === '?') {
            ++cnt2;
        } else {
            s2 += num[i].charCodeAt(0) - '0'.charCodeAt(0);
        }
    }
    return (cnt1 + cnt2) % 2 === 1 || 2 * (s1 - s2) !== 9 * (cnt2 - cnt1);
}

1927. 求和游戏

题目描述

解法

方法一：分类讨论

评论