【LeetCode】200、岛屿数量

【LeetCode】200、岛屿数量

一、并查集

1.1 并查集

// go
var sets int
var father [90000]int

func 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 = 0
    for 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] = idx
                sets++
            }
        }
    }
}

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] = fb
        sets--
    }
}

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
}

参考
参考