LeetCode 605. Can Place Flowers 题解题目描述假设有一个很长的花坛一部分地块种植了花另一部分却没有。可是花不能种植在相邻的地块上它们会争夺水源两者都会死去。给你一个整数数组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解题思路方法贪心算法思路贪心算法的核心思想是在每一步选择中都采取在当前状态下最好或最优的选择从而希望导致结果是全局最好或最优的。对于这个问题我们可以遍历花坛数组。对于每个位置如果当前位置是空的0并且前一个位置如果存在也是空的或者是数组的开头并且后一个位置如果存在也是空的或者是数组的结尾那么就可以在这个位置种花。种完花后将当前位置标记为 1并跳过下一个位置因为不能相邻。当种植的花的数量达到 n 时返回 true。遍历结束后如果种植的花的数量大于等于 n返回 true否则返回 false。复杂度分析时间复杂度O(n)其中 n 是花坛的长度。只需要遍历一次花坛数组。空间复杂度O(1)只需要常数级的额外空间。代码实现方法贪心算法class Solution: def canPlaceFlowers(self, flowerbed: List[int], n: int) - bool: # 初始化种植的花的数量 count 0 # 遍历花坛数组 i 0 while i len(flowerbed): # 检查当前位置是否可以种花 if flowerbed[i] 0 and \ (i 0 or flowerbed[i-1] 0) and \ (i len(flowerbed)-1 or flowerbed[i1] 0): # 种花 flowerbed[i] 1 # 增加种植的花的数量 count 1 # 跳过下一个位置 i 1 # 移动到下一个位置 i 1 # 检查是否种植了足够的花 return count n测试用例测试用例 1输入flowerbed [1,0,0,0,1], n 1输出true测试用例 2输入flowerbed [1,0,0,0,1], n 2输出false总结本题是贪心算法的经典问题主要考察对贪心算法思想的理解和应用。通过遍历花坛数组我们可以高效地判断是否可以种植指定数量的花。贪心算法的核心思想是在每一步选择中都采取在当前状态下最好或最优的选择从而希望导致结果是全局最好或最优的。这种方法不仅适用于种花问题还可以应用于许多其他需要局部最优选择的问题。掌握贪心算法的原理对于理解算法设计思想非常重要。