[LeetCode] 岛屿数量问题(Number of Islands)

发表于 更新于 分类于 Waline： 阅读次数： 本文字数： 5.6k 阅读时长 ≈ 5 分钟

By Long Luo

200. 岛屿数量 305. 岛屿数量 II

200. 岛屿数量

BFS

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
public static int numIslands_bfs(char[][] grid) {
    if (grid == null || grid.length == 0 || grid[0].length == 0) {
        return 0;
    }

    int row = grid.length;
    int col = grid[0].length;
    boolean[][] visited = new boolean[row][col];
    int ans = 0;
    for (int i = 0; i < row; i++) {
        for (int j = 0; j < col; j++) {
            if (grid[i][j] == '1' && !visited[i][j]) {
                bfs(grid, visited, i, j);
                ans++;
            }
        }
    }

    return ans;
}

public static void bfs(char[][] grid, boolean[][] visited, int x, int y) {
    int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    Queue<int[]> queue = new LinkedList<>();
    queue.offer(new int[]{x, y});
    visited[x][y] = true;
    while (!queue.isEmpty()) {
        int[] pos = queue.poll();
        for (int[] dir : dirs) {
            int nextX = pos[0] + dir[0];
            int nextY = pos[1] + dir[1];
            if (nextX >= 0 && nextX < grid.length && nextY >= 0 && nextY < grid[0].length
                    && !visited[nextX][nextY] && grid[nextX][nextY] == '1') {
                queue.offer(new int[]{nextX, nextY});
                visited[nextX][nextY] = true;
            }
        }
    }
}

DFS

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
class Solution {
    public int numIslands(char[][] grid) {
        int m = grid.length;
        int n = grid[0].length;

        boolean[][] visited = new boolean[m][n];

        int ans = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1' && !visited[i][j]) {
                    dfs(grid, visited, i, j);
                    ans++;
                }
            }
        }

        return ans;
    }

    private void dfs(char[][] grid, boolean[][] visited, int x, int y) {
        int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

        int m = grid.length;
        int n = grid[0].length;

        visited[x][y] = true;

        for (int[] dir : dirs) {
            int nextX = x + dir[0];
            int nextY = y + dir[1];

            if (nextX >= 0 && nextX < m && nextY >= 0 && nextY < n && grid[nextX][nextY] == '1' && !visited[nextX][nextY]) {
                dfs(grid, visited, nextX, nextY);
            }
        }
    }
}

Union Find

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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
class Solution {
    public int numIslands(char[][] grid) {
        int m = grid.length;
        int n = grid[0].length;

        UnionFind uf = new UnionFind(grid);

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '0') {
                    continue;
                }

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

                if (i < m - 1 && grid[i + 1][j] == '1') {
                    uf.union(i * n + j, (i + 1) * n + j);
                }

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

                if (j < n - 1 && grid[i][j + 1] == '1') {
                    uf.union(i * n + j, i * n + j + 1);
                }
            }
        }

        return uf.getCount();
    }

    class UnionFind {
        int count = 0;
        int[] parents;
        int[] rank;

        UnionFind(char[][] grid) {
            int m = grid.length;
            int n = grid[0].length;

            parents = new int[m * n];
            rank = new int[m * n];

            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (grid[i][j] == '1') {
                        parents[i * n + j] = i * n + j;
                        rank[i * n + j] = 1;
                        count++;
                    }
                }
            }
        }

        int find(int x) {
            while (x != parents[x]) {
                x = parents[x];
                parents[x] = parents[parents[x]];
            }

            return x;
        }

        void union(int x, int y) {
            int rootX = find(x);
            int rootY = find(y);

            if (rootX == rootY) {
                return;
            }

            if (rank[rootX] < rank[rootY]) {
                parents[rootX] = rootY;
            } else if (rank[rootX] > rank[rootY]) {
                parents[rootY] = rootX;
            } else {
                parents[rootY] = rootX;
                rank[rootX]++;
            }

            count--;
        }

        int getCount() {
            return count;
        }
    }
}

305. 岛屿数量 II

Union Find

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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
class Solution {
    public List<Integer> numIslands2(int m, int n, int[][] positions) {
        List<Integer> ans = new ArrayList<>();

        int[][] dirs = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

        UnionFind uf = new UnionFind(m * n);

        boolean[] visited = new boolean[m * n];

        for (int[] pos : positions) {
            int x = pos[0];
            int y = pos[1];

            int idx = x * n + y;

            if (visited[idx]) {
                ans.add(uf.getCount());
                continue;
            }

            uf.setParent(idx);
            visited[idx] = true;

            for (int[] dir : dirs) {
                int nextX = x + dir[0];
                int nextY = y + dir[1];

                int nextIdx = nextX * n + nextY;

                if (inArea(m, n, nextX, nextY) && uf.isValid(nextIdx) && visited[nextIdx]) {
                    uf.union(idx, nextIdx);
                }
            }

            ans.add(uf.getCount());
        }

        return ans;
    }

    private static boolean inArea(int rows, int cols, int x, int y) {
        return x >= 0 && x < rows && y >= 0 && y < cols;
    }

    class UnionFind {
        int[] parents;
        int[] rank;
        int count = 0;

        UnionFind(int n) {
            parents = new int[n];
            rank = new int[n];
            count = 0;

            Arrays.fill(parents, -1);
        }

        boolean isValid(int x) {
            return parents[x] != -1;
        }

        void setParent(int x) {
            if (parents[x] != x) {
                count++;
            }

            parents[x] = x;
        }

        int find(int x) {
            while (x != parents[x]) {
                parents[x] = parents[parents[x]];
                x = parents[x];
            }

            return x;
        }

        boolean isConnected(int x, int y) {
            return find(x) == find(y);
        }

        void union(int x, int y) {
            int rootX = find(x);
            int rootY = find(y);

            if (rootX == rootY) {
                return;
            }

            if (rank[rootX] > rank[rootY]) {
                parents[rootY] = rootX;
            } else if (rank[rootX] < rank[rootY]) {
                parents[rootX] = rootY;
            } else {
                parents[rootY] = rootX;
                rank[rootX]++;
            }

            count--;
        }

        int getCount() {
            return count;
        }
    }
}

参考文献

  1. [岛屿数量 II] (https://leetcode.cn/problems/number-of-islands-ii/solution/dao-yu-shu-liang-ii-by-leetcode/)
  2. 并查集（使用rank + 路径压缩优化）的Java语言版本