[每日 LeetCode] 605. Can Place Flowers

Description:

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 numbern, return ifnnew 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:

1. The input array won't violate no-adjacent-flowers rule.
2. The input array size is in the range of [1, 20000].
3. nis a non-negative integer which won't exceed the input array size.

思路：首先处理首位置和末位置的情况(默认首位的前面和末尾的后一位为 0)。然后遍历数组，如果某个位置为 0，就看其前面一个和后面一个位置的值，如果 pre 和 next 均为 0，那么说明当前位置可以放花，n 自减 1，并且当前位置的后一个位置一定不能放置，i++，最后看 n 是否小于等于 0。

C++ 代码

class Solution {
public:
    bool canPlaceFlowers(vector<int>& flowerbed, int n) {
        flowerbed.insert(flowerbed.begin(),0);
        flowerbed.push_back(0);
        int i=1;
        while (i<flowerbed.size()-1)
        {
            if (flowerbed[i]==0 && flowerbed[i-1]==0 &&flowerbed[i+1]==0)
            {
                n--;
                //如果当前这个放置了，那么后面一个不用判断了，因为一定不能放置。
                i++;
            }
            i++;    
        }      
        return n<=0;
    }
};
​

运行时间：20ms
运行内存：12M