IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> 【LeetCode 深度优先搜索专项】不同岛屿的数量(694) -> 正文阅读

[数据结构与算法]【LeetCode 深度优先搜索专项】不同岛屿的数量(694)

1. 题目

给定一个 m × n m \times n m×n 的二维矩阵 grid ,同时将由横向或纵向按边相接的 1 1 1 (代表陆地)所组成的集合视为岛屿,可以假定矩阵区域之外都为海水。

如果两个岛屿可以且仅可以通过平移的方式(不可进行旋转或镜像)覆盖相同的区域,就称这两个岛屿是相同的,要求返回 grid 中不同岛屿的数量。

1.1 示例

  • 示例 1 1 1

    • 输入: grid = [[1, 1, 0, 0, 0], [1, 1, 0, 0, 0], [0, 0, 0, 1, 1], [0, 0, 0, 1, 1]]
    • 输出: 1 1 1

在这里插入图片描述

  • 示例 2 2 2

    • 输入: grid = [[1, 1, 0, 1, 1], [1, 0, 0, 0, 0], [0, 0, 0, 0, 1], [1, 1, 0, 1, 1]]
    • 输出: 3 3 3

在这里插入图片描述

1.2 说明

1.3 提示

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 50
  • grid[i][j] 只会是 0 0 0 或者 1 1 1

1.4 进阶

你可以使用多种方法解答这道题目么?(深度优先搜索、广度优先搜索)

2. 解法一(深度优先搜索)

2.1 分析

很显然得想办法把二维矩阵中的「岛屿」进行转化,变成比如字符串这样的类型,然后利用 set 这样的数据结构去重,最终得到不同的岛屿的个数。

如果想把岛屿转化成字符串,说白了就是序列化,序列化说白了就是遍历。

首先,对于形状相同的岛屿,如果从同一起点出发,深度优先遍历的顺序肯定是一样的。因为遍历顺序是写死在递归函数里面的,不会动态改变;所以,遍历顺序从某种意义上说就可以用来描述岛屿的形状,比如下图这两个岛屿:

在这里插入图片描述
假设它们的遍历顺序是:

下,右,上,撤销上,撤销右,撤销下

如果我用分别用 1 1 1 2 2 2 3 3 3 4 4 4 代表上下左右,用 ? 1 -1 ?1 ? 2 -2 ?2 ? 3 -3 ?3 ? 4 -4 ?4 代表上下左右的撤销(这里的撤销可以理解为递归调用的返回),那么可以这样表示它们的遍历顺序:

2 2 2 4 4 4 1 1 1 ? 1 -1 ?1 ? 4 -4 ?4 ? 2 -2 ?2

最后对不同的遍历顺序进行序列化并去重之后即可得到结果。

2.2 解答

from typing import List
from json import dumps


class Solution:
    def _dfs_flood(self, grid: List[List[int]], path: List[int], i: int, j: int, direction: int):
        m, n = len(grid), len(grid[0])
        if i < 0 or i >= m or j < 0 or j >= n:
            return
        if grid[i][j] == 0:
            return
        path.append(direction)
        grid[i][j] = 0
        self._dfs_flood(grid, path, i - 1, j, 1)
        self._dfs_flood(grid, path, i + 1, j, 2)
        self._dfs_flood(grid, path, i, j - 1, 3)
        self._dfs_flood(grid, path, i, j + 1, 4)
        path.append(-direction)

    def num_distinct_islands(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        islands = set()
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:
                    path = []
                    self._dfs_flood(grid, path, i, j, 0)
                    islands.add(dumps(path))
        return len(islands)


def main():
    grid = [[1, 1, 0, 0, 0], 
            [1, 1, 0, 0, 0], 
            [0, 0, 0, 1, 1], 
            [0, 0, 0, 1, 1]]
    sln = Solution()
    print(sln.num_distinct_islands(grid))  # 2


if __name__ == '__main__':
    main()

2.3 复杂度

  • 时间复杂度: O ( m n ) O(mn) O(mn),其中 m m m n n n 分别为行数和列数。
  • 空间复杂度: O ( m n ) O(mn) O(mn)
  数据结构与算法 最新文章
LeetCode 383 赎金信[数组] HERODING的Leet
matlab中fill函数的使用方法
动态规划总结篇一
LeetCode530 二叉搜索树的最小绝对差
单链表的增删改查
拓扑排序 golang实现
用栈实现队列的功能Java(leetcode)
两数相加
动态规划思路
希尔排序——C++实现
上一篇文章      下一篇文章      查看所有文章
加:2021-10-28 12:36:29  更:2021-10-28 12:38:53 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
360图书馆 购物 三丰科技 阅读网 日历 万年历 2021年12日历 -2021/12/4 20:56:48-
图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码