草庐IT

leetcode 695. Max Area of Island 岛屿的最大面积(中等)

okokabcd 2023-03-28 原文

一、题目大意

标签: 搜索

https://leetcode.cn/problems/max-area-of-island

给你一个大小为 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

二、解题思路

搜索类的题，这题可以用深度优先搜索，定义一个主函数和一个辅函数，主函数用于遍历所有的搜索位置，判断是否可以开始搜索，辅函数则负责深度优先搜索的递归调用。

三、解题方法

3.1 Java实现

public class Solution {
    public int maxAreaOfIsland(int[][] grid) {
        this.GRID = grid;
        this.M = grid.length;
        this.N = grid[0].length;
        for (int i = 0; i < M; i++) {
            for (int j = 0; j < N; j++) {
                if (GRID[i][j] == 1) {
                    dfs(i, j);
                    max = Math.max(max, island);
                    island = 0;
                }
            }
        }
        return max;
    }

    private int[][] GRID;
    private int M;
    private int N;
    private int[][] dirs = new int[][]{{0, 1}, {0, -1}, {-1, 0}, {1, 0}};
    private int island = 0;
    private int max = 0;

    private void dfs(int i, int j) {
        // 此处保证GRID[i][j] == 1
        GRID[i][j] = 0;
        island++;
        for (int[] dir : dirs) {
            int x = i + dir[0];
            int y = j + dir[1];
            if (x >= 0 && x < M && y >= 0 && y < N && GRID[x][y] == 1) {
                dfs(x, y);
            }
        }
    }
}

四、总结小记

  • 2022/5/31 5月最后一天啦
大面大面积intgridprivate算法与数据结构

