(图论) 1020. 飞地的数量 ——【Leetcode每日一题】
❓ 1020. 飞地的数量
难度:中等
给你一个大小为 m x n
的二进制矩阵 grid
,其中 0
表示一个 海洋单元格、1
表示一个 陆地单元格。
一次 移动 是指从一个陆地单元格走到另一个相邻(上、下、左、右)的陆地单元格或跨过 grid
的边界。
返回网格中 无法 在任意次数的移动中离开网格边界的陆地单元格的数量。
示例 1:
输入:grid = [[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]]
输出:3
解释:有三个 1 被 0 包围。一个 1 没有被包围,因为它在边界上。
示例 2:
输入:grid = [[0,1,1,0],[0,0,1,0],[0,0,1,0],[0,0,0,0]]
输出:0
解释:所有 1 都在边界上或可以到达边界。
提示:
m == grid.length
n == grid[i].length
1 <= m, n <= 500
grid[i][j]
的值为0
或1
💡思路:DFS
本题要求找到不靠边的陆地面积,那么
- 我们只要从周边找到陆地
- 然后 通过
dfs
或者bfs
将周边靠陆地且相邻的陆地都变成海洋, - 然后再去重新遍历地图的时候,统计此时还剩下的陆地就可以了。
🍁代码:(C++、Java)
C++
class Solution {
private:int dir[4][2] = {-1, 0, 0, -1, 1, 0, 0, 1}; // 保存四个方向int m = 0, n = 0;void dfs(int i, int j, vector<vector<int>>& grid){if(grid[i][j] == 0){ // 是海洋则返回return;}grid[i][j] = 0;for(int k = 0; k < 4; k++){ // 向四个方向遍历int nexti = i + dir[k][0];int nextj = j + dir[k][1];if(nexti < 0 || nexti >= m || nextj < 0 || nextj >= n) continue;dfs(nexti, nextj, grid);}}
public:int numEnclaves(vector<vector<int>>& grid) {m = grid.size();n = grid[0].size();// 从左侧边,和右侧边 向中间遍历for(int i = 0; i < m; i++){dfs(i, 0, grid);dfs(i, n - 1, grid);}// 从上边和下边 向中间遍历for(int i = 0; i < n; i++){dfs(0, i, grid);dfs(m - 1, i, grid);}//统计剩余陆地的面积int ans = 0;for(int i = 0; i < m; i++){for(int j = 0; j < n; j++){if(grid[i][j] == 1) ans++;}}return ans;}
};
Java
class Solution {private int[][] dir = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}}; // 四个方向int m = 0, n = 0;private void dfs(int i, int j, int[][] grid){if(grid[i][j] == 0) return;// 是海洋则返回grid[i][j] = 0;for(int k = 0; k < 4; k++){// 向四个方向遍历int nexti = i + dir[k][0];int nextj = j + dir[k][1];// 超过边界if(nexti < 0 || nexti >= m || nextj < 0 || nextj >= n) continue;dfs(nexti, nextj, grid);}}public int numEnclaves(int[][] grid) {m = grid.length;n = grid[0].length;// 从左侧边,和右侧边 向中间遍历for(int i = 0; i < m; i++){dfs(i, 0, grid);dfs(i, n - 1, grid);}// 从上边和下边 向中间遍历for(int j = 0; j < n; j++){dfs(0, j, grid);dfs(m - 1, j, grid);}//统计剩余陆地的面积int ans = 0;for(int i = 0; i < m; i++){for(int j = 0; j < n; j++){if(grid[i][j] == 1) ans++;}}return ans;}
}
🚀 运行结果:
🕔 复杂度分析:
-
时间复杂度: O ( m n ) O(mn) O(mn),其中
m
和n
分别是网格grid
的行数和列数。深度优先搜索最多访问每个单元格一次,需要 O ( m n ) O(mn) O(mn) 的时间,遍历网格统计飞地的数量也需要 O ( m n ) O(mn) O(mn) 的时间。 -
空间复杂度: O ( m n ) O(mn) O(mn),空间复杂度主要取决于递归调用栈空间,最大空间复杂度是 O ( m n ) O(mn) O(mn)。
题目来源:力扣。
放弃一件事很容易,每天能坚持一件事一定很酷,一起每日一题吧!
关注我LeetCode主页 / CSDN—力扣专栏,每日更新!
注: 如有不足,欢迎指正!
相关文章:

(图论) 1020. 飞地的数量 ——【Leetcode每日一题】
❓ 1020. 飞地的数量 难度:中等 给你一个大小为 m x n 的二进制矩阵 grid ,其中 0 表示一个 海洋单元格、1 表示一个 陆地单元格。 一次 移动 是指从一个陆地单元格走到另一个相邻(上、下、左、右)的陆地单元格或跨过 grid 的边…...

c++ 重载、重写、覆盖
重载:指在同一作用域内,有多个同名但参数不同的函数的现象,叫重载;可以是任何用户定义的函数,例如 类成员函数、类静态函数、普通函数重写:子类重写父类的同名函数,只要子类出现有父类的同名函数…...

