605. 种花问题

[buuing]

假设你有一个很长的花坛，一部分地块种植了花，另一部分却没有。可是，花卉不能种植在相邻的地块上，它们会争夺水源，两者都会死去。

给定一个花坛（表示为一个数组包含0和1，其中0表示没种植花，1表示种植了花），和一个数 n 。能否在不打破种植规则的情况下种入 n 朵花？能则返回True，不能则返回False。

示例 1:

输入: flowerbed = [1,0,0,0,1], n = 1
输出: True

示例 2:

输入: flowerbed = [1,0,0,0,1], n = 2
输出: False

注意:

1. 数组内已种好的花不会违反种植规则。
2. 输入的数组长度范围为 [1, 20000]。
3. n 是非负整数，且不会超过输入数组的大小。

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/can-place-flowers 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

---

• 贪心算法

为了不考虑边界问题, 我分别在开头和结尾的位置添加一个0

接下来开始看规律

101 => 连续1个0 => 0 1001 => 连续2个0 => 0 10001 => 连续3个0 => 1 100001 => 连续4个0 => 1 1000001 => 连续5个0 => 2 10000001 => 连续6个0 => 2 100000001 => 连续7个0 => 3

由此我们可以推测出一个公式: (count / 2 + 0.5 >> 0) - 1

后面的思路就变的很简单, 当遇到0的时候, 我们只负责计数, 当遇到1的时候, 就结算当前的count, 所以我在最后又push了一个1用来结算最后一次

const canPlaceFlowers = (flowerbed, n) => {
  flowerbed.unshift(0)
  flowerbed.push(0, 1)
  let count = 0
  for (let i = 0; i < flowerbed.length; i++) {
    let curr = flowerbed[i]
    if (curr === 1) {
      const num = (count / 2 + 0.5 >> 0) - 1
      if (num > 0) {
        n -= num
        if (n <= 0) return true
      }
      count = 0
    } else {
      count++
    }
  }
  return n <= 0
}