How do I know when to stop planting flowers in the 'Can Place Flowers' problem?

You can stop planting flowers once n reaches 0, indicating that all required flowers have been placed.

What is the time complexity of the 'Can Place Flowers' problem?

The time complexity is O(n), where n is the length of the flowerbed array, because each plot is checked once.

Why is it important to handle boundary conditions in this problem?

Boundary conditions are crucial because the first and last plots may not have two adjacent plots to check, and overlooking this can lead to errors.

What is the greedy approach used in the 'Can Place Flowers' problem?

The greedy approach places flowers in each empty plot (0), ensuring no adjacent flowers are placed, and stops once the required number of flowers is planted.

How can GhostInterview help me solve problems like 'Can Place Flowers'?

GhostInterview offers a detailed, step-by-step guide to solving problems with a focus on greedy algorithms, boundary handling, and interview-ready solutions.

#605

Easy

auto_awesome贪心·invariant

LeetCode 题解工作台

种花问题

假设有一个很长的花坛，一部分地块种植了花，另一部分却没有。可是，花不能种植在相邻的地块上，它们会争夺水源，两者都会死去。给你一个整数数组 flowerbed 表示花坛，由若干 0 和 1 组成，其中 0 表示没种植花， 1 表示种植了花。另有一个数 n ，能否在不打破种植规则的情况下种入 n 朵花…

数组贪心

题目描述

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

给你一个整数数组 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⁴
flowerbed[i] 为 0 或 1
flowerbed 中不存在相邻的两朵花
0 <= n <= flowerbed.length

lightbulb

解题思路

方法一：贪心

我们直接遍历数组 $flowerbed$ ，对于每个位置 $i$ ，如果 $flowerbed[i]=0$ ，并且其左右相邻位置都为 $0$ ，则我们可以在该位置种花，否则不能。最后我们统计可以种下的花的数量，如果其不小于 $n$ ，则返回 $true$ ，否则返回 $false$ 。

时间复杂度 $O(n)$ ，其中 $n$ 是数组 $flowerbed$ 的长度。我们只需要遍历数组一次。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

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

speed

复杂度分析

指标	值
时间	O(n)
空间	O(1)

psychology

面试官常问的追问

外企场景

question_mark
Candidate demonstrates understanding of greedy algorithms.
question_mark
Candidate is able to explain the importance of early termination and boundary conditions.
question_mark
Candidate can handle edge cases involving small or large flowerbed arrays.

warning

常见陷阱

外企场景

error
Failing to account for boundary conditions (first and last plot).
error
Incorrectly attempting to plant flowers in adjacent plots, violating the rule.
error
Not terminating early when enough flowers are planted.

swap_horiz

进阶变体

外企场景

arrow_right_alt
What if we need to plant more than one flower in a single pass?
arrow_right_alt
What if the flowerbed array is larger or smaller than typical inputs?
arrow_right_alt
How would the approach change if the flowerbed could have more complex rules, such as spacing requirements between flowers?

help

常见问题

外企场景

继续练习

#611 有效三角形的个数 #621 任务调度器 #624 数组列表中的最大距离