种花问题

一、题目描述

假设你有一个很长的花坛，一部分地块种植了花，另一部分却没有。可是，花卉不能种植在相邻的地块上，它们会争夺水源，两者都会死去。

给定一个花坛（表示为一个数组包含0和1，其中0表示没种植花，1表示种植了花），和一个数 n 。能否在不打破种植规则的情况下种入 n 朵花？能则返回True，不能则返回False。
（力扣（LeetCode））

示例 1:
输入: flowerbed = [1,0,0,0,1], n = 1
输出: True

示例 2:
输入: flowerbed = [1,0,0,0,1], n = 2
输出: False
注意:

数组内已种好的花不会违反种植规则。
输入的数组长度范围为 [1, 20000]。
n 是非负整数，且不会超过输入数组的大小。

二、解决方法

1. 暴力法（三个三个数一起考虑）

class Solution {
    public boolean canPlaceFlowers(int[] flowerbed, int n) {
    	//处理长度小于3的情况
       if(flowerbed.length==1){
            return flowerbed[0]==0?(n<=1):(n==0);
        }
        if(flowerbed.length==2){
            return flowerbed[0]==0&&flowerbed[1]==0?n<=1:n==0;
        }
        int count=0;
        //左端需特殊考虑
        if(flowerbed[0]==0&&flowerbed[1]==0){
            flowerbed[0]=1;
            count++;
        }
        for (int i = 1; i < flowerbed.length-1; i++) {
        	//将数组遍历三个三个数一起考虑
            if(flowerbed[i-1]==0&&flowerbed[i]==0&&flowerbed[i+1]==0){
                flowerbed[i]=1;
                count++;
            }
        }
        //右端特殊考虑
        if(flowerbed[flowerbed.length-2]==0&&flowerbed[flowerbed.length-1]==0){
            count++;
        }
        return count>=n;
    }
}

2. 暴力法(两个两个数一起考虑，左端特殊情况就可以避免了，评论区大佬方法)

class Solution {
     public boolean canPlaceFlowers(int[] flowerbed, int n) {
        for (int i = 0; i < flowerbed.length; i += 2) {
            if (flowerbed[i] == 0) {
            	//如果当前是最后一个数或者是当前数的下一个数是0
            	//说明当前可以种花，将n--（要种n朵，如果减到负值就说明不可以）
                if (i == flowerbed.length - 1 || flowerbed[i + 1] == 0) {
                    n--;
                } else {
                	//否则再跳一个数(本来就跳两个数，下一个数是1肯定也要跳过)
                    i++;
                }
            }
        }
        return n <= 0;
    }
}

3. 贪心算法（官方题解）

class Solution {
    public boolean canPlaceFlowers(int[] flowerbed, int n) {
        int count = 0;
        int m = flowerbed.length;
        //记录前一个为1的数组下标
        int prev = -1;
        for (int i = 0; i < m; i++) {
        	//如果当前为1进行判断
            if (flowerbed[i] == 1) {
                if (prev < 0) {
                	//当前下标前面的数没有1，count+=i / 2
                	//比如:[0,0,0,1] ,i=3,count+=1
                    count += i / 2;
                } else {
	                //当前下标前面的数有1，count += (i - prev - 2) / 2;
	                //就是获取两个1之间最多放1的数
	                //比如：[1,0,0,0,1],pre=0,i=4,count+=1
                    count += (i - prev - 2) / 2;
                }
                prev = i;
            }
        }
        if (prev < 0) {
        	//特殊情况：数组都为0
            count += (m + 1) / 2;
        } else {
        	//正常情况：最后边界有可能没统计进去
        	//如：[1,0,0,0,1,0,0](没统计最后一个数)
        	//此时：count=1,pre=4,m=7。count+=1
            count += (m - prev - 1) / 2;
        }
        return count >= n;
    }
}