您的位置 首页 golang

Leetcode-岛屿数量代码示例(Golang)

题目描述

给定一个由 ‘1’(陆地)和 ‘0’(水)组成的二维网格,计算岛屿的数量。一个岛被水包围,并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。

示例 1:

示例 2:

输入:

11000

11000

00100

00011

输出: 3

解题思路

深度优先遍历:每次遇到grid [i][j]==1 的地方,岛屿数+1,之后从该位置上下左右开始遍历,将遇到的1的位置全部置为0,遇到0的地方或者遍历返回。

代码示例

对每一个可能的元素(grid[i][j]==1)深入(上下左右方位)到不能再深入为止(一步步递归进行),而且每个节点只能访问一次。

 func numIslands(grid [][]byte) int {
    var count int
    if len(grid) == 0{
        return count
    }
    rows := len(grid)
    cols := len(grid[0])

    for i := 0; i < rows; i++{
        for j := 0; j < cols; j++{
            if grid[i][j] == '1'{
                dfsHelper(grid, i, j, rows, cols)
                count++
            }
        }
    }

    return count
}

func dfsHelper(grid [][]byte, i, j, rows, cols int){
    if i < 0 || j < 0 || i >= rows || j >= cols || grid[i][j] == '0'{
        return
    }

    grid[i][j] = '0'
    dfsHelper(grid, i-1, j, rows, cols)
    dfsHelper(grid, i+1, j, rows, cols)
    dfsHelper(grid, i, j-1, rows, cols)
    dfsHelper(grid, i, j+1, rows, cols)

    return
}
  

如有不对、欢迎指正,相互学习,共同进步。

文章来源:智云一二三科技

文章标题:Leetcode-岛屿数量代码示例(Golang)

文章地址:https://www.zhihuclub.com/99696.shtml

关于作者: 智云科技

热门文章

网站地图