并查集框架结构：
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; } }
给你一个字符串 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 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<Integer, Integer> 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--; } }
? 所谓一个朋友圈子，不一定其中的人都互相直接认识。
? 例如：小张的朋友是小李，小李的朋友是小王，那么他们三个人属于一个朋友圈。
? 现在给出一些人的朋友关系，人按照从 到 编号在这中间会进行询问某两个人是否属于一个朋友圈，请你编写程序，实现这个过程。
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(); } }
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<Integer, Integer> 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--; } }
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 解释: 无需交换座位，所有的情侣都已经可以手牵手了。
说明:
len(row) 是偶数且数值在 [4, 60]范围内。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; } }
原文：https://www.cnblogs.com/billyqiu/p/14750833.html