605. Can Place Flowers

Easy

Description

給定一個整數陣列 flowerbed（0 代表空，1 代表已種花）和整數 n，判斷能否在不違反「相鄰不可種花」規則的情況下再種 n 朵花。

Example:

Input: flowerbed = [1,0,0,0,1], n = 1 Output: true

Intuition#

核心思路：貪心策略——從左到右掃描，每當可以種花就種，能種的數量越多越好。

一個位置可以種花的條件：自身為 0，左邊為 0（或不存在），右邊為 0（或不存在）
貪心是最優的：提早種花不會影響後面的最優解

Approaches#

1: 模擬（建立新陣列）#

概念: 複製陣列，逐一檢查並種花
時間複雜度: O(n) - 遍歷一次
空間複雜度: O(n) - 複製陣列

class Solution {
    fun canPlaceFlowers(flowerbed: IntArray, n: Int): Boolean {
        val bed = flowerbed.copyOf()
        var count = 0
        for (i in bed.indices) {
            if (bed[i] == 0) {
                val leftEmpty = i == 0 || bed[i - 1] == 0
                val rightEmpty = i == bed.lastIndex || bed[i + 1] == 0
                if (leftEmpty && rightEmpty) {
                    bed[i] = 1
                    count++
                }
            }
        }
        return count >= n
    }
}

⭐2: 貪心（原地修改）#

概念: 直接在原陣列上操作，每當條件滿足就種花並跳過下一格
時間複雜度: O(n) - 遍歷一次
空間複雜度: O(1) - 原地修改

class Solution {
    fun canPlaceFlowers(flowerbed: IntArray, n: Int): Boolean {
        var count = 0
        for (i in flowerbed.indices) {
            if (flowerbed[i] == 0) {
                val leftEmpty = i == 0 || flowerbed[i - 1] == 0
                val rightEmpty = i == flowerbed.lastIndex || flowerbed[i + 1] == 0
                if (leftEmpty && rightEmpty) {
                    flowerbed[i] = 1
                    count++
                    if (count >= n) return true
                }
            }
        }
        return count >= n
    }
}

🔑 Takeaways#

Pattern: 貪心 + 一次遍歷，遇到可行位置就立即行動
關鍵技巧: 種花後將位置設為 1，自然阻止下一格再種；提前 return 可以在找到足夠位置時提早結束