LeetCode算法题(Go语言实现)_04

题目

假设有一个很长的花坛，一部分地块种植了花，另一部分却没有。可是，花不能种植在相邻的地块上，它们会争夺水源，两者都会死去。
给你一个整数数组 flowerbed 表示花坛，由若干 0 和 1 组成，其中 0 表示没种植花，1 表示种植了花。另有一个数 n ，能否在不打破种植规则的情况下种入 n 朵花？能则返回 true ，不能则返回 false 。

一、Go 语言实现

func canPlaceFlowers(flowerbed []int, n int) bool {
    count := 0
    i := 0
    for i < len(flowerbed) {
        if flowerbed[i] == 0 {
            // 检查左侧和右侧是否为0（或边界）
            leftOk := (i == 0) || (flowerbed[i-1] == 0)
            rightOk := (i == len(flowerbed)-1) || (flowerbed[i+1] == 0)
            if leftOk && rightOk {
                count++
                i += 2 // 跳过下一个位置
                continue
            }
        }
        i++
    }
    return count >= n
}

二、算法分析

1. 核心思路

• 贪心策略：遍历花坛，若当前位置可种花（满足左右无花且当前为空），则立即种花并跳过下一个位置，以最大化可种数量。
• 关键观察：种花后相邻位置不可再种，因此直接跳过下一位置避免重复检查。

2. 关键步骤

1. 遍历花坛：从左到右依次检查每个位置。
2. 条件判断：
   • 当前为空（flowerbed[i] == 0）。
   • 左侧无花（i == 0 或 flowerbed[i-1] == 0）。
   • 右侧无花（i == len(flowerbed)-1 或 flowerbed[i+1] == 0）。
3. 种花计数：满足条件则计数加1，并跳过下一位置。
4. 结果判定：最终可种数量 count 是否大于等于 n。

3. 复杂度

• 时间复杂度：O(n)，仅需一次线性遍历。
• 空间复杂度：O(1)，仅使用常数变量。

三、 图解

四、 边界条件与扩展

1. 空花坛：题目保证 n ≥ 0，无需处理。
2. 全空花坛：若花坛全为 0，最多可种 (len(flowerbed)+1)/2 朵花。
3. n=0：直接返回 true。
4. 单元素花坛：[0] 可种1朵，[1] 不可种。

五、总结

• 核心逻辑：贪心遍历，及时跳过不可种位置。
• 优化点：无需修改原数组，仅需判断条件并计数。
• 适用场景：类似“间隔放置”或“最大化覆盖”问题可借鉴此思路。