当前位置: 首页 > news >正文

图论06-飞地的数量(Java)

6.飞地的数量

  • 题目描述

给你一个大小为 m x n 的二进制矩阵 grid ,其中 0 表示一个海洋单元格、1 表示一个陆地单元格。

一次 移动 是指从一个陆地单元格走到另一个相邻(上、下、左、右)的陆地单元格或跨过 grid 的边界。

返回网格中 无法 在任意次数的移动中离开网格边界的陆地单元格的数量。

示例 1:

img

输入:grid = [[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]]
输出:3
解释:有三个 10 包围。一个 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 &#xff0c;其中 0 表示一个海洋单元格、1 表示一个陆地单元格。 一次 移动 是指从一个陆地单元格走到另一个相邻&#xff08;上、下、左、右&#xff09;的陆地单元格或跨过 grid 的边界。 返回网格中 无法…...

Java设计模式之单例设计模式

单例设计模式就是保证整个软件系统中&#xff0c;某个类只能存在一个对象实例&#xff0c;并且该类只提供一个取得该对象的方法。 单例设计模式包括两种&#xff1a;饿汉式和懒汉式。 饿汉式&#xff1a; 含义&#xff1a; 在类加载时就创建并初始化单例对象。这种方式确保了…...

多维时序 | MATLAB实现BiTCN-selfAttention自注意力机制结合双向时间卷积神经网络多变量时间序列预测

多维时序 | MATLAB实现BiTCN-selfAttention自注意力机制结合双向时间卷积神经网络多变量时间序列预测 目录 多维时序 | MATLAB实现BiTCN-selfAttention自注意力机制结合双向时间卷积神经网络多变量时间序列预测预测效果基本介绍模型描述程序设计参考资料 预测效果 基本介绍 1.M…...

深入了解Android垃圾回收机制

文章目录 一、内存分配二、垃圾回收触发条件三、GC算法3.1 Dalvik虚拟机的GC算法3.2 ART的GC算法 四、优化GC性能五、监控GC耗时情况六、总结 在Android应用开发中&#xff0c;内存管理和垃圾回收&#xff08;GC&#xff09;对于应用性能和稳定性至关重要。理解GC机制有助于我们…...

如何学好Python语言

学习Python&#xff1a;一场充满探索与实践的编程之旅 Python&#xff0c;作为一种解释型、交互式和面向对象的编程语言&#xff0c;近年来在数据科学、人工智能、Web开发等多个领域得到了广泛的应用。掌握Python&#xff0c;不仅可以提升个人的编程技能&#xff0c;还能够为未…...

计算机408网课评测+资料分享

408当然有比较好的网课推荐&#xff0c;比如王道的视频课 现在大部分人备战408基本都用王道的讲义&#xff0c;然后再搭配王道408的课程来听&#xff0c;可以学的很好。 其中408视频课中&#xff0c;我认为讲的比较好的是数据结构&#xff0c;和操作系统&#xff0c;计算机组…...

使用 ZipArchiveInputStream 读取压缩包内文件总数

读取压缩包内文件总数 简介 ZipArchiveInputStream 是 Apache Commons Compress 库中的一个类&#xff0c;用于读取 ZIP 格式的压缩文件。在处理 ZIP 文件时&#xff0c;编码格式是一个重要的问题&#xff0c;因为它决定了如何解释文件中的字符数据。通常情况下&#xff0c;Z…...

JavaScript对象修饰教程

在JavaScript中&#xff0c;对象修饰是一种常见的编程模式&#xff0c;用于动态地向对象添加新的功能或修改现有功能&#xff0c;同时保持对象的原始结构不变。对象修饰可以帮助我们实现代码的复用、扩展和维护&#xff0c;让代码更加灵活和可扩展。本文将深入探讨JavaScript对…...

转置卷积(transposed-conv)

