岛屿数量.

岛屿数量."/>

岛屿数量.

题目链接

思路

• 数组中上下左右都为’1’的会被认为1块连续的岛屿
• 将二维数据进行循环,如果当前节点元素为’1’就对当前节点上下左右方向进行扩展(深度搜索)
• 每搜索一块儿岛屿就把当前节点置为’0’,避免重复搜索
• 直至搜索到索引结束或者搜索到的元素为’0’的节点结束
• 扩展完一块儿岛屿并记录岛屿的数量

java

    public int numIslands(char[][] grid) {// 岛屿的数量int res = 0;for (int x = 0; x < grid.length; x++) {for (int y = 0; y < grid[x].length; y++) {if (grid[x][y] == '1') {// 遇到岛屿开始进行搜索;并记录岛屿的数量++res;dfs(grid, x, y);}}}return res;}private void dfs(char[][] grid, int x, int y) {if (x < 0 || x >= grid.length || y < 0 || y >= grid[x].length || grid[x][y] == '0') {// 遇到水或者索引越界返回return;}// 搜索完将当前节点置为水,避免重复搜索grid[x][y] = '0';dfs(grid, x - 1, y);dfs(grid, x + 1, y);dfs(grid, x, y - 1);dfs(grid, x, y + 1);}

go

func numIslands(grid [][]byte) int {// 岛屿的数量res := 0for x, arr := range grid {for y, ch := range arr {if ch == '1' {// 遇到岛屿开始进行搜索;并记录岛屿的数量res++dfs(&grid, x, y)}}}return res
}func dfs(grid *[][]byte, x, y int) {if x < 0 || x >= len(*grid) || y < 0 || y >= len((*grid)[x]) || (*grid)[x][y] == '0' {// 遇到水或者索引越界返回return}// 搜索完将当前节点置为水,避免重复搜索(*grid)[x][y] = '0'dfs(grid, x-1, y)dfs(grid, x+1, y)dfs(grid, x, y-1)dfs(grid, x, y+1)
}

注意: java使用grid传参的时候,由于数组是引用数据类型,当使用引用数据类型作为方法的形参时,若在方法体中修改形参指向的数据内容,则会对实参变量的数值产生影响,因为形参变量和实参变量共享同一块堆区.但是使用go时,numIslands函数必须要标明是引用传递,不如果不进行标注默认是值传递;值传递其实是把数组copy一份给numIslands使用,numIslands对grid的一切操作都不会影响调用者.