WNJXYK
Thanks to the cruel world.
WNJXYKのBlog
LeetCode 810. 黑板异或游戏
LeetCode 810. 黑板异或游戏

因为数学菜,我还是直接翻译英文网站的题解好了。https://leetcode.com/articles/chalkboard-xor-game/

810. 黑板异或游戏 / 810. Chalkboard XOR Game

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

换种说法就是,轮到某个玩家时,如果当前黑板上所有数字按位异或运算结果等于 0,这个玩家获胜。

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

示例:
输入: nums = [1, 1, 2]
输出: false
解释:
小红有两个选择: 擦掉数字 1 或 2。
如果擦掉 1, 数组变成 [1, 2]。剩余数字按位异或得到 1 XOR 2 = 3。那么小明可以擦掉任意数字,因为小红会成为擦掉最后一个数字的人,她总是会输。
如果小红擦掉 2,那么数组变成[1, 1]。剩余数字按位异或得到 1 XOR 1 = 0。小红仍然会输掉游戏。

说明:

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

方法一: 数学 [通过]

思路与算法

正如题目描述里说的一样, 如果整个数组的异或和0的话,那么小红就赢了。

如果在任何擦数字的过程中异或和都不会为0, 那么显然两个人只能一人一步走,当且仅当当数组的大小为偶数的时候小红才可能获胜。

现在,跳出当前这个思路,事实上, 当数组个数是偶数的时候,小红总是可以安全的擦掉一个数字的。假设 S=x_1\oplus x_2\oplus \cdots x_n \neq 0,却没办法擦掉任何一个数字使得异或和不为0,即 (S\oplus x_i = 0),那么可以推知(S\oplus x_1) \oplus (S\oplus x_2) \oplus \cdots \oplus(S\oplus x_n) = (S\oplus \cdots S)\oplus(x_1\oplus x_2 \oplus \cdots \oplus x_n) = 0 \oplus S \neq 0 , 这是矛盾的,假设不成立。

相似的, 数组中有奇数个数字的情况也可以类推。所以轮到小明时,黑板上有奇数的元素的情况下,他总是可以安全地擦掉一个数字。 所以答案就是数组中元素个数的奇偶性。

熟悉SG定理的人可以能会知道这个游戏是一个misère-form game, 也就是说SG定理的方法对这个问题并不使用,同时也暗示这个问题可能有一个很简单的解法

复杂度分析

  • 时间复杂度:O(N), N是数组nums的长度

  • 空间复杂度:O(1)

赞赏
https://secure.gravatar.com/avatar/f83b57c055136369e9feba5d6671d6b5?s=256&r=g

WNJXYK

文章作者

一个蒟蒻

推荐文章

发表评论

textsms
account_circle
email

WNJXYKのBlog

LeetCode 810. 黑板异或游戏
因为数学菜,我还是直接翻译英文网站的题解好了。https://leetcode.com/articles/chalkboard-xor-game/ 810. 黑板异或游戏 / 810. Chalkboard XOR Game 一个黑板上写着一个非负整数…
扫描二维码继续阅读
2019-01-02
<--! http2https -->