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 技巧之如何解决岛屿的最大面积问题”这篇文章的所有内容，感谢各位的阅读！希望分享的内容对大家有帮助，更多相关知识，欢迎关注亿速云行业资讯频道！