专门做酒店网站,网址没封的来一个,新东方考研班收费价格表,深圳有什么互联网公司200. 岛屿问题 难度#xff1a;中等 力扣地址#xff1a;https://leetcode.cn/studyplan/top-100-liked/ 问题描述
给你一个由 1#xff08;陆地#xff09;和 0#xff08;水#xff09;组成的的二维网格#xff0c;请你计算网格中岛屿的数量。
岛屿总是被水包围中等 力扣地址https://leetcode.cn/studyplan/top-100-liked/ 问题描述
给你一个由 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 写起来比较简单也比较容易理解所以真心推荐合适场景下考虑 DFS。
如下图所示白色筷子表示 “水”也就是遍历时的边界。 所以接下的问题就非常简单我们从 (0, 0) 这个坐标出发如果是陆地就 travel也就是 DFS 遍历如果是水就修改方向如果没有地方去了就切换到下一个陆地。
为了更好理解我们可以考虑把经过的陆地全部都换成水避免下次还来这个地方
解题代码
对应的 C 代码如下
class Solution {
public:void travel(vectorvectorchar grid, int x, int y) {// 遇到边界或没有可访问的点if (x grid.size() || x 0 || y grid[0].size() || y 0 || grid[x][y] 0) {return;}// 标记一下已经访问grid[x][y] 0;// 四个方向 traveltravel(grid, x 1, y);travel(grid, x - 1, y);travel(grid, x, y 1);travel(grid, x, y - 1);}int numIslands(vectorvectorchar grid) {// 记录结果int result 0;// 根据 (i, j) 开始尝试 travelfor (int i 0; i grid.size(); i) {for (int j 0; j grid[0].size(); j) {// 如果遇到的这个点是陆地if (grid[i][j] 1) {// 开始traveltravel(grid, i, j);// travel 结束后 1表示那一片陆地已经访问过了result 1;}}}return result;}
};时间复杂度O(MN)空间复杂度O(MN 对应的 java 代码如下
class Solution {// 定义 travel 方法public void travel(char[][] grid, int x, int y) {// 遇到边界或没有可访问的点if (x grid.length || x 0 || y grid[0].length || y 0 || grid[x][y] 0) {return;}// 标记已经访问过的点grid[x][y] 0;// 四个方向进行递归调用travel(grid, x 1, y);travel(grid, x - 1, y);travel(grid, x, y 1);travel(grid, x, y - 1);}// 定义 numIslands 方法public int numIslands(char[][] grid) {// 记录结果int result 0;// 遍历整个网格for (int i 0; i grid.length; i) {for (int j 0; j grid[0].length; j) {// 如果遇到陆地if (grid[i][j] 1) {// 开始进行递归访问travel(grid, i, j);// 访问结束后计数加一result;}}}// 返回结果return result;}
}
对应的python代码为
class Solution:def travel(self, grid, x, y):# 遇到边界或没有可访问的点if x len(grid) or x 0 or y len(grid[0]) or y 0 or grid[x][y] 0:return# 标记已经访问过的点grid[x][y] 0# 四个方向进行递归调用self.travel(grid, x 1, y)self.travel(grid, x - 1, y)self.travel(grid, x, y 1)self.travel(grid, x, y - 1)def numIslands(self, grid):# 记录结果result 0# 遍历整个网格for i in range(len(grid)):for j in range(len(grid[0])):# 如果遇到陆地if grid[i][j] 1:# 开始进行递归访问self.travel(grid, i, j)# 访问结束后计数加一result 1# 返回结果return result总结
作为 DFS 的一个比较简单的例子限制条件也比较少只需要考虑边界问题即可。先应该学习一下 DFS 的基本逻辑然后能够写 DFS 的代码在此基础上稍微改改就可以刷这道题。
我更加想称这个操作为防水游戏就是把每块岛屿都用海水淹没看看需要操作多少次。
多谢小伙伴们的点赞支持 ~ Smileyan 2024.06.30 23:52
