Number of Islands

两种解法; 解法1, dfs flooding来count有多少个unique islands. 这个会修改原数组.

解法二, union find, root最后的数量决定了多少个islands. 第一步认为所有'1'的点根为自身, 一共有n个岛屿, n为1的个数. 不断对4个方向做union, 做一次union操作, n的数量减一, 直到做完所有union. 一个需要注意的地方, union find的root array将二维数组map到了一维数组. a[x][y] = root[x*m+y];

    public int numIslands(char[][] grid) {

        if (grid==null || grid.length==0 || grid[0].length==0) return 0;
        int count = 0;
        for(int i=0;i<grid.length;i++)
            for(int j=0;j<grid[0].length;j++){
                if(grid[i][j]=='1'){
                    count++;
                    merge(grid, i, j);
                }
            }
            return count;
    }

    public void merge(char[][] grid, int i, int j){
        if(i< 0 || j < 0 || i>=grid.length || j>=grid[0].length || grid[i][j]!='1')
            return;
        grid[i][j] = '0';
        merge(grid, i-1,j);
        merge(grid, i+1, j);
        merge(grid, i, j-1);
        merge(grid, i, j+1);
    }

解法二: Union FInd

public int numIslands(char[][] grid){
        if(grid==null || grid.length==0 || grid[0].length==0) return 0;
        int[] x = {-1, 0, 0, 1};
        int[] y = {0,-1, 1, 0};
        UnionFind uf = new UnionFind(grid);
        for(int i=0;i<grid.length;i++)
            for(int j=0;j<grid[0].length;j++){
                if(grid[i][j]=='1'){
                    for(int k=0;k<4;k++){
                        int xx = i+x[k];
                        int yy = j+y[k];
                        if(xx>=0 && xx<grid.length && yy>=0 && yy<grid[0].length && grid[xx][yy]=='1')
                            uf.union(i*grid[0].length + j, xx*grid[0].length+yy);
                    } 
                }
            }
        return uf.count;
    }

}

 class UnionFind{
    int[] root;
    int row; int col;
    int count = 0;
    public UnionFind(char[][] grid){
        this.row = grid.length; this.col = grid[0].length;
        root = new int[row*col];
        Arrays.fill(root, -1);
        for(int i=0;i<row;i++)
            for(int j=0;j<col;j++){
                if(grid[i][j]=='1'){
                    root[i*col +j] = i*col+j;
                    count++;
                }
            }
    }

    public void union(int p1, int p2){
        int root1 = find(p1);
        int root2 = find(p2);
        if(root1!=root2){
         root[root2] = root1;
         count--;   
        }
    }

    public int find(int x){

        while(root[x]!=x) x= root[x];
        return x;

    }

}

Surrounded Regions

开始用了dfs flooding, 用list保存所有O的点, dfs如果返回true, 证明被完全包裹后, 将list里的点全部置为X. Stackover flow

public class Solution {
    public void solve(char[][] board) {
        if(board ==null || board.length==0||board[0].length==0) return;
        int m = board.length; int n = board[0].length;
        for(int i=0;i<m;i++)
            for(int j=0;j<n;j++){
                if(board[i][j]=='O'){
                    List<Integer> list = new ArrayList<Integer>();
                    if(dfs(board, list, i, j)){
                        for(int p : list){
                            board[p/n][p%n] = 'X';
                        }
                    }
                }
            }
    }

    public boolean dfs(char[][] board, List<Integer> list,  int i, int j){
        int m = board.length; int n = board[0].length;
        if(i<0||i>=m||j<0 ||j>=n) return false;
        if(board[i][j]=='X' || list.contains(i*n+j)) return true;
        list.add(i*n+j);
        if(dfs(board, list, i-1,j)==false) return false;
        if(dfs(board, list, i+1,j)==false) return false;
        if(dfs(board, list, i,j-1)==false) return false;
        if(dfs(board, list, i,j+1)==false) return false;

        return true;
    }
}

更好的方式是从四条边的O向中心扫描. 将扫到的O标记为S. 最后将O变成X, S变成O. 然而当边上所有的点都是O的时候, 还是会TLE. 一维数组都是0时.

public class Solution {
    public void solve(char[][] board) {
        if(board ==null || board.length==0||board[0].length==0) return;
        int m = board.length; int n = board[0].length;
        for(int i=0;i<m;i++){
            if(board[i][0]=='O')
                dfs(board, i, 0);
            if(board[i][n-1]=='O')
                dfs(board, i, n-1);
        }

        for(int j=0;j<n;j++){
            if(board[0][j]=='O')
                dfs(board, 0, j);
            if(board[m-1][j]=='O')
                dfs(board, m-1, j);
        }

        for(int i=0;i<m;i++)
            for(int j=0;j<n;j++){
                if(board[i][j]=='O'){
                    board[i][j] = 'X';
                }
                if(board[i][j]=='#'){
                    board[i][j] = 'O';
                }
            }
    }

    public void dfs(char[][] board, int i, int j){
        int m = board.length; int n = board[0].length;
        if(i<0||i>=m||j<0 ||j>=n || board[i][j]=='X'||board[i][j]=='#') return;
        board[i][j] = '#';
        dfs(board, i-1,j);
        dfs(board, i+1,j);
        dfs(board, i,j-1);
        dfs(board, i,j+1);
    }
}

这道题还可以用Union Find, 如果O点的root在边上, 就保持为O, 否则设为X.