原题地址

贪心算法

这题非常简单，一看就是贪心来求解， 从左到右遍历数组，在符合条件的地方种花即可 。

什么样的地方是可以种花的呢？

满足 flowerbed[i] == 0 and flowerbed[i-1] == 0 and flowerbed[i+1] == 0 的地方可以种花。

参考代码1

注意： i==0 and i ==lens-1 是首尾，为了能统一用上面公式解决，可以在首尾添0

 复制代码
class Solution:
    def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:
        # 为了统一处理，给数组的首和尾添加0
        flowerbed.insert(0, 0)
        flowerbed.append(0)
        lens = len(flowerbed)
        for i in range(1, lens-1):
            # 如果i-1处为0，i+1处为0，可种植
            if flowerbed[i-1] == 0 and flowerbed[i] == 0 and flowerbed[i+1] == 0:
                flowerbed[i] = 1
                n -= 1
            if n <= 0:
                return True
        return False

参考代码2

也可以将以上公式稍作改变，来适应首尾特殊情况
flowerbed[i] == 0 and (i==0 or flowerbed[i-1] == 0) and (i==lens-1 or flowerbed[i+1] == 0)

 复制代码
class Solution:
    def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:
        lens = len(flowerbed)
        for i in range(lens):
            # 如果i-1处为0，i+1处为0，可种植
            if (i==0 or flowerbed[i-1] == 0) and flowerbed[i] == 0 and (i==lens-1 or flowerbed[i+1] == 0):
                flowerbed[i] = 1
                n -= 1
            if n <= 0:
                return True
        return False