Leetcode 3203. Find Minimum Diameter After Merging Two Trees
- Leetcode 3203. Find Minimum Diameter After Merging Two Trees
- 1. 解题思路
- 2. 代码实现
- 题目链接:3203. Find Minimum Diameter After Merging Two Trees
1. 解题思路
这一题的话算是一个拓扑树的题目?总之就是从树的叶子节点不断向上遍历,不断地删除已访问的叶子节点,并加入更新之后的新的叶子节点,这样我们就能得到树的最大深度,然后在遍历过程中我们考察其任意节点上的当前深度和已有深度的和的最大值,即为经过该节点的最大路径长度,遍历整张图,我们即刻获得整个树的深度和diameter。然后,我们要连接两个图的话,能够获得的最大路径长度就是两个图的深度之和加一。
由此,我们即可完成这道题目了。
2. 代码实现
给出python代码实现如下:
class Solution:def minimumDiameterAfterMerge(self, edges1: List[List[int]], edges2: List[List[int]]) -> int:def dfs(edges):if edges == []:return 0, 0diameter = 0graph = defaultdict(list)deg = defaultdict(int)for u, v in edges:graph[u].append(v)graph[v].append(u)deg[u] += 1deg[v] += 1seen = set()leafs = [u for u in deg if deg[u] == 1]depth = defaultdict(int)while leafs != []:u = leafs.pop(0)if u in seen:continueseen.add(u)for v in graph[u]:if v in seen:continuediameter = max(diameter, depth[v] + depth[u] + 1)depth[v] = max(depth[v], depth[u]+1)deg[v] -= 1if deg[v] == 1:leafs.append(v)return max(depth.values()), diameterdepth1, diameter1 = dfs(edges1)depth2, diameter2 = dfs(edges2)return max(depth1 + depth2 + 1, diameter1, diameter2)
提交代码评测得到:耗时3216ms,占用内存93.4MB。
相关文章:
Leetcode 3203. Find Minimum Diameter After Merging Two Trees
Leetcode 3203. Find Minimum Diameter After Merging Two Trees 1. 解题思路2. 代码实现 题目链接:3203. Find Minimum Diameter After Merging Two Trees 1. 解题思路 这一题的话算是一个拓扑树的题目?总之就是从树的叶子节点不断向上遍历ÿ…...
【抽代复习笔记】24-群(十八):循环群的两道例题
例1:证明: (1)三次交错群A3是循环群,它与(Z3,)同构,其中Z3 {[0],[1],[2]}; (2)G {1,i,-1,-i},G上的代数运算是数的乘法,则G是一个循环群&…...
Linux常见操作问题
1、登录刚创建的用户,无法操作。 注:etc/passwd文件是Linux操作系统中存储用户账户信息的文本文件,包含了系统中所有用户的基本信息,比如用户名、用户ID、用户组ID、用户家目录路径。 注:etc: 这个目录存放所有的系统…...
鲁工小装载机-前后桥传动轴油封更换记录
鲁工装载机 因前后桥大量漏齿轮油,故拆开查看、更换油封 一: 如图圈起来的地方是螺丝和钢板相别,用200的焊接电流用电焊机点开一个豁口后拆除螺丝。 转轴是拆除传动轴后的样子。 这就是拆下来的样子,这玩意插上边那图&…...
商城自动化测试实战 —— 登录+滑块验证
hello大家好,我是你们的小编! 本商城测试项目采取PO模型和数据分离式架构,采用pytestseleniumjenkins结合的方式进行脚本编写与运行,项目架构如下: 1、创建项目名称:code_shopping,创建所需项目…...
8.计算机视觉—增广和迁移
目录 1.数据增广数据增强数据增强的操作代码实现2.微调 迁移学习 Transfer learning(重要的技术)网络结构微调:当目标数据集比源数据集小得多时,微调有助于提高模型的泛化能力。训练固定一些层总结代码实现1.数据增广 CES上的真实故事 有一家做智能售货机的公司,发现他们…...
【Matlab】-- BP反向传播算法
文章目录 文章目录 00 写在前面01 BP算法介绍02 基于Matlab的BP算法03 代码解释 00 写在前面 BP算法可以结合鲸鱼算法、飞蛾扑火算法、粒子群算法、灰狼算法、蝙蝠算法等等各种优化算法一起,进行回归预测或者分类预测。 01 BP算法介绍 BP(Backpropag…...
【Python】 数据分析中的常见统计量:众数
那年夏天我和你躲在 这一大片宁静的海 直到后来我们都还在 对这个世界充满期待 今年冬天你已经不在 我的心空出了一块 很高兴遇见你 让我终究明白 回忆比真实精彩 🎵 王心凌《那年夏天宁静的海》 众数(Mode)是统计学中另…...
Karabiner-Elements 设置mac键盘
软件下载地址: Karabiner-Elements 修改键盘位置,但是重启后,就消失了。 {"description": "New Rule (change left_shiftcaps_lock to page_down, right_shiftcaps_lock to left_commandmission_control)","manip…...
Mybatis实现流程
一,UserDAO 接口定义 首先,定义 UserDAO接口,包含 getList()方法,定义类型为List<User>: package dao;import model.User; import java.util.List;public interface UserDAO {List<User> getList(); }二,…...
简单的springboot整合activiti5-serviceImpl部分(1)
简单的springboot整合activiti5.22.0-serviceImpl部分(1) 原来的流程serviceImpl部分代码过多,所以此处单独记录一下,此处记录的是serviceImpl第一部分代码 package cn.git.workflow.service.impl;import cn.git.cache.api.BaseCacheApi; import cn.gi…...
snat、dnat和firewalld
目录 概述 SNAT源地址转换 DANT目的地址转换 抓包 firewalld 端口管理 概述 snat :源地址转换 内网——外网 内网ip转换成可以访问外网的ip 也就是内网的多个主机可以只有一个有效的公网ip地址访问外部网络 DNAT:目的地址转发 外部用户&#…...
[数据集][目标检测]鸡蛋缺陷检测数据集VOC+YOLO格式2918张2类别
数据集格式:Pascal VOC格式YOLO格式(不包含分割路径的txt文件,仅仅包含jpg图片以及对应的VOC格式xml文件和yolo格式txt文件) 图片数量(jpg文件个数):2918 标注数量(xml文件个数):2918 标注数量(txt文件个数):2918 标注…...
前后端防重复提交
数据重复提交是一个大忌,会带来无效数据,应该在前端和后端都建议检测防范。 前端一般是按钮按下触发数据提交,如果用户鼠标操作习惯不好,或者鼠标或系统设置问题会导致鼠标连击,如果前端不做相关处理,可能会…...
JVM专题八:JVM如何判断可回收对象
在JVM专题七:JVM垃圾回收机制中提到JVM的垃圾回收机制是一个自动化的后台进程,它通过周期性地检查和回收不可达的对象(垃圾),帮助管理内存资源,确保应用程序的高效运行。今天就让我们来看看JVM到底是怎么定…...
binary_cross_entropy_with_logits函数的参数设定
binary_cross_entropy_with_logits 该函数参数: logits (Tensor) - 输入预测值。其数据类型为float16或float32。 label (Tensor) - 输入目标值,shape与 logits 相同。数据类型为float16或float32。 weight (Tensor,可选) - 指定每个批次二…...
Python 面试【★★★★★】
欢迎莅临我的博客 💝💝💝,很高兴能够在这里和您见面!希望您在这里可以感受到一份轻松愉快的氛围,不仅可以获得有趣的内容和知识,也可以畅所欲言、分享您的想法和见解。 推荐:「stormsha的主页」…...
C# StringBuilder
以下是一些基本的 StringBuilder 使用方法:创建 StringBuilder 实例:追加字符串:插入字符串:删除字符串:替换字符串:清空 StringBuilder:转换 StringBuilder 为字符串:使用容量&…...
4个文章生成器免费版分享,让文章创作更轻松便捷
在当今这个信息飞速传播的时代,文章创作的重要性愈发凸显。无论是从事内容创作的专业人士,还是偶尔需要撰写文章的普通大众,都希望能更高效地完成文章创作任务。而在实际操作中,我们常常会遇到思路卡顿、没有创作灵感的问题。今天…...
redis-cluster(集群模式搭建)
redis中间件版本: redis-5.0.5环境介绍 这里使用服务器数量3,分别为172.0.0.1,172.0.0.2,172.0.0.3,每台机器redis节点数量2个,共6个redis节点构成redis-cluster模式。编译安装包 在172.0.0.1的机器上进入安装目录 cd …...
19c补丁后oracle属主变化,导致不能识别磁盘组
补丁后服务器重启,数据库再次无法启动 ORA01017: invalid username/password; logon denied Oracle 19c 在打上 19.23 或以上补丁版本后,存在与用户组权限相关的问题。具体表现为,Oracle 实例的运行用户(oracle)和集…...
零门槛NAS搭建:WinNAS如何让普通电脑秒变私有云?
一、核心优势:专为Windows用户设计的极简NAS WinNAS由深圳耘想存储科技开发,是一款收费低廉但功能全面的Windows NAS工具,主打“无学习成本部署” 。与其他NAS软件相比,其优势在于: 无需硬件改造:将任意W…...
51c自动驾驶~合集58
我自己的原文哦~ https://blog.51cto.com/whaosoft/13967107 #CCA-Attention 全局池化局部保留,CCA-Attention为LLM长文本建模带来突破性进展 琶洲实验室、华南理工大学联合推出关键上下文感知注意力机制(CCA-Attention),…...
【Oracle APEX开发小技巧12】
有如下需求: 有一个问题反馈页面,要实现在apex页面展示能直观看到反馈时间超过7天未处理的数据,方便管理员及时处理反馈。 我的方法:直接将逻辑写在SQL中,这样可以直接在页面展示 完整代码: SELECTSF.FE…...
日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする
日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする 1、前言(1)情况说明(2)工程师的信仰2、知识点(1) にする1,接续:名词+にする2,接续:疑问词+にする3,(A)は(B)にする。(2)復習:(1)复习句子(2)ために & ように(3)そう(4)にする3、…...
阿里云ACP云计算备考笔记 (5)——弹性伸缩
目录 第一章 概述 第二章 弹性伸缩简介 1、弹性伸缩 2、垂直伸缩 3、优势 4、应用场景 ① 无规律的业务量波动 ② 有规律的业务量波动 ③ 无明显业务量波动 ④ 混合型业务 ⑤ 消息通知 ⑥ 生命周期挂钩 ⑦ 自定义方式 ⑧ 滚的升级 5、使用限制 第三章 主要定义 …...
Debian系统简介
目录 Debian系统介绍 Debian版本介绍 Debian软件源介绍 软件包管理工具dpkg dpkg核心指令详解 安装软件包 卸载软件包 查询软件包状态 验证软件包完整性 手动处理依赖关系 dpkg vs apt Debian系统介绍 Debian 和 Ubuntu 都是基于 Debian内核 的 Linux 发行版ÿ…...
【Zephyr 系列 10】实战项目:打造一个蓝牙传感器终端 + 网关系统(完整架构与全栈实现)
🧠关键词:Zephyr、BLE、终端、网关、广播、连接、传感器、数据采集、低功耗、系统集成 📌目标读者:希望基于 Zephyr 构建 BLE 系统架构、实现终端与网关协作、具备产品交付能力的开发者 📊篇幅字数:约 5200 字 ✨ 项目总览 在物联网实际项目中,**“终端 + 网关”**是…...
零基础在实践中学习网络安全-皮卡丘靶场(第九期-Unsafe Fileupload模块)(yakit方式)
本期内容并不是很难,相信大家会学的很愉快,当然对于有后端基础的朋友来说,本期内容更加容易了解,当然没有基础的也别担心,本期内容会详细解释有关内容 本期用到的软件:yakit(因为经过之前好多期…...
Linux C语言网络编程详细入门教程:如何一步步实现TCP服务端与客户端通信
文章目录 Linux C语言网络编程详细入门教程:如何一步步实现TCP服务端与客户端通信前言一、网络通信基础概念二、服务端与客户端的完整流程图解三、每一步的详细讲解和代码示例1. 创建Socket(服务端和客户端都要)2. 绑定本地地址和端口&#x…...
