基本信息

  • 题号：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 漏洞的代码，需要思维严密
  • 本题作为基础题，勤加练习方能熟能生巧😭