日野弥生：勉強しよう
LeetCode 605 - 种花问题
发表于2025年04月09日
一开始想利用双指针的方式进行解决，通过头尾指针之间的0的个数来判断最多能种几朵花。确实，0的个数和能插入花的个数有一定的数学关系： 能插入花的个数 = （尾指针 - 头指针 - 1） // 2
但是，面临的困难：边界情况很难处理。
使用贪心理念
class Solution:
def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:
length = len(flowerbed)
i = 0
while i < length:
if flowerbed[i] == 0:
# 如果左边是空，或者没有左边时
empty_left = (i == 0 or flowerbed[i - 1] == 0)
# 如果右边是空，或者没有右边时
empty_right = (i == length - 1 or flowerbed[i + 1] == 0)
if empty_left and empty_right:
flowerbed[i] = 1
n -= 1
if n == 0:
# 剪枝优化，如果已经插完了不需要继续遍历下去
return True
i += 2 # 剪枝优化，插入花后，下一个位置必然不能插花，跳过下一个位置
continue
# 正常迭代
i += 1
return n <= 0