Leetcode 1254 Number of Closed Islands + Leetcode 1020 Number of Enclaves
Leetcode 1254
题意
给定一个m*n的矩阵含有0和1,1代表水,0代表陆地,岛屿是陆地的集合,如果一个岛屿和四个方向的边界相连,则不算封闭岛屿。求有多少个封闭的岛屿。
题目链接
https://leetcode.com/problems/number-of-closed-islands/
思路
从边界上的0开始用dfs向四个方向遍历,把这些0形成的岛屿都遍历完成,这样就能排除和边界相连的岛屿。然后再从没有遍历过的0开始用dfs向四个方向遍历,并且计数。这些岛屿就是封闭的岛屿(参考number of islands)
题解
class Solution {
public:int m;int n;int closedIsland(vector<vector<int>>& grid) {m = grid.size();n = grid[0].size();int res = 0;vector<vector<bool>> vis(m, vector<bool>(n, false));for(int i = 0; i < m; i++) {if(grid[i][0] == 0 && !vis[i][0]) {dfs(grid, vis, i, 0);}if(grid[i][n-1] == 0 && !vis[i][n-1]) {dfs(grid, vis, i, n-1);}}for(int i = 0; i < n; i++) {if(grid[0][i] == 0 && !vis[0][i]) {dfs(grid, vis, 0, i);}if(grid[m-1][i] == 0 && !vis[m-1][i]) {dfs(grid, vis, m-1, i);}}for(int i = 0; i < m; i++) {for(int j = 0; j < n; j++) {if(grid[i][j] == 0 && !vis[i][j]) {dfs(grid, vis, i, j);res++;}}}return res;}void dfs(vector<vector<int>>& grid, vector<vector<bool>>& vis, int x, int y) {vis[x][y] = true;int dk[] = {-1, 0, 1, 0, -1};for(int i = 0; i < 4; i++) {int dx = x + dk[i];int dy = y + dk[i+1];if(dx >= 0 && dx < m && dy >= 0 && dy < n && !vis[dx][dy] && grid[dx][dy] == 0) {dfs(grid, vis, dx, dy);}}}
};
时间复杂度: O ( m n ) O(mn) O(mn) m为给定矩阵的长度,n为给定矩阵的宽度
空间复杂度: O ( m n ) O(mn) O(mn) m为给定矩阵的长度,n为给定矩阵的宽度
Leetcode 1020
思路
和Leetcode 1254一样,只是换壳的Number of Closed Islands + Max Area of Island,不赘述了。
题解
class Solution {
public:int m;int n;int numEnclaves(vector<vector<int>>& grid) {m = grid.size();n = grid[0].size();int res = 0;vector<vector<bool>> vis(m, vector<bool>(n, false));for(int i = 0; i < m; i++) {if(grid[i][0] == 1 && !vis[i][0]) {dfs(grid, vis, i, 0);}if(grid[i][n-1] == 1 && !vis[i][n-1]) {dfs(grid, vis, i, n-1);}}for(int i = 0; i < n; i++) {if(grid[0][i] == 1 && !vis[0][i]) {dfs(grid, vis, 0, i);}if(grid[m-1][i] == 1 && !vis[m-1][i]) {dfs(grid, vis, m-1, i);}}for(int i = 0; i < m; i++) {for(int j = 0; j < n; j++) {if(grid[i][j] == 1 && !vis[i][j]) {res += dfs(grid, vis, i, j);}}}return res;}int dfs(vector<vector<int>>& grid, vector<vector<bool>>& vis, int x, int y) {vis[x][y] = true;int area = 1;int dk[] = {-1, 0, 1, 0, -1};for(int i = 0; i < 4; i++) {int dx = x + dk[i];int dy = y + dk[i+1];if(dx >= 0 && dx < m && dy >= 0 && dy < n && grid[dx][dy] == 1 && !vis[dx][dy]) {area += dfs(grid, vis, dx, dy);}}return area;}
};
时间复杂度: O ( m n ) O(mn) O(mn) m为给定矩阵的长度,n为给定矩阵的宽度
空间复杂度: O ( m n ) O(mn) O(mn) m为给定矩阵的长度,n为给定矩阵的宽度
相关文章:
Leetcode 1254 Number of Closed Islands + Leetcode 1020 Number of Enclaves
Leetcode 1254 题意 给定一个m*n的矩阵含有0和1,1代表水,0代表陆地,岛屿是陆地的集合,如果一个岛屿和四个方向的边界相连,则不算封闭岛屿。求有多少个封闭的岛屿。 题目链接 https://leetcode.com/problems/number…...
Junit4单元测试快速上手
文章目录 POM依赖引入业务层测试代码Web层测试代码生成测试类文件 在工作中我用的最多的单元测试框架是Junit4。通常在写DAO、Service、Web层代码的时候都会进行单元测试,方便后续编码,前端甩锅。 POM依赖引入 <dependency><groupId>org.spr…...
U盘提示格式化?原因、恢复方案与预防措施全解析
一、U盘提示格式化现象概述 在日常使用U盘的过程中,我们有时会遇到一个令人头疼的问题——U盘插入电脑后,系统却弹出一个提示框,告知我们U盘需要格式化才能访问。这个提示往往伴随着数据的潜在丢失风险,让我们不禁为之心焦。U盘提…...
HTML——13.超链接
<!DOCTYPE html> <html><head><meta charset"UTF-8"><title>超链接</title></head><body><!--超链接:从一个网页链接到另一个网页--><!--语法:<a href"淘宝网链接的地址"> 淘宝…...
vue中的设计模式
vue中使用了哪些设计模式 1. 观察者模式(Observer Pattern) 应用场景:Vue 的响应式系统核心就是观察者模式。 实现方式:通过 Object.defineProperty 或 Proxy 监听数据变化,当数据发生变化时,通知依赖的视…...
利用python将图片转换为pdf格式的多种方法,实现批量转换,内置模板代码,全网最全,超详细!!!
文章目录 前言1、img2pdf库的使用1.1 安装img2pdf库1.2 案例演示(模板代码) 2、Pillow库的使用2.1 pillow库的安装2.2 案例演示(模板代码) 3、PyMuPDF库的使用3.1 安装pymupdf库3.2 案例演示(模板代码)3.3 …...
tcpdump的常见方法
详解tcpdump的使用方法:网络数据包捕获与分析 tcpdump是一个功能强大的命令行工具,用于捕获和分析通过网络接口传输的数据包。它广泛应用于网络故障诊断、网络安全监控和协议分析等领域。本文将详细介绍tcpdump的使用方法,包括安装、基本命令…...
工控主板ESM7000/6800E支持远程桌面控制
英创公司ESM7000 是面向工业领域的双核 Cortex-A7 高性能嵌入式主板,ESM6800E则为单核Cortex-A7 高性价比嵌入式主板,ESM7000、ESM6800E都是公司的成熟产品,已广泛应用于工业很多领域。ESM7000/6800E板卡中Linux系统配置为linux-4.9.11内核、…...
wamp php7.4 运行dm8
背景 1、电脑安装了dm8,具体参照官网dm8安装 2、安装好了wamp,我当前的php版本切换成了7.4的,我wamp的安装路径d:\wamp64\ 操作 3、查看phpinfo,如果Thread Safet为enabled,则选择pdo74_dm.dll,否则选择…...
HTML5 进度条(Progress Bar)详解
HTML5 进度条(Progress Bar)详解 进度条是用于显示任务完成进度的控件,常用于加载、上传或下载等操作。HTML5提供了原生的<progress>元素,使得创建进度条变得简单和直观。 1. 基本用法 <progress>元素的基本语法如…...
LabVIEW开发中常见硬件通讯接口快速识别
在 LabVIEW 开发中,与硬件进行通讯是实现数据采集与控制的重要环节。准确判断通讯接口类型和协议,可以提高开发效率,减少调试时间。本文结合 LabVIEW 的实际应用,详细介绍如何识别和判断常见硬件通讯接口的定义,并提供…...
高频 SQL 50 题(基础版)_1068. 产品销售分析 I
销售表 Sales: (sale_id, year) 是销售表 Sales 的主键(具有唯一值的列的组合)。 product_id 是关联到产品表 Product 的外键(reference 列)。 该表的每一行显示 product_id 在某一年的销售情况。 注意: price 表示每…...
笔记:一次mysql主从复制延迟高的处理尝试
背景 mysql 5.7 主从复制 主库进行了一次灌数,导致多个大事务产生,主从延迟下不去,经确认该表最终truncate,并且该表仅有insert和select操作,故对该表的事务进行跳过,直到同步至truncate 跳过事务需谨慎&…...
基于C语言的卡丁车管理系统【控制台应用程序】
注意:需要提前创建对应的.dat文件 本项目实现了数据的永久存储,有用户的注册、登录。 管理员对卡丁车的管理、查看预约用户、修改帐户权限。 用户对个人信息的管理、查看并预约卡丁车、卡丁车维修上报。 维修员对卡丁车的维修状态上报、个人信息管理。 …...
Docker 搭建 Gogs
Docker 搭建 Gogs 准备工作 先准备配置目录和持久化目录,举个栗子:mkdir -p /opt/module/gogs/{data,backup} 拉取官方Gogs镜像 # 拉取 gogs:0.13 docker pull gogs/gogs:0.13 # 拉取最新版 gogs 镜像 docker pull gogs/gogs启动一个临时容器【通过创…...
PostgreSQL的备份方式
PostgreSQL 提供多种方式进行备份,适用于不同需求的场景。常用的备份方法如下: 1. 逻辑备份(pg_dump 和 pg_dumpall) 1.1 使用 pg_dump 备份单个数据库 pg_dump 是 PostgreSQL 内置的逻辑备份工具,可以将数据库导出为…...
Springboot 3项目整合Knife4j接口文档(接口分组详细教程)
文章目录 前言一、Spring Boot 3.0整合Knife4j二、OpenApi 3注解的使用规范三、使用步骤 1.Spring Boot 3.0项目中使用knife4j2.在application.yml中添加knife4j相关配置3.设置WebMvc相关配置(解决封装统一异常处理后doc.html无法打开的问题)4.创建Knif…...
深入解析 Conda 安装的默认依赖包及其作用:conda create安装了哪些包(中英双语)
深入解析 Conda 安装的默认依赖包及其作用 当我们使用 Conda 创建新环境时,例如执行命令: conda create -n olmes python3.10Conda 会自动为我们安装一系列基础依赖包,保证 Python 环境能够正常运行。这些包不仅是我们开发的基础工具&#…...
Redis核心技术知识点全集
Redis数据结构和常用命令 1. String字符串2. Hash哈希3. List列表4. Set集合5. Sorted Set有序集合6. Redis常用命令参考Redis事务机制...
【Unity3D】ECS入门学习(九)SystemBase
SystemBase:支持主线程或多线程执行筛选实体任务。 主要介绍是内部成员:Entities的各种筛选方法,其内部成员还有EntityManager ForEach方法筛选,传递一个有参委托函数进去,参数ref xxx组件类(可填多个&…...
Fay-UE5数字人系统架构深度解析:基于Unreal Engine 5的实时交互虚拟人技术实现
Fay-UE5数字人系统架构深度解析:基于Unreal Engine 5的实时交互虚拟人技术实现 【免费下载链接】fay-ue5 项目地址: https://gitcode.com/gh_mirrors/fa/fay-ue5 Fay-UE5是一个基于Unreal Engine 5引擎构建的高性能数字人解决方案,通过深度集成F…...
4个维度掌控企业驱动管理:DriverStore Explorer从诊断到优化的全流程方案
4个维度掌控企业驱动管理:DriverStore Explorer从诊断到优化的全流程方案 【免费下载链接】DriverStoreExplorer Driver Store Explorer 项目地址: https://gitcode.com/gh_mirrors/dr/DriverStoreExplorer 一、问题诊断:企业环境中的驱动管理痛点…...
CAM++说话人识别系统优化指南:调整相似度阈值提升准确率
CAM说话人识别系统优化指南:调整相似度阈值提升准确率 1. 相似度阈值的基础认知 1.1 什么是相似度阈值 在CAM说话人识别系统中,相似度阈值是一个关键参数,用于判断两段语音是否来自同一说话人。系统会计算两段语音特征的余弦相似度&#x…...
NaViL-9B多场景应用:医疗报告图解、工业缺陷识别、文档智能审阅
NaViL-9B多场景应用:医疗报告图解、工业缺陷识别、文档智能审阅 1. 平台简介 NaViL-9B是上海人工智能实验室研发的原生多模态大语言模型,具备强大的文本理解和图像分析能力。不同于传统单一模态模型,NaViL-9B能够同时处理纯文本问答和图片理…...
Nvidia、谷歌、MiniMax、阶跃星辰等60+实战专家齐聚,2026 奇点智能技术大会最新最全日程发布!
责编 | 梦依丹出品 | CSDN(ID:CSDNnews)昨晚,AI 圈彻夜无眠。Claude Code 51 万行源码泄露引发众多开发者连夜 Fork 拆解,OpenAI 创纪录的 1220 亿美元天价融资……这一系列令人眩晕的数字和事件,折射出一个…...
选AI面试软件,为何一定要看中防作弊、可解释、全场景?
想象一下:你花了半个月筛选简历,终于确定了100个面试候选人,却发现一半人在用AI生成器写答案、用提词器念稿,甚至找人替考;好不容易拿到AI评分,却看不懂分数怎么来的,候选人质疑时你根本没法解释…...
JAVA重点基础、进阶知识及易错点总结(13)File 类 + 路径操作
🚀 Java 巩固进阶 第13天 主题:File 类 路径操作 —— IO 体系的第一块基石📅 进度概览:从今天起,我们正式进入 Java IO 流体系。第一站:java.io.File。 💡 核心价值: 文件操作基石…...
告别黑盒:用Python拆解OpenBCI GUI的滤波与可视化模块(附完整代码)
从零构建Python版OpenBCI数据处理引擎:解码脑电信号处理全流程 在脑机接口开发领域,OpenBCI以其开源特性和专业级性能成为众多研究者的首选硬件平台。然而,其官方GUI虽然功能完善,却像一座封闭的城堡——我们能看到华丽的城墙&…...
千问3.5-9B提示词工程:优化OpenClaw任务拆解质量
千问3.5-9B提示词工程:优化OpenClaw任务拆解质量 1. 为什么需要优化提示词 去年冬天第一次用OpenClaw自动整理会议纪要时,我被它的"耿直"气笑了——让它"提取关键结论",结果给我返回了整段录音的文字版,连&…...
内网渗透初探保姆级教程!零基础小白从零入门,轻松学会内网渗透核心知识
0x01 基础知识 内网渗透,从字面上理解便是对目标服务器所在内网进行渗透并最终获取域控权限的一种渗透。内网渗透的前提需要获取一个Webshell,可以是低权限的Webshell,因为可以通过提权获取高权限。 在进行内网渗透之前需要了解一个概念&…...
