序言
虽然算法很难，但不应该就放弃。这是一个学习笔记，希望你们喜欢~
先自己尝试写，大概十几分钟仍然写不出来
看思路，再尝试跟着思路写
仍然写不出来，再看视频
b站up视频推荐：爱学习的饲养员
leetcode其他文章：
数组篇：
链表篇：
从小白开始刷算法 ListNode 链表篇 leetcode.203
从小白开始刷算法 ListNode 链表篇 leetcode.206
队列篇
从小白开始刷算法 ListNode 链表篇 leetcode.933
栈篇
从小白开始刷算法 Stack 栈篇 leetcode.496
哈希篇
从小白开始刷算法 Hash 哈希篇 leetcode.217
从小白开始刷算法 Hash 哈希篇 leetcode.705
树篇
从小白开始刷算法 Tree 树篇 先序遍历 leetcode.144
从小白开始刷算法 Tree 树篇 中序遍历 leetcode.94
从小白开始刷算法 Tree 树篇 后序遍历 leetcode.94
堆篇
从小白开始刷算法 Heap 堆篇 最大堆排序 leetcode.215
小白开始刷算法 Heap 堆篇 最小堆排序 leetcode.692
双指针篇
二分法篇
滑动窗口篇
递归篇
分治法篇
回溯法篇
dfs篇
bfs篇
并查集篇
难度：中等
题目：
200. 岛屿数量
给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。
示例 1：
输入：grid = [
[“1”,“1”,“1”,“1”,“0”],
[“1”,“1”,“0”,“1”,“0”],
[“1”,“1”,“0”,“0”,“0”],
[“0”,“0”,“0”,“0”,“0”]
]
输出：1
示例 2：
输入：grid = [
[“1”,“1”,“0”,“0”,“0”],
[“1”,“1”,“0”,“0”,“0”],
[“0”,“0”,“1”,“0”,“0”],
[“0”,“0”,“0”,“1”,“1”]
]
输出：3
题目来源：力扣（LeetCode）
并查集介绍：
- 并查集（Disjoint Set Union，简称并查集）是一种用于处理集合合并和查询连通性的数据结构。它提供了两个主要操作：合并（union）和查找（find）。并查集主要用于解决一些关于集合的合并和查询问题，比如判断无向图中的连通分量、求解最小生成树、判断图中是否存在环等。并查集的核心思想是维护一个由多个集合构成的集合族，每个集合代表一个独立的连通分量。初始时，每个元素自成一个集合，然后通过不断的合并操作，将具有连通关系的元素合并到同一个集合中。通过查找操作，可以确定两个元素是否属于同一个集合。并查集的实现通常使用一个数组来表示集合，其中每个元素的值表示其所属集合的根节点。通过将不同集合的根节点连接在一起，形成一个森林结构，从而快速合并集合和查找元素所属的集合。并查集的常用操作：
- 初始化：创建一个并查集，每个元素自成一个集合。
- 查找：查找元素所属的集合，即找到其根节点。
- 合并：将两个集合合并成一个集合，即将两个根节点连接起来。
- 并查集的时间复杂度：
- 初始化：O(n)
- 查找：O(log n)（路径压缩优化后，接近常数时间）
- 合并：O(log n)（按秩合并优化后，接近常数时间）
- 并查集是一种简单而高效的数据结构，适用于解决一些集合合并和查询连通性的问题。它在图论、网络连接、最小生成树等领域都有广泛的应用。
并查集思路
能否写出：不能写出。
时间：1个小时起步 第一次写
思路：
- 首先判断输入的二维字符数组
grid是否为空或长度为0，如果是，则返回0，表示没有岛屿。 - 获取二维字符数组的行数和列数，分别赋值给变量
row和col。 - 创建一个
UnionFind对象uf，并将二维字符数组grid传入构造函数中进行初始化。 - 遍历二维字符数组
grid，对每个元素进行如下操作：
- 如果当前元素为水域（‘0’），则计数器
waters加1，表示遇到了一个水域。 - 如果当前元素为岛屿（‘1’），则根据上、下、左、右四个方向，判断相邻位置是否也是岛屿，如果是，则将它们通过并查集的
union操作合并到同一个集合中。
- 返回并查集
uf的岛屿数量uf.getCount()减去计数器waters，即为实际岛屿的数量。
并查集的实现部分包含以下内容：
UnionFind类有两个成员变量：root数组和count计数器。- 在构造函数中，根据二维字符数组
grid的行数和列数，初始化root数组，并将每个位置的索引作为初始的根节点。 find方法用于查找指定位置元素的根节点，并通过路径压缩将其直接连接到根节点，以加快后续查找操作的速度。union方法用于将两个元素合并到同一个集合中。首先找到两个元素的根节点，如果它们不相等，则将其中一个根节点指向另一个根节点，并将计数器count减1，表示合并了一个集合。getCount方法用于获取当前并查集中的集合数量。
通过并查集的操作，将相邻的岛屿合并到同一个集合中，最后返回集合数量减去水域数量，即为实际岛屿的数量。
// 仅是我的思路代码，leetcode上大神更厉害 class Solution { public int numIslands(char[][] grid) { if (grid == null || grid.length == 0) { return 0; } int row = grid.length; int col = grid[0].length; int waters = 0; UnionFind uf = new UnionFind(row * col); for (int i = 0; i < row; i++) { for (int j = 0; j < col; j++) { if (grid[i][j] == '0') { waters++; } else { //上下左右的位置坐标 int[][] directions = new int[][]{{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; for (int[] dir : directions) { //通过当前ij位置坐标 计算 四周位置坐标 int x = i + dir[0]; int y = j + dir[1]; //判断边界问题 //xy必须是正数 //xy必须不超过行列 //坐标是岛屿 if (x >= 0 && y >= 0 && x < row && y < col && grid[x][y] == '1') { //上下左右四方 相邻 的位置 x y, 当前位置 i j uf.union(x * col + y, i * col + j); } } } } } //count是土地和水的合并，减去水就剩陆地的个数 return uf.getCount() - waters; } } class UnionFind { private int[] parent; private int count; public UnionFind(int size) { count = size; parent = new int[size]; for (int i = 0; i < size; i++) { parent[i] = i; } } // Find the root of X public int find(int x) { if (x == parent[x]) { return x; } //将当前节点的父节点直接设为根节点 return parent[x] = find(parent[x]); } /** * Union two element into one root * * @param x 要被更改的祖先 * @param y 祖先 */ public void union(int x, int y) { int parentX = find(x); int parentY = find(y); if (parentX != parentY) { parent[parentX] = parentY; //两块土地合成一块 count--; } } public int getCount() { return count; } }
时间复杂度：O(MNα(MN))
- M 和 N 分别是二维字符数组
grid的行数和列数，α 是 Ackermann 函数的反函数，它可以看作是一个很小的常数。
空间复杂度：O(MN)
