class Solution:
def countHighestScoreNodes(self, parents: List[int]) -> int:
# 统计每个节点从上面来了几个位置，从左边和右边出了几个位置，父亲直接使用整数相减
# A 建树
# B 遍历
n = len(parents)
tree = [[-2]*2 for _ in range(len(parents))]#邻接矩阵
root =-1
for i,p in enumerate(parents):
if p == -1:
root = i
continue
if tree[p][0]==-2:
tree[p][0] = i
else:
tree[p][1] = i
ans = []
def postorder(root):
if root == -2:
return 0
a = postorder(tree[root][0])
b = postorder(tree[root][1])
if a == b ==0:
# ans[0] = max(n-1,ans[0])
ans.append(n-1)
elif a == 0:
# ans[0] = max(b*(n-1-b),ans[0])
if n-1-b:
ans.append(b*(n-1-b))
else:
ans.append(b)
elif b == 0:
if n-1-a:
ans.append(a*(n-1-a))
else:
ans.append(a)
else:
if n-1-a-b:
# ans[0] = max(b*a*(n-1-a-b),ans[0])
ans.append(b*a*(n-1-a-b))
else:
# ans[0] = max(b*a,ans[0])
ans.append(b*a)
return a+b+1
postorder(root)
# print(ans)
return ans.count(max(ans))
03-19leetcode刷题，相信自己的思路然后一步过
606. 根据二叉树创建字符串
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def tree2str(self, root: Optional[TreeNode]) -> str:
def dfs(root):
if root == None:
return ''
else:
a = dfs(root.left)
b = dfs(root.right)
if a == '' and b =='':
return str(root.val)
elif a == '' and b != '':
return str(root.val)+'()({})'.format(b)
elif a != '' and b=='':
return str(root.val)+'({})'.format(a)
else:
return str(root.val)+'({})({})'.format(a,b)
return dfs(root)
2039. 网络空闲的时刻
初版，只是简单的看了下数据规模就知道Floyd必超时
TLE了
class Solution:
def networkBecomesIdle(self, edges: List[List[int]], patience: List[int]) -> int:
#两步，1步进行最短路径
# 第二步，最短路径与patience的结合
n = len(patience)
# adj_matrix = [[0]*len(edges) for _ in range(n)]
dis_matrix = [[math.inf]*n for _ in range(n)]
for item in edges:
dis_matrix[item[0]][item[1]] = 1
dis_matrix[item[1]][item[0]] = 1
for i in range(n):
dis_matrix[i][i] = 0
for k in range(n):
for i in range(n):
for j in range(n):
if dis_matrix[i][k] + dis_matrix[k][j] < dis_matrix[i][j]:
dis_matrix[i][j] = dis_matrix[i][k] + dis_matrix[k][j]
main_sub = [i*2 for i in dis_matrix[0]]
max_ = -math.inf
for i in range(n):
if main_sub[i]<=patience[i]:
max_=max(max_,main_sub[i]+1)
else:
max_=max(max_,((main_sub[i]-1)//patience[i])*patience[i]+main_sub[i]+1)
return max_
再版：dijistra的最短路径
class Solution:
def networkBecomesIdle(self, edges: List[List[int]], patience: List[int]) -> int:
#两步，1步进行最短路径
# 第二步，最短路径与patience的结合
n = len(patience)
adj_matrix = [[0]*n for _ in range(n)]
main_sub =[math.inf]*n
for item in edges:
if item[0] == 0:
main_sub[item[1]] = 1
if item[1] == 0:
main_sub[item[0]] = 1
adj_matrix[item[0]][item[1]] = 1
adj_matrix[item[1]][item[0]] = 1
# dis_matrix = [[math.inf]*n for _ in range(n)]
# for item in edges:
# dis_matrix[item[0]][item[1]] = 1
# dis_matrix[item[1]][item[0]] = 1
# for i in range(n):
# dis_matrix[i][i] = 0
# for k in range(n):
# for i in range(n):
# for j in range(n):
# if dis_matrix[i][k] + dis_matrix[k][j] < dis_matrix[i][j]:
# dis_matrix[i][j] = dis_matrix[i][k] + dis_matrix[k][j]
# main_sub = [i*2 for i in dis_matrix[0]]
exist = set()
re = None
for i in range(n):
if len(exist)==n:
break
min_ = math.inf
for i in range(n):
if i in exist:
continue
if main_sub[i]<min_:
re = i
min_=main_sub[i]
exist.add(re)
for i in range(n):
if i in exist:
continue
if adj_matrix[i][re]:
main_sub[i] = min(main_sub[re] + 1,main_sub[i])
print(main_sub)
main_sub = [i*2 for i in main_sub]
max_ = -math.inf
for i in range(1,n):
if main_sub[i]<=patience[i]:
max_=max(max_,main_sub[i]+1)
else:
max_=max(max_,((main_sub[i]-1)//patience[i])*patience[i]+main_sub[i]+1)
return max_
上一版被卡住的样例过了，但仍被卡TLE
网友评论