并查集

并查集框架结构：

class UF {
    int count;
    int[] parent;
    int[] size;

    public UF(int n) {
        this.count = n;
        this.parent = new int[n];
        this.size = new int[n];

        for(int i = 0; i < n; i++) {
            this.parent[i] = i;
            this.size[i] = 1;
        }
    }

    public void connect(int p, int q) {
        int rootP = find(p);
        int rootQ = find(q);

        if(rootP == rootQ) {
            return;
        }
　　　　　//降低树的高度
        if(size[rootP] > size[rootQ]) {
            parent[rootQ] = rootP;
            size[rootP] += size[rootQ];
        } else {
            parent[rootP] = rootQ;
            size[rootQ] += size[rootP];
        }
        count--;
    }

    public boolean isConnected(int p, int q) {
        int rootP = find(p);
        int rootQ = find(q);

        if(rootP == rootQ) {
            return true;
        } else {
            return false;
        }
    }

    public int find(int x) {
　　　　 //路径压缩
        while(parent[x] != x) {
            parent[x] = parent[parent[x]];
            x = parent[x];
        }

        return x;
    }
}

1202. 交换字符串中的元素

给你一个字符串 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"

class Solution {
    public String smallestStringWithSwaps(String s, List> pairs) {
        UF uf = new UF(s.length());

        for(List pair : pairs) {
            int from = pair.get(0);
            int end = pair.get(1);
            uf.connect(from, end);
        }

        HashMap> charMap = new HashMap<>();

        for(int i = 0; i < s.length(); i++) {
            int parent = uf.find(i);
            charMap.computeIfAbsent(parent, key -> new PriorityQueue<>()).offer(s.charAt(i));
        }

        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < s.length(); i++) {
            int parent = uf.find(i);
            sb.append(charMap.get(parent).poll());
        }
        return sb.toString();
    }
}

class UF {
    int count;
    int[] parent;
    int[] size;

    public UF(int n) {
        this.count = n;
        this.parent = new int[n];
        this.size = new int[n];

        for(int i = 0; i < n; i++) {
            this.parent[i] = i;
            this.size[i] = 1;
        }
    }

    public void connect(int p, int q) {
        int rootP = find(p);
        int rootQ = find(q);

        if(rootP == rootQ) {
            return;
        }

        if(size[rootP] > size[rootQ]) {
            parent[rootQ] = rootP;
            size[rootP] += size[rootQ];
        } else {
            parent[rootP] = rootQ;
            size[rootQ] += size[rootP];
        }
        count--;
    }

    public boolean isConnected(int p, int q) {
        int rootP = find(p);
        int rootQ = find(q);

        if(rootP == rootQ) {
            return true;
        } else {
            return false;
        }
    }

    public int find(int x) {

        while(parent[x] != x) {
            parent[x] = parent[parent[x]];
            x = parent[x];
        }

        return x;
    }

}

朋友圈

题目描述

? 所谓一个朋友圈子，不一定其中的人都互相直接认识。

? 例如：小张的朋友是小李，小李的朋友是小王，那么他们三个人属于一个朋友圈。

? 现在给出一些人的朋友关系，人按照从  到  编号在这中间会进行询问某两个人是否属于一个朋友圈，请你编写程序，实现这个过程。

import java.util.Scanner;

class UF {
    public int count;
    private int[] parent;
    private int[] size;

    public UF(int n) {
        this.count = n;
        this.parent = new int[n+1];
        this.size = new int[n + 1];

        for(int i = 1; i <= n; i++) {
            parent[i] = i;
            size[i] = 1;
        }
    }

    public void connect(int p, int q) {
        int rootP = find(p);
        int rootQ = find(q);

        if(rootP == rootQ) {
            return;
        }
        if(size[rootP] > rootQ) {
            parent[rootQ] = rootP;
            size[rootP] += size[rootQ];
        } else {
            parent[rootP] = rootQ;
            size[rootQ] += size[rootP];
        }
        count--;
    }

    public int find(int x) {
        while(parent[x] != x) {
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    }

    public boolean isConnected(int p, int q) {
        return find(p) == find(q);
    }

}

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int personCount = scanner.nextInt();
        int ops = scanner.nextInt();
        UF uf = new UF(personCount);
        StringBuilder sb = new StringBuilder();
        while(ops-- > 0) {
            if(uf.count <= 1) {
                sb.append("Yes\n");
                continue;
            }
            if(scanner.nextInt() == 1) {
                uf.connect(scanner.nextInt(),scanner.nextInt());
            } else {
                if(uf.isConnected(scanner.nextInt(),scanner.nextInt())) {
                    sb.append("Yes\n");
                } else {
                    sb.append("No\n");
                }
            }
        }
        System.out.print(sb);
        scanner.close();
    }
}

947. 移除最多的同行或同列石头

n 块石头放置在二维平面中的一些整数坐标点上。每个坐标点上最多只能有一块石头。

如果一块石头的 同行或者同列 上有其他石头存在，那么就可以移除这块石头。

给你一个长度为 n 的数组 stones ，其中 stones[i] = [xi, yi] 表示第 i 块石头的位置，返回 可以移除的石子 的最大数量。

示例 1：

输入：stones = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]
输出：5
解释：一种移除 5 块石头的方法如下所示：
1. 移除石头 [2,2] ，因为它和 [2,1] 同行。
2. 移除石头 [2,1] ，因为它和 [0,1] 同列。
3. 移除石头 [1,2] ，因为它和 [1,0] 同行。
4. 移除石头 [1,0] ，因为它和 [0,0] 同列。
5. 移除石头 [0,1] ，因为它和 [0,0] 同行。
石头 [0,0] 不能移除，因为它没有与另一块石头同行/列。

