coding-challenges/leetcode/605-can-place-flowers.js at master · xiaoyunyang/coding-challenges · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
/**
 * @param {number[]} flowerbed
 * @param {number} n
 * @return {boolean}
 */
var canPlaceFlowersGreedy = function(flowerbed, n) {
  let planted = 0
  for(let i=0; i<flowerbed.length; i++) {
    if(flowerbed[i]===0 && !flowerbed[i-1] && !flowerbed[i+1]) {
      flowerbed[i] = 1
      planted++
    }
    if(planted>=n) return true
  }
  return false
};


/**
 * @param {number[]} flowerbed
 * @param {number} n
 * @return {boolean}
 */
var canPlaceFlowers = function(flowerbed, n) {
  let zeros = 0
  let canPlant = 0
  let prevOne = -1
  for(let i=0; i<flowerbed.length; i++) {
    if(flowerbed[i]!==1) continue

    if(prevOne===-1) {
      canPlant+= (i>>1)
    } else {
      const numZeros = (i-prevOne-1)
      canPlant+= (numZeros-1)>>1
    }
    if(canPlant>=n) return true
    prevOne = i

  }
  if(prevOne===-1) {
    canPlant+= (flowerbed.length+1)>>1
  } else if(prevOne<flowerbed.length) {
    canPlant+= (flowerbed.length-prevOne-1)>>1
  }
  return canPlant>=n
};