美团春招实习笔试，懵逼了！
大家好，我是吴师兄。
美团在前几天也开启了春招实习招聘模式，这一轮的笔试难度比较大，总共有五题，前三题属于“送分题”，最后一题属于名副其实的难题，毕竟涉及到一个相对复杂的数据结构--并查集，我看了关于这次笔试的一些讨论，很多人都对这题有些懵逼，所以今天我们来讲一道并查集相关的算法题。
先看题目描述。
给你一个由 '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
提示：
m == grid.lengthn == grid[i].length1 <= m, n <= 300grid[i][j]的值为'0'或'1'
LeetCode 上有一些与岛屿相关的题目，这些题目通常涉及图的遍历、深度优先搜索（DFS）、广度优先搜索（BFS）等算法，这些题目的解法大同小异，甚至在代码层面都相差无几，所以只要彻底掌握一道，其它的岛屿题目都能顺利拿下。
下面这些题目，能弄懂一道就够了。
- 题目：200. Number of Islands
- 考察重点： 图的遍历，DFS/BFS
- 解题技巧： 使用 DFS 或 BFS 遍历岛屿，将访问过的地块标记，以避免重复计算。
- 题目：695. Max Area of Island
- 考察重点： 图的遍历，DFS/BFS
- 解题技巧： 类似于寻找岛屿数量，但是需要记录并更新每个岛屿的面积。
- 题目：463. Island Perimeter
- 考察重点： 图的遍历
- 解题技巧： 遍历每块陆地，计算其边界与水域相邻的边的数量。
- 题目：694. Number of Distinct Islands
- 考察重点： 图的遍历，DFS/BFS，哈希
- 解题技巧： 使用 DFS/BFS 遍历每个岛屿，并用哈希集合来记录不同的岛屿形状。
- 题目：1020. Number of Enclaves
- 考察重点： 图的遍历，DFS/BFS
- 解题技巧： 先从边界开始遍历，标记所有能够到达边界的陆地，然后计算剩余陆地块数。
- 题目：305. Number of Islands II
- 考察重点： 并查集，动态图的更新
- 解题技巧： 在陆地不断增加的情况下，使用并查集来动态维护岛屿数量。
- 题目：827. Making A Large Island
- 考察重点： 图的遍历，DFS/BFS，连通性
- 解题技巧： 遍历每块陆地，计算各个岛屿的大小，然后尝试将小岛连接起来以形成更大的岛屿。
今天我们用并查集来解决。
- 初始化阶段：
- 首先，获取网格的行数
rows和列数cols。 - 初始化一个并查集
unionFind，大小为rows * cols，因为每个单元格都可以视为一个独立的“岛屿”（在后续操作中会进行合并）。
- 首先，获取网格的行数
- 遍历网格：
- 遍历每个网格单元格。
- 如果遇到水（
'0'），则增加一个计数器spaces来记录水格的数量。 - 如果遇到陆地（
'1'），则尝试将其与右侧和下侧的陆地单元格合并（如果存在）。
- 并查集操作：
- 寻找（Find）：确定某个单元格的“根”或者说是代表元素。根元素代表了与当前单元格相连的所有单元格的最终归属。
- 合并（Union）：如果两个单元格都是陆地，我们会将它们合并为一个岛屿。实际上，这意味着让其中一个单元格的根元素指向另一个单元格的根元素。
- 处理边界和方向：
- 只考虑每个单元格的右方和下方单元格进行合并操作，这样可以避免重复计算，并保证所有可能的连接都被考虑到。
- 计算岛屿数量：
- 最后，
unionFind.getCount()会返回并查集中独立集合的数量，即岛屿数量。但我们还需要从这个数中减去水格的数量，因为在初始化并查集时，水格也被当作了独立的岛屿。
- 最后，
核心代码解析
getIndex(int i, int j)方法用于将二维坐标转换为一维，以方便在并查集中管理。unionFind对象是解题的关键，它通过合并操作减少岛屿数量的计数，直到所有可能合并的陆地都被处理完毕。- 在每次遍历时，只有当当前单元格为
'1'（陆地）时，我们才考虑其与右侧和下侧单元格的合并。
小贴士
- 并查集是一种非常高效处理集合合并和查询问题的数据结构，尤其适合解决像这样的连通性问题。
- 理解并查集的两个基本操作——
find和union——是理解这类问题的关键。
// 岛屿数量（LeetCode 200）（并查集解法）：https://leetcode.cn/problems/number-of-islands/
class Solution {
private int rows;
private int cols;
public int numIslands(char[][] grid) {
rows = grid.length;
cols = grid[0].length;
// 水格的数量
int spaces = 0;
UnionFind unionFind = new UnionFind(rows * cols);
// 沿着每个网格的右方、下方去查找
int[][] directions = {{1, 0}, {0, 1}};
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
// 当前网格是水
if (grid[i][j] == '0') {
// 水格的数量增加
spaces++;
// 当前网格是陆地
} else {
// 沿着这个陆地的右方、下方这两个方向去查找
for (int[] direction : directions) {
// 新网格的 x 坐标
int newX = i + direction[0];
// 新网格的 y 坐标
int newY = j + direction[1];
// 如果新网格的坐标位于矩阵内
// 并且是陆地
if (newX < rows && newY < cols && grid[newX][newY] == '1') {
// 那么就把这两个网格连接起来
unionFind.union(getIndex(i, j), getIndex(newX, newY));
}
}
}
}
}
return unionFind.getCount() - spaces;
}
// 把这些二维网格进行编号
// 比如第 0 行第 0 列网格的编号是 0
// 比如第 0 行第 1 列网格的编号是 1
// 比如第 1 行第 1 列网格的编号是 5（一列有 5 个元素）
private int getIndex(int i, int j) {
return i * cols + j;
}
}
// 并查集
class UnionFind {
int[] roots;
int count;
public UnionFind(int n) {
// 使用一维数组用来记录每个网格的出发位置
roots = new int[n];
for (int i = 0; i < n ; i++) {
// 默认每个网格的出发位置是自己本身
roots[i] = i;
}
// 所以一开始有 n 个岛屿
count = n ;
}
// 寻找当前网格的出发位置
public int find(int i){
if( i == roots[i]) return i ;
roots[i] = find(roots[i]);
return roots[i];
}
// 连通操作，把陆地连接起来
public void union(int p, int q) {
// 寻找陆地 p 的出发位置
int pRoot = find(p);
// 寻找陆地 q 的出发位置
int qRoot = find(q);
// 如果两者的出发位置不同
// 那么需要采取操作把 p 和 q 所在的两堆网格合到一起
if (pRoot != qRoot) {
// 也就是把其中一个的最上面的出发位置挂过来就行
roots[pRoot] = qRoot;
// 与此同时，两堆陆地变成了一堆陆地
count--;
}
}
// 获取当前区间的所有连通量
public int getCount() {
// 也就是有多少陆地网格 + 水网格
return count;
}
}本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2024-03-12，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录