605.种花问题

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

题解 1 - typescript

• 编辑时间：2021-01-02
• 执行用时：96ms
• 内存消耗：41.2MB
• 编程语言：typescript
• 解法介绍：计算每朵花之间的空格进行累加,与 n 比较。

function canPlaceFlowers(flowerbed: number[], n: number): boolean {
  const computeCount = (num: number) => (num < 1 ? 0 : ~~((num + 1) / 2));
  let max = 0;
  const len = flowerbed.length;
  if (flowerbed.every(v => v === 0)) return computeCount(len) >= n;
  const list: number[] = [];
  flowerbed.forEach((v, i) => v && list.push(i));
  for (let i = 0, l = list.length; i < l; i++) {
    const index = list[i];
    if (i === 0 && index > 1) max += computeCount(index - 1);
    if (i === l - 1) max += computeCount(len - index - 2);
    else max += computeCount(list[i + 1] - index - 3);
  }
  return max >= n;
}

题解 2 - python

• 编辑时间：2023-09-29
• 执行用时：60ms
• 内存消耗：16.3MB
• 编程语言：python
• 解法介绍：同上。

class Solution:
    def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:
        prev = -1
        for i in range(len(flowerbed)):
            if flowerbed[i] == 0:
                if prev + 1 == i and (i == len(flowerbed) - 1 or flowerbed[i + 1] == 0):
                    n -= 1
                else:
                    prev = i
        return n <= 0