有关leetcode 695. Max Area of Island 岛屿的最大面积(中等)的更多相关文章

  1. Python 刷Leetcode题库，顺带学英语单词（31） - 2

    ValidPalindromeGivenastring,determineifitisapalindrome,consideringonlyalphanumericcharactersandignoringcases. [#125]Example:"Aman,aplan,acanal:Panama"isapalindrome."raceacar"isnotapalindrome.Haveyouconsiderthatthestringmightbeempty?Thisisagoodquestiontoaskduringaninterview.Forthepurposeofthisproblem

  2. ruby - 获取数组中的值并最小化某个类属性的最优雅的方法是什么？ - 2

    假设我有以下类(class):classPersondefinitialize(name,age)@name=name@age=ageenddefget_agereturn@ageendend我有一组Person对象。是否有一种简洁的、类似于Ruby的方法来获取最小(或最大)年龄的人？如何根据它对它们进行排序？ 最佳答案 这样做会:people_array.min_by(&:get_age)people_array.max_by(&:get_age)people_array.sort_by(&:get_age)

  3. IDEA使用LeetCode插件 - 2

    前言我们习惯用idea编写、调试代码，在LeetCode上刷题时，如果能够在IDEA编写代码，并且做好代码管理，是一件事半功倍的事情。对于后续复习题目，做笔记也会非常便利。本文目的在于介绍LeetCodeEditor的使用，以及配置工具类，最终目录结构如下：note：放置笔记src：放置代码leetcode.editor.cn：插件LeetCodeEditor自动生成utils：自定义的工具包，可用于自动化输入测试用例，定义题目需要的类（结构体）out：运行测试时自动生成LeetCodeEditorGitHub：https://github.com/shuzijun/leetcode-edit

  4. ruby - 用 ruby​​ 将 2 个破折号插入这个字符串的最短方法是什么？ - 2

    这是字符串:04046955104021109我需要这样格式化:040469551-0402-1109用ruby​​做到这一点的最短/最有效的方法是什么？ 最佳答案 两个简单的插入就可以了:example_string.insert(-9,'-').insert(-5,'-')负数表示您从字符串末尾开始计数。如果您愿意，也可以从头数起:example_string.insert(9,'-').insert(14,'-') 关于ruby-用ruby​​将2个破折号插入这个字符串的最短方法是

  5. ruby - 在公差范围内确定两条线段是否属于同一线段的最有效方法是什么？ - 2

    编辑:更改了标题。我对两个部分是否相同不太感兴趣，而是如果它们在一定的公差范围内彼此共线。如果是这样，那么这些线应该聚集在一起作为一个单独的线段。编辑:我想有一个简短的说法:我试图以一种有效的方式将相似的线段聚集在一起。假设我有线段f(fx0,fy0)和(fx1,fy1)和g(gx0,gy0)和(gx1,gy1)这些来自计算机视觉算法边缘检测器之类的东西，在某些情况下，两条线基本相同，但由于像素容差而被视为两条不同的线。有几种情况f和g共享完全相同的端点，例如:f=(0,0),(10,10)g=(0,0),(10,10)f和g共享大致相同的端点和大致相同的长度，例如:f=(0,0.01

  6. ruby - 将数据写入文件的最有效方法 - 2

    我想将2TB的数据写入一个文件，future可能是PB。数据由全'1'组成。例如2TB的数据由"1111111111111......11111"组成(每个字节用'1'表示)以下是我的方法:File.open("data",File::RDWR||File::CREAT)do|file|2*1024*1024*1024*1024.timesdofile.write('1')endend也就是说，File.write被调用了2TB次。从Ruby的角度，有没有更好的实现方式？ 最佳答案 你有几个问题:File::RDWR||File::

  7. ruby - 在 ruby​​ 中对范围进行排序的最优雅的方法是什么 - 2

    我需要根据起点对Range类型的对象表进行排序。为此，我有以下代码可以正常工作:ranges=@ranges.sortdo|a,b|(a.min)(b.min)end我只是想知道是否有更短、更优雅的方法来做同样的事情。 最佳答案 怎么样:ranges=@ranges.sort_by(&:min)或者如果您实际上指的是起点而不是最小值，因为可能存在诸如(5..3)的范围:ranges=@ranges.sort_by(&:first) 关于ruby-在ruby​​中对范围进行排序的最优雅的方

  8. ruby - 从对象数组中获取包含特定值的数组的最 Rubyish 方式？ - 2

    我有一组ruby​​对象，看起来像这样:[#,#,#]数组中的每个对象都有一个email属性。我想获取数组中ruby​​对象的所有电子邮件属性的新数组。执行代码后，我将得到一个如下所示的数组:["email@example.com","anotheremail@gmail.com",...]我是ruby​​的新手，想以最像ruby​​ish的方式来做这件事。我的问题是，在ruby​​中执行此操作的最佳方法是什么？ 最佳答案 您可以使用map方法将block应用于数组的每个元素，返回一个包含每次调用结果的新数组:somearray.m

  9. ruby - 确定变量是否是值列表中的任何一个的最短/最惯用的方法是什么？ - 2

    这似乎是一个非常简单的问题，但是用Ruby重写它的最短/最惯用的方法是什么？ifvariable==:aorvariable==:borvariable==:corvariable==:d#etc.我看到了这个解决方案:if[:a,:b,:c,:d].include?variable但这在功能上并不总是等价的-我相信Array#include?实际上是在查看变量对象是否包含在列表中；它没有考虑到对象可以使用def==(other)实现自己的相等性测试。正如下面有帮助的评论员所说，这种解释是不正确的。include?确实使用==但它使用数组中项目的==方法。在我的示例中，它是符号，而不是

  10. ruby - 访问任意深度的嵌套哈希值的最像 ruby​​ 的方法是什么？ - 2

    这个问题在这里已经有了答案:HowtoavoidNoMethodErrorformissingelementsinnestedhashes,withoutrepeatednilchecks?(16个答案)关闭7年前。给定一个散列，例如:AppConfig={'service'=>{'key'=>'abcdefg','secret'=>'secret_abcdefg'},'other'=>{'service'=>{'key'=>'cred_abcdefg','secret'=>'cred_secret_abcdefg'}}}我需要一个函数来在某些情况下返回服务/key，在其他情况下返回其

随机推荐