可以種花嗎? Can Place Flowers_Leetcode 精選75題解析

Annie Spratt on Unsplash

題目敘述

題目會給定我們一格花盆陣列flowerbed，和欲種植的花朵數目n。

花盆陣列中，0代表空位，1代表已經有種好的花盆存在。

種花的要求是，不能有兩兩相鄰的花盆出現，中間一定要間隔至少一個空位。

問我們在給定的條件下，能不能順利種完n個花朵盆栽?

若可以返回True，若無解返回False。

題目的原文敘述

測試範例

Example 1:

Input: flowerbed = [1,0,0,0,1], n = 1
Output: true
我們可以這樣種，剛好種下一個花朵盆栽。
[1,0,1,0,1]​

Example 2:

Input: flowerbed = [1,0,0,0,1], n = 2
Output: false
不行，無解。​

約束條件

Constraints:

• 1 <= flowerbed.length <= 2 * 10^4

花盆陣列的長度介於1~2*10^4之間

• flowerbed[i] is 0 or 1.

花盆陣列內的元素值指有可能為0或1

• There are no two adjacent flowers in flowerbed.

不可有兩兩相鄰種植的花盆

• 0 <= n <= flowerbed.length

n 欲種植的花朵數目介於0~花盆陣列的長度之間

演算法

這題考的就是情境模擬演算法的實現。

考量到這題是一個一維最佳化題目，最佳化目標為種植n個花盆，同時要滿足不可以兩兩相鄰。

我們可以試著朝greedy的思路出發，盡可能的種花，也就是從左邊開始掃描到右邊，遇到可種植空位就種植一朵花，下一步馬上檢查下一個可能的位置，同時讓位置安排越緊湊越好，因為我們要的目標是: 在不可以兩兩相鄰的情況下，種下n個花盆。