数据结构与算法LeetCode-种花问题No605

LeetCode 605. 种花问题

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

给定一个花坛（表示为一个数组包含 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, 20000]。

n 是非负整数，且不会超过输入数组的大小。

---

我的思路

总的来讲，这道题在 leetCode 中不算难的，关键就是要有思路。下面是我自己做题时的分析。

1. 在两边都是花 中间都是空地的情况下 (关键前提)，算出可以种花的最值。如 [1,0,0,0,0,1]=>1

    连续空地数 可种花的最值
           0  => 0
           1  => 0
           2  => 0
           3  => 1
           4  => 1
           5  => 2
           6  => 2
           7  => 3

有感觉的老哥，估计已经有了想法，没错就是

parseInt((n - 1) / 2 ) = 可以种几颗 // (n 为最近两个花 之间的空地数量)

得出了这个结论 就基本完成了 但是还有 2 种特殊情况, 以下是完整代码（战胜 84% 的 js 提交）

let canPlaceFlowers = (flowerbed, n) => {let filedBegin = flowerbed[0] > 0 ? true : false;
  let filedEnd = flowerbed[flowerbed.length - 1] > 0 ? true : false;
  if (!filedBegin) {flowerbed.unshift(1, 0)
  }
  if (!filedEnd) {flowerbed.push(0, 1)
  }
  // 上面步骤的原因
  // 遇到这两种情况 [0, 0, 1, 0, 0]  或者 [0]
  // 按照 parseInt((n - 1) / 2)  规则得出的都是零 因为这种算法 是以  两边都是花的情况下的结果
  // 而上面这两种 0 的两面 或者有一面 是没有花的 所以手动 给他们加上
  // [0, 0, 1, 0, 0]=> [1, 0, 0, 1, 0, 0, 0, 1]
  // [0]=> [1, 0, 0, 0, 1]
  // 这样就符合我们的规则了

  let size = 0  // 最近两个花 之间的空地数量
  let canfiled = 0 // 可以种植的数量
  for (let i = 1, len = flowerbed.length; i < len; i++) {if (flowerbed[i] > 0) {//
      if (size == 0) continue // 说明 处在 1 1 相邻的情况 直接跳过
      let num = parseInt((size - 1) / 2) // 当前间隔最多可以种植的数量
      canfiled += num
      size = 0 // 重置间隔数量
    } else {// 当前是空地  空地数量 +1
      size++
    }
  }
  return canfiled >= n
};

2. 最快的范例
这种思路是以每个循环的元素为核心 当 当前空地元素的前一个元素和后一个元素为空地 那么代表着能够种植，（当然 依然要考虑到目标数组的头尾为空地 0 的情况）而且直接改变原数组 flowerbed[j] = 1 -> 这是他逻辑中画龙点睛的步骤

var canPlaceFlowers = function (flowerbed, n) {
  // 定义一个 sum = 0
  // 遍历花坛，找到这样一个位置，此位置空，&& 前后都为空，则 sum+1
  // 判断 sum 与 n 大小比较
  [0, 1, 0]
  if (!n) return true;
  var sum = 0
  var length = flowerbed.length
  for (var j = 0; j < length; j++) {if (!flowerbed[j]) {// 当前是 空地
      // 对于右侧的限制条件 true 表示可以种植（仅对于左侧来讲）var leftVoid = j === 0 || flowerbed[j - 1] === 0
      // 对于右侧的限制条件 true 表示可以种植（仅对于右侧来讲）var rightVoid = j === length - 1 || flowerbed[j + 1] === 0
      if (leftVoid && rightVoid) {
        // 可以种植
        flowerbed[j] = 1  // 直接将改位置 种上花  让后面的判断顺利进行  比较关键
        sum++
        if (sum === n) {  // 循环次数  可能少些 因为 sum 的最大值是大于等于 n 才能满足
          return true
        }
      }
    }
  }

  return false
}

如果喜欢 LeetCode 或者更多数据结构的内容，可以戳这里, 欢迎 star