LeetCode演算法題-Can Place Flowers（Java實現）
這是悅樂書的第272 次更新，第287 篇原創
01 看題和準備
今天介紹的是LeetCode演算法題中Easy級別的第140題（順位題號是605）。假設你有一個花壇，其中一些地塊是種植的，有些則不是。 然而，花不能種植在相鄰的地塊，因為它們會爭奪水，兩者都會死亡。給定一個花壇（表示為包含0和1的陣列，其中0表示空，可以種植，1表示不為空，不能種植）和數字n，如果可以在其中種植n個新花而不違反無鄰花規則則返回true。例如：
輸入：花壇=[1,0,0,0,1]，n = 1
輸出：true
輸入：花壇=[1,0,0,0,1]，n = 2
輸出：false
注意：
-
輸入陣列不會違反無鄰花規則。
-
輸入陣列大小在[1,20000]範圍內。
-
n是一個非負整數，不會超過輸入陣列大小。
本次解題使用的開發工具是eclipse，jdk使用的版本是1.8，環境是win7 64位系統，使用Java語言編寫和測試。
02 第一種解法
要想種花，即當前地塊是可以種植的（值為0），需要滿足兩個條件：當前地塊的前一個地塊是可以種植的（值也為0），當前地塊的後一個地塊也是可以種植的（值也為0），把滿足這些條件的地塊數加起來，判斷與給定的花數量的大小，來返回true或者false。在這裡，我們使用三個布林值來判斷，第二個布林值與第三個布林值表示了剛剛分析的兩種情況，第一個布林值是初始條件，只有三者都滿足，那麼我們就可以在當前位置種花。
public boolean canPlaceFlowers(int[] flowerbed, int n) {
int i = 0;
int len = flowerbed.length;
while (i < len) {
boolean b = flowerbed[i] == 0;
boolean b2 = i == 0 || flowerbed[i-1] == 0;
boolean b3 = i == len-1 || flowerbed[i+1] == 0;
if (b && b2 && b3) {
flowerbed[i] = 1;
n--;
}
i++;
}
return n <= 0;
}
03 第二種解法
思路與上面第一種解法類似，只是換個形式實現。我們獲取當前位置的前一個位置的值與後一個位置的值，判斷他們是不是都等於0，如果等於，n就自減1，如果n小於等於0，表示需要種的花已經種完了，直接返回true。但是，此種寫法我們需要判斷一下n是否等於0，n等於0表示沒有種花，直接返回true。
public boolean canPlaceFlowers2(int[] flowerbed, int n) {
if (n == 0) {
return true;
}
int i = 0;
int len = flowerbed.length;
while (i < len) {
if (flowerbed[i] == 0) {
int next = i == len-1 ? 0 : flowerbed[i+1];
int pre = i == 0 ? 0 : flowerbed[i-1];
if (next == 0 && pre == 0) {
flowerbed[i] = 1;
n--;
}
if (n <= 0) {
return true;
}
}
i++;
}
return false;
}
04 小結
演算法專題目前已日更超過四個月 ，演算法題文章140 +篇，公眾號對話方塊回覆【資料結構與演算法 】、【演算法 】、【資料結構 】中的任一關鍵詞，獲取系列文章合集。
以上就是全部內容，如果大家有什麼好的解法思路、建議或者其他問題，可以下方留言交流，點贊、留言、轉發就是對我最大的回報和支援！