LeetCode 题解工作台
黑板异或游戏
黑板上写着一个非负整数数组 nums[i] 。 Alice 和 Bob 轮流从黑板上擦掉一个数字，Alice 先手。如果擦除一个数字后，剩余的所有数字按位异或运算得出的结果等于 0 的话，当前玩家游戏失败。 另外，如果只剩一个数字，按位异或运算得到它本身；如果无数字剩余，按位异或运算结果为 0 。 …
5
题型
4
代码语言
3
相关题
当前训练重点
困难 · 数组·数学
答案摘要
根据游戏规则，轮到某个玩家时，如果当前黑板上所有数字按位异或运算结果为 ，这个玩家获胜。由于 Alice 先手，因此当 中所有数字的异或结果为 时，Alice 可以获胜。 当 中所有数字的异或结果不为 时，我们不妨考虑从数组 的长度奇偶性来分析 Alice 的获胜情况。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·数学 题型思路
题目描述
黑板上写着一个非负整数数组 nums[i] 。
Alice 和 Bob 轮流从黑板上擦掉一个数字，Alice 先手。如果擦除一个数字后，剩余的所有数字按位异或运算得出的结果等于 0 的话，当前玩家游戏失败。 另外，如果只剩一个数字，按位异或运算得到它本身；如果无数字剩余，按位异或运算结果为 0。
并且，轮到某个玩家时，如果当前黑板上所有数字按位异或运算结果等于 0 ，这个玩家获胜。
假设两个玩家每步都使用最优解，当且仅当 Alice 获胜时返回 true。
示例 1：
输入: 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 仍然会输掉游戏。
示例 2:
输入: nums = [0,1] 输出: true
示例 3:
输入: nums = [1,2,3] 输出: true
提示：
1 <= nums.length <= 10000 <= nums[i] < 216
解题思路
方法一：位运算
根据游戏规则，轮到某个玩家时，如果当前黑板上所有数字按位异或运算结果为 ，这个玩家获胜。由于 Alice 先手，因此当 中所有数字的异或结果为 时，Alice 可以获胜。
当 中所有数字的异或结果不为 时，我们不妨考虑从数组 的长度奇偶性来分析 Alice 的获胜情况。
当 的长度为偶数时，如果 Alice 必败，那么只有一种情况，就是 Alice 无论擦掉哪个数字，剩余所有数字的异或结果都等于 。我们来分析一下是否存在这种情况。
假设数组 长度为 ，并且 是偶数，记所有数字异或结尾为 ，则有：
我们记 为数组 擦掉第 个数字后的异或结果，那么有：
等式两边同时异或 ，得到：
如果无论 Alice 擦掉哪个数字，剩余所有数字的异或结果都等于 ，那么对所有 ，都有 ，即：
我们将 代入上式，得到：
上式共有 （偶数）个 ，而 也等于 ，因此上式等价于 。这与 矛盾，因此不存在这种情况。因此当 的长度为偶数时，Alice 必胜。
如果长度为奇数，那么 Alice 擦掉一个数字后，剩余数字个数为偶数，也就是将偶数长度的情况留给 Bob，那么 Bob 必胜，也即 Alice 必败。
综上，当 的长度为偶数，或者 中所有数字的异或结果为 时，Alice 可以获胜。
时间复杂度 ，其中 为数组 的长度。空间复杂度 。
class Solution:
def xorGame(self, nums: List[int]) -> bool:
return len(nums) % 2 == 0 or reduce(xor, nums) == 0
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(N) |
| 空间 | O(1) |
面试官常问的追问
外企场景- question_mark
Candidates should demonstrate an understanding of game theory principles and XOR operations in an array.
- question_mark
Look for the ability to think ahead and simulate potential moves based on XOR outcomes.
- question_mark
Assess the candidate's ability to optimize the solution using bit manipulation rather than brute force.
常见陷阱
外企场景- error
Overlooking the initial XOR value and immediately assuming that Alice loses.
- error
Failing to correctly simulate the sequence of moves and understanding the implications of each player’s move on the overall XOR value.
- error
Misunderstanding the game theory aspect, especially with regard to whether Alice or Bob has the advantage based on the array length and the XOR value.
进阶变体
外企场景- arrow_right_alt
What if Alice and Bob can erase multiple elements in a turn? How does that change the strategy?
- arrow_right_alt
Consider the game with a different number of players and analyze how it affects the XOR game theory.
- arrow_right_alt
What if the XOR operation is replaced with a different binary operation, like AND or OR? How does that impact the game strategy?