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.
自己代码:
\(n\leq3\) 时, 情况都列出来;
\(n>3\) 时, 那点若为首点 i == 0 && A[i] == 0 && A[1] == 0,则count+1,且将A[0]=1, 否则那点若为尾点i == (n - 1) && A[i] == 0 && A[i - 1] == 0,则count+1,且将A[n-1]=1,否则的话,这个点既不是首也不是尾巴,就可以放心的看这个点和前一个点以及后一个点是否全为0,A[i] == 0 && A[i - 1] == 0 && A[i + 1] == 0,若是则count+1,且A[i]=1.
我这个逻辑稍显复杂,较难控制.
编写这个用了多久怎么能和你说呢!
我用了足足1分钟! ^^
\(O(n)\) time, \(O(1)\) extra space.
bool canPlaceFlowers(vector<int>& A, int k) {
int i, count = 0, n = A.size();
if (n <= 3) {
if (n == 1 && A[0] == 0) count = 1;
if (n == 1 && A[0] == 1) count = 0;
if (n == 2 && A[0] == 0 && A[1] == 0) count = 1;
if ((n == 2 && A[0] == 1 && A[1] == 0) || (n == 2 && A[0] == 0 && A[1] == 1)) count = 0;
if (n == 3 && A[0] == 0 && A[1] == 0 && A[2] == 0) count = 2;
if (n == 3 && A[0] == 0 && A[1] == 0 && A[2] == 1) count = 1;
if (n == 3 && A[0] == 1 && A[1] == 0 && A[2] == 0) count = 1;
return k <= count ? true : false;
}
else {
for (i = 0; i < n; i++) {
if (i == 0 && A[i] == 0 && A[1] == 0) {A[i] = 1; count++;}
else if (i == (n - 1) && A[i] == 0 && A[i - 1] == 0) {A[i] = 1; count++;}
else if (A[i] == 0 && A[i - 1] == 0 && A[i + 1] == 0) {A[i] = 1; count++;}
}
return k <= count ? true : false;
}
}
再看看人家的,妈的过分吧,是人脑袋吗,还有点正常人的思维吗,想杀人!
\(O(n)\) time, \(O(1)\) extra space.
bool canPlaceFlowers(vector<int>& A, int n) {
A.insert(A.begin(), 0);
A.push_back(0);
for (int i = 1; i < A.size() - 1; ++i){
if (A[i - 1] + A[i] + A[i + 1] == 0){
--n;
++i;
}
}
return n <= 0;
}