1927.求和游戏：抵消+看最值

【LetMeFly】1927.求和游戏：抵消+看最值

力扣题目链接：https://leetcode.cn/problems/sum-game/

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

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

1. 选择一个下标 i 满足 num[i] == '?' 。
2. 将 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 <= 105
• num.length 是 偶数 。
• num 只包含数字字符和 '?' 。

解题方法：先抵消，然后看最值

先算算前半个字符串总值是多少、问号有多少；再算算后半字符串总值是多少、问号有多少。

不妨令后半字符串的问号不少于前半字符串（如果少于则交换前后两字符串的总值、问号数，不影响填写结果）。

计算前半字符串比后半字符串的总值差值 $diff$，以及问号数差值 $times$。

为何可以计算两字符串问号数量的差值？因为(假设前半字符串问号数量少)Alice在前半段填写什么，Bob就可以在后半段填写一样的数抵消差值，且Alice的最佳方案可以只填9或0。

现在问题变成了，前半段总值比后半段多$diff$，后半段字符串有$times$个问号，Alice先手，能否导致后面总值不等于$diff$。

算下先手Alice想让后半段字符串问号总和最大的话（Alice全填9Bob全填0）能有多大；算下先手Alice想让后半段字符串问号总和最小的话（Alice全填0Bob全填9）能有多小。如果bob全填0的后半段问号最大值$M$大于$diff$则Alice获胜、如果bob全填9的后半段问号最小值$m$小于$diff$则Alice获胜；否则Bob获胜。

• 时间复杂度$O(len(num))$
• 空间复杂度$O(1)$

AC代码

C++

/*
 * @LastEditTime: 2026-08-23 13:46:29
 */
typedef pair<int, int> pii;
class Solution {
private:
    pii cal(string& s, int l, int r) {
        int val = 0, cnt = 0;
        for (int i = l; i < r; i++) {
            if ('0' <= s[i] && s[i] <= '9') {
                val += s[i] - '0';
            } else {
                cnt++;
            }
        }
        return {val, cnt};
    }

    int getM(int n) {
        return 9 * ((n + 1) / 2);
    }

    int getm(int n) {
        return 9 * (n / 2);
    }
public:
    bool sumGame(string& num) {
        int n = num.size();
        auto [val1, cnt1] = cal(num, 0, n / 2);
        auto [val2, cnt2] = cal(num, n / 2, n);
        if (cnt1 > cnt2) {
            swap(val1, val2);
            swap(cnt1, cnt2);
        }
        int diff = val1 - val2, times = cnt2 - cnt1;
        int M = getM(times), m = getm(times);
        return M > diff || m < diff;
    }
};

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源