【数据结构与算法】【LeetCode】【贪心算法】605.种花问题

贪心策略、

题目

假设有一个很长的花坛，一部分地块种植了花，另一部分却没有。可是，花不能种植在相邻的地块上，它们会争夺水源，两者都会死去。

给你一个整数数组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 * 10^4$
• $flowerbed[i] 为 0 或 1$
• $flowerbed 中不存在相邻的两朵花$
• $0 <= n <= flowerbed.length$

题解

方法一：跳格子解法

题目要求是否能在不打破规则的情况下插入n朵花，与直接计算不同，采用“跳格子”的解法只需遍历不到一遍数组，处理以下两种不同的情况即可：

• 【1】当遍历到index遇到1时，说明这个位置有花，那必然从index+2的位置才有可能种花，因此当碰到1时直接跳过下一格
• 【2】当遍历到index遇到0时，由于每次碰到1都是跳两格，因此前一格必定是0，此时只需要判断下一格是不是1即可得出index这一格能不能种花，如果能种则令n减一，然后这个位置就按照遇到1时处理，即跳两格；如果index的后一格是1，说明这个位置不能种花且之后两格也不可能种花（参照【1】），直接跳过3格。

当n减为0时，说明可以种入n朵花，则可以直接退出遍历返回true；如果遍历结束n没有减到0，说明最多种入的花的数量小于n，则返回false。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution:
    def canPlaceFlowers(self, flowerbed, n) -> bool:
        
        i = 0
        
        while i<len(flowerbed) and n>0:
            if flowerbed[i]==1:
                i = i+2
            else:
                if i==len(flowerbed)-1 or flowerbed[i+1]==0:
                    n=n-1
                    i=i+2
                else:
                    i=i+3
        return n<=0

1
2
3
4
5

a=Solution()
flowerbed=[1,0,0,0,1]
n=2
result=a.canPlaceFlowers(flowerbed,n)
print(result)

False

方法二：贪心

从左向右遍历花坛，在可以种花的地方就种一朵，能种就种（因为在任一种花时候，不种都不会得到更优解），就是一种贪心的思想

这里可以种花的条件是：

• 自己为空
• 左边为空 或者 自己是最左
• 右边为空 或者 自己是最右

最后判断n朵花是否有剩余，为了效率起见，可以在种花的过程中做判断，一旦花被种完就返回true

1
2
3
4
5
6
7
8
9

class Solution:
    def canPlaceFlowers(self, flowerbed, n) -> bool:
        i=0
        while i<len(flowerbed) and n>0:
            if flowerbed[i]==0 and (i==0 or flowerbed[i-1]==0 ) and (i==len(flowerbed)-1 or flowerbed[i+1]==0):
                n=n-1
                flowerbed[i]=1
            i=i+1
        return n<=0

1
2
3
4
5

a=Solution()
flowerbed=[1,0,0,0,0,1]
n=2
result=a.canPlaceFlowers(flowerbed,n)
print(result)

False