当前位置: 首页 > 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;还是不行。…...

VLL: a lock manager redesign for main memory database systems阅读

为何要有VLL&#xff1f;VLL旨在解决什么问题&#xff1f; 在数据库系统中&#xff0c;锁是广泛使用的并发控制机制。然而对于内存数据库系统&#xff0c;锁管理器却成为了性能瓶颈所在。 一项研究说明内存数据库中有16%&#xff5e;25%的时间用于与锁管理器的交互 在传统的锁…...

REST API实战演练之JavaScript使用Rest API

咱们前面讲了一下如何创建REST API 假期别闲着&#xff1a;REST API实战演练之创建Rest API-CSDN博客 又讲了java客户端如何使用REST API 假期别闲着&#xff1a;REST API实战演练之客户端使用Rest API-CSDN博客 接下来咱们看看JavaScript怎么使用REST API。 一、新建一个…...

期货量化交易软件:MQL5 中的范畴论 (第 15 部分)函子与图论

概述 在上一篇文章中&#xff0c;我们目睹了前期文章中涵盖的概念&#xff08;如线性序&#xff09;如何视作范畴&#xff0c;以及为什么它们的“态射”在与其它范畴相关时即构成函子。在本文中&#xff0c;我们赫兹量化软件将阐述来自前期文章中的概括&#xff0c;即通过查看…...

2024妈妈杯数学建模B题思路-甲骨文智能识别中原始拓片单字自动分割与识别研究

# 1 赛题 B 题 甲骨文智能识别中原始拓片单字自动分割与识别研究 甲骨文是我国目前已知的最早成熟的文字系统&#xff0c;它是一种刻在龟甲或 兽骨上的古老文字。甲骨文具有极其重要的研究价值&#xff0c;不仅对中国文明的 起源具有重要意义&#xff0c;也对世界文明的研究有着…...

sql 之 索引

索引是对数据库表中一列或多列的值进行排序的一种结构&#xff0c;使用索引可快速访问数据库表中的特定信息。 1. 什么是索引 官方上面说索引是帮助MySQL高效获取数据的数据结构&#xff0c;通俗点来说&#xff0c;数据库索引就像是是一本书的目录&#xff0c;可以直接根据页码…...

创建基于Node的WebSocket服务

一:安装nodejs与npm apt-get install nodejs npm 但这种方法安装的版本可能偏低,影响后续的 npm install ws wscat。 按照 How to Install Node.js and npm on Ubuntu 18.04 | Linuxize里的步骤安装: 1、curl -sL https://deb.nodesource.com/setup_12.x | sudo -E bash …...

Flask快速搭建文件上传服务与接口

说明&#xff1a;仅供学习使用&#xff0c;请勿用于非法用途&#xff0c;若有侵权&#xff0c;请联系博主删除 作者&#xff1a;zhu6201976 一、需求背景 前端通过浏览器&#xff0c;访问后端服务器地址&#xff0c;将目标文件进行上传。 访问地址&#xff1a;http://127.0.0…...

AI算力报告:算力大时代,AI算力产业链全景梳理

今天分享的是AI算力专题系列深度研究报告&#xff1a;《算力大时代&#xff0c;AI算力产业链全景梳理》。 &#xff08;报告出品方&#xff1a;中信建投证券&#xff09; 报告共计&#xff1a;98页 核心观点 生成式 AI取得突破&#xff0c;我们对生成式 A 带来的算力需求做…...

点击上传文件

一、页面样式&#xff1a; &#xff08;1&#xff09;点击前&#xff1a; &#xff08;2&#xff09;点击后&#xff1a; 设计&#xff1a;①自定义elementPlus图标&#xff1b;②使用Tooltip实现鼠标悬浮按钮上出现文字提示&#xff1b;③上传与更换的切换样式&#xff1b;…...

文件上传【2】--靶场通关

1.前端禁用js绕过 上传文件&#xff0c;进行抓包&#xff0c;没有抓到&#xff0c;说明这里的验证是前端js验证跳出的弹窗 禁用js后&#xff0c;php文件上传成功。 2.文件上传.htaccess 上传png木马后连接不上 代码中存在.htaccess&#xff0c;判断此时应该就是需要用到.htac…...