戴绿帽的耗子

[LeetCode AK 计划]200. 岛屿数量
题目链接:200. 岛屿数量难度:Medium题解分析本题是图论中的问题,可以先进行一定的抽象把输入数据理解为一张...
扫描右侧二维码阅读全文
04
2019/10

[LeetCode AK 计划]200. 岛屿数量

题目

链接:200. 岛屿数量
难度:Medium

题干

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

示例1:

输入:
11110
11010
11000
00000

输出:1

示例2:

输入:
11000
11000
00100
00011

输出:3

题解

分析

本题是图论中的问题,可以先进行一定的抽象把输入数据理解为一张图。所有的数字1对应的坐标可以看作是图中的结点,相邻的1代表两个结点相连(之间存在边),否则就没有边。这样,求岛屿的数量实质是就是在求图中最大联通分量的个数,最容易想到的办法自然就是深度优先搜索和广度优先搜索了。

实现

第一版:使用队列实现的非递归的BFS

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        int ret = 0;
        
        int r = grid.size();
        int c = r == 0 ? 0 : grid[0].size();
        vector<vector<bool>> flag(r, vector<bool>(c, false));
        queue<size_t> x, y;
        size_t tmp_x, tmp_y;
        for(size_t i = 0; i < r; ++i) {
            for(size_t j = 0; j < c; ++j) {
                if(flag[i][j]) continue;
                flag[i][j] = true;
                if(grid[i][j] == '1') {
                    x.push(i);
                    y.push(j);
                    ++ret;
                    while(!x.empty()) {
                        tmp_x = x.front();
                        tmp_y = y.front();
                        x.pop();
                        y.pop();
                        if(tmp_y >= 1 && !flag[tmp_x][tmp_y - 1] && grid[tmp_x][tmp_y - 1] == '1') {
                            x.push(tmp_x);
                            y.push(tmp_y - 1);
                            flag[tmp_x][tmp_y - 1] = true;
                        }
                        if(tmp_y < c - 1 && !flag[tmp_x][tmp_y + 1] && grid[tmp_x][tmp_y + 1] == '1') {
                            x.push(tmp_x);
                            y.push(tmp_y + 1);
                            flag[tmp_x][tmp_y + 1] = true;
                        }
                        if(tmp_x >= 1 && !flag[tmp_x - 1][tmp_y] && grid[tmp_x - 1][tmp_y] == '1') {
                            x.push(tmp_x - 1);
                            y.push(tmp_y);
                            flag[tmp_x - 1][tmp_y] = true;
                        }
                        if(tmp_x < r - 1 && !flag[tmp_x + 1][tmp_y] && grid[tmp_x + 1][tmp_y] == '1') {
                            x.push(tmp_x + 1);
                            y.push(tmp_y);
                            flag[tmp_x + 1][tmp_y] = true;
                        }
                    }
                }
            }
        }
        return ret;
    }
};

顺利通过全部47个测试用例,用时12ms,超过95.43%的提交记录。但是查看提交记录,发现在我之前还存在8ms、4ms、0ms三个梯队。分别阅读了它们的代表源码发现了一个共同点:它们都没有设置专门的visited来标记访问,而是直接把已经记录过的所有连通分量中的1置0,省去了不少额外空间和判断。除此之外,它们的策略均是递归或非递归的DFS。
第二版:用栈实现的非递归的DFS(这是我目前各种尝试得到的最快版本,我甚至直接提交了0ms梯队示例代码)

struct pos {
    int x;
    int y;
    
    pos(int i, int j) {
        x = i;
        y = j;
    }
};

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        int ret = 0;
        
        r = grid.size();
        c = r == 0 ? 0 : grid[0].size();
        
        for(int i = 0; i < r; ++i) {
            for(int j = 0; j < c; ++j) {
                if(grid[i][j] == '1') {
                    dfs(grid, i, j);
                    ++ret;
                }
            }
        }
        
        return ret;
    }
    
private:
    void dfs(vector<vector<char>>& grid, int i, int j) {
        if(grid[i][j] != '1')   return;
        
        stack<pos> q;
        q.push(pos(i, j));
        while(!q.empty()) {
            pos tmp = q.top();
            q.pop();
            grid[tmp.x][tmp.y] = 0;
            
            if(tmp.x - 1 >= 0 && grid[tmp.x - 1][tmp.y] == '1') q.push(pos(tmp.x - 1, tmp.y));
            if(tmp.x + 1 < r && grid[tmp.x + 1][tmp.y] == '1')  q.push(pos(tmp.x + 1, tmp.y));
            if(tmp.y - 1 >= 0 && grid[tmp.x][tmp.y - 1] == '1') q.push(pos(tmp.x, tmp.y - 1));
            if(tmp.y + 1 < c && grid[tmp.x][tmp.y + 1] == '1')  q.push(pos(tmp.x, tmp.y + 1));
        }
    }
    
    int r;
    int c;
};

最终用时4ms,处于第二梯队。
第三版:0ms梯队,目前还未达到。
惯例,附上最优提交截图:
结果

Last modification:February 1st, 2020 at 12:51 am
如果觉得我的文章对你有用,请随意赞赏

Leave a Comment