并查集

并查集通用类

private class UnionFind{
        public int[] parent;
        public int[] rank;
        public int setcount;
        public UnionFind(int n) {
            this.parent = new int[n];
            this.rank = new int[n];
            for(int i=0;i<n;i++){
                parent[i] = i;
                rank[i] = 1;
            }
            this.setcount = n;
        }
        public void union(int x,int y){
            int rootx = find(x);
            int rooty = find(y);
            if(rootx==rooty) return;
            if(rank[rootx]==rank[rooty]){
                parent[rootx] = rooty;
                rank[rooty]++;
            }else if(rank[rootx]<rank[rooty]){
                parent[rootx] = rooty;
            }else {
                parent[rooty] = rootx;
            }
            this.setcount--;
        }
        public int find(int y) {
        if(y!=parent[y]){
            parent[y] = find(parent[y]);
        }
        return parent[y];
        }
    }

Leetcode 1722.执行交换操作后到最小汉明距离

1. 思路

思路就是将sources中的点看做是图中的节点，allowedSwaps数组表示各节点之间的连接关系，然后使用UnionFind去查看这个图的连通关系，假设这个图有n个连通分量，每一个连通分量都有一个父节点，每个连通分量在sources数组中的对应值都在target中有相应的映射，需要将target中的这些值都存储起来，以便于计算汉明距离，考虑到可能有重复的元素，故使用hashMap，key是target中的对应值，value是该值在集合中的个数，然后由前面说的，这个集合对应一个连通分量的根节点，因此需要将n个结点与对应的集合映射起来，这里又用到了一个hashMap。综上所述，需要用到两层hashMap。
最后，遍历sources数组中的每个元素，先用unionFind找出根节点，然后在上述的map中看看是否有值相等的target，若有，将这个target的数量减一；若无，汉明距离加一。遍历完sources数组后返回结果即可。

2. 代码

class Solution {
public int minimumHammingDistance(int[] source, int[] target, int[][] allowedSwaps) {
        int len = source.length;
        UnionFind uf = new UnionFind(len);
        for(int[] edge:allowedSwaps){
            uf.union(edge[0],edge[1]);
        }
        //HashMap<Integer, List<Integer>> hashMap = new HashMap<>();
        int res = 0;
        Map<Integer, Map<Integer, Integer>> map = new HashMap<>();
        for(int i = 0; i < target.length; i++) {
            int f = uf.find(i);
            if(!map.containsKey(f)) {
                map.put(f, new HashMap<>());
            }
            map.get(f).put(target[i], map.get(f).getOrDefault(target[i], 0)+1);
        }
        for(int i = 0; i < source.length; i++) {
            int f = uf.find(i);
            if(!map.get(f).containsKey(source[i]) || map.get(f).get(source[i]) == 0) {
                res++;
            }else {
                map.get(f).put(source[i], map.get(f).get(source[i])-1);
            }
        }
        return res;
    }
    //并查集通用类
   public int[] parent;
        public int[] rank;
        public int setcount;
        public UnionFind(int n) {
            this.parent = new int[n];
            this.rank = new int[n];
            for(int i=0;i<n;i++){
                parent[i] = i;
                rank[i] = 1;
            }
            this.setcount = n;
        }
        public void union(int x,int y){
            int rootx = find(x);
            int rooty = find(y);
            if(rootx==rooty) return;
            if(rank[rootx]==rank[rooty]){
                parent[rootx] = rooty;
                rank[rooty]++;
            }else if(rank[rootx]<rank[rooty]){
                parent[rootx] = rooty;
            }else {
                parent[rooty] = rootx;
            }
            this.setcount--;
        }
        public int find(int y) {
        if(y!=parent[y]){
            parent[y] = find(parent[y]);
        }
        return parent[y];
   }
}

Leetcode 1202.交换字符串中的元素

1. 思路

第 1 步：先遍历 pairs 中的索引对，将索引对中成对的索引输入并查集，并查集会帮助我们实现同属于一个连通分量中的元素的合并工作。注意：并查集管理的是「索引」不是「字符」。
第 2 步：遍历输入字符串 s，对于每一个索引，找到这个索引在并查集中的代表元，把同属于一个代表元的字符放在一起。这一步需要建立一个映射关系。键：并查集中的代表元，值：同属于一个代表元的 s 中的字符。可以使用哈希表建立映射关系。

2. 代码

class Solution {
    public String smallestStringWithSwaps(String s, List<List<Integer>> pairs) {
        if(pairs.size()==0){
            return s;
        }
        int len = s.length();
        UnionFind unionFind = new UnionFind(len);
        for(List<Integer> pair:pairs){
            unionFind.union(pair.get(0),pair.get(1));
        }
        char[] charArray = s.toCharArray();
        HashMap<Integer, PriorityQueue<Character>> hashMap = new HashMap<>();
        for(int i=0;i<len;i++){
            int root = unionFind.find(i);
            hashMap.computeIfAbsent(root,key->new PriorityQueue<>()).offer(charArray[i]);
        }
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 0; i < len; i++) {
            int root = unionFind.find(i);
            stringBuilder.append(hashMap.get(root).poll());
        }
        return stringBuilder.toString();
    }
    private class UnionFind{
        private int[] parent;
        private int[] rank;
        public UnionFind(int n){
            this.parent = new int[n];
            this.rank = new int[n];
            for(int i=0;i<n;i++){
                this.parent[i] = i;
                this.rank[i] = 1;
            }
        }
        public void union(int x,int y){
            int rootx = find(x);
            int rooty = find(y);
            if(rootx==rooty) return;
            if(rank[rootx]==rank[rooty]){
                parent[rootx] = rooty;
                rank[rooty]++;
            }
            else if(rank[rootx]<rank[rooty]){
                parent[rootx] = rooty;
            }else {
                parent[rooty] = rootx;
            }
        }
        public int find(int x){
            if(x!=parent[x]){
                parent[x] = find(parent[x]);
            }
            return parent[x];
        }
    }
}