力扣第695题 岛屿的最大面积 C++ DFS BFS 附Java代码

题目

695. 岛屿的最大面积

中等

相关标签

深度优先搜索   广度优先搜索   并查集   数组   矩阵

给你一个大小为 m x n 的二进制矩阵 grid 。

岛屿 是由一些相邻的 1 (代表土地) 构成的组合,这里的「相邻」要求两个 1 必须在 水平或者竖直的四个方向上 相邻。你可以假设 grid 的四个边缘都被 0(代表水)包围着。

岛屿的面积是岛上值为 1 的单元格的数目。

计算并返回 grid 中最大的岛屿面积。如果没有岛屿,则返回面积为 0 。

示例 1:

输入:grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]]
输出:6
解释:答案不应该是 11 ,因为岛屿只能包含水平或垂直这四个方向上的 1。

示例 2:

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

提示:

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 50
  • grid[i][j] 为 0 或 1

思路和解题方法 1 DFS

  1. dfs 函数通过传入的坐标 (x, y) 来探索当前陆地区域的情况。如果当前坐标越界(超出了网格范围)或者是海洋(值为 0),则返回面积 0,表示此处不是陆地。

  2. 如果当前坐标是陆地(值为 1),则将其标记为已访问过(即将值置为 0),以免重复访问同一块陆地。然后开始向当前位置的上、下、左、右四个方向进行深度优先搜索,探索与当前陆地相连的其他陆地。

  3. 在每一步深度优先搜索中,我们累加当前陆地的面积,并递归地探索相邻的陆地。这样,通过深度优先搜索,我们能够计算出以当前位置为起点的整个连通陆地区域的面积。

  4. 最后,将累计的面积作为返回值返回给上一级递归调用。

maxAreaOfIsland 函数中,我们遍历整个网格,对于每个岛屿的起始位置(即值为 1 的位置),调用 dfs 函数来计算以该位置为起点的岛屿的面积。并将得到的面积与当前记录的最大面积进行比较,并更新最大面积的值。

时间复杂度分析:

  • 对于每个格子,最坏情况下需要进行深度优先搜索,而深度优先搜索的时间复杂度是 O(m*n),其中 m 和 n 分别为 grid 的行数和列数。
  • 因此,总的时间复杂度为 O(m*n),其中 m 为 grid 的行数,n 为 grid 的列数。

空间复杂度分析:

  • 深度优先搜索过程中使用的递归调用栈的最大深度为岛屿的大小,最坏情况下为整个 grid 大小,因此空间复杂度为 O(m*n)。
  • 此外,还需要考虑输入参数和一些辅助变量的空间占用,但是这些空间占用都是常数级别的,因此不影响总体的空间复杂度。

综上所述,该算法的时间复杂度为 O(mn),空间复杂度也为 O(mn)。

c++ 代码

class Solution {
public:
    // 深度优先搜索函数,用于搜索连通的岛屿区域并返回面积
    int dfs(vector<vector<int>>& grid, int x, int y) {
        // 递归终止条件
        if (x < 0 || x == grid.size() || y < 0 || y == grid[0].size() || grid[x][y] == 0) return 0;
        
        grid[x][y] = 0; // 将已经搜索过的陆地置为0,防止重复搜索(即将其视为沉没的岛屿)
        int ans = 1;
        // 分别搜索当前陆地的上、下、右、左四个方向的区块
        ans += dfs(grid, x, y + 1); // 上面
        ans += dfs(grid, x, y - 1); // 下面
        ans += dfs(grid, x + 1, y); // 右边
        ans += dfs(grid, x - 1, y); // 左边

        return ans;  // 返回当前连通岛屿的总面积
    }

