计数子岛

夜宇大大_3941

夜宇大大_3941

2024-08-29

981人浏览

转载

1905 年。计算子岛屿

难度:中等

主题:数组、深度优先搜索、广度优先搜索、并集查找、矩阵

给定两个 m x n 二进制矩阵 grid1 和 grid2,其中仅包含 0(代表水)和 1(代表土地)。 岛屿是一组由1连接的4向(水平或垂直)。网格之外的任何细胞都被视为水细胞。

如果 grid1 中的一个岛包含所有构成 grid2 中这个岛的单元格,则 grid2 中的岛被视为子岛 .

返回grid2中被视为子岛的数量个岛屿。

示例1:

计数子岛

  • 输入: 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]], 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]]
  • 输出: 3
  • 说明:
    • 上图中,左边的网格是grid1,右边的网格是grid2。
    • grid2 中红色的 1 被认为是子岛的一部分。共有三个子岛。

示例2:

计数子岛

  • 输入: grid1 = [[1,0,1,0,1],[1,1,1,1,1],[0,0,0,0,0],[1, 1,1,1,1],[1,0,1,0,1]], grid2 = [[0,0,0,0,0],[1,1,1,1,1],[ 0,1,0,1,0],[0,1,0,1,0],[1,0,0,0,1]]
  • 输出: 2
  • 说明:
    • 上图中,左边的网格是grid1,右边的网格是grid2。
    • grid2 中红色的 1 被认为是子岛的一部分。有两个子岛。

约束:

GitHub Actions 工作流调试器
GitHub Actions 工作流调试器

使用 GitHub REST API v3 /actions/runs 和 /actions/jobs 端点诊断失败的 GitHub Actions 工作流程。解析步骤日志,识别 YAML 语法错误,并为运行器环境问题提供修复建议。

下载
  • m == grid1.length == grid2.length
  • n == grid1[i].length == grid2[i].length
  • 1
  • grid1[i][j] 和 grid2[i][j] 为 0 或 1。

提示:

  1. 让我们使用洪水填充来迭代第二个网格的岛屿
  2. 让我们注意,如果第二个网格中的一个岛上的所有单元格都由第一个网格中的土地表示,那么它们就会连接起来,从而使该岛成为一个子岛

解决方案:

我们将使用深度优先搜索 (dfs) 方法来探索 grid2 中的岛屿,并检查每个岛屿是否完全包含在 grid1 中的相应岛屿内。以下是我们实施该解决方案的方法:

步骤:

  1. 遍历网格:我们将迭代 grid2 中的每个单元格。
  2. 识别 grid2 中的岛屿:当我们在 grid2 中遇到陆地单元 (1) 时,我们将使用 dfs 探索整个岛屿。
  3. 检查子岛情况: 在 grid2 中的一个岛屿上执行 dfs 时,我们将检查 grid1 中所有对应的单元格是否也是陆地单元格。如果是的话,该岛就是一个子岛。
  4. 计算子岛数: 对于 grid2 中满足子岛条件的每个岛屿,我们将增加子岛数。

让我们用 php 实现这个解决方案:1905。数一下子岛屿

<?php /**
 * @param $grid1
 * @param $grid2
 * @return int
 */
function countSubIslands($grid1, $grid2) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

/**
 * @param $grid1
 * @param $grid2
 * @param $i
 * @param $j
 * @param $m
 * @param $n
 * @return int|true
 */
function dfs(&$grid1, &$grid2, $i, $j, $m, $n) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:

// Example 1
$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]
];

$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]
];

echo countSubIslands($grid1, $grid2); // Output: 3

// Example 2
$grid1 = [
    [1,0,1,0,1],
    [1,1,1,1,1],
    [0,0,0,0,0],
    [1,1,1,1,1],
    [1,0,1,0,1]
];

$grid2 = [
    [0,0,0,0,0],
    [1,1,1,1,1],
    [0,1,0,1,0],
    [0,1,0,1,0],
    [1,0,0,0,1]
];

echo countSubIslands($grid1, $grid2); // Output: 2
?>

解释:

  • dfs 函数: dfs 函数探索 grid2 中的岛屿,并检查 grid1 中相应的单元格是否都是陆地单元格。如果 grid2 中的任何单元格是陆地,但 grid1 中相应的单元格是水,则 grid2 中的岛屿不是子岛。
  • 标记已访问: 当我们遍历 grid2 时,我们通过将单元格设置为 0 将其标记为已访问。
  • 主循环:我们迭代grid2中的所有单元格。每当我们发现一个尚未访问过的陆地单元时,我们都会启动 dfs 来检查它是否是子岛的一部分。

