605. 种花问题 Easy

假设有一个很长的花坛，一部分地块种植了花，另一部分却没有。可是，花不能种植在相邻的地块上，它们会争夺水源，两者都会死去。

给你一个整数数组 flowerbed 表示花坛，由若干 0 和 1 组成，其中 0 表示没种植花，1 表示种植了花。另有一个数 n ，能否在不打破种植规则的情况下种入 n 朵花？能则返回 true ，不能则返回 false 。

示例 1:
输入：flowerbed = [1,0,0,0,1], n = 1
输出：true

示例 2:
输入：flowerbed = [1,0,0,0,1], n = 2
输出：false

解题思路

输入： 一个花坛数组 flowerbed，整数 n

输出： 是否可以在不相邻的情况下种下 n 朵花

这是一个 数组遍历 问题。

我们遍历花坛，每次判断当前位置能否种花：

• 当前格子为 0
• 左边为空或越界
• 右边为空或越界

• 如果满足条件，就在此处种花（标记为 1），并减少需要种的数量 n。
• 在遍历过程中，如果 n <= 0，说明已经成功种下足够的花，直接返回 true。
• 遍历结束仍未满足，则返回 false。

代码实现

python

class Solution:
    def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:
        # 遍历花坛，检查每个位置是否可以种花
        for i, flower in enumerate(flowerbed):
            # 如果当前位置是空的，且左边和右边也是空的，才可以种花
            if flower == 0 and (i == 0 or flowerbed[i - 1] == 0) and (i == len(flowerbed) - 1 or flowerbed[i + 1] == 0):
                # 在当前位置种花
                flowerbed[i] = 1
                # 需要种的花数减少 1
                n -= 1
            # 如果已经种了足够的花，则直接返回 True
            if n <= 0:
                return True

        # 如果遍历完后仍然不能种下足够的花，则返回 False
        return False

javascript

var canPlaceFlowers = function(flowerbed, n) {
    let count = n;                 // 还需要种的花数
    const len = flowerbed.length;  // 花坛长度

    for (let i = 0; i < len; i++) {
        const f = flowerbed[i];    // 当前格子的状态（0 或 1）

        // 如果当前位置是空地，并且前后都没有花
        if (
            f === 0 &&                                // 当前为空
            (i === 0 || flowerbed[i - 1] === 0) &&    // 左边为空或越界（第一格）
            (i === len - 1 || flowerbed[i + 1] === 0) // 右边为空或越界（最后一格）
        ) {
            flowerbed[i] = 1; // 在当前位置种花
            count--;          // 需要种的数量减一
        }

        // 如果已经种够了，提前返回 true
        if (count <= 0) return true;
    }

    // 遍历结束后仍然没种够，返回 false
    return false;
};

复杂度分析

时间复杂度：O(n)

空间复杂度：O(n)

链接

605 国际版

605 中文版