445,BFS和DFS两种方式解岛屿数量
However dark and scary the world might be right now, there will be light.
无论世界现在有多黑暗,多可怕,终有一天会重现光明。
问题描述
给你一个由 '1'(陆地)和 '0'(水)组成的的二维网格,请你计算网格中岛屿的数量。
岛屿总是被水包围,并且每座岛屿只能由水平方向或竖直方向上相邻的陆地连接形成。
此外,你可以假设该网格的四条边均被水包围。
示例 1:
输入:
[
['1','1','1','1','0'],
['1','1','0','1','0'],
['1','1','0','0','0'],
['0','0','0','0','0']
]
输出: 1
示例 2:
输入:
[
['1','1','0','0','0'],
['1','1','0','0','0'],
['0','0','1','0','0'],
['0','0','0','1','1']
]
输出: 3
解释: 每座岛屿只能由水平和/或竖直方向上相邻的陆地连接而成。
DFS解决
这题让求的是岛屿的面积,二维数组中值是1的都是岛屿,如果多个1是连着的,那么他们只能算一个岛屿。
最简单的一种方式就是遍历数组中的每一个值,如果是1就说明是岛屿,然后把它置为0或者其他的字符都可以,只要不是1就行,然后再遍历他的上下左右4个位置。如果是1,说明这两个岛屿是连着的,只能算是一个岛屿,我们还要把它置为0,然后再以它为中心遍历他的上下左右4个位置……。如果是0,就说明不是岛屿,就不在往他的上下左右4个位置遍历了。这里就以示例1为例来看一下
每个位置只要是1,先要把它置为0,然后沿着他的上下左右4个方向继续遍历,执行同样的操作,要注意边界条件的判断。代码比较简单,来看下
1public int numIslands(char[][] grid) { 2 //边界条件判断 3 if (grid == null || grid.length == 0) 4 return 0; 5 //统计岛屿的个数 6 int count = 0; 7 //两个for循环遍历每一个格子 8 for (int i = 0; i < grid.length; i++) 9 for (int j = 0; j < grid[0].length; j++) { 10 //只有当前格子是1才开始计算 11 if (grid[i][j] == '1') { 12 //如果当前格子是1,岛屿的数量加1 13 count++; 14 //然后通过dfs把当前格子的上下左右4 15 //个位置为1的都要置为0,因为他们是连着 16 //一起的算一个岛屿, 17 dfs(grid, i, j); 18 } 19 } 20 //最后返回岛屿的数量 21 return count; 22} 23 24//这个方法会把当前格子以及他邻近的为1的格子都会置为1 25public void dfs(char[][] grid, int i, int j) { 26 //边界条件判断,不能越界 27 if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] == '0') 28 return; 29 //把当前格子置为0,然后再从他的上下左右4个方向继续遍历 30 grid[i][j] = '0'; 31 dfs(grid, i - 1, j);//上 32 dfs(grid, i + 1, j);//下 33 dfs(grid, i, j + 1);//左 34 dfs(grid, i, j - 1);//右 35}
BFS解决
DFS就是沿着一条路径一直走下去,当遇到终止条件的时候才会返回,而BFS就是先把当前位置附近的访问一遍,就像下面这样先访问圈内的,然后再把圈放大继续访问,就像下面这样
这题使用BFS和DFS都能解决,如果遇到位置为1的格子,只要能把他们挨着的为1的全部置为0,然后挨着的挨着的为1的位置也置为0,然后……一直这样循环下去,看下代码
1public int numIslands(char[][] grid) { 2 //边界条件判断 3 if (grid == null || grid.length == 0) 4 return 0; 5 //统计岛屿的个数 6 int count = 0; 7 //两个for循环遍历每一个格子 8 for (int i = 0; i < grid.length; i++) 9 for (int j = 0; j < grid[0].length; j++) { 10 //只有当前格子是1才开始计算 11 if (grid[i][j] == '1') { 12 //如果当前格子是1,岛屿的数量加1 13 count++; 14 //然后通过bfs把当前格子的上下左右4 15 //个位置为1的都要置为0,因为他们是连着 16 //一起的算一个岛屿, 17 bfs(grid, i, j); 18 } 19 } 20 return count; 21} 22 23private void bfs(char[][] grid, int x, int y) { 24 //把当前格子先置为0 25 grid[x][y] = '0'; 26 int n = grid.length; 27 int m = grid[0].length; 28 //使用队列,存储的是格子坐标转化的值 29 Queue<Integer> queue = new LinkedList<>(); 30 //我们知道平面坐标是两位数字,但队列中存储的是一位数字, 31 //所以这里是把两位数字转化为一位数字 32 int code = x * m + y; 33 //坐标转化的值存放到队列中 34 queue.add(code); 35 while (!queue.isEmpty()) { 36 //出队 37 code = queue.poll(); 38 //在反转成坐标值(i,j) 39 int i = code / m; 40 int j = code % m; 41 if (i > 0 && grid[i - 1][j] == '1') {//上 42 //如果上边格子为1,把它置为0,然后加入到队列中 43 //下面同理 44 grid[i - 1][j] = '0'; 45 queue.add((i - 1) * m + j); 46 } 47 if (i < n - 1 && grid[i + 1][j] == '1') {//下 48 grid[i + 1][j] = '0'; 49 queue.add((i + 1) * m + j); 50 } 51 if (j > 0 && grid[i][j - 1] == '1') { //左 52 grid[i][j - 1] = '0'; 53 queue.add(i * m + j - 1); 54 } 55 if (j < m - 1 && grid[i][j + 1] == '1') {//右 56 grid[i][j + 1] = '0'; 57 queue.add(i * m + j + 1); 58 } 59 } 60}
总结
这题首先要搞懂岛屿是由什么组成的,如果都是1并且挨着的话那么他们只能算一个岛屿,所以当我们找到一个岛屿的时候,首先要把他变为0,然后再把它上下左右4个方向为1的也要变成0,因为他们挨着的算是一个岛屿,接着继续再把挨着的挨着的以同样的方式遍历……。
●422,剑指 Offer-使用DFS和BFS解机器人的运动范围
长按上图,识别图中二维码之后即可关注。
本文分享自微信公众号 - 数据结构和算法(sjjghsf)。
如有侵权,请联系 support@oschina.cn 删除。
本文参与“OSC源创计划”,欢迎正在阅读的你也加入,一起分享。
低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。
持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。
转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。
- 上一篇
【微服务】143:商品分类业务的实现
今天是刘小爱自学Java的第143天。 感谢你的观看,谢谢你。 学习计划安排如下: 商品分类业务的初步实现。 数据模型的分析:数据表字段的设计,Java中对应的实体类,前端页面vue组件。 业务模型的分析:请求路径是什么?根据什么去数据库查询?具体实现代码的编写。 其中还有一个跨域问题未来得及解决,怎么感觉积累的问题越来越多了,这样下去可不行啊。 一、商品分类业务 我们的项目是刘小爱商城,其核心自然是商品了,所以就要涉及到一个商品分类业务。 1需求分析 我们先看看国内的主流网站上是如何做的? 比如说家用电器,这是一级类目。 它又分为很多种:比如说电视、空调、洗衣机、冰箱……等,这是二级类目。 并且还能够垂直细分,比如说电视又可以被分为:超薄电视、全面屏电视……等。 好,如何用代码实现这种需求? 一个需求拿到手中了,优先建立数据模型。 前端页面中的这些数据如何存放到数据库中? 数据库中的表如何设计,有哪些字段? 设计Java实体类和数据表对应? 这些问题解决了,方向也就定了,剩下的就是具体代码的编写了。 所以说数据模型是非常重要的,你想呀,方向都弄错了,写再多的代码有什么用? 2数据库表...
- 下一篇
Nacos 快速上手
Nacos 快速上手 简介 准备工作 部署 Spring Boot 集成 配置说明 Spring Cloud + Nacos Dubbo + Nacos 问题及解决方式 微服务现在越来火,有基于 Spring Cloud Netflix 体系的,也有基于 Spring Cloud Alibaba 为体系的。从以前的 Eureka 注册中心、Spring Cloud Config 配置中心、Spring Cloud Bus消息总线 到完全可以替代他们的 Nacos 出现,微服务技术体系的未来发展方向愈加清晰。所以,学会并了解如何使用 Nacos 是十分重要的。Nacos 不仅仅可以作为配置中心使用,还可以作为注册中心使用,其有很多十分优秀的特性,部署起来也十分方便。 主要目的: 熟练使用 Nacos; 基于 Spring Cloud Alibaba 体系进行项目基础 Demo 搭建,便于后续源码分析; 整合 Dubbo,便于后续源码分析; 手机用户请横屏获取最佳阅读体验,REFERENCES中是本文参考的链接,如需要链接和更多资源,可以加入『知识星球』获取长期知识分享服务。 简介 动态配...
相关文章
文章评论
共有0条评论来说两句吧...
文章二维码
点击排行
推荐阅读
最新文章
- SpringBoot2整合Redis,开启缓存,提高访问速度
- CentOS7编译安装Cmake3.16.3,解决mysql等软件编译问题
- CentOS7编译安装Gcc9.2.0,解决mysql等软件编译问题
- Docker快速安装Oracle11G,搭建oracle11g学习环境
- CentOS8编译安装MySQL8.0.19
- MySQL8.0.19开启GTID主从同步CentOS8
- SpringBoot2全家桶,快速入门学习开发网站教程
- CentOS7,CentOS8安装Elasticsearch6.8.6
- CentOS8,CentOS7,CentOS6编译安装Redis5.0.7
- Red5直播服务器,属于Java语言的直播服务器