题目
给你一个字符串 s，以及该字符串中的一些「索引对」数组 pairs，其中 pairs[i] = [a, b] 表示字符串中的两个索引（编号从 0 开始）。
你可以 任意多次交换 在 pairs 中任意一对索引处的字符。
返回在经过若干次交换后，s 可以变成的按字典序最小的字符串。
示例 1:
输入：s = “dcab”, pairs = [[0,3],[1,2]]
输出：“bacd”
解释：
交换 s[0] 和 s[3], s = “bcad”
交换 s[1] 和 s[2], s = “bacd”
示例 2：
输入：s = “dcab”, pairs = [[0,3],[1,2],[0,2]]
输出：“abcd”
解释：
交换 s[0] 和 s[3], s = “bcad”
交换 s[0] 和 s[2], s = “acbd”
交换 s[1] 和 s[2], s = “abcd”
示例 3：
输入：s = “cba”, pairs = [[0,1],[1,2]]
输出：“abc”
解释：
交换 s[0] 和 s[1], s = “bca”
交换 s[1] 和 s[2], s = “bac”
交换 s[0] 和 s[1], s = “abc”
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/smallest-string-with-swaps
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
这一题想了半天没有思路：看了题解，这里再梳理一下。
- 并查集
-
在两个pair中，如果有相同的数字，我们可以认为他们是一伙的，比如[0,1]和[1,2]。
举个例子
s=“abcdefg”
[[0,2],[1,3],[2,5],[4,6],[3,4]]
如上面的图，这里我们可以将其分为两个帮派：（0,2,5）和（1,3,4,6）
public String smallestStringWithSwaps(String s, List<List<Integer>> pairs) {
int length = s.length();
int[] p = new int[length];
//并查集数组初始化，每个元素都是自己的父节点
for (int i = 0; i < length; i++){
p[i] = i;
}
//pairs数组中合并，看成一个集合
for (List<Integer> pair : pairs){
union(pair.get(0), pair.get(1), p);
}
//建立集合和优先队列对应哈希表
HashMap<Integer, PriorityQueue<Character>> map = new HashMap<>();
//对于每一个字符串下标i，首先找到它对应的集合（父节点），
//并且建立对应的优先队列，并把S[i]字符储存进优先队列
for (int i = 0; i < length; i++){
int cur = find(i, p);
if (!map.containsKey(cur)){
map.put(cur, new PriorityQueue<>());
}
map.get(cur).offer(s.charAt(i));
}
//建立字符串，把对应下标所在集合对应的优先队列中的char一个个加入字符串中
StringBuilder sb = new StringBuilder();
for (int i = 0; i < length; i++){
sb.append(map.get(find(i, p)).poll());
}
return sb.toString();
}
public int find(int x, int[] p){
if (p[x] != x){
p[x] = find(p[x], p);
}
return p[x];
}
public void union(int x, int y, int[] p){
int px = find(x, p);
int py = find(y, p);
if (px != py){
p[px] = py;
}
}
初识并查集
-
问题引入：修路
首先在地图上给若干城镇，然后告诉你有哪些城镇之间是有道路连接的。
那么问题来了，最少需要修几条道路才能将所有的村庄连接起来？ -
问题抽象 ：图论中的连通集。
城镇----》点
道路----》连接点之间的线
修路：求图中有几个连通集。
如果是一个，则不需要新建道路；
如果是两个，那么至少需要修一条，即：两个连通集中，各挑一个点，这两点之间修一条路即可。
依次类推… -
什么是并查集？
并查集有两部分组成。一个数组+两个函数
一个数组：pre[]记录了每个节点的前导节点。pre[x]=y，节点x的父节点是y。
find()：查找"代表"
int find(x){
int r=x;
while(pre[x]!=r){
r=pre[r];
}
return r;
}
join():合并，最后连通。
int join(int x,int y){
int fx=find(x);
int fy=find(y);
if(fx!=fy){
pre[fx]=fy;
}