网页设计教程详细步骤,枣庄做网站优化,seo是什么服务,做旅游网站的关注与回复黑板上写着一个非负整数数组 nums[i] 。Alice 和 Bob 轮流从黑板上擦掉一个数字#xff0c;Alice 先手。如果擦除一个数字后#xff0c;剩余的所有数字按位异或运算得出的结果等于 0 的话#xff0c;当前玩家游戏失败。 (另外#xff0c;如果只剩一个数字#xff0c;按位异…黑板上写着一个非负整数数组 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 仍然会输掉游戏。
解题思路
奇偶不变
因为ALice和Bob是轮流取数字的所以如果刚开始的元素个数是偶数个那么Alice每次取元素时元素都是偶数。
S^nums[i]Si
设Si为数组去掉第i个元素以后的异或的结果S为所有元素异或的结果,即有Sinums[i]S变形得Snums[i]Si
反证法
在数组长度为偶数并且S!0(因为如果S0那么就胜负已经确定了)的情况假设无论取走的元素是哪个都有Si0 即S00S10…,等价于S0S1S2…0,代入S^nums[i]Si得
(S^nums[0])^(S^nums[1])^....0
(S^S...)^(nums[0]^nums[1]....)0
又因为S为所有元素异或的结果并且数组长度为偶数所以有偶数个S因此
S^S…(奇数个S)0即S0与S0矛盾,所以可以得出无论取走的元素是哪个都不存在Si0也就是说数组长度为偶数的那一方可以使得另一方永远产生不了剩下元素异或结果为0的情况。
所以Alice要想赢只需要两种情况
原数组异或的结果是0因为Alice是先手所以直接就赢了原数组的长度为偶数
代码
class Solution {public boolean xorGame(int[] nums) {int res0;if((nums.length1)0) return true;for (int num : nums) {res^num;}return res0;}
}
