前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >LeetCode笔记:695. Max Area of Island

LeetCode笔记:695. Max Area of Island

作者头像
Cloudox
发布2021-11-23 16:39:46
2890
发布2021-11-23 16:39:46
举报
文章被收录于专栏:月亮与二进制月亮与二进制

问题(Easy):

Given a non-empty 2D array grid of 0's and 1's, an island is a group of 1's (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water. Find the maximum area of an island in the given 2D array. (If there is no island, the maximum area is 0.) Example 1: [[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]] Given the above grid, return 6. Note the answer is not 11, because the island must be connected 4-directionally. Example 2: [[0,0,0,0,0,0,0,0]] Given the above grid, return 0. Note: The length of each dimension in the given grid does not exceed 50.

大意:

给出一个非空的二维数组grid,由0和1组成,一个岛是指由1通过四个方向(水平或垂直)组成的一块区域(代表陆地)。你可以假设grid的四边都是水。 找到给出的二维数组中最大区域的岛。(如果没有岛,最大区域就是0)。 例1: [[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]] 给出上面的grid,返回6。注意答案不是11,因为岛必须由四个方向连接。 例2: [[0,0,0,0,0,0,0,0]] 给出上面的grid,返回0。 注意:给出的grid每个方向的长度不会超过50。

思路:

我们遍历二维数组的时候,遇到1了,肯定是要检查上下左右是否依然是1(同时注意不要超出边界),如果检查出某一边是1,则还要进一步继续检查它的上下左右是否是1,这说明我们要通过递归来做,遍历时每遇到一个1,就放到递归中去检测并计算岛屿面积。

此外,为了避免循环计算重复的区域,我们要改变已经计算过的岛屿的位置的值,可以从1改成2。

这种递归方式其实就是一种DFS,遇到一个1,则找遍其四周及四周的四周等等,来计算一个岛屿面积,同时改变找过的1的值,避免重复计算。

代码(C++):

代码语言:javascript
复制
class Solution {
public:
    int findLand(vector<vector<int>>& grid, int i, int j) {
        grid[i][j] = 2;
        int sum = 1;
        if (i > 0 && grid[i-1][j] == 1) sum = sum + findLand(grid, i-1, j);
        if (i < grid.size()-1 && grid[i+1][j] == 1) sum = sum + findLand(grid, i+1, j);
        if (j > 0 && grid[i][j-1] == 1) sum = sum + findLand(grid, i, j-1);
        if (j < grid[0].size()-1 && grid[i][j+1] == 1) sum = sum + findLand(grid, i, j+1);
        return sum;
    }
    
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        if (grid.size() == 0) return 0;
        int res = 0;
        for (int i = 0; i < grid.size(); i++) {
            for (int j = 0; j < grid[0].size(); j++) {
                if (grid[i][j] == 1) {
                    int temp = findLand(grid, i, j);
                    res = max(temp, res);
                }
            }
        }
        return res;
    }
};

合集:https://github.com/Cloudox/LeetCode-Record


本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2018/1/22 上,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 问题(Easy):
  • 大意:
  • 思路:
  • 代码(C++):
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档