力扣 810. 黑板异或游戏

题目描述

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

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

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

示例 ：

 输入: 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 仍然会输掉游戏。  

提示 ：

• 1 <= N <= 1000
• 0 <= nums[i] <= 2^16

解决方案

方法一：数学

下文将「按位异或运算」简称为「异或」。

根据游戏规则，轮到某个玩家时，如果当前黑板上所有数字异或结果等于 0，则当前玩家获胜。由于 Alice 是先手，因此如果初始时黑板上所有数字异或结果等于 0，则 Alice 获胜。

下面讨论初始时黑板上所有数字异或结果不等于 0 的情况。

由于两人交替擦除数字，且每次都恰好擦掉一个数字，因此对于这两人中的任意一人，其每次在擦除数字前，黑板上剩余数字的个数的奇偶性一定都是相同的。

这启发我们从数组 nums 长度的奇偶性来讨论。如果 nums 的长度是偶数，先手 Alice 是否有可能失败呢？假设 Alice 面临失败的状态，则只有一种情况，即无论擦掉哪一个数字，剩余所有数字的异或结果都等于 0。

下面证明这是不可能的。设数组 nums 的长度为 n，n 是偶数，用

表示异或，记 S 为数组 nums 的全部元素的异或结果，则有

记 Si 为擦掉 nums[i] 之后，剩余所有数字的异或结果，则有

等式两边同时异或 nums[i]，由于对任意整数 x 都有

，得

如果无论擦掉哪一个数字，剩余的所有数字异或结果都等于 0，即对任意

，都有

。因此对所有的 Si 异或结果也等于 0，即

将

代入上式，并根据异或运算的交换律和结合律化简，有

上述计算中，第 3 行的左边括号为 n 个 S 异或，由于 n 是偶数，因此 n 个 S 异或的结果是 0。

根据上述计算，可以得到 S = 0，与实际情况

矛盾。

因此当数组的长度是偶数时，先手 Alice 总能找到一个数字，在擦掉这个数字之后剩余的所有数字异或结果不等于 0 。

在 Alice 擦掉这个数字后，黑板上剩下奇数个数字，无论 Bob 擦掉哪个数字，留给 Alice 的一定是黑板上剩下偶数个数字，此时 Alice 要么获胜，要么仍可以找到一个数字，在擦掉这个数字之后剩余的所有数字异或结果不等于 0，因此 Alice 总能立于不败之地。

同理可得，当数组的长度是奇数时，Alice 在擦掉一个数字之后，留给 Bob 的一定是黑板上剩下偶数个数字，因此 Bob 必胜。

综上所述，当且仅当以下两个条件至少满足一个时，Alice 必胜：

• 数组 nums 的全部元素的异或结果等于 0；
• 数组 nums 的长度是偶数。

代码实现时，可以先判断数组 nums 的长度是否是偶数，当长度是偶数时直接返回 true，当长度是奇数时才需要遍历数组计算全部元素的异或结果。该实现方法在数组长度是偶数时只需要 O(1) 的时间即可得到答案。

Java

 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;
    }
}  

C#

 public class Solution {
    public bool XorGame(int[] nums) {
        if (nums.Length % 2 == 0) {
            return true;
        }
        int xor = 0;
        foreach (int num in nums) {
            xor ^= num;
        }
        return xor == 0;
    }
}  

JavaScript

 var xorGame = function(nums) {
    if (nums.length % 2 == 0) {
        return true;
    }
    let xor = 0;
    for (const num of nums) {
        xor ^= num;
    }
    return xor == 0;
};  

Golang

 func xorGame(nums []int) bool {
    if len(nums)%2 == 0 {
        return true
    }
    xor := 0
    for _, num := range nums {
        xor ^= num
    }
    return xor == 0
}  

Python3

 class Solution:
    def xorGame(self, nums: List[int]) -> bool:
        if len(nums) % 2 == 0:
            return True
        
        xorsum = reduce(xor, nums)
        return xorsum == 0  

C++

 class Solution {
public:
    bool xorGame(vector<int>& nums) {
        if (nums.size() % 2 == 0) {
            return true;
        }
        int xorsum = 0;
        for (int num : nums) {
            xorsum ^= num;
        }
        return xorsum == 0;
    }
};  

C

 bool xorGame(int* nums, int numsSize) {
    if (numsSize % 2 == 0) {
        return true;
    }
    int xorsum = 0;
    for (int i = 0; i < numsSize; i++) {
        xorsum ^= nums[i];
    }
    return xorsum == 0;
}  

复杂度分析

• 时间复杂度：O(n)，其中 n 是数组 nums 的长度。最坏情况下，需要遍历数组一次，计算全部元素的异或结果。
• 空间复杂度：O(1)。

本文作者：力扣

声明：本文归“力扣”版权所有，如需转载请联系。