9月5日freewheel笔试

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 res

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)