605. 種花問題

假設(shè)有一個很長的花壇，一部分地塊種植了花，另一部分卻沒有。可是，花不能種植在相鄰的地塊上，它們會爭奪水源，兩者都會死去。

給你一個整數(shù)數(shù)組 flowerbed 表示花壇，由若干 0 和 1 組成，其中 0 表示沒種植花，1 表示種植了花。另有一個數(shù) n，能否在不打破種植規(guī)則的情況下種入 n朵花？能則返回 true ，不能則返回 false。

示例 1：

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

示例 2：

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

提示：

• 1 <= flowerbed.length <= 2 * 10<sup>4</sup>
• flowerbed[i] 為 0 或 1
• flowerbed 中不存在相鄰的兩朵花
• 0 <= n <= flowerbed.length

題解
題目要求是否能在不打破規(guī)則的情況下插入n朵花，與直接計算不同，采用“跳格子”的解法只需遍歷不到一遍數(shù)組，處理以下兩種不同的情況即可：

【1】當(dāng)遍歷到index遇到1時，說明這個位置有花，那必然從index+2的位置才有可能種花，因此當(dāng)碰到1時直接跳過下一格。
【2】當(dāng)遍歷到index遇到0時，由于每次碰到1都是跳兩格，因此前一格必定是0，此時只需要判斷下一格是不是1即可得出index這一格能不能種花，如果能種則令n減一，然后這個位置就按照遇到1時處理，即跳兩格；如果index的后一格是1，說明這個位置不能種花且之后兩格也不可能種花（參照【1】），直接跳過3格。

當(dāng)n減為0時，說明可以種入n朵花，則可以直接退出遍歷返回true；如果遍歷結(jié)束n沒有減到0，說明最多種入的花的數(shù)量小于n，則返回false。

作者：hatsune-miku-k

class Solution {
public:
    bool canPlaceFlowers(vector<int>& flowerbed, int n) {
        for (int i = 0, len = flowerbed.size(); i < len && n > 0;) {
            if (flowerbed[i] == 1) {
                i += 2;
            } else {
                if(i == len - 1 || flowerbed[i + 1] == 0) {
                    n--;
                    i += 2;
                } else {
                    i += 3;
                }
            }
        }
        return n <= 0;
    } 
};