dtcms模板 XnMatrix IntelliJ IDEA教程 java开发环境变量 svn swing validation parsing input axios NEC pmp视频教程下载 linux源码在线阅读 oracle查询所有数据库 nikto扫描web漏洞 php获取当天的0点时间戳 python基础 python测试 python下载安装教程 python随机整数 python匹配字符串 python函数返回 python建站 java删除数组中的元素 java开发者 java循环语句 java地址 java怎么写接口 java中的注释 java字符串比较 java接口的修饰符 javahttp linux密码忘记 超级煎蛋卷 苹果5s降级 tftpd64 ipad锁屏 免费脚本 mac画图工具 办公室复印机使用方法
当前位置: 首页 > 学习教程  > 编程语言

LeetCode题解(LCP10):二叉树任务调度(Python)

2021/1/13 20:40:52 文章标签: 测试文章如有侵权请发送至邮箱809451989@qq.com投诉后文章立即删除

题目:原题链接(困难) 标签:深度优先搜索、动态规划、树、二叉树 解法时间复杂度空间复杂度执行用时Ans 1 (Python)O(N)O(N)O(N)O(N)O(N)O(N)96ms (85.97%)Ans 2 (Python)Ans 3 (Python) 解法一: class Solution:def…

题目:原题链接(困难)

标签:深度优先搜索、动态规划、树、二叉树

解法时间复杂度空间复杂度执行用时
Ans 1 (Python) O ( N ) O(N) O(N) O ( N ) O(N) O(N)96ms (85.97%)
Ans 2 (Python)
Ans 3 (Python)

解法一:

class Solution:
    def minimalExecTime(self, root: TreeNode) -> float:
        total_root, full_root = self.dfs(root)
        return total_root - full_root

    def dfs(self, root):
        """深度优先搜索

        :param root: 当前树(子树)的根节点
        :return: 总计运行时间、最大并行时间
        """
        # 处理空节点的情况
        if not root:
            return 0., 0.

        # 递归左子树和右子树
        total_left, full_left = self.dfs(root.left)
        total_right, full_right = self.dfs(root.right)

        # 计算树的总计运行时间
        total_root = root.val + total_left + total_right

        if total_left < total_right:
            total_left, total_right = total_right, total_left
            full_left, full_right = full_right, full_left

        # 处理左子节点和右子节点均可以完全双线程的情况
        if total_left - 2 * full_left <= total_right:
            full_root = (total_left + total_right) / 2

        # 处理左子节点和右子节点不能完全双线程的情况
        else:
            full_root = total_right + full_left

        return total_root, full_root

本文链接: http://www.dtmao.cc/news_show_600401.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?