岛屿数量

发表于
本文字数： 3.7k 阅读时长 ≈ 3 分钟

LeetCode每日一题，200. Number of Islands

先看题目描述

大意就是给定一个二维网格，代表岛屿地图，网格中 ‘1’ 代表岛屿，’0’ 代表海，让我们返回岛屿地图中的群岛数量

算法和思路

深度优先搜索

定义一个 visited 数组来记录某个岛是否已被访问过，扫描整个二维网格，如果一个位置为 1 且未被访问过，则从此点开始j进行深度优先搜索，在深度优先搜索过程中，每个搜索到的未被访问的岛屿都会被标记为 visited，最终群岛的数量就是深度优先搜索的次数

算法源码

深度优先搜索

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
class Solution {
    private boolean visited[][];
    private int res = 0;

    public int numIslands(char[][] grid) {
        int m = grid.length;
        if (m == 0) return 0;
        int n = grid[0].length;
        visited = new boolean[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1' && !visited[i][j]) {
                    res += 1;
                    dfs(grid, i, j);
                }
            }
        }
        return res;
    }

    private void dfs(char[][] grid, int i, int j) {
        if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] == '0' || visited[i][j]) return;
        visited[i][j] = true;
        dfs(grid, i - 1, j);
        dfs(grid, i + 1, j);
        dfs(grid, i, j - 1);
        dfs(grid, i, j + 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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
public class Solution {

    public int numIslands(char[][] grid) {
        int rows = grid.length;
        if (rows == 0) {
            return 0;
        }
        int cols = grid[0].length;

        int size = rows * cols;
        // 两个方向的方向向量（理解为向下和向右的坐标偏移）
        int[][] directions = {{1, 0}, {0, 1}};
        // +1 是认为虚拟的水域
        UnionFind unionFind = new UnionFind(size + 1);

        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {

                if (grid[i][j] == '1') {
                    for (int[] direction : directions) {
                        int newX = i + direction[0];
                        int newY = j + direction[1];
                        if (newX < rows && newY < cols && grid[newX][newY] == '1') {
                            unionFind.union(cols * i + j, cols * newX + newY);
                        }
                    }
                } else {
                    // 如果不是陆地，所有的水域和一个虚拟的水域连接
                    unionFind.union(cols * i + j, size);
                }
            }
        }

        // 减去那个一开始多设置的虚拟的水域
        return unionFind.count - 1;
    }


    class UnionFind {
        
        private int[] parent;
        private int count;

        public UnionFind(int n) {
            this.count = n;
            parent = new int[n];
            for (int i = 0; i < n; i++) {
                parent[i] = i;
            }
        }

        /**
         * 返回索引为 p 的元素的根结点
         *
         * @param p
         * @return
         */
        public int find(int p) {
            // 在 find 的时候执行路径压缩
            while (p != parent[p]) {
                // 两步一跳完成路径压缩，这里是「隔代压缩」
                // 说明：「隔代压缩」和「按秩合并」选择一个实现即可，「隔代压缩」的代码量少，所以选它
                parent[p] = parent[parent[p]];
                p = parent[p];
            }
            return p;
        }

        public boolean connected(int p, int q) {
            int pRoot = find(p);
            int qRoot = find(q);
            return pRoot == qRoot;
        }

        public void union(int p, int q) {
            int pRoot = find(p);
            int qRoot = find(q);
            if (pRoot == qRoot) {
                return;
            }
            parent[qRoot] = pRoot;
            // 每次 union 以后，连通分量减 1
            count--;
        }
    }
}