当前位置: 首页 > news >正文

leetcode 684. 冗余连接

树可以看成是一个连通且 无环 的 无向 图。

给定往一棵 n 个节点 (节点值 1~n) 的树中添加一条边后的图。添加的边的两个顶点包含在 1 到 n 中间,且这条附加的边不属于树中已存在的边。图的信息记录于长度为 n 的二维数组 edges ,edges[i] = [ai, bi] 表示图中在 ai 和 bi 之间存在一条边。

请找出一条可以删去的边,删除后可使得剩余部分是一个有着 n 个节点的树。如果有多个答案,则返回数组 edges 中最后出现的那个。

示例 1:
在这里插入图片描述
输入: edges = [[1,2], [1,3], [2,3]]
输出: [2,3]

示例 2:
在这里插入图片描述
输入: edges = [[1,2], [2,3], [3,4], [1,4], [1,5]]
输出: [1,4]

提示:
n == edges.length
3 <= n <= 1000
edges[i].length == 2
1 <= ai < bi <= edges.length
ai != bi
edges 中无重复元素
给定的图是连通的
题目链接:leetcode 684

思路,可以采用并查集实现,记录每个节点的对用的最终 parent 节点,加入一条边为 (a, b), 则赋值 a 的 parent 节点为 b 的 parent 节点, 如果一条边的 parent 对应节点相同,那么说明这俩节点已经在 图中了。

class Solution:def getParent(self, parent, key):if parent[key] != key:return self.getParent(parent, parent[key])return keydef union(self, parent, key1, key2):parent[self.getParent(parent, key1)] = self.getParent(parent, key2)def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:parent = [i for i in range(len(edges)+1)]for x in edges:node1, node2 = x if self.getParent(parent, node1) == self.getParent(parent, node2):return xelse:self.union(parent, node1, node2)

方法二,直接暴力计算

class Solution:def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:node, visited = set(), set()for x in edges:node.add(x[0])node.add(x[1])  current = set()visited.add(edges[0][0])visited.add(edges[0][1])vis = [0 for i in range(len(edges))]vis[0] = 1res = []for i in range(len(node)):## 每次循环只加一个顶点进去,最后的肯定是答案for j in range(len(edges)):if vis[j] == 0:x = edges[j]if x[0] in visited and x[1] in visited:vis[j] = 1res.append(x)breakelif x[0] in visited:vis[j] = 1visited.add(x[1])breakelif x[1] in visited:vis[j] = 1visited.add(x[0])breakif len(res) > 0:return res[-1]return res

相关文章:

leetcode 684. 冗余连接

树可以看成是一个连通且 无环 的 无向 图。 给定往一棵 n 个节点 (节点值 1&#xff5e;n) 的树中添加一条边后的图。添加的边的两个顶点包含在 1 到 n 中间&#xff0c;且这条附加的边不属于树中已存在的边。图的信息记录于长度为 n 的二维数组 edges &#xff0c;edges[i] …...

yolov8模型训练、目标跟踪

一、准备条件 1.下载yolov8 https://github.com/ultralytics/ultralytics2.安装python https://www.python.org/ftp/python/3.8.0/python-3.8.0-amd64.exe3.安装依赖 进入ultralytics-main&#xff0c;执行&#xff1a; pip install -r requirements.txt pip install -U ul…...

Flink SQL Regular Join 、Interval Join、Temporal Join、Lookup Join 详解

Flink ⽀持⾮常多的数据 Join ⽅式&#xff0c;主要包括以下三种&#xff1a; 动态表&#xff08;流&#xff09;与动态表&#xff08;流&#xff09;的 Join动态表&#xff08;流&#xff09;与外部维表&#xff08;⽐如 Redis&#xff09;的 Join动态表字段的列转⾏&#xf…...

如何在搜索引擎中应用AI大语言模型,提高企业生产力?

人工智能尤其是大型语言模型的应用&#xff0c;重塑了我们与信息交互的方式&#xff0c;也为企业带来了重大的变革。将基于大模型的检索增强生成&#xff08;RAG&#xff09;集成到业务实践中&#xff0c;不仅是一种趋势&#xff0c;更是一种必要。它有助于实现数据驱动型决策&…...

实验七 组合器模式的应用

实验目的 1)掌握组合器模式&#xff08;composite&#xff09;的特点 2 分析具体问题&#xff0c;使用组合器模式进行设计。 实验内容和要求 在例3.3的设计中&#xff0c;添加一个空军大队( Wing)类&#xff0c;该类与Squadron、Group类是平行的&#xff0c;因此应该继承了AirU…...

Springboot实现人脸识别与WebSocket长连接的实现

0.什么是WebSocket,由于普通的请求是间断式发送的,如果要同一时间发生大量的请求,必然导致响应速度慢(因为根据tcp协议要经过三层握手,如果不持续发送,就会导致n多次握手,关闭连接,打开连接) 1.业务需求: 由于我需要使用java来处理视频的问题,视频其实就是图片,相当于每张图片…...

