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

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&#xff0c;1代表水&#xff0c;0代表陆地&#xff0c;岛屿是陆地的集合&#xff0c;如果一个岛屿和四个方向的边界相连&#xff0c;则不算封闭岛屿。求有多少个封闭的岛屿。 题目链接 https://leetcode.com/problems/number…...

Junit4单元测试快速上手

文章目录 POM依赖引入业务层测试代码Web层测试代码生成测试类文件 在工作中我用的最多的单元测试框架是Junit4。通常在写DAO、Service、Web层代码的时候都会进行单元测试&#xff0c;方便后续编码&#xff0c;前端甩锅。 POM依赖引入 <dependency><groupId>org.spr…...

U盘提示格式化?原因、恢复方案与预防措施全解析

一、U盘提示格式化现象概述 在日常使用U盘的过程中&#xff0c;我们有时会遇到一个令人头疼的问题——U盘插入电脑后&#xff0c;系统却弹出一个提示框&#xff0c;告知我们U盘需要格式化才能访问。这个提示往往伴随着数据的潜在丢失风险&#xff0c;让我们不禁为之心焦。U盘提…...

HTML——13.超链接

<!DOCTYPE html> <html><head><meta charset"UTF-8"><title>超链接</title></head><body><!--超链接:从一个网页链接到另一个网页--><!--语法&#xff1a;<a href"淘宝网链接的地址"> 淘宝…...

vue中的设计模式

vue中使用了哪些设计模式 1. 观察者模式&#xff08;Observer Pattern&#xff09; 应用场景&#xff1a;Vue 的响应式系统核心就是观察者模式。 实现方式&#xff1a;通过 Object.defineProperty 或 Proxy 监听数据变化&#xff0c;当数据发生变化时&#xff0c;通知依赖的视…...

利用python将图片转换为pdf格式的多种方法,实现批量转换,内置模板代码,全网最全,超详细!!!

文章目录 前言1、img2pdf库的使用1.1 安装img2pdf库1.2 案例演示&#xff08;模板代码&#xff09; 2、Pillow库的使用2.1 pillow库的安装2.2 案例演示&#xff08;模板代码&#xff09; 3、PyMuPDF库的使用3.1 安装pymupdf库3.2 案例演示&#xff08;模板代码&#xff09;3.3 …...

tcpdump的常见方法

详解tcpdump的使用方法&#xff1a;网络数据包捕获与分析 tcpdump是一个功能强大的命令行工具&#xff0c;用于捕获和分析通过网络接口传输的数据包。它广泛应用于网络故障诊断、网络安全监控和协议分析等领域。本文将详细介绍tcpdump的使用方法&#xff0c;包括安装、基本命令…...

工控主板ESM7000/6800E支持远程桌面控制

英创公司ESM7000 是面向工业领域的双核 Cortex-A7 高性能嵌入式主板&#xff0c;ESM6800E则为单核Cortex-A7 高性价比嵌入式主板&#xff0c;ESM7000、ESM6800E都是公司的成熟产品&#xff0c;已广泛应用于工业很多领域。ESM7000/6800E板卡中Linux系统配置为linux-4.9.11内核、…...

wamp php7.4 运行dm8

背景 1、电脑安装了dm8&#xff0c;具体参照官网dm8安装 2、安装好了wamp&#xff0c;我当前的php版本切换成了7.4的&#xff0c;我wamp的安装路径d:\wamp64\ 操作 3、查看phpinfo&#xff0c;如果Thread Safet为enabled&#xff0c;则选择pdo74_dm.dll&#xff0c;否则选择…...

HTML5 进度条(Progress Bar)详解

HTML5 进度条&#xff08;Progress Bar&#xff09;详解 进度条是用于显示任务完成进度的控件&#xff0c;常用于加载、上传或下载等操作。HTML5提供了原生的<progress>元素&#xff0c;使得创建进度条变得简单和直观。 1. 基本用法 <progress>元素的基本语法如…...

LabVIEW开发中常见硬件通讯接口快速识别

