LeetCode 200. Number of Islands    原题链接    中等

作者： 作者的头像   cornerCao ,  2019-05-15 23:14:36 ,  所有人可见 ,  阅读 1732

4


1

题目描述

给定包含‘1’（陆地）和‘0’（水）的2维网格图，计算岛屿数量。

岛被水包围，通过水平或垂直连接相邻的土地而形成。

你可以假设网格的所有四个边都被水包围。

样例

输入：
11110
11010
11000
00000
输出: 1
解释：可以看到岛屿可以全部连成一块，所以最后是1个岛屿

输入：
11000
11000
00100
00011
输出: 3
解释：可以看到左上角有一片岛屿，中间有一片岛屿，右下角有一片岛屿，所以最后是3个岛屿

算法

(并查集) $O(n^2)$

遍历网格，如果发现某个坐标是‘1’(说明是岛屿)，则向上下左右四个方向查找，一旦方向往某个方向走是‘1’，则可以合并成一个集合，最后数集合的个数就好。

时间复杂度分析：需要遍历网格，复杂度为$O(n^2)$

C++ 代码

class UnionFind{
public:
    vector<int>father;
    UnionFind(int num){//num表示元素的个数
        for(int i = 0; i < num; i++){
            father.push_back(i);//箭头指向自己
        }
    }
    int Find(int n){
        //递归
        if(father[n] == n)
            return n;
        father[n] = Find(father[n]);//路径压缩版本
        return father[n];
    }
    void Union(int a, int b){
        int fa = Find(a);
        int fb = Find(b);
        father[fb] = fa;
    }
};
class Solution {
public:
    int directions[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    int encode(int i, int j, int n){
        return i*n+j;
    }
    int numIslands(vector<vector<char>>& grid) {
        int M = grid.size();
        if(M==0)
            return 0;
        int N = grid[0].size();
        if(N==0)
            return 0;
        UnionFind UF(M*N);
        for(int i = 0; i < M; i++){
            for(int j = 0; j < N; j++){
                if(grid[i][j]=='1'){
                    for(int d = 0; d < 4; d++){
                        int di = directions[d][0];
                        int dj = directions[d][1];
                        if(i+di >=0 && i+di < M && j+dj >=0 && 
                           j+dj < N && grid[i+di][j+dj]=='1'){
                            UF.Union(encode(i, j, N), encode(i+di, j+dj, N));
                        }
                    }
                }
            }
        }
        int res = 0;
        for(int i = 0; i < M; i++){
            for(int j = 0; j < N; j++){
                if(grid[i][j]=='1'){
                    int id = encode(i, j, N);
                    if(UF.Find(id) == id)
                        res++;
                }
            }
        }
        return res;
    }
};

2 评论

用户头像
有心人   2021-08-18 16:00         踩      回复

贴一个BFS的解法，DFS 和 BFS 详解 见 详细题解：
- DFS：时间 O(mn), 空间 O(mn)
- BFS：时间 O(mn), 空间 O(min(m, n))

// bfs: 时间 O(mn), 空间 O(min(m, n))
class Solution {
public:
    vector<vector<char>> g;

    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1}; // 左-上-右-下

    int numIslands(vector<vector<char>>& grid) {
        g = grid;

        int cnt = 0;
        for (int i = 0; i < g.size(); i ++ )
            for (int j = 0; j < g[0].size(); j ++ )
                if (g[i][j] == '1') {
                    cnt ++ ;
                    bfs(i, j);
                }
        return cnt;
    }

    void bfs(int i, int j) {
        g[i][j] = '2';

        queue<pair<int, int>>q;
        q.push({i, j});

        while (!q.empty()) {
            auto t = q.front(); q.pop();
            int x = t.first, y = t.second;

            for (int k = 0; k < 4; k ++ ) {
                int a = x + dx[k], b = y + dy[k];
                if (a >= 0 && a < g.size() && b >= 0 && b <g[a].size() && g[a][b] == '1') {
                    q.push({a, b});
                    g[a][b] = '2'; // 这里是 '=', 一开始手残打成 "==", leetcode报超时
                }
            }
        }
    }
};
用户头像
extrovert   2019-05-16 20:03         踩      回复

指路牌 DFS做法：https://www.acwing.com/solution/LeetCode/content/263/