岛屿的最大面积

发布时间:2020-10-13 11:30:00
阅读量:49
作者:猎维人工智能培训
算法面试题

题目描述

给定一个包含了一些 0 和 1的非空二维数组 grid , 一个 岛屿 是由四个方向 (水平或垂直) 的 1 (代表土地) 构成的组合。你可以假设二维矩阵的四个边缘都被水包围着。

找到给定的二维数组中最大的岛屿面积。(如果没有岛屿,则返回面积为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]]

对于上面这个给定矩阵应返回 6。注意答案不应该是11,因为岛屿只能包含水平或垂直的四个方向的‘1’。

示例 2:

[[0,0,0,0,0,0,0,0]]

对于上面这个给定的矩阵, 返回 0。

注意: 给定的矩阵grid 的长度和宽度都不超过 50。

分析与解法

解法一

这道题跟之前的那两道Number of Islands和Number of Distinct Islands是同一个类型的,只不过这次需要统计出每个岛的大小,再来更新结果res。

先用递归来做,遍历grid,当遇到为1的点,我们调用递归函数,在递归函数中,我们首先判断i和j是否越界,还有grid[i][j]是否为1,我们没有用visited数组,而是直接修改了grid数组,遍历过的标记为-1。如果合法,那么cnt自增1,并且更新结果res,然后对其周围四个相邻位置分别调用递归函数即可。

参见代码如下:

class Solution {

public:

vector dirs ;

int maxAreaOfIsland(vector& grid) {

int m = grid.size(), n = grid[0].size(), res = 0;

for (int i = 0; i < m; ++i) {

for (int j = 0; j < n; ++j) {

if (grid[i][j] != 1) continue;

int cnt = 0;

helper(grid, i, j, cnt, res);

}

}

return res;

}

void helper(vector& grid, int i, int j, int& cnt, int& res) {

int m = grid.size(), n = grid[0].size();

if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] <= 0) return;

res = max(res, ++cnt);

grid[i][j] *= -1;

for (auto dir : dirs) {

helper(grid, i + dir[0], j + dir[1], cnt, res);

}

}

};

解法二

下面是迭代的写法,BFS遍历,使用queue来辅助运算,思路没啥太大区别,都是套路,都是模版,往里套就行了。

参见代码如下:

class Solution {

public:

vector dirs ;

int maxAreaOfIsland(vector& grid) {

int m = grid.size(), n = grid[0].size(), res = 0;

for (int i = 0; i < m; ++i) {

for (int j = 0; j < n; ++j) {

if (grid[i][j] != 1) continue;

int cnt = 0;

queue q };

grid[i][j] *= -1;

while (!q.empty()) {

auto t = q.front(); q.pop();

res = max(res, ++cnt);

for (auto dir : dirs) {

int x = t.first + dir[0], y = t.second + dir[1];

if (x < 0 || x >= m || y < 0 || y >= n || grid[x][y] <= 0) continue;

grid[x][y] *= -1;

q.push({x, y});

}

}

}

}

return res;

}

};

类似题目:

Number of Distinct Islands

Island Perimeter

Number of Islands 

更多资讯