今天你刷题了嘛 605 ～插花？

基本信息

• 题号：605
• 题厂：谷歌
• 难度系数：低

数组 flowerbed代表插花位：1 代表该位已种花，0 代表还没种……

要求只能隔空插花，即不能出现 2+ 连续 1

问：改数组能插入 n 朵花嘛？能——返回 true，不能——返回 false

例如：flowerbed = [1,0,0,0,1], n = 1

返回 true，插在第三个槽位即可满足条件，即：[1,0,1,0,1]

解题思路

• 本题的解题思路是显而易见的——遍历数组，当卡位可插花时，counter 加 1；
• 判断当前卡位能否插花：元素 flowerbed[i] 为 0 且前后卡位 flowerbed[i + 1] flowerbed[i - 1] 均为 0
• 一旦 counter 大于等于 n，即可返回 true

class Solution:
    def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:
        count = 0
        
        for i in range(len(flowerbed)):
            if count >= n:
                return True
            
            if flowerbed[i] == 0:
                # 判断前卡位是否可以插花
                left = (i == 0) or (flowerbed[i - 1] == 0)
                # 判断后卡位能否插花
                right = (i == len(flowerbed) - 1) or (flowerbed[i + 1] == 0)
                
                if left and right:
                    flowerbed[i] = 1
                    count += 1
                    
        return count >= n

Constraints

• 1 <= flowerbed.length <= 2 * 104
• flowerbed[i] is 0 or 1.
• There are no two adjacent flowers in flowerbed.
• 0 <= n <= flowerbed.length

考试时可以向考官询问已知的花床数组会不会自带 2+ 连续 1

需不需哟判断当 n 大于花床数组长度的案例

Big O

• Time：O（n）
• Space：O（1）

测试

• 花床 0 开头，0 结尾案例
• 花床 1 开头，1 结尾案例
• 花床为单数，偶数时……

总结

• 本题代码以及解体思路属于简单级别。但要在想出解题思路后迅速写出无 bug 漏洞的代码，需要思维严密
• 本题作为基础题，勤加练习方能熟能生巧😭