[recommend for beginners]clean C++ implementation with detailed explaination


  • 2

    I really want to kill myself when I find I mistake the '=' to '=='

       ALL IN ALL, this problem is really easy if you are familiar with the DFS. 
    

    here is my implementation

     class Solution {
        public:
            int numIslands(vector<vector<char>>& grid) {
                int m=grid.size();
                if(m==0)  return 0;
        
                int n=grid[0].size();
                int result=0;
                for(int i=0; i<m; i++){
                    for(int j=0; j<n; j++){
                        if(grid[i][j]=='1'){
                            help(i, j, grid);
                            result++;
                        }
                    }
                }
                return result;
            }
        
            void help(int i, int j, vector<vector<char>>& grid){
                if(i<0 || i>=grid.size() || j<0 || j>=grid[0].size() || grid[i][j]=='0')   return;
        
                grid[i][j]=='0';
                help(i+1, j, grid);
                help(i-1, j, grid);
                help(i, j+1, grid);
                help(i, j-1, grid);
                return;
            }
        };

  • 0
    class Solution {
    public:
        int numIslands(vector<vector<char>>& grid) {
            int m=grid.size();
            if(m==0)    return 0;
            int n=grid[0].size();
            
            int result=0;
            for(int i=0; i<m; i++){
                for(int j=0; j<n; j++){
                    if(grid[i][j]=='1'){
                        help(i, j, grid);
                        result++;
                    }
                }
            }
            return result;
        }
        
        void help(int i, int j, vector<vector<char>>& grid){
           /*** make sure the corner condition is OK ***/
            if(i<0 || i>=grid.size() || j<0 || j>=grid[0].size() || grid[i][j]=='0')
                return;
            grid[i][j]='0';
            help(i+1, j, grid);
            help(i-1, j, grid);
            help(i, j+1, grid);
            help(i, j-1, grid);
        }
    };

  • 0
    M

    Where is the detailed explanation?


  • 0

    Update : Number of Islands 2

    Here is a post from the @dietpepsi

    We use the UnionFind typical class defination to help us accelerate the code !

    Here are the key points :

      change the 2D index to 1D representation
    
      use the union find 
    

    Here is AC implementation :

    public class Solution {
    
        private int[][] dir = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};
    
        public List<Integer> numIslands2(int m, int n, int[][] positions) {
            UnionFind2D islands = new UnionFind2D(m, n);
            List<Integer> ans = new ArrayList<>();
            for (int[] position : positions) {
                int x = position[0], y = position[1];
                int p = islands.add(x, y);
                for (int[] d : dir) {
                    int q = islands.getID(x + d[0], y + d[1]);
                    if (q > 0 && !islands.find(p, q))
                        islands.unite(p, q);
                }
                ans.add(islands.size());
            }
            return ans;
        }
    }
    

    }

    Here is the defination of the Union Find class :

    class UnionFind2D {
        private int[] id;
        private int[] sz;
        private int m, n, count;
    
        public UnionFind2D(int m, int n) {
            this.count = 0;
            this.n = n;
            this.m = m;
            this.id = new int[m * n + 1];
            this.sz = new int[m * n + 1];
        }
    
        public int index(int x, int y) { return x * n + y + 1; }
    
        public int size() { return this.count; }
    
        public int getID(int x, int y) {
            if (0 <= x && x < m && 0<= y && y < n)
                return id[index(x, y)];
            return 0;
        }
    
        public int add(int x, int y) {
            int i = index(x, y);
            id[i] = i; sz[i] = 1;
            ++count;
            return i;
        }
    
        public boolean find(int p, int q) {
            return root(p) == root(q);
        }
    
        public void unite(int p, int q) {
            int i = root(p), j = root(q);
            if (sz[i] < sz[j]) { //weighted quick union
                id[i] = j; sz[j] += sz[i];
            } else {
                id[j] = i; sz[i] += sz[j];
            }
            --count;
        }
    
        private int root(int i) {
            for (;i != id[i]; i = id[i])
                id[i] = id[id[i]]; //path compression
            return i;
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.