时间复杂度:

时间复杂度为 (o(m × n)),其中 m 是行数,n 是列数。这是因为我们可能会访问每个单元格一次。

该解决方案应该在给定的限制内有效地工作。

联系链接

如果您发现本系列有帮助,请考虑在 github 上给存储库 一个星星,或在您最喜欢的社交网络上分享该帖子?。您的支持对我来说意义重大!

如果您想要更多类似的有用内容,请随时关注我:

  • 领英
  • github

相关文章

PHP速学视频免费教程(入门到精通)
PHP速学视频免费教程(入门到精通)

PHP怎么学习?PHP怎么入门?PHP在哪学?PHP怎么学才快?不用担心,这里为大家提供了PHP速学教程(入门到精通),有需要的小伙伴保存下载就能学习啦!

下载

相关标签:

git 社交网络

本站声明:本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn

相关专题

更多
length函数用法
length函数用法

length函数用于返回指定字符串的字符数或字节数。可以用于计算字符串的长度,以便在查询和处理字符串数据时进行操作和判断。 需要注意的是length函数计算的是字符串的字符数,而不是字节数。对于多字节字符集,一个字符可能由多个字节组成。因此,length函数在计算字符串长度时会将多字节字符作为一个字符来计算。更多关于length函数的用法,大家可以阅读本专题下面的文章。

2023.09.19

2047

6

github中文官网入口 github中文版官网网页进入
github中文官网入口 github中文版官网网页进入

github中文官网入口https://docs.github.com/zh/get-started,GitHub 是一种基于云的平台,可在其中存储、共享并与他人一起编写代码。 通过将代码存储在GitHub 上的“存储库”中,你可以: “展示或共享”你的工作。 持续“跟踪和管理”对代码的更改。

2026.01.21

9045

27

GitHub官网入口版本汇总
GitHub官网入口版本汇总

本专题整合了GitHub入口版本地址汇总,阅读专题下面的文章了解更多详细内容。

2026.04.02

1078

19

Navicat创建数据库教程
Navicat创建数据库教程

本专题整理Navicat创建数据库相关教程,介绍新建前的准备、基础设置和创建后的检查方法。内容兼顾入门学习及实际使用需求,帮助用户了解不同数据库类型下的操作差异,为后续建表、保存数据和日常管理提供参考。

2026.11.20

0

7

Navicat入门教程大全
Navicat入门教程大全

本专题整理Navicat入门教程,从认识软件界面到开展数据库操作,介绍初次使用需要了解的知识和方法。内容兼顾连接配置、数据管理及日常使用中的疑问,方便用户按学习进度查阅,为后续实践和独立操作打好基础。

2026.11.20

0

17

Navicat数据库连接配置指南
Navicat数据库连接配置指南

从确认数据库信息到建立可用连接,本专题串联Navicat连接数据库的相关知识和操作方法。既有初次配置时需要了解的基础内容,也有连接后的检查思路,方便用户按实际需求查阅教程,逐步熟悉数据库连接的设置流程。

2026.11.20

0

10

PHP8.6数组与数据处理教程
PHP8.6数组与数据处理教程

本专题汇总PHP8.6数组与数据处理教程,涵盖CSV读取和导出、引用遍历删除、array_filter回调模式、配置键名冲突、pathinfo文件名校验、GMP大整数进制转换及UTF-8正则筛选,说明升级兼容变化、输入范围和失败处理方法。

2026.11.20

0

8

PHP8.6升级迁移教程
PHP8.6升级迁移教程

本专题汇总PHP8.6升级迁移与弃用接口改造教程,涵盖反射调用、对象属性赋值、标识符更名、构造函数与__debugInfo调整,以及插件类名检查、常量导出、ArrayIterator排序、SPL和DTO查询参数转换,帮助梳理弃用提示并完成代码兼容改造。

2026.11.20

0

10

PHP8.6安装配置与FPM运维教程
PHP8.6安装配置与FPM运维教程

本专题汇总PHP8.6正式版安装部署与FPM运维教程,涵盖Linux并存安装、独立ini配置、扩展重新编译、Nginx切换与回滚、FPM状态监控和慢日志排查,以及环境变量、请求超时、OPcache刷新和预加载配置。

2026.11.20

0

10

热门下载

更多
网站特效
/
网站源码
/
网站素材
/
前端模板

精品课程

更多
相关推荐
/
热门推荐
/
最新课程
Postman Native Git工作流指南
Postman Native Git工作流指南

共0课时 | 0人学习

vscode手册
vscode手册

共0课时 | 0人学习

Git 教程
Git 教程

共21课时 | 8.2万人学习