图论06-飞地的数量(Java)
6.飞地的数量
- 题目描述
给你一个大小为 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 没有被包围,因为它在边界上。
- 题目分析
1.题目分析
给定一个二进制矩阵 grid,其中0表示海洋单元格,1表示陆地单元格。
一次移动是指从一个陆地单元格走到另一个相邻的陆地单元格或者跨过矩阵边界。
要求找出在任意次数的移动中无法离开网格边界的陆地单元格数量。2.思路分析
--主要思路:
使用深度优先搜索(DFS)来遍历所有的陆地单元格,并标记与边界相连的陆地单元格。
维护两个全局变量 flag 和 spare,分别用于标记每块岛屿是否靠海和记录每块岛屿的面积。
遍历整个二维网格,对每个陆地单元格进行DFS处理,统计无法跨越边界的方块数。--详细步骤:
-初始化 count 为0,用于表示无法跨越边界的方块数。
-遍历二维网格 grid 的每个单元格 (i, j):
-如果当前单元格为陆地(grid[i][j] == 1),则调用 dfs 方法进行DFS处理。
-在 dfs 方法中:
如果当前位置 (i, j) 超出边界或者是海洋(grid[i][j] == 0),则返回。否则,标记当前位置为已访问,更新 spare 记录当前岛屿面积。
如果当前位置在边界上,则将 flag 标记为1,表示当前岛屿靠近海洋。继续递归调用DFS处理当前位置的四个相邻位置。
如果当前岛屿不靠近海洋(flag == 0),则将当前岛屿的面积累加到 count 中。最后返回 count 作为结果。
-复杂度分析:
时间复杂度:O(m*n),m 和 n 分别为二维网格的行数和列数,需要遍历整个二维网格。
空间复杂度:O(1),除了函数调用栈外,没有使用额外空间。
- Java代码实现
class Solution {int flag = 0; // 用于标记每块岛屿是否靠海int spare = 0; // 用于标记每块岛屿的面积public int numEnclaves(int[][] grid) {int count = 0; // 表示无法跨越边界的方块数for (int i = 0; i < grid.length; i++) {for (int j = 0; j < grid[0].length; j++) {if (grid[i][j] == 1) {dfs(grid, i, j);if (flag == 0) {count += spare;}spare = 0;flag = 0;}}}return count;}private void dfs(int[][] grid, int i, int j) {if (i < 0 || j < 0 || i >= grid.length || j >= grid[0].length) {return;}if (grid[i][j] == 0) {return;}spare++;grid[i][j] = 0;if (i == 0 || i == grid.length - 1 || j == 0 || j == grid[0].length - 1) {flag = 1; // 表示存在临海区域}dfs(grid, i + 1, j); // 下dfs(grid, i - 1, j); // 上dfs(grid, i, j + 1); // 右dfs(grid, i, j - 1); // 左}
}
相关文章:
图论06-飞地的数量(Java)
6.飞地的数量 题目描述 给你一个大小为 m x n 的二进制矩阵 grid ,其中 0 表示一个海洋单元格、1 表示一个陆地单元格。 一次 移动 是指从一个陆地单元格走到另一个相邻(上、下、左、右)的陆地单元格或跨过 grid 的边界。 返回网格中 无法…...
Java设计模式之单例设计模式
单例设计模式就是保证整个软件系统中,某个类只能存在一个对象实例,并且该类只提供一个取得该对象的方法。 单例设计模式包括两种:饿汉式和懒汉式。 饿汉式: 含义: 在类加载时就创建并初始化单例对象。这种方式确保了…...
多维时序 | MATLAB实现BiTCN-selfAttention自注意力机制结合双向时间卷积神经网络多变量时间序列预测
多维时序 | MATLAB实现BiTCN-selfAttention自注意力机制结合双向时间卷积神经网络多变量时间序列预测 目录 多维时序 | MATLAB实现BiTCN-selfAttention自注意力机制结合双向时间卷积神经网络多变量时间序列预测预测效果基本介绍模型描述程序设计参考资料 预测效果 基本介绍 1.M…...
深入了解Android垃圾回收机制
文章目录 一、内存分配二、垃圾回收触发条件三、GC算法3.1 Dalvik虚拟机的GC算法3.2 ART的GC算法 四、优化GC性能五、监控GC耗时情况六、总结 在Android应用开发中,内存管理和垃圾回收(GC)对于应用性能和稳定性至关重要。理解GC机制有助于我们…...
如何学好Python语言
学习Python:一场充满探索与实践的编程之旅 Python,作为一种解释型、交互式和面向对象的编程语言,近年来在数据科学、人工智能、Web开发等多个领域得到了广泛的应用。掌握Python,不仅可以提升个人的编程技能,还能够为未…...
计算机408网课评测+资料分享
408当然有比较好的网课推荐,比如王道的视频课 现在大部分人备战408基本都用王道的讲义,然后再搭配王道408的课程来听,可以学的很好。 其中408视频课中,我认为讲的比较好的是数据结构,和操作系统,计算机组…...
使用 ZipArchiveInputStream 读取压缩包内文件总数
读取压缩包内文件总数 简介 ZipArchiveInputStream 是 Apache Commons Compress 库中的一个类,用于读取 ZIP 格式的压缩文件。在处理 ZIP 文件时,编码格式是一个重要的问题,因为它决定了如何解释文件中的字符数据。通常情况下,Z…...
JavaScript对象修饰教程
在JavaScript中,对象修饰是一种常见的编程模式,用于动态地向对象添加新的功能或修改现有功能,同时保持对象的原始结构不变。对象修饰可以帮助我们实现代码的复用、扩展和维护,让代码更加灵活和可扩展。本文将深入探讨JavaScript对…...
转置卷积(transposed-conv)
一、什么是转置卷积 1、转置卷积的背景 通常,对图像进行多次卷积运算后,特征图的尺寸会不断缩小。而对于某些特定任务 (如图像分割和图像生成等),需将图像恢复到原尺寸再操作。这个将图像由小分辨率映射到大分辨率的尺寸恢复操作,…...
P1481 魔族密码
P1481 魔族密码 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 字典树 在插入字符串 s s s时,不断记录 s 0... k s_{0...k} s0...k的个数取最大即可。 #include <bits/stdc.h> using namespace std; const int N 1e5 21; int cnt[N], tr[N][30], idx,…...
无人机/飞控--ArduPilot、PX4学习记录(2)
这是一篇碎碎念,零零碎碎的记录了环境配置过程,仅供本人记录学习历程和参考。(记录的挺乱的,但是文章链接里的博客写的是真好) 本章主要完成的目标: 安装PX4 并 成功运行出3D无人机界面。 参考文章: 搭建PX4环境&…...
【Arxml专题】-29-使用Cantools将CAN Matrix Arxml自动生成C语言代码
目录 1 安装Python和Cantools 1.1 查看Python已安装的Package包 1.2 在Python中安装Cantools插件包 1.3 获取更多Cantools工具的更新动态 2 CAN Matrix Arxml自动生成C语言代码 2.1 批处理文件CAN_Matrix_Arxml_To_C.bat内容说明 2.2 CAN Matrix Arxml文件要求 2.3 如何…...
【id:21】【20分】E. 抄袭查找(结构体+指针+函数)
题目描述 已知一群学生的考试试卷,要求对试卷内容进行对比,查找是否有抄袭。 每张试卷包含:学号(整数类型)、题目1答案(字符串类型)、题目2答案(字符串类型)、题目3答案…...
ASP.NET-常用控件总结
一、ASP.NET基础控件 1、asp:TextBox (输入框) ASP.NET TextBox 控件用于接收用户输入。 <asp:TextBox ID"txtInput" runat"server"></asp:TextBox>2、asp:DropDownList (下拉框) ASP.NET DropDownList 控件用于提供一个下拉列表供用户选择…...
SpringBoot3整合Mybatis-Plus与PageHelper包冲突解决
😊 作者: 一恍过去 💖 主页: https://blog.csdn.net/zhuocailing3390 🎊 社区: Java技术栈交流 🎉 主题: SpringBoot3整合Mybatis-Plus与PageHelper包冲突解决 ⏱️ 创作时间&a…...
MQTT Keep Alive机制
MQTT 协议是承载于 TCP 协议之上的, 而 TCP 协议以连接为导向, 在连接双方之间, 提供稳定、 有序的字节流功能。 但是, 在部分情况下, TCP 可能出现半连接问题。 所谓半连接, 是指某一方的连接已经断开或者…...
基于springboot+vue的游戏交易系统
博主主页:猫头鹰源码 博主简介:Java领域优质创作者、CSDN博客专家、阿里云专家博主、公司架构师、全网粉丝5万、专注Java技术领域和毕业设计项目实战,欢迎高校老师\讲师\同行交流合作 主要内容:毕业设计(Javaweb项目|小程序|Pyt…...
高职(大专)结构化面试之答题思路
目录 一、岗位认知 二、职教热点 三、教育教学 四、人际关系 五、组织管理 六、应急应变 七、时政与教育 八、专业知识 一、岗位认知 考试方向:主要考察对岗位的全面认识、职业目标、职业规划、职业理想。 必背题目: 1.“你为什么要报考我们学校的教师岗…...
Python基础学习笔记(一)
Python简介 Python 语言是一种跨平台、开源、免费、解释型、面向对象、动态数据类型的高级程序设计语言。早期版本的 Python 被称作是 Python1;Python2 最后一个版本是 2.7;Python3 是目前最活跃的版 本,基本上新开发的 Python 代码都会支持…...
机器学习-可解释性机器学习:支持向量机与fastshap的可视化模型解析
一、引言 支持向量机(Support Vector Machine, SVM)作为一种经典的监督学习方法,在分类和回归问题中表现出色。其优点之一是生成的模型具有较好的泛化能力和可解释性,能够清晰地展示特征对于分类的重要性。 fastshap是一种用于快速计算SHAP值(…...
苍穹外卖--缓存菜品
1.问题说明 用户端小程序展示的菜品数据都是通过查询数据库获得,如果用户端访问量比较大,数据库访问压力随之增大 2.实现思路 通过Redis来缓存菜品数据,减少数据库查询操作。 缓存逻辑分析: ①每个分类下的菜品保持一份缓存数据…...
Element Plus 表单(el-form)中关于正整数输入的校验规则
目录 1 单个正整数输入1.1 模板1.2 校验规则 2 两个正整数输入(联动)2.1 模板2.2 校验规则2.3 CSS 1 单个正整数输入 1.1 模板 <el-formref"formRef":model"formData":rules"formRules"label-width"150px"…...
Spring是如何解决Bean的循环依赖:三级缓存机制
1、什么是 Bean 的循环依赖 在 Spring框架中,Bean 的循环依赖是指多个 Bean 之间互相持有对方引用,形成闭环依赖关系的现象。 多个 Bean 的依赖关系构成环形链路,例如: 双向依赖:Bean A 依赖 Bean B,同时 Bean B 也依赖 Bean A(A↔B)。链条循环: Bean A → Bean…...
AirSim/Cosys-AirSim 游戏开发(四)外部固定位置监控相机
这个博客介绍了如何通过 settings.json 文件添加一个无人机外的 固定位置监控相机,因为在使用过程中发现 Airsim 对外部监控相机的描述模糊,而 Cosys-Airsim 在官方文档中没有提供外部监控相机设置,最后在源码示例中找到了,所以感…...
书籍“之“字形打印矩阵(8)0609
题目 给定一个矩阵matrix,按照"之"字形的方式打印这个矩阵,例如: 1 2 3 4 5 6 7 8 9 10 11 12 ”之“字形打印的结果为:1,…...
嵌入式面试常问问题
以下内容面向嵌入式/系统方向的初学者与面试备考者,全面梳理了以下几大板块,并在每个板块末尾列出常见的面试问答思路,帮助你既能夯实基础,又能应对面试挑战。 一、TCP/IP 协议 1.1 TCP/IP 五层模型概述 链路层(Link Layer) 包括网卡驱动、以太网、Wi‑Fi、PPP 等。负责…...
【笔记】AI Agent 项目 SUNA 部署 之 Docker 构建记录
#工作记录 构建过程记录 Microsoft Windows [Version 10.0.27871.1000] (c) Microsoft Corporation. All rights reserved.(suna-py3.12) F:\PythonProjects\suna>python setup.py --admin███████╗██╗ ██╗███╗ ██╗ █████╗ ██╔════╝…...
Vue 实例的数据对象详解
Vue 实例的数据对象详解 在 Vue 中,数据对象是响应式系统的核心,也是组件状态的载体。理解数据对象的原理和使用方式是成为 Vue 专家的关键一步。我将从多个维度深入剖析 Vue 实例的数据对象。 一、数据对象的定义方式 1. Options API 中的定义 在 Options API 中,使用 …...
自定义线程池1.2
自定义线程池 1.2 1. 简介 上次我们实现了 1.1 版本,将线程池中的线程数量交给使用者决定,并且将线程的创建延迟到任务提交的时候,在本文中我们将对这个版本进行如下的优化: 在新建线程时交给线程一个任务。让线程在某种情况下…...
[QMT量化交易小白入门]-六十二、ETF轮动中简单的评分算法如何获取历史年化收益32.7%
本专栏主要是介绍QMT的基础用法,常见函数,写策略的方法,也会分享一些量化交易的思路,大概会写100篇左右。 QMT的相关资料较少,在使用过程中不断的摸索,遇到了一些问题,记录下来和大家一起沟通,共同进步。 文章目录 相关阅读1. 策略概述2. 趋势评分模块3 代码解析4 木头…...