在 LabVIEW 开发中&#xff0c;与硬件进行通讯是实现数据采集与控制的重要环节。准确判断通讯接口类型和协议&#xff0c;可以提高开发效率&#xff0c;减少调试时间。本文结合 LabVIEW 的实际应用&#xff0c;详细介绍如何识别和判断常见硬件通讯接口的定义&#xff0c;并提供…...

高频 SQL 50 题(基础版)_1068. 产品销售分析 I

销售表 Sales&#xff1a; (sale_id, year) 是销售表 Sales 的主键&#xff08;具有唯一值的列的组合&#xff09;。 product_id 是关联到产品表 Product 的外键&#xff08;reference 列&#xff09;。 该表的每一行显示 product_id 在某一年的销售情况。 注意: price 表示每…...

笔记:一次mysql主从复制延迟高的处理尝试

背景 mysql 5.7 主从复制 主库进行了一次灌数&#xff0c;导致多个大事务产生&#xff0c;主从延迟下不去&#xff0c;经确认该表最终truncate&#xff0c;并且该表仅有insert和select操作&#xff0c;故对该表的事务进行跳过&#xff0c;直到同步至truncate 跳过事务需谨慎&…...

基于C语言的卡丁车管理系统【控制台应用程序】

注意&#xff1a;需要提前创建对应的.dat文件 本项目实现了数据的永久存储&#xff0c;有用户的注册、登录。 管理员对卡丁车的管理、查看预约用户、修改帐户权限。 用户对个人信息的管理、查看并预约卡丁车、卡丁车维修上报。 维修员对卡丁车的维修状态上报、个人信息管理。 …...

Docker 搭建 Gogs

Docker 搭建 Gogs 准备工作 先准备配置目录和持久化目录&#xff0c;举个栗子&#xff1a;mkdir -p /opt/module/gogs/{data,backup} 拉取官方Gogs镜像 # 拉取 gogs:0.13 docker pull gogs/gogs:0.13 # 拉取最新版 gogs 镜像 docker pull gogs/gogs启动一个临时容器【通过创…...

PostgreSQL的备份方式

PostgreSQL 提供多种方式进行备份&#xff0c;适用于不同需求的场景。常用的备份方法如下&#xff1a; 1. 逻辑备份&#xff08;pg_dump 和 pg_dumpall&#xff09; 1.1 使用 pg_dump 备份单个数据库 pg_dump 是 PostgreSQL 内置的逻辑备份工具&#xff0c;可以将数据库导出为…...

Springboot 3项目整合Knife4j接口文档(接口分组详细教程)

文章目录 前言一、Spring Boot 3.0整合Knife4j二、OpenApi 3注解的使用规范三、使用步骤 1.Spring Boot 3.0项目中使用knife4j2.在application.yml中添加knife4j相关配置3.设置WebMvc相关配置&#xff08;解决封装统一异常处理后doc.html无法打开的问题&#xff09;4.创建Knif…...

深入解析 Conda 安装的默认依赖包及其作用:conda create安装了哪些包(中英双语)

深入解析 Conda 安装的默认依赖包及其作用 当我们使用 Conda 创建新环境时&#xff0c;例如执行命令&#xff1a; conda create -n olmes python3.10Conda 会自动为我们安装一系列基础依赖包&#xff0c;保证 Python 环境能够正常运行。这些包不仅是我们开发的基础工具&#…...

Redis核心技术知识点全集

Redis数据结构和常用命令 1. String字符串2. Hash哈希3. List列表4. Set集合5. Sorted Set有序集合6. Redis常用命令参考Redis事务机制...

【Unity3D】ECS入门学习(九)SystemBase

SystemBase&#xff1a;支持主线程或多线程执行筛选实体任务。 主要介绍是内部成员&#xff1a;Entities的各种筛选方法&#xff0c;其内部成员还有EntityManager ForEach方法筛选&#xff0c;传递一个有参委托函数进去&#xff0c;参数ref xxx组件类&#xff08;可填多个&…...

抛开Transformer,我们还能如何理解Attention机制?

对于许多软件测试从业者而言&#xff0c;“Attention机制”这个词常常与Transformer、BERT、GPT这些大模型名词紧密捆绑&#xff0c;仿佛是深度学习“黑盒”中一个难以触及的复杂组件。然而&#xff0c;当我们暂时抛开Transformer这棵参天大树&#xff0c;回归到Attention机制本…...

