我用算法学golang（岛屿的最大面积）

给定一个包含了一些 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。

解题思路

首先需要读懂题意 可以想象成一个棋盘 将0看为水 将1 看为陆地 上下左右 相邻得越多 即岛屿面积越大

直接将二维数组遍历 发现存在等于1 时 做一个递归寻找 即查找上下左右得是否为1

答案

func maxAreaOfIsland(grid [][]int) int {
    res :=0
    for i,v1 := range grid{
        for j,v2 := range v1{
            if v2 == 1{
                num := depthSearch(&grid,i,j)
                if num > res {
                    res = num
                }
            }
        }
    }

return res 
}

// 传入参数为指针 指向这个二维数组得指针 使得值不需要重复
func depthSearch(grid *[][]int,  i int, j int ) int{
    if i>=0 && i< len(*grid) && j >= 0 && j < len((*grid)[i]) && (*grid)[i][j] == 1{
        (*grid)[i][j] = 0 // 注意此出递归时 需要将自己赋值为0  
        num := 1 + depthSearch(grid,i-1,j) + depthSearch(grid,i+1,j) + depthSearch(grid,i,j+1) + depthSearch(grid,i,j-1)

        return num
        }
    return 0
}

学到了

1. 递归函数
2. DFS

本作品采用《CC 协议》，转载必须注明作者和本文链接