Leetcode - 605 - Can Place Flowers
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:
题解：
注意前面一段和后面一段。
class Solution {
public:
bool canPlaceFlowers(vector<int>& flowerbed, int n) {
int cnt, ans = 0, st = -1, ed = flowerbed.size()-1;
for(int i=0; i<=ed; ++i){
if(flowerbed[i] == 1){
cnt = i - 1 - st;
if(cnt > 0){
ans += cnt/2;
}
st = i + 1;
}
}
if(flowerbed[ed] != 1){
cnt = ed + 1 - st;
if(cnt > 0){
ans += cnt/2;
}
}
return (ans >= n);
}
};
Leetcode - 605 - Can Place Flowers
原文：http://www.cnblogs.com/zhang-yd/p/7082582.html