0810. 黑板异或游戏

ITCharge大约 3 分钟

---

0810. 黑板异或游戏

标签：位运算、脑筋急转弯、数组、数学、博弈
难度：困难

题目链接

0810. 黑板异或游戏 - 力扣

题目大意

描述：

黑板上写着一个非负整数数组 $nums[i]$ 。

Alice 和 Bob 轮流从黑板上擦掉一个数字，Alice 先手。如果擦除一个数字后，剩余的所有数字按位异或运算得出的结果等于 0 的话，当前玩家游戏失败。另外，如果只剩一个数字，按位异或运算得到它本身；如果无数字剩余，按位异或运算结果为 0。

并且，轮到某个玩家时，如果当前黑板上所有数字按位异或运算结果等于 0，这个玩家获胜。

要求：

假设两个玩家每步都使用最优解，当且仅当 Alice 获胜时返回 true， $Bob$ 获胜时返回 false。

说明：

$1 \le nums.length \le 10^{3}$ 。
$0 \le nums[i] \lt 2^{16}$ 。

示例：

示例 1：

输入: nums = [1,1,2]
输出: false
解释: 
Alice 有两个选择: 擦掉数字 1 或 2。
如果擦掉 1, 数组变成 [1, 2]。剩余数字按位异或得到 1 XOR 2 = 3。那么 Bob 可以擦掉任意数字，因为 Alice 会成为擦掉最后一个数字的人，她总是会输。
如果 Alice 擦掉 2，那么数组变成[1, 1]。剩余数字按位异或得到 1 XOR 1 = 0。Alice 仍然会输掉游戏。

示例 2：

输入: nums = [0,1]
输出: true

解题思路

思路 1：博弈论 + 数学

这道题是一个博弈问题，需要分析在最优策略下谁会获胜。

关键观察：

如果初始状态所有数字的异或结果为 0，Alice 直接获胜。
如果数组长度为偶数，Alice 必胜。原因如下：
- 假设所有数字的异或结果为 $x \neq 0$ 。
- 由于异或运算的性质，至少有一个数字 $nums[i]$ 使得 $x \oplus nums[i] \neq 0$ （否则所有数字异或结果为 0）。
- 在 Alice 的回合，如果她无法找到一个数字使得擦除后异或结果不为 0，说明擦除任何数字后异或结果都为 0，这意味着所有数字都相同且等于 $x$ 。
- 但如果所有数字都相同，数组长度为偶数时，异或结果应该为 0，矛盾。
- 因此，Alice 总能找到一个数字擦除，使得游戏继续，最终 Bob 会面临奇数个数字的局面。
如果数组长度为奇数且异或结果不为 0，Bob 必胜。

结论：Alice 获胜的条件是：初始异或结果为 0，或数组长度为偶数。

思路 1：代码

class Solution:
    def xorGame(self, nums: List[int]) -> bool:
        # 计算所有数字的异或结果
        xor_sum = 0
        for num in nums:
            xor_sum ^= num
        
        # Alice 获胜的条件：异或结果为 0，或数组长度为偶数
        return xor_sum == 0 or len(nums) % 2 == 0

思路 1：复杂度分析

时间复杂度： $O(n)$ ，其中 $n$ 是数组的长度。需要遍历数组计算异或结果。
空间复杂度： $O(1)$ ，只使用常数额外空间。