【图论】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
解题思路
- 1、使用深度优先搜索DFS来遍历二维网格,找到所有岛屿。(PS: 深度优先搜索(DFS)一般是使用递归来实现)
- 2、对于每个遍历到的陆地(‘1’),开始进行搜索,将其与相邻的陆地标记为已访问过,直到将整个岛屿搜索完成。
- 3、统计搜索过程中遇到的岛屿数量。
Java实现
public class NumberOfIslands {public int numIslands(char[][] grid) {if (grid == null || grid.length == 0 || grid[0].length == 0) {return 0;}int m = grid.length;int n = grid[0].length;int count = 0;
// {'1', '1', '0', '0', '0'},
// {'1', '1', '0', '0', '0'},
// {'0', '0', '1', '0', '0'},
// {'0', '0', '0', '1', '1'}for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (grid[i][j] == '1') {// 当前位置为陆地,开始进行深度优先搜索// 直到grid[i][j]周边没有相连的陆地dfs(grid, i, j);// 每开始一次搜索,岛屿数量加一count++;}}}return count;}/*** 深度优先搜索函数* @param grid* @param i* @param j*/private void dfs(char[][] grid, int i, int j) {int m = grid.length;int n = grid[0].length;// 边界条件和递归终止条件if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] == '0') {return;}grid[i][j] = '0'; //将当前单元格标记为已访问//继续搜索当前位置的上、下、左、右四个方向,探索相邻的单元格//直到没有相邻的岛屿(grid[i][j] == '0')dfs(grid, i + 1, j);dfs(grid, i - 1, j);dfs(grid, i, j + 1);dfs(grid, i, j - 1);}public static void main(String[] args) {NumberOfIslands islands = new NumberOfIslands();char[][] grid = {{'1', '1', '0', '0', '0'},{'1', '1', '0', '0', '0'},{'0', '0', '1', '0', '0'},{'0', '0', '0', '1', '1'}};System.out.println("Number of islands: " + islands.numIslands(grid));}
}
时间空间复杂度
-
时间复杂度:O(m * n),其中 m 和 n 分别是二维网格的行数和列数,因为需要遍历整个二维网格。
-
空间复杂度:O(m * n),深度优先搜索的递归调用可能达到 O(m * n) 的深度,其中 m 和 n 分别是二维网格的行数和列数。
相关文章:
【图论】Leetcode 200. 岛屿数量【中等】
岛屿数量 给你一个由 ‘1’(陆地)和 ‘0’(水)组成的的二维网格,请你计算网格中岛屿的数量。 岛屿总是被水包围,并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。 此外,你可以…...

酒店大厅装水离子雾化壁炉前和装后对比
在酒店大厅装水离子雾化壁炉之前和之后,大厅的氛围和体验会有显著的对比: 装水离子雾化壁炉之前: 传统感:在壁炉安装之前,大厅可能会有传统的装饰或者简单的暖气设备,缺乏现代化的元素。这种传统感可能会…...

城市内涝与海绵城市规划设计中的水文水动力模拟
原文链接:城市内涝与海绵城市规划设计中的水文水动力模拟https://mp.weixin.qq.com/s?__bizMzUzNTczMDMxMg&mid2247601198&idx5&sn35b9e5e3961ea2f190f9742236a7217f&chksmfa820dc9cdf584df97633f64d19bdc3e5f7d1a5a85000c8f040e1953c51b9b39c87b5…...
C++项目实战与经验分享
在编程世界中,C++ 是一种功能强大且灵活的编程语言,广泛应用于系统级编程、游戏开发、嵌入式系统以及高性能计算等领域。本文将分享一个基于C++的图像处理系统项目实战经验,并深入探讨在开发过程中遇到的问题及解决方案。 一、项目概述 本次项目实战的目标是开发一个基于C…...

Day17_学点JavaEE_转发、重定向、Get、POST、乱码问题总结
1 转发 转发:一般查询了数据之后,转发到一个jsp页面进行展示 req.setAttribute("list", list); req.getRequestDispatcher("student_list.jsp").forward(req, resp);2 重定向 重定向:一般添加、删除、修改之后重定向到…...

Mouse IFN-α ELISA kit (Quick Test)
干扰素α(IFN-α)是一类由免疫细胞分泌的内源性调节因子,也被称为白细胞干扰素,主要参与响应病毒感染的先天性免疫。 基于结构特征、受体、细胞来源和生物活性的不同,干扰素可被分为Ⅰ、Ⅱ、Ⅲ三种类型,其中…...

AMD Tensile 简介与示例
按照知其然,再知其所以然的认知次序进行 1,下载代码 git clone --recursive https://github.com/ROCm/Tensile.git 2,安装 Tensile cd Tensile mkdir build cd build ../Tensile/bin/Tensile ../Tensile/Configs/rocblas_dgemm_nn_asm_full…...

Rust语言
文章目录 Rust语言一,Rust语言是什么二,Rust语言能做什么?Rust语言的设计使其适用于许多不同的领域,包括但不限于以下几个方面:1. 传统命令行程序:2. Web 应用:3. 网络服务器:4. 嵌入…...

排序算法之冒泡排序
目录 一、简介二、代码实现三、应用场景 一、简介 算法平均时间复杂度最好时间复杂度最坏时间复杂度空间复杂度排序方式稳定性冒泡排序O(n^2 )O(n)O(n^2)O(1)In-place稳定 稳定:如果A原本在B前面,而AB,排序之后A仍然在B的前面; 不…...

js打印页面源码 ,打印选取的容器里的内容,打印指定内容
js打印页面源码 ,打印选取的容器里的内容,打印指定内容 效果 代码 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><meta http-equiv"X-UA-Compatible" content"IEedge&…...
算法练习第五十天|123.买卖股票的最佳时机III、188.买卖股票的最佳时机IV
123. 买卖股票的最佳时机 III 188. 买卖股票的最佳时机 IV 123.买卖股票的最佳时机III class Solution {public int maxProfit(int[] prices) {//dp[i][j] 第i天买卖股票获得的最大利润/**j0不操作j1第一次持有j2第一次不持有j3第二次持有j4第二次不持有dp[i][0] dp[i-1][0]d…...

细胞世界:4.细胞分化(划区域)与细胞衰老(设施磨损)
(1)细胞凋亡 1. 概念:细胞凋亡可以比作城市的规划者主动拆除某些建筑来更新城市或防止危险建筑对市民的潜在伤害。这是一个有序的过程,由城市(细胞内部)的特定规划(基因)所决定。 2. 特征:细…...

c语言:操作符
操作符 一.算术操作符: + - * % / 1.除了%操作符之外,其他的几个操作符可以作用与整数和浮点数,如:5%2.0//error. 2.对于操作符,如果两个操作数都为整数,执行整数除法而只要有浮点数执行的就是浮点数除法。 3.%操作符的两个操作数必须为整数。 二.移位操作符:<&…...

谷歌seo自然搜索排名怎么提升快?
要想在谷歌上排名快速上升,关键在于运用GPC爬虫池跟高低搭配的外链组合 首先你要做的,就是让谷歌的蜘蛛频繁来你的网站,网站需要被谷歌蜘蛛频繁抓取和索引,那这时候GPC爬虫池就能派上用场了,GPC爬虫池能够帮你大幅度提…...

Golang | Leetcode Golang题解之第13题罗马数字转整数
题目: 题解: var symbolValues map[byte]int{I: 1, V: 5, X: 10, L: 50, C: 100, D: 500, M: 1000}func romanToInt(s string) (ans int) {n : len(s)for i : range s {value : symbolValues[s[i]]if i < n-1 && value < symbolValues[s…...

说说我理解的数据库中的Schema吧
一、SQL标准对schema如何定义? ISO/IEC 9075-1 SQL标准中将schema定义为描述符的持久命名集合(a persistent, named collection of descriptors)。 大部分的网上资料定义Schema如下: schema是用来组织和管理数据的一种方式。它…...
nginx 如何对用户屏蔽网站首页但是对蜘蛛开放
使用 Nginx 的 if 指令结合 $http_user_agent 变量来实现条件判断。不过,请注意,Nginx 官方文档通常建议避免在配置中过度使用 if 指令,因为它可能会导致不可预测的行为,尤其是在复杂的配置中。然而,对于简单的用例&am…...

【vue】ref 和 reactive 对比
ref:存储单个数据,如数值,字符串reactive:存储复杂数据,如对象,数组 <!DOCTYPE html> <html lang"en"><head><meta charset"UTF-8"><meta name"vie…...

爬虫现在还有那么吃香嘛?
Python 作为一种广泛应用的编程语言,在 Web 开发、大数据开发、人工智能开发和嵌入式开发等领域都有着重要的应用。 Python 的易学性、清晰性和可移植性等特点使它得到很多技术人士的喜爱。对于数据科学和机器学习领域的程序员来说,Python 提供了强大的…...

MobaXterm无法登陆oracle cloud的问题
问题 我在oracle cloud上创建实例的时候,只能使用密钥的方式登陆,当时下载了私钥文件。实例创建好以后,在mobaxterm上使用这个私钥文件无法登陆 排查 尝试使用mobaxterm的keygen,把私钥文件转成ppk格式,还是不行。…...

日语AI面试高效通关秘籍:专业解读与青柚面试智能助攻
在如今就业市场竞争日益激烈的背景下,越来越多的求职者将目光投向了日本及中日双语岗位。但是,一场日语面试往往让许多人感到步履维艰。你是否也曾因为面试官抛出的“刁钻问题”而心生畏惧?面对生疏的日语交流环境,即便提前恶补了…...
Device Mapper 机制
Device Mapper 机制详解 Device Mapper(简称 DM)是 Linux 内核中的一套通用块设备映射框架,为 LVM、加密磁盘、RAID 等提供底层支持。本文将详细介绍 Device Mapper 的原理、实现、内核配置、常用工具、操作测试流程,并配以详细的…...
高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数
高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数 在软件开发中,单例模式(Singleton Pattern)是一种常见的设计模式,确保一个类仅有一个实例,并提供一个全局访问点。在多线程环境下,实现单例模式时需要注意线程安全问题,以防止多个线程同时创建实例,导致…...

R 语言科研绘图第 55 期 --- 网络图-聚类
在发表科研论文的过程中,科研绘图是必不可少的,一张好看的图形会是文章很大的加分项。 为了便于使用,本系列文章介绍的所有绘图都已收录到了 sciRplot 项目中,获取方式: R 语言科研绘图模板 --- sciRplothttps://mp.…...
CppCon 2015 学习:Reactive Stream Processing in Industrial IoT using DDS and Rx
“Reactive Stream Processing in Industrial IoT using DDS and Rx” 是指在工业物联网(IIoT)场景中,结合 DDS(Data Distribution Service) 和 Rx(Reactive Extensions) 技术,实现 …...
Yii2项目自动向GitLab上报Bug
Yii2 项目自动上报Bug 原理 yii2在程序报错时, 会执行指定action, 通过重写ErrorAction, 实现Bug自动提交至GitLab的issue 步骤 配置SiteController中的actions方法 public function actions(){return [error > [class > app\helpers\web\ErrorAction,],];}重写Error…...

五、jmeter脚本参数化
目录 1、脚本参数化 1.1 用户定义的变量 1.1.1 添加及引用方式 1.1.2 测试得出用户定义变量的特点 1.2 用户参数 1.2.1 概念 1.2.2 位置不同效果不同 1.2.3、用户参数的勾选框 - 每次迭代更新一次 总结用户定义的变量、用户参数 1.3 csv数据文件参数化 1、脚本参数化 …...
Netty自定义协议解析
目录 自定义协议设计 实现消息解码器 实现消息编码器 自定义消息对象 配置ChannelPipeline Netty提供了强大的编解码器抽象基类,这些基类能够帮助开发者快速实现自定义协议的解析。 自定义协议设计 在实现自定义协议解析之前,需要明确协议的具体格式。例如,一个简单的…...

从0开始学习R语言--Day17--Cox回归
Cox回归 在用医疗数据作分析时,最常见的是去预测某类病的患者的死亡率或预测他们的结局。但是我们得到的病人数据,往往会有很多的协变量,即使我们通过计算来减少指标对结果的影响,我们的数据中依然会有很多的协变量,且…...

React、Git、计网、发展趋势等内容——前端面试宝典(字节、小红书和美团)
React React Hook实现架构、.Hook不能在循环嵌套语句中使用 , 为什么,Fiber架构,面试向面试官介绍,详细解释 用户: React Hook实现架构、.Hook不能在循环嵌套语句中使用 , 为什么,Fiber架构,面试向面试官介绍&#x…...