Python异步编程高并发执行爬虫采集,用回调函数解析响应
一、问题:当发送API请求,读写数据库任务较重时,程序运行效率急剧下降。 异步技术是Python编程中对提升性能非常重要的一项技术。在实际应用,经常面临对外发送网络请求,调用外部接口,或者不断更新数据库或文…...

SpriteKit与Swift配合:打造您的第一个简易RPG游戏的步骤指南
1. 简介: RPG(Role-Playing Game)游戏是一种角色扮演游戏,它允许玩家在一个虚拟的游戏世界中扮演一个或多个角色。在本教程中,我们将使用Apple的2D游戏框架SpriteKit和Swift编程语言来创建一个简单的RPG游戏。我们将从…...

服务网格的面临挑战:探讨服务网格实施中可能遇到的问题和解决方案
🌷🍁 博主猫头虎 带您 Go to New World.✨🍁 🦄 博客首页——猫头虎的博客🎐 🐳《面试题大全专栏》 文章图文并茂🦕生动形象🦖简单易学!欢迎大家来踩踩~🌺 &a…...

leetcode61 旋转链表
题目 给你一个链表的头节点 head ,旋转链表,将链表每个节点向右移动 k 个位置。 示例 输入:head [1,2,3,4,5], k 2 输出:[4,5,1,2,3] 解析 这道题属实不好想:需要计算出链表的长度,然后在k > n的…...

【学习笔记】各类基于决策单调性的dp优化
文章目录 对于决策单调性的一般解释关于决策单调性的证明四边形不等式一维dp区间dp一种二维dp一些满足四边形不等式的函数类 与图形相结合 决策单调性的常见优化手段二分队列二分栈分治类莫队做法 SMAWKWQS二分WQS多解情况满足四边形不等式的序列划分问题的答案凸性以及WQS二分…...

【C++】构造函数初始化列表 ⑤ ( 匿名对象 生命周期 | 构造函数 中 不能调用 构造函数 )
文章目录 一、匿名对象 生命周期1、匿名对象 生命周期 说明2、代码示例 - 匿名对象 生命周期 二、构造函数 中调用 构造函数1、构造函数 中 不能调用 构造函数2、代码示例 - 构造函数中调用构造函数 构造函数初始化列表 总结 : 初始化列表 可以 为 类的 成员变量 提供初始值 ;…...

Knife4j系列--使用方法
原文网址:Knife4j系列--使用/教程/实例/配置_IT利刃出鞘的博客-CSDN博客...

