LeetCode HOT 100 —— 200 .岛屿问题
创始人
2024-04-21 04:57:30
0

题目

给你一个由 ‘1’(陆地)和 ‘0’(水)组成的的二维网格,请你计算网格中岛屿的数量。

岛屿总是被水包围,并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外,你可以假设该网格的四条边均被水包围。
在这里插入图片描述
在这里插入图片描述

思路

岛屿类问题通用解法(DFS遍历框架):

岛屿问题是网格结构DFS的典型代表,可以先理解二叉树上的DFS遍历方法,然后类比写出网格结构的DFS遍历

二叉树DFS遍历:

void traverse(TreeNode root) {// 判断 base caseif (root == null) {return;}// 访问两个相邻结点:左子结点、右子结点traverse(root.left);traverse(root.right);
}

网格 DFS 遍历

void dfs(int[][] grid, int r, int c) {// 判断 base case// 如果坐标 (r, c) 超出了网格范围,直接返回if (!inArea(grid, r, c)) {return;}// 访问上、下、左、右四个相邻结点dfs(grid, r - 1, c);dfs(grid, r + 1, c);dfs(grid, r, c - 1);dfs(grid, r, c + 1);
}// 判断坐标 (r, c) 是否在网格中
boolean inArea(int[][] grid, int r, int c) {return 0 <= r && r < grid.length && 0 <= c && c < grid[0].length;
}

然后需要考虑避免重复遍历,因为网格结构的 DFS 与二叉树的 DFS 最大的不同之处在于,遍历中可能遇到遍历过的结点

这里对遍历过的格子赋值为2,格子一共三个取值

  • 0 —— 海洋格子
  • 1 —— 陆地格子(未遍历过)
  • 2 —— 陆地格子(已遍历过)

所以可以在模板中加入避免重复遍历的语句:

void dfs(int[][] grid, int r, int c) {// 判断 base caseif (!inArea(grid, r, c)) {return;}// 如果这个格子不是岛屿,直接返回if (grid[r][c] != 1) {return;}grid[r][c] = 2; // 将格子标记为「已遍历过」// 访问上、下、左、右四个相邻结点dfs(grid, r - 1, c);dfs(grid, r + 1, c);dfs(grid, r, c - 1);dfs(grid, r, c + 1);
}// 判断坐标 (r, c) 是否在网格中
boolean inArea(int[][] grid, int r, int c) {return 0 <= r && r < grid.length && 0 <= c && c < grid[0].length;
}

这就是岛屿问题、乃至各种网格问题的通用 DFS 遍历方法,然后在此基础上修改即可。

本题java代码如下:

class Solution{public int numIslands(char[][] grid){//定义一个表示岛屿数量的变量int count = 0;//两层for循环遍历整张二维表格中所有的陆地for(int i = 0; i < grid.length; i++){for(int j = 0; j < grid[0].length; j++){//取出所有的陆地,也就是值为1的格子if(grid[i][j] == '1'){//深度递归,遍历所有的陆地dfs(grid, i, j);//用来统计有多少岛屿,岛屿是由多个陆地组成的,概念不一样count++;}}}//返回岛屿的数量return count;}public void dfs(char[][] grid, int i, int j){//防止 i 和 j 越界,也就是防止超出岛屿(上下左右)的范围,遍历到海洋的时候也退出循环if(i < 0 || j < 0 || i >= grid.length || j >= grid[0].length || grid[i][j] == '0'){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);}
}

相关内容

热门资讯

鸿蒙怎样还原安卓系统,系统切换... 你有没有想过,鸿蒙系统竟然能还原安卓系统?这听起来是不是有点像魔法一样神奇?没错,今天就要带你一探究...
电脑安卓转苹果系统,系统迁移攻... 你有没有想过,有一天你的安卓手机突然变成了苹果的忠实粉丝,想要跳槽到iOS的阵营呢?这可不是什么天方...
安卓xp系统下载地址,轻松获取... 你有没有想过,手机系统也能穿越时空?没错,今天我要给你揭秘的就是这样一个神奇的存在——安卓XP系统。...
安卓系统怎么清理相册,安卓系统... 手机里的相册是不是越来越臃肿了?每次打开都感觉像是在翻山越岭,找一张照片都要费老鼻子劲。别急,今天就...
安卓系统安装ios转移,轻松实... 你有没有想过,手机系统之间的转换竟然也能如此神奇?没错,今天就要来聊聊安卓系统安装iOS转移这个话题...
安卓系统与ios系统的优势,系... 你有没有想过,为什么你的手机里装的是安卓系统而不是苹果的iOS系统呢?或者反过来,为什么你的朋友用的...
安卓系统游戏如何升级,轻松实现... 亲爱的安卓玩家们,你是否也和我一样,对安卓系统游戏升级这件事充满了好奇和期待呢?每次游戏更新,都仿佛...
安卓系统蛋仔派对,安卓系统下的... 你有没有发现,最近你的手机里多了一个超级好玩的游戏?没错,就是安卓系统上的“蛋仔派对”!这款游戏可是...
坚果3安卓原生系统,深度体验原... 你有没有听说过坚果3这款手机?它可是最近在数码圈里火得一塌糊涂呢!今天,我就要来给你详细介绍一下这款...
安卓子系统点不开,排查与解决指... 最近是不是你也遇到了安卓子系统点不开的烦恼?这可真是让人头疼啊!别急,今天就来给你详细解析一下这个问...
安卓系统经常误删文件,如何有效... 你有没有遇到过这种情况?手机里的文件突然不见了,找来找去,怎么也找不到。别急,这可能是安卓系统的小调...
安卓51系统如何破解,轻松解锁... 安卓51系统如何破解——探索未知的技术边界在数字化时代,手机已经成为我们生活中不可或缺的一部分。而安...
安卓系统怎么换回主题,安卓系统... 亲爱的手机控们,你是不是也和我一样,对安卓系统的主题换换换乐此不疲呢?不过,有时候换着换着,突然发现...
黑莓安卓系统 太垃圾,令人失望... 你有没有用过黑莓的安卓系统?别告诉我你没有,因为现在这个系统真的是太垃圾了!是的,你没听错,就是那个...
修改安卓系统权限代码,安卓系统... 你有没有想过,你的安卓手机里那些神秘的系统权限代码?它们就像隐藏在手机里的秘密通道,有时候让你觉得既...
虚拟大师安卓系统教程,教程详解... 你有没有想过,手机里的世界可以变得更加神奇?今天,就让我带你一起探索虚拟大师安卓系统的奥秘吧!想象你...
基于安卓系统个人博客,轻松构建... 你有没有想过,在这个信息爆炸的时代,拥有一片属于自己的网络小天地是多么酷的事情啊!想象每天都能在这里...
安卓怎么传到苹果系统,从安卓到... 你是不是也有过这样的烦恼:手机里存了好多好用的安卓应用,可是一换到苹果系统,就发现这些宝贝们都不见了...
安卓改系统字体app,安卓系统... 你有没有想过,手机上的字体也能变得个性十足?没错,就是那个安卓改系统字体app,它可是让手机界面焕然...
安卓系统重启密码错误,破解与预... 手机突然重启了,屏幕上竟然出现了密码输入的界面!这可怎么办?别急,让我来帮你一步步解决这个安卓系统重...