9月5日freewheel笔试
1. 求每一层的最小时间消耗，然后再相加AC100%
class TreeNode: def __init__(self, x): self.val = x self.left = None self.right = None from collections import deque class Solution: def GetMinTimeCost(self , root , failId , timeCost ): def get_failroot(troot): if troot is None: return troot if troot.val == failId: return troot res = get_failroot(troot.left) if res is not None: return res return get_failroot(troot.right) failroot = get_failroot(root) # write code here q = deque([[1,failroot]]) inf = int(1e9+7) curtime = 0 level = 0 high = [] thigh = -1 while len(q): tlevel,troot = q[0] q.popleft() if troot is None: continue if tlevel!= level: high.append(curtime) curtime = inf level = tlevel if troot.val< len(timeCost): curtime = min(curtime,timeCost[troot.val]) if troot.val == failId: thigh = tlevel q.append([tlevel+1,troot.left]) q.append([tlevel+1,troot.right]) if thigh ==-1: return 0 res = sum(high)-sum(high[:thigh]) return res2. 类似俄罗斯套娃AC100%
class Solution: def maxPreRolDuration(self , orders ): # write code here new_orders = [] for i in range(len(orders)): torders = sorted(orders[i][:-1],reverse=True)+orders[i][-1:] new_orders.append(torders) orders = sorted(new_orders,reverse=True) n = len(orders) dp= [0]*n # dp[0] = orders[0][0]*orders[0][3] for i in range(n): dp[i] =orders[i][0]*orders[i][3] for j in range(i): if orders[i][0]<= orders[j][0] and orders[i][1]<= orders[j][1] and orders[i][2]<= orders[j][2] : dp[i] = max(dp[i],dp[j]+orders[i][0]*orders[i][3]) return max(dp)
