200. Number of Islands

JIAKAOBO

LeetCode

感谢赞助!

• ㊗️
• 大家
• offer
• 多多！

Problem

Given a 2d grid map of ‘1’s (land) and ‘0’s (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example 1:

Input:
11110
11010
11000
00000

Output: 1

Example 2:

Input:
11000
11000
00100
00011

Output: 3

Code

DFS

class Solution {
    public int numIslands(char[][] grid) {
        int m = grid.length;
        int n = grid[0].length;

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

        return res;
    }

    private void helper(char[][] grid, int x, int y) {
        if (x < 0 || x >= grid.length || y < 0 || y >= grid[0].length) return;
        if (grid[x][y] == '0') return;

        grid[x][y] = '0';
        helper(grid, x + 1, y);
        helper(grid, x - 1, y);
        helper(grid, x, y + 1);
        helper(grid, x, y - 1);
    }
}

BFS

class Solution {
    public int numIslands(char[][] grid) {
        int m = grid.length;
        int n = grid[0].length;

        int res = 0;

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

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1') {
                    res++;
                    // 每次处理掉所有相邻的1
                    grid[i][j] = '0';
                    Queue<int[]> queue = new LinkedList<>();
                    queue.offer(new int[]{i, j});
                    while (!queue.isEmpty()) {
                        int[] curr = queue.poll();
                        for (int[] dir : dirs) {
                            int x = curr[0] + dir[0];
                            int y = curr[1] + dir[1];
                            if (x < 0 || x >= m || y < 0 || y >= n) continue;
                            if (grid[x][y] != '1') continue;
                            queue.offer(new int[]{x, y});
                            grid[x][y] = '0';
                        }
                    }
                }
            }
        }
        return res;
    }
}

Union find

class Solution {
    public class UnionFind {
        int[] parents;
        int[] ranks;
        int groupNum = 0;

        // two dimensions
        public UnionFind(char[][] matrix) {
            int m = matrix.length;
            int n = matrix[0].length;

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

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

                    ranks[i * n + j] = 1;
                }
            }
        }

        public boolean union(int x, int y) {
            int xParent = find(x);
            int yParent = find(y);
            // same parent
            if (xParent == yParent) return false;
            // different parent
            groupNum--;
            if (ranks[xParent] > ranks[yParent]) {
                parents[yParent] = xParent;
            } else if (ranks[xParent] < ranks[yParent]) {
                parents[xParent] = yParent;
            } else {
                parents[yParent] = xParent;
                ranks[xParent]++;
            }

            return true;
        }

        public int find(int node) {
            while (node != parents[node]) {
                int parentNode = parents[parents[node]];

                parents[node] = parentNode;
                node = parentNode;
            }

            return node;
        }

        public int getGroupNum() {
            return groupNum;
        }
    }

    public int numIslands(char[][] grid) {
        int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        UnionFind unionFind = new UnionFind(grid);

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

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1') {
                    grid[i][j] = '0';
                    for (int[] dir : dirs) {
                        int x = i + dir[0];
                        int y = j + dir[1];
                        if (x < 0 || x >= m || y < 0 || y >= n) continue;
                        if (grid[x][y]=='0') continue;
                        unionFind.union(i * n + j, x * n + y);
                    }
                }
            }
        }

        return unionFind.getGroupNum();
    }
}