当前位置: 首页 > article >正文

200. 岛屿数量【 力扣(LeetCode) 】

文章目录

  • 零、LeetCode 原题
  • 一、题目描述
  • 二、测试用例
  • 三、解题思路
  • 四、参考代码

零、LeetCode 原题


200. 岛屿数量

一、题目描述

给你一个由 ‘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.length
n == grid[i].length
1 <= m, n <= 300
grid[i][j] 的值为 '0''1'

三、解题思路

  1. 基本思路:
      这一题其实本质上就是考图的遍历,使用深度搜索和广度搜索都可以,关键是如何标识已经搜索过的区域。我的做法是采用一个二维向量来标识该块区域是否搜索过,官方的做法是直接修改原始数据,将1改为0,表示搜索过。【有兴趣可以在评论区晒出自己的算法】
  2. 具体思路:
    • 遍历二维向量,每次碰到一个没有搜索过的 1 :
      • 岛屿数量+1;
      • 将该块加入到搜索栈中,只要栈不为空:
        • 弹出栈顶元素,将其四周存在且未搜索的 1 加入栈中。
    • 返回结果。

四、参考代码

时间复杂度: O ( m n ) \Omicron(mn) O(mn)
空间复杂度: O ( m n ) \Omicron(mn) O(mn)

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        int ans = 0;
        vector<vector<bool>> used(m, vector<bool>(n, false));
        vector<pair<int, int>> dfs;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (used[i][j])
                    continue;
                used[i][j] = true;
                if (grid[i][j] == '0')
                    continue;
                ans++;
                dfs.emplace_back(i, j);
                while (dfs.size()) {
                    const auto index = dfs.back();
                    dfs.pop_back();
                    used[index.first][index.second] = true;
                    if (index.first > 0 && !used[index.first - 1][index.second]) {
                        if (grid[index.first - 1][index.second] == '1') {
                            dfs.emplace_back(index.first - 1, index.second);
                        }
                    }
                    if (index.first + 1 < m && !used[index.first + 1][index.second]) {
                        if (grid[index.first + 1][index.second] == '1') {
                            dfs.emplace_back(index.first + 1, index.second);
                        }
                    }
                    if (index.second > 0 && !used[index.first][index.second - 1]) {
                        if (grid[index.first][index.second - 1] == '1') {
                            dfs.emplace_back(index.first, index.second - 1);
                        }
                    }
                    if (index.second + 1 < n && !used[index.first][index.second + 1]) {
                        if (grid[index.first][index.second + 1] == '1') {
                            dfs.emplace_back(index.first, index.second + 1);
                        }
                    }
                }
            }
        }

        return ans;
    }
};

http://www.kler.cn/a/413627.html

相关文章:

  • 深度学习模型:卷积神经网络(CNN)
  • 网络技术-服务链编排的介绍和与虚拟化的区别
  • 开源免费的 分布式配置中心 介绍 与 选型 建议
  • Python双向链表、循环链表、栈
  • 实时数据开发 | 一文理解Flink窗口机制
  • Vue Promise的使用,界面使用异步线程循环执行方法(模拟线程)
  • 数据结构 (7)线性表的链式存储
  • uni-app中的样式尺寸单位,px,rpx,vh,vw
  • C++多线程——线程
  • 【人工智能】AutoML自动化机器学习模型构建与优化:使用Auto-sklearn与TPOT的实战指南
  • SpringBoot+Vue的音乐网站项目
  • mysql 触发器进入历史
  • Android 使用Charles抓包显示Unknown
  • MySQL 数据库索引优化实践指南
  • 利用阿里云镜像仓库和 Github Action 同步镜像
  • 【Qt】重写QComboBox下拉展示多列数据
  • CSGO游戏搬砖党如何应对上海Major
  • 【81-90期】Java核心面试问题深度解析:性能优化与高并发设计
  • 卷积神经网络(CNN)中的批量归一化层(Batch Normalization Layer)
  • ORACLE数据库直接取出数据库字段JSON串中的 VALUE内容
  • ensp配置静态路由与RIP协议
  • Harbor安装、HTTPS配置、修改端口后不可访问?
  • 【Java 解释器模式】实现高扩展性的医学专家诊断规则引擎
  • Js-对象-04-JSON
  • 林业产品推荐系统:Spring Boot开发手册
  • 九、Ubuntu Linux操作系统