605.种花问题(Easy)

题目描述

一个很长的花坛中已经种了一部分花，要求花与花之间不能相邻，问现在给定n朵花，能不能全部种下。

样例

Input: [1,0,0,0,1], 1
Output: True

Input: [1,0,0,1], 1
Output: False

题解

贪心算法选择最佳种花的位置，当从左向右遍历，选择最近的不相邻的地块种植花朵最优。 具体: 从左向右遍历，当存在0，且左右两侧也是0的时候，种下花

代码示例

Python 示例

class Solution:
    def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:
        if not flowerbed: return False
        for idx in range(len(flowerbed)):
            if (flowerbed[idx] == 0) and \
               (idx == 0 or flowerbed[idx - 1] == 0) and \ 
               (idx == len(flowerbed) - 1 or flowerbed[idx + 1] == 0):
                n -= 1 # 种花
                flowerbed[idx] = 1
            
        return bool(n <= 0)

Go 示例

func canPlaceFlowers(flowerbed []int, n int) bool {
   m := len(flowerbed)
   if m < 1 { return false }
   for i := 0; i < m; i++ {
       if flowerbed[i] == 0 && 
          (i == 0 || flowerbed[i - 1] == 0) && 
          (i == m - 1 || flowerbed[i + 1] == 0) {
              n--
              flowerbed[i] = 1
          }
   }    
   return n <= 0