605. Can Place Flowers

Level - easy

Task

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 true if n new flowers can be planted in the flowerbed without violating the no-adjacent-flowers rule and false otherwise.

Объяснение

Необходимо проверить, можно ли посадить n цветов на клумбу, не нарушая правило, что цветы не должны расти рядом друг с другом. Это означает, что между любыми двумя цветами (как уже посаженными, так и новыми) должна быть хотя бы одна пустая позиция (0).

У вас есть цветочная клумба, представленная массивом, где 0 обозначает пустое место, а 1 обозначает место, где уже посажен цветок. Цветы нельзя сажать рядом друг с другом, так как они будут соревноваться за воду и свет. Вам нужно определить, можно ли посадить n новых цветов на эту клумбу, соблюдая правило, что цветы не должны расти рядом друг с другом.

Дан массив flowerbed, который состоит из 0 и 1, и целое число n. Нужно определить, можно ли посадить n новых цветов на клумбу, не нарушая правило, что цветы не должны расти рядом друг с другом.

Примеры:

Вход: flowerbed = [1,0,0,0,1], n = 1
Выход: true
Объяснение: Можно посадить цветок на второй позиции (индекс 2), так как он не будет соседствовать с другим цветком.

Вход: flowerbed = [1,0,0,0,1], n = 2
Выход: false
Объяснение: Нельзя посадить два цветка, не нарушив правило, так как они будут соседствовать друг с другом.

Как можно решить:
Для решения задачи можно пройтись по массиву flowerbed и проверять, можно ли посадить цветок на каждой пустой позиции (0), учитывая, что он не будет соседствовать с другими цветами. Если можно посадить цветок, то уменьшаем n на 1 и помечаем эту позицию как занятую (например, меняем 0 на 1). Если в итоге n станет равным 0, то это означает, что все цветы были успешно посажены, и можно вернуть true. Если после прохода по массиву n все еще больше 0, то вернуть false.

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 * 10^4
flowerbed[i] is 0 or 1.
There are no two adjacent flowers in flowerbed.
0 <= n <= flowerbed.length