示例 2：

输入：stones = [[0,0],[0,2],[1,1],[2,0],[2,2]]
输出：3
解释：一种移除 3 块石头的方法如下所示：
1. 移除石头 [2,2] ，因为它和 [2,0] 同行。
2. 移除石头 [2,0] ，因为它和 [0,0] 同列。
3. 移除石头 [0,2] ，因为它和 [0,0] 同行。
石头 [0,0] 和 [1,1] 不能移除，因为它们没有与另一块石头同行/列。

示例 3：

输入：stones = [[0,0]]
输出：0
解释：[0,0] 是平面上唯一一块石头，所以不可以移除它。

class Solution {
    public int removeStones(int[][] stones) {
        UF uf = new UF();
        for(int[] stone : stones) {
            uf.merge(stone[0] + 10001, stone[1]);
        }

        return stones.length - uf.count;
    }
}

class UF {
    Map parent;
    int count;

    public UF() {
        this.parent = new HashMap<>();
        this.count = 0;
    }

    public int find(int x) {
        if(parent.get(x) == null) {
            count++;
            parent.put(x, x);
        }

        while(x != parent.get(x)) {
            parent.put(x, parent.get(x));
            x = parent.get(x);
        }

        return x;
    }

    public void merge(int x, int y) {
        int pX = find(x);
        int pY = find(y);

        if(pX == pY) {
            return;
        }

        parent.put(pX, pY);
        count--;
    }

}

765. 情侣牵手

N 对情侣坐在连续排列的 2N 个座位上，想要牵到对方的手。 计算最少交换座位的次数，以便每对情侣可以并肩坐在一起。 一次交换可选择任意两人，让他们站起来交换座位。

人和座位用 0 到 2N-1 的整数表示，情侣们按顺序编号，第一对是 (0, 1)，第二对是 (2, 3)，以此类推，最后一对是 (2N-2, 2N-1)。

这些情侣的初始座位  row[i] 是由最初始坐在第 i 个座位上的人决定的。

示例 1:

输入: row = [0, 2, 1, 3]
输出: 1
解释: 我们只需要交换row[1]和row[2]的位置即可。

示例 2:

输入: row = [3, 2, 0, 1]
输出: 0
解释: 无需交换座位，所有的情侣都已经可以手牵手了。

说明:

1. len(row) 是偶数且数值在 [4, 60]范围内。
2. 可以保证row 是序列 0...len(row)-1 的一个全排列。

class Solution {
    public int minSwapsCouples(int[] row) {
        int couples = row.length / 2;
        UF uf = new UF(couples);

        for(int i = 0; i < row.length; i = i + 2) {
            uf.connect(row[i]/2, row[i+1]/2);
        }

        return couples - uf.getCount();

    }
}

class UF {
    private int count;
    private int[] parent;
    private int[] size;

    public UF(int n) {
        this.count = n;
        this.parent = new int[n];
        this.size = new int[n];

        for(int i = 0; i < n; i++) {
            this.parent[i] = i;
            this.size[i] = 1;
        }
    }

    public void connect(int p, int q) {
        int rootP = find(p);
        int rootQ = find(q);

        if(rootP == rootQ) {
            return;
        }

        if(size[rootP] > size[rootQ]) {
            parent[rootQ] = rootP;
            size[rootP] += size[rootQ];
        } else {
            parent[rootP] = rootQ;
            size[rootQ] += size[rootP];
        }
        count--;
    }

    public boolean isConnected(int p, int q) {
        int rootP = find(p);
        int rootQ = find(q);

        if(rootP == rootQ) {
            return true;
        } else {
            return false;
        }
    }

    public int find(int x) {

        while(parent[x] != x) {
            parent[x] = parent[parent[x]];
            x = parent[x];
        }

        return x;
    }

    public int getCount() {
        return this.count;
    }
}

128. 最长连续序列

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

进阶：你可以设计并实现时间复杂度为 O(n) 的解决方案吗？

示例 1：

输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。

示例 2：

输入：nums = [0,3,7,2,5,8,4,6,0,1]
输出：9

class Solution {
    public int longestConsecutive(int[] nums) {
        if(nums.length <= 1) return nums.length; 
        HashMap numMap = new HashMap<>();
        UF uf = new UF(nums.length);

        for(int i = 0; i < nums.length; i++) {
            int num = nums[i];
            if(numMap.containsKey(num)) {
                continue;
            }
            numMap.put(num, i);
            if(numMap.containsKey(num - 1)) {
                uf.connect(i, numMap.get(num - 1));
            }
            if(numMap.containsKey(num + 1)) {
                uf.connect(i, numMap.get(num + 1));
            }
        } 

        int result = 1;
        for(int i = 0; i < nums.length; i++) {
            if(uf.find(i) == i && uf.size[i] > result) {
                result = uf.size[i];
            }
        }
        return result;
    }

}

class UF {
    int n;
    int[] parent;
    int[] size;

    public UF(int n) {
        this.n = n;
        parent = new int[n];
        size = new int[n];
        for(int i = 0; i < n; i++) {
            parent[i] = i;
            size[i] = 1;
        }
    }

    public void connect(int p, int q) {
        int rootP = find(p);
        int rootQ = find(q);

        if(rootP == rootQ) {
            return;
        }

        if(size[rootP] > size[rootQ]) {
            parent[rootQ] = rootP;
            size[rootP] += size[rootQ];
        } else {
            parent[rootP] = rootQ;
            size[rootQ] += size[rootP];
        }
    }

    public int find(int x) {
        while(parent[x] != x) {
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    }
}