1927-求和游戏

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:45:43 2023-09-13 16:45:43 Updated    

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 只包含数字字符和 '?' 。

方法一：猜想 + 数学归纳法验证

提示 1

如果问号的个数为奇数，那么 Alice 一定获胜。

提示 1 解释

由于 Alice 先手，那么最后一个问号一定是由 Alice 操作。

显然，在 [0, 9] 中最多只有一个数字 d 可以使得最终前一半数字的和等于后一半数字的和，因此 Alice 只要将问号替换成 d 以外的任意数字即可。

接下来我们就只需要考虑问号的个数为偶数的情况。

提示 2

如果问号的个数为 0，那么 Bob 获胜当且仅当前一半数字的和等于后一半数字的和。

提示 3

如果问号的个数为 2 并且它们出现在不同侧（即一个问号在前一半中，另一个问号在后一半中），那么 Bob 获胜当且仅当前一半数字的和等于后一半数字的和。

提示 3 解释

如果前一半数字的和等于后一半数字的和，那么 Alice 选择任意一个问号替换成任意数字 d，Bob 只需要选择另一个问号同样替换成数字 d 即可，因此 Bob 一定获胜。

如果前一半数字的和不等于后一半数字的和，那么 Alice 只需要选择较大的那一半数字中的问号，将其替换成 9。由于无法将问号替换成比 9 更大的数，因此 Alice 一定获胜。

提示 4

如果问号的个数为 2 并且它们出现在同侧，那么 Bob 获胜当且仅当包含问号的一半的数字和恰好比不包含问号的一半的数字和小 9。

提示 4 解释

Bob 总可以保证它和 Alice 在相邻的两次操作中替换的数字之和为 9，即如果 Alice 选择将问号替换成数字 d，Bob 就将另一个问号替换成数字 9-d。

因此，如果满足提示 4，那么 Bob 一定获胜，否则：

  • 如果超过 9，那么 Alice 将问号替换成 0；

  • 如果不超过 9（不包含 9），那么 Alice 将问号替换成 9。

这样一来，Bob 无法选择 [0, 9] 中的数字使得前一半数字的和等于后一半数字的和，因此 Alice 一定获胜。

提示 5

假设前一半的数字和为 n_0，问号的个数为 q_0，后一半的数字和为 n_1，问号的个数为 q_1，且 q_0+q_1 为偶数，那么 Bob 获胜当且仅当：

n_0 - n_1 = 9/2}(q_1 - q_0) \tag{1}

我们可以根据提示 3 和提示 4 形象地解释这个等式。不失一般性，我们假设 q_0 \leq q_1，那么：

  • 对于 q_0 个分别在两侧的问号，根据提示 3，Alice 和 Bob 的最优策略会使得它们的数字和完全相等；

  • 对于 q_1-q_0 个在后一半中的问号，根据提示 4，Alice 和 Bob 的最优策略会使得它们分成 \dfrac{q_1-q_0/2 对，每一对的数字和为 9。

  • 因此，要使得数字和相等，前一半必须比后一半大 \dfrac{9/2}(q_1-q_0)。

提示 5 解释

更严谨的证明可以对问号的总个数 q_0+q_1 使用数学归纳法：

  • 根据提示 3 和提示 4，当 q_0+q_1=2 时，提示 5 成立，即当等式 (1) 成立时 Bob 一定获胜，否则 Alice 一定获胜；

  • 假设当 q_0+q_1=k 时提示 5 成立，那么当 q_0+q_1=k+2 时，不失一般性，我们假设 q_0 \leq q_1，那么：

    • 如果此时等式 (1) 已经成立，那么如果 Alice 选择将左侧的问号替换成 d，Bob 就将右侧的问号替换成 d；如果 Alice 选择将右侧的问号替换成 d，Bob 就将另一个右侧的问号替换成 9-d，使得等式 (1) 仍然成立。这样就归纳到了 q_0+q_1=k 的情况，说明 Bob 一定获胜；

    • 如果此时等式 (1) 不成立，记 n_0 - n_1 = \dfrac{9/2}(q_1-q_0) + \delta，

      • 如果 \delta > 0，那么 Alice 选择将右侧的问号替换成 0。这样一来，如果 Bob 选择左侧的问号替换成 d：

      (n_0+d)-n_1=9/2}(q_1-q_0)+(\delta + d) \neq 9/2}((q_1-1)-(q_0-1))

      等式 (1) 仍然不成立。如果 Bob 选择另一个右侧的问号替换成 d：

      n_0 - (n_1 + d) = 9/2}((q_1-2)-q_0)+(\delta+9-d) \neq 9/2}((q_1-2)-q_0)

      等式 (1) 同样不成立；

      • 如果 \delta < 0，那么 Alice 选择将右侧的问号替换成 9。这样一来，如果 Bob 选择左侧的问号替换成 d：

      (n_0+d)-(n_1+9)=9/2}(q_1-q_0)+(\delta-9+d) \neq 9/2}((q_1-1)-(q_0-1))

      等式 (1) 仍然不成立。如果 Bob 选择另一个右侧的问号替换成 d：

      n_0 - (n_1 + 9 + d) = 9/2}((q_1-2)-q_0)+(\delta-d) \neq 9/2}((q_1-2)-q_0)

      等式 (1) 同样不成立。

      此时我们就将所有的可能归纳到了 q_0+q_1=k 的情况，说明 Alice 一定获胜。

因此提示 5 成立。

思路与算法

我们对字符串 num 进行遍历，计算出 n_0, q_0, n_1, q_1。如果 q_0+q_1 为奇数则 Alice 必胜，否则通过提示 5 来判断获胜方。

代码

[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    bool sumGame(string num) {
        int n = num.size();

        auto get = [](string&& s) -> pair<int, int> {
            int nn = 0, qq = 0;
            for (char ch: s) {
                if (ch == '?') {
                    ++qq;
                }
                else {
                    nn += (ch - '0');
                }
            }
            return {nn, qq};
        };

        auto [n0, q0] = get(num.substr(0, n / 2));
        auto [n1, q1] = get(num.substr(n / 2, n / 2));

        return ((q0 + q1) % 2 == 1) || (n0 - n1 != (q1 - q0) * 9 / 2);
    }
};
[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def sumGame(self, num: str) -> bool:
        n = len(num)
        
        def get(s: str) -> (int, int):
            nn = qq = 0
            for ch in s:
                if ch == "?":
                    qq += 1
                else:
                    nn += int(ch)
            return nn, qq
        
        n0, q0 = get(num[:n//2])
        n1, q1 = get(num[n//2:])
        
        return (q0 + q1) % 2 == 1 or n0 - n1 != (q1 - q0) * 9 // 2

复杂度分析

  • 时间复杂度：O(n)，其中 n 是字符串 num 的长度。

  • 空间复杂度：O(n)。上面给出的代码对 num 的两侧进行了拷贝，使得代码更加直观。我们也可以直接对 num 进行一次遍历计算出 n_0, q_0, n_1, q_1，空间复杂度为 O(1)。

 Comments
On this page
1927-求和游戏