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

统计子岛屿的数量

统计子岛屿

题目描述

给你两个 m x n 的二进制矩阵 grid1 和 grid2 ,它们只包含 0 (表示水域)和 1 (表示陆地)。一个 岛屿 是由 四个方向 (水平或者竖直)上相邻的 1 组成的区域。任何矩阵以外的区域都视为水域。

如果 grid2 的一个岛屿,被 grid1 的一个岛屿 完全 包含,也就是说 grid2 中该岛屿的每一个格子都被 grid1 中同一个岛屿完全包含,那么我们称 grid2 中的这个岛屿为 子岛屿 。

请你返回 grid2 中 子岛屿 的 数目 。

在这里插入图片描述
在这里插入图片描述

思路:

对于(i, j)来说,有四种情况

case1:grid1[i][j] = 1, grid2[i][j] = 1.

case2:grid1[i][j] = 1, grid2[i][j] = 0.

case3: grid1[i][j] = 0, grid2[i][j] = 1.

case4: grid1[i][j] = 0, grid2[i][j] = 0.

对于case4,我们完全不用关心;剩下的case1、case2、case3我们再看,由于是grid1包含grid2,对于case3,如果grid2是陆地,grid1是海水,那么grid1就不包含grid2,那么我们就可以提前干掉grid2中的点;对于case2,如果grid1是陆地,grid2是海水,那么grid2必然不是grid1的子岛,我们可以不做任何操作;对于case1,那么grid2必然是grid1的子岛,我们就计数,然后dfs。

