810. 黑板异或游戏

Hard

题目描述

给你一个整数数组 nums 表示黑板上写的数字。

Alice 和 Bob 轮流从黑板上擦掉恰好一个数字，Alice 先手。如果擦除一个数字后，剩余所有数字按位异或运算得到 0，则当前玩家败。只有一个数字时，按位异或运算的结果是该数字本身；没有数字时，按位异或运算的结果是 0。

同时，如果任何一个玩家在其回合开始时，黑板上所有数字按位异或运算结果等于 0，则该玩家获胜。

假设两个玩家都采用最优策略，如果 Alice 获胜则返回 true，否则返回 false。

示例 1：

输入：nums = [1,1,2]
输出：false
解释：
Alice 有两个选择：擦掉 1 或擦掉 2。
如果她擦掉 1，nums 数组变成 [1, 2]。剩余数字按位异或得到 1 XOR 2 = 3。现在 Bob 可以擦掉任意数字，因为 Alice 将擦掉最后一个数字并败北。
如果 Alice 先擦掉 2，现在 nums 变成 [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^16

解题思路

这是一道博弈论题目，需要分析 Alice 获胜的条件。

核心观察：

1. 如果游戏开始时所有数字的异或值为 0，Alice 直接获胜
2. 如果游戏开始时所有数字的异或值不为 0，需要分析数组长度：
   • 若数组长度为偶数，Alice 必胜
   • 若数组长度为奇数，Alice 必败

数学证明：

设所有数字的异或值为 S。对于任意数字 x，如果移除 x 后剩余数字异或值为 0，则有：S ⊕ x = 0，即 x = S。

• 当 S ≠ 0 且数组长度为偶数时：Alice 总能选择一个不等于 S 的数字（因为如果所有数字都等于 S，那么偶数个相同数字的异或值应为 0，与 S ≠ 0 矛盾）
• 当 S ≠ 0 且数组长度为奇数时：如果存在不等于 S 的数字，Alice 可以移除它；如果所有数字都等于 S，移除任意一个都会让 Bob 面临偶数长度且异或值为 S ≠ 0 的局面，此时 Bob 必胜

因此，Alice 获胜的条件是：S = 0 或 数组长度为偶数。

代码实现

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

class Solution:
    def xorGame(self, nums: List[int]) -> bool:
        xor_sum = 0
        for num in nums:
            xor_sum ^= num
        return xor_sum == 0 or len(nums) % 2 == 0

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

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var xorGame = function(nums) {
    let xor = 0;
    for (let num of nums) {
        xor ^= num;
    }
    return xor === 0 || nums.length % 2 === 0;
};

复杂度分析