高通平台实战:手把手教你解析和修改CDT中的board-id(附常见报错排查)

高通平台深度实战&#xff1a;CDT中board-id的解析与定制化修改指南 引言&#xff1a;为什么需要关注board-id&#xff1f; 在Android底层开发中&#xff0c;board-id就像设备的"身份证号"&#xff0c;它决定了系统如何识别硬件配置并加载对应的设备树和驱动。对于从…...

告别数据打架:手把手教你用Python+Seurat整合单细胞数据,无缝衔接scVelo做RNA速率分析

告别数据打架&#xff1a;手把手教你用PythonSeurat整合单细胞数据&#xff0c;无缝衔接scVelo做RNA速率分析 单细胞测序技术的快速发展为生物医学研究带来了前所未有的分辨率&#xff0c;但不同分析工具之间的数据格式壁垒常常让研究者头疼。特别是当我们需要在R语言的Seurat和…...

OpenClaw技能开发入门:为Qwen3-4B定制专属自动化模块

OpenClaw技能开发入门&#xff1a;为Qwen3-4B定制专属自动化模块 1. 为什么需要自定义OpenClaw技能 去年夏天&#xff0c;我接手了一个重复性极高的周报生成工作。每周都要从十几个PDF报告中提取关键数据&#xff0c;整理成固定格式的Excel表格&#xff0c;再转成PPT汇报。当…...

从STFT到ISTFT:窗函数、填充与流式处理的实战指南

1. 窗函数一致性&#xff1a;信号重建的隐形守护者 第一次用STFT处理语音信号时&#xff0c;我踩过一个典型坑&#xff1a;用汉宁窗做分析&#xff0c;却忘了在重建时指定相同窗函数。结果重建后的语音像被掐着脖子说话&#xff0c;高频部分全是毛刺。这个教训让我明白&#xf…...

能源在线监测管理系统平台[fu源码]

EMS能源管理系统 基于 Vue3 / Spring Boot/Spring Cloud & Alibaba 微服务架构 项目技术框架 RuoYi-Cloud 基础框架上开发而成 源智优控AI能源大脑&#xff0c;能源AI版&#xff0c;即将上线 仓库地址&#xff1a; https://gitee.com/guangdong122/energy-management …...

彻底清除TortoiseSVN:从基础卸载到深度清理全指南

1. 为什么TortoiseSVN卸载这么麻烦&#xff1f; 很多朋友第一次卸载TortoiseSVN时都会遇到各种"后遗症"——右键菜单残留、注册表垃圾、文件夹图标异常。这其实和它的工作原理有关。TortoiseSVN作为Windows资源管理器的Shell扩展&#xff0c;会深度集成到系统底层。我…...

class文件加载到内存

‌JVM将class文件加载到内存的过程主要分为三个阶段&#xff1a;加载&#xff08;Loading&#xff09;、链接&#xff08;Linking&#xff09;和初始化&#xff08;Initialization&#xff09;‌&#xff0c;其中链接又细分为验证、准备、解析三个步骤 。 一、加载&#xff08;…...

文墨共鸣大模型处理Java八股文与面试题:智能学习与模拟面试

文墨共鸣大模型处理Java八股文与面试题&#xff1a;智能学习与模拟面试 准备Java技术面试&#xff0c;大概是每个开发者都绕不开的一道坎。面对海量的“八股文”知识点和层出不穷的面试题&#xff0c;你是不是也经历过这样的场景&#xff1a;翻开厚厚的面试宝典&#xff0c;感…...

实战构建企业技能评估系统:基于快马平台实现skill-vetter全流程解决方案

实战构建企业技能评估系统&#xff1a;基于快马平台实现skill-vetter全流程解决方案 最近在帮公司搭建内部技能认证系统时&#xff0c;发现传统线下考试方式存在效率低、数据难沉淀的问题。于是尝试用InsCode(快马)平台开发了一套skill-vetter系统&#xff0c;整个过程比想象中…...