岛屿数量问题
给一个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))
解释
- 深度优先搜索(DFS):
dfs函数用于遍历所有与当前陆地相连的陆地,并将它们标记为已访问(即0)。- 每当遇到一个未访问的陆地(即值为1的单元格),我们增加岛屿计数,并调用
dfs来标记所有相连的陆地。
- 遍历矩阵:
numIslands函数遍历整个矩阵,每当遇到一个新的陆地时,调用dfs函数,并增加岛屿计数。
复杂度
- 时间复杂度:O(M * N),其中M是矩阵的行数,N是矩阵的列数,因为我们需要遍历整个矩阵一次。
- 空间复杂度:O(M * N)(在极端情况下,递归调用栈的深度可能达到这个级别),但由于DFS的深度通常较小,实际空间占用可能会更小。
相关文章:
岛屿数量问题
给一个0 1矩阵,1代表是陆地,0代表海洋, 如果两个1相邻,那么这两个1属于同一个岛。我们只考虑上下左右为相邻。 岛屿问题: 相邻陆地可以组成一个岛屿(相邻:上下左右) 判断岛屿个数。 C 解决方案 #include &…...
智能制造基础- TPM(全面生产维护)
TPM 前言一、TPM二、TPM实施步骤三、 消除主要问题3.1 实施指南3.2 如何进行“主要问题”的消除? 四、自主维护4.1 实施指南4.2 主要工作内容4.3 如何进行“自主维护“ 五、计划维护5.1 实施指南5.2 如何实施计划维护 六、TPM 适当的 设备 设计5.1 实施指南5.2 如何…...
C++学习笔记----11、模块、头文件及各种主题(一)---- 模板概览与类模板(4)
2.2.2、显式实例化 有危险存在于有些类模板成员函数的编译错误,在隐式实例化时没有注意到。未被使用的类模板成员函数也可能包含语法错误,因为它们不会被编译到。这会使得检测代码的语法错误很困难。可以强制编译器生成所有成员函数的代码,vi…...
【力扣热题100】[Java版] 刷题笔记-160. 相交链表
题目:160. 相交链表 给你两个单链表的头节点 headA 和 headB ,请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点,返回 null 。 图示两个链表在节点 c1 开始相交: 题目数据 保证 整个链式结构中不存在环。 注意…...
多线程和线程同步复习
多线程和线程同步复习 进程线程区别创建线程线程退出线程回收全局写法传参写法 线程分离线程同步同步方式 互斥锁互斥锁进行线程同步 死锁读写锁api细说读写锁进行线程同步 条件变量生产者消费者案例问题解答加强版生产者消费者 总结信号量信号量实现生产者消费者同步-->一个…...
贝式计算的 AI4S 观察:使用机器学习对世界进行感知与推演,最大魅力在于横向扩展的有效性
「传统研究方法高度依赖于科研人员自身的特征和问题定义能力,通常采用小数据,在泛化能力和拓展能力上存疑。而 AI 研究方法则需要引入大规模、高质量数据,并采用机器学习进行特征抽取,这使得产生的科研结果在真实世界的问题中非常…...
容器化技术入门:Docker详解
💓 博客主页:瑕疵的CSDN主页 📝 Gitee主页:瑕疵的gitee主页 ⏩ 文章专栏:《热点资讯》 容器化技术入门:Docker详解 容器化技术入门:Docker详解 容器化技术入门:Docker详解 引言 Doc…...
基于SSM(Spring + Spring MVC + MyBatis)框架的药房管理系统
基于SSM(Spring Spring MVC MyBatis)框架的药房管理系统 项目概述 功能需求 用户管理:管理员可以添加、删除、修改和查询用户信息。药品管理:支持对药品信息的增删改查操作,包括药品名称、价格、库存量等。供应商…...
在服务器里安装2个conda
1、安装新的conda 下载地址:Index of /anaconda/archive/ | 清华大学开源软件镜像站 | Tsinghua Open Source Mirror 本文选择:Anaconda3-2023.03-1-Linux-x86_64.sh 安装:Ubuntu安装Anaconda详细步骤(Ubuntu22.04.1ÿ…...
web安全漏洞之ssrf入门
web安全漏洞之ssrf入门 1.什么是ssrf SSRF(Server Side Request Forgery,服务端请求伪造)是一种通过构造数据进而伪造成服务端发起请求的漏洞。因为请求是由服务器内部发起,所以一般情况下SSRF漏洞的目标往往是无法从外网访问的内系统。 SSRF漏洞形成的原理多是服务…...
《NoSQL 基础知识总结》
在当今的数据存储和管理领域,NoSQL 数据库正逐渐崭露头角,成为许多应用场景下的有力选择。今天,我们就来一起深入了解一下 NoSQL 的基础知识吧。 一、什么是 NoSQL? NoSQL,即 “Not Only SQL”,它是一种不…...
高校宿舍信息管理系统小程序
作者主页:编程千纸鹤 作者简介:Java领域优质创作者、CSDN博客专家 、CSDN内容合伙人、掘金特邀作者、阿里云博客专家、51CTO特邀作者、多年架构师设计经验、多年校企合作经验,被多个学校常年聘为校外企业导师,指导学生毕业设计并参…...
2.索引:MySQL 索引分类
MySQL中的索引是提高数据查询速度的重要工具,就像一本书的目录,可以帮助我们快速定位到所需的内容。选择适合的索引类型对数据库设计和性能优化至关重要。本文将详细介绍MySQL中常见的索引类型,并重点讲解聚集索引和二级索引的概念及应用。 1…...
sklearn红酒数据集分类器的构建和评估
实验目的: 1. 掌握sklearn科学数据包中决策树和神经网络分类器的构建 2. 掌握对不同分类器进行综合评估 实验数据: 红酒数据集 红酒数据集利用红酒的化学特征来描述三种不同类型的葡萄酒。 实验内容与要求: 解压文件得到wine数据。利用pa…...
【IC验证面试常问-4】
IC验证面试常问-4 1.11 struct和union的异同1.13 rose 和posedge 的区别?1.14 semaphore的用处是什么?1.15 类中的静态方法使用注意事项有哪些?1.16 initial和final的区别? s t o p , stop, stop,finish的区别1.17 logic,wire和re…...
【数据集】【YOLO】【目标检测】交通事故识别数据集 8939 张,YOLO道路事故目标检测实战训练教程!
数据集介绍 【数据集】道路事故识别数据集 8939 张,目标检测,包含YOLO/VOC格式标注。数据集中包含2种分类:{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(必做,参考readme_api.md&…...
基于ViT的无监督工业异常检测模型汇总
基于ViT的无监督工业异常检测模型汇总 论文1:VT-ADL: A Vision Transformer Network for Image Anomaly Detection and Localization(2021)1.1 主要思想1.2 系统框架 论文2:Inpainting Transformer for Anomaly Detection…...
数据库管理-第258期 23ai:Oracle Data Redaction(20241104)
数据库管理258期 2024-11-04 数据库管理-第258期 23ai:Oracle Data Redaction(20241104)1 简介2 应用场景与有点3 多租户环境4 特性与能力4.1 全数据编校4.2 部分编校4.3 正则表达式编校4.4 随机编校4.5 空值编校4.6 无编校4.7 不同数据类型上…...
运放进阶篇-多种波形可调信号发生器-产生方波-三角波-正弦波
引言:前几节我们已经说到硬件相关基础的电路,以及对于运放也讲到了初步的理解,特别是比较器的部分,但是放大器的部分我们对此并没有阐述,在这里通过实例进行理论结合实践的学习。而运放真正的核心,其实就是…...
wordpress后台更新后 前端没变化的解决方法
使用siteground主机的wordpress网站,会出现更新了网站内容和修改了php模板文件、js文件、css文件、图片文件后,网站没有变化的情况。 不熟悉siteground主机的新手,遇到这个问题,就很抓狂,明明是哪都没操作错误&#x…...
应用升级/灾备测试时使用guarantee 闪回点迅速回退
1.场景 应用要升级,当升级失败时,数据库回退到升级前. 要测试系统,测试完成后,数据库要回退到测试前。 相对于RMAN恢复需要很长时间, 数据库闪回只需要几分钟。 2.技术实现 数据库设置 2个db_recovery参数 创建guarantee闪回点,不需要开启数据库闪回。…...
树莓派超全系列教程文档--(62)使用rpicam-app通过网络流式传输视频
使用rpicam-app通过网络流式传输视频 使用 rpicam-app 通过网络流式传输视频UDPTCPRTSPlibavGStreamerRTPlibcamerasrc GStreamer 元素 文章来源: http://raspberry.dns8844.cn/documentation 原文网址 使用 rpicam-app 通过网络流式传输视频 本节介绍来自 rpica…...
3.3.1_1 检错编码(奇偶校验码)
从这节课开始,我们会探讨数据链路层的差错控制功能,差错控制功能的主要目标是要发现并且解决一个帧内部的位错误,我们需要使用特殊的编码技术去发现帧内部的位错误,当我们发现位错误之后,通常来说有两种解决方案。第一…...
【Redis技术进阶之路】「原理分析系列开篇」分析客户端和服务端网络诵信交互实现(服务端执行命令请求的过程 - 初始化服务器)
服务端执行命令请求的过程 【专栏简介】【技术大纲】【专栏目标】【目标人群】1. Redis爱好者与社区成员2. 后端开发和系统架构师3. 计算机专业的本科生及研究生 初始化服务器1. 初始化服务器状态结构初始化RedisServer变量 2. 加载相关系统配置和用户配置参数定制化配置参数案…...
Opencv中的addweighted函数
一.addweighted函数作用 addweighted()是OpenCV库中用于图像处理的函数,主要功能是将两个输入图像(尺寸和类型相同)按照指定的权重进行加权叠加(图像融合),并添加一个标量值&#x…...
CocosCreator 之 JavaScript/TypeScript和Java的相互交互
引擎版本: 3.8.1 语言: JavaScript/TypeScript、C、Java 环境:Window 参考:Java原生反射机制 您好,我是鹤九日! 回顾 在上篇文章中:CocosCreator Android项目接入UnityAds 广告SDK。 我们简单讲…...
Redis数据倾斜问题解决
Redis 数据倾斜问题解析与解决方案 什么是 Redis 数据倾斜 Redis 数据倾斜指的是在 Redis 集群中,部分节点存储的数据量或访问量远高于其他节点,导致这些节点负载过高,影响整体性能。 数据倾斜的主要表现 部分节点内存使用率远高于其他节…...
【笔记】WSL 中 Rust 安装与测试完整记录
#工作记录 WSL 中 Rust 安装与测试完整记录 1. 运行环境 系统:Ubuntu 24.04 LTS (WSL2)架构:x86_64 (GNU/Linux)Rust 版本:rustc 1.87.0 (2025-05-09)Cargo 版本:cargo 1.87.0 (2025-05-06) 2. 安装 Rust 2.1 使用 Rust 官方安…...
在Mathematica中实现Newton-Raphson迭代的收敛时间算法(一般三次多项式)
考察一般的三次多项式,以r为参数: p[z_, r_] : z^3 (r - 1) z - r; roots[r_] : z /. Solve[p[z, r] 0, z]; 此多项式的根为: 尽管看起来这个多项式是特殊的,其实一般的三次多项式都是可以通过线性变换化为这个形式…...
