class Solution {
public:
bool sumGame(string num) {
}
};
1927. 求和游戏
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 只包含数字字符和 '?' 。原站题解
golang 解法, 执行用时: 12 ms, 内存消耗: 6.1 MB, 提交时间: 2023-09-07 11:17:10
func sumGame(num string) bool {
n := len(num)
_get := func(s string) (int, int) {
nn, qq := 0, 0
for _, ch := range s {
if ch == '?' {
qq++
} else {
nn += int(ch) - 48
}
}
return nn, qq
}
n0, q0 := _get(num[:n/2])
n1, q1 := _get(num[n/2:])
return (q0 + q1) % 2 == 1 || n0 - n1 != (q1 - q0) * 9 / 2
}
cpp 解法, 执行用时: 56 ms, 内存消耗: 12.3 MB, 提交时间: 2023-09-07 11:05:54
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);
}
};
python3 解法, 执行用时: 116 ms, 内存消耗: 16.6 MB, 提交时间: 2023-09-07 11:05:34
# 数学归纳
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