并查集

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

前言

并查集有什么用？并查集是什么？搞懂这两个问题，相关的并查集问题就变得非常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 按字典序排列的最小等价字符串