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

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

思路：

只要保证所插得花两侧都没有花即可，也就是花的两侧都为0，也就是说至少有3个0才能插一枝花，比较特殊的地方是边界的位置，那么将边界的位置考虑成特殊情况，假设边界处（-1和length处）摆着一个空花盆，那么就可以连续的进行判断了，还需要注意的是int除法是默认四舍五入的，但是半个花盆是无法种花的，所以出现算出半枝花的情况就将其减去。

代码如下：

class Solution {public boolean canPlaceFlowers(int[] flowerbed, int n) {float maxFlower = 0;int maxZero = 0;int length = flowerbed.length;for (int i = 0; i < length; i++) {if (flowerbed[i] == 0) {if (i == 0) {maxZero += 1;}maxZero += 1;} else {if (i == length - 1 && flowerbed[i] == 0) {maxZero += 1;}maxFlower += (maxZero - 1) / 2;if (maxFlower != (int) maxFlower) {maxFlower -= 0.5;}maxZero = 0;}}if (maxZero != 0) {maxZero += 1;}maxFlower += (maxZero - 1) / 2;if (maxFlower != (int) maxFlower) {maxFlower -= 0.5;}return maxFlower >= n;}
}

方法二：

每次都判断当前位置的前一个位置、当前位置、当前位置后一个位置是否为0，如果满足条件就将当前位置置为1，再向后遍历，边界点单独判断。

public boolean canPlaceFlowers(int[] flowerbed, int n) {int len = flowerbed.length;int cnt = 0;for (int i = 0; i < len && cnt < n; i++) {if (flowerbed[i] == 1) {continue;}int pre = i == 0 ? 0 : flowerbed[i - 1];int next = i == len - 1 ? 0 : flowerbed[i + 1];if (pre == 0 && next == 0) {cnt++;flowerbed[i] = 1;}}return cnt >= n;
}