LeetCode 题解工作台
求和游戏
Alice 和 Bob 玩一个游戏，两人轮流行动， Alice 先手 。 给你一个 偶数长度 的字符串 num ，每一个字符为数字字符或者 '?' 。每一次操作中，如果 num 中至少有一个 '?' ，那么玩家可以执行以下操作： 选择一个下标 i 满足 num[i] == '?' 。 将 num[i…
4
题型
5
代码语言
3
相关题
当前训练重点
中等 · 贪心·invariant
答案摘要
如果 `'?'` 的个数为奇数，那么 Alice 一定会获胜，因为她可以选择将最后一个 `'?'` 替换为任何一个数字，使得前一半的和与后一半的和不相等。 如果 `'?'` 的个数为偶数，Alice 为了使得前一半的和与后一半的和不相等，那么会选择在当前和较大的一半数字中放置 ，在当前和较小的一半数字中放置 ，而 Bob 为了使得前后两半的和相等，那么会选择在 Alice 替换数字的另一半放置一个…
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 贪心·invariant 题型思路
题目描述
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 <= 105num.length是 偶数 。num只包含数字字符和'?'。
解题思路
方法一：分类讨论
如果 '?' 的个数为奇数，那么 Alice 一定会获胜，因为她可以选择将最后一个 '?' 替换为任何一个数字，使得前一半的和与后一半的和不相等。
如果 '?' 的个数为偶数，Alice 为了使得前一半的和与后一半的和不相等，那么会选择在当前和较大的一半数字中放置 ，在当前和较小的一半数字中放置 ，而 Bob 为了使得前后两半的和相等，那么会选择在 Alice 替换数字的另一半放置一个与 Alice 替换数字相同的数字。
因此，最终会使得剩下的所有偶数个 '?' 集中在其中一半。假设当前两半的数字差值为 。
我们先考虑，如果剩下两个 '?'，差值为 ，此时：
- 如果 ，那么 Alice 必胜，因为 Alice 可以将其中一个
'?'替换为 ，使得前一半的和与后一半的和不相等； - 如果 ，那么 Alice 必胜，因为 Alice 可以将其中一个
'?'替换为 ，使得前一半的和与后一半的和不相等； - 如果 ，那么 Bob 必胜，假设 Alice 替换的数字为 ，那么 Bob 可以将另一个
'?'替换为 ，使得前后两半的和相等。
因此，如果两半数字差值为 ，其中 为剩下的 '?' 的个数，那么 Bob 必胜，否则 Alice 必胜。
时间复杂度 ，其中 为字符串的长度。空间复杂度 。
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
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n) since each character is processed once to compute sums and count '?'. Space complexity is O(1) beyond input storage as only counters are used. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Looking for correct sum tracking and handling of '?'
- question_mark
Expect insight into greedy strategy and modular reasoning
- question_mark
Checking ability to predict outcome before simulating all moves
常见陷阱
外企场景- error
Forgetting to consider distribution of '?' between halves
- error
Assuming Alice can always pick optimal digits without considering Bob's counters
- error
Neglecting modulo arithmetic leading to wrong winner prediction
进阶变体
外企场景- arrow_right_alt
Sum Game with odd length strings requiring extra rules
- arrow_right_alt
Allow '?' to be replaced with digits outside 0-9 range
- arrow_right_alt
Multiple players alternating instead of just Alice and Bob