    // 计算最大岛屿面积的函数
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        int ans = 0;  // 初始化最大面积为0
        for (int i = 0; i != grid.size(); ++i) {
            for (int j = 0; j != grid[0].size(); ++j) {
                if (grid[i][j] == 1) {  // 如果当前位置是陆地
                    int cnt = dfs(grid, i, j);  // 对当前的岛屿区域进行深度优先搜索,得到面积
                    ans = max(ans, cnt);  // 更新最大面积
                }
            }
        }
        return ans;  // 返回最大岛屿面积
    }
};

思路和解题方法 2 BFS

  1. 首先,定义了一个类 Solution,其中包含了一个公有函数 maxAreaOfIsland,该函数接收一个二维向量 grid 作为参数,并返回岛屿的最大面积。

  2. maxAreaOfIsland 函数中,我们首先初始化 ans 为 0,以便记录最大的岛屿面积。

  3. 接下来是两个嵌套的 for 循环,用来遍历整个二维网格 grid

  4. 在每次迭代中,我们首先初始化 cur 为 0,用于记录当前岛屿的面积。然后创建两个队列 queueiqueuej,用于存储待访问的陆地坐标。

  5. 将当前遍历到的位置 (i, j) 入队,即将它们分别加入到 queueiqueuej 中。

  6. 进入while循环,只要队列非空,就不断进行以下操作:

    • 弹出队首的坐标 (cur_i, cur_j)
    • 检查当前坐标是否越界或者不是陆地,若是则跳过本次循环;
    • 若当前坐标是陆地,则将当前面积 cur 自增,并将当前坐标标记为已访问过的海洋(即将值置为 0),然后探索当前位置的上、下、左、右四个方向;
    • 将相邻的陆地坐标入队。
  7. 在每次内部循环结束时,更新 ans 为当前 curans 之间的较大值。

  8. 最后,遍历结束后返回 ans,即为岛屿的最大面积。

时间复杂度分析:

  • 时间复杂度取决于岛屿的数量和网格的大小。假设网格的行数为 m,列数为 n,岛屿的数量为 k,那么时间复杂度可以表示为 O(mn+k),其中 mn 表示遍历整个网格的时间复杂度,k 表示计算岛屿面积的时间复杂度。

空间复杂度分析:

  • 空间复杂度方面,使用了两个队列 queueiqueuej,它们的最大长度可以达到网格的面积大小,因此空间复杂度也是 O(m*n)。

综上所述,该算法的时间复杂度为 O(mn),空间复杂度也为 O(mn)。

c++ 代码

class Solution {
public:
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        int ans = 0;
        // 遍历二维网格的每一个位置
        for (int i = 0; i != grid.size(); ++i) {
            for (int j = 0; j != grid[0].size(); ++j) {
                int cur = 0;  // 当前岛屿的面积
                queue<int> queuei;
                queue<int> queuej;
                queuei.push(i);  // 将当前位置加入队列
                queuej.push(j);
                while (!queuei.empty()) {
                    int cur_i = queuei.front(), cur_j = queuej.front();  // 取出队首元素
                    queuei.pop();
                    queuej.pop();
                    if (cur_i < 0 || cur_j < 0 || cur_i == grid.size() || cur_j == grid[0].size() || grid[cur_i][cur_j] != 1) {
                        continue;  // 如果当前位置超出边界或者不是岛屿,跳过
                    }
                    ++cur;  // 当前岛屿面积加一
                    grid[cur_i][cur_j] = 0;  // 将当前位置置为0,表示已经访问过
                    int di[4] = {0, 0, 1, -1};  // 方向数组,表示上下左右四个方向
                    int dj[4] = {1, -1, 0, 0};
                    for (int index = 0; index != 4; ++index) {
                        int next_i = cur_i + di[index], next_j = cur_j + dj[index];  // 计算四个相邻位置
                        queuei.push(next_i);  // 将相邻位置加入队列
                        queuej.push(next_j);
                    }
                }
                ans = max(ans, cur);  // 更新最大岛屿面积
            }
        }
        return ans;  // 返回最大岛屿面积
    }
};

附Java代码

