【LeetCode】200、岛屿数量

【LeetCode】200、岛屿数量

一、并查集

1.1 并查集

// go
var sets int
var father [90000]intfunc numIslands(grid [][]byte) int {n, m := len(grid), len(grid[0])build(grid, n, m)for i := range n {for j := range m {if grid[i][j] == '1' {if i > 0 && grid[i-1][j] == '1' { // 因为第一行 i == 0, 所以只有 i > 0 时 grid[i-1][j] 才不越界union(idx(m,i,j), idx(m,i-1,j))}if j > 0 && grid[i][j-1] == '1' {union(idx(m,i,j), idx(m,i,j-1))}}}}return sets
}// 编码: 二维变一维, 表示 并查集的 集合编号
// cols 为列的数量
func idx(cols, i, j int) int {return i*cols+j
}// 把1, 新建并查集, 有几个1就有几个集合
func build(grid [][]byte, n, m int) {// 清零全局变量sets = 0for i := range father {father[i] = 0}for i := range n {for j := range m {if grid[i][j] == '1' {idx := idx(m,i,j)father[idx] = idxsets++}}}
}func find(i int) int {if father[i] != i {father[i] = find(father[i])}return father[i]
}func union(a, b int) {fa, fb := find(a), find(b)if fa != fb {father[fa] = fbsets--}
}func isSameSet(a, b int) bool {return find(a) == find(b)
}

参考 左神 并查集

1.2 多语言解法

$Cpp/Go/Python/Rust/Js/Ts$

// cpp

// go 同上

# python

// rust

// js

// ts

二、洪水填充 DFS

2.1 洪水填充 DFS

若遇到未访问过的陆地则数量++, 并延展此块陆地的最大边界

遇到1则发现岛屿, 通过dfs尽量探索到岛屿的边界, 复杂度O(m*n)

func numIslands(grid [][]byte) (ans int) {m, n := len(grid), len(grid[0])var dfs func(r, c int)   dfs = func(r, c int) { // 延展此块陆地的最大边界if r < 0 || r >= m || c < 0 || c >= n {return} // 递归终止条件：越界（无效的网格），则返回if grid[r][c] != '1' {return} // [非 未访问过的陆地]（水or已访问过的陆地），则返回grid[r][c] = '2' // 标记已访问过的陆地：防止无限循环无法退出dfs(r-1, c); dfs(r+1, c); dfs(r, c-1); dfs(r, c+1)}for r := 0; r < m; r++ {for c := 0; c < n; c++ {if grid[r][c] == '1' { // 若遇到一个 [未访问过的陆地]，则结果+1，并则将其周围四个相连的陆地变为非陆地ans++dfs(r, c)}}}return
}

参考
参考