python-leetcode-种花问题

605. 种花问题 - 力扣（LeetCode）

使用 贪婪算法 来解决这个问题，思绪如下：

• 遍历 flowerbed 数组，找到值为 0 的地块。
  
• 检查该地块的前后是否为空（即 flowerbed[i-1] 和 flowerbed[i+1] 是否都为 0 或者 i 在边界）。
  
• 假如可以种花，就将 flowerbed 设为 1 并淘汰 n 的数目。
  
• 假如 n 变成 0，提前返回 True，表示可以种下全部的花。
  
• 遍历竣事后，假如仍然 n > 0，返回 False。
  

代码实现如下：

1. from typing import List
3. def canPlaceFlowers(flowerbed: List[int], n: int) -> bool:
4.     length = len(flowerbed)
5.    
6.     for i in range(length):
7.         if flowerbed[i] == 0:
8.             prev_empty = (i == 0 or flowerbed[i - 1] == 0)  # 边界或前一个为空
9.             next_empty = (i == length - 1 or flowerbed[i + 1] == 0)  # 边界或后一个为空
10.             
11.             if prev_empty and next_empty:  # 满足种植条件
12.                 flowerbed[i] = 1
13.                 n -= 1
14.                 if n == 0:
15.                     return True  # 直接返回
17.     return n <= 0  # 如果 n 还大于 0，说明不能全部种下
19. # 测试
20. print(canPlaceFlowers([1, 0, 0, 0, 1], 1))  # True
21. print(canPlaceFlowers([1, 0, 0, 0, 1], 2))  # False
22. print(canPlaceFlowers([0, 0, 1, 0, 0], 1))  # True

复制代码

复杂度分析：

• 时间复杂度：O(n)，只须要遍历一遍数组。
  
• 空间复杂度：O(1)，仅使用了常数额外空间。
  

如许可以高效判断可否种入 n 朵花，且尽可能早返回效果。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。