题目

假设有一个很长的花坛，一部分地块种植了花，另一部分却没有。可是，花不能种植在相邻的地块上，它们会争夺水源，两者都会死去。
给你一个整数数组 flowerbed 表示花坛，由若干 0 和 1 组成，其中 0 表示没种植花，1 表示种植了花。另有一个数 n ，能否在不打破种植规则的情况下种入 n 朵花？能则返回 true ，不能则返回 false。

考察知识点

贪心算法
分配问题

思考

贪心算法之所以叫贪心算法，是因为它要求每次操作都是组局最优的，从而使最后得到的结果是全局最优的。

如何让其种花是最优的呢

我看读题可发现，种花是有要求的，花不能种在相邻的地块上，因为它们会争夺水源
而种啦花在数组中用1表示 每种的用0表示 那吗最优的种花数组表示法为[0,1,0]
[0,1,0] 除啦这一种最优的还有其他的吗？
思考一下开始和结尾需不需要种花
当开始位置种花用数组表示为[1,0]
当结尾位置种花用数组表示为[0,1]

总结规律

[0,1,0] : 空地 花 空地
[1,0]：花 空地
[0,1]： 空地 花
数组当前位 等于 0
上一位不能等于 1 因为 开始于结束位置 用数组表示为 [undefined, 1 , 0] [0, 1 , undefined] 当其判断条件为 等于 0 那吗开头与结尾就不能满足条件
下一位不能等于 0

代码实现

自己实现

  1. var canPlaceFlowers = function (flowerbed, n) {
  2.     for (let i = 0; i < flowerbed.length; i++) { 
  3.         if(flowerbed[i] === 0 && flowerbed[i - 1] !== 1 && flowerbed[i + 1] !== 1){
  4.             flowerbed[i] = 1;
  5.             --n;
  6.             if(n <= 0) return true;
  7.         }
  8.     }
  9.     return n <= 0
  10. }

其他思路参考

  1. /**
  2.  * @param {number[]} flowerbed
  3.  * @param {number} n
  4.  * @return {boolean}
  5.  */
  6. var canPlaceFlowers = function(flowerbed, n) {
  7.     flowerbed.push(0);
  8.     flowerbed.unshift(0);
  9.     for(let i = 1; i < flowerbed.length - 1; i++){
  10.         if(flowerbed[i-1] + flowerbed[i] + flowerbed[i+1] == 0){
  11.             flowerbed[i] = 1;
  12.             n--;
  13.         }
  14.         if(n <= 0) return true;
  15.     }
  16.     return n <= 0;
  17. };