郑州手机网站搭建,溧水网站建设,企业网站建设一般考虑哪些因素,企业网页页面模块【LeetCode】200、岛屿数量 文章目录 一、并查集1.1 并查集1.2 多语言解法 二、洪水填充 DFS2.1 洪水填充 DFS 一、并查集
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 …【LeetCode】200、岛屿数量 文章目录 一、并查集1.1 并查集1.2 多语言解法 二、洪水填充 DFS2.1 洪水填充 DFS 一、并查集
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*colsj
}// 把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 多语言解法 C p p / G o / P y t h o n / R u s t / J s / T s Cpp/Go/Python/Rust/Js/Ts 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(r1, c); dfs(r, c-1); dfs(r, c1)}for r : 0; r m; r {for c : 0; c n; c {if grid[r][c] 1 { // 若遇到一个 [未访问过的陆地]则结果1并则将其周围四个相连的陆地变为非陆地ansdfs(r, c)}}}return
}参考 参考
