Leetcode No.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: TrueExample 2:
Input: flowerbed = [1,0,0,0,1], n = 2
Output: FalseNote:
- 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.
想法:
這題很簡單,就是判斷式去符合題目要求。為了怕超過運算時間,所以就想了一些加速方法,因為相當於是花要間隔放,所以假設 array size 6,那 n 最多只能 3,用這個判斷進可能提早結束。其實我覺得這題在 leetcode 有點太看得起他了。
class Solution {
public:
bool canPlaceFlowers(vector<int>& flowerbed, int n) {
int size = flowerbed.size();
int maxN = (size + 1) / 2;
int AllowN = 0;
bool Previous = false;
for (int i = 0; i < size — 1; i++) {
if (Previous == false && flowerbed[i] == 0 && flowerbed[i+1] == 0) {
AllowN++;
Previous = true;
} else if (flowerbed[i] == 1) {
Previous = true;
} else if (flowerbed[i] == 0 && Previous == true) {
Previous = false;
}
if (AllowN >= n)
return true;
int remain = size — i — 1 — Previous;
if ((remain + 1)/2 + AllowN < n)
return false;
}
if (flowerbed[size — 1] == 0 && Previous == false)
AllowN++;
if (AllowN >= n)
return true;
else
return false;
}
};
網路上的解法:
差不多就我的概念,不過他們有優話一些判斷式,還滿有趣的,讓程式變簡潔,但是沒有加速。
class Solution {
public:
bool canPlaceFlowers(vector<int>& flowerbed, int n) {
flowerbed.insert(flowerbed.begin(),0);
flowerbed.push_back(0);
for(int i = 1; i < flowerbed.size()-1; ++i)
{
if(flowerbed[i-1] + flowerbed[i] + flowerbed[i+1] == 0)
{
--n;
++i;
}
}
return n <=0;
}
};class Solution {
public:
bool canPlaceFlowers(vector<int>& bed, int n) {
for (int i = 0; i < bed.size(); i++) {
if (!bed[i] && (i == 0 || !bed[i - 1]) && (i == bed.size() - 1 || !bed[i + 1])) {
bed[i] = 1;
n--;
}
}
return n <= 0;
}
};
