0200. 岛屿数量
题目地址(200. 岛屿数量)
https://leetcode-cn.com/problems/number-of-islands/
题目描述
给你一个由 '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'前置知识
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)$
欢迎关注我的公众号《脑洞前端》获取更多更新鲜的 LeetCode 题解
相关题目
最后更新于
这有帮助吗？