位运算题目：黑板异或游戏

题目

标题和出处

标题：黑板异或游戏

出处：810. 黑板异或游戏

难度

8 级

题目描述

要求

给定一个整数数组 $\text{nums}$，表示写在黑板上的数字。

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

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

假设两个玩家使用最优策略，当且仅当 Alice 获胜时返回 $\text{true}$。

示例

示例 1：

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

示例 2：

输入：$\text{nums = [0,1]}$
输出：$\text{true}$

示例 3：

输入：$\text{nums = [1,2,3]}$
输出：$\text{true}$

数据范围

• $\text{1}\le \text{nums.length}\le \text{1000}$
• $\text{0}\le \text{nums[i]}<{\text{2}}^{\text{16}}$

解法

思路和算法

如果初始时数组 $\text{nums}$ 中的所有数字的按位异或运算结果是 $0$，则 Alice 获胜。以下考虑初始时数组 $\text{nums}$ 中的所有数字的按位异或运算结果不是 $0$ 的情况。

如果 Alice 面临失败，则只有一种情况：Alice 擦掉数字之前，剩余的所有数字的按位异或运算结果不是 $0$，且 Alice 擦掉任意一个数字之后，剩余的所有数字的按位异或运算结果是 $0$。

用 $n$ 表示数组 $\text{nums}$ 的长度，用 $X$ 表示数组 $\text{nums}$ 中的所有数字的按位异或运算结果：

$$X=\text{nums}[0]\oplus \text{nums}[1]\oplus \dots \oplus \text{nums}[n-1]\ne 0$$

对于 $0\le i<n$，用 $X_i$ 表示擦掉 $\text{nums}[i]$ 之后剩余的所有数字的按位异或运算结果，则对于每个 $0\le i<n$ 都有 $X_i=0$。用 $Y$ 表示所有 $X_i$ 的按位异或运算结果：

$$Y=X_0\oplus X_1\oplus \dots \oplus X_{n-1}=0$$

对于每个 $0\le i<n$ 都有 $X=X_i\oplus \text{nums}[i]$，等价于 $X_i=X\oplus \text{nums}[i]$，代入 $Y$ 的表达式，用 $X^{(n)}$ 表示 $n$ 个 $X$ 的按位异或运算结果：

$$Y=X^{(n)}\oplus (\text{nums}[0]\oplus \text{nums}[1]\oplus \dots \oplus \text{nums}[n-1])=X^{(n)}\oplus X=X^{(n+1)}$$

由于 $Y=0$，因此 $X^{(n+1)}=0$，即 $n+1$ 个 $X$ 的按位异或运算结果是 $0$。由于 $X\ne 0$，因此只有当 $n+1$ 是偶数即 $n$ 是奇数时，上式才可能成立。当 $n$ 是偶数时，Alice 一定可以找到一个数字，擦掉该数字之后，剩余的所有数字的按位异或运算的结果不是 $0$，因此 Alice 可以获胜。

根据上述分析，只要满足以下两个条件之一，Alice 就能获胜：

• 初始时数组 $\text{nums}$ 中的所有数字的按位异或运算结果是 $0$；

• 初始时数组 $\text{nums}$ 的长度是偶数。

实现方面，可以首先判断数组 $\text{nums}$ 的长度的奇偶性，如果数组长度是偶数则直接返回 $\text{true}$，只有当数组长度是奇数时才需要遍历数组计算按位异或运算结果是否为 $0$，该做法对于数组长度是偶数的情形的时间复杂度是 $O(1)$。

代码

class Solution {public boolean xorGame(int[] nums) {if (nums.length % 2 == 0) {return true;}int xor = 0;for (int num : nums) {xor ^= num;}return xor == 0;}
}

复杂度分析

• 时间复杂度：$O(n)$，其中 $n$ 是数组 $\text{nums}$ 的长度。当 $n$ 是偶数时直接返回 $\text{true}$，时间复杂度是 $O(1)$，当 $n$ 是奇数时需要遍历数组计算所有数字的按位异或运算结果，时间复杂度是 $O(n)$，因此最差情况的时间复杂度是 $O(n)$。

• 空间复杂度：$O(1)$。