图论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值(…...
MIPI CSI-2 信号完整性实战:从波形抓取到问题定位
1. MIPI CSI-2信号完整性调试的核心挑战 调试MIPI CSI-2接口就像给高速运行的列车做体检——信号以Gbps级速度传输,任何细微的硬件问题都会导致图像传输失败。我遇到过最典型的案例是:某4K摄像头模组在实验室测试正常,量产时却出现随机花屏。…...
TEKLauncher深度解析:如何打造ARK生存进化终极启动器
TEKLauncher深度解析:如何打造ARK生存进化终极启动器 【免费下载链接】TEKLauncher Launcher for ARK: Survival Evolved 项目地址: https://gitcode.com/gh_mirrors/te/TEKLauncher ARK: Survival Evolved作为一款深受玩家喜爱的大型多人在线生存游戏&#…...
Rust的迭代器适配器与消费者在流式处理中的零拷贝设计
Rust的迭代器适配器与消费者在流式处理中的零拷贝设计,是现代高性能编程中的关键技术。通过迭代器链的组合与惰性求值,Rust能够在处理数据流时避免不必要的内存复制,显著提升性能。这种设计尤其适用于网络协议解析、文件处理等场景࿰…...
CSS如何让多个元素在一行显示_灵活使用float属性
float让元素排成一行失败的核心原因是脱离文档流致父容器塌陷;需触发BFC(如overflow:hidden)、子元素设width、慎用clear:both位置、响应式中须重置float/clear。float让多个元素排成一行的典型失败场景直接给多个 div 加 float: left&#x…...
告别字幕烦恼:B站CC字幕下载转换终极指南
告别字幕烦恼:B站CC字幕下载转换终极指南 【免费下载链接】BiliBiliCCSubtitle 一个用于下载B站(哔哩哔哩)CC字幕及转换的工具; 项目地址: https://gitcode.com/gh_mirrors/bi/BiliBiliCCSubtitle 还在为无法保存B站视频字幕而苦恼吗?想要将精彩的…...
多模态导航商业化落地倒计时:3类高毛利场景+2套ROI测算模型(附奇点大会独家评估矩阵)
第一章:2026奇点智能技术大会:多模态导航应用 2026奇点智能技术大会(https://ml-summit.org) 多模态导航的技术基座 本届大会首次公开了基于统一时空表征的多模态导航框架「NexusNav」,该框架融合视觉、激光雷达、IMU、语义地图与自然语言指…...
IDEA2023.1.2集成Jrebel与XRebel热部署全攻略
1. 为什么需要Jrebel与XRebel热部署? 作为一个写了十几年Java的老码农,我经历过无数次修改代码→重启服务→刷新页面的痛苦循环。特别是开发微服务项目时,改个字段名都要等上两三分钟。直到遇到Jrebel,才真正体会到什么叫"代…...
电机控制:PWM 原理与应用
电机控制:PWM原理与应用 在现代工业自动化和智能设备中,电机控制技术扮演着至关重要的角色。其中,脉宽调制(PWM)技术因其高效、灵活的特点,成为电机控制的核心手段之一。无论是家用电器中的风扇调速&#…...
从SMS网格到FVCOM输入:.grd与.2dm文件结构解析与实战转换指南
1. 认识SMS网格文件与FVCOM输入需求 搞海洋数值模拟的朋友们都知道,FVCOM作为常用的三维海洋环流模型,对输入网格文件有着特定要求。而SMS(Surface-water Modeling System)则是我们最常用的网格生成工具之一。在实际项目中&#x…...
工业 AI 产品对比:研发与生产场景选型思路解析
工业 AI 市场产品类型多样,不同方案在场景适配、功能落地、易用性、安全性等方面存在明显差异。企业在选型时,通常聚焦图纸管理、SOP 标准化两大高频场景,对比维度包括场景贴合度、操作门槛、数据安全、扩展能力等。本文结合市场现状…...
