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 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.
Solutions
My solution
class Solution {
public:
bool canPlaceFlowers(vector<int>& flowerbed, int n) {
int size = flowerbed.size();
int i = 0;
while(i < size && flowerbed[i] == 0) ++i;
n -= i == size ? (i + 1) / 2 : i / 2;
while(i < size){
int j = i + 1;
while(j < size && flowerbed[j] == 0) ++j;
n -= j == size ? (j - i - 1) / 2 : (j - i - 2) / 2;
if(n <= 0) return true;
i = j;
}
return n <= 0;
}
};
Optimal solution
Credit: https://leetcode.com/problems/can-place-flowers/discuss/103883/Java-Very-easy-solution
class Solution {
public:
bool canPlaceFlowers(vector<int>& flowerbed, int n) {
int zeros = 1; // the essential part: setting # of zeros to 1
for(int num : flowerbed){
if(num == 0){
++zeros;
}else{
n -= (zeros - 1) / 2;
if(n <= 0) return true;
zeros = 0;
}
}
n -= zeros / 2;
return n <= 0;
}
};
Last updated