【Day26】810.黑板异或游戏

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

题解:

class Solution {
public:
    bool xorGame(vector& nums) {
        //数组元素个数是奇数/偶数,有决定性作用:
        //如果是偶数,先手必胜;
        //如果是奇数,只有当一上来所有元素异或的结果为0,先手才获胜,
        //否则,接下来轮到后手,此时元素个数为偶数,则后手必胜,先手必败!
        int len = nums.size(), t = 0;
        if(len % 2)
        {
            for(auto& x:nums) t ^= x; //所有元素异或的结果
            if(t) return false;
            else return true;
        }
        else return true;
    }
};

   转载规则


《【Day26】810.黑板异或游戏》 Tyzhao 采用 知识共享署名 4.0 国际许可协议 进行许可。
 上一篇
【Day27】1707.与数组中元素的最大异或值 【Day27】1707.与数组中元素的最大异或值
1707. 与数组中元素的最大异或值给你一个由非负整数组成的数组 nums 。另有一个查询数组 queries ,其中 queries[i] = [xi, mi] 。 第 i 个查询的答案是 xi 和任何 nums 数组中不超过 mi 的元
2021-05-23
下一篇 
【Day25】1035.不相交的线 【Day25】1035.不相交的线
1035. 不相交的线在两条独立的水平线上按给定的顺序写下 nums1 和 nums2 中的整数。 现在,可以绘制一些连接两个数字 nums1[i] 和 nums2[j] 的直线,这些直线需要同时满足满足: nums1[i] == num
2021-05-21
  目录