本文涉及知识点

博弈论 数学

LeetCode1927. 求和游戏

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⁵
num.length 是 偶数 。
num 只包含数字字符和 ‘?’ 。

博弈论

性质一：如果有奇数个*，则Alice必胜。最后一个操作是Alice，此时顶多只有一个数可以让左右两部分相等。Alice选择此数外的任意数字，必胜。
性质二：如果左右都只有一个*，则排除后，左右相等，Bom胜；不等,Alice。相等，Alice选择x,Bom则对面选择x。如果不等，不失一般性，假定左边大，则在左边选择9，右边选择0。这样差距无法缩小。
性质三：如果左边（右边)，有偶数个，右边(左边)没有。2个换成9，左右相等，则Bom胜；否则，Alice胜利。相等，Alice选择x,Bom选择9-x。不等，如果左边小，Alice选择0，Bom无论选择什么，都不会让左边变大。
性质四：左右的号抵消后，2个号相当于9。不失一般性，假定左边的多。
如果左右相等，则Bom必胜。如果Alice选择右边的x，则Bom选择左边的x。如果Alice选择左边的x，如果右边有*，则选择右边的x；否则选择左边的9-x。
如果不等则Alice必胜。如果左边大，Alice选择左边的9，Bom无论选择什么都无法减少差距。
结论：如果为奇数，则Alice必胜；否则两个号算9，不等则Alice胜，相等则Bom胜。

代码

核心代码

class Solution {
		public:
			bool sumGame(string num) {
				const int N = num.length();
				int i = 0;
				int ans = 0,cnt=0;
				for (; i < N / 2; i++) {
					if ('?' == num[i]) { cnt++; continue; }
					ans += num[i] - '0';
				}
				for (; i < N; i++) {
					if ('?' == num[i]) { cnt--; continue; }
					ans -= num[i] - '0';
				}
				if (cnt & 1) { return true; }
				ans += cnt / 2 * 9;
				return 0 != ans;
			}
		};

单元测试

string num;
		TEST_METHOD(TestMethod1)
		{
			num = "5023";
			auto res = Solution().sumGame(num);
			AssertEx(false, res);
		}
		TEST_METHOD(TestMethod2)
		{
			num = "25??";
			auto res = Solution().sumGame(num);
			AssertEx(true, res);
		}
		TEST_METHOD(TestMethod3)
		{
			num = "?3295???";
			auto res = Solution().sumGame(num);
			AssertEx(false, res);
		}
		TEST_METHOD(TestMethod4)
		{
			num = "8?6?90?5";
			auto res = Solution().sumGame(num);
			AssertEx(true, res);
		}