DFS

class Solution {
    public int maxAreaOfIsland(int[][] grid) {
        int ans = 0;  // 初始化最大岛屿面积为0
        for (int i = 0; i != grid.length; ++i) {  // 遍历二维网格的每一个位置
            for (int j = 0; j != grid[0].length; ++j) {
                ans = Math.max(ans, dfs(grid, i, j));  // 计算以当前位置为起点的岛屿面积,并更新最大值
            }
        }
        return ans;  // 返回最大岛屿面积
    }

    public int dfs(int[][] grid, int cur_i, int cur_j) {
        if (cur_i < 0 || cur_j < 0 || cur_i == grid.length || cur_j == grid[0].length || grid[cur_i][cur_j] != 1) {
            return 0;  // 如果当前位置超出边界或者不是岛屿,返回面积为0
        }
        grid[cur_i][cur_j] = 0;  // 将当前位置置为0,表示已经访问过
        int[] di = {0, 0, 1, -1};  // 方向数组,表示上下左右四个方向
        int[] dj = {1, -1, 0, 0};
        int ans = 1;  // 当前岛屿面积初始化为1
        for (int index = 0; index != 4; ++index) {
            int next_i = cur_i + di[index], next_j = cur_j + dj[index];  // 计算四个相邻位置
            ans += dfs(grid, next_i, next_j);  // 递归计算相邻位置的岛屿面积并累加
        }
        return ans;  // 返回当前岛屿面积
    }
}

BFS

class Solution {
    // 计算岛屿的最大面积
    public int maxAreaOfIsland(int[][] grid) {
        int ans = 0;  // 初始化最大面积为 0
        // 遍历整个网格
        for (int i = 0; i != grid.length; ++i) {
            for (int j = 0; j != grid[0].length; ++j) {
                int cur = 0;  // 当前岛屿的面积
                Queue<Integer> queuei = new LinkedList<Integer>();  // 存储陆地坐标的队列
                Queue<Integer> queuej = new LinkedList<Integer>();  // 存储陆地坐标的队列
                queuei.offer(i);  // 将当前坐标入队
                queuej.offer(j);  // 将当前坐标入队
                // BFS 遍历岛屿
                while (!queuei.isEmpty()) {
                    int cur_i = queuei.poll(), cur_j = queuej.poll();  // 出队当前坐标
                    // 检查当前坐标是否越界或者不是陆地,若是则跳过本次循环
                    if (cur_i < 0 || cur_j < 0 || cur_i == grid.length || cur_j == grid[0].length || grid[cur_i][cur_j] != 1) {
                        continue;
                    }
                    ++cur;  // 当前岛屿的面积加一
                    grid[cur_i][cur_j] = 0;  // 标记当前坐标为已访问过的海洋
                    int[] di = {0, 0, 1, -1};  // 方向数组,分别表示上、下、左、右四个方向
                    int[] dj = {1, -1, 0, 0};  // 方向数组,分别表示上、下、左、右四个方向
                    // 探索当前位置的上、下、左、右四个方向
                    for (int index = 0; index != 4; ++index) {
                        int next_i = cur_i + di[index], next_j = cur_j + dj[index];  // 计算相邻坐标
                        queuei.offer(next_i);  // 将相邻的陆地坐标入队
                        queuej.offer(next_j);  // 将相邻的陆地坐标入队
                    }
                }
                ans = Math.max(ans, cur);  // 更新最大面积
            }
        }
        return ans;  // 返回岛屿的最大面积
    }
}

觉得有用的话可以点点赞,支持一下。

如果愿意的话关注一下。会对你有更多的帮助。

每天都会不定时更新哦  >人<  。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/155998.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

9.jvm调优相关工具-java自带

目录 概述jdk工具包jpsjps -qjps -mjps -vjps -l jstatjstat -gcjstat -gcutiljinfo jmapjmap heapjmap histo[:live]jmap clstatsjmap dump jhatjstack 结束 概述 做了一些 1.8 与1.17.x jdk对比&#xff0c;最重要的是实际操作一次。 这些是java自带的命令&#xff0c;属于离…

