605-种花问题

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

给你一个整数数组  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
通过次数135,615提交次数412,417

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/can-place-flowers
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

错误方法

看完题目后，我首先想到的是假如一个全0的数组，那么最多可以种植多少株花呢？ 比如[0,0,0],显然最多可以种植2株，即[1,0,1] [0,0,0,0,0],最多可以种植3株，即[1,0,1,0,1] 所以只要先计算数组最多可以种植的花朵数量，然后减去当前已经种植花朵数量，差值如果小于给定的n，就说明可以种下了。 分分钟写完。

 public boolean canPlaceFlowers(int[] flowerbed, int n) {
 if (n == 0) {
            return true;
        }
        int oneCount = Arrays.stream(flowerbed).filter(k -> k == 1).sum();
        int size = flowerbed.length;
        int total = (size + 1) / 2;
        return n + oneCount <= total;
    }

写完提交发现没有ac,115/124,然后仔细想了想，发现思路是错误的。 因为给定的数组并不一定是按照最优的方法种植的花朵，比如给定数组[0,1,0],那么继续可以种植的花朵实际是0，所以上面思路的问题是没有考虑当前的数组里1的位置，只是按照最乐观的情况进行计算。

模拟算法

老老实实的走模拟的思路，遍历数组，然后在可以种植的位置种上，最后与参数进行比较。 种植的时候注意首尾两个元素需要特殊判断。 这种模拟的方法是符合贪心的思路的，即遍历时候是能种上咱就种上，尽量的多。

public boolean canPlaceFlowers(int[] flowerbed, int n) {
        if (n == 0) {
            return true;
        }
        int size = flowerbed.length;
        if (size == 1) { //先把只包含一个元素这种情况特殊处理下
            return n==1 && flowerbed[0] == 0;
        }
        for (int i = 0; i < flowerbed.length; i++) {
            if(flowerbed[i] == 1){ //如果当前位置已经种植了花，跳过
                continue;
            }
            if (i == 0) { 
                if (flowerbed[i + 1] == 0) { //如果是第0个位置，看看第1个位置是不是0，是0的话就可以种上
                    n--;
                    flowerbed[i] = 1;
                }
            } else if (i == flowerbed.length - 1) {
                if (flowerbed[i - 1] == 0) { //如果是最后一个位置，看下之前的是不是0，如果是0则可以种上
                    n--;
                    flowerbed[i] = 1;
                }
            } else {
                if (flowerbed[i - 1] == 0 && flowerbed[i + 1] == 0) { //数组中间的位置，需要判断之前和之后的是否有花。
                    n--;
                    flowerbed[i] = 1;
                }
            }

        }
        return n <= 0;
    }

复杂度

一趟遍历，时间复杂度是O(n),空间复杂度为O(1)

其他

该方法会修改数组。