Dá para chegar ao último índice
A missão
Problema
Você começa no índice 0 de uma lista de inteiros não negativos. O valor em cada índice é o maior salto que você pode dar dali, então, a partir do índice i, você pode cair em qualquer índice de i + 1 até i + jumps[i]. Retorne True se você conseguir chegar ao último índice; caso contrário, False.
Exemplos
Input: jumps = [2, 3, 1, 1, 4]
Output: True
Por quê: salte 1 passo até o índice 1 e depois 3 passos até o fim
Input: jumps = [3, 2, 1, 0, 4]
Output: False
Por quê: toda rota cai no índice 3, cujo valor 0 não leva a lugar nenhum
Input: jumps = [0]
Output: True
Por quê: edge case: você já está no último índice
Dicas
0 / 3
Testar todas as sequências de saltos explode. Faça uma pergunta menor: até onde, à direita, você consegue chegar usando qualquer um dos índices que alcança?
Varra da esquerda para a direita e mantenha reach, o índice mais distante alcançável até agora. Todo índice até reach é alcançável, então cada um pode estendê-lo até i + jumps[i].
Se a varredura chegar a um índice maior que reach, há uma lacuna que você não consegue atravessar e a resposta é False. Se a varredura terminar, o último índice estava ao alcance.
- Tempo-alvo
- O(n)
- Espaço-alvo
- O(1)
Restrições
- the values are non-negative integers
Solução
Os índices alcançáveis sempre formam um único bloco contínuo que começa em 0, porque, se você consegue cair no índice i, também pode parar em qualquer ponto antes do salto completo. Então o estado inteiro é um número só: o limite direito desse bloco. Percorrendo da esquerda para a direita, cada índice dentro do bloco pode empurrar o limite mais para a frente; o primeiro índice fora dele prova que nada além pode ser alcançado, já que nenhum índice alcançável saltou longe o bastante. É por isso que a escolha gulosa é segura: guardar o maior alcance não perde nenhuma informação sobre qual rota chegou até ali. Uma passada, tempo O(n) e espaço O(1).
def can_reach_end(jumps):
reach = 0 # farthest index reachable so far
for i, step in enumerate(jumps):
if i > reach: # a gap nobody can jump over
return False
reach = max(reach, i + step)
return True
print(can_reach_end([2, 3, 1, 1, 4])) # -> True
print(can_reach_end([3, 2, 1, 0, 4])) # -> False
print(can_reach_end([0])) # -> TrueTravou na ideia, e não no código? Jump Game explica isso.