最大人工岛(Leetcode 827)

题目分析

   这种题目小伙伴们应该见过很多了，直接并查集的模板套用即可。小伙伴先看一下能否顺利写出并查集的模板。

并查集

并查集不过多介绍，还有不会的小伙伴可以参考并查集。

本题的思路是：

1. 首先将每个区域的面积求出来
2. 遍历所有的点，若该点为1，则就是该区域所对应的面积。如果该点为0，将该点变为1，此时计算上下左右的面积之和是该区域对应的面积。
3. 这里有一个易错点，就是上下左右可能都是同一个区域，记得不要重复计算，可以根据并查集中的root数组来判断是否是同一个区域。

因为引入了rank数组，算法的**时间复杂度为O(mn)，空间复杂度为O(mn)**。

class Solution {
    public static void main(String[] args) {
        System.out.println(new Solution().largestIsland(new int[][]{{1, 0}, {0, 1}}));
    }

    public int largestIsland(int[][] grid) {
        int row = grid.length;
        int col = grid[0].length;
        UnionFind uf = new UnionFind(grid, row, col);
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (grid[i][j] == 1) {
                    if (i + 1 < row && grid[i + 1][j] == 1) {
                        uf.union(i, j, i + 1, j);
                    }
                    if (j + 1 < col && grid[i][j + 1] == 1){
                        uf.union(i, j, i, j + 1);
                    }
                }
            }
        }
        int[][] dirs = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        HashSet<Integer> rootSet = new HashSet<>();
        int res = 0;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (grid[i][j] == 0) {
                    int size = 0;
                    rootSet.clear();
                    for (int[] dir : dirs) {
                        int newI = i + dir[0];
                        int newJ = j + dir[1];
                        if (newI >= 0 && newI < row && newJ >= 0 && newJ < col && grid[newI][newJ] == 1) {
                            int root = uf.getRoot(uf.getIdx(newI, newJ));
                            if (!rootSet.contains(root)) {
                                size += uf.getSize(root);
                                rootSet.add(root);
                            }
                        }
                    }
                    res = Math.max(res, size + 1);
                } else {
                    res = Math.max(res, uf.getSize(uf.getRoot(uf.getIdx(i, j))));
                }
            }
        }
        return res;
    }
}

class UnionFind {
    private int[] rank;

    private int[] root;

    private int[] size;

    private int row;

    private int col;

    UnionFind(int[][] grid, int row, int col) {
        this.row = row;
        this.col = col;
        rank = new int[row * col];
        root = new int[row * col];
        size = new int[row * col];
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                int idx = getIdx(i, j);
                rank[idx] = 1;
                root[idx] = idx;
                size[idx] = grid[i][j];
            }
        }
    }

    public void union(int i1, int j1, int i2, int j2) {
        int idx1 = getIdx(i1, j1);
        int idx2 = getIdx(i2, j2);
        int root1 = getRoot(idx1);
        int root2 = getRoot(idx2);
        if (root1 != root2) {
            if (rank[root1] <= rank[root2]) {
                root[root1] = root2;
                size[root2] += size[root1];
                if (rank[root1] == rank[root2]) {
                    rank[root2]++;
                }
            } else {
                root[root2] = root1;
                size[root1] += size[root2];
            }
        }
    }

    public int getSize(int idx) {
        return size[idx];
    }

    public int getRoot(int x) {
        if (root[x] != x) {
            return getRoot(root[x]);
        }
        return x;
    }

    public int getIdx(int i, int j) {
        return i * col + j;
    }
}

刷题总结

  并查集同学们一定要会默写，这是面试、比赛、刷题中的利器。