605. 种花问题

一、题目描述

假设有一个很长的花坛，一部分地块种植了花，另一部分却没有。

可是，花不能种植在相邻的地块上，它们会争夺水源，两者都会死去。

给你一个整数数组flowerbed 表示花坛，由若干 0 和 1 组成，其中 0 表示没种植花，1 表示种植了花。

另有一个数n ，能否在不打破种植规则的情况下种入n朵花？能则返回 true ，不能则返回 false。

二、解题思路

遍历数组，除了2端的元素以外，只要有连续的3个为0的地方，就可以在中间的0那里种花。

三、复杂度分析

• 时间 O(n)
• 空间 O(1)

四、参考代码

/**
 * 种花问题
 * @param flowerbed 数组
 * @param n 数量
 * @return true/false
 */
private boolean canPlaceFlowers(int[] flowerbed, int n) {
    if (n <= 0) {
        return true;
    }
    if (flowerbed.length < 2 * n - 1) {
        return false;
    }
    int k = n;
    for (int i = 0; k > 0 && i < flowerbed.length; i++) {
        // 当前不为空
        if (flowerbed[i] != 0) {
            continue;
        }
        // 左边不为空
        if (i - 1 >= 0 && flowerbed[i - 1] != 0) {
            continue;
        }
        // 右边不为空
        if (i + 1 < flowerbed.length && flowerbed[i + 1] != 0) {
            continue;
        }
        // 两边都为空，可以种花
        k--;
        i++;
    }
    return k <= 0;
}