华为 OD 训练营 · 题解精讲
LC605. 种花问题
LC605. 种花问题 视频地址：https://uha.xet.tech/s/2vNFsv
题目描述
假设有一个很长的花坛，一部分地块种植了花，另一部分却没有。可是，花不能种植在相邻的地块上，它们会争夺水源，两者都会死去。 给你一个整数数组 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 * 104 flowerbed[i] 为 0 或 1 flowerbed 中不存在相邻的两朵花 0 <= n <= flowerbed.length
题目解析
解题思路
题目要求在已有花坛中再种入 n 朵花，且不能相邻。参考代码采用贪心算法，从左到右遍历数组，只要当前位置可以种花就立刻种下，并跳过后续不可能种花的位置。这样能保证种下尽可能多的花，从而判断能否满足 n 朵。
用到的数据结构仅为数组本身，无需额外空间。关键思想是：利用已知的种植规则，跳过那些确定无法种花的位置，减少不必要的检查。
关键步骤
遍历指针 i 从 0 开始，当 i < len(flowerbed) 且 n > 0 时循环：
1. 如果 `flowerbed[i] == 1`：当前位置已有花，则 i+1 位置不能种花，直接 i += 2 跳过。 2. 如果 `flowerbed[i] == 0` 且是最后一个位置，或 `flowerbed[i+1] == 0`：说明当前位置可以种花，n -= 1，然后 i += 2（因为种花后下一个位置不能种）。 3. 否则：当前位置为 0 但 flowerbed[i+1] == 1，则 i 和 i+1 都不能种花，且 i+2 因相邻 i+1 的花也不能种，直接 i += 3。
循环结束后，若 n <= 0 则返回 true，否则 false。
示意图（以 [1,0,0,0,1] 为例，i 移动过程）：
i=0: 1 → i+=2
i=2: 0, 后一位0 → 种花, i+=2
i=4: 1 → i+=2, 循环结束, n=0 → true复杂度分析
- 时间复杂度：O(n)，其中 n 为数组长度。每个元素最多被访问一次，且指针每次至少跳 2 步，实际遍历次数 ≤ n。
- 空间复杂度：O(1)，仅使用常数个变量。
参考代码
class Solution:
def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:
# 遍历数组，在遍历过程中，采取贪心的思路，并不需要【每个位置】都去查看是否可以种花
# 1、当前位置已经种花，那么后一个位置明显不能种花，可以跳过去
# 2、当前位置没有种花，需要考虑后面一个位置是否种花
i = 0
while i < len(flowerbed) and n > 0 :
# 1、当前位置已经种花，那么后一个位置明显不能种花，可以跳过去
# 所以让 i 执行加 2 操作，跳过了加 1 后的那个位置
if flowerbed[i] == 1 :
# 让 i 执行加 2 操作
i += 2
# 2、说明当前位置没有种花 flowerbed[i] == 0
# 3、如果这个位置是数组的最后一个位置，说明后一个位置不存在，没有限制，说明 flowerbed[i] 可以种花
# 4、如果这个位置【不是】数组的最后一个位置，那么只有后一个位置【没有种花】，才有资格在 flowerbed[i] 位置种花
elif i == len(flowerbed) - 1 or flowerbed[i + 1] == 0 :
# 以上两种条件都可以在 flowerbed[i] 位置种花
# 成功之后，所需目标减 1
n -= 1
# 在 flowerbed[i] 位置种花之后，i + 1 位置不需要去考虑了，因为它明显不能种花，可以跳过去
# 让 i 执行加 2 操作
i += 2
# 5、说明当前位置没有种花 flowerbed[i] == 0
# 6、但是后一个位置已经种花了，那么当前位置无法采取种花操作
else:
# i + 1 位置已经种花，不用再去访问一遍
# i + 2 位置考虑到 i + 1 位置已经种花，所以也无法种花，不用再去访问
# 让 i 执行加 3 操作
i += 3
# 最后查看是否用完了 n
return n <= 0
四、时空复杂度
时间复杂度：O(n)。
空间复杂度：O(1)。