Last Updated on 2023-03-20 by Clay
題目
You have a long flowerbed in which some of the plots are planted, and some are not. However, flowers cannot be planted in adjacent plots.
Given an integer array flowerbed
containing 0
's and 1
's, where 0
means empty and 1
means not empty, and an integer n
, return if n
new flowers can be planted in the flowerbed
without violating the no-adjacent-flowers rule.
Example 1:
Input: flowerbed = [1,0,0,0,1], n = 1 Output: true
Example 2:
Input: flowerbed = [1,0,0,0,1], n = 2 Output: false
Constraints:
1 <= flowerbed.length <= 2 * 104
flowerbed[i]
is0
or1
.- There are no two adjacent flowers in
flowerbed
. 0 <= n <= flowerbed.length
題目給定一個花壇的列表,0 代表並未種花、1 代表已經有種花。種花存在著限制,就是花不能相鄰地種植。
題目還會給定一個 n
值,代表著我們還希望能夠種多少朵花。如果能在當前的花壇中種完,回傳 true
反之則回傳 false
。
解題思路
我們依序遍歷整個花壇的列表,並在左右兩側為 0 或超出邊界的情況種植花朵(也就是把列表當前位置補上 1),然後將 n 減去 1,繼續遍歷下一個數值,頗有 greedy search 的感覺。
如果 n 能夠減至 0,則代表可以完成種植任務。
C++ 範例程式碼
class Solution {
public:
bool canPlaceFlowers(vector<int>& flowerbed, int n) {
for (int i=0; i<flowerbed.size(); ++i) {
if ((flowerbed[i] == 0) && (i == 0 || flowerbed[i-1] == 0) && (i == flowerbed.size()-1 || flowerbed[i+1] == 0)) {
flowerbed[i] = 1;
--n;
}
if (n <= 0) {
return true;
}
}
return n <= 0;
}
};
Python 範例程式碼
class Solution:
def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:
for i in range(len(flowerbed)):
if flowerbed[i] == 0 and (i == 0 or flowerbed[i-1] == 0) and (i == len(flowerbed)-1 or flowerbed[i+1] == 0):
flowerbed[i] = 1
n -= 1
if n <= 0:
return True
return n <= 0