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

【图论】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’&#xff08;陆地&#xff09;和 ‘0’&#xff08;水&#xff09;组成的的二维网格&#xff0c;请你计算网格中岛屿的数量。 岛屿总是被水包围&#xff0c;并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。 此外&#xff0c;你可以…...

酒店大厅装水离子雾化壁炉前和装后对比

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

城市内涝与海绵城市规划设计中的水文水动力模拟

原文链接&#xff1a;城市内涝与海绵城市规划设计中的水文水动力模拟https://mp.weixin.qq.com/s?__bizMzUzNTczMDMxMg&mid2247601198&idx5&sn35b9e5e3961ea2f190f9742236a7217f&chksmfa820dc9cdf584df97633f64d19bdc3e5f7d1a5a85000c8f040e1953c51b9b39c87b5…...

C++项目实战与经验分享

在编程世界中,C++ 是一种功能强大且灵活的编程语言,广泛应用于系统级编程、游戏开发、嵌入式系统以及高性能计算等领域。本文将分享一个基于C++的图像处理系统项目实战经验,并深入探讨在开发过程中遇到的问题及解决方案。 一、项目概述 本次项目实战的目标是开发一个基于C…...

Day17_学点JavaEE_转发、重定向、Get、POST、乱码问题总结

1 转发 转发&#xff1a;一般查询了数据之后&#xff0c;转发到一个jsp页面进行展示 req.setAttribute("list", list); req.getRequestDispatcher("student_list.jsp").forward(req, resp);2 重定向 重定向&#xff1a;一般添加、删除、修改之后重定向到…...

Mouse IFN-α ELISA kit (Quick Test)

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

AMD Tensile 简介与示例

按照知其然&#xff0c;再知其所以然的认知次序进行 1&#xff0c;下载代码 git clone --recursive https://github.com/ROCm/Tensile.git 2&#xff0c;安装 Tensile cd Tensile mkdir build cd build ../Tensile/bin/Tensile ../Tensile/Configs/rocblas_dgemm_nn_asm_full…...

Rust语言

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

排序算法之冒泡排序

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

js打印页面源码 ,打印选取的容器里的内容,打印指定内容

js打印页面源码 &#xff0c;打印选取的容器里的内容&#xff0c;打印指定内容 效果 代码 <!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. 概念&#xff1a;细胞凋亡可以比作城市的规划者主动拆除某些建筑来更新城市或防止危险建筑对市民的潜在伤害。这是一个有序的过程&#xff0c;由城市&#xff08;细胞内部&#xff09;的特定规划&#xff08;基因&#xff09;所决定。 2. 特征&#xff1a;细…...

c语言:操作符

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

谷歌seo自然搜索排名怎么提升快?

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

Golang | Leetcode Golang题解之第13题罗马数字转整数

题目&#xff1a; 题解&#xff1a; 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如何定义&#xff1f; ISO/IEC 9075-1 SQL标准中将schema定义为描述符的持久命名集合&#xff08;a persistent, named collection of descriptors&#xff09;。 大部分的网上资料定义Schema如下&#xff1a; schema是用来组织和管理数据的一种方式。它…...

nginx 如何对用户屏蔽网站首页但是对蜘蛛开放

使用 Nginx 的 if 指令结合 $http_user_agent 变量来实现条件判断。不过&#xff0c;请注意&#xff0c;Nginx 官方文档通常建议避免在配置中过度使用 if 指令&#xff0c;因为它可能会导致不可预测的行为&#xff0c;尤其是在复杂的配置中。然而&#xff0c;对于简单的用例&am…...

【vue】ref 和 reactive 对比

ref&#xff1a;存储单个数据&#xff0c;如数值&#xff0c;字符串reactive&#xff1a;存储复杂数据&#xff0c;如对象&#xff0c;数组 <!DOCTYPE html> <html lang"en"><head><meta charset"UTF-8"><meta name"vie…...

爬虫现在还有那么吃香嘛?

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

MobaXterm无法登陆oracle cloud的问题

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

