广西网站建设开发外包,上海正规做网站公司有哪些,长春微信做网站,360站长平台并查集前言一、按字典序排列的最小的等价字符串二、并查集总结参考文献前言
并查集有什么用#xff1f;并查集是什么#xff1f;搞懂这两个问题#xff0c;相关的并查集问题就变得非常easy#xff01;
一、按字典序排列的最小的等价字符串 二、并查集
有一种方法#x…
并查集前言一、按字典序排列的最小的等价字符串二、并查集总结参考文献前言
并查集有什么用并查集是什么搞懂这两个问题相关的并查集问题就变得非常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 按字典序排列的最小等价字符串
