Java-LeetCode200. 岛屿数量-并查集 | BFS

• 算法
  • 并查集
  • 1.初始化并查集，用records[i*col+j]表示grid[i][j]节点
  • 2.count计数矩阵中1的个数，表示图的总分支
  • 3.遍历矩阵，当矩阵是1时，合并它右边和下边的1，合并成功分支减一，合并失败说明两个节点已经在同一个分支不再减一
  • 4.count表示图的分支即是岛屿的数量

    class UnionFind {
        private int[] records;
        public UnionFind(int n) {
            records = new int[n];
            for (int i = 0; i < n; i++) {
                records[i] = i;
            }
        }
        public int find(int x) {
            int fx = x;
            while (records[fx] != fx) {
                fx = records[fx];
            }
            // 压缩算法，简化时间
            while (x != fx) {
                int temp = records[x];
                records[x] = fx;
                x = temp;
            }
            return fx;
        }
        // true表示合并成功，false表示合并失败
        public boolean union(int x, int y) {
            int fx = find(x);
            int fy = find(y);
            if (fx != fy) {
                records[fx] = fy;
                return true;
            }
            return false;
        }
    }
    public int solve (char[][] grid) {
        int row = grid.length;
        int col = grid[0].length;
        UnionFind unionFind = new UnionFind(row*col);
        int count = 0;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (grid[i][j] == '1') {
                    count++;
                    if (i + 1 < row && grid[i+1][j] == '1' && unionFind.union(i * col + j, (i + 1) * col + j)) {
                        count--;
                    }
                    if (j + 1 < col && grid[i][j+1] == '1' && unionFind.union(i * col + j, i * col + (j + 1))) {
                        count--;
                    }
                }
            }
        }
        return count;
    }

• 算法
  • bfs
  • 1.队列保存矩阵中1的坐标，通过bfs搜索附近四周同属一个岛屿的所有坐标，并置为0防止后续搜索重复计算
  • 2.搜索一次发现一座岛屿计数加一
  • 3.返回结果

    public int numIslands(char[][] grid) {
        // grid[x] == null; grid[x].length == 0; grid[x].length != grid[y].length;
        if (grid == null || grid.length == 0) {
            return 0;
        }
        int row = grid.length;
        int col = grid[0].length;
        int count = 0;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (grid[i][j] == '1') {
                    Queue queue = new LinkedList();
                    queue.offer(new Point(i, j));
                    grid[i][j] = '0';
                    bfs(queue, grid);
                    count++;
                }
            }
        }
        return count;
    }
    public void bfs(Queue queue, char[][] grid) {
        while (!queue.isEmpty()) {
            Point point = queue.poll();
            int x = point.x;
            int y = point.y;
            if (x - 1 >= 0 && grid[x-1][y] == '1') {
                queue.offer(new Point(x-1, y));
                grid[x-1][y] = '0';
            }
            if (y - 1 >= 0 && grid[x][y-1] == '1') {
                queue.offer(new Point(x, y-1));
                grid[x][y-1] = '0';
            }
            if (x + 1 < grid.length && grid[x+1][y] == '1') {
                queue.offer(new Point(x+1, y));
                grid[x+1][y] = '0';
            }
            if (y + 1 < grid[0].length && grid[x][y+1] == '1') {
                queue.offer(new Point(x, y+1));
                grid[x][y+1] = '0';
            }
        }
    }
    class Point {
        int x;
        int y;
        Point (int _x, int _y) {
            x = _x;
            y = _y;
        }
    }