LeetCode //C - 200. Number of Islands
200. Number of Islands
Given an m x n 2D binary grid grid which represents a map of *‘1’*s (land) and *‘0’*s (water), return the number of islands.
An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
Example 1:
Input: grid = [
[“1”,“1”,“1”,“1”,“0”],
[“1”,“1”,“0”,“1”,“0”],
[“1”,“1”,“0”,“0”,“0”],
[“0”,“0”,“0”,“0”,“0”]
]
Output: 1
Example 2:
Input: grid = [
[“1”,“1”,“0”,“0”,“0”],
[“1”,“1”,“0”,“0”,“0”],
[“0”,“0”,“1”,“0”,“0”],
[“0”,“0”,“0”,“1”,“1”]
]
Output: 3
Constraints:
- m == grid.length
- n == grid[i].length
- 1 <= m, n <= 300
- grid[i][j] is ‘0’ or ‘1’.
From: LeetCode
Link: 200. Number of Islands
Solution:
Ideas:
1. Initialize: The numIslands function initializes the count of islands to zero. It also determines the dimensions of the grid, m (number of rows) and n (number of columns).
2. Iterate through the Grid: The code then iterates over each cell of the grid. If the current cell is ‘1’, it indicates a part of an island that hasn’t been explored yet.
3. DFS to Explore the Island: When a ‘1’ is found, we use the dfs function to explore the entire island. The idea is that once we find a ‘1’, we want to explore all its neighboring cells (up, down, left, and right) to see if they are also part of the same island. If they are, we continue the exploration recursively.
- In the dfs function, if the current cell is out-of-bounds, or if it is water (i.e., ‘0’), we return immediately without further exploration.
- If the current cell is ‘1’, we mark it as visited by changing its value to ‘0’. This ensures that we don’t count the same part of an island more than once.
- We then recursively call dfs on the neighboring cells to continue exploring the island.
4. Counting the Islands: Each time we initiate a DFS exploration from the numIslands function (i.e., every time we find an unexplored ‘1’), we increment our island count by 1. By the end of the iteration over the grid, we would have explored and counted all distinct islands.
5. Return the Count: Finally, numIslands returns the count of islands.
Code:
void dfs(char** grid, int i, int j, int m, int n) {if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] == '0') {return;}grid[i][j] = '0';dfs(grid, i - 1, j, m, n); // updfs(grid, i + 1, j, m, n); // downdfs(grid, i, j - 1, m, n); // leftdfs(grid, i, j + 1, m, n); // right
}int numIslands(char** grid, int gridSize, int* gridColSize) {if (grid == NULL || gridSize == 0 || gridColSize == NULL) {return 0;}int m = gridSize;int n = gridColSize[0];int islandCount = 0;for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (grid[i][j] == '1') {islandCount++;dfs(grid, i, j, m, n);}}}return islandCount;
}
相关文章:
LeetCode //C - 200. Number of Islands
200. Number of Islands Given an m x n 2D binary grid grid which represents a map of *‘1’*s (land) and *‘0’*s (water), return the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically…...

使用Python构建强大的网络爬虫
介绍 网络爬虫是从网站收集数据的强大技术,而Python是这项任务中最流行的语言之一。然而,构建一个强大的网络爬虫不仅仅涉及到获取网页并解析其HTML。在本文中,我们将为您介绍创建一个网络爬虫的过程,这个爬虫不仅可以获取和保存网…...

图像处理之《基于语义对象轮廓自动生成的生成隐写术》论文精读
一、相关知识 首先我们需要了解传统隐写和生成式隐写的基本过程和区别。传统隐写需要选定一幅封面图像,然后使用某种隐写算法比如LSB、PVD、DCT等对像素进行修改将秘密嵌入到封面图像中得到含密图像,通过信道传输后再利用算法的逆过程提出秘密信息。而生…...
Java 字节流
一、输入输出流 输入输出 ------- 读写文件 输入 ------- 从文件中获取数据到自己的程序中,接收处理【读】 输出 ------- 将自己程序中处理好的数据保存到文件中【写】 流 ------- 数据移动的轨迹 二、流的分类 按照数据的移动轨迹分为:输入流 输出流…...

华硕电脑怎么录屏?分享实用录制经验!
“华硕电脑怎么录屏呀,刚买的笔记本电脑,是华硕的,自我感觉挺好用的,但是不知道怎么录屏,最近刚好要录一个教程,怎么都找不到在哪里录制,有人能教教我吗?” 随着电脑技术的不断发展…...
python学习--python的异常处理机制
try…except try:n1int(input(请输入一个整数))n2int(input(请输入另一个整数))resultn1/n2print(结果为,result) except ZeroDivisionError: print(除数不能为0)try…except…else 如果try块中没有抛出异常,则执行else块,如果try中抛出异常࿰…...