wpf devexpress在未束缚模式中生成Tree

TreeListControl 可以在未束缚模式中没有数据源时操作&#xff0c;这个教程示范如何在没有数据源时创建tree 在XAML生成tree 创建ProjectObject类实现数据对象显示在TreeListControl: public class ProjectObject {public string Name { get; set; }public string Executor {…

【C++学习手札】模拟实现string

&#x1f3ac;慕斯主页&#xff1a;修仙—别有洞天 ♈️今日夜电波&#xff1a;缶ビール—みゆな 0:41━━━━━━️&#x1f49f;──────── 2:52 &#x1f504; ◀️ ⏸ ▶️ ☰ &…

2023年中国逆流式冷却塔性能特点、应用领域及市场规模分析[图]

按冷却塔热交换时气流和水流方向不同的配置&#xff0c;机力通风冷却塔又可分为横流式冷却塔、逆流式冷却塔&#xff0c;目前主流的冷却塔型式为逆流式冷却塔&#xff0c;逆流式冷却塔&#xff08;counterflowcoolingtower&#xff09;是指水流在塔内垂直落下&#xff0c;气流方…

员工电脑管理软件,企业电脑管理软件是什么

员工电脑管理软件&#xff0c;企业电脑管理软件是什么 企业电脑管理软件是指用于管理和监控企业员工工作电脑的软件。这些软件通常提供多种功能&#xff0c;旨在帮助企业管理员工电脑的使用、监控和维护&#xff0c;同时确保信息安全、提高生产力并确保合规性。推荐一款功能强…

java计算两个字符串日期相隔天数

