大家好,我是吴师兄。今天来学一下拼多多社招一面的算法题。
先看题目描述。
给你一个由 '1'
(陆地)和 '0'
(水)组成的的二维网格,请你计算网格中岛屿的数量。
岛屿总是被水包围,并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外,你可以假设该网格的四条边均被水包围。
示例 1:
代码语言:javascript复制输入:grid = [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
]
输出:1
示例 2:
代码语言:javascript复制输入:grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
输出:3
提示:
m == grid.length
n == grid[i].length
1 <= m, n <= 300
grid[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,连通性
- 解题技巧: 遍历每块陆地,计算各个岛屿的大小,然后尝试将小岛连接起来以形成更大的岛屿。
今天我们用并查集来解决。
代码语言:javascript复制// 岛屿数量(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;
}
}
我总结并录制了 100 道 LeetCode 高频算法题,涵盖了数组、链表、栈、队列、二叉树、回溯算法、动态规划等众多高频知识点,所选的题目也是非常有特征的题目,一题抵十题。