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

提示：

  • 1 <= flowerbed.length <= 2 * 10^4
  • flowerbed[i] 为 0 或 1
  • flowerbed 中不存在相邻的两朵花
  • 0 <= n <= flowerbed.length

解题思路

这是一道典型的贪心算法题。我们需要找到所有可以种花的位置，并统计最多能种多少朵花。

核心思路：

  1. 从左到右遍历花坛，对于每个位置判断是否可以种花
  2. 一个位置可以种花的条件是：当前位置为空（0），且左右两边都没有花（或者是边界）
  3. 如果可以种花，就立即种上（贪心策略），这样可以为后续留出更多空间
  4. 统计总共能种的花朵数，看是否 >= n

判断条件详解：

  • 当前位置必须是 0
  • 左边没有花：i == 0 || flowerbed[i-1] == 0
  • 右边没有花：i == flowerbed.length-1 || flowerbed[i+1] == 0

贪心正确性： 由于相邻位置不能种花，我们应该尽早种花来占用位置，这样不会影响后续的最优选择。

时间复杂度：O(n)，只需要一次遍历 空间复杂度：O(1)，只使用常数额外空间

代码实现

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

class Solution:
    def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:
        count = 0
        for i in range(len(flowerbed)):
            if (flowerbed[i] == 0 and 
                (i == 0 or flowerbed[i-1] == 0) and 
                (i == len(flowerbed)-1 or flowerbed[i+1] == 0)):
                flowerbed[i] = 1
                count += 1
                if count >= n:
                    return True
        return count >= n

public class Solution {
    public bool CanPlaceFlowers(int[] flowerbed, int n) {
        int count = 0;
        for (int i = 0; i < flowerbed.Length; i++) {
            if (flowerbed[i] == 0 && 
                (i == 0 || flowerbed[i-1] == 0) && 
                (i == flowerbed.Length-1 || flowerbed[i+1] == 0)) {
                flowerbed[i] = 1;
                count++;
                if (count >= n) return true;
            }
        }
        return count >= n;
    }
}

var canPlaceFlowers = function(flowerbed, n) {
    let count = 0;
    for (let i = 0; i < flowerbed.length; i++) {
        if (flowerbed[i]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度分析
时间复杂度O(m)，其中 m 是花坛长度，需要遍历一次数组
空间复杂度O(1)，只使用常数个额外变量

相关题目