Julia's BLOG

LeetCode-695 岛屿的最大面积

2019-02-13

1. 题面（一道经典DFS）

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

找到给定的二维数组中最大的岛屿面积。(如果没有岛屿，则返回面积为0。)

示例 1:

1
2
3
4
5
6
7
8
[[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:

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

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

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

2. 解答

Java解答：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    private boolean[][] seen;
    private int[][] grid;
    private int count = 0;
    public int maxAreaOfIsland(int[][] grid) {
        this.grid = grid;
        seen = new boolean[grid.length][grid[0].length];
        for(int i = 0;i<grid.length;i++) {
            for(int j = 0;j<grid[0].length;j++) {
                count = Math.max(count, countMax(i,j));
            }
        }
        return count;
    }
    private int countMax(int i,int j) {
        if(i<0 || i>grid.length-1 || j<0 || j>grid[0].length-1 || grid[i][j] == 0 || seen[i][j])
            return 0;
        seen[i][j] = true;
        return (1+countMax(i,j+1)+countMax(i,j-1)+countMax(i-1,j)+countMax(i+1,j));
    }
}

JavaScript解答：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * @param {number[][]} grid
 * @return {number}
 */
var maxAreaOfIsland = function(grid) {
    var count = 0;
    const r = grid.length;
    const c = grid[0].length; 
    for(var i = 0;i<grid.length;i++) {
        for(var j =0;j<grid[0].length;j++) {
            count = Math.max(count, countMax(grid,i,j));
        }
    }
    return count;
    
    function countMax(grid,i,j) {
        if(i<0 || i>r-1 || j<0 || j>c-1 || grid[i][j] == 0)
            return 0;
        grid[i][j] = 0;
        return (1+countMax(grid,i+1,j)+countMax(grid,i-1,j)+countMax(grid,i,j+1)+countMax(grid,i,j-1));
    }
};
Tags: LeetCode
← LeetCode-674 最长连续递增序列 js继承的四种方法 →
赏
使用支付宝打赏
使用微信打赏

若你觉得我的文章对你有帮助，欢迎点击上方按钮对我打赏

扫描二维码，分享此文章