Colocar Flores - LeetCode 605

Descripción

Se tiene una serie de macetas en la que algunas tienen flores y otras no. Queremos saber si podemos colocar más flores con la restricción de que no se pueden plantar en macetas que adyacentas.

Se da un array llamado flowerbed que contiene 0s y 1s, donde 0 significa que la maceta está vacía y 1 significa que tiene una flor, también se da un entero n que indica el número de flores por plantar.

Completa la función canPlaceFlower para devolver True si se pueden plantar n nuevas flores en la serie de macetas sin romper la regla de no tener flores adyacentes. Si la regla se rompe, devuelve False.

Ejemplo 1

Entrada: flowerbed = [1,0,0,0,1], n = 1
Salida: True

Ejemplo 2:

Entrada: flowerbed = [1,0,0,0,1], n = 2
Salida: False

Restricciones:

  • 1 <= flowerbed.length <= 2 * 104
  • flowerbed[i] es 0 o 1.
  • No debe haber flores adyacentes en las macetas.
  • 0 <= n <= flowerbed.length

Solución

Mostrar solución 
class Solution:
    def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:
        # Recorrer array flowerbed
        for i in range(len(flowerbed)):
            # Buscar un lugar para colocar la flor, cumpliendo regla de no ser adyacente

            # Terminar el ciclo si no hay más flores por colocar
            if n == 0:
                break

            # Si la maceta está ocupada, ir a la siguiente posición
            if flowerbed[i] == 0:
                # Valores para indicar si los lados de la posición están libres
                left_ok = True
                right_ok = True

                # Si la posición de la izquierda es válida
                if (i - 1) >= 0:
                    # Revisamos la posición
                    if flowerbed[i - 1] == 1:
                        # Si esta ocupada, la marcamos como ocupada / no libre
                        left_ok = False

                # Si la posición de la derecha es válida
                if (i + 1) < len(flowerbed):
                    # Revisamos la posición
                    if flowerbed[i + 1] == 1:
                        # Si esta ocupada, la marcamos como ocupada / no libre
                        right_ok = False

                # Si ambas posiciones están libres
                if left_ok and right_ok:
                    # Colocar flor
                    flowerbed[i] = 1
                    
                    # Testar la flor colcada
                    n -= 1

                # Si no podemos colocar la flor, probar siguiente posición
        # Terminamos de recorrer flowerbed

        # Devolver True solo si no quedan flores que colocar
        return n == 0

Solución en Google Colab Probar Solución

-

Live Resolviendo el Ejercicio

Fuente del ejercicio: https://leetcode.com/problems/can-place-flowers/