Blog

leetcode200岛屿数量

leetcode200 Number of Islands

Posted by BY on July 11, 2019

前言

新的一年，好好学习。

正文

问题来源

本问题来自leetcode上的200题。

问题描述

给定一个由 ’1’（陆地）和 ‘0’（水）组成的的二维网格，计算岛屿的数量。一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。

示例 1：

输入:
11110
11010
11000
00000

输出: 1

示例 2：

输入:
11000
11000
00100
00011

输出: 3

分析：

深度优先

func numIslands(grid [][]byte) int {
    count := 0
    for i := 0; i < len(grid); i++ {
        for j := 0; j < len(grid[i]); j++ {
            if grid[i][j] != '0' {
                count++
                dfs(grid, i, j)
            }
        }
    }
    return count
}

func dfs(grid [][]byte, i, j int) {
    if grid[i][j] == '0' {
        return
    }
    grid[i][j] = '0'
    
    row := len(grid)
    col := len(grid[i])
    if i > 0 {
        dfs(grid, i-1, j)
    }
    if j > 0 {
        dfs(grid, i, j-1)
    }
    if i < row - 1 {
        dfs(grid, i+1, j)
    }
    if j < col - 1 {
        dfs(grid, i, j+1)
    }
}
/**
 func dfs(grid [][]byte, i, j int) {
    row := len(grid)
    col := len(grid[0])
    if i < 0 || i >= row || j < 0 || j >= col {
        return
    }
    if grid[i][j] == '0' {
        return
    }
    grid[i][j] = '0'
    dfs(grid, i-1, j)
    dfs(grid, i, j-1)
    dfs(grid, i+1, j)
    dfs(grid, i, j+1)
}
 */

广度优先

var dirs = []point{
    {
        x: 0,
        y: 1,
    },
    {
        x: 1,
        y: 0,
    },
    {
        x: -1,
        y: 0,
    },
    {
        x: 0,
        y: -1,
    },

}
type point struct {
    x int
    y int
}

// 广度搜索 numIslands
func numIslands(grid [][]byte) int {

    if len(grid) == 0 {
        return 0
    }
    m := len(grid)
    n := len(grid[0])
    queue := make([]point,0)
    num := 0
    for i := range grid {
        for j, val := range grid[i] {
            if val == 49 {
                queue = append(queue, point{i,j})
                num++
                for len(queue) >0 {
                    temp := queue[0]
                    queue = queue[1:]
                    if grid[temp.x][temp.y] == 48 {
                        continue
                    }
                    grid[temp.x][temp.y] = 48
                    for _,dir := range dirs {
                        x := temp.x + dir.x
                        y := temp.y + dir.y
                        if x>=0 && x < m && y >=0 && y <n {
                            if grid[x][y] == 49 {
                                queue = append(queue,point{x,y})
                            }
                        }
                    }
                }
            }
        }
    }
    return num
}

并查集解法
也可以考虑用并查集来做这题，将二维数组重新编号，从0开始，从左到右，从上到下，直到nm-1（其中n为行数，m为列数），对于位置(i,j)则编号为im+j，那么相邻（左右，上下）的为同一个值，则认为他们相通。那么最终只要统计一下father[i]==i且对应值为1的个数即可。

class Solution {
public:
    int findFather(vector<int> &father,int a){
        int f=a;
        while(father[f]!=f){
            f=father[f];
        }
        while(father[a]!=a){
            int z=a;
            a=father[z];
            father[a]=f;

        }
        return f;
    }
    void unionFather(vector<int> &father, int a,int b){
        int fa=findFather(father,a);
        int fb=findFather(father,b);
        if(fa!=fb){
            father[fa]=fb;
        }
    }

    int numIslands(vector<vector<char>>& grid) {
        if(grid.size()==0||grid[0].size()==0) return 0;
        int n=grid.size(),m=grid[0].size(),k=n*m;
        vector<int> father(k,-1);
        for(int i=0;i<k;i++){
            father[i]=i;
        }
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                int t1=i*m+j;
                int t2=t1+1,t3=t1+m;
                if(j+1<m&&grid[i][j]==grid[i][j+1]) unionFather(father,t1,t2);
                if(i+1<n&&grid[i][j]==grid[i+1][j]) unionFather(father,t1,t3);
            }
        }
        int res=0;
        for(int i=0;i<k;i++){
            if(father[i]==i&&grid[i/m][i%m]=='1'){
                res+=1;
            }
        }
        return res;
    }
};

总结：

勤思考。

结语

不管怎么样好好加油。

CATALOG
    FEATURED TAGS
    Blog