605 种花问题（双指针）

梦里梦外; 2022-09-01 09:08 188阅读 0赞

**1. 问题描述：**

假设有一个很长的花坛，一部分地块种植了花，另一部分却没有。可是，花不能种植在相邻的地块上，它们会争夺水源，两者都会死去。给你一个整数数组 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  
来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/can-place-flowers

**2. 思路分析：**

分析题目可以发现能够填1的数目完全取决于连续的0的数目，所以我们需要计算出连续一段0的数目，这里可以分为三种情况，若连续的0的数目为k，当连续的一段0是内部的0，也即当前连续的0的左右端点都是1可以发现能够填1的数目为(k - 1) / 2，当连续的一段0包含了左边界那么能够填1的数目为k / 2，当连续的一段0包含了左右边界那么能够填1的数目为(k + 1) / 2，计算连续1的数目可以使用**双指针算法**，固定起点对应的指针i，指针j往后移动，当指针j停止之后那么\[i，j)一段就是连续的0的数目。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NDQ1MTY1_size_16_color_FFFFFF_t_70][]

**3. 代码如下：**

from typing import List
    
    
    class Solution:
        # 分情况讨论即可
        def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:
            if n == 0: return True
            i = 0
            res = 0
            while i < len(flowerbed):
                if flowerbed[i] == 1:
                    i += 1
                    continue
                # 双指针算法
                j = i
                while j < len(flowerbed) and flowerbed[j] == 0: j += 1
                # 判断属于哪一种情况
                # 一开始的时候假定为内部得了连续0
                k = j - i - 1
                # 如果是左边界
                if i == 0: k += 1
                # 如果是右边界
                if j == len(flowerbed): k += 1
                res += k // 2
                if res >= n: return True
                i = j
            return False

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NDQ1MTY1_size_16_color_FFFFFF_t_70]: /images/20220829/95b27f8fb9394a399c104ef0c81f78db.png