LeetCode 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.
今天第一次做Leetcode的weekly contest，AC了三题，最后一题看起来好繁琐，没A。 第一题，简单贪心即可，从第0个位置开始，检查每个位置的前后是否为1，如果不为1，说明该位置可以种花，填上1，最后统计新填上的1的个数和n的关系。 代码如下： [cpp] class Solution { public: bool canPlaceFlowers(vector<int>& flowerbed, int n) { int m = flowerbed.size(); for (int i = 0; i < m; ++i) { if (flowerbed[i] == 0) { if (i – 1 >= 0 && flowerbed[i – 1] == 1)continue; if (i + 1 < m&&flowerbed[i + 1] == 1)continue; flowerbed[i] = 1; –n; } } return n <= 0; } }; [/cpp] 本代码提交AC，用时26MS。]]>
贪心的代码如下：
[cpp]
class Solution {
public:
int wiggleMaxLength(vector<int>& nums) {
int n = nums.size();
if (n < 2)return n;
int ans = 1, i = 0, j = 1;
bool up = false;
while (j < n && nums[j] == nums[i])++j;
if (nums[j] > nums[i])up = true;
else up = false;
while (j < n) {
if (nums[j] > nums[i] && up) {
++ans;
up = false;
while (j + 1 < n&&nums[j + 1] >= nums[j])++j;
}
else if (nums[j] < nums[i] && !up) {
++ans;
up = true;
while (j + 1 < n&&nums[j + 1] <= nums[j])++j;
}
i = j++;
}
return ans;
}
};
[/cpp]
本代码提交AC，用时3MS。
还可以用动态规划的方法，假设up[i]表示第i个元素处于抖动序列的最后一个位置，且是上升的趋势时，前[0,i]的抖动子序列的最大长度。类似的，down[i]表示第i个元素处于抖动序列的最后一个位置，且是下降趋势时，前[0,i]的抖动子序列的最大长度。
则对于第i个元素，可以枚举所有i前面的元素j跳到i，如果nums[i]>nums[j]，则i处于抖动序列的上升末尾，则从j到i构成的抖动序列中，j是处于下降趋势的，所以有up[i]=max(up[i],down[j]+1)。类似的，如果nums[i]<nums[j]，则有down[i]=max(down[i],up[j]+1)。最后返回1+max(up[n-1],down[n-1])。
代码如下：
[cpp]
class Solution {
public:
int wiggleMaxLength(vector<int>& nums) {
int n = nums.size();
if (n < 2)return n;
vector<int> up(n, 0), down(n, 0);
for (int i = 1; i < n; ++i) {
for (int j = 0; j < i; ++j) {
if (nums[i] > nums[j])up[i] = max(up[i], down[j] + 1);
else if (nums[i] < nums[j])down[i] = max(down[i], up[j] + 1);
}
}
return 1 + max(up[n – 1], down[n – 1]);
}
};
[/cpp]
本代码提交AC，用时6MS。
可以对上述代码优化。j无需枚举所有i前面的元素，而是i直接根据和前一个元素i-1的大小关系进行更新。如果nums[i]>nums[i-1]，则i处于上升末端，所以i-1必须处于下降末端，有up[i]=down[i-1]+1，down[i]不变，即down[i]=down[i-1]。如果nums[i]<nums[i-1]，则i处于下降末端，所以i-1必须处于上升末端，有down[i]=up[i-1]+1，up[i]不变，即up[i]=up[i-1]。如果nums[i]==nums[i-1]，则up[i]和down[i]都不变，分别等于up[i-1]和down[i-1]。
为什么这里可以不用枚举所有i前面的元素了呢，因为上述三种情况中，只更新了该更新的，不能更新的情况都等于前一个元素的结果了，比如第一种情况更新了up[i]，则down[i]保持了down[i-1]的值，所以后续如果要用到down[i-1]的值，也可以直接用down[i]的值了。
代码如下：
[cpp]
class Solution {
public:
int wiggleMaxLength(vector<int>& nums) {
int n = nums.size();
if (n < 2)return n;
vector<int> up(n, 0), down(n, 0);
up[0] = down[0] = 1;
for (int i = 1; i < n; ++i) {
if (nums[i] > nums[i – 1]) {
up[i] = down[i – 1] + 1;
down[i] = down[i – 1];
}
else if (nums[i] < nums[i – 1]) {
down[i] = up[i – 1] + 1;
up[i] = up[i – 1];
}
else {
up[i] = up[i – 1];
down[i] = down[i – 1];
}
}
return max(up[n – 1], down[n – 1]);
}
};
[/cpp]
本代码提交AC，用时3MS。
还可以对上述代码进行空间的优化，因为up[i]和down[i]都只用到了前一个结果up[i-1]和down[i-1]，所以只需保留前一个结果就行，不需要两个数组。代码如下：
[cpp]
class Solution {
public:
int wiggleMaxLength(vector<int>& nums) {
int n = nums.size();
if (n < 2)return n;
int up = 1, down = 1;
for (int i = 1; i < n; ++i) {
if (nums[i] > nums[i – 1]) {
up = down + 1;
}
else if (nums[i] < nums[i – 1]) {
down = up + 1;
}
}
return max(up, down);
}
};
[/cpp]
本代码提交AC，用时0MS，是效率最好的一种解法了。
参考：