英文原文
Alice and Bob take turns playing a game, with Alice starting first.
You are given a string num of even length consisting of digits and '?' characters. On each turn, a player will do the following if there is still at least one '?' in num:
- Choose an index
iwherenum[i] == '?'. - Replace
num[i]with any digit between'0'and'9'.
The game ends when there are no more '?' characters in num.
For Bob to win, the sum of the digits in the first half of num must be equal to the sum of the digits in the second half. For Alice to win, the sums must not be equal.
- For example, if the game ended with
num = "243801", then Bob wins because2+4+3 = 8+0+1. If the game ended withnum = "243803", then Alice wins because2+4+3 != 8+0+3.
Assuming Alice and Bob play optimally, return true if Alice will win and false if Bob will win.
Example 1:
Input: num = "5023" Output: false Explanation: There are no moves to be made. The sum of the first half is equal to the sum of the second half: 5 + 0 = 2 + 3.
Example 2:
Input: num = "25??" Output: true Explanation: Alice can replace one of the '?'s with '9' and it will be impossible for Bob to make the sums equal.
Example 3:
Input: num = "?3295???" Output: false Explanation: It can be proven that Bob will always win. One possible outcome is: - Alice replaces the first '?' with '9'. num = "93295???". - Bob replaces one of the '?' in the right half with '9'. num = "932959??". - Alice replaces one of the '?' in the right half with '2'. num = "9329592?". - Bob replaces the last '?' in the right half with '7'. num = "93295927". Bob wins because 9 + 3 + 2 + 9 = 5 + 9 + 2 + 7.
Constraints:
2 <= num.length <= 105num.lengthis even.numconsists of only digits and'?'.
中文题目
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只包含数字字符和'?'。
通过代码
高赞题解
首先统计：
$sum_1-$ 游戏开始时，左侧不是 ? 的数字和。
$cnt_1-$ 游戏开始时，左侧 ? 的数量。
$sum_2-$ 游戏开始时，右侧不是 ? 的数字和。
$cnt_2-$ 游戏开始时，右侧 ? 的数量。
然后讨论：
如果 $(cnt1 + cnt2)$ 是奇数，那么最后一步肯定是 Alice 走，那么 Alice 可以放置任意数，一定赢。
如果 $(cnt1 + cnt2)$ 是偶数，则需要分类讨论，Alice 想让两个数不相等，无非就是大于和小于，也就是下面的两种情况：
情况一： Alice 希望到游戏结束时 $sum_1 > sum_2$。
Alice 必然在左侧的问号里面放 $9$，右侧的问号里面放 $0$。
此时如果 Bob 尽全力也无法挽回（也就是说，即使 Bob 在左侧的问号里放 $0$，右侧的问号里放 $9$，也无法改变游戏结束时 $sum_1 > sum_2$ 的结局），那么 Alice 必胜。怎样判断这样的情况呢？
设 Alice 在左侧的的问号里，放了 $a$ 个 $9$，
那么她还有 $\displaystyle{\frac{cnt_1 + cnt_2}{2} - a}$ 次操作，这些操作一定是在右侧的问号里，放了 $0$；
那么右侧还有 $\displaystyle{\left(cnt_2 - \left(\frac{cnt_1 + cnt_2}{2} - a\right)\right) = \frac{cnt_2 - cnt_1}{2} + a}$ 个问号留给了 Bob，Bob 一定在这些问号里放了 $9$；
这样，游戏结束后，左侧数字和 与 右侧数字和之差为
$$\begin{aligned} \Delta &= (9 \times a + sum_1) - \left(9 \times \left(\frac{cnt_2 - cnt_1}{2} + a\right) + sum_2\right) \ &= 9 \times \frac{cnt_1 - cnt2}{2} + sum_1 - sum_2 \end{aligned}$$
注意到，最终的差值与 $a$ 无关，只与 $cnt_1 - cnt_2$ 和 $sum_1 - sum_2$ 有关。
因此我们只需判断 $\Delta = \displaystyle{9 \times \frac{cnt_1 - cnt_2}{2} + sum_1 - sum_2} > 0$，即可确认 Alice 获胜。
情况二： Alice 希望到游戏结束时 $sum_1 < sum_2$。
同理可推，如果 $\Delta’ = \displaystyle{9 \times \frac{cnt_2 - cnt_1}{2} + sum_2 - sum_1} > 0$ 即可。
注意 $\Delta’ = -\Delta$，既然 $\Delta > 0$ 和 $\Delta < 0$ 的情况下必胜，也就是 $\Delta != 0$ 的情形下 Alice 必胜；否则必输。
我们无需讨论游戏开始时的 $sum_1$ 与 $sum_2$ 的大小关系。
即使游戏开始时，$sum_1 < sum_2$，Alice 也可以选择让游戏结束时 $sum_1 > sum_2$；
即使游戏开始时，$sum_1 > sum_2$，Alice 也可以选择让游戏结束时 $sum_1 < sum_2$。
（参见示例2）
代码
class Solution {
public:
bool sumGame(string num) {
int n = num.size(), sum1 = 0, cnt1 = 0, sum2 = 0, cnt2 = 0;
for(int i = 0; i < n / 2; ++i)
sum1 += (num[i] == '?' ? 0 : (num[i] - '0')), cnt1 += (num[i] == '?');
for(int i = n / 2; i < n; ++i)
sum2 += (num[i] == '?' ? 0 : (num[i] - '0')), cnt2 += (num[i] == '?');
if((cnt1 + cnt2) & 1) return true;
return 9 * (cnt1 - cnt2) / 2 + sum1 - sum2 != 0;
}
};统计信息
| 通过次数 | 提交次数 | AC比率 |
|---|---|---|
| 1917 | 4602 | 41.7% |
提交历史
| 提交时间 | 提交结果 | 执行时间 | 内存消耗 | 语言 |
|---|
