605_种花问题

类型：数组

种花问题 💚 ⭐

https://leetcode-cn.com/problems/can-place-flowers/

❓ 数组 flowerbed 表示花坛，0 表示没种花，1 表示种了花。我们要再往里种入 n 朵花，花与花不能相邻，问能否种入。

💡 模拟法

遍历花坛，只要出现了可种花的位置，立即种下一棵。该方法会修改原数组。

class Solution:
    def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:
        if n <= 0:
            return True
        if not flowerbed:
            return False
        if len(flowerbed) < 2 * n - 1:
            return False

        for i in range(len(flowerbed)):
            if flowerbed[i] == 0 and (i <= 0 or flowerbed[i - 1] == 0) and (i >= len(flowerbed) - 1 or flowerbed[i + 1] == 0):
                flowerbed[i] = 1
                n -= 1
                if n <= 0:
                    return True

        return False

时间复杂度：O(n)，空间复杂度：O(1)

💡 贪心法

如果 [i, j] 是连续空位，那么这段空位中可以种下 (j−i−2)/2 朵花。

class Solution:
    def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:
        count, m, prev = 0, len(flowerbed), -1
        for i in range(m):
            if flowerbed[i] == 1:
                if prev < 0:
                    count += i // 2
                else:
                    count += (i - prev - 2) // 2
                if count >= n:
                    return True
                prev = i

        if prev < 0:
            count += (m + 1) // 2
        else:
            count += (m - prev - 1) // 2

        return count >= n

时间复杂度：O(n)，空间复杂度：O(1)

💡 动态规划

如果我们有一个空的花坛可以随意种，那么对于任意位置都有种（dp[i][1]）与不种（dp[i][0]）两种可能。但是现在花坛中已经种了一些花了，所以某些位置 dp[i][0] 的可能就被抹除了。

class Solution {
public:
    bool canPlaceFlowers(vector<int>& nums, int n) {
        int size = nums.size();
        int dp[size][2];
        dp[0][1] = 1;
        dp[0][0] = nums[0] == 1 ? -10000 : 0;
        int sum = nums[0];
        for (int i = 1; i < size; i++) {
            dp[i][1] = dp[i-1][0] + 1;
            dp[i][0] = nums[i] == 1 ? -10000 : max(dp[i-1][0], dp[i-1][1]);
            sum += nums[i];
        }
        int mx = max(dp[size-1][0], dp[size-1][1]);
        return mx - sum >= n;
    }
};

时间复杂度：O(n)，空间复杂度：O(1)