pmp项目管理考试是什么?适合哪些人学?
PMP,简单点说,就是美国PMI为考察项目管理人士的专业能力而设立的考试。 该流程以知识和任务驱动型指南评估从业者的能力,同时确定项目经理能力行业标准,包括各项知识、任务和技能的特点、重要性与运用频率。(考纲原文…...

CSDN博客可以添加联系方式了
csdn博客一直不允许留一些联系方式,结果是官方有联系方式路径 在首页,往下拉,左侧就有 点击这个即可添加好友了~ 美滋滋,一起交流, 学习技术 ~...

小程序隐私弹窗的实现
小程序的开发者对于微信官方来说是有爱有恨,三天二头整事是鹅厂的一贯风格。 隐私弹窗的几个要点 回归正题,小程序隐私弹窗的几个要点: 1、何时弹出用户隐私协议的弹窗? 2、是每次进小程序都弹出来吗? 这两个想明…...

【JavaEE】多线程案例-单例模式
文章目录 1. 前言2. 什么是单例模式3. 如何实现单例模式3.1 饿汉模式3.2 懒汉模式4. 解决单例模式中遇到的线程安全问题4.1 加锁4.2 加上一个判断解决频繁加锁问题4.2 解决因指令重排序造成的线程不安全问题 1. 前言 单例模式是我们面试中最常考到的设计模式。什么是设计模式呢…...

社区分享|MeterSphere变身“啄木鸟”,助力云帐房落地接口自动化测试
云帐房网络科技有限公司(以下简称为“云帐房”)成立于2015年3月,以“成为最值得信赖的税务智能公司”为愿景,运用人工智能、大数据等互联网技术,结合深厚的财税行业服务经验,为代账公司和中大型企业提供智能…...

fpga内嵌逻辑分析仪使用方法
文章目录 前言一、方法1 — 使用 IP 核创建 ILA 调试环境1、创建 ILA ip 核2、进行例化3、生成比特流文件4、下载程序5、进行在线调试 二、方法2 — 使用 Debug 标记创建 ILA1、Debug 标记相关信号2、综合操作3、设置 Set Up Debug4、生成比特文件5、下载程序6、进行在线调试 前…...

第14章 结构和其他数据形式
本章介绍以下内容: 关键字:struct、union、typedef 运算符:.、-> 什么是C结构,如何创建结构模板和结构变量 如何访问结构的成员,如何编写处理结构的函数 联合和指向函数的指针 设计程序时,最重要的步骤之…...

vue 把echarts封装成一个方法 并且从后端读取数据 +转换数据格式 =动态echarts 联动echarts表
1.把echarts 在 methods 封装成一个方法mounted 在中调用 折线图 和柱状图 mounted调用下边两个方法 mounted(){//最早获取DOM元素的生命周期函数 挂载完毕console.log(mounted-id , document.getElementById(charts))this.line()this.pie()},methods里边的方法 line() {// …...

Python基础08 面向对象的基本概念
Python使用类(class)和对象(object),进行面向对象(object-oriented programming,简称OOP)的编程。 面向对象的最主要目的是提高程序的重复使用性。我们这么早切入面向对象编程的原因是,Python的整个概念是基于对象的。…...

APP自动化之Poco框架
今天给大家介绍一款自动化测试框架Poco,其脚本写法非常简洁、高效,其元素定位器效率更快,其本质基于python的第三方库,调试起来也会非常方便,能够很好的提升自动化测试效率,节省时间。 (一)背景…...

c++拷贝构造【显式调用】和运算符=重载构造【隐式调用】解析
深拷贝 vs. 浅拷贝 深拷贝:开辟新内存,独立对象,堆区浅拷贝:共享内存,引用对象,栈区 深拷贝:深拷贝是一种拷贝方式,它会在堆区重新分配内存并复制对象的内容。 这意味着原对象和新…...

无涯教程-JavaScript - LCM函数
描述 LCM函数返回整数的最小公倍数。最小公倍数是最小的正整数,它是所有整数参数number1,number2等的倍数。使用LCM添加具有不同分母的分数。 语法 LCM (number1, [number2] ...)争论 Argument描述Required/OptionalNumber1, number2... 您想要最小公倍数的1到255个值。 如…...

Java多线程篇(3)——线程池
文章目录 线程池ThreadPoolExecutor源码分析1、如何提交任务2、如何执行任务3、如何停止过期的非核心线程4、如何使用拒绝策略 ScheduledThreadPoolExecutor源码分析 线程池 快速过一遍基础知识 7大参数 corePoolSize : 核心线程数 maximumPoolSize: 最…...

那些年我们遇到过的关于excel的操作
本文为直接从百度上搜索的关于excel的函数使用,方便以后用,希望会持续补充 excel中筛选出两列重复的数据【场景:A、B两列数据个数不同且无序,想找出A列中的数据在B列中不存在的,通过比较后单元格为空的代表该行不存在的…...

Angular变更检测机制
前段时间遇到这样一个 bug,通过一个 click 事件跳转到一个新页面,新页面迟迟不加载; 经过多次测试发现,将鼠标移入某个 tab ,页面就加载出来了。 举个例子,页面内容无法加载,但是将鼠标移入下图…...

Redis之String类型
文章目录 Redis之String类型1. 赋值/获取值2. 同时设置/获取多个键值3. 数值增减4. 获取字符串长度5. 向尾部追加值6. 分布式锁7.应用场景 Redis之String类型 Redis命令不区分大小写 1. 赋值/获取值 赋值:set key value 取值:get key (当键不存在时候&…...

使用redis中的zset实现滑动窗口限流
使用redis和zset实现滑动窗口限流 文章目录 使用redis和zset实现滑动窗口限流Zset**初始化一个ZSet**:其中包含所有用户的ID和时间戳。**添加元素到ZSet**:当用户发起请求时,将当前时间戳和用户ID作为元素添加到ZSet中。**删除过期的元素**&a…...

Linux下C语言使用 netlink sockets与内核模块通信
netlink简介 Netlink套接字是用以实现用户进程与内核进程通信的一种特殊的进程间通信(IPC) ,也是网络应用程序与内核通信的最常用的接口。在Linux标准内核中,系统默认集成了很多netlink实例,比如日志上报、路由系统等,netlink消息是双向的&a…...

excel中的引用与查找函数篇3
1、INDEX(array,row_num,[col_num]):获取指定范围中指定行号和列号对应的数据 index(查询范围,行号,列号) 行号和列号是相对选中查询范围来写的:分别把第二行第三列的数据和第四行第二列的数据查找出来。 数据是单行或单列,后面只需要给一个参…...

【Linux学习笔记】 - 常用指令学习及其验证(下)
前言:本文延续上一篇文章【Linux学习笔记】 - 常用指令学习及其验证(上)对常用的指令进行介绍和验证。 一、mv指令 (1)功能:用来移动文件或者将文件改名 (2)语法及验证:…...

面试官:请说说flex布局_番茄出品.md
面试官:请说说flex布局_番茄出品.md start 依然记得当初学习 flex 布局时,用 flex 布局:画麻将。一筒到九筒,应有尽有。但是光和面试官说,我用 flex 布局画过麻将,并没有什么用。面试官问你一个语法&…...