基础知识点
并查集（Union-find Data Structure）是一种树型的数据结构。它的特点是由子结点找到父亲结点，用于处理一些不交集（Disjoint Sets）的合并及查询问题。
Find：确定元素属于哪一个子集。它可以被用来确定两个元素是否属于同一子集。
Union：将两个子集合并成同一个集合。
剑指offer
剑指 Offer II 116. 省份数量【中等】
学习：leetcode/并查集/深度优先搜索/朋友圈问题/岛屿问题
题目链接：剑指 Offer II 116. 省份数量
题目内容：
有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。 省份 是一组直接或间接相连的城市，组内不含其他没有相连的城市。 给你一个 n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，而 isConnected[i][j] = 0 表示二者不直接相连。 返回矩阵中 省份 的数量。
思路：
1、并查集
复杂度分析：时间复杂度O(nm)；空间复杂度O(n)
class Solution { public int findCircleNum(int[][] isConnected) { UnionFind uf = new UnionFind(isConnected); int len1 = isConnected.length; int len2 = isConnected[0].length; for (int i = 0; i < len1; i++) { for (int j = 0; j < len2; j++) { if (isConnected[i][j] == 0) continue; uf.merge(i, j); } } return uf.size; } } class UnionFind { public int size; private int[] parent; private int[] weight; public UnionFind(int[][] isConnected) { int n = isConnected.length; this.size = n; this.parent = new int[n]; this.weight = new int[n]; for (int i = 0; i < n; i++) { this.parent[i] = i; this.weight[i] = 1; } } public int find(int x) { if (x == parent[x]) { return x; }else { parent[x] = find(parent[x]); return parent[x]; } } public void merge(int x, int y) { int _x = find(x); int _y = find(y); if (_x == _y) return; if (weight[_x] < weight[_y]) { int temp = _x; _x = _y; _y = temp; } parent[_y] = parent[_x]; weight[_x] += weight[_y]; --size; } }
leetcode
剑指 Offer II 105. 岛屿的最大面积【中等】
题目链接：剑指 Offer II 105. 岛屿的最大面积
题目内容；
思路：
1、dfs深搜
复杂度分析：时间复杂度O(mn)；空间复杂度O(mn)
class Solution { private int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; private int max = 0; public int maxAreaOfIsland(int[][] grid) { //遍历一遍，若是为1进行dfs，然后res+1 for (int i = 0; i < grid.length; i++) { for (int j = 0; j < grid[i].length; j++) { if (grid[i][j] == 1) { max = Math.max(dfs(grid, i, j, 1), max); } } } return max; } public int dfs(int[][] grid, int i, int j, int area) { //边界 if (i < 0 || i >= grid.length || j < 0 || j >= grid[i].length) { return 0; } //若是为1的进行标注并继续往下执行 if (grid[i][j] == 0) { return 0; } //地图位置进行标注 grid[i][j] = 0; //四个方向进行执行 int res = 1; for (int[] direction: directions) { res += dfs(grid, i + direction[0], j + direction[1], area + 1); } return res; } }
2、并查集
复杂度分析：时间复杂度O(mn)；空间复杂度O(mn)
class Solution { public int maxAreaOfIsland(int[][] grid) { if (grid == null || grid.length == 0 || grid[0].length == 0) { return 0; } //初始化并查集 UnionFind unionFind = new UnionFind(grid); int iLen = grid.length; int jLen = grid[0].length; //遍历一遍，若是为1进行dfs，然后res+1 for (int i = 0; i < iLen; i++) { for (int j = 0; j < jLen; j++) { if (grid[i][j] == 0) continue; //四个方向 if (i - 1 >= 0 && grid[i - 1][j] == 1) unionFind.merge(i * jLen + j, (i - 1) * jLen + j); if (i + 1 < iLen && grid[i + 1][j] == 1) unionFind.merge(i * jLen + j, (i + 1) * jLen + j); if (j - 1 >= 0 && grid[i][j - 1] == 1) unionFind.merge(i * jLen + j, i * jLen + j - 1); if (j + 1 < jLen && grid[i][j + 1] == 1) unionFind.merge(i * jLen + j, i * jLen + j + 1); } } int max = 0; for (int i = 0; i < iLen; i++) { for (int j = 0; j < jLen; j++) { max = Math.max(max, unionFind.weight[i * jLen + j]); } } return max; } } class UnionFind { public int size; public int[] parent; public int[] weight; public UnionFind(int[][] grid) { int len1 = grid.length; int len2 = grid[0].length; this.size = len1 * len2; this.parent = new int[size]; this.weight = new int[size]; //初始化 for (int i = 0; i < len1; i++) { for (int j = 0; j < len2; j++) { parent[i * len2 + j] = i * len2 + j; //根据岛屿是否为1来设置权重是否为1 if (grid[i][j] == 1) { weight[i * len2 + j] = 1; }else { weight[i * len2 + j] = 0; } } } } public int find(int x) { if (x == parent[x]) { return x; }else { parent[x] = find(parent[x]); return parent[x]; } } public void merge(int x, int y) { int _x = find(x); int _y = find(y); if (_x == _y) return; if (weight[_x] < weight[_y]) { int temp = _x; _x = _y; _y = temp; } //连通结点 parent[_y] = _x; weight[_x] += weight[_y]; --size; } }
