难度: Medium
Submission
运行时间: 24 ms
内存: 16.6 MB
class Solution:
def nimGame(self, piles: List[int]) -> bool:
tmp = 0
for num in piles:
tmp ^= num
return bool(tmp)
Explain
该题目是Nim游戏的变种，游戏的基本规则是两个玩家轮流从任意数量的堆中取石子，每次至少取一个，最多可以取走整个堆的石子。游戏的目标是避免取到最后一个石子。解题的关键在于利用Nim游戏的经典解法，即使用Nim和（异或和）来判断游戏的胜负。若Nim和不为0，则先手必胜；若为0，则先手必败。题解中，通过对所有堆的石子数进行异或操作，计算出Nim和，从而判断先手玩家的胜负情况。
时间复杂度: O(n)
空间复杂度: O(1)
class Solution:
def nimGame(self, piles: List[int]) -> bool:
tmp = 0 # 初始化Nim和为0
for num in piles: # 遍历每个堆
tmp ^= num # 使用异或操作计算Nim和
return bool(tmp) # 如果Nim和非零，返回True（先手必胜）；否则返回False（先手必败）
Explore
异或操作在Nim游戏中用于计算Nim和，是因为它满足Nim游戏的数学性质。Nim和通过异或运算计算，其中异或运算有如下特性：任何数与其自身异或的结果是0，任何数与0异或是其自身。这意味着，如果所有堆的石子数异或结果为0，则所有堆可以通过适当的移动配对变为0，此时无论先手做何种移动，后手总能找到一种对应移动使得局面保持平衡（每次移动后Nim和仍为0），直到游戏结束。如果Nim和不为0，则存在至少一个堆，使得先手玩家可以通过移动改变当前局面，使Nim和变为0，从而将胜利的机会留给自己。
这一规则基于博弈论中的Nim游戏理论。在Nim游戏中，游戏的状态可以通过堆中石子数的异或和（Nim和）来描述。如果Nim和为0，意味着当前的游戏状态是一个必败态，因为任何合法的移动都将导致Nim和变为非0状态，即转移到一个必胜态，后手玩家可以继续保持这一优势。相反，如果Nim和非0，表示游戏处于一个必胜态，先手玩家可以通过特定的移动使得Nim和变为0，迫使对手进入必败态。这是一个通过数学归纳法可以证明的结果。
在计算Nim和的过程中，堆中石子数量的分布大小不会影响算法的效率。无论石子数量多少，异或操作的时间复杂度都是O(1)，因此，总的时间复杂度仅取决于堆的数量，即O(n)，其中n是堆的数量。异或操作是位运算，其速度非常快，不受操作数大小的影响。因此，石子数的极端分布不会改变算法的总体效率。