Day 24：605. Can Place Flowers

今日题目

题目连结：605. Can Place Flowers
题目主题：Array, Greedy

昨天介绍了 Greedy 的基本概念，今天会在练习一题以 Greedy 当主题的题目，建议还没看过 Greedy 可以先回 Day 23：1974. Minimum Time to Type Word Using Special Typewriter 看看简单说说 Greedy。

题目解说

建议可以看看LeetCode原本的题目说明，这边是用我的方式说明题目，参考就好。

题目会给你一个 flowerbed 花圃，我们要在这里面种植，这个 flowerbed 中 0 代表没有种植、1 代表有种植，另外会给一个 n 代表要种植的数量，目的是确认 flowerbed 中还能不能再种植 n 朵花，若可以回传 True，不行则回 False。

约束：

• 1 <= flowerbed.length <= 2 * 10的4次方。
• flowerbed[i] 不是 0 就是 1。
• flowerbed 中花跟花之间不会靠在一起，中间一定会有一个空。
• 0 <= n <= flowerbed.length。

范例1

输入: flowerbed = [1,0,0,0,1], n = 1
输出: true
解说: flowerbed中间还可以再插一朵花，n 刚好是 1，因此这个范例回 true。

范例2

输入: flowerbed = [1,0,0,0,1], n = 2
输出: false
解说: flowerbed中间只能再插一朵花，因为花不能靠在一起，n 还有两朵花，因此这个范例回 false。

建议到这边先停下来，尝试自己解解看，若没有想法可再继续走下去。

解题的想像

文字描述

1. 写一个递回方法，传入目标的种花数量、花圃、目前位置，最终回传是否能把花全部种完，会检查以下项目：
   • 若种花数量已经到 0 代表成功把花都种完了。
   • 若目前的位置已经超出花圃范围，代表失败，没有把花种完。
   • 每一步会有三种可能性：
     • 若现在位置有花 前进两步。
     • 若现在位置+1有花 前进三步。
     • 若现在位置没花 种1朵花 前进两步。
2. 呼叫这个递回方法，最後回传是否能成功把花种完的结果。

图解过程

范例：flowerbed = [0, 0, 1, 0, 0, 1, 0, 0], n = 2

上图这个例子中，可以先看 step1 ~ step2，从 step1 开始走，当目前位置没有种花时，会将花种下去，并且往前两步，也因目前点种下花，以条件来说下一个点必为空，所以可以看到 step2 的 count 已经 -1 了，并且前进了两步。

step3 因为当下的位置已经有花了，100 中 1 的旁边不能种花，也是直接往前走两步。step4 比较特别，虽然当下的位置没有花，但是因为下一个位置有花不能在这边种花，所以直接前进了三步，原因是 0100 中 1 的旁边都不能种花了，所以可以确定直接往前三步没问题。

step4 前进了三步走到最後的位置後，因为当下的位置是 0 ，所以在这边把最後一朵花种下去，最後 step5 的 count 已经是 0 了，最後这个范例是成功可以把花种完的。

若因为没想法而走到这边，建议看完想像以後再给自己一次机会试一次。

程序码撰写

class Solution:
    def planting(self, count, flowerbed, index = 0):
        # 若把花全部种完回 True
        if count == 0: return True
        # 若花圃都走过一次还没种完回 False
        if index >= len(flowerbed): return False
        
        # 若现在位置有花 前进两步
        if flowerbed[index] == 1:
            return self.planting(count, flowerbed, index+2)
        # 若现在位置+1有花 前进三步
        if (index+1 < len(flowerbed)) and flowerbed[index+1] == 1:
            return self.planting(count, flowerbed, index+3)
        # 若现在位置没花 种1朵花 前进两步
        if flowerbed[index] == 0:
            flowerbed[index] = 1
            return self.planting(count - 1, flowerbed, index+2)
    
    def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:
        return self.planting(n, flowerbed)

希望您今天能了解到...

1. 605. Can Place Flowers的解题方法

若内容有什麽问题或建议欢迎一起交流：）
感谢您今天愿意花时间看完这篇文章~~~~

Next：53. Maximum Subarray