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组件类(可填多个&…...
未来机器人的大脑:如何用神经网络模拟器实现更智能的决策?
编辑:陈萍萍的公主一点人工一点智能 未来机器人的大脑:如何用神经网络模拟器实现更智能的决策?RWM通过双自回归机制有效解决了复合误差、部分可观测性和随机动力学等关键挑战,在不依赖领域特定归纳偏见的条件下实现了卓越的预测准…...
通过Wrangler CLI在worker中创建数据库和表
官方使用文档:Getting started Cloudflare D1 docs 创建数据库 在命令行中执行完成之后,会在本地和远程创建数据库: npx wranglerlatest d1 create prod-d1-tutorial 在cf中就可以看到数据库: 现在,您的Cloudfla…...
【入坑系列】TiDB 强制索引在不同库下不生效问题
文章目录 背景SQL 优化情况线上SQL运行情况分析怀疑1:执行计划绑定问题?尝试:SHOW WARNINGS 查看警告探索 TiDB 的 USE_INDEX 写法Hint 不生效问题排查解决参考背景 项目中使用 TiDB 数据库,并对 SQL 进行优化了,添加了强制索引。 UAT 环境已经生效,但 PROD 环境强制索…...
Frozen-Flask :将 Flask 应用“冻结”为静态文件
Frozen-Flask 是一个用于将 Flask 应用“冻结”为静态文件的 Python 扩展。它的核心用途是:将一个 Flask Web 应用生成成纯静态 HTML 文件,从而可以部署到静态网站托管服务上,如 GitHub Pages、Netlify 或任何支持静态文件的网站服务器。 &am…...
数据链路层的主要功能是什么
数据链路层(OSI模型第2层)的核心功能是在相邻网络节点(如交换机、主机)间提供可靠的数据帧传输服务,主要职责包括: 🔑 核心功能详解: 帧封装与解封装 封装: 将网络层下发…...
《基于Apache Flink的流处理》笔记
思维导图 1-3 章 4-7章 8-11 章 参考资料 源码: https://github.com/streaming-with-flink 博客 https://flink.apache.org/bloghttps://www.ververica.com/blog 聚会及会议 https://flink-forward.orghttps://www.meetup.com/topics/apache-flink https://n…...
【OSG学习笔记】Day 16: 骨骼动画与蒙皮(osgAnimation)
骨骼动画基础 骨骼动画是 3D 计算机图形中常用的技术,它通过以下两个主要组件实现角色动画。 骨骼系统 (Skeleton):由层级结构的骨头组成,类似于人体骨骼蒙皮 (Mesh Skinning):将模型网格顶点绑定到骨骼上,使骨骼移动…...
用docker来安装部署freeswitch记录
今天刚才测试一个callcenter的项目,所以尝试安装freeswitch 1、使用轩辕镜像 - 中国开发者首选的专业 Docker 镜像加速服务平台 编辑下面/etc/docker/daemon.json文件为 {"registry-mirrors": ["https://docker.xuanyuan.me"] }同时可以进入轩…...
【HTTP三个基础问题】
面试官您好!HTTP是超文本传输协议,是互联网上客户端和服务器之间传输超文本数据(比如文字、图片、音频、视频等)的核心协议,当前互联网应用最广泛的版本是HTTP1.1,它基于经典的C/S模型,也就是客…...
pikachu靶场通关笔记22-1 SQL注入05-1-insert注入(报错法)
目录 一、SQL注入 二、insert注入 三、报错型注入 四、updatexml函数 五、源码审计 六、insert渗透实战 1、渗透准备 2、获取数据库名database 3、获取表名table 4、获取列名column 5、获取字段 本系列为通过《pikachu靶场通关笔记》的SQL注入关卡(共10关࿰…...
