每日算法-最大人工岛

2021/9/5 1:05:43

本文主要是介绍每日算法-最大人工岛,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

题目描述


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

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/making-a-large-island


解答详情


这是一道DFS+二维+着色的题目,难度为hard。近日在LeetCode上刷DFS相关题的时候遇到的,觉得挺不错的一题,说一下个人的思路和见解:

如果使用暴力法:对每个海域即二维数组为0的位置进行dfs算出岛屿最大值,还需要对其置1后恢复,比较麻烦且容易出错,并且时间复杂度上在LeetCode上是肯定超时的。

其实对于DFS的题来说,一般使用DFS+回溯就能够解决了,但这毕竟是hard题,对此本人使用着色的方法,即定义一个int类型全局变量;先对二维数组进行一次DFS,将不同岛屿进行着色区分并计算出填海前(将某个0变成1)的面积;定义一个全局变量Map用于存储每个岛屿的对应面积,即颜色为key,对应面积为value;对其进行第一次DFS后,所有岛屿完成了着色并计算出填海前的面积,此时再去寻找具有相邻岛屿的海域进行填海(将某个0变成1),从而得出最大岛屿面积。

class Solution {
    //全局Map,key着色,val岛屿面积
    private Map<Integer,Integer> islandAreaMap = new HashMap<>();

    //全局int,每个岛屿的用color值划分
    private int color = -1;

    public int largestIsland(int[][] grid) {
        int res = 0;
        int m = grid.length;
        //先对二维数据进行一次dfs,得出每个岛屿的面积
        for(int i = 0 ; i < m ; i++){
            for(int j = 0 ; j < m ; j++){
                if(grid[i][j]==1){
                    color --;//用于区分不同岛屿
                    int area = dfs(grid,i,j);//通过dfs计算岛屿面积
                    islandAreaMap.put(color,area);
                    res = Math.max(res,area);
                }
            }
        }

        //寻找相邻岛屿,填海,找最大值
        for(int i = 0 ; i < m ; i++){
            for(int j = 0 ; j < m ; j++){
                //使用Set标记相邻岛屿面积
                Set<Integer> islandAreaSet = new HashSet<>();
                //判断填海位置是否具有相邻岛屿,岛屿已被着色
                if(grid[i][j]==0){
                    if(i > 0 && grid[i-1][j]<0){
                        islandAreaSet.add(grid[i-1][j]);// 将岛屿颜色作为val
                    }
                    if(i < m-1 && grid[i+1][j]<0){
                        islandAreaSet.add(grid[i+1][j]);
                    }
                    if(j > 0 && grid[i][j-1]<0){
                        islandAreaSet.add(grid[i][j-1]);
                    }
                    if(j < m-1 && grid[i][j+1]<0){
                        islandAreaSet.add(grid[i][j+1]);
                    }
                }
                //计算填海后岛屿面积
                int area = 1;
                for(Integer islandColor : islandAreaSet){
                    area += islandAreaMap.getOrDefault(islandColor,0);
                }
                res = Math.max(res,area);
            }
        }

        return res;
    }

    private int dfs(int[][] grid,int i,int j){
        int m = grid.length;
        //异常退出
        if(i < 0 || j < 0 || i >= m || j >= m || grid[i][j] < 1){
            return 0;
        }
        //对同一岛屿进行着色
        if(grid[i][j]==1){
            grid[i][j] = color;
        }
        //计算岛屿面积,对垂直/水平分别进行DFS
        return 1+dfs(grid,i-1,j)+dfs(grid,i+1,j)+dfs(grid,i,j-1)+dfs(grid,i,j+1);
    }
}




这篇关于每日算法-最大人工岛的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程