当前位置: 首页 > 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;许多企业、机构和大学只能通过终端连接来访问它们。…...

ubuntu搭建nfs服务centos挂载访问

在Ubuntu上设置NFS服务器 在Ubuntu上&#xff0c;你可以使用apt包管理器来安装NFS服务器。打开终端并运行&#xff1a; sudo apt update sudo apt install nfs-kernel-server创建共享目录 创建一个目录用于共享&#xff0c;例如/shared&#xff1a; sudo mkdir /shared sud…...

R语言AI模型部署方案:精准离线运行详解

R语言AI模型部署方案:精准离线运行详解 一、项目概述 本文将构建一个完整的R语言AI部署解决方案,实现鸢尾花分类模型的训练、保存、离线部署和预测功能。核心特点: 100%离线运行能力自包含环境依赖生产级错误处理跨平台兼容性模型版本管理# 文件结构说明 Iris_AI_Deployme…...

Redis相关知识总结(缓存雪崩,缓存穿透,缓存击穿,Redis实现分布式锁,如何保持数据库和缓存一致)

文章目录 1.什么是Redis&#xff1f;2.为什么要使用redis作为mysql的缓存&#xff1f;3.什么是缓存雪崩、缓存穿透、缓存击穿&#xff1f;3.1缓存雪崩3.1.1 大量缓存同时过期3.1.2 Redis宕机 3.2 缓存击穿3.3 缓存穿透3.4 总结 4. 数据库和缓存如何保持一致性5. Redis实现分布式…...

通过Wrangler CLI在worker中创建数据库和表

官方使用文档&#xff1a;Getting started Cloudflare D1 docs 创建数据库 在命令行中执行完成之后&#xff0c;会在本地和远程创建数据库&#xff1a; npx wranglerlatest d1 create prod-d1-tutorial 在cf中就可以看到数据库&#xff1a; 现在&#xff0c;您的Cloudfla…...

【服务器压力测试】本地PC电脑作为服务器运行时出现卡顿和资源紧张(Windows/Linux)

要让本地PC电脑作为服务器运行时出现卡顿和资源紧张的情况&#xff0c;可以通过以下几种方式模拟或触发&#xff1a; 1. 增加CPU负载 运行大量计算密集型任务&#xff0c;例如&#xff1a; 使用多线程循环执行复杂计算&#xff08;如数学运算、加密解密等&#xff09;。运行图…...

如何在网页里填写 PDF 表格?

有时候&#xff0c;你可能希望用户能在你的网站上填写 PDF 表单。然而&#xff0c;这件事并不简单&#xff0c;因为 PDF 并不是一种原生的网页格式。虽然浏览器可以显示 PDF 文件&#xff0c;但原生并不支持编辑或填写它们。更糟的是&#xff0c;如果你想收集表单数据&#xff…...

Java求职者面试指南:Spring、Spring Boot、MyBatis框架与计算机基础问题解析

Java求职者面试指南&#xff1a;Spring、Spring Boot、MyBatis框架与计算机基础问题解析 一、第一轮提问&#xff08;基础概念问题&#xff09; 1. 请解释Spring框架的核心容器是什么&#xff1f;它在Spring中起到什么作用&#xff1f; Spring框架的核心容器是IoC容器&#…...

VM虚拟机网络配置(ubuntu24桥接模式):配置静态IP

编辑-虚拟网络编辑器-更改设置 选择桥接模式&#xff0c;然后找到相应的网卡&#xff08;可以查看自己本机的网络连接&#xff09; windows连接的网络点击查看属性 编辑虚拟机设置更改网络配置&#xff0c;选择刚才配置的桥接模式 静态ip设置&#xff1a; 我用的ubuntu24桌…...

【Redis】笔记|第8节|大厂高并发缓存架构实战与优化

缓存架构 代码结构 代码详情 功能点&#xff1a; 多级缓存&#xff0c;先查本地缓存&#xff0c;再查Redis&#xff0c;最后才查数据库热点数据重建逻辑使用分布式锁&#xff0c;二次查询更新缓存采用读写锁提升性能采用Redis的发布订阅机制通知所有实例更新本地缓存适用读多…...

全面解析数据库:从基础概念到前沿应用​

在数字化时代&#xff0c;数据已成为企业和社会发展的核心资产&#xff0c;而数据库作为存储、管理和处理数据的关键工具&#xff0c;在各个领域发挥着举足轻重的作用。从电商平台的商品信息管理&#xff0c;到社交网络的用户数据存储&#xff0c;再到金融行业的交易记录处理&a…...