This is the 7th day of my participation in Gwen Challenge

The topic of dry

Suppose you have a very long flower bed, and one part of the plot is planted with flowers, but the other part is not. However, flowers cannot grow in adjacent plots. They compete for water and both die.

Flowerbed gives you an array of integers representing a flowerbed, consisting of zeros and ones, where 0 indicates no flowers and 1 indicates flowers. Another number, n, can I plant n flowers without breaking the planting rules? Returns true if yes, false if no.

Example 1:

Input: flowerbed = [1,0,0,0,1], n = 1 Output: trueCopy the code

Example 2:

Input: flowerbed = [1,0,0,0,1], n = 2 output: falseCopy the code

Idea: Greedy thinking

How do we find local optimality in this problem? I think is a comparison between three elements, as long as the num [I] element accords with a condition, is to judge num and num [I – 1] [I + 1] value, there are two special values need to be processed, is the head end and the end of the boundary value, if the conditions for growing flowers, we will assume that the first side after an element of 0 before or at the end of the a element is zero, This will meet the demand.

Execution time: 88 ms, beating 80.24% of all JavaScript commits

Memory consumption: 39.5 MB, beating 97.59% of all JavaScript commits

var canPlaceFlowers = function (flowerbed, n) {
    let length = flowerbed.length
    for (let i = 0; i < length; i++) {
      if (n == 0) break
      if (flowerbed[i] == 1) {
        continue;
      }
      let pre = i == 0 ? 0 : flowerbed[i - 1]
      let next = i == length - 1 ? 0 : flowerbed[i + 1]
      if (pre == 0 && next == 0) {
        n--
        flowerbed[i] = 1; }}return n <= 0
  };
Copy the code