题目描述

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

给你一个整数数组 flowerbed 表示花坛，由若干 0 和 1 组成，其中 0 表示没种植花，1 表示种植了花。另有一个数 n ，能否在不打破种植规则的情况下种入 n 朵花？能则返回 true ，不能则返回 false。

样例

输入：flowerbed = [1,0,0,0,1], n = 1
输出：true
输入：flowerbed = [1,0,0,0,1], n = 2
输出：false

思路

首先我们看有多少个零在一起，然后不难发现n个零在一起可以插入（n-1）/2个
但是这道题要考虑的就是开始和结束的情况比较特殊
所以重新一个数组，可以在开始和最后分别加一个零，这样就统一了
但是空间就会用的比较大，所以采取把数值加一就可以了

时间复杂度 o(n)

C++ 代码

  bool canPlaceFlowers(vector<int>& flowerbed, int n) {
         int size = flowerbed.size();
         int res=0;
         int start=1;

         for(int i = 0;i<size; i++){
             if(flowerbed[i]==0){
                     start ++;
             }
             else {
                res+=(start-1)/2;
                 start =0;
             }
         }
         res+=start/2;
         return res>=n;
    }