nacos+Dubbo整合快速入门
官网:Nacos Spring Boot 快速开始 下载下载链接启动:进入bin目录,startup.cmd -m standalone引入依赖 <dependency><groupId>org.apache.dubbo</groupId><artifactId>dubbo</artifactId><version>3.0.9…...

QT实现钟表
1、 头文件 #ifndef MAINWINDOW_H #define MAINWINDOW_H#include <QMainWindow> #include <QPaintEvent> //绘制事件类 #include <QDebug> //信息调试类 #include <QPainter> //画家类 #include <QTimerEve…...

准备我们心爱的IDEA写Jsp
JSP学习 一、准备我们心爱的IDEA new一个项目:New Project --> Next -->Next -->Finsh 二、配置好服务器Tomcat-9.0.30 1.> 在WEB-INF下创建一个Lib包 将jsp-api.jar复制进去,并使其生效 未生效前: 生效过程: 2.>…...

将近 5 万字讲解 Python Django 框架详细知识点(更新中)
Django 框架基本概述 Django 是一个开源的 Web 应用后端框架,由 Python 编写。它采用了 MVC 的软件设计模式,即模型(Model)、视图(View)和控制器(Controller)。在 Django 框架中&am…...

Arcgis提取每个像元的多波段反射率值
Arcgis提取每个像元的多波段反射率值 数据预处理 数据预处理阶段需要对遥感图像进行编辑传感器参数、辐射定标、大气校正、正射校正,具体流程见该文章 裁剪研究区 对于ENVI处理得到的tiff影像,虽然是经过裁剪了,但是还存在黑色的背景值&a…...
JavaScript面试题整理(一)
数据类型篇 1、JavaScript有哪些数据类型,它们的区别是什么? 基本数据类型:number、string、boolean、undefined、NaN、BigInt、Symbol 引入数据类型:Object NaN是JS中的特殊值,表示非数字,NaN不是数字…...

数据结构:树和二叉树之-堆排列 (万字详解)
目录 树概念及结构 1.1树的概念 1.2树的表示 编辑2.二叉树概念及结构 2.1概念 2.2数据结构中的二叉树:编辑 2.3特殊的二叉树: 编辑 2.4 二叉树的存储结构 2.4.1 顺序存储: 2.4.2 链式存储: 二叉树的实现及大小堆…...

爬虫入门基础:深入解析HTTP协议的工作过程
目录 一、HTTP协议简介 二、HTTP协议的工作过程 三、请求方法与常见用途 四、请求头与常见字段 五、状态码与常见含义 六、进阶话题和注意事项 总结 在如今这个数字化时代,互联网已经成为我们获取信息、交流和娱乐的主要渠道。而在互联网中,HTTP协…...

k8备份与恢复-Velero
简介 Velero 是一款可以安全的备份、恢复和迁移 Kubernetes 集群资源和持久卷等资源的备份恢复软件。 Velero 实现的 kubernetes 资源备份能力,可以轻松实现 Kubernetes 集群的数据备份和恢复、复制 kubernetes 集群资源到其他kubernetes 集群或者快速复制生产环境…...

基于Python开发的火车票分析助手(源码+可执行程序+程序配置说明书+程序使用说明书)
一、项目简介 本项目是一套基于Python开发的火车票分析助手,主要针对计算机相关专业的正在做毕设的学生与需要项目实战练习的Python学习者。 包含:项目源码、项目文档等,该项目附带全部源码可作为毕设使用。 项目都经过严格调试,…...

旺店通·企业奇门与金蝶云星空对接集成订单查询连通销售订单新增(旺店通销售-金蝶销售订单-小红书)
旺店通企业奇门与金蝶云星空对接集成订单查询连通销售订单新增(旺店通销售-金蝶销售订单-小红书) 接通系统:旺店通企业奇门 慧策最先以旺店通ERP切入商家核心管理痛点——订单管理,之后围绕电商经营管理中的核心管理诉求,先后布局流量获取、会…...

卡尔曼滤波应用在数据处理方面的应用
卡尔曼滤波应用到交通领域 滤波器介绍核心思想核心公式一维卡尔曼滤波器示例导入所需的库 滤波器介绍 卡尔曼滤波器是一种用于估计系统状态的数学方法,它以卡尔曼核心思想为基础,广泛应用于估计动态系统的状态和滤除测量中的噪声。以下是卡尔曼滤波器的核…...

