leetcode 并查集整理
并查集整理
- 990. 等式方程的可满足性
- 剑指 Offer II 116. 省份数量
- 200.岛屿数量
- 684. 冗余连接
- 1319. 连接网络的操作次数
- 299.除法求值
990. 等式方程的可满足性
题目,这是对并查集的简单应用,并查集的套路就是实现union和find函数。
固定模板, 路径压缩方式为隔代压缩,可以用在无带权并查集,前五道题都是使用隔代压缩的方法:
public void union(int[] parent, int index1, int index2) {
parent[find(parent, index1)] = find(parent, index2);
}
public int find(int[] parent, int index) {
while (parent[index] != index) {
parent[index] = parent[parent[index]];
index = parent[index];
}
return index;
}
有了并查集就很容易解决该题:
public boolean equationsPossible(String[] equations) {
int[] parent = new int[26];
for (int i = 0; i < 26; i++) {
parent[i] = i;
}
for (String str : equations) {
if (str.charAt(1) == '=') {
int index1 = str.charAt(0) - 'a';
int index2 = str.charAt(3) - 'a';
union(parent, index1, index2);
}
}
for (String str : equations) {
if (str.charAt(1) == '!') {
int index1 = str.charAt(0) - 'a';
int index2 = str.charAt(3) - 'a';
if (find(parent, index1) == find(parent, index2)) {
return false;
}
}
}
return true;
}
剑指 Offer II 116. 省份数量
题目,还是对并查集的应用,union之后查找city数组中值和下标一致的数目就是省份数量。
public int findCircleNum(int[][] isConnected) {
int n = isConnected.length;
int[] city = new int[n];
for (int i = 0; i < n; i++) {
city[i] = i;
}
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (isConnected[i][j] == 1) {
union(city, i, j);
}
}
}
int re = 0;
for (int i = 0; i < n; i++) {
if (city[i] == i) {
re++;
}
}
return re;
}
200.岛屿数量
题目,这道题使用dfs,每在循环最外边调用一次dfs就将count+1即可,并查集只是一个思路,实现起来也比较复杂,只做一个记录。
HashMap<Integer, int[]> map;
int[] island;
public int numIslands(char[][] grid) {
int n = grid.length;
int m = grid[0].length;
island = new int[n * m];
for (int i = 0; i < m * n; i++) {
island[i] = i;
}
map = new HashMap<>();
int count = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (grid[i][j] == '1') {
map.put(count, new int[]{i, j});
dfs(grid, i, j, count);
count++;
} else if (grid[i][j] == '0') {
island[getIndex(i, j, m)] = -1;
}
}
}
int re = 0;
for (int i = 0; i < m * n; i++) {
if (island[i] == i) {
re++;
}
}
return re;
}
public void dfs(char[][] grid, int r, int c, int count) {
if (!inArea(grid, r, c)) {
return;
}
// 如果这个格子不是岛屿,直接返回
if (grid[r][c] != '1') {
return;
}
grid[r][c] = '2'; // 将格子标记为「已遍历过」
int index1 = getIndex(r, c, grid[0].length);
int[] tmp = map.get(count);
int index2 = getIndex(tmp[0], tmp[1], grid[0].length);
union(island, index1, index2);
// 访问上、下、左、右四个相邻结点
dfs(grid, r - 1, c, count);
dfs(grid, r + 1, c, count);
dfs(grid, r, c - 1, count);
dfs(grid, r, c + 1, count);
}
boolean inArea(char[][] grid, int r, int c) {
return 0 <= r && r < grid.length
&& 0 <= c && c < grid[0].length;
}
int getIndex(int i, int j, int m) {
return i * m + j;
}
684. 冗余连接
题目,如果新加入的点,他们的parent一致,说明已经连接,就是要找到的最后出现的边。
public int[] findRedundantConnection(int[][] edges) {
int n = edges.length;
int[] parent = new int[n + 1];
for (int i = 0; i < n + 1; i++) {
parent[i] = i;
}
for (int[] edge : edges) {
if (find(parent, edge[0]) != find(parent, edge[1])) {
union(parent, edge[0], edge[1]);
} else {
return edge;
}
}
return null;
}
1319. 连接网络的操作次数
题目,这道题实际上是上一道题的改进,首先用并查集计算出网络中冗余连接数,然后再遍历parent数组,查找有多少个不相连的网络n,如果n-1 < count则说明能连接,返回n-1,否则返回-1。
public int makeConnected(int n, int[][] connections) {
int[] parent = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
}
int count = 0;
for (int[] edge : connections) {
if (find(parent, edge[0]) != find(parent, edge[1])) {
union(parent, edge[0], edge[1]);
} else {
count++;
}
}
int re = -1;
for (int i = 0; i < n; i++) {
if (parent[i] == i) {
if (count-- < 0) return -1;
re++;
}
}
return re;
}
299.除法求值
题目这道题是带权重的并查集,并查集中需要维护节点的权重,使用递归的方式进行路径压缩,使每一个节点都直接指向父节点,并在路径压缩中更新权值。
public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
int equationsSize = equations.size();
UnionFind unionFind = new UnionFind(2 * equationsSize);
// 第 1 步:预处理,将变量的值与 id 进行映射,使得并查集的底层使用数组实现,方便编码
Map<String, Integer> hashMap = new HashMap<>(2 * equationsSize);
int id = 0;
for (int i = 0; i < equationsSize; i++) {
List<String> equation = equations.get(i);
String var1 = equation.get(0);
String var2 = equation.get(1);
if (!hashMap.containsKey(var1)) {
hashMap.put(var1, id);
id++;
}
if (!hashMap.containsKey(var2)) {
hashMap.put(var2, id);
id++;
}
unionFind.union(hashMap.get(var1), hashMap.get(var2), values[i]);
}
// 第 2 步:做查询
int queriesSize = queries.size();
double[] res = new double[queriesSize];
for (int i = 0; i < queriesSize; i++) {
String var1 = queries.get(i).get(0);
String var2 = queries.get(i).get(1);
Integer id1 = hashMap.get(var1);
Integer id2 = hashMap.get(var2);
if (id1 == null || id2 == null) {
res[i] = -1.0d;
} else {
res[i] = unionFind.isConnected(id1, id2);
}
}
return res;
}
private class UnionFind {
private int[] parent;
/**
* 指向的父结点的权值
*/
private double[] weight;
public UnionFind(int n) {
this.parent = new int[n];
this.weight = new double[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
weight[i] = 1.0d;
}
}
public void union(int x, int y, double value) {
int rootX = find(x);
int rootY = find(y);
if (rootX == rootY) {
return;
}
parent[rootX] = rootY;
// 关系式的推导请见「参考代码」下方的示意图
weight[rootX] = weight[y] * value / weight[x];
}
/**
* 路径压缩
*
* @param x
* @return 根结点的 id
*/
public int find(int x) {
if (x != parent[x]) {
int origin = parent[x];
parent[x] = find(parent[x]);
weight[x] *= weight[origin];
}
return parent[x];
}
public double isConnected(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX == rootY) {
return weight[x] / weight[y];
} else {
return -1.0d;
}
}
}