RocketMQ延迟消息机制

两种延迟消息 RocketMQ中提供了两种延迟消息机制 指定固定的延迟级别 通过在Message中设定一个MessageDelayLevel参数&#xff0c;对应18个预设的延迟级别指定时间点的延迟级别 通过在Message中设定一个DeliverTimeMS指定一个Long类型表示的具体时间点。到了时间点后&#xf…...

智慧工地云平台源码,基于微服务架构+Java+Spring Cloud +UniApp +MySql

智慧工地管理云平台系统&#xff0c;智慧工地全套源码&#xff0c;java版智慧工地源码&#xff0c;支持PC端、大屏端、移动端。 智慧工地聚焦建筑行业的市场需求&#xff0c;提供“平台网络终端”的整体解决方案&#xff0c;提供劳务管理、视频管理、智能监测、绿色施工、安全管…...

多场景 OkHttpClient 管理器 - Android 网络通信解决方案

下面是一个完整的 Android 实现&#xff0c;展示如何创建和管理多个 OkHttpClient 实例&#xff0c;分别用于长连接、普通 HTTP 请求和文件下载场景。 <?xml version"1.0" encoding"utf-8"?> <LinearLayout xmlns:android"http://schemas…...

Auto-Coder使用GPT-4o完成:在用TabPFN这个模型构建一个预测未来3天涨跌的分类任务

通过akshare库&#xff0c;获取股票数据&#xff0c;并生成TabPFN这个模型 可以识别、处理的格式&#xff0c;写一个完整的预处理示例&#xff0c;并构建一个预测未来 3 天股价涨跌的分类任务 用TabPFN这个模型构建一个预测未来 3 天股价涨跌的分类任务&#xff0c;进行预测并输…...

Vue2 第一节_Vue2上手_插值表达式{{}}_访问数据和修改数据_Vue开发者工具

文章目录 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染2. 插值表达式{{}}3. 访问数据和修改数据4. vue响应式5. Vue开发者工具--方便调试 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染 准备容器引包创建Vue实例 new Vue()指定配置项 ->渲染数据 准备一个容器,例如: …...

大模型多显卡多服务器并行计算方法与实践指南

一、分布式训练概述 大规模语言模型的训练通常需要分布式计算技术,以解决单机资源不足的问题。分布式训练主要分为两种模式: 数据并行:将数据分片到不同设备,每个设备拥有完整的模型副本 模型并行:将模型分割到不同设备,每个设备处理部分模型计算 现代大模型训练通常结合…...

深度学习习题2

1.如果增加神经网络的宽度&#xff0c;精确度会增加到一个特定阈值后&#xff0c;便开始降低。造成这一现象的可能原因是什么&#xff1f; A、即使增加卷积核的数量&#xff0c;只有少部分的核会被用作预测 B、当卷积核数量增加时&#xff0c;神经网络的预测能力会降低 C、当卷…...

腾讯云V3签名

想要接入腾讯云的Api&#xff0c;必然先按其文档计算出所要求的签名。 之前也调用过腾讯云的接口&#xff0c;但总是卡在签名这一步&#xff0c;最后放弃选择SDK&#xff0c;这次终于自己代码实现。 可能腾讯云翻新了接口文档&#xff0c;现在阅读起来&#xff0c;清晰了很多&…...

在 Spring Boot 项目里,MYSQL中json类型字段使用

前言&#xff1a; 因为程序特殊需求导致&#xff0c;需要mysql数据库存储json类型数据&#xff0c;因此记录一下使用流程 1.java实体中新增字段 private List<User> users 2.增加mybatis-plus注解 TableField(typeHandler FastjsonTypeHandler.class) private Lis…...

【C++】纯虚函数类外可以写实现吗?

1. 答案 先说答案&#xff0c;可以。 2.代码测试 .h头文件 #include <iostream> #include <string>// 抽象基类 class AbstractBase { public:AbstractBase() default;virtual ~AbstractBase() default; // 默认析构函数public:virtual int PureVirtualFunct…...