827. 最大人工岛

1.题目描述

给你一个大小为 n x n 二进制矩阵 grid 。最多 只能将一格 0 变成 1 。

返回执行此操作后，grid 中最大的岛屿面积是多少？

岛屿 由一组上、下、左、右四个方向相连的 1 形成。

示例 1:

输入: grid = [[1, 0], [0, 1]]
输出: 3
解释: 将一格0变成1，最终连通两个小岛得到面积为 3 的岛屿。

示例 2:

输入: grid = [[1, 1], [1, 0]]
输出: 4
解释: 将一格0变成1，岛屿的面积扩大为 4。

示例 3:

输入: grid = [[1, 1], [1, 1]]
输出: 4
解释: 没有0可以让我们变成1，面积依然为 4。

提示：

    n == grid.length
    n == grid[i].length
    1 <= n <= 500
    grid[i][j] 为 0 或 1


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

2.解题思路

步骤一：遍历矩阵，统计有多少个岛屿，以及岛屿对应的面积，利用Map记录。

步骤二：遍历矩阵，当出现海洋时，判断其上下左右是否的岛屿，并利用Set（去重）集合记录下来，便于后面计算修改后的总面积。

步骤三：根据步骤二得到的集合，根据集合中的岛屿对应的面积进行累加，可得到修改海洋后的岛屿面积，依次计算，记录最大的修改后的岛屿面积。

难点：
（1）计算岛屿面积。可以使用深度优先遍历方法，遍历所有连续出现的"1",并为遍历过的“1”赋相同是值，防止重复遍历。
（2）遍历“0”时，需要记录其四个方向的不为“0”的值。
（3）需要有边界判断条件。

3.代码

 public int largestIsland(int[][] grid) {
        if (grid == null || grid.length == 0) return 1;
        int result = 0, index = 2;//返回面积最大的岛屿以及记录岛屿的数量
        HashMap<Integer, Integer> areasMap = new HashMap();//保存每个岛屿的编号以及面积
        for (int i = 0; i < grid.length; i++)
            for (int j = 0; j < grid[0].length; j++)
                if (grid[i][j] == 1) areasMap.put(index, calculateAreas(index++, grid, i, j)); // 只计算未编号的岛屿

        if (areasMap.size() == 0) return 1; // 没有岛屿，全是海洋
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 0) {
                    Set<Integer> islands = getIslands(grid, i, j);
                    if (islands.size() == 0) continue; // 周围没有岛屿
                    //根据海洋周围岛屿的类型获取对应的面积，并求得面积总和+1.
                    result = Math.max(result, islands.stream().map(item -> areasMap.get(item)).reduce(Integer::sum).orElse(0) + 1);
                }
            }
        }
        if (result == 0) return areasMap.get(2); // 全是岛屿，没有海洋
        return result;
    }

    //计算岛屿的面积
    public int calculateAreas(int index, int[][] grid, int row, int column) {
        if (!isLegal(grid, row, column) || grid[row][column] != 1) return 0;
        grid[row][column] = index;
        return calculateAreas(index, grid, row + 1, column) + calculateAreas(index, grid, row - 1, column) + calculateAreas(index, grid, row, column - 1) + calculateAreas(index, grid, row, column + 1) + 1;
    }

    //判断区域是否合法
    public boolean isLegal(int[][] grid, int row, int column) {
        return row >= 0 && row < grid.length && column >= 0 && column < grid[0].length;
    }

    //获取当前位置所在的岛屿
    public Set<Integer> getIslands(int[][] grid, int row, int column) {
        Set<Integer> result = new HashSet<>();
        if (isLegal(grid, row + 1, column) && grid[row + 1][column] != 0)
            result.add(grid[row + 1][column]);
        if (isLegal(grid, row - 1, column) && grid[row - 1][column] != 0)
            result.add(grid[row - 1][column]);
        if (isLegal(grid, row, column - 1) && grid[row][column - 1] != 0)
            result.add(grid[row][column - 1]);
        if (isLegal(grid, row, column + 1) && grid[row][column + 1] != 0)
            result.add(grid[row][column + 1]);
        return result;
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

注意：这段代码的作用是获取set中值所对应的map中的value，并将所有所对应的value进行求和。方法stream()与reduce()是Java8引入的新特性。

islands.stream().map(item -> areasMap.get(item)).reduce(Integer::sum).orElse(0)
1

力扣（LeetCode）-题目链接