860. Cambio de limonada

Dificultad: Fácil

Temas: Matriz, codicioso

En un puesto de limonada, cada limonada cuesta $5. Los clientes hacen cola para comprarle y realizar pedidos uno a la vez (en el orden especificado en las facturas). Cada cliente solo comprará una limonada y pagará con un billete de $5, $10 o $20. Debes proporcionar el cambio correcto a cada cliente para que la transacción neta sea que el cliente pague $5.

Ten en cuenta que al principio no tienes ningún cambio disponible.

Dada una matriz de números enteros facturas donde facturas[i] es la factura que paga el i^ésimo cliente, devuelva verdadero si puede proporcionar a cada cliente el cambio correcto, o falso en caso contrario .

Ejemplo 1:

• Entrada: facturas = [5,5,5,10,20]
• Salida: verdadero
• Explicación:
  • De los primeros 3 clientes, cobramos tres billetes de $5 en orden.
  • Del cuarto cliente, cobramos un billete de $10 y le devolvemos $5.
  • Del quinto cliente, le damos un billete de $10 y otro de $5.
  • Dado que todos los clientes obtuvieron el cambio correcto, generamos verdadero.

Ejemplo 2:

• Entrada: facturas = [5,5,10,10,20]
• Salida: falso
• Explicación:
  • De los dos primeros clientes en orden, cobramos dos billetes de $5.
  • Para los siguientes dos clientes en orden, cobramos un billete de $10 y devolvemos un billete de $5.
  • Para el último cliente, no podemos devolverle el cambio de $15 porque solo tenemos dos billetes de $10.
  • Dado que no todos los clientes recibieron el cambio correcto, la respuesta es falsa.

Restricciones:

• 5
• los billetes[i] son ​​5, 10 o 20.

Solución:

Necesitamos simular el proceso de proporcionar cambio a los clientes en función de las facturas que utilizan para pagar. La clave es realizar un seguimiento del número de billetes de $5 y $10 que tienes, ya que son necesarios para dar cambio a billetes más grandes

Implementemos esta solución en PHP: 860. Cambio de limonada

Explicación:

1. Inicialización: comenzamos con $cinco y $diez establecidos en 0, lo que representa el recuento de billetes de $5 y $10 que tenemos.

2. Procesamiento de cada factura:

   • Si el cliente paga con un billete de $5: Simplemente incrementamos el recuento de billetes de $5.
   • Si el cliente paga con un billete de $10: Necesitamos devolver un billete de $5 como cambio, por lo que disminuimos el recuento de billetes de $5 e incrementamos el recuento de billetes de $10. Si no tenemos ningún billete de $5, devuelve false.
   • Si el cliente paga con un billete de $20: Priorizamos dar un billete de $10 y un billete de $5 como cambio. Si eso no es posible, intentamos dar tres billetes de $5. Si ninguna de las opciones está disponible, devuelve falso.

3. Verificación final: Si procesamos exitosamente a todos los clientes sin quedarnos sin cambio, devuelve verdadero.

Casos extremos:

• La función debe manejar situaciones en las que es imposible dar el cambio correcto, como cuando recibes un billete de $10 o $20 demasiado pronto sin tener a mano los billetes de $5 necesarios.
• Debería manejar de manera eficiente tamaños de entrada grandes debido a las limitaciones (hasta 100 000 clientes). La solución se ejecuta en una complejidad de tiempo O(n), lo que la hace óptima para este problema.

Enlaces de contacto

Si esta serie te resultó útil, considera darle al repositorio una estrella en GitHub o compartir la publicación en tus redes sociales favoritas. ¡Tu apoyo significaría mucho para mí!

Si quieres más contenido útil como este, no dudes en seguirme:

• LinkedIn
• GitHub