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

并查集及其优化

1.并查集

#define SIZE 100
int UFSets[SIZE];void Initial(int S[]) {for (int i = 0; i < SIZE; i++)S[i]=-1;
}int Find(int S[], int x) {//查while(S[x] >= 0)x = S[x];return x;
}void Union(int S[], int Root1, int Root2) {//并if(Root1 == Root2)return;S[Root2] = Root1;
}

Find操作最坏时间复杂度:O(n)
Union操作最坏时间复杂度:O(1)
优化Union操作,小树并入大树,减少Find操作的复杂度。

2.优化

void Union(int S[], int Root1, int Root2) {if(Root1 == Root2)return;if(Root2 > Root1) {S[Root1] += S[Root2];S[Root2] = Root1;}else {S[Root2] += S[Root1];S[Root1] = Root2;}
}

Find操作最坏时间复杂度:O(logn)

2.进一步优化:压缩路径

优化Find操作,使树更矮。

int Find(int S[], int x) {int root = x;while(S[x] >= 0)root = S[root];while(x != root) {int t = S[x];S[x] = root;x = t;}return root;
}

Find操作最坏时间复杂度:O(α(n))

相关文章:

并查集及其优化

1.并查集 #define SIZE 100 int UFSets[SIZE];void Initial(int S[]) {for (int i 0; i < SIZE; i)S[i]-1; }int Find(int S[], int x) {//查while(S[x] > 0)x S[x];return x; }void Union(int S[], int Root1, int Root2) {//并if(Root1 Root2)return;S[Root2] Roo…...

LeetCode 周赛上分之旅 #48 一道简单的树上动态规划问题

⭐️ 本文已收录到 AndroidFamily&#xff0c;技术和职场问题&#xff0c;请关注公众号 [彭旭锐] 和 BaguTree Pro 知识星球提问。 学习数据结构与算法的关键在于掌握问题背后的算法思维框架&#xff0c;你的思考越抽象&#xff0c;它能覆盖的问题域就越广&#xff0c;理解难度…...

mysql报错:Column Count Doesn‘t Match Value Count at Row 1

mysql中执行insert、update、delete报错&#xff1a;Column Count Doesnt Match Value Count at Row 1 的解决方案 通常情况&#xff1a;字段不匹配 如&#xff1a;student有id, name, age字段 -- 错误写法 INSERT INTO student VALUES(5,horse)-- 正确写法 INSERT INTO stu…...

安卓 kuaishou 设备did和egid 学习分析

did和egid注册 接口 https://gdfp.ksapisrv.com/rest/infra/gdfp/report/kuaishou/android did 是本地生成的16进制 或者 获取的 android_id public static final Random f16237a new Random(System.currentTimeMillis()); public static long m19668a() { return f1623…...

基于Vue+ELement实现增删改查案例与表单验证(附源码)

&#x1f389;&#x1f389;欢迎来到我的CSDN主页&#xff01;&#x1f389;&#x1f389; &#x1f3c5;我是Java方文山&#xff0c;一个在CSDN分享笔记的博主。&#x1f4da;&#x1f4da; &#x1f31f;推荐给大家我的专栏《ELement》。&#x1f3af;&#x1f3af; &#x1…...

webpack:使用externals配置来排除打包后的某个依赖插件IgnorePlugin的使用

背景 假设&#xff0c;我们写了一个库并使用 webpack 打包输出 bundle&#xff0c;但是这个库依赖一个第三方包&#xff0c;比如依赖 lodash&#xff0c;这时候我们不想把这个库打包进 bundle 里因为体积会变大&#xff0c;而且我们的主项目里已经安装了这个 lodash&#xff0…...

2023年中国工业脱水机行业供需分析:随着自动化和智能化技术的快速发展,销量同比增长4.9%[图]

