LeetCode之岛屿数量(两百)
发布日期:2021-06-30 21:11:11
浏览次数:2
分类:技术文章
本文共 2977 字,大约阅读时间需要 9 分钟。
目录
题目
(原题链接:)
给你一个由 '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 解释: 每座岛屿只能由水平和/或竖直方向上相邻的陆地连接而成。
解题
方法一、深度优先搜索法
分析:
为了求出岛屿的数量,我们可以扫描整个MxN的二维网格。如果一个位置为 1,则以其为起始节点开始进行深度优先搜索。在深度优先搜索的过程中,每个搜索到的 1 都会被重新标记为 0。最终,岛屿的数量就是我们进行深度优先搜索的次数。
代码:
class Solution {public: int numIslands(vector>& grid) { int r = grid.size(); if (r==0) return 0; int c = grid[0].size(); int islandsNumber = 0; for (int i=0; i >& g, int i, int j) { int r = g.size(); int c = g[0].size(); g[i][j] = '0'; if (i - 1 >= 0 && g[i-1][j] == '1') dfs(g, i - 1, j); if (i + 1 < r && g[i+1][j] == '1') dfs(g, i + 1, j); if (j - 1 >= 0 && g[i][j-1] == '1') dfs(g, i, j - 1); if (j + 1 < c && g[i][j+1] == '1') dfs(g, i, j + 1); }};
时间复杂度:O(MN),其中 M 和 N 分别为行数和列数。
空间复杂度:O(MN),在最坏情况下,整个网格均为陆地,深度优先搜索的深度达到 MN。
执行结果:
方法二、广度优先搜索法
分析:同理,差别只是进行广度优先搜索算法。
代码:
class Solution {public: int numIslands(vector>& grid) { int nr = grid.size(); if (nr == 0) return 0; int nc = grid[0].size(); int num_islands = 0; for (int r = 0; r < nr; ++r) { for (int c = 0; c < nc; ++c) { if (grid[r][c] == '1') { ++num_islands; grid[r][c] = '0'; queue > neighbors; neighbors.push({r, c}); while (!neighbors.empty()) { auto rc = neighbors.front(); neighbors.pop(); int row = rc.first, col = rc.second; if (row - 1 >= 0 && grid[row-1][col] == '1') { neighbors.push({row-1, col}); grid[row-1][col] = '0'; } if (row + 1 < nr && grid[row+1][col] == '1') { neighbors.push({row+1, col}); grid[row+1][col] = '0'; } if (col - 1 >= 0 && grid[row][col-1] == '1') { neighbors.push({row, col-1}); grid[row][col-1] = '0'; } if (col + 1 < nc && grid[row][col+1] == '1') { neighbors.push({row, col+1}); grid[row][col+1] = '0'; } } } } } return num_islands; }};
时间复杂度:O(MN),其中 M 和 N 分别为行数和列数。
空间复杂度:O(min(M,N)),在最坏情况下,整个网格均为陆地,深度优先搜索的深度达到 min(M,N)。
执行结果:
转载地址:https://liuzhen.blog.csdn.net/article/details/107398030 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
逛到本站,mark一下
[***.202.152.39]2024年04月09日 00时45分30秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
基于java的图书管理系统的设计与实现
2019-04-30
基于java的SSM框架理财管理系统的设计与实现
2019-04-30
基于java的ssm框架就业信息管理系统的设计
2019-04-30
基于java的ssm框架的旅游网站设计与实现
2019-04-30
基于java的SSM框架的流浪猫救助网站的设计与实现
2019-04-30
基于java的SSM框架的教务关系系统的设计与实现
2019-04-30
别再问我什么是A/B测试了!
2019-04-30
如何用同期群分析模型提升留存?(Tableau实战)
2019-04-30
爱了,吹爆这个高颜值的流程图工具!
2019-04-30
一个数据项目
2019-04-30
基于JAVA_JSP电子书下载系统
2019-04-30
基于java出租车计价器设计与实现
2019-04-30
基于java的B2C的网上拍卖系统
2019-04-30
十二时辰篇:这该死的 996
2019-04-30
2021最新 上海互联网公司排名
2019-04-30
字节vs快手!取消大小周之战
2019-04-30
送一个闲置显示器!
2019-04-30
Oracle 行转列 pivot函数基本用法
2019-04-30
Oracle字符串分隔符替换(替换奇数个或偶数个)
2019-04-30
Oracle 利用 UTL_SMTP 包发送邮件
2019-04-30