java计算两个字符串日期相隔天数 public static void main(String[] args) throws ParseException {Scanner sc new Scanner(System.in);System.out.print("请输入计算开始的日期(yyyy-MM-dd):");String startTime sc.next();System.out.print("请输入计算结…

算法-链表-简单-相交、反转、回文、环形、合并

记录一下算法题的学习5 在写关于链表的题目之前&#xff0c;我们应该熟悉回忆一下链表的具体内容 什么是链表&#xff1a; 链表&#xff08;Linked list&#xff09;是一种常见的基础数据结构&#xff0c;是一种线性表&#xff0c;但是并不会按线性的顺序存储数据&#xff0c…

Windows电脑画面如何投屏到电视?怎样限定投屏内容?

电视通常比计算机屏幕更大&#xff0c;因此将电脑画面投射到电视上可以提供更广阔的视野和更好的视觉体验。通过将电脑画面投射到电视上&#xff0c;您可以与他人共享您的计算机屏幕上的内容。这对于展示演示文稿、观看影片或与他人分享照片等活动非常有用。 如果你的电脑系统是…

Azure的AI使用-(语言检测、图像分析、图像文本识别)

1.语言检测 安装包&#xff1a; # 语言检测 %pip install azure-ai-textanalytics5.2.0 需要用到密钥和资源的终结点&#xff0c;所以去Azure上创建资源&#xff0c;我这个是创建好的了然后点击密钥和终结者去拿到key和终结点 两个密钥选择哪个都行 语言检测代码示例&#…

Vue数据绑定

在我们Vue当中有两种数据绑定的方法 1.单向绑定 2.双向绑定 让我为大家介绍一下吧&#xff01; 1、单向绑定(v-bind) 数据只能从data流向页面 举个例子&#xff1a; <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"…

图论| 827. 最大人工岛 127. 单词接龙

827. 最大人工岛 题目&#xff1a;给你一个大小为 n x n 二进制矩阵 grid 。最多 只能将一格 0 变成 1 。返回执行此操作后&#xff0c;grid 中最大的岛屿面积是多少&#xff1f; 岛屿 由一组上、下、左、右四个方向相连的 1 形成。 题目链接&#xff1a;[827. 最大人工岛](ht…

佳易王麻将馆计时收费系统怎么安装,麻将馆的灯控什么原理?

佳易王麻将馆计时收费系统怎么安装&#xff0c;麻将馆的灯控什么原理&#xff1f; 佳易王计时计费软件只需将压缩包文件解压即可使用&#xff0c;灯控的原理是&#xff1a;软件在点击开始计时的时候&#xff0c;软件向灯控器发送开灯信号&#xff0c;相应的灯打开&#xff0c;…

【面试】测试/测开(未完成)

1. 黑盒测试方法 黑盒测试&#xff1a;关注的是软件功能的实现&#xff0c;关注功能实现是否满足需求&#xff0c;测试对象是基于需求规格说明书。 1&#xff09;等价类&#xff1a;有效等价类、无效等价类 2&#xff09;边界值 3&#xff09;因果图&#xff1a;不同的原因对应…

C/C+=内存管理

C/C内存管理以及动态内存的申请_c动态内存的申请与释放_Demo Test的博客-CSDN博客 问题是&#xff0c;这个0x0804 8000 到0xC 0000 0000之间&#xff0c;不止3GB&#xff0c;应该有47GB&#xff0c;该怎么解释呢&#xff1f;

【图像分类】【深度学习】【Pytorch版本】ResNet模型算法详解

【图像分类】【深度学习】【Pytorch版本】 ResNet模型算法详解 文章目录 【图像分类】【深度学习】【Pytorch版本】 ResNet模型算法详解前言ResNet讲解Deep residual learning framework(深度残差学习框架)ResNet残差结构ResNet模型结构 ResNet Pytorch代码完整代码总结 前言 …

深入探讨TensorFlow:张量与矩阵

在机器学习和深度学习领域中&#xff0c;TensorFlow作为一款强大且受欢迎的开源机器学习框架&#xff0c;为研究人员和开发者提供了丰富的工具和资源。在TensorFlow中&#xff0c;张量&#xff08;tensor&#xff09;和矩阵&#xff08;matrix&#xff09;是核心概念&#xff0…

Odoo 15开发手册第七章 记录集 - 使用模型数据

在前面的章节中&#xff0c;我们概览了模型创建以及如何向模型加载数据。现在我们已有数据模型和相关数据&#xff0c;是时候学习如何编程与其进行交互了。 业务应用需要业务逻辑来计算数据、执行验证或自动化操作。Odoo框架API为开发者提供了工具用于实现这种业务逻辑。大多数…

(二)什么是Vite——Vite 和 Webpack 区别(冷启动)

vite分享ppt&#xff0c;感兴趣的可以下载&#xff1a; ​​​​​​​Vite分享、原理介绍ppt 什么是vite系列目录&#xff1a; &#xff08;一&#xff09;什么是Vite——vite介绍与使用-CSDN博客 &#xff08;二&#xff09;什么是Vite——Vite 和 Webpack 区别&#xff0…

2018年五一杯数学建模C题江苏省本科教育质量综合评价解题全过程文档及程序

2019年五一杯数学建模 C题 江苏省本科教育质量综合评价 原题再现 随着中国的改革开放&#xff0c;国家的综合实力不断增强&#xff0c;中国高等教育发展整体已进入世界中上水平。作为一个教育大省&#xff0c;江苏省的本科教育发展在全国名列前茅&#xff0c;而江苏省13个地级…

【PB续命05】WinHttp.WinHttpRequest的介绍与使用

0 WinHttp.WinHttpRequest简介 winhttp.winhttprequest是Windows操作系统中的一个API函数&#xff0c;用于创建和发送HTTP请求。它可以用于从Web服务器获取数据&#xff0c;或将数据发送到Web服务器。该函数提供了许多选项&#xff0c;例如设置请求头、设置代理服务器、设置超…