0605.花园种花问题(简易)

问题描述

你有一段很长的花坛，其中一些位置已经种了花，而另一些则为空。根据规则，不允许在相邻的位置种植花朵。

给定一个整数数组flowerbed，其中0表示空位，1表示已有花，以及一个整数n，请判断是否可以在不违反不相邻种植规则的前提下，在花坛中种下n朵新花。

示例 1:

输入: flowerbed = [1,0,0,0,1], n = 1
输出: true

示例 2:

输入: flowerbed = [1,0,0,0,1], n = 2
输出: false

约束条件:

• 1 <= flowerbed.length <= 2 * 10^4
• flowerbed[i]为0或1。
• 花坛中不存在两朵相邻的花。
• 0 <= n <= flowerbed.length

问题解析

本题的核心在于如何有效地检查并利用花坛中的空位来种植新花，同时确保遵守不相邻的规则。一种直观的方法是采用贪心算法，即从左至右遍历花坛，一旦发现符合种植条件的位置（即该位置及其左右均为空），立即在此处种下一朵花，并减少需要种植的花的数量。如果最终能将所有计划中的花都种下，则返回真值；反之，则返回假值。

编程实现

Java 实现

public class Solution {
    public boolean canPlaceFlowers(int[] flowerbed, int n) {
        if (n == 0) {
            return true;
        }
        for (int i = 0; i             // 检查当前位置是否为空且其左右位置也为空
            if (flowerbed[i] == 0 && (i == 0 || flowerbed[i - 1] == 0) && (i == flowerbed.length - 1 || flowerbed[i + 1] == 0)) {
                flowerbed[i] = 1; // 在当前位置种花
                n--; // 减少需要种下的花的数量
                if (n == 0) {
                    return true; // 已经种下所有计划中的花
                }
            }
        }
        return false; // 无法种下所有计划中的花
    }
}