605. Can Place Flowers
题目描述
假设有一个很长的花坛，一部分地块种植了花，另一部分却没有。可是，花不能种植在相邻的地块上，它们会争夺水源，两者都会死去。
给你一个整数数组 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
题解
定位：贪心问题 求解花坛的最大种花数量
子问题：求解每个0区间长度 根据区间长度分别求解子区间可以种植的花数
数学归纳：
-
对于中间的0区间：
-
1~2个0：可种0朵；
-
3~4个：可种1朵；
-
5~6个：可种2朵；
-
…
-
count个：可种 (count-1)/2 朵
-
-
对于两头的0区间，由于左边、右边分别没有1的限制，可种花朵数稍有不同
+ 可以在数组最左边、数组最右边分别补1个0，意味着花坛左边、右边没有花。
代码
class Solution {
public boolean canPlaceFlowers(int[] flowerbed, int n) {
// 贪心问题 求解花坛的最大种花数量// 根据花坛中0的个数来计算// 数学归纳：// 1-2 0// 3-4 1// 5-6 2// count = (count-1)/2// 优化if(flowerbed.length==0 || flowerbed == null ){
return n==0;}// 统计可以种花数目int num = 0;// 花坛总长度// 计算0的个数 默认为1可以处理边界问题 补00操作int countofzero = 1;int length = flowerbed.length;for(int i=0;i<length;i++){
if(flowerbed[i] == 0){
countofzero++;}else{
//遇到1了 计算该区间种花的个数num += (countofzero-1)/2;countofzero = 0 ;}}// 最后补0countofzero++;num += (countofzero-1)/2;return num>=n;}
}