leetcode 605. Can Place Flowers 间隔种花 + 补齐元素然后遍历

喜欢ヅ旅行 2022-06-02 20:57 149阅读 0赞

Suppose you have a long flowerbed in which some of the plots are planted and some are not. However, flowers cannot be planted in adjacent plots - they would compete for water and both would die.

Given a flowerbed (represented as an array containing 0 and 1, where 0 means empty and 1 means not empty), and a number n, return if n new flowers can be planted in it without violating the no-adjacent-flowers rule.

Example 1:  
Input: flowerbed = \[1,0,0,0,1\], n = 1  
Output: True  
Example 2:  
Input: flowerbed = \[1,0,0,0,1\], n = 2  
Output: False  
Note:  
The input array won’t violate no-adjacent-flowers rule.  
The input array size is in the range of \[1, 20000\].  
n is a non-negative integer which won’t exceed the input array size.

这道题给了我们一个01数组，其中1表示已经放了花，0表示可以放花的位置，但是有个限制条件是不能有相邻的花。那么我们来看如果是一些简单的例子，如果有3个连续的零，000，能放几盆花呢，其实是要取决约左右的位置的，如果是10001，那么只能放1盆，如果左右是边界的花，那么就能放两盆，101，所以如果我们想通过计算连续0的个数，然后直接算出能放花的个数，就必须要对边界进行处理，处理方法是如果首位置是0，那么前面再加上个0，如果末位置是0，就在最后面再加上个0。这样处理之后我们就默认连续0的左右两边都是1了，这样如果有k个连续0，那么就可以通过(k-1)/2来快速计算出能放的花的数量

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <numeric>
    #include <cmath>
    #include <regex>
    
    using namespace std;
    
    class Solution 
    {
    public:
        bool canPlaceFlowers(vector<int>& flowerbed, int n) 
        {
            if (flowerbed.size() <= 0)
                return false;
            if (flowerbed[0] == 0)
                flowerbed.insert(flowerbed.begin(),0);
            if (flowerbed[flowerbed.size() - 1] == 0)
                flowerbed.push_back(0);
    
            int sum = 0, count = 0;
            for (int i = 0; i < flowerbed.size(); i++)
            {
                if (flowerbed[i] == 1)
                {
                    sum += (count - 1) / 2;
                    count = 0;
                }
                else
                    count++;
            }
            if(count>0)
                sum += (count - 1) / 2;
            return sum >= n;
        }
    };