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

按字典序排列的最小的等价字符串[拆解并查集]

并查集

  • 前言
  • 一、按字典序排列的最小的等价字符串
  • 二、并查集
  • 总结
  • 参考文献

前言

并查集有什么用?并查集是什么?搞懂这两个问题,相关的并查集问题就变得非常easy!

一、按字典序排列的最小的等价字符串

在这里插入图片描述

二、并查集

有一种方法,并查集,它能将有关系的东西归为一类。
这里的问题,根据两字符的等价关系,将其归为一类,并得到最小字典序的root字符。
这里是一样的,只是选择每类的root字符时,需要比较一下,取字典序最小的字符节点作为root。

idea)构建好并查集后,遍历字符串baseStr,通过并查集寻找该字符的root,即该类最小等价字符。
注:
并查集是什么?并查集 = 数组 + union操作,经典的 数据结构 + 算法 == 程序,数组中每个元素为一个节点,根据节点的关系进行union操作,将各个节点分类。

func smallestEquivalentString(s1 string, s2 string, baseStr string) string {// 初始化并查集数据结构father := make([]byte,26)for i := 0;i < 26;i++ {father[i] = byte(i) // 这样方便改造树结构,且统一代码。i == father[i],此时返回father[i]和i的效果是一样的。}// 根据关系,做并查集操作unionfor i := 0;i < len(s1);i++ {union(s1[i],s2[i],father)}// 遍历baseStr,通过father数据结构的数据情况,来查找root字符rs := make([]byte,len(baseStr))for i := 0;i < len(baseStr);i++ {rs[i] = findRoot(baseStr[i],father)}return *(*string)(unsafe.Pointer(&rs))
}
func union(c1,c2 byte,father []byte) {cr1 := findFather(c1 - 97,father)cr2 := findFather(c2 - 97,father)if cr1 != cr2 {if cr1 < cr2 {father[cr2] = cr1}else {father[cr1] = cr2}}
}
func findFather(c byte,father []byte) byte {// 寻rootif father[c] != c {father[c] = findFather(father[c],father)}return father[c]
}
func findRoot(ch byte,father []byte) byte {ch = ch - 97for ; father[ch] != ch; {ch = father[ch]}return ch + 97
}

总结

1)并查集是什么?程序 = 数据结构+算法,并查集程序 = 数组 + union联合两节点。
2)并查集有什么用?每个数组元素为一个节点,根据节点关系union两节点,所以并查集的作用就是将元素归类。
3)并查集就像树一样,但是不是用链表来实现父子节点,而是连续内存的数组来实现。这跟字典树用arraylist来实现类似,并查集是子节点存父节点在数组中的位置,字典树是父节点存各个子节点在数组中的位置。毕竟并查集是从子找父,而字典树是从父找子。

参考文献

[1] LeetCode 按字典序排列的最小等价字符串

相关文章:

按字典序排列的最小的等价字符串[拆解并查集]

并查集前言一、按字典序排列的最小的等价字符串二、并查集总结参考文献前言 并查集有什么用&#xff1f;并查集是什么&#xff1f;搞懂这两个问题&#xff0c;相关的并查集问题就变得非常easy&#xff01; 一、按字典序排列的最小的等价字符串 二、并查集 有一种方法&#x…...

操作系统——6.系统调用

目录 1.概述 2.系统调用的定义和作用 2.1 定义 2.2 功能 2.3 分类 3.系统调用和库函数的区别 4.系统调用背后的过程 5.小结 1.概述 这篇文章我们主要来介绍一下操作系统中的系统调用&#xff0c;下面来看一下具体的框架图&#xff1a; 2.系统调用的定义和作用 2.1 定…...

JavaScript DOM操作

目录 获取元素&#xff1a; 修改元素属性&#xff1a; 添加、删除、替换元素&#xff1a; 修改样式&#xff1a; DOM&#xff08;文档对象模型&#xff09;是一种用于操作 HTML 和 XML 文档的 API。JavaScript 通过 DOM API 可以访问和操作页面中的元素、属性和样式等。 获…...

【数据结构】顺序表

文章目录前言初始化顺序表打印顺序表检查容量判空顺序表数据个数尾部插入尾部删除头部插入头部删除在pos位置插入数据删除pos位置的数据查找数据修改数据销毁顺序表整体代码写在最后前言 顺序表作为数据结构中的小小弟&#xff0c;还是很好应付的。说到数据结构&#xff0c;顺序…...

【人工智能 AI 】RPA 架构师需要具备的技能有哪些?RPA Solution Architect

RPA 架构师需要具备的技能有哪些?使用markdown格式,不少于3000字,细化到3级目录。 文章目录 一、RPA架构师需要具备的技能1. 对RPA的理解2. 对RPA技术的熟练掌握2.1 RPA系统的架构模式2.2 RPA软件的操作模式2.3 RPA程序的编写方式3. 对RPA应用的知识4. 对软件开发的基本知识…...

【模拟集成电路】鉴频鉴相器设计(Phase Frequency Detector,PFD)

