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

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构建强大的网络爬虫

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

图像处理之《基于语义对象轮廓自动生成的生成隐写术》论文精读

一、相关知识 首先我们需要了解传统隐写和生成式隐写的基本过程和区别。传统隐写需要选定一幅封面图像&#xff0c;然后使用某种隐写算法比如LSB、PVD、DCT等对像素进行修改将秘密嵌入到封面图像中得到含密图像&#xff0c;通过信道传输后再利用算法的逆过程提出秘密信息。而生…...

Java 字节流

一、输入输出流 输入输出 ------- 读写文件 输入 ------- 从文件中获取数据到自己的程序中&#xff0c;接收处理【读】 输出 ------- 将自己程序中处理好的数据保存到文件中【写】 流 ------- 数据移动的轨迹 二、流的分类 按照数据的移动轨迹分为&#xff1a;输入流 输出流…...

华硕电脑怎么录屏?分享实用录制经验!

“华硕电脑怎么录屏呀&#xff0c;刚买的笔记本电脑&#xff0c;是华硕的&#xff0c;自我感觉挺好用的&#xff0c;但是不知道怎么录屏&#xff0c;最近刚好要录一个教程&#xff0c;怎么都找不到在哪里录制&#xff0c;有人能教教我吗&#xff1f;” 随着电脑技术的不断发展…...

python学习--python的异常处理机制

try…except try:n1int(input(请输入一个整数))n2int(input(请输入另一个整数))resultn1/n2print(结果为,result) except ZeroDivisionError: print(除数不能为0)try…except…else 如果try块中没有抛出异常&#xff0c;则执行else块&#xff0c;如果try中抛出异常&#xff0…...

nacos+Dubbo整合快速入门

官网&#xff1a;Nacos Spring Boot 快速开始 下载下载链接启动&#xff1a;进入bin目录&#xff0c;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一个项目&#xff1a;New Project --> Next -->Next -->Finsh 二、配置好服务器Tomcat-9.0.30 1.> 在WEB-INF下创建一个Lib包 将jsp-api.jar复制进去&#xff0c;并使其生效 未生效前&#xff1a; 生效过程&#xff1a; 2.>…...

将近 5 万字讲解 Python Django 框架详细知识点(更新中)

Django 框架基本概述 Django 是一个开源的 Web 应用后端框架&#xff0c;由 Python 编写。它采用了 MVC 的软件设计模式&#xff0c;即模型&#xff08;Model&#xff09;、视图&#xff08;View&#xff09;和控制器&#xff08;Controller&#xff09;。在 Django 框架中&am…...

Arcgis提取每个像元的多波段反射率值

Arcgis提取每个像元的多波段反射率值 数据预处理 数据预处理阶段需要对遥感图像进行编辑传感器参数、辐射定标、大气校正、正射校正&#xff0c;具体流程见该文章 裁剪研究区 对于ENVI处理得到的tiff影像&#xff0c;虽然是经过裁剪了&#xff0c;但是还存在黑色的背景值&a…...

JavaScript面试题整理(一)

数据类型篇 1、JavaScript有哪些数据类型&#xff0c;它们的区别是什么&#xff1f; 基本数据类型&#xff1a;number、string、boolean、undefined、NaN、BigInt、Symbol 引入数据类型&#xff1a;Object NaN是JS中的特殊值&#xff0c;表示非数字&#xff0c;NaN不是数字…...

数据结构:树和二叉树之-堆排列 (万字详解)

目录 树概念及结构 1.1树的概念 1.2树的表示 ​编辑2.二叉树概念及结构 2.1概念 2.2数据结构中的二叉树&#xff1a;​编辑 2.3特殊的二叉树&#xff1a; ​编辑 2.4 二叉树的存储结构 2.4.1 顺序存储&#xff1a; 2.4.2 链式存储&#xff1a; 二叉树的实现及大小堆…...

爬虫入门基础:深入解析HTTP协议的工作过程

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

k8备份与恢复-Velero

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

基于Python开发的火车票分析助手(源码+可执行程序+程序配置说明书+程序使用说明书)

一、项目简介 本项目是一套基于Python开发的火车票分析助手&#xff0c;主要针对计算机相关专业的正在做毕设的学生与需要项目实战练习的Python学习者。 包含&#xff1a;项目源码、项目文档等&#xff0c;该项目附带全部源码可作为毕设使用。 项目都经过严格调试&#xff0c;…...

旺店通·企业奇门与金蝶云星空对接集成订单查询连通销售订单新增(旺店通销售-金蝶销售订单-小红书)

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

