java数据结构与算法刷题-----LeetCode684. 冗余连接
| java数据结构与算法刷题目录(剑指Offer、LeetCode、ACM)-----主目录-----持续更新(进不去说明我没写完):https://blog.csdn.net/grd_java/article/details/123063846 |
|---|
文章目录
- 并查集
并查集
| 解题思路:时间复杂度O( n ∗ l o g 2 n n*log_2n n∗log2n),空间复杂度O( n n n) |
|---|
- 并查集是图论的经典算法,主要用于处理不相交集合的合并问题,常用于求连通子图,求最小生成树的Kruskal算法和求最近公共祖先(LCA)等等
- 其代码操作非常简单,初始化init,查询find,合并union
- 初始化操作:用一个数组parent来存储每个顶点的祖先,初始时将自己设置为自己的祖先
- 查询操作:找到i的祖先,index是否是祖先的条件为,parent[index] == index.入果不满足,就需要找到index的祖先x,并更新parent[index] = x
- 合并操作:将两个集合index1和index2合并,直接找到两个集合的祖先x和y,让x指向y
- 根据题目描述,一棵树中,边的数量比结点数量少1,但是现在加了一条边,让这颗树的边和结点数量一致了
- 树是连通无环的无向图,但是多了一条边就会出现环。也就是说,这道题的本质上就是让我们求出导致环出现的这条边(导致两个顶点属于同一连通分量的边)
- 使用并查集,每个集合代表一个连通分量,初始每个结点都属于不同连通分量。遍历每一条边连接的两个顶点
- 两个顶点属于不同连通分量,说明遍历到当前边之前,两个顶点不连通,因此当前边不会导致环的出现,则合并两个顶点的连通分量
- 两个顶点属于相同连通分量,说明在遍历到当前边之前,两个顶点已经连通(间接),而这条边又将两个顶点直接连通,从而导致环的出现,则它就是罪魁祸首。
| 代码 |
|---|
class Solution {public int[] findRedundantConnection(int[][] edges) {int n = edges.length;//顶点个数int[] parent = new int[n + 1];//并查集中下标从1开始for (int i = 1; i <= n; i++) {parent[i] = i;}//遍历每个顶点的边的信息for (int i = 0; i < n; i++) {int[] edge = edges[i];//获取顶点i的边int node1 = edge[0], node2 = edge[1];//获取两条边相邻的顶点if (find(parent, node1) != find(parent, node2)) {//如果和顶点i都不属于同一个集合(连通分量)union(parent, node1, node2);//说明这条边不会导致环的出现,将两个顶点加入并查集} else {//如果属于同一个集合,说明人家两个顶点已经间接连接一起了,现在你这条边居然又把我俩直接连接了起来return edge;//此边是构成环的罪魁祸首,将其返回}}return new int[0];//无结果返回空}//并查集代码,合并public void union(int[] parent, int index1, int index2) {//合并index1和index2的步骤为:找到index1的祖先,然后找到index2的祖先//让index1的祖先指向index2的祖先,完成两个集合的合并。parent[find(parent, index1)] = find(parent, index2);}//从parent中查找index的祖先public int find(int[] parent, int index) {if (parent[index] != index) {//如果index不是自己指向自己,说明它自己不是集合中的根节点(祖先),他也有自己的祖先parent[index] = find(parent, parent[index]);//不断找到其祖先,然后将其祖先记录到parent[index]位置,保证parent[index]只要find一次,就必须指向index的祖先}return parent[index];//返回自己的祖先}
}
相关文章:
java数据结构与算法刷题-----LeetCode684. 冗余连接
java数据结构与算法刷题目录(剑指Offer、LeetCode、ACM)-----主目录-----持续更新(进不去说明我没写完):https://blog.csdn.net/grd_java/article/details/123063846 文章目录 并查集 并查集 解题思路:时间复杂度O( n ∗ l o g 2…...
循环神经网络简介
卷积神经网络相当于人类的视觉,但是它并没有记忆能力,所以它只能处理一种特定的视觉任务,没办法根据以前的记忆来处理新的任务。比如,在一场电影中推断下一个时间点的场景,这个时候仅依赖于现在的场景还不够࿰…...
计算机网络 子网掩码与划分子网
一、实验要求与内容 1、需拓扑图和两个主机的IP配置截图。 2、设置网络A内的主机IP地址为“192.168.班内学号.2”,子网掩码为“255.255.255.128”,网关为“192.168.班内学号.1”;设置网络B内的主机IP地址为“192.168.班内学号100.2”&#…...
HUD抬头显示器中如何设计LCD的阳光倒灌实验
关键词:阳光倒灌实验、HUD光照温升测试、LCD光照温升测试、太阳光模拟器 HUD(Head-Up Display,即抬头显示器)是一种将信息直接投影到驾驶员视线中的技术,通常用于飞机、汽车等驾驶舱内。HUD系统中的LCD(Liq…...
Shoplazza闪耀Shoptalk 2024,新零售创新解决方案引领行业新篇章!
在近期举办的全球零售业瞩目盛事——Shoptalk 2024大会上,全球*的零售技术平台-店匠科技(Shoplazza)以其*的创新实力与前瞻的技术理念,成功吸引了与会者的广泛关注。此次盛会于3月17日至20日在拉斯维加斯曼德勒湾隆重举行,汇聚了逾万名行业精英。在这场零售业的盛大聚会上,Shop…...
Linux:sprintf、snprintf、vsprintf、asprintf、vasprintf比较
这些函数都在stdio.h里,不过不同系统不同库,有些函数不一定提供。 1. sprintf 函数原型: int sprintf (char *str, const char *format, ...); extern int sprintf (char *__restrict __s, const char *__restrict __format, ...); 功能是将…...
Github远程仓库改名字之后,本地git如何配置?
文章目录 缘由解决方案 缘由 今天在github创建一个仓库,备份一下本地电脑上的资料。起初随便起一个仓库名字,后来修改之。既然远程仓库改名,那么本地仓库需要更新地址。这里采用SSH格式。 解决方案 如果你的GitHub仓库改名了,你…...
Objective-C学习笔记(ARC,分类,延展)4.10
1.自动释放池autoreleasepool:存入到自动释放池的对象,在自动释放池销毁时,会自动调用池内所有对象的release方法。调用autorelease方法将对象放入自动释放池。 Person *p1 [ [ [ Person alloc ] init ] autorelease]; 2.在类方法里写一个…...
02 Git 之IDEA 集成使用 GitHub(Git同时管理本地仓库和远程仓库)
2 .IDEA 集成使用 GitHub(Git同时管理本地仓库和远程仓库) 首先在 IDEA 的设置中绑定 GitHub 的账号 先创建一个 test1.txt 文件,内容为 aaa. 最上一栏 VCS, SHARE ON GitHub,然后选择要发送到远程仓库的文件即可。…...
CSS滚动条样式修改
前言 目前我们可以通过 CSS伪类 来实现滚动条的样式修改,以下为修改滚动条样式用到的CSS伪类: ::-webkit-scrollbar — 整个滚动条 ::-webkit-scrollbar-button — 滚动条上的按钮 (上下箭头) ::-webkit-scrollbar-thumb — 滚动条上的滚动滑块 ::-web…...
《零秒思考》像麦肯锡精英一样思考 - 三余书屋 3ysw.net
零秒思考:像麦肯锡精英一样思考 大家好,今天我们要深入探讨的著作是《零秒思考》。在领导提出问题时,我们常常会陷入沉思,却依然难以有所进展,仿佛原地踏步,但是身边的同事却能够立即给出清晰的回答。这种…...
使用docker制作Android镜像(实操可用)
一、安装包准备 1、准备jdk 下载地址:Java Downloads | Oracle 注意版本!!!!!! 我下载的jdk17,不然后面构建镜像报错,就是版本不对 2、准备安装的工具包 ttps://dev…...
大厂MVP技术JAVA架构师培养
课程介绍 这是一个很强悍的架构师涨薪计划课程,课程由专家级MVP讲师进行教学,分为是一个章节进行分解式面试及讲解,不仅仅是面试,更像是一个专业的架构师研讨会课程。课程内容从数据结构与算法、Spring Framwork、JVM原理、 JUC并…...
uniapp实现文件和图片选择上传功能实现
主要介绍了uni-file-picker文件选择上传,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下 上传一张: <template><view class="container example"><uni-forms ref="baseForm" …...
2024认证杯数学建模C题思路模型代码
目录 2024认证杯数学建模C题思路模型代码:4.11开赛后第一时间更新,获取见文末名片 以下为2023年认证杯C题: 2024年认证杯数学建模C题思路模型代码见此 2024认证杯数学建模C题思路模型代码:4.11开赛后第一时间更新,获…...
springcloud项目中,nacos远程的坑
我将允许重写放在了远程nacos的注册中心,还是无法启动。这个bug,想想确实也可以解决。 解决方案 1.配置到bootstrap.yml或者application.yml中 2.实现EnvironmentPostProcessor并设置值,并在META-INF中注入我们的类 org.springframework.boot…...
南京航空航天大学-考研科目-513测试技术综合 高分整理内容资料-01-单片机原理及应用分层教程-单片机有关常识部分
系列文章目录 高分整理内容资料-01-单片机原理及应用分层教程-单片机有关常识部分 文章目录 系列文章目录前言总结 前言 单片机的基础内容繁杂,有很多同学基础不是很好,对一些细节也没有很好的把握。非常推荐大家去学习一下b站上的哈工大 单片机原理及…...
【python】Flask Web框架
文章目录 WSGI(Web服务器网关接口)示例Web应用程序Web框架Flask框架创建项目安装Flask创建一个基本的 Flask 应用程序调试模式路由添加变量构造URLHTTP方法静态文件模板—— Jinja2模板文件(Template File)<...
Electron+React 搭建桌面应用
创建应用程序 创建 Electron 应用 使用 Webpack 创建新的 Electron 应用程序: npm init electron-applatest my-new-app -- --templatewebpack 启动应用 npm start 设置 Webpack 配置 添加依赖包,确保可以正确使用 JSX 和其他 React 功能ÿ…...
基于Android的记单词App系统的设计与实现
博主介绍:✌IT徐师兄、7年大厂程序员经历。全网粉丝15W、csdn博客专家、掘金/华为云//InfoQ等平台优质作者、专注于Java技术领域和毕业项目实战✌ 🍅文末获取源码联系🍅 👇🏻 精彩专栏推荐订阅👇dz…...
web vue 项目 Docker化部署
Web 项目 Docker 化部署详细教程 目录 Web 项目 Docker 化部署概述Dockerfile 详解 构建阶段生产阶段 构建和运行 Docker 镜像 1. Web 项目 Docker 化部署概述 Docker 化部署的主要步骤分为以下几个阶段: 构建阶段(Build Stage):…...
MPNet:旋转机械轻量化故障诊断模型详解python代码复现
目录 一、问题背景与挑战 二、MPNet核心架构 2.1 多分支特征融合模块(MBFM) 2.2 残差注意力金字塔模块(RAPM) 2.2.1 空间金字塔注意力(SPA) 2.2.2 金字塔残差块(PRBlock) 2.3 分类器设计 三、关键技术突破 3.1 多尺度特征融合 3.2 轻量化设计策略 3.3 抗噪声…...
uniapp微信小程序视频实时流+pc端预览方案
方案类型技术实现是否免费优点缺点适用场景延迟范围开发复杂度WebSocket图片帧定时拍照Base64传输✅ 完全免费无需服务器 纯前端实现高延迟高流量 帧率极低个人demo测试 超低频监控500ms-2s⭐⭐RTMP推流TRTC/即构SDK推流❌ 付费方案 (部分有免费额度&#x…...
多模态大语言模型arxiv论文略读(108)
CROME: Cross-Modal Adapters for Efficient Multimodal LLM ➡️ 论文标题:CROME: Cross-Modal Adapters for Efficient Multimodal LLM ➡️ 论文作者:Sayna Ebrahimi, Sercan O. Arik, Tejas Nama, Tomas Pfister ➡️ 研究机构: Google Cloud AI Re…...
Java数值运算常见陷阱与规避方法
整数除法中的舍入问题 问题现象 当开发者预期进行浮点除法却误用整数除法时,会出现小数部分被截断的情况。典型错误模式如下: void process(int value) {double half = value / 2; // 整数除法导致截断// 使用half变量 }此时...
微服务通信安全:深入解析mTLS的原理与实践
🔥「炎码工坊」技术弹药已装填! 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 一、引言:微服务时代的通信安全挑战 随着云原生和微服务架构的普及,服务间的通信安全成为系统设计的核心议题。传统的单体架构中&…...
计算机系统结构复习-名词解释2
1.定向:在某条指令产生计算结果之前,其他指令并不真正立即需要该计算结果,如果能够将该计算结果从其产生的地方直接送到其他指令中需要它的地方,那么就可以避免停顿。 2.多级存储层次:由若干个采用不同实现技术的存储…...
ABAP设计模式之---“Tell, Don’t Ask原则”
“Tell, Don’t Ask”是一种重要的面向对象编程设计原则,它强调的是对象之间如何有效地交流和协作。 1. 什么是 Tell, Don’t Ask 原则? 这个原则的核心思想是: “告诉一个对象该做什么,而不是询问一个对象的状态再对它作出决策。…...
【中间件】Web服务、消息队列、缓存与微服务治理:Nginx、Kafka、Redis、Nacos 详解
Nginx 是什么:高性能的HTTP和反向代理Web服务器。怎么用:通过配置文件定义代理规则、负载均衡、静态资源服务等。为什么用:提升Web服务性能、高并发处理、负载均衡和反向代理。优缺点:轻量高效,但动态处理能力较弱&am…...
SQL 注入开放与修复
开发: SQL 注入是一种数据库攻击手段。攻击者通过向应用程序提交恶意代码来改变原 SQL 语句的含义, 进而执行任意 SQL 命令,达到入侵数据库乃至操作系统的目的。 例如:下面代码片段中,动态构造并执行了一个 SQ…...




