难度: Hard
Submission
运行时间: 35 ms
内存: 16.0 MB
class Solution:
def findGameWinner(self, n: int) -> bool:
sg1, sg2 = 0, 1
for _ in range(n-1):
t = (sg1+1)^(sg2+1)
sg1, sg2 = t, sg1
return bool(sg1)
Explain
此题解基于斐波那契数列的分析，采用了Sprague-Grundy定理。每个节点的SG值是其子节点SG值加一后的异或结果（此处加一代表该节点的一个额外的游戏状态）。通过计算不同的SG值，并通过这些值来判断最终游戏的胜负，如果最终的SG值为0，则表示后手必胜，否则先手必胜。代码中的`sg1`和`sg2`用来交替存储当前和前一步的SG值，每次循环计算新的SG值并更新`sg1`和`sg2`。
时间复杂度: O(n)
空间复杂度: O(1)
class Solution:
def findGameWinner(self, n: int) -> bool:
sg1, sg2 = 0, 1 # 初始化sg1和sg2分别代表最初两个SG值
for _ in range(n-1): # 从第三个值开始计算到第n个值
t = (sg1+1)^(sg2+1) # 计算新的SG值，基于前两个SG值
sg1, sg2 = t, sg1 # 更新sg1和sg2为新的SG值及前一个SG值
return bool(sg1) # 返回最终的SG值的布尔值，非0即True表示先手胜利
Explore
斐波那契树具有递归的结构，其中每个节点的子树大小符合斐波那契数列的规律。在利用Sprague-Grundy定理分析每个节点的SG值时，基本思想是将每个节点的SG值设为其不同子游戏SG值的最小非负整数，这通常由其子节点决定。由于每个节点的子节点数目符合斐波那契数列，因此可以通过递归地计算其子节点的SG值来得到当前节点的SG值。具体到代码实现，考虑到斐波那契数列的性质，每个节点的SG值可以通过其前两个相邻节点的SG值计算得出，从而实现了对斐波那契树结构SG值的有效计算。
Sprague-Grundy定理中，一个复合游戏的SG值是所有子游戏SG值的nim-sum，即所有子游戏SG值的异或结果。这是因为nim游戏的基本规则是通过异或操作来计算。在斐波那契树的场景中，每个节点的SG值由其下层子节点的SG值决定，而通过异或操作，我们可以有效地计算出每个节点在游戏中的独特状态，这使得可以根据子节点的SG值来确定当前节点的SG值，从而判断游戏的胜负。
异或操作具有几个关键性质，如交换律和结合律，这保证了SG值的计算是一致且无序的。由于每个游戏状态的SG值是通过异或其所有子游戏状态的SG值得到的，这保证了每个游戏状态都是由其子状态唯一确定的。此外，异或操作能够有效地合并相同的SG值（相同数值异或结果为0），确保了不同游戏状态的SG值不会重复，从而每个SG值都能正确且唯一地代表一个特定的游戏状态。
在实现中，根据斐波那契树的属性，我们知道根节点的前两个SG值是固定的，分别为0和1。根据这些初始值，后续的SG值可以通过前两个SG值计算得出。这是因为斐波那契数列的每一项都是前两项的和，因此，从第三个SG值开始计算，通过前两个已知的SG值可以递推出后面的SG值，这样可以减少计算量并简化问题。