golang刷leetcode 技巧之如何解决岛屿的最大面积问题

这篇文章主要介绍golang刷leetcode 技巧之如何解决岛屿的最大面积问题,文中介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们一定要看完!

给定一个包含了一些 0 和 1 的非空二维数组 grid 。

一个 岛屿 是由一些相邻的 1 (代表土地) 构成的组合,这里的「相邻」要求两个 1 必须在水平或者竖直方向上相邻。你可以假设 grid 的四个边缘都被 0(代表水)包围着。

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

解题思路:

1,这个问题和朋友圈那个问题类似,只不过求解目标不一样

2,朋友圈问题是求解连通域个数,这里是求解联通域面积

3,解决方案:深度优先遍历

4,深度优先遍历最简单的方法便是递归

5,这里比朋友圈问题复杂的地方在于,朋友圈问题是对称的,因此是个一维问题,这个问题是二维问题

6,小技巧:是否访问一般用map存,当时golang访问map需要判定,所以简单方法用slice存

代码实现:

func maxAreaOfIsland(grid [][]int) int {    visited:=make([][]int,len(grid))    for i:=0;i<len(grid);i++{        visited[i]=make([]int,len(grid[0]))    }        max:=0    for i:=0;i<len(grid);i++{        for j:=0;j<len(grid[0]);j++{            v:=dfs(grid,visited,i,j)            if v>max{                max=v            }        }    }    return max}
func dfs(grid,visited [][]int,i,j int)int{    if i<0 ||j<0 ||i>=len(grid) ||j>=len(grid[0]) ||grid[i][j]!=1 ||visited[i][j]==1{        return 0    }    visited[i][j]=1    return 1+dfs(grid,visited,i+1,j)+dfs(grid,visited,i,j+1)+dfs(grid,visited,i-1,j)+dfs(grid,visited,i,j-1)}

以上是“golang刷leetcode 技巧之如何解决岛屿的最大面积问题”这篇文章的所有内容,感谢各位的阅读!希望分享的内容对大家有帮助,更多相关知识,欢迎关注亿速云行业资讯频道!

原创文章,作者:Maggie-Hunter,如若转载,请注明出处:https://blog.ytso.com/223981.html

(0)
上一篇 2022年1月7日
下一篇 2022年1月7日

相关推荐

发表回复

登录后才能评论