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

深入浅出Asp.Net Core MVC应用开发系列-AspNetCore中的日志记录

ASP.NET Core 是一个跨平台的开源框架&#xff0c;用于在 Windows、macOS 或 Linux 上生成基于云的新式 Web 应用。 ASP.NET Core 中的日志记录 .NET 通过 ILogger API 支持高性能结构化日志记录&#xff0c;以帮助监视应用程序行为和诊断问题。 可以通过配置不同的记录提供程…...

云计算——弹性云计算器(ECS)

弹性云服务器&#xff1a;ECS 概述 云计算重构了ICT系统&#xff0c;云计算平台厂商推出使得厂家能够主要关注应用管理而非平台管理的云平台&#xff0c;包含如下主要概念。 ECS&#xff08;Elastic Cloud Server&#xff09;&#xff1a;即弹性云服务器&#xff0c;是云计算…...

IGP(Interior Gateway Protocol,内部网关协议)

IGP&#xff08;Interior Gateway Protocol&#xff0c;内部网关协议&#xff09; 是一种用于在一个自治系统&#xff08;AS&#xff09;内部传递路由信息的路由协议&#xff0c;主要用于在一个组织或机构的内部网络中决定数据包的最佳路径。与用于自治系统之间通信的 EGP&…...

汇编常见指令

汇编常见指令 一、数据传送指令 指令功能示例说明MOV数据传送MOV EAX, 10将立即数 10 送入 EAXMOV [EBX], EAX将 EAX 值存入 EBX 指向的内存LEA加载有效地址LEA EAX, [EBX4]将 EBX4 的地址存入 EAX&#xff08;不访问内存&#xff09;XCHG交换数据XCHG EAX, EBX交换 EAX 和 EB…...

pikachu靶场通关笔记22-1 SQL注入05-1-insert注入(报错法)

目录 一、SQL注入 二、insert注入 三、报错型注入 四、updatexml函数 五、源码审计 六、insert渗透实战 1、渗透准备 2、获取数据库名database 3、获取表名table 4、获取列名column 5、获取字段 本系列为通过《pikachu靶场通关笔记》的SQL注入关卡(共10关&#xff0…...

Python 包管理器 uv 介绍

Python 包管理器 uv 全面介绍 uv 是由 Astral&#xff08;热门工具 Ruff 的开发者&#xff09;推出的下一代高性能 Python 包管理器和构建工具&#xff0c;用 Rust 编写。它旨在解决传统工具&#xff08;如 pip、virtualenv、pip-tools&#xff09;的性能瓶颈&#xff0c;同时…...

九天毕昇深度学习平台 | 如何安装库?

pip install 库名 -i https://pypi.tuna.tsinghua.edu.cn/simple --user 举个例子&#xff1a; 报错 ModuleNotFoundError: No module named torch 那么我需要安装 torch pip install torch -i https://pypi.tuna.tsinghua.edu.cn/simple --user pip install 库名&#x…...

Fabric V2.5 通用溯源系统——增加图片上传与下载功能

fabric-trace项目在发布一年后,部署量已突破1000次,为支持更多场景,现新增支持图片信息上链,本文对图片上传、下载功能代码进行梳理,包含智能合约、后端、前端部分。 一、智能合约修改 为了增加图片信息上链溯源,需要对底层数据结构进行修改,在此对智能合约中的农产品数…...

C++课设:简易日历程序(支持传统节假日 + 二十四节气 + 个人纪念日管理)

名人说:路漫漫其修远兮,吾将上下而求索。—— 屈原《离骚》 创作者:Code_流苏(CSDN)(一个喜欢古诗词和编程的Coder😊) 专栏介绍:《编程项目实战》 目录 一、为什么要开发一个日历程序?1. 深入理解时间算法2. 练习面向对象设计3. 学习数据结构应用二、核心算法深度解析…...

tomcat入门

1 tomcat 是什么 apache开发的web服务器可以为java web程序提供运行环境tomcat是一款高效&#xff0c;稳定&#xff0c;易于使用的web服务器tomcathttp服务器Servlet服务器 2 tomcat 目录介绍 -bin #存放tomcat的脚本 -conf #存放tomcat的配置文件 ---catalina.policy #to…...