题目描述
给你一个由 '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.length
n == grid[i].length
1 <= m, n <= 300
grid[i][j] 的值为 '0' 或 '1'
难度:Middle
前置知识
- DFS
公司
- 阿里
- 腾讯
- 百度
- 字节
思路
如图,我们其实就是要求红色区域的个数,换句话说就是求连续区域的个数。
符合直觉的做法是用DFS来解:
- 我们需要建立一个 visited 数组用来记录某个位置是否被访问过。
- 对于一个为
1
且未被访问过的位置,我们递归进入其上下左右位置上为1
的数,将其 visited 变成 true。 - 重复上述过程
- 找完相邻区域后,我们将结果 res 自增1,然后我们在继续找下一个为
1
且未被访问过的位置,直至遍历完.
但是这道题目只是让我们求连通区域的个数,因此我们其实不需要额外的空间去存储visited信息。
注意到上面的过程,我们对于数字为0的其实不会进行操作的,也就是对我们“没用”。 因此对于已经访问的元素,
我们可以将其置为0即可。
关键点解析
- 二维数组DFS解题模板
- 将已经访问的元素置为0,省去visited的空间开销
代码
- 语言支持:C++, Java, JS, python3
C++ Code:
class Solution {
public:
int numIslands(vector<vector<char>>& grid) {
int res = 0;
for(int i=0;i<grid.size();i++)
{
for(int j=0;j<grid[0].size();j++)
{
if(grid[i][j] == '1')
{
dfs(grid, i, j);
res += 1;
}
}
}
return res;
}
void dfs(vector<vector<char>>& grid, int i, int j)
{
// edge
if(i<0 || i>= grid.size() || j<0 || j>= grid[0].size() || grid[i][j] != '1')
{
return;
}
grid[i][j] = '0';
dfs(grid, i+1, j);
dfs(grid, i-1, j);
dfs(grid, i, j+1);
dfs(grid, i, j-1);
}
};
Java Code:
public int numIslands(char[][] grid) {
if (grid == null || grid.length == 0 || grid[0].length == 0) return 0;
int count = 0;
for (int row = 0; row < grid.length; row++) {
for (int col = 0; col < grid[0].length; col++) {
if (grid[row][col] == '1') {
dfs(grid, row, col);
count++;
}
}
}
return count;
}
private void dfs(char[][] grid,int row,int col) {
if (row<0||row== grid.length||col<0||col==grid[0].length||grid[row][col]!='1') {
return;
}
grid[row][col] = '0';
dfs(grid, row-1, col);
dfs(grid, row+1, col);
dfs(grid, row, col+1);
dfs(grid, row, col-1);
}
Javascript Code:
/*
* @lc app=leetcode id=200 lang=javascript
*
* [200] Number of Islands
*/
function helper(grid, i, j, rows, cols) {
if (i < 0 || j < 0 || i > rows - 1 || j > cols - 1 || grid[i][j] === "0")
return;
grid[i][j] = "0";
helper(grid, i + 1, j, rows, cols);
helper(grid, i, j + 1, rows, cols);
helper(grid, i - 1, j, rows, cols);
helper(grid, i, j - 1, rows, cols);
}
/**
* @param {character[][]} grid
* @return {number}
*/
var numIslands = function(grid) {
let res = 0;
const rows = grid.length;
if (rows === 0) return 0;
const cols = grid[0].length;
for (let i = 0; i < rows; i++) {
for (let j = 0; j < cols; j++) {
if (grid[i][j] === "1") {
helper(grid, i, j, rows, cols);
res++;
}
}
}
return res;
};
python code:
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
if not grid: return 0
count = 0
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j] == '1':
self.dfs(grid, i, j)
count += 1
return count
def dfs(self, grid, i, j):
if i < 0 or j < 0 or i >= len(grid) or j >= len(grid[0]) or grid[i][j] != '1':
return
grid[i][j] = '0'
self.dfs(grid, i + 1, j)
self.dfs(grid, i - 1, j)
self.dfs(grid, i, j + 1)
self.dfs(grid, i, j - 1)
复杂度分析
– 时间复杂度:$O(m * n)$
– 空间复杂度:$O(m * n)$
相关题目
- 695. 岛屿的最大面积
- 原题leetcode链接:https://leetcode-cn.com/problems/number-of-islands/
- 更多力扣 解题: 力扣 – 全球极客挚爱的技术成长平台 ,也可以访问我的 JS中文网 – 码农周刊 仓库:https://github.com/meibin08/free-programming-books,标星关注一起学习更多前端前沿知识。
看完两件小事
如果你觉得这篇文章对你挺有启发,我想请你帮我两个小忙:
- 把这篇文章分享给你的朋友 / 交流群,让更多的人看到,一起进步,一起成长!
- 关注公众号 「画漫画的程序员」,公众号后台回复「资源」 免费领取我精心整理的前端进阶资源教程
本文著作权归作者所有,如若转载,请注明出处
转载请注明:文章转载自「 Js中文网 · 前端进阶资源教程 」https://www.javascriptc.com