一、什么是转置卷积 1、转置卷积的背景 通常&#xff0c;对图像进行多次卷积运算后&#xff0c;特征图的尺寸会不断缩小。而对于某些特定任务 (如图像分割和图像生成等)&#xff0c;需将图像恢复到原尺寸再操作。这个将图像由小分辨率映射到大分辨率的尺寸恢复操作&#xff0c…...

P1481 魔族密码

P1481 魔族密码 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 字典树 在插入字符串 s s s时&#xff0c;不断记录 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)

这是一篇碎碎念&#xff0c;零零碎碎的记录了环境配置过程&#xff0c;仅供本人记录学习历程和参考。(记录的挺乱的&#xff0c;但是文章链接里的博客写的是真好) 本章主要完成的目标&#xff1a; 安装PX4 并 成功运行出3D无人机界面。 参考文章&#xff1a; 搭建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. 抄袭查找(结构体+指针+函数)

题目描述 已知一群学生的考试试卷&#xff0c;要求对试卷内容进行对比&#xff0c;查找是否有抄袭。 每张试卷包含&#xff1a;学号&#xff08;整数类型&#xff09;、题目1答案&#xff08;字符串类型&#xff09;、题目2答案&#xff08;字符串类型&#xff09;、题目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包冲突解决

&#x1f60a; 作者&#xff1a; 一恍过去 &#x1f496; 主页&#xff1a; https://blog.csdn.net/zhuocailing3390 &#x1f38a; 社区&#xff1a; Java技术栈交流 &#x1f389; 主题&#xff1a; SpringBoot3整合Mybatis-Plus与PageHelper包冲突解决 ⏱️ 创作时间&a…...

MQTT Keep Alive机制

MQTT 协议是承载于 TCP 协议之上的&#xff0c; 而 TCP 协议以连接为导向&#xff0c; 在连接双方之间&#xff0c; 提供稳定、 有序的字节流功能。 但是&#xff0c; 在部分情况下&#xff0c; TCP 可能出现半连接问题。 所谓半连接&#xff0c; 是指某一方的连接已经断开或者…...

基于springboot+vue的游戏交易系统

博主主页&#xff1a;猫头鹰源码 博主简介&#xff1a;Java领域优质创作者、CSDN博客专家、阿里云专家博主、公司架构师、全网粉丝5万、专注Java技术领域和毕业设计项目实战&#xff0c;欢迎高校老师\讲师\同行交流合作 ​主要内容&#xff1a;毕业设计(Javaweb项目|小程序|Pyt…...

高职(大专)结构化面试之答题思路

目录 一、岗位认知 二、职教热点 三、教育教学 四、人际关系 五、组织管理 六、应急应变 七、时政与教育 八、专业知识 一、岗位认知 考试方向&#xff1a;主要考察对岗位的全面认识、职业目标、职业规划、职业理想。 必背题目&#xff1a; 1.“你为什么要报考我们学校的教师岗…...

Python基础学习笔记(一)

Python简介 Python 语言是一种跨平台、开源、免费、解释型、面向对象、动态数据类型的高级程序设计语言。早期版本的 Python 被称作是 Python1&#xff1b;Python2 最后一个版本是 2.7&#xff1b;Python3 是目前最活跃的版 本&#xff0c;基本上新开发的 Python 代码都会支持…...

机器学习-可解释性机器学习:支持向量机与fastshap的可视化模型解析

一、引言 支持向量机(Support Vector Machine, SVM)作为一种经典的监督学习方法&#xff0c;在分类和回归问题中表现出色。其优点之一是生成的模型具有较好的泛化能力和可解释性&#xff0c;能够清晰地展示特征对于分类的重要性。 fastshap是一种用于快速计算SHAP值&#xff08…...

Zynq裸机调试RTL8211FS网口,从ping不通到ping通的踩坑与填坑记录

Zynq裸机调试RTL8211FS网口的深度排错指南 当你在Zynq平台上第一次尝试让RTL8211FS PHY芯片工作时&#xff0c;可能会遇到一个令人沮丧的现象——网口指示灯亮了&#xff0c;但就是ping不通。这不是简单的驱动适配问题&#xff0c;而是一场需要耐心和系统思维的硬件调试之旅。 …...

