侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 471 篇文章
  • 累计创建 108 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

【图, 并查集】岛屿数量

GabrielxD
2022-06-01 / 0 评论 / 0 点赞 / 32 阅读 / 759 字 / 正在检测是否收录...

题目

200. 岛屿数量


给你一个由 '1'(陆地)和 '0'(水)组成的的二维网格,请你计算网格中岛屿的数量。

岛屿总是被水包围,并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外,你可以假设该网格的四条边均被水包围。

示例 1:

输入:grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
输出:1

示例 2:

输入:grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
输出:3

提示:

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 300
  • grid[i][j] 的值为 '0''1'

解题

方法一:并查集

思路

与 [【图, 并查集】岛屿数量 II.md](【图, 并查集】岛屿数量 II.md) 的解法差不多,只不过这次提前给了二维网格中每个格子的状态。

代码

class Solution {
    public int[] findRedundantConnection(int[][] edges) {
        int n = edges.length;
        UnionFind uf = new UnionFind(n + 1);
        for (int[] edge : edges) {
            if (uf.isConnected(edge[0], edge[1])) return edge;
            uf.union(edge[0], edge[1]);
        }
        return new int[2];
    }

    static class UnionFind {
        public int groups;
        private int[] root;
        private int[] rank;

        public UnionFind() {}

        public UnionFind(int size) {
            groups = size;
            root = new int[size];
            rank = new int[size];
            for (int i = 0; i < size; i++) {
                root[i] = i;
                rank[i] = 1;
            }
        }

        public void union(int p, int q) {
            int rootP = find(p);
            int rootQ = find(q);
            if (rootP == rootQ) return;
            if (rank[rootP] > rank[rootQ]) {
                root[rootQ] = rootP;
            } else if (rank[rootP] < rank[rootQ]) {
                root[rootP] = rootQ;
            } else {
                root[rootQ] = rootP;
                rank[rootP]++;
            }
            groups--;
        }

        public int find(int n) {
            return n == root[n] ? n : (root[n] = find(root[n]));
        }

        public boolean isConnected(int p, int q) {
            return find(p) == find(q);
        }
    }
}

优化

既然每个格子状态都知道,就不用上下左右全部检查一遍了,只要检查右边和下边或者左边和上边,能覆盖所有格子就行。

class Solution {
    public int numIslands(char[][] grid) {
        int rowLen = grid.length, colLen = grid[0].length;
        UnionFind uf = new UnionFind(rowLen * colLen);
        for (int row = 0; row < rowLen; row++) {
            for (int col = 0; col < colLen; col++) {
                if (grid[row][col] == '0') continue;
                int idx = row * colLen + col;
                uf.count++;
                if (row - 1 >= 0 && grid[row - 1][col] == '1') {
                    uf.union(idx, (row - 1) * colLen + col);
                }
                if (col + 1 < colLen && grid[row][col + 1] == '1') {
                    uf.union(idx, idx + 1);
                }
            }
        }
        return uf.count;
    }

    static class UnionFind {
        public int count;
        private int[] root;
        private int[] rank;

        public UnionFind() {}

        public UnionFind(int size) {
            count = 0;
            root = new int[size];
            rank = new int[size];
            for (int i = 0; i < size; i++) {
                root[i] = i;
                rank[i] = 1;
            }
        }

        public void union(int p, int q) {
            int rootP = find(p);
            int rootQ = find(q);
            if (rootP == rootQ) return;
            if (rank[rootP] > rank[rootQ]) {
                root[rootQ] = rootP;
            } else if (rank[rootP] < rank[rootQ]) {
                root[rootP] = rootQ;
            } else {
                root[rootQ] = rootP;
                rank[rootP]++;
            }
            count--;
        }

        public int find(int n) {
            return n == root[n] ? n : (root[n] = find(root[n]));
        }

        public boolean isConnected(int p, int q) {
            return find(p) == find(q);
        }
    }
}
0

评论区