下面看代码:

	public int countSubIslands(int[][] grid1, int[][] grid2) {int m = grid1.length, n = grid1[0].length, count = 0;// 先排除不是子岛屿的节点for(int i = 0;i < m;i++){for(int j = 0;j < n;j++){if(grid2[i][j] == 1 && grid1[i][j] == 0){dfs(grid2, i, j, m, n);}}}System.out.println("======");for(int i = 0;i < m;i++){for(int j = 0;j < n;j++){// 对于条件case1和case2来说// 这块可以优化成if(grid2[i][j] == 1)if(grid2[i][j] == 1 && grid1[i][j] == 1){count++;dfs(grid2, i, j, m, n);}}}return count;}public void dfs(int[][] grid, int i, int j, int m, int n){if(i >= m || i < 0 || j >= n || j < 0|| grid[i][j] == 0 ){return;}grid[i][j] = 0;dfs(grid, i + 1, j, m, n);dfs(grid, i - 1, j, m, n);dfs(grid, i, j + 1, m, n);dfs(grid, i, j - 1, m, n);}public static void main(String[] args) {int[][] grid1 = {{1,1,1,0,0},{0,1,1,1,1},{0,0,0,0,0},{1,0,0,0,0},{1,1,0,1,1}};int[][] grid2 = {{1,1,1,0,0},{0,0,1,1,1},{0,1,0,0,0},{1,0,1,1,0},{0,1,0,1,0}};CountSubIslands countSubIslands = new CountSubIslands();countSubIslands.countSubIslands(grid1, grid2);}

相关文章:

统计子岛屿的数量

统计子岛屿 题目描述 给你两个 m x n 的二进制矩阵 grid1 和 grid2 &#xff0c;它们只包含 0 &#xff08;表示水域&#xff09;和 1 &#xff08;表示陆地&#xff09;。一个 岛屿 是由 四个方向 &#xff08;水平或者竖直&#xff09;上相邻的 1 组成的区域。任何矩阵以外…...

IntelliJ IDEA Maven 项目的依赖分析

在一个 maven 的项目中&#xff0c;我们需要知道我们的项目中使用的包可能有哪些冲突。 这个在 IntelliJ IDEA 中提供了贴心的查看。 选择 Maven 项目中的分析依赖。 随后&#xff0c;IntelliJ IDEA 将会打开一个依赖分析的标签页。 在这个标签页中&#xff0c;我们可以看到…...

数学建模、统计建模、计量建模整体框架的理解以及建模的步骤

数学建模、统计建模、计量建模整体框架的理解以及建模的步骤 引言正文模型的设定模型的估计建模中可能遇到的四种数据类型 模型的检验模型的应用 最后 引言 这篇博客主要写给统计或者数学专业的小白&#xff0c;以供快速上手建模比赛&#xff1b;本人将在这里整合参加建模比赛…...

WaitGroup原理分析

背景 在实际业务开发中&#xff0c;我们会遇到以下场景&#xff1a;请求数据库&#xff0c;批量获取1000条数据记录后&#xff0c;处理数据 为了减少因一次批量获取的数据太多&#xff0c;导致的数据库延时增加&#xff0c;我们可以把一次请求拆分成多次请求&#xff0c;并发去…...

java直播源码:如何使用Java构建一个高效的直播系统

Java直播源码是一种用于实现实时视频流传输的技术&#xff0c;它可以将视频流从一个地方传送到另一个地方。它使用Java语言编写&#xff0c;可以支持多种视频格式&#xff0c;如MPEG、H.264等。 Java直播源码是一种用于实现实时视频流传输的技术&#xff0c;它可以将视频流从一…...

Websocket获取B站直播间弹幕教程——第二篇、解包/拆包

教程一、Websocket获取B站直播间弹幕教程 — 哔哩哔哩直播开放平台 1、封包 我们连接上B站Websocket成功后&#xff0c;要做两件事情&#xff1a; 第一、发送鉴权包。第二、发送心跳包&#xff0c;每30秒一次&#xff0c;维持websocket连接。 这两个包不是直接发送过去&…...

膝关节检测之1设计目标手势与物体交互的动画

原来只用unity自带的IK&#xff0c;发现背部不能动&#xff0c;且手和手指的移动和旋转试了好像没法通过animation实现&#xff08;加入关键帧并修改最终状态的数值后播放没有变化&#xff0c;确定最终关键帧的数值已经改了的&#xff09;。看资料&#xff0c;发现final IK&…...

canvas力导布局

老规矩&#xff0c;先上效果图 <html><head><style>* {margin: 0;padding: 0;}canvas {display: block;width: 100%;height: 100%;background: #000;}</style> </head><body><canvas id"network"></canvas> </…...

【网络安全】「漏洞原理」(二)SQL 注入漏洞之理论讲解

前言 严正声明&#xff1a;本博文所讨论的技术仅用于研究学习&#xff0c;旨在增强读者的信息安全意识&#xff0c;提高信息安全防护技能&#xff0c;严禁用于非法活动。任何个人、团体、组织不得用于非法目的&#xff0c;违法犯罪必将受到法律的严厉制裁。 【点击此处即可获…...

JavaScript中类的学习

一、JavaScript中的类 1.什么是类 类描述了一种代码的组织结构形式&#xff0c;不同的语言中对其实现形式各有差异。JavaScript中的类Class实际是一种描述对象之间引用关系的语法糖。 在Class语法糖出现之前&#xff0c;我们想重用一个功能模块&#xff0c;通常是用一个函数来…...

1600*A. Linova and Kingdom(DFS优先队列贪心)

Problem - 1336A - Codeforces Linova and Kingdom - 洛谷 解析&#xff1a; 开始认为分情况讨论 k 小于等于叶子结点和大于叶子结点的情况&#xff0c;然后选择深度最深的叶子结点和子孙数量最小的结点&#xff0c;但是发现如果把某一个非叶子结点选取&#xff0c;那么其子孙…...

gitlab git lfs的替代软件整理汇总及分析

文章目录 前言替代软件分析git-annexgit-fatgit-symgit-meida 总结 前言 git-lfs科普 Git LFS&#xff08;Large File Storage&#xff09;是一个Git扩展&#xff0c;用于管理大型文件。Git LFS通过将大型文件存储在Git仓库之外&#xff0c;从而加快了Git操作的速度。它使用指…...

IDEA 2023.2.2图文安装教程及下载

IDE 系列的第二个年度更新现已发布&#xff0c;涵盖 IntelliJ IDEA、WebStorm、PyCharm、DataGrip、GoLand、DataSpell 以及 All Products Pack 订阅中包含的其他工具。该版本还包括多项用户体验增强功能&#xff0c;例如 Search Everywhere&#xff08;随处搜索&#xff09;中…...

第六届“中国法研杯”司法人工智能挑战赛

解锁司法科技的未来 “中国法研杯”司法人工智能挑战赛&#xff08;Legal AI Challenge&#xff0c;简称LAIC&#xff09;&#xff0c;是面向法院侧人工智能应用领域唯一权威比赛&#xff0c;大赛愿景是在拥有全球最大规模司法数据的中国&#xff0c;实现法律界、学术界、产业界…...

Springcloud中间件-----分布式搜索引擎 Elasticsearch

该笔记是根据黑马程序员的课来自己写了一遍的,b站有对应教程和资料 第一部分 第二部分 第三部分 预计看完跟着练习5小时足够 1.初识elasticsearch 1.1.了解ES 1.1.1.elasticsearch的作用 elasticsearch是一款非常强大的开源搜索引擎&#xff0c;具备非常多强大功能&#xff…...

基于深度学习的目标检测和语义分割:机器视觉中的最新进展

基于深度学习的目标检测和语义分割是机器视觉领域的两个重要任务&#xff0c;它们在图像处理、自动驾驶、医学影像分析和智能视频监控等应用中发挥着关键作用。以下是这两个领域的最新进展&#xff1a; 目标检测&#xff08;Object Detection&#xff09;&#xff1a; 一阶段检…...

微信小程序报错request:fail -2:net::ERR_FAILED(生成中间证书)

微信小程序报错request:fail -2:net::ERR_FAILED-生成中间证书 前言一、检查网站ssl证书二、生成证书方法1.获取中间证书手动合并1.进入网站&#xff1a;[https://www.myssl.cn/tools/downloadchain.html](https://www.myssl.cn/tools/downloadchain.html)2.点击下一步3.手动合…...

Ubuntu更改时区

sudo apt install tzdata 进行安装时区&#xff0c;有很多时区可供选择。 然后执行:tzselect rootd75c94dcd226:/# date 2023年 10月 11日 星期三 06:25:12 UTC rootd75c94dcd226:/# tzselect Please identify a location so that time zone rules can be set correctly. Ple…...

0144 文件管理

目录 4.文件管理 4.1文件系统基础 4.2目录 4.3文件系统 部分习题 4.文件管理 4.1文件系统基础 4.2目录 4.3文件系统 部分习题 1.UNIX操作系统忠&#xff0c;输入/输出设备视为&#xff08;&#xff09; A.普通文件 B.目录文件 C.索引文件 D.特殊文…...

python psutil库之——获取网络信息(网络接口信息、网络配置信息、以太网接口、ip信息、ip地址信息)

文章目录 使用Python psutil库获取网络信息安装psutil库获取网络连接信息查看所有网络连接过滤特定状态的连接 获取网络接口信息获取网络IO统计信息实例1实例2 总结 使用Python psutil库获取网络信息 Python的psutil库是一个跨平台库&#xff0c;能够方便地获取系统使用情况和…...

【kafka】Golang实现分布式Masscan任务调度系统

要求&#xff1a; 输出两个程序&#xff0c;一个命令行程序&#xff08;命令行参数用flag&#xff09;和一个服务端程序。 命令行程序支持通过命令行参数配置下发IP或IP段、端口、扫描带宽&#xff0c;然后将消息推送到kafka里面。 服务端程序&#xff1a; 从kafka消费者接收…...

visual studio 2022更改主题为深色

visual studio 2022更改主题为深色 点击visual studio 上方的 工具-> 选项 在选项窗口中&#xff0c;选择 环境 -> 常规 &#xff0c;将其中的颜色主题改成深色 点击确定&#xff0c;更改完成...

拉力测试cuda pytorch 把 4070显卡拉满

import torch import timedef stress_test_gpu(matrix_size16384, duration300):"""对GPU进行压力测试&#xff0c;通过持续的矩阵乘法来最大化GPU利用率参数:matrix_size: 矩阵维度大小&#xff0c;增大可提高计算复杂度duration: 测试持续时间&#xff08;秒&…...

在web-view 加载的本地及远程HTML中调用uniapp的API及网页和vue页面是如何通讯的?

uni-app 中 Web-view 与 Vue 页面的通讯机制详解 一、Web-view 简介 Web-view 是 uni-app 提供的一个重要组件&#xff0c;用于在原生应用中加载 HTML 页面&#xff1a; 支持加载本地 HTML 文件支持加载远程 HTML 页面实现 Web 与原生的双向通讯可用于嵌入第三方网页或 H5 应…...

android13 app的触摸问题定位分析流程

一、知识点 一般来说,触摸问题都是app层面出问题,我们可以在ViewRootImpl.java添加log的方式定位;如果是touchableRegion的计算问题,就会相对比较麻烦了,需要通过adb shell dumpsys input > input.log指令,且通过打印堆栈的方式,逐步定位问题,并找到修改方案。 问题…...

Linux系统部署KES

1、安装准备 1.版本说明V008R006C009B0014 V008&#xff1a;是version产品的大版本。 R006&#xff1a;是release产品特性版本。 C009&#xff1a;是通用版 B0014&#xff1a;是build开发过程中的构建版本2.硬件要求 #安全版和企业版 内存&#xff1a;1GB 以上 硬盘&#xf…...

WPF八大法则:告别模态窗口卡顿

⚙️ 核心问题&#xff1a;阻塞式模态窗口的缺陷 原始代码中ShowDialog()会阻塞UI线程&#xff0c;导致后续逻辑无法执行&#xff1a; var result modalWindow.ShowDialog(); // 线程阻塞 ProcessResult(result); // 必须等待窗口关闭根本问题&#xff1a…...

算法打卡第18天

从中序与后序遍历序列构造二叉树 (力扣106题) 给定两个整数数组 inorder 和 postorder &#xff0c;其中 inorder 是二叉树的中序遍历&#xff0c; postorder 是同一棵树的后序遍历&#xff0c;请你构造并返回这颗 二叉树 。 示例 1: 输入&#xff1a;inorder [9,3,15,20,7…...

Matlab实现任意伪彩色图像可视化显示

Matlab实现任意伪彩色图像可视化显示 1、灰度原始图像2、RGB彩色原始图像 在科研研究中&#xff0c;如何展示好看的实验结果图像非常重要&#xff01;&#xff01;&#xff01; 1、灰度原始图像 灰度图像每个像素点只有一个数值&#xff0c;代表该点的​​亮度&#xff08;或…...

轻量级Docker管理工具Docker Switchboard

简介 什么是 Docker Switchboard &#xff1f; Docker Switchboard 是一个轻量级的 Web 应用程序&#xff0c;用于管理 Docker 容器。它提供了一个干净、用户友好的界面来启动、停止和监控主机上运行的容器&#xff0c;使其成为本地开发、家庭实验室或小型服务器设置的理想选择…...