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
解释：没有 '?' 需要替换。
前一半的和等于后一半的和：5 + 0 = 2 + 3。
示例 2：
输入：num = "25??"
输出：true
解释：Alice 可以将其中一个 '?' 替换为 '9'，这样 Bob 就不可能让两边的和相等。
示例 3：
输入：num = "?3295???"
输出：false
解释：可以证明 Bob 总是能获胜。
提示：
2 <= num.length <= 10^5num.length是偶数num只包含数字和 ‘?’
解题思路
这是一个博弈论问题，需要分析在双方都采用最优策略时的胜负结果。
核心思路：
- 状态分析：统计左半部分和右半部分的数字和以及问号个数
- 博弈策略：Alice 想要制造差异，Bob 想要平衡差异
- 最优操作：Alice 会尽量填大数字(9)在较小的一边，Bob 会通过填数字来平衡
关键观察：
- 如果问号总数为奇数，Alice 最后一步可以决定性地制造不平衡
- 如果问号总数为偶数，需要分析初始差值和问号分布
分析过程：
- 计算左右两半的当前数字和差值：
diff = leftSum - rightSum - 计算左右两半的问号数量差：
questionDiff = leftQuestions - rightQuestions - Alice 和 Bob 轮流操作，Alice 试图最大化差异，Bob 试图最小化差异
判断条件：
- Alice 获胜当且仅当：
diff + questionDiff * 4.5 != 0 - 这里 4.5 表示平均每个问号对差值的贡献（Alice 填 9，Bob 填 0 的平均效果）
代码实现
class Solution {
public:
bool sumGame(string num) {
int n = num.length();
int leftSum = 0, rightSum = 0;
int leftQuestions = 0, rightQuestions = 0;
// 计算左半部分的和与问号数量
for (int i = 0; i < n / 2; i++) {
if (num[i] == '?') {
leftQuestions++;
} else {
leftSum += num[i] - '0';
}
}
// 计算右半部分的和与问号数量
for (int i = n / 2; i < n; i++) {
if (num[i] == '?') {
rightQuestions++;
} else {
rightSum += num[i] - '0';
}
}
// 计算初始差值和问号差值
int diff = leftSum - rightSum;
int questionDiff = leftQuestions - rightQuestions;
// Alice获胜的条件：最终无法平衡
// 每个问号最多贡献9，Alice和Bob轮流，平均贡献4.5
return diff + questionDiff * 4.5 != 0;
}
};
class Solution:
def sumGame(self, num: str) -> bool:
n = len(num)
left_sum = right_sum = 0
left_questions = right_questions = 0
# 计算左半部分的和与问号数量
for i in range(n // 2):
if num[i] == '?':
left_questions += 1
else:
left_sum += int(num[i])
# 计算右半部分的和与问号数量
for i in range(n // 2, n):
if num[i] == '?':
right_questions += 1
else:
right_sum += int(num[i])
# 计算初始差值和问号差值
diff = left_sum - right_sum
question_diff = left_questions - right_questions
# Alice获胜的条件：最终无法平衡
return diff + question_diff * 4.5 != 0
public class Solution {
public bool SumGame(string num) {
int n = num.Length;
int leftSum = 0, rightSum = 0;
int leftQuestions = 0, rightQuestions = 0;
// 计算左半部分的和与问号数量
for (int i = 0; i < n / 2; i++) {
if (num[i] == '?') {
leftQuestions++;
} else {
leftSum += num[i] - '0';
}
}
// 计算右半部分的和与问号数量
for (int i = n / 2; i < n; i++) {
if (num[i] == '?') {
rightQuestions++;
} else {
rightSum += num[i] - '0';
}
}
// 计算初始差值和问号差值
int diff = leftSum - rightSum;
int questionDiff = leftQuestions - rightQuestions;
// Alice获胜的条件：最终无法平衡
return diff + questionDiff * 4.5 != 0;
}
}
/**
* @param {string} num
* @return {boolean}
*/
var sumGame = function(num) {
const n = num.length;
let leftSum = 0, rightSum = 0;
let leftQuestions = 0, rightQuestions = 0;
// 计算左半部分的和与问号数量
for (let i = 0; i < n / 2; i++) {
if (num[i]
复杂度分析
| 复杂度类型 | 值 | 说明 |
|---|---|---|
| 时间复杂度 | O(n) | 需要遍历一次字符串统计数字和与问号数量 |
| 空间复杂度 | O(1) | 只使用常数个变量存储统计信息 |