2021-04-18：给定一个二维数组matrix，里面的值不是1就是0，上、下、左、右相邻的1认为是一片岛，返回matrix中岛的数量。

2021-04-18：给定一个二维数组matrix，里面的值不是1就是0，上、下、左、右相邻的1认为是一片岛，返回matrix中岛的数量。java

福大大 答案2021-04-18：git

并查集。github

代码用golang编写。代码以下：golang

package main

import "fmt"

func main() { 
    arr := [][]byte{ 
        { 49, 49, 49, 49, 48},
        { 49, 49, 48, 49, 48},
        { 49, 49, 48, 49, 48},
        { 49, 49, 48, 48, 48},
        { 48, 48, 48, 48, 48}}
    ret := numIslands(arr)
    fmt.Println(ret)
}
func numIslands(board [][]byte) int { 
    row := len(board)
    col := len(board[0])
    uf := NewUnionFind(board)
    for j := 1; j < col; j++ { 
        if board[0][j-1] == '1' && board[0][j] == '1' { 
            uf.union(0, j-1, 0, j)
        }
    }
    for i := 1; i < row; i++ { 
        if board[i-1][0] == '1' && board[i][0] == '1' { 
            uf.union(i-1, 0, i, 0)
        }
    }
    for i := 1; i < row; i++ { 
        for j := 1; j < col; j++ { 
            if board[i][j] == '1' { 
                if board[i][j-1] == '1' { 
                    uf.union(i, j-1, i, j)
                }
                if board[i-1][j] == '1' { 
                    uf.union(i-1, j, i, j)
                }
            }
        }
    }
    return uf.getSets()
}

type UnionFind2 struct { 
    parent []int
    size   []int
    help   []int
    col    int
    sets   int
}

func NewUnionFind(board [][]byte) *UnionFind2 { 
    ret := &UnionFind2{ }
    ret.col = len(board[0])
    ret.sets = 0
    row := len(board)
    length := row * ret.col
    ret.parent = make([]int, length)
    ret.size = make([]int, length)
    ret.help = make([]int, length)
    for r := 0; r < row; r++ { 
        for c := 0; c < ret.col; c++ { 
            if board[r][c] == '1' { 
                i := ret.index(r, c)
                ret.parent[i] = i
                ret.size[i] = 1
                ret.sets++
            }
        }
    }
    return ret
}

// (r,c) -> i
func (this *UnionFind2) index(r int, c int) int { 
    return r*this.col + c
}

// 原始位置 -> 下标
func (this *UnionFind2) find(i int) int { 
    hi := 0
    for i != this.parent[i] { 
        this.help[hi] = i
        hi++
        i = this.parent[i]
    }
    for hi--; hi >= 0; hi-- { 
        this.parent[this.help[hi]] = i
    }
    return i
}

func (this *UnionFind2) union(r1 int, c1 int, r2 int, c2 int) { 
    i1 := this.index(r1, c1)
    i2 := this.index(r2, c2)
    f1 := this.find(i1)
    f2 := this.find(i2)
    if f1 != f2 { 
        if this.size[f1] >= this.size[f2] { 
            this.size[f1] += this.size[f2]
            this.parent[f2] = f1
        } else { 
            this.size[f2] += this.size[f1]
            this.parent[f1] = f2
        }
        this.sets--
    }
}

func (this *UnionFind2) getSets() int { 
    return this.sets
}

执行结果以下：
数组

左神java代码
力扣200. 岛屿数量this