智能安全帽功能-EIS智能防抖摄像头4G定位视频语音气体检测

智能安全帽是一种集成多种智能功能的产品&#xff0c;例如实时定位、语音对讲、健康监测和AI智能预警等。这些丰富的功能能够更好地帮助工人开展工作&#xff0c;并提升安全保障水平。智能安全帽在各个行业中的应用越来越广泛。尤其在工程建设领域&#xff0c;项目管理和工作安…...

TEMU跨境平台珠宝首饰RSL报告如何办理?

首饰或者产品TEMU拼多多跨境平台要求的RSL报告如何办理&#xff1f; 珠宝首饰上架前必须进行RSL Report&#xff08;欧盟禁限用化学物质检测报告&#xff09; 随着人们对珠宝首饰的要求越来越高&#xff0c;为了确保珠宝首饰的安全性&#xff0c;欧盟REACH法规规定&#xff0c…...

51单片机的篮球计分器液晶LCD1602显示( proteus仿真+程序+原理图+PCB+设计报告+讲解视频)

51单片机的篮球计分器液晶LCD1602显示 &#x1f4d1;1.主要功能&#xff1a;&#x1f4d1;讲解视频&#xff1a;&#x1f4d1;2.仿真&#x1f4d1;3. 程序代码&#x1f4d1;4. 原理图&#x1f4d1;5. PCB图&#x1f4d1;6. 设计报告&#x1f4d1;7. 设计资料内容清单&&…...

【NI-DAQmx入门】NI-DAQmx之Python

NI-DAQmx Python GitHub资源&#xff1a; NI-DAQmx Python 文档说明&#xff1a;NI-DAQmx Python Documentation — NI-DAQmx Python API 0.9 documentation nidaqmx支持 CPython 3.7和 PyPy3&#xff0c;需要注意的是多支持USB DAQ和PCI DAQ&#xff0c;cDAQ需要指定…...

YoloV8目标检测与实例分割——目标检测onnx模型推理

一、模型转换 1.onnxruntime ONNX Runtime&#xff08;ONNX Runtime或ORT&#xff09;是一个开源的高性能推理引擎&#xff0c;用于部署和运行机器学习模型。它的设计目标是优化执行使用Open Neural Network Exchange&#xff08;ONNX&#xff09;格式定义的模型&#xff0c;…...

pcigo图床插件的简单开发

1.前言&#xff1a; 如果想写一个图床并且投入使用&#xff0c;那么&#xff0c;接入picgo一定是一个不错的选择。picgo有着windows&#xff0c;mac&#xff0c;linux等多个客户端版本。实用且方便。 2. 开发的准备&#xff1a; 2.0. 需要安装一个node node这里我就不详细说…...

Find My手机保护壳|苹果Find My与手机保护壳结合,智能防丢,全球定位

随着科技水平的快速发展&#xff0c;科技美容这一行业做为新型产业新生而出。时尚IT品牌随着市场的多元化发展。针对手机品牌和功能的增加而呈多样化&#xff0c;将手机保护壳按质地分有PC壳&#xff0c;皮革 &#xff0c;硅胶&#xff0c;布料&#xff0c;硬塑&#xff0c;皮套…...

encode和decode的区别

字节序列和字符串是Python中两种不同的数据类型&#xff0c;它们的主要区别在于表示和处理方式&#xff01; 字节序列&#xff08;Bytes&#xff09;&#xff1a; 字节序列是一种二进制数据类型&#xff0c;它由一系列字节组成。字节是计算机存储信息的基本单位&#xff0c;每…...

建设项目管理中的 5 大预算挑战

为建设项目管理制定可靠、准确的预算是一项艰巨的任务&#xff0c;对于中小型建筑企业来说尤其如此。预算必须精确&#xff0c;同时还要考虑到每项工作的独特性和复杂性。 一项建筑行业相关调查统计了参与施工预算流程的人员所面临的最大挑战&#xff0c;分别是时间、预算、不…...

vue2 集成 - 超图-SuperMap iClient3D for WebGL

1:下载SuperMap iClient3D for WebGL SuperMap iClient3D for WebGL产品包 打开资源目录如下 2:格式化项目中所用的依赖包 开发指南 从超图官网下载SuperMap iClient3D 11i (2023) SP1 for WebGL_CN.zip解压后,将Build目录下的SuperMap3D复制到项目中 \public\static…...

FPGA设计过程中有关数据之间的并串转化

1.原理 并串转化是指的是完成串行传输和并行传输两种传输方式之间的转换的技术&#xff0c;通过移位寄存器可以实现串并转换。 串转并&#xff0c;将数据移位保存在寄存器中&#xff0c;再将寄存器的数值同时输出&#xff1b; 并转串&#xff0c;将数据先进行移位&#xff0…...

hologres基础知识一文全

