求和游戏

2021-07-11

5794. 求和游戏

难度中等2收藏分享切换为英文接收动态反馈

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：

1
2
3

输入：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 <= 105
num.length 是偶数。
num 只包含数字字符和 '?' 。

数学

分类讨论：
1、因为Alice先手，所以如果问号个数为奇数，则Alice必赢（Alice做最后一次问号置换）；
2、统计前后部分数字和，分为三种情况：
三点结论：
【1】由于Alice和Bob都做最优策略，所以左右两边的问号数目可以抵消（彼此做相反策略），且抵消后剩余问号数目一定为偶数（问号总数为奇数的情况已经被排除，precnt + postcnt为偶数，则abs(precnt - postcnt)必为偶数），抵消问号后，仅讨论剩余问号一侧。
【2】问号置换为的数字可以认为只有0和9，剩余问号个数为偶数个，每两个为一个周期，Alice只有两种策略（走极端）：1、增大，Alice回合置换问号为9（Bob阻止，Bob回合置换问号为0）；2、减小，Alice回合置换问号为0（Bob阻止，Bob回合置换问号为9），所以，每个周期剩余问号一侧都会增加9，如果最终两侧相等，则Bob赢，否则Alice赢。
【3】有剩余问号一侧只增不减。
所以，
(1) presum > postsum，如果precnt >= postcnt，则Alice必赢（结论【3】）；如果precnt < postcnt，则return (postcnt - precnt) / 2 * 9 + postsum != presum（结论【2】）。
(2) presum == postsum，如果precnt == postcnt，前后问号两相抵消（结论【1】），Bob赢，否则，Alice赢。
(3) presum < postsum，与（1）同理。
注：
presum — 前半部分数字和
postsum — 后半部分数字和
precnt — 前半部分问号数
postcnt — 后半部分问号数

class Solution {
public boolean sumGame(String num) {
        int n = num.length();
        int sum = 0;
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            char ch = num.charAt(i);
            if (i < n / 2) {
                if (ch == '?') cnt++;
                else sum += (ch - '0');
            } else {
                if (ch == '?') cnt--;
                else sum -= (ch - '0');
            }
        }
        if (cnt % 2 == 1) return true;
        else if (sum == cnt / 2 * -9) return false;
        else return true;
    }
}

作者：mei-mi-xiao-gan-xing
链接：https://leetcode-cn.com/problems/sum-game/solution/mo-ni-yi-xia-si-lu-by-mei-mi-xiao-gan-xi-nnuf/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

作者：Faith_Previal
链接：https://leetcode-cn.com/problems/sum-game/solution/alice-ke-jin-kai-gua-de-xie-beats-shuang-8gu8/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。