Number of Islands (Question No. 200)

The title

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.

In addition, 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

Tip:

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 300
  • Grid [I][j] = ‘0’ or ‘1’

link

Leetcode-cn.com/problems/nu…

explain

This wave, this wave is confused.

To tell the truth, people who have not been exposed to such problems should be difficult to think of the solution, anyway, the author here is not able to do.

After looking at the train of thought, I tried to write out two solutions

The detailed explanation is in the code, 👇 :

Your own answer (FloodFill)

Just see the name of the time is meng, looks very difficult to understand the appearance of ah, in fact is not 🐶.

It’s actually quite simple, and it works in this case, because 0 is water and 1 is land. And the land can be connected to the land above and below and left and right, so you can get the first land and change it to 0, and then you can iterate over the land above and below and left and right, and if it’s 1, change it to 0, and then you can continue to look for the land around it, and you can iterate or you can recurse.

By the way, don’t forget to accumulate the statistics before each recursion.

After all the points have been traversed, all the points should be 0, because all the ones have been changed to 0, and this is what’s called the flooding algorithm, which is like flooding the whole land, which is perfect for this problem.

👇 look at the code:

var numIslands = function(grid) {
  var lenI = grid.length - 1
      lenJ = grid[0].length - 1
      loop = [-1, 1]
      count = 0
  function findNeighbor(i, j) {
    if (i < 0 || i > lenI) return
    if (j < 0 || j > lenJ) return
    if (grid[i][j] === '0') return
    grid[i][j] = '0'
    for (let k = 0; k < loop.length; k++) {
      findNeighbor(i + loop[k], j)
      findNeighbor(i, j + loop[k])
    }
  }
  for (let i = 0; i <= lenI; i++) {
    for (let j = 0; j <= lenJ; j++) {
      if (grid[i][j] === '1') {
        count++
        findNeighbor(i, j)
      }      
    }    
  }
  return count
};
Copy the code

The overall logic is simple. There is a recursive function, findNeighbor, to wipe out all relevant landmasses, and a count is accumulated before the recursion begins to return the final value.

The inner implementation of findNeighbor is simple. It first determines the boundary value and returns directly if it crosses the boundary, and returns directly if it is water itself.

The next step is to take up, down, left and right data. Here we use a loop array to get the adjacent blocks, avoiding the ugly code of calling findNeighbor four times. Of course, if you change the loop to a two-dimensional array here, you only need to call findNeighbor once.

That’s it. That’s the easiest way to write it.

Your own answers (and look up the set)

The concept of looking up sets is not very complicated, there is a good brother said, put a link here, no longer repeat, click here, the brother’s code Java, you can not see, mainly see its concept, said really very clear, and very interesting.

After watching this concept is very easy to understand, here in the loop for the first time set the parent of each piece of land is to land myself, after the second traversal, if the current is land, and the land around the land, then put together two pieces of land, if in the end you can get a set of perfect and check.

If you want to count the number of lands, you can put it inside the set and look it up, add 1 every time you addSet, and then subtract 1 when you connect two lands.

Without further ado, look at the code 👇 :

class UnionFind { constructor() { this.parents = new Map() this.count = 0 } addSet(location) { location = location.toString() this.parents.set(location, location) this.count++ } findSet(location) { location = location.toString() while (this.parents.get(location) ! == location) { location = this.parents.get(location) } return location } unionSet(location1, location2) { var location1Parent = this.findSet(location1) var location2Parent = this.findSet(location2) if (location1Parent === location2Parent) return this.parents.set(location1Parent, location2Parent) this.count-- } getCount() { return this.count } } function numIslands(grid) { var len1 = grid.length len2 = grid[0].length uf = new UnionFind() loop = [1, -1] for (let i = 0; i < len1; i++) { for (let j = 0; j < len2; j++) { if (grid[i][j] === '1') uf.addSet([i, j]) } } for (let i = 0; i < len1; i++) { for (let j = 0; j < len2; j++) { if (grid[i][j] === '1') { for (let k = 0; k < loop.length; k++) { if (grid[i + loop[k]] && grid[i + loop[k]][j] === '1') { uf.unionSet([i, j], [i + loop[k], j]) } if (grid[i][j + loop[k]] && grid[i][j + loop[k]] === '1') { uf.unionSet([i, j], [i, j + loop[k]]) } } } } } return uf.getCount() }Copy the code

It’s a little bit longer code here, but first of all, it’s the definition of a UnionFind class, so that’s the UnionFind set here.

The internal implementation is also relatively simple, 👇 to take a look at:

  • constructor

    There’s nothing to say. I’ve defined variables parents and count

  • addSet

    Each time you add a node, you set the parent to itself, where the key of the object corresponds to the value, and then count increments by one

  • findSet

    So this method is going to find the parent at the top of the node, and we’re going to use a while to find the parent at the top of the node.

  • unionSet

    This method is used to connect two nodes. First find the top parent of the two nodes. If they are one parent, it doesn’t matter. If not, set one node’s top parent to the other.

    And then count decrement by one, because the two nodes are joined together, which is equal to getting rid of one node.

  • getCount

    Finally get the count and return.

After that, the logic is the same as before, first of all, you go through the array, you get the so-called land elements, and you insert them into and look up the set. At this point, all elements in the set have a single land and their parent is themselves.

Then proceed the second traversal. At this time, start to join the set and look up. For each connected land, subtract 1 from the total count, so that the final result can be obtained after the operation of all single land elements.

summary

Here though, the solution and check the set is given out, but it is not a good method, poor performance and flooding algorithm too much, flooding algorithm time and memory footprint can can be over 95% to the top, but the solution and check the set only to around 5%, is very poor is very poor, of course, also because I write is not good, see a loop only once and check the set of solutions, It looks good. Here’s a link for reference.




PS: To view past articles and titles, click on the link below:

Here’s 👇 by date

Front Brush path – Directory (Date classification)

After some friends remind, the feeling should also be classified according to the type of questions here is in accordance with the type of 👇

Front brush problem path – Catalogue (Question type classification)

Those who are interested can also check out my personal homepage 👇

Here is RZ