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

岛屿的数量(BFS)

给你一个由 '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

示例 2:

输入:grid = [["1","1","0","0","0"],["1","1","0","0","0"],["0","0","1","0","0"],["0","0","0","1","1"]
]
输出:3

提示:

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 300
  • grid[i][j] 的值为 '0' 或 '1'


class Solution {
public:int numIslands(vector<vector<char>>& grid) {if (grid.empty()) return 0;int rows = grid.size();int cols = grid[0].size();int islands = 0;int dx[] = {0, 0, -1, 1};int dy[] = {-1, 1, 0, 0};queue<pair<int,int>> q;for(int i = 0; i < rows; i++) {for(int j = 0; j < cols; j++) {  if(grid[i][j] == '1') {      // 发现陆地islands++;               // 岛屿数量加1q.push({i, j});          // 将起点加入队列grid[i][j] = '0';        // 标记为已访问while(!q.empty()) {auto [x, y] = q.front();  // 获取队首坐标q.pop();for(int k = 0; k < 4; k++) {int nx = x + dx[k];   int ny = y + dy[k];  if(nx >= 0 && nx < rows && ny >= 0 && ny < cols && grid[nx][ny] == '1') {q.push({nx, ny}); // 加入队列grid[nx][ny] = '0'; // 标记为已访问}}}}}}return islands;}
};

当遇到 '1'(未访问的陆地)时,说明发现了一个新的岛屿。用 BFS 将所有相连的陆地标记为'0'。

当遍历完后,记录了总的岛屿数量。

相关文章:

岛屿的数量(BFS)

给你一个由 1&#xff08;陆地&#xff09;和 0&#xff08;水&#xff09;组成的的二维网格&#xff0c;请你计算网格中)。 岛屿总是被水包围&#xff0c;并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。 此外&#xff0c;你可以假设该网格的四条边均被水包…...

线上JVM OOM问题,如何排查和解决?

今天咱们来聊聊让无数 Java 开发者头疼的 JVM OOM&#xff08;Out Of Memory&#xff0c;内存溢出&#xff09;问题。在面试中&#xff0c;OOM 问题也是面试官的“心头好”&#xff0c;因为它能直接考察你对 JVM 的理解&#xff0c;以及你在实际问题面前的排查和解决能力。 一…...

Linux的缓存I/O和无缓存IO

一、I/O缓存的背景 I/O缓存是指在内存里开辟一块区域&#xff0c;存放用来接收用户输入和用于计算机输出的数据&#xff0c;以减小系统开销和提高外设效率。linux对IO文件的操作分为不带缓存的IO操作和带缓存的IO操作&#xff08;标准IO操作&#xff09;。为什么存在C标准I/O库…...

【弹性计算】弹性裸金属服务器和神龙虚拟化(三):弹性裸金属技术

弹性裸金属服务器和神龙虚拟化&#xff08;三&#xff09;&#xff1a;弹性裸金属技术 1.弹性裸金属技术背景1.1 传统 KVM 虚拟化系统导致 CPU 计算特性损失1.2 传统 KVM 虚拟化系统导致资源争抢不可避免1.3 传统 KVM 虚拟化系统导致 I/O 性能瓶颈 2.弹性裸金属技术实现2.1 VPC…...

【MySQL】(2) 库的操作

SQL 关键字&#xff0c;大小写不敏感。 一、查询数据库 show databases; 注意加分号&#xff0c;才算一句结束。 二、创建数据库 {} 表示必选项&#xff0c;[] 表示可选项&#xff0c;| 表示任选其一。 示例&#xff1a;建议加上 if not exists 选项。 三、字符集编码和排序…...

Hyper-V -docker-vmware 三者的关系

1. Docker 正常运行&#xff0c;需要启动Hyper-V &#xff0c;打开 hypervisorlaunchtype 2.VMware 正常时&#xff0c;需要关闭Hyper-V &#xff0c;关闭 hypervisorlaunchtype 2.1资源管理器->CPU 里要开启虚拟化 2.2 服务-停掉HV服务 2.3 控制面板 不勾选 2.4 …...

IP-----双重发布

目录 6.双重发布 1.重发布的作用 2.部署条件 1.必须存在ASBR 2.种子度量值 3.重发布的规则 4.重发布的数量 5.重发布的场景 1.场景和规则 2.直连和静态 3.动态RIP 4.动态OSPF 5.更改开销值 6.重发布的问题1 7.重发布的问题2 1.流量 2.前缀列表 3.偏移列表 4…...

【新立电子】探索AI眼镜背后的黑科技,FPC如何赋能实时翻译与语音识别,点击了解未来沟通的新方式!

在全球化的今天&#xff0c;语言障碍成为人们沟通与交流的一大难题。AI眼镜作为一种新兴的智能设备&#xff0c;正在通过实时翻译与语音识别功能&#xff0c;打破语言壁垒&#xff0c;为人们提供无缝沟通的解决方案。FPC在AI眼镜中的应用&#xff0c;为实时翻译与语音识别功能的…...

LeetCode 热题 100_寻找两个正序数组的中位数(68_4_困难_C++)(二分查找)(先合并再挑选中位数;划分数组(二分查找))

LeetCode 热题 100_寻找两个正序数组的中位数&#xff08;68_4&#xff09; 题目描述&#xff1a;输入输出样例&#xff1a;题解&#xff1a;解题思路&#xff1a;思路一&#xff08;先合并再挑选中位数&#xff09;&#xff1a;思路二&#xff08;划分数组&#xff08;二分查找…...

Java多线程与高并发专题——深入ReentrantReadWriteLock

深入ReentrantReadWriteLock 读写锁出现原因 synchronized和ReentrantLock都是互斥锁。如果说有一个操作是读多写少的&#xff0c;还要保证线程安全的话。如果采用上述的两种互斥锁&#xff0c;效率方面很定是很低的。在这种情况下&#xff0c;咱们就可以使用ReentrantReadWr…...

【Python 语法】算法合集

查找二分查找代码大 O 表示法 广度优先搜索代码 狄克斯特拉算法 递归递归调用栈 分而治之&#xff08;divide and conquer&#xff0c;D&C&#xff09;贪心教室调度问题背包问题集合覆盖问题 动态规划背包问题旅游行程最优化 遇到问题时&#xff0c; 如果不确定该如何 高效…...

[STM32]从零开始的STM32 BSRR、BRR、ODR寄存器讲解

一、前言 学习STM32一阵子以后&#xff0c;相信大家对STM32 GPIO的控制也有一定的了解了。之前在STM32 LED的教程中也教了大家如何使用寄存器以及库函数控制STM32的引脚从而点亮一个LED&#xff0c;之前的寄存器只是作为一个引入&#xff0c;并没有深层次的讲解&#xff0c;在教…...

C++ ++++++++++

初始C 注释 变量 常量 关键字 标识符命名规则 数据类型 C规定在创建一个变量或者常量时&#xff0c;必须要指定出相应的数据类型&#xff0c;否则无法给变量分配内存 整型 sizeof关键字 浮点型&#xff08;实型&#xff09; 有效位数保留七位&#xff0c;带小数点。 这个是保…...

C# 牵手DeepSeek:打造本地AI超能力

一、引言 在人工智能飞速发展的当下&#xff0c;大语言模型如 DeepSeek 正掀起新一轮的技术变革浪潮&#xff0c;为自然语言处理领域带来了诸多创新应用。随着数据隐私和安全意识的提升&#xff0c;以及对模型部署灵活性的追求&#xff0c;本地部署 DeepSeek 成为众多开发者和…...

phpstudy安装教程dvwa靶场搭建教程

GitHub - digininja/DVWA: Damn Vulnerable Web Application (DVWA) Dvwa下载地址 Windows版phpstudy下载 - 小皮面板(phpstudy) 小皮下载地址 1选择windows 版本&#xff0c;点击立即下载 下载完成&#xff0c;进行解压&#xff0c;注意不要有中文路径 点击.exe文件进行安装…...

最新版本SpringAI接入DeepSeek大模型,并集成Mybatis

当时集成这个环境依赖冲突&#xff0c;搞了好久&#xff0c;分享一下依赖配置 <?xml version"1.0" encoding"UTF-8"?> <project xmlns"http://maven.apache.org/POM/4.0.0" xmlns:xsi"http://www.w3.org/2001/XMLSchema-instan…...

FastAPI 学习笔记

简介&#xff1a; FastAPI 是一个用于构建 API 的现代、快速&#xff08;高性能&#xff09;的 web 框架&#xff0c;使用 Python 并基于标准的 Python 类型提示。 关键特性: 快速&#xff1a;可与 NodeJS 和 Go 并肩的极高性能&#xff08;归功于 Starlette 和 Pydantic&…...

Elasticsearch:过滤 HNSW 搜索,快速模式

作者&#xff1a;来自 Elastic Benjamin Trent 通过我们的 ACORN-1 算法实现&#xff0c;探索我们对 Apache Lucene 中的 HNSW 向量搜索所做的改进。 多年来&#xff0c;Apache Lucene 和 Elasticsearch 一直支持使用 kNN 查询的过滤搜索&#xff0c;允许用户检索符合指定元数据…...

华为hcia——Datacom实验指南——STP工作基本原理及STP/RSTP基本功能配置

什么时候需要用到STP 在二层交换网络中&#xff0c;为了避免环路产生。 什么是STP STP生成树协议&#xff0c;是用来在冗余链路上消除二层环路。在众多交换机中&#xff0c;需要设置出一个根桥&#xff0c;其余的交换机称为非根桥&#xff0c;根桥是整个交换网络的核心&…...

Vue核心知识:动态路由实现完整方案

在Vue中实现动态路由&#xff0c;并结合后端接口和数据库表设计&#xff0c;是一个复杂的项目&#xff0c;需要多个技术栈和步骤的配合。以下将详细描述整个实现过程&#xff0c;包括数据库设计、后端接口设计、前端路由配置以及如何实现动态路由的功能。 目录 一、需求分析二…...

地震勘探——干扰波识别、井中地震时距曲线特点

目录 干扰波识别反射波地震勘探的干扰波 井中地震时距曲线特点 干扰波识别 有效波&#xff1a;可以用来解决所提出的地质任务的波&#xff1b;干扰波&#xff1a;所有妨碍辨认、追踪有效波的其他波。 地震勘探中&#xff0c;有效波和干扰波是相对的。例如&#xff0c;在反射波…...

如何在看板中体现优先级变化

在看板中有效体现优先级变化的关键措施包括&#xff1a;采用颜色或标签标识优先级、设置任务排序规则、使用独立的优先级列或泳道、结合自动化规则同步优先级变化、建立定期的优先级审查流程。其中&#xff0c;设置任务排序规则尤其重要&#xff0c;因为它让看板视觉上直观地体…...

高等数学(下)题型笔记(八)空间解析几何与向量代数

目录 0 前言 1 向量的点乘 1.1 基本公式 1.2 例题 2 向量的叉乘 2.1 基础知识 2.2 例题 3 空间平面方程 3.1 基础知识 3.2 例题 4 空间直线方程 4.1 基础知识 4.2 例题 5 旋转曲面及其方程 5.1 基础知识 5.2 例题 6 空间曲面的法线与切平面 6.1 基础知识 6.2…...

WordPress插件:AI多语言写作与智能配图、免费AI模型、SEO文章生成

厌倦手动写WordPress文章&#xff1f;AI自动生成&#xff0c;效率提升10倍&#xff01; 支持多语言、自动配图、定时发布&#xff0c;让内容创作更轻松&#xff01; AI内容生成 → 不想每天写文章&#xff1f;AI一键生成高质量内容&#xff01;多语言支持 → 跨境电商必备&am…...

Rust 异步编程

Rust 异步编程 引言 Rust 是一种系统编程语言,以其高性能、安全性以及零成本抽象而著称。在多核处理器成为主流的今天,异步编程成为了一种提高应用性能、优化资源利用的有效手段。本文将深入探讨 Rust 异步编程的核心概念、常用库以及最佳实践。 异步编程基础 什么是异步…...

MySQL 8.0 OCP 英文题库解析(十三)

Oracle 为庆祝 MySQL 30 周年&#xff0c;截止到 2025.07.31 之前。所有人均可以免费考取原价245美元的MySQL OCP 认证。 从今天开始&#xff0c;将英文题库免费公布出来&#xff0c;并进行解析&#xff0c;帮助大家在一个月之内轻松通过OCP认证。 本期公布试题111~120 试题1…...

如何应对敏捷转型中的团队阻力

应对敏捷转型中的团队阻力需要明确沟通敏捷转型目的、提升团队参与感、提供充分的培训与支持、逐步推进敏捷实践、建立清晰的奖励和反馈机制。其中&#xff0c;明确沟通敏捷转型目的尤为关键&#xff0c;团队成员只有清晰理解转型背后的原因和利益&#xff0c;才能降低对变化的…...

【Elasticsearch】Elasticsearch 在大数据生态圈的地位 实践经验

Elasticsearch 在大数据生态圈的地位 & 实践经验 1.Elasticsearch 的优势1.1 Elasticsearch 解决的核心问题1.1.1 传统方案的短板1.1.2 Elasticsearch 的解决方案 1.2 与大数据组件的对比优势1.3 关键优势技术支撑1.4 Elasticsearch 的竞品1.4.1 全文搜索领域1.4.2 日志分析…...

Java求职者面试指南:Spring、Spring Boot、Spring MVC与MyBatis技术解析

Java求职者面试指南&#xff1a;Spring、Spring Boot、Spring MVC与MyBatis技术解析 一、第一轮基础概念问题 1. Spring框架的核心容器是什么&#xff1f;它的作用是什么&#xff1f; Spring框架的核心容器是IoC&#xff08;控制反转&#xff09;容器。它的主要作用是管理对…...

上位机开发过程中的设计模式体会(1):工厂方法模式、单例模式和生成器模式

简介 在我的 QT/C 开发工作中&#xff0c;合理运用设计模式极大地提高了代码的可维护性和可扩展性。本文将分享我在实际项目中应用的三种创造型模式&#xff1a;工厂方法模式、单例模式和生成器模式。 1. 工厂模式 (Factory Pattern) 应用场景 在我的 QT 项目中曾经有一个需…...