605. Can Place Flowers (使用 C 語言解題)

605. Can Place Flowers

Solved

Easy

Topics

Companies

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 true if n new flowers can be planted in the flowerbed without violating the no-adjacent-flowers rule and false otherwise.

 

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] is 0 or 1.
• There are no two adjacent flowers in flowerbed.
• 0 <= n <= flowerbed.length

 

google 翻譯：

你有一個長長的花壇，其中有些地塊種植了，有些則沒有。 
但是，相鄰的地塊不能種植花卉。

給定一個包含0 和1 的整數數組花壇，其中0 表示空，1 表示非空，以及一個整數n，
如果可以在花壇中種植n 朵新花而不違反無相鄰花規則，則返回true，否則回傳false。

想法一：

用 for 跑一次陣列，檢查上一塊和下一塊地，兩塊地要同時等於0，
就可以種植，並把種植數 +1，再與 n 比較並回傳

寫法一：

bool canPlaceFlowers(int* flowerbed, int flowerbedSize, int n) {
    int i, k = 0;
    for(i=0; i<flowerbedSize; i++) {
        if(flowerbed[i] == 0) {
            if((i == 0 || flowerbed[i-1] == 0) && // 開頭或上一塊地是0
               (i != (flowerbedSize-1) || flowerbed[i+1] == 0)) { // 非結尾或下一塊地是0
                k++; // 可種植數 +1
                i++; // 跳過目前這塊地
            }
        }
    }
    return (k >= n);
}

結果一：

前面的三個 case 對了，但是後面隱藏的case 8 錯了...

想法二：

是我筆誤了，把要判斷的結尾，多加了個 “！” ，修正後再跑一次...

寫法二：

bool canPlaceFlowers(int* flowerbed, int flowerbedSize, int n) {
    int i, k = 0;
    for(i=0; i<flowerbedSize; i++) {
        if(flowerbed[i] == 0) {
            if((i == 0 || flowerbed[i-1] == 0) && // 開頭或上一塊地是0
               (i == (flowerbedSize-1) || flowerbed[i+1] == 0)) { // 結尾或下一塊地是0
                k++; // 可種植數 +1
                i++; // 跳過目前這塊地
            }
        }
    }
    return (k >= n);
}

結果二：

這速度也太低了吧，我腦袋是有什麼洞嗎...

想法三：

研究了一下大神的寫法，感覺我這寫法還行啊，再跑一次看看好了...

寫法三：

bool canPlaceFlowers(int* flowerbed, int flowerbedSize, int n) {
    int i, k = 0;
    for(i=0; i<flowerbedSize; i++) {
        if(flowerbed[i] == 0) {
            if((i == 0 || flowerbed[i-1] == 0) && (i == (flowerbedSize-1) || flowerbed[i+1] == 0)) {
                k++;
                i++;
            }
        }
    }
    return (k >= n);
}

結果三：

這是發生了什麼事，我到底看到了什麼，這差距也太大了吧。不過既然結果還不錯，就這樣吧...