难度: 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 * 104flowerbed[i] 为 0 或 1flowerbed 中不存在相邻的两朵花0 <= n <= flowerbed.length运行时间: 22 ms
内存: 16.3 MB
class Solution:
def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:
count, m, prev = 0, len(flowerbed), -1
for i in range(m):
if flowerbed[i] == 1:
if prev < 0:
count += i // 2
else:
count += (i - prev - 2) // 2
if count >= n:
return True
prev = i
if prev < 0:
count += (m + 1) // 2
else:
count += (m - prev - 1) // 2
return count >= n
这个题解采用了一次遍历的贪心策略。通过遍历花坛，统计当前位置左右两侧连续0的个数，如果个数大于等于2，就可以种下一朵花。同时用一个变量 prev 记录上一朵已种花的位置，用于计算当前位置与上一朵花之间的间隔。最后再根据最后一朵花的位置，计算剩余的空位数量，更新可种花的总数 count。如果 count 大于等于 n，说明可以种下 n 朵花，返回 True，否则返回 False。
时间复杂度: O(m)
空间复杂度: O(1)
class Solution:
def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:
count, m, prev = 0, len(flowerbed), -1
for i in range(m):
if flowerbed[i] == 1:
if prev < 0:
count += i // 2 # 计算左侧可种花的数量
else:
count += (i - prev - 2) // 2 # 计算上一朵花到当前花之间可种花的数量
if count >= n: # 如果可种花数量已经满足要求，提前返回
return True
prev = i # 更新上一朵已种花的位置
if prev < 0:
count += (m + 1) // 2 # 如果没有种花，计算整个花坛可种花的数量
else:
count += (m - prev - 1) // 2 # 计算最后一朵花右侧可种花的数量
return count >= n # 判断可种花的总数是否满足要求
对于花坛两端的处理，题解采用以下策略：如果整个花坛的开头没有花（即`prev`初始化为-1），则可以将整个开头连续的0视为一个特殊区域，其可种花的数量由`(i // 2)`计算，其中`i`为第一个遇到的1的位置，或者如果没有1则为花坛的长度。对于花坛的末尾，如果最后一个位置是0，则从最后一个1之后的位置到花坛末尾的连续0也是一个特殊区域，计算其可种花的数量通过`(m - prev - 1) // 2`实现，其中`m`是花坛的长度，`prev`是最后一个1的位置。这样的处理确保了花坛两端的0都被充分利用。
初始化`prev`为-1是为了处理花坛开头是0的情况。这样的设定意味着在花坛的第一个元素之前假想一个位置-1处有一个1，这使得第一个0到第一个1之间的距离正确计算。如果花坛的第一个位置是0并且之后连续有多个0，那么这些0在没有任何前面的1阻碍的情况下，可以按照`(i // 2)`的方法计算可种花的数量。因此，这种初始化方式是合理且有助于边界情况的处理。
对于花坛中间部分的0，准确计算左右两侧连续0的个数依赖于记录上一朵花的位置`prev`。当遇到一个1时，`prev`会更新为当前1的位置。计算任何两个1之间的0的数量（即`i - prev - 2`，其中`i`是当前1的位置），通过这个数量除以2得到这段区域内可以种植的花的数量。这种方法确保了只有当两个1之间至少有一个间隔（即2个0）时，才会种植一朵花，因此可以正确地处理中间0的情况。
题解中的代码实际上在满足种花数量要求时会提前终止遍历并返回True，这是通过`if count >= n`这个条件检查实现的。这种提前终止遍历的策略是高效的，因为一旦我们已经种下了所需的花的数量，就没有必要继续检查剩余的部分。这样做可以节省时间，使算法效率更高。