The title

200. Number of islands

Given a two-dimensional grid of ‘1’ (land) and ‘0’ (water), count the number of islands in the grid.

Islands are always surrounded by water, and each island can only be formed by connecting adjacent lands horizontally and/or vertically.

Furthermore, you can assume that all four sides of the grid are surrounded by water.

 

Example 1:

Input: the grid = [[" 1 ", "1", "1", "1", "0"], [" 1 ", "1", "0", "1", "0"], [" 1 ", "1", "0" and "0" and "0"], [" 0 "and" 0 ", "0" and "0", "0"]] output: 1Copy the code

Example 2:

Input: the grid = [[" 1 ", "1", "0" and "0" and "0"], [" 1 ", "1", "0" and "0" and "0"], [" 0 "and" 0 ", "1", "0" and "0"], [" 0 "and" 0 ", "0", "1", "1"]] output: 3Copy the code

Method a

Ideas:

Chart depth-first search.

The following steps follow the routine,

  1. Declare a Set object visited, used to store whether a node has been traversed
  2. Declare a count to count the number of islands.
  3. If a node has a value of 1, the number of islands +1, and recursively traverses it up, down, left, and right. If a neighboring node has not been traversed, and the value is 1, recursively traverses the neighboring node up, down, left, and right.
  4. Finally return island count.

The code is as follows:

/ * * *@param {character[][]} grid
 * @return {number}* /
var numIslands = function(grid) {
    if(! grid || grid.length ==0) {return 0;
    }
    let height = grid.length;
    let width = grid[0].length;
    let visited = [];
    for(let i=0; i<height; i++){ visited[i] = [] }let count = 0;
    for(let i=0; i<height; i++){for(let j=0; j<width; j++){if(grid[i][j] == 1&&! visited[i][j]){ count++; dfs(grid,visited,i,j); }}}return count;
};

function dfs(grid,visited,i,j){
    let height = grid.length;
    let width = grid[0].length;
    if(i<0 || i>height-1||j<0||j>width-1||visited[i][j] || grid[i][j] == 0) {return ;
    }
    visited[i][j] = true;
    dfs(grid,visited,i,j+1);
    dfs(grid,visited,i,j-1);
    dfs(grid,visited,i+1,j);
    dfs(grid,visited,i-1,j);
}
Copy the code

Complexity analysis

Time complexity: O(M*N), where M and N are the height and width of the matrix respectively

Space complexity: O(M*N), the array storing Visted is M*N, in addition, when all land, the maximum height of recursive stack is M*N.

Ps: In fact, it can be optimized here. Without visiting, the current node is directly judged to be 0, so the traversal is not required. Then, after each traversal of a land, change its value to 0. I am trying to set a depth-first traversal template for charts. I use a visited to make it easy for everyone to understand.

Method 2

Ideas:

Breadth-first traversal.

  1. Declares a queue for neighboring nodes whose node value is 1.
  2. Declare a variable count to hold the number of islands.
  3. The grid is traversed through each node, pushing it to the queue if the value is 1 and counting +1.
  4. Eject the head node of the queue. If there is a node 1 around the node, the adjacent node is pushed into the queue.
  5. As long as the queue is not empty, keep operating and do not process a node, remember to change the value to 0
  6. The final count is the number of islands.

The code is as follows:

/ * * *@param {character[][]} grid
 * @return {number}* /
var numIslands = function(grid) {
    if(! grid || grid.length ==0) {return 0;
    }
    let height = grid.length;
    let width = grid[0].length;
    let count = 0;
    let queue = [];
    for(let i=0; i<height; i++){for(let j=0; j<width; j++){if(grid[i][j] == 1){
                count++;
                queue.push([i,j])
                while(queue.length>0) {let node = queue.shift();
                    let p = node[0],q = node[1];
                    grid[p][q]=0;
                    offerToQueue(grid,queue,p-1,q);
                    offerToQueue(grid,queue,p+1,q);
                    offerToQueue(grid,queue,p,q-1);
                    offerToQueue(grid,queue,p,q+1); }}}}return count;
};

function offerToQueue(grid,queue,i,j){
    let height = grid.length;
    let width = grid[0].length;
    if(i<0 || j<0 || i>height-1||j>width-1 || grid[i][j] == 0) {return ;
    }
    queue.push([i,j]);
    grid[i][j]=0;
}
Copy the code

Complexity analysis:

Time complexity: O(M*N), where M and N are the height and width of the matrix respectively.

Space complexity: O(M*N),M and N are the height and width of the matrix respectively.

Method three

Check and set.

We can use and look up the set, first process all the nodes, construct the initialization parent-child relationship, and initialize the connecting flux to the land number. Then all nodes are traversed. If the current node is 1, look at its upper, lower, left and right nodes. If there is 1, merge the two nodes, connect flux -1, and finally return the connected quantity.

The code is as follows:

/ * * *@param {character[][]} grid
 * @return {number}* /
var numIslands = function(grid) {
    if(! grid || grid.length ==0) {return 0;
    }
    let height = grid.length;
    let width = grid[0].length;
    let count = 0;
    let parent = new Map(a);// process the parent first, and put the value 1 into the parent
    for(let i=0; i<height; i++){for(let j=0; j<width; j++){if(grid[i][j] == 1) {let node = [i,j];
                parent.set(`${i}_${j}`,node); count++; }}}for(let i=0; i<height; i++){for(let j=0; j<width; j++){// If the value is 1, set its own value to 0 first, then look for its left, right, and left, if found, merge, and count--
             if(grid[i][j] == 1){
                grid[i][j] = 0;
                union(grid,parent,[i,j],[i,j+1= =])1 && count--
                union(grid,parent,[i,j],[i,j-1= =])1 && count--
                union(grid,parent,[i,j],[i-1,j])==1 && count--
                union(grid,parent,[i,j],[i+1,j])==1 && count--
             }
        }
    }
    return count;
};
function union(grid,parent,p,q){
    let height = grid.length;
    let width = grid[0].length;
    if(q[0] <0 || q[1] <0 || q[0]>height-1||q[1]>width-1 || grid[q[0]][q[1= =]]0) {return ;
    }
    let rootP = find(parent,p)
    let rootQ = find(parent,q)
    if(rootP ! = rootQ){ parent.set(`${rootP[0]}_${rootP[1]}`,rootQ)
        return 1; }}function find(parent,node){
    if(parent.get(`${node[0]}_${node[1]}`) != node){
        parent.set(`${node[0]}_${node[1]}`,find(parent,parent.get(`${node[0]}_${node[1]}`)))}return parent.get(`${node[0]}_${node[1]}`);
}
Copy the code

Complexity analysis:

Time complexity: O(MNlog(MN)), first the parent array is MN, then the grid is traversed, the worst case is all islands, each node needs traversed to MN, at this time the find search complexity is logMN, so O(MNlog(MN))

Space complexity: O(M*N), the worst case is all land, then the parent needs to store all nodes