題目

難度：★★☆☆☆
類型：數(shù)組

假設(shè)你有一個很長的花壇，一部分地塊種植了花，另一部分卻沒有?？墒?，花卉不能種植在相鄰的地塊上，它們會爭奪水源，兩者都會死去。

給定一個花壇（表示為一個數(shù)組包含0和1，其中0表示沒種植花，1表示種植了花），和一個數(shù) n 。能否在不打破種植規(guī)則的情況下種入 n 朵花？能則返回True，不能則返回False。

注意
數(shù)組內(nèi)已種好的花不會違反種植規(guī)則。
輸入的數(shù)組長度范圍為 [1, 20000]。
n 是非負整數(shù)，且不會超過輸入數(shù)組的大小。

示例

示例 1:
輸入: flowerbed = [1,0,0,0,1], n = 1
輸出: True

示例 2:
輸入: flowerbed = [1,0,0,0,1], n = 2
輸出: False

解答

這道題需理清邏輯，我們可以使用一個寬度為3的滑窗，這里通過指針i表示滑窗中心，則滑窗中包含3個元素[i-1, i, i+1]，指針i從第二個元素開始遍歷到倒數(shù)第二個元素，在遍歷的過程中，我們查看滑窗中是否所有位置都沒有種花，如果沒有，那么我們在滑窗中心栽一朵，否則繼續(xù)遍歷，如果手頭沒有剩下花了，說明可以栽下那么多，否則不能。這里需要注意的是，我們要考慮兩端的情況，需要將數(shù)組做padding（左右各增加一個0）。

class Solution:
    def canPlaceFlowers(self, flowerbed, n):

        flowerbed = [0] + flowerbed + [0]                               # 左右各加一個空位置
        for i in range(1, len(flowerbed)-1):                            # 遍歷出兩端之外的位置
            if flowerbed[i-1] == flowerbed[i] == flowerbed[i+1] == 0:   # 遇到連續(xù)三個空位置
                flowerbed[i] += 1                                       # 放一盆花
                n -= 1                                                  # 花數(shù)減一
            if n <= 0:                                                  # 如果花用完了，返回True
                return True
        return False                                                    # 花沒用完，返回False

如有疑問或建議，歡迎評論區(qū)留言~