PROFIBUS主站转ETHERCAT协议网关
产品介绍 JM-DPM-ECT是自主研发的一款PROFIBUS-DP主站功能的通讯网关。该产品主要功能是将各种PROFIBUS-DP从站接入到ETHERCAT网络中。 本网关连接到PROFIBUS总线中作为主站使用,连接到ETHERCAT总线中作为从站使用。 产品参数 技术参数 ◆ PROFIBUS-DP/V0 协议符…...

Vue路由的使用及node.js下载安装和环境搭建
目录 一、Vue路由 1.1 简介 ( 1 ) 特点 ( 2 ) 作用 1.2 实例 ( 1 ) 引入 ( 2 ) 组件 ( 3 ) 关系 ( 4 ) 路由 ( 5 ) 事件 ( 6 ) 锚点 二、nodeJS 2.1 下载 2.2 安装 2.3 环境搭建 新增 添加 测试 配置 运行 一、Vue路由 1.1 简介 Vue路由是Vue.…...

未来机器人的大脑:如何用神经网络模拟器实现更智能的决策?
编辑:陈萍萍的公主一点人工一点智能 未来机器人的大脑:如何用神经网络模拟器实现更智能的决策?RWM通过双自回归机制有效解决了复合误差、部分可观测性和随机动力学等关键挑战,在不依赖领域特定归纳偏见的条件下实现了卓越的预测准…...

eNSP-Cloud(实现本地电脑与eNSP内设备之间通信)
说明: 想象一下,你正在用eNSP搭建一个虚拟的网络世界,里面有虚拟的路由器、交换机、电脑(PC)等等。这些设备都在你的电脑里面“运行”,它们之间可以互相通信,就像一个封闭的小王国。 但是&#…...
线程与协程
1. 线程与协程 1.1. “函数调用级别”的切换、上下文切换 1. 函数调用级别的切换 “函数调用级别的切换”是指:像函数调用/返回一样轻量地完成任务切换。 举例说明: 当你在程序中写一个函数调用: funcA() 然后 funcA 执行完后返回&…...

理解 MCP 工作流:使用 Ollama 和 LangChain 构建本地 MCP 客户端
🌟 什么是 MCP? 模型控制协议 (MCP) 是一种创新的协议,旨在无缝连接 AI 模型与应用程序。 MCP 是一个开源协议,它标准化了我们的 LLM 应用程序连接所需工具和数据源并与之协作的方式。 可以把它想象成你的 AI 模型 和想要使用它…...

汽车生产虚拟实训中的技能提升与生产优化
在制造业蓬勃发展的大背景下,虚拟教学实训宛如一颗璀璨的新星,正发挥着不可或缺且日益凸显的关键作用,源源不断地为企业的稳健前行与创新发展注入磅礴强大的动力。就以汽车制造企业这一极具代表性的行业主体为例,汽车生产线上各类…...

如何在看板中有效管理突发紧急任务
在看板中有效管理突发紧急任务需要:设立专门的紧急任务通道、重新调整任务优先级、保持适度的WIP(Work-in-Progress)弹性、优化任务处理流程、提高团队应对突发情况的敏捷性。其中,设立专门的紧急任务通道尤为重要,这能…...

SpringCloudGateway 自定义局部过滤器
场景: 将所有请求转化为同一路径请求(方便穿网配置)在请求头内标识原来路径,然后在将请求分发给不同服务 AllToOneGatewayFilterFactory import lombok.Getter; import lombok.Setter; import lombok.extern.slf4j.Slf4j; impor…...

Redis数据倾斜问题解决
Redis 数据倾斜问题解析与解决方案 什么是 Redis 数据倾斜 Redis 数据倾斜指的是在 Redis 集群中,部分节点存储的数据量或访问量远高于其他节点,导致这些节点负载过高,影响整体性能。 数据倾斜的主要表现 部分节点内存使用率远高于其他节…...
2023赣州旅游投资集团
单选题 1.“不登高山,不知天之高也;不临深溪,不知地之厚也。”这句话说明_____。 A、人的意识具有创造性 B、人的认识是独立于实践之外的 C、实践在认识过程中具有决定作用 D、人的一切知识都是从直接经验中获得的 参考答案: C 本题解…...
Typeerror: cannot read properties of undefined (reading ‘XXX‘)
最近需要在离线机器上运行软件,所以得把软件用docker打包起来,大部分功能都没问题,出了一个奇怪的事情。同样的代码,在本机上用vscode可以运行起来,但是打包之后在docker里出现了问题。使用的是dialog组件,…...