[数据结构与算法]【leetcode】种花问题 c++

题目描述：

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

给你一个整数数组 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 * 104
flowerbed[i] 为 0 或 1
flowerbed 中不存在相邻的两朵花
0 <= n <= flowerbed.length

代码：

class Solution {
public:
    bool canPlaceFlowers(vector<int>& flowerbed, int n) {
        int l=flowerbed.size();
        int s=0;
        for(int i=0;i<l;i++){
            if(flowerbed[i]==0){
                if(i==0){
                    if(l==1)s++;//考虑数组没有i+1的情况，否则越界
                    else if(flowerbed[i+1]==0){
                        flowerbed[i]=1;s++;
                    }
                }
                else if(i==l-1){
                    if(flowerbed[i-1]==0){
                        flowerbed[i]=1;s++;
                    }
                }
                else if(flowerbed[i-1]==0){
                    if(l<3)s++; //考虑数组没有i+1的情况，否则越界
                    else if(flowerbed[i+1]==0){
                        flowerbed[i]=1;s++;
                    }
                }
            }
        }
        cout<<"s:"<<s<<endl;
        if(n<=s)return true;
        return false;
    }
};

插花的规则：该位置之前没有花，且其左右均没有花。对两个花中间的空位插花，贪心法插花，一旦有可以插花的位置就进行插花直到没有位置可以插花。

只需遍历数组依次插花即可。s记录可以插花的数量

若位置=0才可以考虑插花：
1.若该0位于数组开头，没有左相邻，只需要考虑右边有无花，若右边没有花，直接插花（改变数组该位置的值为1），s+1

2.若该0位于数组结尾，没有右相临，只需要考虑左边有无花，若左边没有花，直接插花（改变数组该位置的值为1），s+1

3.若该0不在数组的开头结尾，考虑其左右有无花，若都没有花，则插花（改变数组该位置的值为1），s+1

最后比较最多可以插花的数量s和输入的插花数n，若n<=s，则return true