万年县建设银行网站拼音全称,用微信登陆 wordpress,北京联通网站备案,中国空间站机械臂题目#xff1a;
Alice 和 Bob 玩一个游戏#xff0c;两人轮流行动#xff0c;Alice 先手 。
给你一个 偶数长度 的字符串 num #xff0c;每一个字符为数字字符或者 ‘?’ 。每一次操作中#xff0c;如果 num 中至少有一个 ‘?’ #xff0c;那么玩家可以执行以下操…题目
Alice 和 Bob 玩一个游戏两人轮流行动Alice 先手 。
给你一个 偶数长度 的字符串 num 每一个字符为数字字符或者 ‘?’ 。每一次操作中如果 num 中至少有一个 ‘?’ 那么玩家可以执行以下操作
选择一个下标 i 满足 num[i] ‘?’ 。 将 num[i] 用 ‘0’ 到 ‘9’ 之间的一个数字字符替代。 当 num 中没有 ‘?’ 时游戏结束。
Bob 获胜的条件是 num 中前一半数字的和 等于 后一半数字的和。Alice 获胜的条件是前一半的和与后一半的和 不相等 。
比方说游戏结束时 num “243801” 那么 Bob 获胜因为 243 801 。如果游戏结束时 num “243803” 那么 Alice 获胜因为 243 ! 803 。 在 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采取左边尽可能小2Alice采取左边尽可能大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);}
}