鉴频鉴相器设计&#xff08;Phase Frequency Detector&#xff0c;PFD&#xff09;前言一、 PFD的工作原理二、 PFD电路设计&#xff08;1&#xff09;PFD电路图&#xff08;2&#xff09;D触发器电路图&#xff08;3&#xff09;与非门&#xff08;NAND&#xff09;电路图&…...

【Linux】进程间通信介绍 | 管道

​&#x1f320; 作者&#xff1a;阿亮joy. &#x1f386;专栏&#xff1a;《学会Linux》 &#x1f387; 座右铭&#xff1a;每个优秀的人都有一段沉默的时光&#xff0c;那段时光是付出了很多努力却得不到结果的日子&#xff0c;我们把它叫做扎根 目录&#x1f449;进程间通信…...

这次说说腾讯的一场 35K—55K 的 Android 高工面试

一、面试的由来 事情是这样的&#xff0c;因为跟公司发展一些想法的不同&#xff0c;早在十月份的时候就有了跳槽的想法&#xff0c;但是碍于老大的面子就一直就没有跟人事说出口&#xff0c;打算着等到年后金三银四在试试跳槽。 但是发生一件事终于让我忍不住了&#xff0c;…...

Jenkins第一讲

目录 一、Jenkins 1.1 敏捷开发与持续集成 1.1.1 敏捷开发 1.1.2 持续集成 1.2 持续集成工具 1.2.1 jenkins和hudson 1.2.2 技术组合 1.2.3 部署方式对比 1.3 安装Jenkins 1.3.1 下载Jenkins的war包 1.3.2 开启Jenkins 1.4 Jenkins全局安全配置 1.5 使用Jenkins部…...

变分推断 | MATLAB实现VBMC变分贝叶斯蒙特卡洛模拟的贝叶斯推断

变分推断 | MATLAB实现变分贝叶斯蒙特卡洛模拟的贝叶斯推断 目录 变分推断 | MATLAB实现变分贝叶斯蒙特卡洛模拟的贝叶斯推断效果一览基本介绍研究内容模型描述模型设计参考资料效果一览 基本介绍 MATLAB实现变分贝叶斯蒙特卡洛模拟的贝叶斯推断。变分贝叶斯蒙特卡洛(VBMC)是…...

代码随想录【Day25】| 216. 组合总和 III、17. 电话号码的字母组合

216. 组合总和 III 题目链接 题目描述&#xff1a; 找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数&#xff0c;并且每种组合中不存在重复的数字。 说明&#xff1a; 所有数字都是正整数。 解集不能包含重复的组合。 示例 1: 输入: k 3, n 7 输…...

web中git漏洞的形成的原理及使用

目录 1.Git漏洞的成因 1.不正确的权限设置&#xff1a; 2.代码注入漏洞&#xff1a; 3.未经身份验证的访问&#xff1a; 4.非安全传输&#xff1a; 5.跨站脚本攻击&#xff08;XSS&#xff09;&#xff1a; 2.git泄露环境的搭建 git init&#xff1a; git add&#xff1…...

【SPSS】单样本T检验分析详细操作教程(附案例实战)

&#x1f935;‍♂️ 个人主页&#xff1a;艾派森的个人主页 ✍&#x1f3fb;作者简介&#xff1a;Python学习者 &#x1f40b; 希望大家多多支持&#xff0c;我们一起进步&#xff01;&#x1f604; 如果文章对你有帮助的话&#xff0c; 欢迎评论 &#x1f4ac;点赞&#x1f4…...

计算机网络笔记、面试八股(三)—— HTTPS协议

本章目录3. HTTPS协议3.1 HTTPS协议简介3.2 SSL/TLS协议3.2.1 SSL/TLS功能的实现3.3 HTTP和HTTPS的区别3.4 HTTPS协议的优点3.5 HTTPS协议的缺点3.6 HTTPS协议的工作流程3.7 HTTPS是如何解决HTTP的缺点的3.7.1 解决内容可能被窃听的问题——加密3.7.1.1 方法1.对称加密3.7.1.2 …...

浅谈liunx init.d 和 rc.local 两种起动方式

浅谈liunx init.d 和 rc.local 两种起动方式 以rabbitmq 举例 &#xff08;一&#xff09;.init.d 方式 开机自动重启设置 1.在/etc/init.d 目录下新建一个 rabbitmq [rootlocalhost init.d]# vi rabbitmq具体脚本如下所示&#xff1a; #!/bin/bash # # chkconfig: 2345 …...

元宇宙+教育,正在引发哪些剧烈变革?机会在哪里?丨圆桌实录

图片来源&#xff1a;由无界AI绘画工具生成2月23日&#xff0c;温州元宇宙创新中心为2023年第一批申请入驻的项目企业举办了签约仪式。温州临境网络科技有限公司、温州好玩文化产业有限公司、温州云兮科技有限公司&#xff08;筹&#xff09;等企业完成签约。这意味着&#xff…...

追梦之旅【数据结构篇】——详解C语言实现顺序队列

