March 17, 2019

200. Number of Islands

用 BFS 和 DFS 都可以做。另有 Union Find 的解法。
相似题目：
130. Surrounded Regions
286. Walls and Gates

Sol 1. DFS

Time = O(mn), Space = O(mn) (递归栈的大小)

class Solution {
    private int[][] dirs = {`{-1, 0}, {1, 0}, {0, -1}, {0, 1}`};

    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) {
            return 0;
        }
        int numOfIsland = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == '1') {
                    dfsHelper(grid, i, j);
                    numOfIsland ++;
                }
            }
        }
        return numOfIsland;
    }
    
    private void dfsHelper(char[][] grid, int i, int j) {
        if (i < 0 || j < 0 || i > grid.length - 1 || j > grid[0].length - 1 || grid[i][j] == '0') {
            return;
        }
        grid[i][j] = '0';    
        for (int[] dir : dirs) {
            dfsHelper(grid, i + dir[0], j + dir[1]);
        }
    }
}

Sol 2. BFS

Time = O(mn), space = O(mn) (Queue的大小)

class Solution {
    private int[][] dirs = {`{-1, 0}, {1, 0}, {0, -1}, {0, 1}`};
    
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) {
            return 0;
        }
        int numOfIsland = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == '1') {
                    bfsHelper(grid, i, j);
                    numOfIsland ++;
                }
            }
        }
        return numOfIsland;
    }
    
    private void bfsHelper(char[][] grid, int i, int j) {
        Deque<int[]> queue = new ArrayDeque<>();
        queue.offer(new int[]{i, j});
        grid[i][j] = '0';
        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            for (int[] dir : dirs) {
                int x = cur[0] + dir[0];
                int y = cur[1] + dir[1];
                if (x < 0 || x > grid.length - 1 || y < 0 || y > grid[0].length - 1 || grid[x][y] == '0') {
                    continue;
                }
                grid[x][y] = '0';
                queue.offer(new int[]{x, y});
            }
        }
    }
}

Sol 3. Union Find

TODO