全球非洲科技展聚焦非洲数字化发展

“2026全球非洲科技展”3月28日在阿尔及利亚首都阿尔及尔开幕&#xff0c;本次展会聚焦推动非洲数字基础设施建设和促进非洲技术主权。 联合国副秘书长、秘书长数字和新兴技术特使阿曼迪普辛格吉尔在开幕致辞中表示&#xff0c;非洲各国应携手合作&#xff0c;制定自己的人工智…...

QTTabBar多语言配置完整指南:快速实现Windows文件管理器本地化

QTTabBar多语言配置完整指南&#xff1a;快速实现Windows文件管理器本地化 【免费下载链接】qttabbar QTTabBar is a small tool that allows you to use tab multi label function in Windows Explorer. https://www.yuque.com/indiff/qttabbar 项目地址: https://gitcode.c…...

生成式AI应用用户流失率飙升的真正原因:不是模型不准,而是这6个隐性体验缺口未被填补

第一章&#xff1a;生成式AI应用用户体验设计的核心范式转变 2026奇点智能技术大会(https://ml-summit.org) 传统UI/UX设计以“确定性交互”为前提——用户操作触发预设响应&#xff0c;界面状态可穷举、反馈可预测。生成式AI彻底颠覆了这一根基&#xff1a;系统输出具有概率性…...

05华夏之光永存:(院士视角)华为未来十年算力生态前瞻 昇腾+盘古·算力与大模型端边云协同落地

华夏之光永存&#xff1a;华为未来十年算力生态前瞻系列第5篇 昇腾盘古算力与大模型端边云协同落地 一、摘要 昇腾芯片提供底层算力支撑&#xff0c;盘古大模型输出智能决策能力&#xff0c;二者协同是华为未来十年算力生态实现规模化、高效化、全场景落地的核心组合。本文聚焦…...

Ubuntu自动安装ISO生成器:3步实现无人值守系统部署

Ubuntu自动安装ISO生成器&#xff1a;3步实现无人值守系统部署 【免费下载链接】ubuntu-autoinstall-generator Generate a fully-automated Ubuntu ISO for unattended installations. 项目地址: https://gitcode.com/gh_mirrors/ub/ubuntu-autoinstall-generator 还在…...

浙江大学提出“少即是多“:让AI减少细节反而看得更清楚

这项由浙江大学国家CAD&CG重点实验室领导的研究发表于2026年4月的arXiv预印本平台&#xff08;论文编号&#xff1a;arXiv:2604.04838v1&#xff09;&#xff0c;有兴趣深入了解的读者可以通过该编号查询完整论文。研究团队在视觉语言模型&#xff08;VLM&#xff09;领域取…...

07_NVIDIA Triton Java API:企业级高性能推理服务

NVIDIA Triton Java API&#xff1a;企业级高性能推理服务 摘要&#xff1a;NVIDIA Triton 是业界最先进的模型推理服务软件&#xff0c;支持多框架并发执行和动态批处理。本文深入解析 Triton 架构、Java API 的两种形态、TensorRT-LLM 后端集成&#xff0c;以及如何构建高性能…...

HPH的构造全解析

HPH身为一种至关重要的工程结构&#xff0c;其内部所具备的构造直接对设备的安全性以及运行效率起着决定性作用。对于从事相关领域工作的技术人员而言&#xff0c;透彻理解HPH的组成逻辑以及设计原理是极为关键的。本文会从核心部件、密封机制和安全设计这三个维度入手&#xf…...

如何用3分钟免费备份你的QQ空间所有历史说说?GetQzonehistory终极指南

如何用3分钟免费备份你的QQ空间所有历史说说&#xff1f;GetQzonehistory终极指南 【免费下载链接】GetQzonehistory 获取QQ空间发布的历史说说 项目地址: https://gitcode.com/GitHub_Trending/ge/GetQzonehistory 在数字记忆日益珍贵的今天&#xff0c;你是否担心QQ空…...