Pular para o conteúdo

Dá para chegar ao último índice

Fácil#greedy#farthest-reach~15 min

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

Tempo-alvo
O(n)
Espaço-alvo
O(1)

Restrições

  • the values are non-negative integers

Travou na ideia, e não no código? Jump Game explica isso.

Python 3Ctrl+Enter executa
Caso de teste personalizado