LeetCode-Go 题解精讲605. Can Place Flowers 种花问题的贪心双步扫描法【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读本文深入讲解 LeetCode 605. Can Place Flowers种花问题给定一个由 0/1 组成的花坛数组判断能否在不违反花卉不能相邻种植规则的前提下再种入 n 朵花。文章以 LeetCode-Go 仓库中该题的 README 题解 为主体逐行剖析仓库内 Go 实现 的贪心双步扫描思路并通过 测试文件 中的 6 组用例验证正确性。读完本文你将掌握该类间隔占位问题的通用分析方法、边界处理技巧以及如何在本地运行测试复现结论。题目描述原题如下英文原文You have a long flowerbed in which some of the plots are planted, and some are not. However, flowers cannot be planted inadjacentplots.Given an integer arrayflowerbedcontaining0s and1s, where0means empty and1means not empty, and an integern, returnifnnew flowers can be planted in theflowerbedwithout violating the no-adjacent-flowers rule.题目大意中文假设你有一个很长的花坛一部分地块种植了花另一部分却没有。可是花卉不能种植在相邻的地块上它们会争夺水源两者都会死去。给定一个花坛表示为一个数组包含 0 和 1其中 0 表示没种植花1 表示种植了花和一个数 n。能否在不打破种植规则的情况下种入 n 朵花能则返回 True不能则返回 False。输入输出示例示例 1Input: flowerbed [1,0,0,0,1], n 1 Output: true示例 2Input: flowerbed [1,0,0,0,1], n 2 Output: false约束条件1 flowerbed.length 2 * 10^4flowerbed[i]是0或1初始花坛中不存在相邻的两朵花该约束保证输入永远合法是解题的重要前提0 n flowerbed.length从约束可以看出数组最长可达 2×10^4线性时间 O(n) 的算法完全够用同时n flowerbed.length说明 n 不可能超出理论可种上限只需判断能否种下而不需要考虑种不完的情况。解题思路一步长为 2 的扫描 边界特判最容易想到的思路是以步长为 2 遍历数组依次统计可种花的位置。之所以步长取 2是因为一旦在某位置种下花其左右相邻位置就再也不能种花所以下一次可检查的位置至少间隔 2。但这个朴素思路存在两种需要单独处理的特殊情况原 README 中已有说明首尾连续多个 0例如00001和10000。首部000...中的第 0 位左侧没有花可以直接种尾部同理最后一个位置若为 0其右侧没有花也可以直接种。这类位置在以 1 为参照的常规判断中容易被遗漏。两个 1 之间夹着的 0 不足以种花例如1001和100001。1001中间两个 0 各自都与 1 相邻种不下任何花100001中间四个 0只有正中间的两个位置可以各种一朵即最多只能种 1 朵花。如果单独把这两种情况分别处理代码会变得冗长且容易出错。解题思路二以 00 为基本单元统一处理原 README 给出了更简洁的第二种思路也是仓库实际采用的实现找到可以种花的基本单元是00那么上面那 2 种特殊情况都可以统一成一种情况。判断是否当前存在 00 的组合如果存在 00 的组合都可以种花。末尾的情况需要单独判断如果末尾为 0也可以种花。这个时候不需要再找 00 组合因为会越界。把能不能在位置 i 种花抽象成一句话位置 i 本身为 0并且它的右邻居要么不存在i 是最后一个位置要么也是 0。由于输入保证不存在相邻的 1只要满足当前为 0 且右邻为 0或越界位置 i 的左邻必然也是 0要么 i 是第 0 位要么 flowerbed[i-1] 由于输入合法而不可能为 1因此该位置一定可以安全种花。这样首部连续 0、尾部连续 0、两 1 之间 0 不足等所有边界情况都被00 基本单元 末尾特判统一覆盖无需再分情况讨论。核心代码实现仓库中 605. Can Place Flowers.go 的完整实现如下与 README 中的代码完全一致package leetcode func canPlaceFlowers(flowerbed []int, n int) bool { lenth : len(flowerbed) for i : 0; i lenth n 0; i 2 { if flowerbed[i] 0 { if i1 lenth || flowerbed[i1] 0 { n-- } else { i } } } if n 0 { return true } return false }逐行解读lenth : len(flowerbed)记录数组长度供末尾判断使用。循环条件i lenth n 0一旦 n 减到 0立即提前终止循环无需再遍历剩余位置这是贪心策略的提前退出优化。步长i 2体现种下一朵花后下一个候选位置至少隔 2 格的核心思想。if flowerbed[i] 0当前位置为空才可能种花若当前位置为 1则直接跳过i 2后检查下一个间隔位置。if i1 lenth || flowerbed[i1] 0这是整个算法的关键判定i1 lenth表示 i 是数组最后一个位置右侧没有地块末尾单独判断由此完成——末尾为 0 即可种花不需要再找 00 组合否则访问flowerbed[i1]会越界flowerbed[i1] 0表示当前位置与其右邻构成00组合即 README 所述的可种花基本单元。满足任一条件则n--在该位置种下一朵花否则进入 else 分支。else { i }这是最容易忽视、但必不可少的一行。它出现的场景是flowerbed[i] 0但flowerbed[i1] 1。此时位置 i 的右邻已种花位置 i 不能种又因为位置 i1 被占用位置 i2 与 i1 相邻也不能种所以下一个真正的候选位置是 i3。这里的i配合循环的i 2恰好把 i 推进到 i3一次性跳过两个不可用位置。没有这行算法会在类似[1,0,0,1,0]的输入上误判详见下文用例 6 的推演。复杂度分析时间复杂度O(n)。循环最多执行 ⌈lenth/2⌉ 次每次操作均为常数时间且一旦 n 减为 0 便提前退出实际开销往往更小。空间复杂度O(1)。只使用了若干整型变量不依赖额外数据结构符合数组长度最大 2×10^4 的约束。关键用例逐步推演下面选取仓库 测试文件 中的全部 6 组用例逐一推演验证算法对普通、首尾、间隔不足等各类情形的处理。#flowerbedn期望输出推演过程1[1,0,0,0,1]1truei0 处为 1 跳过i2 处为 0 且 flowerbed[3]0构成 00n 减为 0提前退出返回 true2[1,0,0,0,1]2falsei2 处种一朵n 减为 1i4 处为 1 跳过循环结束 n 仍为 1返回 false3[1,0,0,0,0,1]2falsei2 处种一朵n 减为 1i4 处为 0 但 flowerbed[5]1进入 elsei 跳至 7 越界n 仍为 1返回 false——即两个 1 之间的 4 个 0 最多只够种 1 朵4[0,0,1,0]1truei0 处为 0 且 flowerbed[1]0种下后 n 减为 0返回 true首部连续 0 场景5[0,0,1,0,0]1truei0 处构成 00 直接种下n 减为 0返回 true首尾连续 0 场景6[1,0,0,1,0]2falsei0 处为 1 跳过i2 处为 0 但 flowerbed[3]1进入 else 使 i 变为 5 越界n 仍为 2返回 false——若没有 else 中的 ii4 会被误判为可种导致错误输出 true其中用例 6 最能体现else { i }的必要性[1,0,0,1,0]中位置 2 与位置 3 相邻位置 4 也与位置 3 相邻整块花坛实际一个空位都没有必须返回 false。再看两个典型的边界情形flowerbed [0,0,0], n 2i0 处 00 种一朵i2 处i1 lenth触发末尾判断再种一朵返回 true——验证了末尾为 0 也可以种flowerbed [0], n 1i0 处i1 lenth成立直接种下返回 true——长度为 1 的退化输入同样正确。测试用例与本地验证仓库为本题准备了完整的表驱动测试605. Can Place Flowers_test.go。测试采用 LeetCode-Go 统一的question605/para605/ans605结构组织用例其中para605封装输入参数flowerbed与nans605封装期望输出Test_Problem605遍历全部用例并打印输入输出type para605 struct { flowerbed []int n int } type ans605 struct { one bool } func Test_Problem605(t *testing.T) { qs : []question605{ {para605{[]int{1, 0, 0, 0, 1}, 1}, ans605{true}}, {para605{[]int{1, 0, 0, 0, 1}, 2}, ans605{false}}, {para605{[]int{1, 0, 0, 0, 0, 1}, 2}, ans605{false}}, {para605{[]int{0, 0, 1, 0}, 1}, ans605{true}}, {para605{[]int{0, 0, 1, 0, 0}, 1}, ans605{true}}, {para605{[]int{1, 0, 0, 1, 0}, 2}, ans605{false}}, } // ... for _, q : range qs { _, p : q.ans605, q.para605 fmt.Printf(【input】:%v 【output】:%v\n, p, canPlaceFlowers(p.flowerbed, p.n)) } }在仓库根目录模块定义见 go.modGo 版本为 1.19执行以下命令即可单独运行本题的全部测试go test ./leetcode/0605.Can-Place-Flowers/ -v若要运行整个仓库所有题目的测试并生成覆盖率报告可参考根目录的 gotest.shgo test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...该脚本一次性对./leetcode/...下所有包生成单一合法的覆盖率文件也是仓库100% test coverage约定的落地方式之一。小结与同类问题联想Can Place Flowers 是典型的贪心 间隔占位问题核心收获有三点基本单元抽象把复杂的边界情况首尾连续 0、两 1 之间 0 不足统一为当前位置为 0 且右邻为 0 或越界这一条判定代码因此极其简洁步长 2 的跳跃扫描利用种花后相邻格作废的性质将扫描量减半配合n 0的提前退出实际运行时间远低于线性上界else 分支的 i 精妙处理在右邻被占用时连跳两格i3避免对必然不可种的 i2 做无效判断这是本实现与朴素写法最大的区别。类似地凡是相邻不可同时占用类问题如会议室安排、任务调度中的不相邻选择等都可以参考按间隔跳跃扫描 边界特判的分析框架。若想查看更多同类数组/贪心题目的 Go 题解可以在本仓库leetcode/目录下按题号查阅对应的 README.md 与配套测试文件。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考