求和游戏

标签: 贪心数学字符串博弈

难度: Medium

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

Submission

运行时间: 84 ms

内存: 16.9 MB

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 (q1+ q0)%2== 1 or n0- n1 != (q1- q0)*9//2

Explain

此题解采用的是贪心算法的思路。首先，通过遍历字符串的前半部分和后半部分，分别统计两部分中数字的总和以及'?'的数量。然后，根据这些统计结果，分析Alice和Bob的最优策略。如果'?'的总数为奇数，那么无论如何都不可能使得前后两部分的和相等，因此Alice获胜。如果'?'的总数为偶数，那么我们需要进一步分析。考虑到Alice和Bob都会尽可能地使自己获胜，我们可以假设每一对'?'中，一个会被替换为9，另一个会被替换为0，这样对总和的影响最大。因此，我们可以通过比较n0-n1与(q1-q0)*9/2的关系来判断胜负。如果二者相等，那么Bob可以获胜，否则Alice获胜。

时间复杂度: O(n)

空间复杂度: O(1)

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 (q1 + q0) % 2 == 1 or n0 - n1 != (q1 - q0) * 9 // 2

Explore

当'?'的总数为奇数时，Alice必胜的结论主要基于游戏的对称性和替换策略。在游戏中，每个'?'可以被替换成0至9中的任意一个数字。如果'?'的总数为奇数，由于Alice和Bob轮流替换'?'，最终会剩下一个'?'由Alice替换。Alice有机会选择一个对自己最有利的数字来确保两侧的总和不相等，从而获胜。无论前面的替换如何进行，Alice都能通过调整这最后一个'?'的值来控制游戏结果，确保自己处于有利位置。

如果'?'的总数为偶数，Alice和Bob将轮流替换所有的'?'，最终不会剩下任何'?'。在这种情况下，为了最大化对总和的影响，我们假设每一对'?'中，一个被替换为9，另一个被替换为0。这种替换策略是因为9和0的差距最大，可以最大化或最小化两部分的和的差异。这种极端替换策略可以让我们计算在最不利情况下（即对手尝试平衡总分时）Alice和Bob各自能达到的最大和最小总和差异。这样的分析帮助判断在最极端情况下游戏的可能结果。

公式(n0 - n1) != (q1 - q0) * 9 // 2的逻辑基于假设Alice和Bob都以最优策略替换'?'，即一方试图增加总和，另一方试图减少总和。这里n0和n1分别表示字符串前半部和后半部的数字总和，q0和q1分别表示前半部和后半部的'?'数量。当Alice和Bob替换'?'时，他们可以选择替换为0或9来最大化差异。如果所有的'?'均被替换为9和0，则总和的最大可能变化是(q1 - q0) * 9。然而，由于Alice和Bob交替替换，实际上每一对替换可以使总和差异改变18（一个+9，一个-9）。因此，总的可能变化是(q1 - q0) * 9 / 2。如果n0和n1之间的差与这个最大可能变化不匹配，则表示无法通过替换'?'达到平衡，因此Alice获胜。