Leetcode No.605( Can Place Flowers) 心得

ChingYuanYang
Aug 25, 2017 · 2 min read

題目:

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:

  1. The input array won’t violate no-adjacent-flowers rule.
  2. The input array size is in the range of [1, 20000].
  3. 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;
}
};

)
Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade