网站建设毕业设计总体规划,wordpress 转发,上海建设工程安全质量监督总站网站,信誉好的中山网站建设链接 假设有一个很长的花坛#xff0c;一部分地块种植了花#xff0c;另一部分却没有。可是#xff0c;花不能种植在相邻的地块上#xff0c;它们会争夺水源#xff0c;两者都会死去。给你一个整数数组 flowerbed 表示花坛#xff0c;由若干 0 和 1 组成#xff0c;其中…链接 假设有一个很长的花坛一部分地块种植了花另一部分却没有。可是花不能种植在相邻的地块上它们会争夺水源两者都会死去。给你一个整数数组 flowerbed 表示花坛由若干 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 flowerbed.length 2 * 104 flowerbed[i] 为 0 或 1 flowerbed 中不存在相邻的两朵花 0 n flowerbed.length
1.暴力求解
从数组的首个元素开始判断是否种花判断当前位置的前后位置是否种花要注意数组越界问题和首地址和尾地址位置问题。
bool canPlaceFlowers(int* flowerbed, int flowerbedSize, int n){int i0;if(n0){return true;}if(flowerbedSize1){if(flowerbed[i]0){flowerbed[i]1;n--;i;}}while(iflowerbedSize){if(i0){if(flowerbed[0]0flowerbed[1]0){flowerbed[i]1;n--;i2;}else{i2;}}else if(iflowerbedSize-1){if(flowerbed[i]0flowerbed[i-1]0){flowerbed[i]1;n--;}else{i;}} else if(flowerbed[i]1){i2;}else if(flowerbed[i]0i0flowerbed[i-1]0flowerbed[i1]0i1flowerbedSize){flowerbed[i]1;n--;i2;}else if(flowerbed[i1]1i1flowerbedSize){i3;}else{i2;}}if(n0){return true;}else{return false;}
}2.暴力优化
可以优化下知道在什么情况下可以种花当不处于临界位置的时候如果当前位置的值为0前面一个位置和后面一个位置的值都为0就可以种花当第一个位置和第二个位置的值或者最后一个位置的值和前一个位置的值为0的时候也可以种花。要注意数组越界的问题。
bool canPlaceFlowers(int* flowerbed, int flowerbedSize, int n){ for(int i0;iflowerbedSize;i){// printf(i%d\n,i);if(flowerbed[i]0(i0||flowerbed[i-1]0)(((i1flowerbedSize)(flowerbed[i1]0))||iflowerbedSize-1)){flowerbed[i]1;n--;}}return n0;
}
0求解法
长度为1且值为0直接种植如果元素不全为0统计0的个数如果连续三个1就可以种一个如果全为0如果长度为2只能种一个否则就是0的个数除以2加1
bool canPlaceFlowers(int* flowerbed, int flowerbedSize, int n){ int count0,i,sum0,flage0;if(flowerbedSize1){if(flowerbed[0]0){return true;}}if(flowerbed[0]0){count;}for(i0;iflowerbedSize;i){if(flowerbed[i]0){count;}else if(count2){flage1;sum(count-1)/2;count0;}else if(count2){count0;flage1;}}if(count2){if(flage0){if(count2){sum-1;}else{sumcount/2;}}else{if(count2){sum1;}else{if(count%20){sumcount/2;}else{sum(count-1)/2;}}}}if(sumn){return true;}else{return false;}
}
