605. Can Place Flowers #

Problem #

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

Problem Meaning #

Suppose you have a very long flowerbed, where some plots are planted with flowers and others are not. However, flowers cannot be planted in adjacent plots, because they will compete for water and both will die. Given a flowerbed (represented as an array containing 0s and 1s, where 0 means no flower is planted and 1 means a flower is planted), and a number n . Can n flowers be planted without violating the planting rule? Return True if possible, otherwise return False.

Solution Approach #

The most intuitive solution for this problem is to traverse the array with a step size of 2 and count the number of 0s one by one. There are 2 special cases that need to be handled separately. The first case is multiple consecutive 0s at the beginning or end, such as 00001 and 10000. The second case is when the 0s between two 1s are not enough to plant flowers, such as 1001 and 100001; 1001 cannot plant any flowers, while 100001 can only plant one flower. After handling these 2 cases separately, this problem can be ACed.
From another perspective, the basic unit where a flower can be planted is 00, so the above 2 special cases can both be unified into one case. Determine whether a 00 combination currently exists; if a 00 combination exists, a flower can be planted. The case at the end needs to be handled separately: if the last position is 0, a flower can also be planted. At this point, there is no need to look for a 00 combination anymore, because it would go out of bounds. The code implementation is as follows, and the idea is very concise and clear.

Code #

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
}