【算法题】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 <= 10^5
num.length 是 偶数 。
num 只包含数字字符和 ‘?’ 。

java代码：

class Solution {public boolean sumGame(String num) {int len = num.length();//1,为Alice采取左边尽可能小，2，Alice采取左边尽可能大int l1 = 0, r1 = 0, l2 = 0, r2 = 0, m = len / 2;int flag = 0;for(int i = 0; i < len; i++){char c = num.charAt(i);if(i < m){if(c == '?'){if(flag == 0){l2 += 9;flag = 1;}else{l1 += 9;flag = 0;}}else{l1 += c - '0';l2 += c - '0';}}else{if(c == '?'){if(flag == 0){r1 += 9;flag = 1;}else{r2 += 9;flag = 0;}}else{r1 += c - '0';r2 += c - '0';}}}return !(l1 >= r1 && l2 <= r2);}
}