卡尔曼滤波应用在数据处理方面的应用

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

PROFIBUS主站转ETHERCAT协议网关

产品介绍 JM-DPM-ECT是自主研发的一款PROFIBUS-DP主站功能的通讯网关。该产品主要功能是将各种PROFIBUS-DP从站接入到ETHERCAT网络中。 本网关连接到PROFIBUS总线中作为主站使用&#xff0c;连接到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.…...

【HarmonyOS 5.0】DevEco Testing:鸿蒙应用质量保障的终极武器

——全方位测试解决方案与代码实战 一、工具定位与核心能力 DevEco Testing是HarmonyOS官方推出的​​一体化测试平台​​&#xff0c;覆盖应用全生命周期测试需求&#xff0c;主要提供五大核心能力&#xff1a; ​​测试类型​​​​检测目标​​​​关键指标​​功能体验基…...

Docker 运行 Kafka 带 SASL 认证教程

Docker 运行 Kafka 带 SASL 认证教程 Docker 运行 Kafka 带 SASL 认证教程一、说明二、环境准备三、编写 Docker Compose 和 jaas文件docker-compose.yml代码说明&#xff1a;server_jaas.conf 四、启动服务五、验证服务六、连接kafka服务七、总结 Docker 运行 Kafka 带 SASL 认…...

select、poll、epoll 与 Reactor 模式

在高并发网络编程领域&#xff0c;高效处理大量连接和 I/O 事件是系统性能的关键。select、poll、epoll 作为 I/O 多路复用技术的代表&#xff0c;以及基于它们实现的 Reactor 模式&#xff0c;为开发者提供了强大的工具。本文将深入探讨这些技术的底层原理、优缺点。​ 一、I…...

css3笔记 (1) 自用

outline: none 用于移除元素获得焦点时默认的轮廓线 broder:0 用于移除边框 font-size&#xff1a;0 用于设置字体不显示 list-style: none 消除<li> 标签默认样式 margin: xx auto 版心居中 width:100% 通栏 vertical-align 作用于行内元素 / 表格单元格&#xff…...

CRMEB 中 PHP 短信扩展开发:涵盖一号通、阿里云、腾讯云、创蓝

目前已有一号通短信、阿里云短信、腾讯云短信扩展 扩展入口文件 文件目录 crmeb\services\sms\Sms.php 默认驱动类型为&#xff1a;一号通 namespace crmeb\services\sms;use crmeb\basic\BaseManager; use crmeb\services\AccessTokenServeService; use crmeb\services\sms\…...

scikit-learn机器学习

# 同时添加如下代码, 这样每次环境(kernel)启动的时候只要运行下方代码即可: # Also add the following code, # so that every time the environment (kernel) starts, # just run the following code: import sys sys.path.append(/home/aistudio/external-libraries)机…...

Python Einops库:深度学习中的张量操作革命

Einops&#xff08;爱因斯坦操作库&#xff09;就像给张量操作戴上了一副"语义眼镜"——让你用人类能理解的方式告诉计算机如何操作多维数组。这个基于爱因斯坦求和约定的库&#xff0c;用类似自然语言的表达式替代了晦涩的API调用&#xff0c;彻底改变了深度学习工程…...

Golang——7、包与接口详解

包与接口详解 1、Golang包详解1.1、Golang中包的定义和介绍1.2、Golang包管理工具go mod1.3、Golang中自定义包1.4、Golang中使用第三包1.5、init函数 2、接口详解2.1、接口的定义2.2、空接口2.3、类型断言2.4、结构体值接收者和指针接收者实现接口的区别2.5、一个结构体实现多…...

从物理机到云原生:全面解析计算虚拟化技术的演进与应用

前言&#xff1a;我的虚拟化技术探索之旅 我最早接触"虚拟机"的概念是从Java开始的——JVM&#xff08;Java Virtual Machine&#xff09;让"一次编写&#xff0c;到处运行"成为可能。这个软件层面的虚拟化让我着迷&#xff0c;但直到后来接触VMware和Doc…...

规则与人性的天平——由高考迟到事件引发的思考

当那位身着校服的考生在考场关闭1分钟后狂奔而至&#xff0c;他涨红的脸上写满绝望。铁门内秒针划过的弧度&#xff0c;成为改变人生的残酷抛物线。家长声嘶力竭的哀求与考务人员机械的"这是规定"&#xff0c;构成当代中国教育最尖锐的隐喻。 一、刚性规则的必要性 …...