860. Mudança de limonada

Dificuldade: Fácil

Tópicos: Matriz, Ganancioso

Em uma barraca de limonada, cada limonada custa US$ 5. Os clientes ficam em fila para comprar de você e fazer o pedido um de cada vez (na ordem especificada nas faturas). Cada cliente comprará apenas uma limonada e pagará com uma nota de US$ 5, US$ 10 ou US$ 20. Você deve fornecer o troco correto a cada cliente para que a transação líquida seja que o cliente pague US$ 5.

Observação que você não tem nenhuma alteração em mãos a princípio.

Dada uma matriz inteira bills onde bills[i] é a fatura que o i^ésimo cliente paga, retorne true se você puder fornecer a cada cliente a alteração correta, ou false caso contrário .

Exemplo 1:

• Entrada: contas = [5,5,5,10,20]
• Saída: verdadeiro
• Explicação:
  • Dos três primeiros clientes, coletamos três notas de US$ 5 em ordem.
  • Do quarto cliente, cobramos uma nota de US$ 10 e devolvemos US$ 5.
  • Do quinto cliente, damos uma nota de US$ 10 e uma nota de US$ 5.
  • Como todos os clientes obtiveram a alteração correta, produzimos verdadeiro.

Exemplo 2:

• Entrada: contas = [5,5,10,10,20]
• Saída: falso
• Explicação:
  • Dos dois primeiros clientes do pedido, coletamos duas notas de US$ 5.
  • Para os próximos dois clientes do pedido, cobramos uma nota de US$ 10 e devolvemos uma nota de US$ 5.
  • Para o último cliente, não podemos devolver o troco de US$ 15 porque só temos duas notas de US$ 10.
  • Como nem todos os clientes receberam a alteração correta, a resposta é falsa.

Restrições:

• 5
• contas[i] é 5, 10 ou 20.

Solução:

Precisamos simular o processo de fornecimento de troco aos clientes com base nas contas que eles usam para pagar. O segredo é rastrear o número de notas de US$ 5 e US$ 10 que você possui, pois elas são necessárias para fornecer troco para notas maiores

Vamos implementar esta solução em PHP: 860. Mudança de limonada

Explicação:

1. Inicialização: Começamos com $5 e $10 definidos como 0, representando a contagem de notas de $5 e $10 que temos.

2. Processando cada fatura:

   • Se o cliente pagar com uma nota de $ 5: simplesmente incrementamos a contagem de notas de $ 5.
   • Se o cliente pagar com uma nota de $ 10: Precisamos devolver uma nota de $ 5 como troco, então diminuímos a contagem de notas de $ 5 e aumentamos a contagem de notas de $ 10. Se não tivermos notas de $ 5, retorne falso.
   • Se o cliente pagar com uma nota de US$ 20: Priorizamos dar uma nota de US$ 10 e uma nota de US$ 5 como troco. Se isso não for possível, tentamos dar três notas de 5 dólares. Se nenhuma opção estiver disponível, retorne false.

3. Verificação final: se processamos com sucesso todos os clientes sem ficar sem troco, retorne verdadeiro.

Casos extremos:

• A função deve lidar com cenários em que é impossível dar o troco correto, como quando você recebe uma nota de US$ 10 ou US$ 20 muito cedo sem ter as notas de US$ 5 necessárias em mãos.
• Deve lidar com eficiência com grandes tamanhos de entrada devido às restrições (até 100.000 clientes). A solução é executada em complexidade de tempo O(n), tornando-a ideal para este problema.

Links de contato

Se você achou esta série útil, considere dar uma estrela ao repositório no GitHub ou compartilhar a postagem em suas redes sociais favoritas ?. Seu apoio significaria muito para mim!

Se você quiser mais conteúdo útil como este, sinta-se à vontade para me seguir:

• LinkedIn
• GitHub