Can Place Flowers

发表于 | 分类于

Can Place Flowers

题目描述：

给定一个数组，数组中1表示该位置栽花；0则代表没有。则要求返回该数组是否能种n株花，在花的栽种间隔为1的情况下。

例子：

具体描述看LeetCode605

解题思路：

本题中的主要难点有两个(1)0的个数和栽种花的数量的关系(2)如何处理好数组头部和尾部的情况和全0的情况。代码中先设置的c=1是为了处理开头为0的情况；在循环的外部是为了处理尾部结尾为0的情况。因为在开头为0和结尾为0的情况，0的个数和栽花数量的关系较为特殊。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    bool canPlaceFlowers(vector<int>& flowerbed, int n) {
        int c = 1;
        int m = 0;
        for (auto i : flowerbed){
            if (i == 0){
                c++;
            }else{
                m += (c - 1) / 2;
                c = 0;
            }
        }
        c++;
        m += (c - 1) / 2;
        return m >= n;
    }
};