九章演算法 | Google 面試題：種花

02-22

撰文 | Ben助教+ 施助教

專欄 | 九章演算法

題目描述

一個長條花壇里有若干並排的花槽，有些花槽中已經種了花，有些則還沒種花。然而，不能將兩株花種在相鄰的花槽否則它們會爭奪水分導致兩者都枯萎。給定一個花壇的種植情況flowerbed（一個包含0和1的數組，0表示該花槽為空，1表示該花槽已經種了花），以及一個數n，問是否可以再種下新的n株花且滿足相鄰花槽不能同時種花的條件。

樣例

樣例 1

輸入： flowerbed = [1,0,0,0,1], n = 1 輸出： True

樣例 2

輸入： flowerbed = [1,0,0,0,1], n = 2輸出： False

注意

輸入數組本身滿足相鄰花槽不同時種花的條件。輸入數組的長度範圍為[1, 20000]。n是非負整數且大小不會超過輸入數組的長度。

解題思路分析

a. 為了儘可能的多種點花，應該使花種得盡量的密集。可以使用貪心的方法種花：從左往右掃描花槽，每遇到一個滿足條件可以種植的花槽（前後花槽都為空或者為邊界），就在這個位置種花，看能種下的花的數量是否大於等於n，是則返回true，否則返回false。一個小優化是當計數計到n時即可直接返回true。演算法時間複雜度為O(n)，額外空間複雜度為O(1)。

b. Follow up：證明該貪心演算法的正確性。證明貪心演算法的正確性一般分為兩部分：證明問題具有最優子結構（在這題中就是對於一個種植數量最多的最優種植方案，將方案中的一株花種下後得到新的花壇，方案除掉這株花之後得到到的剩餘的方案仍是對於新花壇來說的最優方案），以及證明每一步的貪心選擇一定屬於某個最優方案。

參考程序

九章演算法 - 幫助更多中國人找到好工作，矽谷頂尖IT企業工程師實時在線授課為你傳授面試技巧

面試官角度分析

此題屬於簡單的貪心題，解題思路也很直觀。給出正確的演算法即可hire。

lintcode相關問題

打劫房屋