当前位置: 首页 > 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;可填多个&…...

uniapp 对接腾讯云IM群组成员管理(增删改查)

UniApp 实战&#xff1a;腾讯云IM群组成员管理&#xff08;增删改查&#xff09; 一、前言 在社交类App开发中&#xff0c;群组成员管理是核心功能之一。本文将基于UniApp框架&#xff0c;结合腾讯云IM SDK&#xff0c;详细讲解如何实现群组成员的增删改查全流程。 权限校验…...

【Python】 -- 趣味代码 - 小恐龙游戏

文章目录 文章目录 00 小恐龙游戏程序设计框架代码结构和功能游戏流程总结01 小恐龙游戏程序设计02 百度网盘地址00 小恐龙游戏程序设计框架 这段代码是一个基于 Pygame 的简易跑酷游戏的完整实现,玩家控制一个角色(龙)躲避障碍物(仙人掌和乌鸦)。以下是代码的详细介绍:…...

TDengine 快速体验(Docker 镜像方式)

简介 TDengine 可以通过安装包、Docker 镜像 及云服务快速体验 TDengine 的功能&#xff0c;本节首先介绍如何通过 Docker 快速体验 TDengine&#xff0c;然后介绍如何在 Docker 环境下体验 TDengine 的写入和查询功能。如果你不熟悉 Docker&#xff0c;请使用 安装包的方式快…...

RocketMQ延迟消息机制

两种延迟消息 RocketMQ中提供了两种延迟消息机制 指定固定的延迟级别 通过在Message中设定一个MessageDelayLevel参数&#xff0c;对应18个预设的延迟级别指定时间点的延迟级别 通过在Message中设定一个DeliverTimeMS指定一个Long类型表示的具体时间点。到了时间点后&#xf…...

Leetcode 3576. Transform Array to All Equal Elements

Leetcode 3576. Transform Array to All Equal Elements 1. 解题思路2. 代码实现 题目链接&#xff1a;3576. Transform Array to All Equal Elements 1. 解题思路 这一题思路上就是分别考察一下是否能将其转化为全1或者全-1数组即可。 至于每一种情况是否可以达到&#xf…...

《Qt C++ 与 OpenCV:解锁视频播放程序设计的奥秘》

引言:探索视频播放程序设计之旅 在当今数字化时代,多媒体应用已渗透到我们生活的方方面面,从日常的视频娱乐到专业的视频监控、视频会议系统,视频播放程序作为多媒体应用的核心组成部分,扮演着至关重要的角色。无论是在个人电脑、移动设备还是智能电视等平台上,用户都期望…...

shell脚本--常见案例

1、自动备份文件或目录 2、批量重命名文件 3、查找并删除指定名称的文件&#xff1a; 4、批量删除文件 5、查找并替换文件内容 6、批量创建文件 7、创建文件夹并移动文件 8、在文件夹中查找文件...

循环冗余码校验CRC码 算法步骤+详细实例计算

通信过程&#xff1a;&#xff08;白话解释&#xff09; 我们将原始待发送的消息称为 M M M&#xff0c;依据发送接收消息双方约定的生成多项式 G ( x ) G(x) G(x)&#xff08;意思就是 G &#xff08; x ) G&#xff08;x) G&#xff08;x) 是已知的&#xff09;&#xff0…...

SCAU期末笔记 - 数据分析与数据挖掘题库解析

这门怎么题库答案不全啊日 来简单学一下子来 一、选择题&#xff08;可多选&#xff09; 将原始数据进行集成、变换、维度规约、数值规约是在以下哪个步骤的任务?(C) A. 频繁模式挖掘 B.分类和预测 C.数据预处理 D.数据流挖掘 A. 频繁模式挖掘&#xff1a;专注于发现数据中…...

Opencv中的addweighted函数

一.addweighted函数作用 addweighted&#xff08;&#xff09;是OpenCV库中用于图像处理的函数&#xff0c;主要功能是将两个输入图像&#xff08;尺寸和类型相同&#xff09;按照指定的权重进行加权叠加&#xff08;图像融合&#xff09;&#xff0c;并添加一个标量值&#x…...