4、种花问题

原题：力扣《种花问题》
难度：简单

题目

假设有一个很长的花坛，一部分地块种植了花，另一部分却没有。可是，花不能种植在相邻的地块上，它们会争夺水源，两者都会死去。
给你一个整数数组 flowerbed 表示花坛，由若干 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 <= flowerbed.length <= 2 * 104
• flowerbed[i] 为 0 或 1
• flowerbed 中不存在相邻的两朵花
• 0 <= n <= flowerbed.length

解题

个人

关键：小算法 + 硬解的

1. 规则：花不能相邻，则两个花之间 0 的数量 >= 1
2. 要求：能否再种 n 朵花，那就是将现有的 0，按规则转为 1 后，看 n 是否还剩有，有剩的则不能种，否则能种
3. 现有的 0 能否转为 1 呢？将它转为 1 后，判断前后是否都为 0，是则可转

/**
 * @param {number[]} flowerbed
 * @param {number} n
 * @return {boolean}
 */
var canPlaceFlowers = function (flowerbed, n) {
  if (flowerbed.length < 2) {
    if (flowerbed.length === 0) return false; // 处理 []
    else if (flowerbed[0] === 0) return true; // 处理 [0]
  }

  // 种下一朵花
  const placeFlower = (index) => {
    flowerbed[index] = 1;
    n--;
  };

  for (let index = 0, len = flowerbed.length; index < len; index++) {
    const element = flowerbed[index];

    if (element === 0) {
      // element === 0 表明当前位置为空

      if (index === 0 && flowerbed[index + 1] === 0) {
        // 处理第一列，只需判断右边是否为 0，即可以种下一朵花
        placeFlower(index);
        continue;
      }

      if (flowerbed[index - 1] === 0 && flowerbed[index + 1] === 0) {
        // 则可以转为 1，即能种下一朵花
        placeFlower(index);
        continue;
      }

      if (index === len - 1 && flowerbed[index - 1] === 0) {
        // 处理最后列，只需判断左边是否为 0，即可以种下一朵花
        placeFlower(index);
        continue;
      }
    }
  }

  return n <= 0;
};

执行用时，消耗内存
61 ms，51.21 MB

耗时：23 min

官方

关键：贪心
思路：非常复杂，我看不懂

社区

关键：跳格子
思路：

1. 当 f[index] 为 1 时，则表明当前已种花，那 index+1 必为 0，且不能种花，因此跳两格 index+2 重新判断
2. 当 f[index] 为 0 时，则表明当前未种花，由于第一步遇 1 跳两格，则 index-1 必为 0，那只需要判断 index+1 是否为 1，若不为 1 则能种花并跳两格 index+2，若为 1 则不能种并跳三格 index+3 重新判断

var canPlaceFlowers = function (flowerbed, n) {
  if (flowerbed.length < 2) {
    if (flowerbed.length === 0) return false; // 处理 []
    else if (flowerbed[0] === 0) return n <= 1; // 处理 [0]
  }
  let start = 0;

  while (start < flowerbed.length && n > 0) {
    if (flowerbed[start] === 0) {
      // 当前没种花
      if (flowerbed[start + 1] === 0 || start == flowerbed.length - 1) {
        // 当前位置为空，且右边也为空，可以种花
        n--;
        start += 2;
      } else {
        // 当前位置为空，且右边不为空，不可以种花
        start += 3;
      }
    } else {
      // 当前已种花
      start += 2;
    }
  }
  return n <= 0;
};

执行用时，消耗内存
67 ms，51.28 MB

总结

这次没具体的算法名称，所以靠自己找规律。