題目
假設你有一個很長的花壇肚豺，一部分地塊種植了花，另一部分卻沒有党瓮。可是盐类，花卉不能種植在相鄰的地塊上寞奸，它們會爭奪水源，兩者都會死去在跳。
給定一個花壇（表示為一個數(shù)組包含0和1枪萄，其中0表示沒種植花，1表示種植了花）猫妙，和一個數(shù) n 瓷翻。能否在不打破種植規(guī)則的情況下種入 n 朵花？能則返回True割坠，不能則返回False齐帚。
注意:
- 數(shù)組內(nèi)已種好的花不會違反種植規(guī)則。
- 輸入的數(shù)組長度范圍為 [1, 20000]彼哼。
- n 是非負整數(shù)对妄，且不會超過輸入數(shù)組的大小。
思路
典型的貪心算法敢朱。
遍歷一次數(shù)組剪菱，針對遍歷的不同位置做不同的判斷：
- 如果
i == 0摩瞎， 檢查flowerbed[0]和flowerbed[1]是否為0- 若同時為0，則令
flowerbed[0] = 1, n--;
- 若同時為0，則令
- 如果
i == len - 1孝常，檢查flowerbed[len-1]和flowerbed[len-2]是否為0旗们，- 若同時為0，則令
flowerbed[len-1] = 1, n--;
- 若同時為0，則令
- 否則构灸，檢查
flowerbed[i-1],[i],[i+1]是否為0上渴，- 若同時為0，則
令flowerbed[i] = 1冻押，n--驰贷；
- 若同時為0，則
遍歷結束后，檢查n是否大于0,
- 大于0洛巢，返回
false括袒； - 小于等于0，返回
true稿茉；
實現(xiàn)
Java
class Solution {
public boolean canPlaceFlowers(int[] flowerbed, int n) {
int len = flowerbed.length;
if (len == 0) return false;
if (len == 1) {
if (n == 0) return true;
else if (n == 1) return flowerbed[0] == 0;
else return false;
}
for (int i = 0; i < len; i++) {
if (i == 0) {
if (flowerbed[i] == 0 && flowerbed[i+1] == 0) {
flowerbed[i] = 1;
n--;
}
}else if (i == len - 1) {
if (flowerbed[i] == 0 && flowerbed[i-1] == 0) {
n--;
flowerbed[i] = 1;
}
}else {
if (flowerbed[i] == 0 && flowerbed[i-1] == 0 && flowerbed[i+1] == 0) {
n--;
flowerbed[i] = 1;
}
}
}
return n > 0 ? false : true;
}
}
