当前位置: 首页 > 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…...

Python爬虫实战:研究MechanicalSoup库相关技术

一、MechanicalSoup 库概述 1.1 库简介 MechanicalSoup 是一个 Python 库,专为自动化交互网站而设计。它结合了 requests 的 HTTP 请求能力和 BeautifulSoup 的 HTML 解析能力,提供了直观的 API,让我们可以像人类用户一样浏览网页、填写表单和提交请求。 1.2 主要功能特点…...

国防科技大学计算机基础课程笔记02信息编码

1.机内码和国标码 国标码就是我们非常熟悉的这个GB2312,但是因为都是16进制&#xff0c;因此这个了16进制的数据既可以翻译成为这个机器码&#xff0c;也可以翻译成为这个国标码&#xff0c;所以这个时候很容易会出现这个歧义的情况&#xff1b; 因此&#xff0c;我们的这个国…...

谷歌浏览器插件

项目中有时候会用到插件 sync-cookie-extension1.0.0&#xff1a;开发环境同步测试 cookie 至 localhost&#xff0c;便于本地请求服务携带 cookie 参考地址&#xff1a;https://juejin.cn/post/7139354571712757767 里面有源码下载下来&#xff0c;加在到扩展即可使用FeHelp…...

【Oracle APEX开发小技巧12】

有如下需求&#xff1a; 有一个问题反馈页面&#xff0c;要实现在apex页面展示能直观看到反馈时间超过7天未处理的数据&#xff0c;方便管理员及时处理反馈。 我的方法&#xff1a;直接将逻辑写在SQL中&#xff0c;这样可以直接在页面展示 完整代码&#xff1a; SELECTSF.FE…...

Unity3D中Gfx.WaitForPresent优化方案

前言 在Unity中&#xff0c;Gfx.WaitForPresent占用CPU过高通常表示主线程在等待GPU完成渲染&#xff08;即CPU被阻塞&#xff09;&#xff0c;这表明存在GPU瓶颈或垂直同步/帧率设置问题。以下是系统的优化方案&#xff1a; 对惹&#xff0c;这里有一个游戏开发交流小组&…...

前端倒计时误差!

提示:记录工作中遇到的需求及解决办法 文章目录 前言一、误差从何而来?二、五大解决方案1. 动态校准法(基础版)2. Web Worker 计时3. 服务器时间同步4. Performance API 高精度计时5. 页面可见性API优化三、生产环境最佳实践四、终极解决方案架构前言 前几天听说公司某个项…...

基于服务器使用 apt 安装、配置 Nginx

&#x1f9fe; 一、查看可安装的 Nginx 版本 首先&#xff0c;你可以运行以下命令查看可用版本&#xff1a; apt-cache madison nginx-core输出示例&#xff1a; nginx-core | 1.18.0-6ubuntu14.6 | http://archive.ubuntu.com/ubuntu focal-updates/main amd64 Packages ng…...

cf2117E

原题链接&#xff1a;https://codeforces.com/contest/2117/problem/E 题目背景&#xff1a; 给定两个数组a,b&#xff0c;可以执行多次以下操作&#xff1a;选择 i (1 < i < n - 1)&#xff0c;并设置 或&#xff0c;也可以在执行上述操作前执行一次删除任意 和 。求…...

HBuilderX安装(uni-app和小程序开发)

下载HBuilderX 访问官方网站&#xff1a;https://www.dcloud.io/hbuilderx.html 根据您的操作系统选择合适版本&#xff1a; Windows版&#xff08;推荐下载标准版&#xff09; Windows系统安装步骤 运行安装程序&#xff1a; 双击下载的.exe安装文件 如果出现安全提示&…...

VTK如何让部分单位不可见

最近遇到一个需求&#xff0c;需要让一个vtkDataSet中的部分单元不可见&#xff0c;查阅了一些资料大概有以下几种方式 1.通过颜色映射表来进行&#xff0c;是最正规的做法 vtkNew<vtkLookupTable> lut; //值为0不显示&#xff0c;主要是最后一个参数&#xff0c;透明度…...