【LeetCode】605.种花问题

1 问题

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

给你一个整数数组 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

2 解题思路

2.1 贪心算法

假设花坛任一位置i，有以下几种情况需要考虑：

• 该位置flowerbed[i]==1，已经种了花，跳过；
• i既不在开头位置0，也不在最后位置，且前一位已经种了花，即flowerbed[i-1]==1，这里不能种了，跳过；
• i不在最后位置，但其后已经种了，即flowerbed[i+1]==1，不能种，跳过；
• 其他情况，能种，i++，n--，若此时n<=0，花都种完了，返回true.

见代码常规算法。

2.2 改进

对于任一位置i，当`flowerbed[i]==0’时，才有资格讨论是否能种，且以下几种情况均可种花：

• i是最后一个，则必须flowerbed[i - 1] == 0才可种；
• i是第一个，则flowerbed[i + 1] == 0才可种；
• i是在中间，则其前后都必须可种才能种，即满足flowerbed[i + 1] == 0 && flowerbed[i - 1] == 0。

3 代码

class Solution {
    //改进算法
    public boolean canPlaceFlowers(int[] flowerbed, int n) {
        int len = flowerbed.length;
        int cnt = 0;

        for (int i = 0; i < len; i++) {
            if (flowerbed[i] == 0) {
                //1.i是最后一个，则必须flowerbed[i - 1] == 0才可种；
                //2.i是第一个，则flowerbed[i + 1] == 0才可种；
                //3.i是在中间，则其前后都必须可种才能种。
                if ((i == len - 1 || flowerbed[i + 1] == 0) && (i == 0 || flowerbed[i - 1] == 0)) {
                    flowerbed[i] = 1;
                    cnt++;
                }
            }
        }
        return cnt >= n;
    }

    //常规贪心算法
    public boolean canPlaceFlowers(int[] flowerbed, int n) {
        for (int i = 0; i < flowerbed.length; i++) {
            if (n <= 0) {        // 如果已经种够花了，可以提前返回true
                return true;
            }
            if (flowerbed[i] == 1) {     // 如果已经种过花了，则不能再种了
                continue;
            }
            if (i > 0 && flowerbed[i - 1] == 1) {        // 如果上一个格子已经种过花了，则当前这格不能种花
                continue;
            }
            if (i < flowerbed.length - 1 && flowerbed[i + 1] == 1) {   // 如果下一个格子已经种过花了，则当前这格不能种花
                continue;
            }
            // 可以种花了，并且记录次数
            flowerbed[i] = 1;
            n--;
        }
        return n <= 0;
    }
}