其他网站
1115. 取石子游戏
dfs, https://www.acwing.com/problem/content/description/1117/
有两堆石子，两个人轮流去取，每次取的时候，只能从较多的那堆石子里取，并且取的数目必须是较少的那堆石子数目的整数倍（不能不取）。
最后谁能够把一堆石子取空谁就算赢。
比如初始的时候两堆石子的数目是25和7
| 25 7 | → | 11 7 | → | 4 7 | → | 4 3 | → | 1 3 | → | 1 0 |
|---|---|---|---|---|---|---|---|---|---|---|
| 选手1取 | 选手2取 | 选手1取 | 选手2取 | 选手1取 |
最后选手1（先取的）获胜，在取的过程中选手2都只有唯一的一种取法。
给定初始时石子的数目，如果两个人都采取最优策略，请问先手能否获胜。
输入格式
输入包含多数数据。每组数据一行，包含两个正整数 a 和 b，表示初始时石子的数目。
输入以两个0表示结束。
输出格式
如果先手胜，输出”win”，否则输出”lose”。
数据范围：1≤a,b≤10^9
输入样例：
34 12
15 24
0 0输出样例：
win
lose提示
假设石子数目为 (a,b) 且 a≥b，如果 [a/b]≥2 则先手必胜,如果 [a/b]<2，那么先手只有唯一的一种取法。
[a/b] 表示 a 除以 b 取整后的值。
按题目提示递归，函数返回值为布尔变量，取一次石子先后手交换，返回相反的结果。注意边界条件，如果有两堆一样的则“当前先手”胜。
# 徐至晟 24光华管院
def f(x,y):
if x<y:
return f(y,x)
if x>=y*2:
return True
elif x==y:
return True
else:
return not f(x-y,y)
a,b=map(int,input().split())
while a:
if f(a,b):
print("win")
else:
print("lose")
a,b=map(int,input().split())思路：遍历先手取完后所有可能的结果，如果后手有必赢策略则lose，反之win
# 彭凌越 24光华管理学院
dic = {}
def dfs(a,b):
if (a,b) in dic:
return dic[(a,b)]
if a==0 or b==0:
dic[(a,b)]=True
return True
if a<b:
a,b = b,a
if a%b==0:
dic[(a,b)]=True
return True
for i in range(1,a//b+1):
if not dfs(a-i*b,b):
dic[(a,b)]=True
return True
dic[(a,b)]=False
return False
while True:
a, b = map(int, input().split())
if a == 0 and b == 0:
break
if dfs(a,b):
print('win')
else:
print('lose')from functools import lru_cache
import sys
sys.setrecursionlimit(1<<30)
@lru_cache(maxsize=None)
def can_win(a, b):
if a == 0 or b == 0:
return False # 如果有一堆石子为空，则先手输
if a > b:
for i in range(1, a // b + 1):
if not can_win(a - b * i, b):
return True
else:
for i in range(1, b // a + 1):
if not can_win(a, b - a * i):
return True
return False
def main():
while True:
a, b = map(int, input().split())
if a == 0 and b == 0:
break
if can_win(max(a, b), min(a, b)):
print("win")
else:
print("lose")
if __name__ == "__main__":
main()NC208830找到搜索二叉树中两个错误的节点
https://ac.nowcoder.com/acm/problem/208830
一棵二叉树原本是搜索二叉树，但是其中有两个节点调换了位置，使得这棵二叉树不再是搜索二叉树，请按升序输出这两个错误节点的值。(每个节点的值各不相同)
搜索二叉树：满足每个节点的左子节点小于当前节点，右子节点大于当前节点。
样例1图
样例2图
数据范围：3≤n≤1000003≤n≤100000,节点上的值满足 1≤val≤n1≤val≤n ，保证每个value各不相同
进阶：空间复杂度 O(1)O(1)，时间复杂度 O(n)O(n)
示例1
输入
{1,2,3}返回值
[1,2]说明
如题面图示例2
输入
{4,2,5,3,1}返回值
[1,3]我们可以通过对二叉树进行中序遍历（In-order Traversal）来解决这个问题。
解题思路
在一个正常的二叉搜索树（BST）中，中序遍历得到的值序列应该是严格递增的。如果其中有两个节点的值被交换了，那么中序遍历的序列中就会出现逆序对（即前一个节点的值大于后一个节点的值）。
设中序遍历序列为
- 如果交换的两个节点不相邻，序列中会出现两处逆序对。
- 例如：正常序列为
[1, 2, 3, 4, 5, 6]，交换2和5后变为[1, 5, 3, 4, 2, 6]。 - 逆序对为：
5 > 3和4 > 2。 - 第一个错误节点是第一处逆序对中较大的那个值（
5），第二个错误节点是第二处逆序对中较小的那个值（2）。
- 例如：正常序列为
- 如果交换的两个节点相邻，序列中只会存在一处逆序对。
- 例如：正常序列为
[1, 2, 3, 4]，交换2和3后变为[1, 3, 2, 4]。 - 逆序对为：
3 > 2。 - 第一个错误节点是这处逆序对中较大的值（
3），第二个错误节点是较小的值（2）。
- 例如：正常序列为
根据题目进阶要求，我们需要实现
Python 代码实现
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param root TreeNode类 the root
# @return int整型一维数组
#
class Solution:
def findError(self , root: TreeNode) -> List[int]:
# 用于记录两个错误的节点值
first_err = None
second_err = None
# 记录中序遍历中的前一个节点值
prev_val = float('-inf')
curr = root
# 使用 Morris 中序遍历
while curr is not None:
if curr.left is None:
# 访问当前节点
if prev_val > curr.val:
if first_err is None:
first_err = prev_val
second_err = curr.val
else:
second_err = curr.val
prev_val = curr.val
curr = curr.right
else:
# 寻找当前节点的前驱节点
pred = curr.left
while pred.right is not None and pred.right is not curr:
pred = pred.right
if pred.right is None:
# 建立临时线索指针
pred.right = curr
curr = curr.left
else:
# 恢复树的结构
pred.right = None
# 访问当前节点
if prev_val > curr.val:
if first_err is None:
first_err = prev_val
second_err = curr.val
else:
second_err = curr.val
prev_val = curr.val
curr = curr.right
# 题目要求按升序输出这两个节点的值
# first_err 记录的是较大的错误值，second_err 记录的是较小的错误值
return [second_err, first_err]复杂度分析
- 时间复杂度：
。在 Morris 遍历中，虽然存在内部循环寻找前驱节点，但整棵树的每条边最多被访问 3 次，因此总体时间复杂度为线性。 - 空间复杂度：
。我们只使用了几个辅助指针和变量，没有使用递归栈或额外的队列/栈结构，符合进阶的空间复杂度要求。