Número da Lista: 3
Conteúdo da Disciplina: Algoritmos Ambiciosos

Para o Trabalho 3, nossa dupla selecionou e resolveu quatro desafios da plataforma LeetCode, em conformidade com as diretrizes do professor Maurício Serrano. Foram solucionados três problemas de nível difícil e um de nível médio. O objetivo deste trabalho é demonstrar o conhecimento adquirido nas aulas e estudos sobre a teoria dos Algoritmos Ambiciosos.

Para cada exercício, são apresentados o código-fonte da solução, a captura de tela da submissão bem-sucedida no LeetCode e um vídeo explicativo de até cinco minutos detalhando o raciocínio utilizado.

• C++

A solução gulosa usa um Min-Heap para manter uma janela com um elemento de cada lista. A cada passo, o menor elemento da janela é removido e substituído pelo próximo da mesma lista. Essa estratégia avança a janela eficientemente, atualizando o menor intervalo ([mínimo, máximo]) encontrado até que uma lista se esgote.

A solução adota uma abordagem gulosa reversa, desconstruindo a string target de volta para '?'s. A cada passo, ela busca e substitui qualquer substring que corresponda ao stamp — tratando '?'s como curingas — até que toda a string seja convertida. A sequência final de movimentos é a ordem inversa das substituições feitas.

A solução gulosa usa um Max-Heap (fila de prioridade) para armazenar o combustível de todos os postos de gasolina já alcançados. A cada passo, o carro avança o máximo possível com seu combustível atual. Quando não pode mais prosseguir, ele "abastece" usando a maior quantidade de combustível disponível no heap (a melhor opção passada). Essa estratégia garante que cada parada maximize o alcance futuro, minimizando o número total de paradas necessárias até que o destino seja alcançado.

A solução gulosa utiliza duas variáveis para controlar os "níveis" de alcance: fim_alcance_atual e alcance_maximo. A cada passo, o alcance_maximo é atualizado com o ponto mais distante que pode ser atingido. Quando a iteração alcança a fronteira (fim_alcance_atual), um novo salto é registrado e essa fronteira é expandida para o alcance_maximo calculado. Essa estratégia avança a janela de alcance eficientemente, garantindo que cada salto seja o mais longo possível até que o final do array seja coberto.