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…...
Prompt Tuning、P-Tuning、Prefix Tuning的区别
一、Prompt Tuning、P-Tuning、Prefix Tuning的区别 1. Prompt Tuning(提示调优) 核心思想:固定预训练模型参数,仅学习额外的连续提示向量(通常是嵌入层的一部分)。实现方式:在输入文本前添加可训练的连续向量(软提示),模型只更新这些提示参数。优势:参数量少(仅提…...
【git】把本地更改提交远程新分支feature_g
创建并切换新分支 git checkout -b feature_g 添加并提交更改 git add . git commit -m “实现图片上传功能” 推送到远程 git push -u origin feature_g...
NLP学习路线图(二十三):长短期记忆网络(LSTM)
在自然语言处理(NLP)领域,我们时刻面临着处理序列数据的核心挑战。无论是理解句子的结构、分析文本的情感,还是实现语言的翻译,都需要模型能够捕捉词语之间依时序产生的复杂依赖关系。传统的神经网络结构在处理这种序列依赖时显得力不从心,而循环神经网络(RNN) 曾被视为…...
OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别
OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别 直接训练提示词嵌入向量的核心区别 您提到的代码: prompt_embedding = initial_embedding.clone().requires_grad_(True) optimizer = torch.optim.Adam([prompt_embedding...
OpenLayers 分屏对比(地图联动)
注:当前使用的是 ol 5.3.0 版本,天地图使用的key请到天地图官网申请,并替换为自己的key 地图分屏对比在WebGIS开发中是很常见的功能,和卷帘图层不一样的是,分屏对比是在各个地图中添加相同或者不同的图层进行对比查看。…...
分布式增量爬虫实现方案
之前我们在讨论的是分布式爬虫如何实现增量爬取。增量爬虫的目标是只爬取新产生或发生变化的页面,避免重复抓取,以节省资源和时间。 在分布式环境下,增量爬虫的实现需要考虑多个爬虫节点之间的协调和去重。 另一种思路:将增量判…...
Pinocchio 库详解及其在足式机器人上的应用
Pinocchio 库详解及其在足式机器人上的应用 Pinocchio (Pinocchio is not only a nose) 是一个开源的 C 库,专门用于快速计算机器人模型的正向运动学、逆向运动学、雅可比矩阵、动力学和动力学导数。它主要关注效率和准确性,并提供了一个通用的框架&…...
Docker 本地安装 mysql 数据库
Docker: Accelerated Container Application Development 下载对应操作系统版本的 docker ;并安装。 基础操作不再赘述。 打开 macOS 终端,开始 docker 安装mysql之旅 第一步 docker search mysql 》〉docker search mysql NAME DE…...
【VLNs篇】07:NavRL—在动态环境中学习安全飞行
项目内容论文标题NavRL: 在动态环境中学习安全飞行 (NavRL: Learning Safe Flight in Dynamic Environments)核心问题解决无人机在包含静态和动态障碍物的复杂环境中进行安全、高效自主导航的挑战,克服传统方法和现有强化学习方法的局限性。核心算法基于近端策略优化…...
【笔记】WSL 中 Rust 安装与测试完整记录
#工作记录 WSL 中 Rust 安装与测试完整记录 1. 运行环境 系统:Ubuntu 24.04 LTS (WSL2)架构:x86_64 (GNU/Linux)Rust 版本:rustc 1.87.0 (2025-05-09)Cargo 版本:cargo 1.87.0 (2025-05-06) 2. 安装 Rust 2.1 使用 Rust 官方安…...