1 功能特性 1.1多场景查询分析 Hologres支持行存、列存、行列共存等多种存储模式和索引类型,同时满足简单查询、复杂查询、即席查询等多样化的分析查询需求。Hologres使用大规模并行处理架构,分布式处理SQL,提高资源利用率,实现海量数据极速分析。 亚秒级交互式分析 Holo…...

阿里云oss迁移到AWS S3

这里写自定义目录标题 0.项目背景1.rclone 方式2.rsync方式3.注意 0.项目背景 公司迁移要求&#xff1a;从阿里云oss到亚马逊s3&#xff0c;数据量大概500G-2T左右。 开启阿里云oss 加速模式&#xff0c;这样能够跨机房和区域加速。 主要采用以下两种方式同步数据&#xff0c;…...

RabbitMQ(高级特性):限流

消费端限流 在rabbitmq中&#xff0c;使用消费端限流必须开启手动签收信息 过MQ可以对请求进行“削峰填谷”&#xff0c;即通过消费端限流的方式限制消息的拉取速度&#xff0c;达到保护消费端的目的。 生产者批量发送消息&#xff1a; Test public void testSendBatch() {…...

C# SqlSugar:依赖注入与仓储模式实践

C# SqlSugar&#xff1a;依赖注入与仓储模式实践 在 C# 的应用开发中&#xff0c;数据库操作是必不可少的环节。为了让数据访问层更加简洁、高效且易于维护&#xff0c;许多开发者会选择成熟的 ORM&#xff08;对象关系映射&#xff09;框架&#xff0c;SqlSugar 就是其中备受…...

《基于Apache Flink的流处理》笔记

思维导图 1-3 章 4-7章 8-11 章 参考资料 源码&#xff1a; https://github.com/streaming-with-flink 博客 https://flink.apache.org/bloghttps://www.ververica.com/blog 聚会及会议 https://flink-forward.orghttps://www.meetup.com/topics/apache-flink https://n…...

自然语言处理——Transformer

自然语言处理——Transformer 自注意力机制多头注意力机制Transformer 虽然循环神经网络可以对具有序列特性的数据非常有效&#xff0c;它能挖掘数据中的时序信息以及语义信息&#xff0c;但是它有一个很大的缺陷——很难并行化。 我们可以考虑用CNN来替代RNN&#xff0c;但是…...

[Java恶补day16] 238.除自身以外数组的乘积

给你一个整数数组 nums&#xff0c;返回 数组 answer &#xff0c;其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法&#xff0c;且在 O(n) 时间复杂度…...

JAVA后端开发——多租户

数据隔离是多租户系统中的核心概念&#xff0c;确保一个租户&#xff08;在这个系统中可能是一个公司或一个独立的客户&#xff09;的数据对其他租户是不可见的。在 RuoYi 框架&#xff08;您当前项目所使用的基础框架&#xff09;中&#xff0c;这通常是通过在数据表中增加一个…...

LINUX 69 FTP 客服管理系统 man 5 /etc/vsftpd/vsftpd.conf

FTP 客服管理系统 实现kefu123登录&#xff0c;不允许匿名访问&#xff0c;kefu只能访问/data/kefu目录&#xff0c;不能查看其他目录 创建账号密码 useradd kefu echo 123|passwd -stdin kefu [rootcode caozx26420]# echo 123|passwd --stdin kefu 更改用户 kefu 的密码…...

【Nginx】使用 Nginx+Lua 实现基于 IP 的访问频率限制

使用 NginxLua 实现基于 IP 的访问频率限制 在高并发场景下&#xff0c;限制某个 IP 的访问频率是非常重要的&#xff0c;可以有效防止恶意攻击或错误配置导致的服务宕机。以下是一个详细的实现方案&#xff0c;使用 Nginx 和 Lua 脚本结合 Redis 来实现基于 IP 的访问频率限制…...

在 Spring Boot 项目里,MYSQL中json类型字段使用

前言&#xff1a; 因为程序特殊需求导致&#xff0c;需要mysql数据库存储json类型数据&#xff0c;因此记录一下使用流程 1.java实体中新增字段 private List<User> users 2.增加mybatis-plus注解 TableField(typeHandler FastjsonTypeHandler.class) private Lis…...

水泥厂自动化升级利器:Devicenet转Modbus rtu协议转换网关

在水泥厂的生产流程中&#xff0c;工业自动化网关起着至关重要的作用&#xff0c;尤其是JH-DVN-RTU疆鸿智能Devicenet转Modbus rtu协议转换网关&#xff0c;为水泥厂实现高效生产与精准控制提供了有力支持。 水泥厂设备众多&#xff0c;其中不少设备采用Devicenet协议。Devicen…...

热烈祝贺埃文科技正式加入可信数据空间发展联盟

2025年4月29日&#xff0c;在福州举办的第八届数字中国建设峰会“可信数据空间分论坛”上&#xff0c;可信数据空间发展联盟正式宣告成立。国家数据局党组书记、局长刘烈宏出席并致辞&#xff0c;强调该联盟是推进全国一体化数据市场建设的关键抓手。 郑州埃文科技有限公司&am…...