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

岛屿数量问题

        给一个0 1矩阵,1代表是陆地,0代表海洋, 如果两个1相邻,那么这两个1属于同一个岛。我们只考虑上下左右为相邻。 岛屿问题: 相邻陆地可以组成一个岛屿(相邻:上下左右) 判断岛屿个数。

 C++ 解决方案

#include <iostream>
#include <vector>using namespace std;void dfs(vector<vector<int>>& grid, int i, int j) {if (i < 0 || i >= grid.size() || j < 0 || j >= grid[0].size() || grid[i][j] == 0) {return;}grid[i][j] = 0; // Mark the current cell as visited// Visit all four adjacent cellsdfs(grid, i - 1, j); // Updfs(grid, i + 1, j); // Downdfs(grid, i, j - 1); // Leftdfs(grid, i, j + 1); // Right
}int numIslands(vector<vector<int>>& grid) {int count = 0;for (int i = 0; i < grid.size(); ++i) {for (int j = 0; j < grid[0].size(); ++j) {if (grid[i][j] == 1) {++count;dfs(grid, i, j); // Start DFS from the current cell to mark all connected 1s as visited}}}return count;
}int main() {vector<vector<int>> grid = {{1, 1, 0, 0, 0},{1, 1, 0, 0, 1},{0, 0, 1, 0, 1},{0, 0, 0, 1, 1}};cout << "Number of islands: " << numIslands(grid) << endl;return 0;
}

Python 解决方案 

def dfs(grid, i, j):if i < 0 or i >= len(grid) or j < 0 or j >= len(grid[0]) or grid[i][j] == 0:returngrid[i][j] = 0  # Mark the current cell as visited# Visit all four adjacent cellsdfs(grid, i - 1, j)  # Updfs(grid, i + 1, j)  # Downdfs(grid, i, j - 1)  # Leftdfs(grid, i, j + 1)  # Rightdef num_islands(grid):count = 0for i in range(len(grid)):for j in range(len(grid[0])):if grid[i][j] == 1:count += 1dfs(grid, i, j)  # Start DFS from the current cell to mark all connected 1s as visitedreturn count# Example usage
grid = [[1, 1, 0, 0, 0],[1, 1, 0, 0, 1],[0, 0, 1, 0, 1],[0, 0, 0, 1, 1]
]print("Number of islands:", num_islands(grid))

解释

  1. 深度优先搜索(DFS)
    • dfs函数用于遍历所有与当前陆地相连的陆地,并将它们标记为已访问(即0)。
    • 每当遇到一个未访问的陆地(即值为1的单元格),我们增加岛屿计数,并调用dfs来标记所有相连的陆地。
  2. 遍历矩阵
    • numIslands函数遍历整个矩阵,每当遇到一个新的陆地时,调用dfs函数,并增加岛屿计数。

复杂度

  • 时间复杂度:O(M * N),其中M是矩阵的行数,N是矩阵的列数,因为我们需要遍历整个矩阵一次。
  • 空间复杂度:O(M * N)(在极端情况下,递归调用栈的深度可能达到这个级别),但由于DFS的深度通常较小,实际空间占用可能会更小。

相关文章:

岛屿数量问题

给一个0 1矩阵&#xff0c;1代表是陆地&#xff0c;0代表海洋&#xff0c; 如果两个1相邻&#xff0c;那么这两个1属于同一个岛。我们只考虑上下左右为相邻。 岛屿问题: 相邻陆地可以组成一个岛屿&#xff08;相邻:上下左右&#xff09; 判断岛屿个数。 C 解决方案 #include &…...

智能制造基础- TPM(全面生产维护)

TPM 前言一、TPM二、TPM实施步骤三、 消除主要问题3.1 实施指南3.2 如何进行“主要问题”的消除&#xff1f; 四、自主维护4.1 实施指南4.2 主要工作内容4.3 如何进行“自主维护“ 五、计划维护5.1 实施指南5.2 如何实施计划维护 六、TPM 适当的 设备 设计5.1 实施指南5.2 如何…...

C++学习笔记----11、模块、头文件及各种主题(一)---- 模板概览与类模板(4)

2.2.2、显式实例化 有危险存在于有些类模板成员函数的编译错误&#xff0c;在隐式实例化时没有注意到。未被使用的类模板成员函数也可能包含语法错误&#xff0c;因为它们不会被编译到。这会使得检测代码的语法错误很困难。可以强制编译器生成所有成员函数的代码&#xff0c;vi…...

【力扣热题100】[Java版] 刷题笔记-160. 相交链表

题目&#xff1a;160. 相交链表 给你两个单链表的头节点 headA 和 headB &#xff0c;请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点&#xff0c;返回 null 。 图示两个链表在节点 c1 开始相交&#xff1a; 题目数据 保证 整个链式结构中不存在环。 注意…...

多线程和线程同步复习

多线程和线程同步复习 进程线程区别创建线程线程退出线程回收全局写法传参写法 线程分离线程同步同步方式 互斥锁互斥锁进行线程同步 死锁读写锁api细说读写锁进行线程同步 条件变量生产者消费者案例问题解答加强版生产者消费者 总结信号量信号量实现生产者消费者同步-->一个…...

贝式计算的 AI4S 观察:使用机器学习对世界进行感知与推演,最大魅力在于横向扩展的有效性

「传统研究方法高度依赖于科研人员自身的特征和问题定义能力&#xff0c;通常采用小数据&#xff0c;在泛化能力和拓展能力上存疑。而 AI 研究方法则需要引入大规模、高质量数据&#xff0c;并采用机器学习进行特征抽取&#xff0c;这使得产生的科研结果在真实世界的问题中非常…...

容器化技术入门:Docker详解

&#x1f493; 博客主页&#xff1a;瑕疵的CSDN主页 &#x1f4dd; Gitee主页&#xff1a;瑕疵的gitee主页 ⏩ 文章专栏&#xff1a;《热点资讯》 容器化技术入门&#xff1a;Docker详解 容器化技术入门&#xff1a;Docker详解 容器化技术入门&#xff1a;Docker详解 引言 Doc…...

基于SSM(Spring + Spring MVC + MyBatis)框架的药房管理系统

基于SSM&#xff08;Spring Spring MVC MyBatis&#xff09;框架的药房管理系统 项目概述 功能需求 用户管理&#xff1a;管理员可以添加、删除、修改和查询用户信息。药品管理&#xff1a;支持对药品信息的增删改查操作&#xff0c;包括药品名称、价格、库存量等。供应商…...

在服务器里安装2个conda

1、安装新的conda 下载地址&#xff1a;Index of /anaconda/archive/ | 清华大学开源软件镜像站 | Tsinghua Open Source Mirror 本文选择&#xff1a;Anaconda3-2023.03-1-Linux-x86_64.sh 安装&#xff1a;Ubuntu安装Anaconda详细步骤&#xff08;Ubuntu22.04.1&#xff…...

web安全漏洞之ssrf入门

web安全漏洞之ssrf入门 1.什么是ssrf SSRF(Server Side Request Forgery,服务端请求伪造)是一种通过构造数据进而伪造成服务端发起请求的漏洞。因为请求是由服务器内部发起&#xff0c;所以一般情况下SSRF漏洞的目标往往是无法从外网访问的内系统。 SSRF漏洞形成的原理多是服务…...

《NoSQL 基础知识总结》

在当今的数据存储和管理领域&#xff0c;NoSQL 数据库正逐渐崭露头角&#xff0c;成为许多应用场景下的有力选择。今天&#xff0c;我们就来一起深入了解一下 NoSQL 的基础知识吧。 一、什么是 NoSQL&#xff1f; NoSQL&#xff0c;即 “Not Only SQL”&#xff0c;它是一种不…...

高校宿舍信息管理系统小程序

作者主页&#xff1a;编程千纸鹤 作者简介&#xff1a;Java领域优质创作者、CSDN博客专家 、CSDN内容合伙人、掘金特邀作者、阿里云博客专家、51CTO特邀作者、多年架构师设计经验、多年校企合作经验&#xff0c;被多个学校常年聘为校外企业导师&#xff0c;指导学生毕业设计并参…...

2.索引:MySQL 索引分类

MySQL中的索引是提高数据查询速度的重要工具&#xff0c;就像一本书的目录&#xff0c;可以帮助我们快速定位到所需的内容。选择适合的索引类型对数据库设计和性能优化至关重要。本文将详细介绍MySQL中常见的索引类型&#xff0c;并重点讲解聚集索引和二级索引的概念及应用。 1…...

sklearn红酒数据集分类器的构建和评估

实验目的&#xff1a; 1. 掌握sklearn科学数据包中决策树和神经网络分类器的构建 2. 掌握对不同分类器进行综合评估 实验数据&#xff1a; 红酒数据集 红酒数据集利用红酒的化学特征来描述三种不同类型的葡萄酒。 实验内容与要求&#xff1a; 解压文件得到wine数据。利用pa…...

【IC验证面试常问-4】

IC验证面试常问-4 1.11 struct和union的异同1.13 rose 和posedge 的区别&#xff1f;1.14 semaphore的用处是什么&#xff1f;1.15 类中的静态方法使用注意事项有哪些&#xff1f;1.16 initial和final的区别&#xff1f; s t o p , stop, stop,finish的区别1.17 logic,wire和re…...

【数据集】【YOLO】【目标检测】交通事故识别数据集 8939 张,YOLO道路事故目标检测实战训练教程!

数据集介绍 【数据集】道路事故识别数据集 8939 张&#xff0c;目标检测&#xff0c;包含YOLO/VOC格式标注。数据集中包含2种分类&#xff1a;{0: accident, 1: non-accident}。数据集来自国内外图片网站和视频截图。检测范围道路事故检测、监控视角检测、无人机视角检测、等&…...

书生浦语第四期基础岛L1G4000-InternLM + LlamaIndex RAG 实践

文章目录 一、任务要求11.首先创建虚拟环境2. 安装依赖3. 下载 Sentence Transformer 模型4.下载 NLTK 相关资源5. 是否使用 LlamaIndex 前后对比6. LlamaIndex web7. LlamaIndex本地部署InternLM实践 一、任务要求1 任务要求1&#xff08;必做&#xff0c;参考readme_api.md&…...

基于ViT的无监督工业异常检测模型汇总

基于ViT的无监督工业异常检测模型汇总 论文1&#xff1a;VT-ADL: A Vision Transformer Network for Image Anomaly Detection and Localization&#xff08;2021&#xff09;1.1 主要思想1.2 系统框架 论文2&#xff1a;Inpainting Transformer for Anomaly Detection&#xf…...

数据库管理-第258期 23ai:Oracle Data Redaction(20241104)

数据库管理258期 2024-11-04 数据库管理-第258期 23ai&#xff1a;Oracle Data Redaction&#xff08;20241104&#xff09;1 简介2 应用场景与有点3 多租户环境4 特性与能力4.1 全数据编校4.2 部分编校4.3 正则表达式编校4.4 随机编校4.5 空值编校4.6 无编校4.7 不同数据类型上…...

运放进阶篇-多种波形可调信号发生器-产生方波-三角波-正弦波

引言&#xff1a;前几节我们已经说到硬件相关基础的电路&#xff0c;以及对于运放也讲到了初步的理解&#xff0c;特别是比较器的部分&#xff0c;但是放大器的部分我们对此并没有阐述&#xff0c;在这里通过实例进行理论结合实践的学习。而运放真正的核心&#xff0c;其实就是…...

大语言模型如何处理长文本?常用文本分割技术详解

为什么需要文本分割? 引言:为什么需要文本分割?一、基础文本分割方法1. 按段落分割(Paragraph Splitting)2. 按句子分割(Sentence Splitting)二、高级文本分割策略3. 重叠分割(Sliding Window)4. 递归分割(Recursive Splitting)三、生产级工具推荐5. 使用LangChain的…...

质量体系的重要

质量体系是为确保产品、服务或过程质量满足规定要求&#xff0c;由相互关联的要素构成的有机整体。其核心内容可归纳为以下五个方面&#xff1a; &#x1f3db;️ 一、组织架构与职责 质量体系明确组织内各部门、岗位的职责与权限&#xff0c;形成层级清晰的管理网络&#xf…...

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

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

JDK 17 新特性

#JDK 17 新特性 /**************** 文本块 *****************/ python/scala中早就支持&#xff0c;不稀奇 String json “”" { “name”: “Java”, “version”: 17 } “”"; /**************** Switch 语句 -> 表达式 *****************/ 挺好的&#xff…...

ip子接口配置及删除

配置永久生效的子接口&#xff0c;2个IP 都可以登录你这一台服务器。重启不失效。 永久的 [应用] vi /etc/sysconfig/network-scripts/ifcfg-eth0修改文件内内容 TYPE"Ethernet" BOOTPROTO"none" NAME"eth0" DEVICE"eth0" ONBOOT&q…...

#Uniapp篇:chrome调试unapp适配

chrome调试设备----使用Android模拟机开发调试移动端页面 Chrome://inspect/#devices MuMu模拟器Edge浏览器&#xff1a;Android原生APP嵌入的H5页面元素定位 chrome://inspect/#devices uniapp单位适配 根路径下 postcss.config.js 需要装这些插件 “postcss”: “^8.5.…...

PAN/FPN

import torch import torch.nn as nn import torch.nn.functional as F import mathclass LowResQueryHighResKVAttention(nn.Module):"""方案 1: 低分辨率特征 (Query) 查询高分辨率特征 (Key, Value).输出分辨率与低分辨率输入相同。"""def __…...

C++课设:简易日历程序(支持传统节假日 + 二十四节气 + 个人纪念日管理)

名人说:路漫漫其修远兮,吾将上下而求索。—— 屈原《离骚》 创作者:Code_流苏(CSDN)(一个喜欢古诗词和编程的Coder😊) 专栏介绍:《编程项目实战》 目录 一、为什么要开发一个日历程序?1. 深入理解时间算法2. 练习面向对象设计3. 学习数据结构应用二、核心算法深度解析…...

STM32HAL库USART源代码解析及应用

STM32HAL库USART源代码解析 前言STM32CubeIDE配置串口USART和UART的选择使用模式参数设置GPIO配置DMA配置中断配置硬件流控制使能生成代码解析和使用方法串口初始化__UART_HandleTypeDef结构体浅析HAL库代码实际使用方法使用轮询方式发送使用轮询方式接收使用中断方式发送使用中…...

第7篇:中间件全链路监控与 SQL 性能分析实践

7.1 章节导读 在构建数据库中间件的过程中&#xff0c;可观测性 和 性能分析 是保障系统稳定性与可维护性的核心能力。 特别是在复杂分布式场景中&#xff0c;必须做到&#xff1a; &#x1f50d; 追踪每一条 SQL 的生命周期&#xff08;从入口到数据库执行&#xff09;&#…...