mirror of
https://github.com/halfrost/LeetCode-Go.git
synced 2025-07-07 18:10:29 +08:00
60 lines
2.3 KiB
Markdown
60 lines
2.3 KiB
Markdown
# [605. Can Place Flowers](https://leetcode.com/problems/can-place-flowers/)
|
||
|
||
## 题目
|
||
|
||
You have a long flowerbed in which some of the plots are planted, and some are not. However, flowers cannot be planted in **adjacent** plots.
|
||
|
||
Given an integer array `flowerbed` containing `0`'s and `1`'s, where `0` means empty and `1` means not empty, and an integer `n`, return *if* `n` new flowers can be planted in the `flowerbed` without violating the no-adjacent-flowers rule.
|
||
|
||
**Example 1:**
|
||
|
||
```
|
||
Input: flowerbed = [1,0,0,0,1], n = 1
|
||
Output: true
|
||
```
|
||
|
||
**Example 2:**
|
||
|
||
```
|
||
Input: flowerbed = [1,0,0,0,1], n = 2
|
||
Output: false
|
||
```
|
||
|
||
**Constraints:**
|
||
|
||
- `1 <= flowerbed.length <= 2 * 104`
|
||
- `flowerbed[i]` is `0` or `1`.
|
||
- There are no two adjacent flowers in `flowerbed`.
|
||
- `0 <= n <= flowerbed.length`
|
||
|
||
## 题目大意
|
||
|
||
假设你有一个很长的花坛,一部分地块种植了花,另一部分却没有。可是,花卉不能种植在相邻的地块上,它们会争夺水源,两者都会死去。给定一个花坛(表示为一个数组包含0和1,其中0表示没种植花,1表示种植了花),和一个数 n 。能否在不打破种植规则的情况下种入 n 朵花?能则返回True,不能则返回False。
|
||
|
||
## 解题思路
|
||
|
||
- 这一题最容易想到的解法是步长为 2 遍历数组,依次计数 0 的个数。有 2 种特殊情况需要单独判断,第一种情况是首尾连续多个 0,例如,00001 和 10000,第二种情况是 2 个 1 中间存在的 0 不足以种花,例如,1001 和 100001,1001 不能种任何花,100001 只能种一种花。单独判断出这 2 种情况,这一题就可以 AC 了。
|
||
- 换个思路,找到可以种花的基本单元是 00,那么上面那 2 种特殊情况都可以统一成一种情况。判断是否当前存在 00 的组合,如果存在 00 的组合,都可以种花。末尾的情况需要单独判断,如果末尾为 0,也可以种花。这个时候不需要再找 00 组合,因为会越界。代码实现如下,思路很简洁明了。
|
||
|
||
## 代码
|
||
|
||
```go
|
||
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 i+1 == lenth || flowerbed[i+1] == 0 {
|
||
n--
|
||
} else {
|
||
i++
|
||
}
|
||
}
|
||
}
|
||
if n == 0 {
|
||
return true
|
||
}
|
||
return false
|
||
}
|
||
``` |