JavaScript implementation of twitter puddles algorithm example

JavaScript implementation of twitter puddles algorithm example_javascript skills

WBOY

Release： 2016-05-16 16:28:48

Original

1388 people have browsed it

I found a very interesting algorithm question today. The following is its algorithm description, which is derived from an interview question on Twitter.

Twitter puddles algorithm description

Look at a picture first

The numbers in the picture above are described based on the contents of an array. Finally, the height of a wall will be simulated based on the size of each number, and finally a wall will be generated. I ask you, when it rains, this wall can be installed How much water, in units of 1.

Here is what a wall looks like after filling it with water

After reading the above picture, I think it is very interesting. Indeed, let’s briefly analyze its algorithm implementation

In fact, this principle is relatively simple. There are a few key points in total:

1. The far left and rightmost sides must not be filled with water
2. The height of water filling depends on the minimum of the two maximum values on the left and right sides

Below we use js to simply implement it:

Copy code The code is as follows:

/**

* Calculate how much water a wall with the array item as the height can hold 

* Array example [2,5,1,2,3,4,7,7,6,9]

**/

function getWaterCounts(arg){

var i = 0,

        j = 0,

Count = 0;

// Both the first and last items must be excluded

for(i = 1; i < arg.length - 1; i ){

      var left = Math.max.apply(null, arg.slice(0, i 1));

      var right = Math.max.apply(null, arg.slice(i, arg.length));

        var min = left >= right ? right : left;

              // The smaller of the maximum values ​​on the left and right sides shall prevail 

​​​​ //If the current value is greater than or equal to this value, do nothing

           if(arg[i] < min){

Count = min - arg[i];

}

}

console.log(count);

}

getWaterCounts([2,5,1,2,3,4,7,7,6,9]); // 11

Summary

Hey, the implementation is quite simple, in fact, as long as you are willing to think, you can achieve a lot of fun things with js.