605. 种花问题 也是很不错的题目
假设你有一个很长的花坛，一部分地块种植了花，另一部分却没有。可是，花卉不能种植在相邻的地块上，它们会争夺水源，两者都会死去。
给定一个花坛（表示为一个数组包含0和1，其中0表示没种植花，1表示种植了花），和一个数 n 。能否在不打破种植规则的情况下种入 n 朵花？能则返回True，不能则返回False。
示例 1:
输入: flowerbed = [1,0,0,0,1], n = 1
输出: True
示例 2:
输入: flowerbed = [1,0,0,0,1], n = 2
输出: False
注意:
- 数组内已种好的花不会违反种植规则。
- 输入的数组长度范围为 [1, 20000]。
- n 是非负整数，且不会超过输入数组的大小。
第一版，改了好一会，速度较慢
执行用时 :24 ms, 在所有 cpp 提交中击败了40.79%的用户
内存消耗 :10.4 MB, 在所有 cpp 提交中击败了80.32%的用户
boolcanPlaceFlowers(vector<int>&flowerbed, intn) {
unordered_map<int, int>res;// 0/1,count
res[0] =0;
res[1] =0;
size_ti=0;
while (i<flowerbed.size() &&flowerbed[i] ==0 ) {
res[0] ++;
i++;
}
if (i==flowerbed.size()) {//全是 0
return (res[0] +1) /2>=n;
}
intplantFlower= res[0] /2;//遇到1了，此时flowerbed[i] = 1
res[1] =1;
res[0] =0;
i++;
for (; i<flowerbed.size();++i ) {
res[flowerbed[i]] +=1;
if (res[1] ==2) {
//countZero = res[0];
plantFlower+= (res[0] -1) /2;
res[1] =1;
res[0] =0;
}
}
if (res[1] ==2) {
//countZero = res[0];
plantFlower+= (res[0] -1) /2;
}
elseif (res[1] ==1) {
//countZero = res[0];
plantFlower+=res[0] /2;
}
returnplantFlower>=n;
}
第二版，别的想法，防御性种花，这思路可以的....
防御式编程思想：在 flowerbed 数组两端各增加一个 0， 这样处理的好处在于不用考虑边界条件，任意位置处只要连续出现三个 0 就可以栽上一棵花。
执行用时 :24 ms, 在所有 cpp 提交中击败了40.79%的用户
内存消耗 :10.2 MB, 在所有 cpp 提交中击败了93.09%的用户
boolcanPlaceFlowers(vector<int>&flowerbed, intn) {
intlen=1, ans=0; //认为左边界提供1个0
for (auto&i : flowerbed) {
if (i) {//为1,遇到1了
ans+= (len-1) /2; //len个0可以种这么多花
len=0;
}
else {//为0
++len;
}
}
ans+= (len) /2; //处理0尾，认为右边界提供一个0
returnans>=n;
}
