605.can-place-flowers.md

605. Can Place Flowers

Greedy

判断能否在不打破种植规则的情况下在花坛内种入n朵花，从贪心的角度考虑，应该在不打破种植规则的情况下种入尽可能多的花

从左到右遍历数组，能种花就立刻种花。 为了简化判断逻辑，可以在数组的开头和末尾各插入一个0。

We can place a flower if the previous and next position are empty or out of bounds:

1. If the current position is the first position, we can place a flower if the next position is empty or out of bounds.
2. If the current position is the last position, we can place a flower if the previous position is empty or out of bounds.
3. If the current position is in the middle, we can place a flower if the previous and next positions are empty.

fun canPlaceFlowers(flowerbed: IntArray, required: Int): Boolean {
    if (required == 0) return true
    if (flowerbed.size == 1) return flowerbed[0] == 0

    val n = flowerbed.size
    var planted = 0
    for (i in 0 until n) {
        if (flowerbed[i] == 1) continue
        if (i == 0) {
            if (i + 1 < n && flowerbed[i + 1] == 0) {
                flowerbed[i] = 1
                planted++
            }
        } else if (i == n - 1) {
            if (i - 1 >= 0 && flowerbed[i - 1] == 0) {
                flowerbed[i] = 1
                planted++
            }
        } else { // Not first or last position, we check the previous and next positions
            if (flowerbed[i - 1] == 0 && flowerbed[i + 1] == 0) {
                flowerbed[i] = 1
                planted++
            }
        }
        if (planted >= required) return true
    }
    return planted >= required
}

// Or the same idea but more concise
fun canPlaceFlowers(flowerbed: IntArray, required: Int): Boolean {
    var planted = 0
    for (i in 0 until flowerbed.size) {
        if (flowerbed[i] == 1) continue
        val previous = if (i == 0) 0 else flowerbed[i - 1]
        val next = if (i == n - 1) 0 else flowerbed[i + 1]
        if (previous == 0 && next == 0) {
            flowerbed[i] = 0
            planted++
        }
        if (planted >= required) return true
    }
    return planted >= required
}

• Time complexity: O(n)
• Space complexity: O(1)