給定一個整數陣列
flowerbed（0 代表空，1 代表已種花）和整數n，判斷能否在不違反「相鄰不可種花」規則的情況下再種n朵花。
Example:
Input: flowerbed = [1,0,0,0,1], n = 1 Output: true
Intuition
TIP
核心思路：貪心策略——從左到右掃描，每當可以種花就種，能種的數量越多越好。
- 一個位置可以種花的條件：自身為 0，左邊為 0（或不存在），右邊為 0（或不存在）
- 貪心是最優的：提早種花不會影響後面的最優解
Approaches
1. Simulation (new array) — O(n) / O(n)
- Idea: 複製陣列，逐一檢查並種花
- Time:
O(n)- 遍歷一次 - Space:
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. Greedy (in-place) — O(n) / O(1)
- Idea: 直接在原陣列上操作，每當條件滿足就種花並跳過下一格
- Time:
O(n)- 遍歷一次 - Space:
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: 貪心 + 一次遍歷，遇到可行位置就立即行動
- Key trick: 種花後將位置設為 1，自然阻止下一格再種；提前 return 可以在找到足夠位置時提早結束