605. Can Place Flowers

LeetCode задача 605

Задача

Дана длинная грядка, на которой некоторые участки уже засажены, а некоторые нет. Однако цветы нельзя сажать на соседние участки.

Подход

Чтобы решить эту задачу, мы будем итерироваться по каждому участку грядки. Если участок пустой и его соседи (если они существуют) тоже пусты, мы сажаем цветок и уменьшаем наш счетчик.

Алгоритм

1. Итерируемся по каждому участку грядки.
2. Если участок пустой, проверяем его соседей.
   • Если левый сосед пустой или его нет (начало грядки), проверяем правого соседа.
   • Если правый сосед пустой или его нет (конец грядки), сажаем цветок на текущий участок и уменьшаем n.
3. В конце проверяем, достиг ли n нуля или стал отрицательным.
   • Если да, то это означает, что мы можем посадить все цветы.

Решение

def canPlaceFlowers(flowerbed, n):
    def check_neighbors(n):
        if i < len(flowerbed) - 1:
            if flowerbed[i+1] == 0: #2.2
                flowerbed[i] = 1
                n -= 1
        else:
            flowerbed[i] = 1
            n -= 1
        return n

    for i in range(len(flowerbed)):  #1
        if flowerbed[i] == 0:  #2
            if i > 0:
                if flowerbed[i-1] == 0: #2.1
                    n = check_neighbors(n)
            else:
                n = check_neighbors(n)
    return n <= 0  #3