当前位置: 首页 > 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 按字典序排列的最小等价字符串

http://www.lryc.cn/news/19641.html

相关文章:

  • 操作系统——6.系统调用
  • JavaScript DOM操作
  • 【数据结构】顺序表
  • 【人工智能 AI 】RPA 架构师需要具备的技能有哪些?RPA Solution Architect
  • 【模拟集成电路】鉴频鉴相器设计(Phase Frequency Detector,PFD)
  • 【Linux】进程间通信介绍 | 管道
  • 这次说说腾讯的一场 35K—55K 的 Android 高工面试
  • Jenkins第一讲
  • 变分推断 | MATLAB实现VBMC变分贝叶斯蒙特卡洛模拟的贝叶斯推断
  • 代码随想录【Day25】| 216. 组合总和 III、17. 电话号码的字母组合
  • web中git漏洞的形成的原理及使用
  • 【SPSS】单样本T检验分析详细操作教程(附案例实战)
  • 计算机网络笔记、面试八股(三)—— HTTPS协议
  • 浅谈liunx init.d 和 rc.local 两种起动方式
  • 元宇宙+教育,正在引发哪些剧烈变革?机会在哪里?丨圆桌实录
  • 追梦之旅【数据结构篇】——详解C语言实现顺序队列
  • 使用自己的数据集Fine-tune PaddleHub预训练模型
  • 带组态物联网平台源码 代码开源可二次开发 web MQTT Modbus
  • 计算机网络的发展历程
  • 【华为OD机试模拟题】用 C++ 实现 - 不含 101 的数(2023.Q1)
  • 面试题-下单后位置信息上报的方案
  • 视觉人培训团队把它称之为,工业领域人类最伟大的软件创造,它的名字叫Halcon
  • 干了2年的手工点点点,感觉每天浑浑噩噩,我的自动化测试之路...
  • 嵌入式系统硬件设计与实践(学习方法)
  • 如何拥有自己的Gitee代码仓库
  • 通用信息抽取技术UIE产业案例解析,Prompt 范式落地经验分享!
  • integrationobjects/OPC AE Client ActiveX Crack
  • JavaScript HTML DOM 简介
  • interrupt多线程设计模式
  • Spring IoC 和 Spring AOP