Nameless Site

But one day, you will stand before its decrepit gate,without really knowing why.

0%

岛屿数量

Posted on In , ,
Symbols count in article: 2.6k Reading time ≈ 2 mins.

来源Leetcode第200题 岛屿数量

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

示例 1:

1
2
3
4
5
6
7
输入:
11110
11010
11000
00000

输出: 1

并查集

在初始化并查集的根节点时，记录所有为1的点的数量，同时将为1的点的根节点初始化为自身，对数组进行遍历，如果遍历时当前点为1，并且其上下左右里有点为1，就意味着相连，合并，并将对应的并查集里的岛屿数减1，最后返回并查集里的岛屿数即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
class UnionFind {
    int[] parents;
    int count = 0;

    public UnionFind(char[][] grid) {
        int row = grid.length;
        int col = grid[0].length;
        parents = new int[row * col];
        for(int i = 0 ; i < row; i ++)
            for(int j = 0 ; j < col ; j++){
                if(grid[i][j] == '1'){
                    parents[i * col + j] = i * col + j; //初始化陆地并查集
                    count++;
                }
            }
    }

    // 合并连通区域是通过find来操作的, 即看这两个节点是不是在一个连通区域内.
    void union(int node1, int node2) {
        int root1 = find(node1);
        int root2 = find(node2);
        if (root1 != root2) {
            parents[root2] = root1;
            count--;
        }
    }

    int find(int node) {
        while (parents[node] != node) {
            // 当前节点的父节点 指向父节点的父节点.
            // 保证一个连通区域最终的parents只有一个.
            parents[node] = parents[parents[node]];
            node = parents[node];
        }

        return node;
    }

    boolean isConnected(int node1, int node2) {
        return find(node1) == find(node2);
    }

}

public int numIslands(char[][] grid) {
    if(grid == null || grid.length == 0)
        return 0;

    int row = grid.length;
    int col = grid[0].length;

    UnionFind uf = new UnionFind(grid);

    for(int i = 0 ; i < row ; i++){
        for(int j = 0 ; j < col ; j++){
            if(grid[i][j] == '1'){
                grid[i][j] = '0';
                if(i - 1 >= 0 && grid[i - 1][j] == '1')
                    uf.union(i * col + j , (i - 1) * col + j);
                if(i + 1 < row && grid[i + 1][j] == '1')
                    uf.union(i * col + j , (i + 1) * col + j);
                if(j - 1 >= 0 && grid[i][j - 1] == '1')
                    uf.union(i * col + j , i* col + j - 1);
                if(j + 1 < col && grid[i][j + 1] == '1')
                    uf.union(i * col + j , i* col + j + 1);
            }
        }
    }

    return uf.count;
}

DFS

线性扫描整个二维网格，如果一个结点包含 1，则以其为根结点启动深度优先搜索。在深度优先搜索过程中，每个访问过的结点被标记为 0。计数启动深度优先搜索的根结点的数量，即为岛屿的数量。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
int nRow = 0;
int nColumn = 0;

void dfs(char[][] grid, int row, int column) {
    nRow = grid.length;
    nColumn = grid[0].length;
    if (row < 0 || column < 0 || row >= nRow || column >= nColumn || grid[row][column] == '0') {
        return;
    }
    grid[row][column] = '0';
    dfs(grid, row - 1, column);
    dfs(grid, row + 1, column);
    dfs(grid, row, column - 1);
    dfs(grid, row, column + 1);
}

public int numIslands(char[][] grid) {
    if (grid == null || grid.length == 0) {
        return 0;
    }
    nRow = grid.length;
    nColumn = grid[0].length;
    int num = 0;
    for (int r = 0; r < nRow; ++r) {
        for (int c = 0; c < nColumn; ++c) {
            if (grid[r][c] == '1') {
                ++num;
                dfs(grid, r, c);
            }
        }
    }
    return num;
}