黑板异或游戏

难度: Hard

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

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

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

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

示例 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

示例 3:

输入: nums = [1,2,3]
输出: true

提示：

1 <= nums.length <= 1000
0 <= nums[i] < 2¹⁶

Submission

运行时间: 22 ms

内存: 16.1 MB

class Solution:
    @staticmethod
    def xorGame(nums: list[int], /) -> bool:
        if len(nums) & 1 == 0:
            return True
        a = 0
        for num in nums:
            a ^= num
        return a == 0

Explain

该题解的思路是利用异或运算的性质来判断游戏的结果。异或运算具有以下性质：对于任意两个数字 a 和 b，有 a ^ b ^ b = a。在本题中，如果数组的长度为偶数，那么无论 Alice 如何选择，Bob 总是可以选择一个数字，使得剩余数字的异或结果等于 0，从而让 Alice 输掉游戏。如果数组的长度为奇数，那么 Alice 只有在数组的异或结果为 0 时才能获胜。因此，该题解先判断数组长度的奇偶性，如果为偶数直接返回 True。如果为奇数，则计算整个数组的异或结果，如果结果为 0 则返回 True，否则返回 False。

时间复杂度: O(n)

空间复杂度: O(1)

class Solution:
    @staticmethod
    def xorGame(nums: list[int], /) -> bool:
        # 如果数组长度为偶数，Alice 总是会输
        if len(nums) & 1 == 0:
            return True
        # 计算整个数组的异或结果
        a = 0
        for num in nums:
            a ^= num
        # 如果异或结果为 0，Alice 获胜；否则 Alice 输
        return a == 0

Explore

题解的这个假设是不完全正确的。在具有偶数个元素的数组中，Alice不一定总是输。关键因素是数组元素的具体值和每轮选择的策略。如果整个数组的异或总和为0，Alice可以通过合适的策略确保每次移除元素后剩余的数组元素的异或总和仍为0，从而最终获胜。但如果数组的异或总和不为0，那么Bob将有方法确保Alice最终面对一个非零异或总和，从而Alice会输。因此，Alice在偶数长度的数组中能获胜的关键是数组的异或总和需要为0。

题解没有考虑所有可能的数字组合和擦除策略。实际上，Alice的输赢取决于她的选择策略和数组的异或总和。如果数组的异或总和为0，Alice可以采取策略保持这个状态，最终获胜。如果异或总和不为0，那么不论数组的长度是奇是偶，最终Alice都将输掉游戏。因此，题解的一般化结论是有误的，应该更详细考虑数组元素和游戏策略。

题解所述方法在判断Alice是否有可能获胜时通常有效，但它依赖于数组元素的初始状态。如果数组长度为奇数且异或结果为0，Alice可以获胜，因为她可以采取策略始终保持异或结果为0。如果不为0，Alice将无法获胜。在数组长度为偶数时，如果异或结果不为0，Bob可以获胜。因此，这种方法可以有效判断Alice的潜在获胜可能性，但具体获胜策略还需要根据实际游戏情况动态调整。

使用`len(nums) & 1 == 0`来判断数组长度是否为偶数是一种位运算的方法，它的优势在于执行速度通常比传统的除法运算要快，因为它直接操作整数的二进制表示。这种方法检查最低位是否为0（即是否为偶数）。等效的方法包括使用`len(nums) % 2 == 0`，这是最常见的方式。尽管两者在功能上等效，但在低层次的计算优化上，位运算可能有更好的性能。