详解C语言实现顺序队列~&#x1f60e;前言&#x1f64c;预备小知识&#x1f64c;队列的概念及结构&#x1f60a;1.顺序队列头文件编写&#x1f64c;2.Queue.c文件的编写&#x1f64c;1&#xff09;队列的初始化函数实现&#x1f60a;2&#xff09;队列的销毁函数实现&#x1f6…...

使用自己的数据集Fine-tune PaddleHub预训练模型

使用自己的数据Fine-tune PaddleHub预训练模型 果农需要根据水果的不同大小和质量进行产品的定价&#xff0c;所以每年收获的季节有大量的人工对水果分类的需求。基于人工智能模型的方案&#xff0c;收获的大堆水果会被机械放到传送带上&#xff0c;模型会根据摄像头拍到的图片…...

带组态物联网平台源码 代码开源可二次开发 web MQTT Modbus

物联网IOT平台开发辅助文档 技术栈&#xff1a;JAVA [ springmvc / spring / mybatis ] 、Mysql 、Html 、 Jquery 、css 使用协议和优势&#xff1a; TCP/IP、HTTP、MQTT 通讯协议 1.1系统简介 IOT通用物联网系统平台带组态&#xff0c;是一套面向通用型业务数据处理的系统…...

计算机网络的发展历程

计算机网络的历史可以追溯到20世纪60年代。那个时候&#xff0c;计算机还非常昂贵&#xff0c;只有少数大型机可以被用于处理重要任务。这些大型机通常被安装在大型企业、政府机构和大学中。由于这些机器非常昂贵&#xff0c;许多企业、机构和大学只能通过终端连接来访问它们。…...

C++_核心编程_多态案例二-制作饮品

#include <iostream> #include <string> using namespace std;/*制作饮品的大致流程为&#xff1a;煮水 - 冲泡 - 倒入杯中 - 加入辅料 利用多态技术实现本案例&#xff0c;提供抽象制作饮品基类&#xff0c;提供子类制作咖啡和茶叶*//*基类*/ class AbstractDr…...

阿里云ACP云计算备考笔记 (5)——弹性伸缩

目录 第一章 概述 第二章 弹性伸缩简介 1、弹性伸缩 2、垂直伸缩 3、优势 4、应用场景 ① 无规律的业务量波动 ② 有规律的业务量波动 ③ 无明显业务量波动 ④ 混合型业务 ⑤ 消息通知 ⑥ 生命周期挂钩 ⑦ 自定义方式 ⑧ 滚的升级 5、使用限制 第三章 主要定义 …...

ssc377d修改flash分区大小

1、flash的分区默认分配16M、 / # df -h Filesystem Size Used Available Use% Mounted on /dev/root 1.9M 1.9M 0 100% / /dev/mtdblock4 3.0M...

【OSG学习笔记】Day 16: 骨骼动画与蒙皮(osgAnimation)

骨骼动画基础 骨骼动画是 3D 计算机图形中常用的技术&#xff0c;它通过以下两个主要组件实现角色动画。 骨骼系统 (Skeleton)&#xff1a;由层级结构的骨头组成&#xff0c;类似于人体骨骼蒙皮 (Mesh Skinning)&#xff1a;将模型网格顶点绑定到骨骼上&#xff0c;使骨骼移动…...

k8s业务程序联调工具-KtConnect

概述 原理 工具作用是建立了一个从本地到集群的单向VPN&#xff0c;根据VPN原理&#xff0c;打通两个内网必然需要借助一个公共中继节点&#xff0c;ktconnect工具巧妙的利用k8s原生的portforward能力&#xff0c;简化了建立连接的过程&#xff0c;apiserver间接起到了中继节…...

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

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

mysql已经安装,但是通过rpm -q 没有找mysql相关的已安装包

文章目录 现象&#xff1a;mysql已经安装&#xff0c;但是通过rpm -q 没有找mysql相关的已安装包遇到 rpm 命令找不到已经安装的 MySQL 包时&#xff0c;可能是因为以下几个原因&#xff1a;1.MySQL 不是通过 RPM 包安装的2.RPM 数据库损坏3.使用了不同的包名或路径4.使用其他包…...

uniapp 字符包含的相关方法

在uniapp中&#xff0c;如果你想检查一个字符串是否包含另一个子字符串&#xff0c;你可以使用JavaScript中的includes()方法或者indexOf()方法。这两种方法都可以达到目的&#xff0c;但它们在处理方式和返回值上有所不同。 使用includes()方法 includes()方法用于判断一个字…...

华为OD机试-最短木板长度-二分法(A卷,100分)

此题是一个最大化最小值的典型例题&#xff0c; 因为搜索范围是有界的&#xff0c;上界最大木板长度补充的全部木料长度&#xff0c;下界最小木板长度&#xff1b; 即left0,right10^6; 我们可以设置一个候选值x(mid)&#xff0c;将木板的长度全部都补充到x&#xff0c;如果成功…...

springboot 日志类切面,接口成功记录日志,失败不记录

springboot 日志类切面&#xff0c;接口成功记录日志&#xff0c;失败不记录 自定义一个注解方法 import java.lang.annotation.ElementType; import java.lang.annotation.Retention; import java.lang.annotation.RetentionPolicy; import java.lang.annotation.Target;/***…...