工业脱水机行业是指专门从湿润的固体物料中去除水分的设备制造和相关服务。它广泛应用于食品加工、化工、制药、纺织、环保等行业&#xff0c;用于去除物料中的水分&#xff0c;提高产品质量和降低能耗。 工业脱水机行业分类 资料来源&#xff1a;共研产业咨询&#xff08;共研…...

[论文笔记]MacBERT

引言 今天带来MacBERT的阅读笔记。论文题目是 重新审视中文自然语言处理的预训练模型。 本篇主要是探讨中文预训练语言模型在非英文语言中的有效性,然后提出了一种简单而有效的模型,称为MacBERT,它在多个方面改进了RoBERTa,特别是采用纠错型掩码语言模型(MLM as correcti…...

AI发展目前最大挑战是什么?

影响AI成本的因素包括多个方面&#xff1a; 首先&#xff0c;AI技术的复杂性是其成本高昂的一个重要原因。AI技术需要进行大量数据处理、模型训练和优化&#xff0c;这需要耗费大量的计算资源和时间。同时&#xff0c;AI技术需要高水平的专业人才进行设计、开发和维护&#xf…...

自然语言处理NLP:LTP、SnowNLP、HanLP 常用NLP工具和库对比

文章目录 常见NLP任务常见NLP工具英文NLP工具中文NLP工具 常见NLP任务 Word Segmentation 分词 – Tokenization Stem extraction 词干提取 - Stemming Lexical reduction 词形还原 – Lemmatization Part of Speech Tagging 词性标注 – Parts of Speech Named entity rec…...

百度交易中台之内容分润结算系统架构浅析

作者 | 交易中台团队 导读 随着公司内容生态的蓬勃发展&#xff0c;内容产出方和流量提供方最关注的“收益结算”的工作&#xff0c;也就成为重中之重。本文基于内容分润结算业务为入口&#xff0c;介绍了实现过程中的重难点&#xff0c;比如千万级和百万级数据量下的技术选型和…...

【索引】常见的索引、B+树结构、什么时候需要使用索引、优化索引方法、索引主要的数据结构、聚簇索引、二级索引、创建合适的索引等重点知识汇总

目录 索引的分类 什么时候需要 / 不需要创建索引&#xff1f; 有什么优化索引的方法 MySQL索引主要使用的两种数据结构是什么 为什么 MySQL 采用 B 树作为索引 聚簇索引和二级索引 根据给定的表&#xff0c;如何创建索引比较好 索引的分类 普通索引&#xff1a;最基本的…...

Egg 封装接口返回信息

中间件封装 代码 const msgArr {"200":成功,"401":token失效 } module.exports (option, app) > {return async function(ctx, next) {try{//成功是返回的信息ctx.emit(code,data,msg)>{console.log(1111,code,data,msg)ctx.body {code,data:dat…...

Android AMS——创建APP进程(五)

接上一篇,在 ActivityTaskSupervisor 中会判断进程是否存在,如果进程不存在,则会创建进程,执行 startProcessAsync() 方法。如果进程存在,则执行 realStartActivityLocked() 方法。在APP 的启动时,进程是不存在的。所以我们先来分析一下进程不存在的情况。 一、创建进程…...

凉鞋的 Unity 笔记 102. 场景层次 与 GameObject 的增删改查

102. 场景层次 与 GameObject 的增删改查 在上一篇&#xff0c;我们完成了 Unity 引擎的 Hello world 输出&#xff0c;并且完成了第一个基本循环&#xff1a; 通过这次基本循环的完成&#xff0c;我们获得了一点点的 Unity 使用经验&#xff0c;这非常重要。 有实践经验后再…...

信息安全:网络安全审计技术原理与应用.

信息安全&#xff1a;网络安全审计技术原理与应用. 网络安全审计是指对网络信息系统的安全相关活动信息进行获取、记录、存储、分析和利用的工作。网络安全审计的作用在于建立“事后“安全保障措施&#xff0c;保存网络安全事件及行为信息&#xff0c;为网络安全事件分析提供线…...

嵌入式Linux应用开发-第十三章APP怎么读取按键值

嵌入式Linux应用开发-第十三章读取按键及按键驱动程序 第十三章 APP怎么读取按键值13.1 妈妈怎么知道孩子醒了13.2 APP读取按键的4种方法13.2.1 查询方式13.2.2 休眠-唤醒方式13.2.3 poll方式13.2.4 异步通知方式13.2.4.1 异步通知的原理&#xff1a;发信号13.2.4.2 应用程序之…...

Web 中间件怎么玩?

本次主要是聊聊关于 web 中间件&#xff0c; 分为如下四个方面 什么是 web 框架中间件 为什么要使用 web 中间件 如何使用及其原理 哪些场景需要使用中间件 开门见山 web 中间件是啥 Web 框架中的中间件主要指的是在 web 请求到具体路由之前或者之后&#xff0c;会经过一个或…...

HMTL知识点系列(4)

目录 1. 在你过去的项目中&#xff0c;你如何解决HTML的布局和样式问题&#xff1f;2. 你能否解释一下HTML的“文档对象模型”&#xff08;DOM&#xff09;是什么&#xff0c;以及它的重要性&#xff1f;3. 你有没有经验处理网页的兼容性问题&#xff0c;特别是在不同浏览器之间…...

CFS内网穿透靶场实战

一、简介 不久前做过的靶场。 通过复现CFS三层穿透靶场&#xff0c;让我对漏洞的利用&#xff0c;各种工具的使用以及横向穿透技术有了更深的理解。 一开始nmap探测ip端口,直接用thinkphpv5版本漏洞工具反弹shell&#xff0c;接着利用蚁剑对服务器直接进行控制&#xff0c;留下…...

【RabbitMQ实战】07 3分钟部署一个RabbitMQ集群

一、集群的安装部署 我们还是利用docker来安装RabbitMQ集群。3分钟安装一个集群&#xff0c;开始。 前提条件&#xff0c;docker安装了docker-compose。如果没安装的话&#xff0c;参考这里 docker-compose文件参考bitnami官网&#xff1a;https://github.com/bitnami/contai…...

PS 切片工具 选择切片 切片存储

上文 PS 透视裁剪工具 中 我们简单讲述了透视裁剪工具 今天 我们来讲他后面的切片工具 首先 他的用途还是很多的 例如 你有一个很大的图片 其中包括 轮播 导航 主题内容 但他们都在一个图片上 你就可以用切片工具 将完整的图片切成多个部分 这里 我们选择了切片工具 光标也会…...

Git版本控制系统

概念&#xff1a; 一个免费的 开源 分布式源码仓库&#xff0c;帮助团队维护代码 个人使用 多人联机使用 git安装: 这里直接看大佬的安装 文章 很不错的 git 安装配置https://blog.csdn.net/mukes/article/details/115693833 安装完毕之后&#xff1a; 使用命名git -v查看…...

Element UI搭建首页导航和左侧菜单以及Mock.js和(组件通信)总线的运用

目录 前言 一、Mock.js简介及使用 1.Mock.js简介 1.1.什么是Mock.js 1.2.Mock.js的两大特性 1.3.Mock.js使用的优势 1.4.Mock.js的基本用法 1.5.Mock.js与前端框架的集成 2.Mock.js的使用 2.1安装Mock.js 2.2.引入mockjs 2.3.mockjs使用 2.3.1.定义测试数据文件 2…...

What is an HTTP Flood DDoS attack?

HTTP 洪水攻击是一种针对 Web 和应用程序服务器的第 7 层分布式拒绝服务 &#xff08;DDoS&#xff09; 攻击。HTTP 洪水攻击通过使用 HTTP GET 或 HTTP POST 请求执行 DDoS 攻击。这些请求是有效的&#xff0c;并且针对可用资源&#xff0c;因此很难防范 HTTP 洪水攻击。 匿名…...

第 114 场 LeetCode 双周赛题解

A 收集元素的最少操作次数 模拟: 反序遍历数组&#xff0c;用一个集合存当前遍历过的不超过 k k k 的正数 class Solution { public:int minOperations(vector<int> &nums, int k) {unordered_set<int> vis;int n nums.size();int i n - 1;for (;; i--) {if…...

[Java框架] Java常用爬虫框架推荐

Selenium GitHub 截止 2023年9月份 Star数量27.7K Selenium是一款基于浏览器自动化的工具&#xff0c;它可以模拟用户在浏览器上的操作行为&#xff0c;并获取网页上的内容。Selenium支持多种浏览器&#xff0c;可以很好地处理JavaScript生成内容。但是Selenium相较于其他框架而…...

Kafka:安装与简单使用

文章目录 下载安装windows安装目录结构启动服务器创建主题发送一些消息启动消费者设置多代理集群常见问题 工具kafka tool 常用指令topic查看topic删除topic 常见问题参考文献 下载安装 下载地址&#xff1a;kafka-download windows安装 下载完后&#xff0c;找一个目录解压…...

029-从零搭建微服务-消息队列(一)

写在最前 如果这个项目让你有所收获&#xff0c;记得 Star 关注哦&#xff0c;这对我是非常不错的鼓励与支持。 源码地址&#xff08;后端&#xff09;&#xff1a;mingyue: &#x1f389; 基于 Spring Boot、Spring Cloud & Alibaba 的分布式微服务架构基础服务中心 源…...

Python2020年06月Python二级 -- 编程题解析

题目一 数字转汉字 用户输入一个1~9&#xff08;包含1和9&#xff09;之间的任一数字&#xff0c;程序输出对应的汉字。 如输入2&#xff0c;程序输出“二”。可重复查询。 答案: 方法一 list1[一,二,三,四,五,六,七,八,九] while True:n int(input(请输入1~9之间任意一个数字…...

网站建设人员培训/网站如何快速收录

wrap是包裹元素的作用&#xff0c;比如我想在img外面包裹一个a标签时&#xff0c;可以这样写法&#xff1a; $(function(){$(img).wrap(function(){return <a href" this.src " title"点击查看原图" target"_blank"></a>;}) }); 此…...

中国建设银行培训网站/网络推广软件免费

文章目录1、新建xcs格式文本2、打开xshell&#xff0c;导入配置文件3、配色方案效果图1、新建xcs格式文本 [skycolor] text00ff80 cyan(bold)00ffff text(bold)e9e9e9 magentac000c0 green80ff00 green(bold)3c5a38 background042028 cyan00c0c0 red(bold)ff0000 yellowc0c000…...

微网站开发平台 开源/网站建设公司哪家好?

如何删除一行 sed -i /search some thing/d nginx.conf...

网上购物网站建设的实训报告/舆情信息

1.正则表达式回溯问题解析转载于:https://www.cnblogs.com/MagicalFool/p/10077399.html...

手机自建网站平台/seo短期培训班

《 python 金融数据挖掘及其应用》 课程教学 大纲 课程代码&#xff1a; 学 分&#xff1a; 5 学 时&#xff1a; 80 &#xff08;其中&#xff1a;讲课学时&#xff1a; 60 实践或实验学时&#xff1a; 20 &#xff09; 先修课程&#xff1a;数学分析、高等代数、概率统计、金…...

视频剪辑培训班的学费是多少/seo关键词排名系统

1.前言前几天&#xff0c;用es6的语法重写了我的一个代码库&#xff0c;说是重写&#xff0c;其实改动的并不多&#xff0c;工作量不大。在重写完了的时候&#xff0c;就个人总结了一下es6常用的一些常用的语法和比es5优越的方面。下面提到的语法可能也就是es6新特性的10%-20%&…...