¿Se puede alcanzar el último índice?
La misión
Problema
Empiezas en el índice 0 de una lista de enteros no negativos. El valor de cada índice es el salto más largo que puedes dar desde ahí, así que desde el índice i puedes caer en cualquier índice de i + 1 a i + jumps[i]. Devuelve True si puedes llegar al último índice y False en caso contrario.
Ejemplos
Input: jumps = [2, 3, 1, 1, 4]
Output: True
Por qué: saltas 1 paso al índice 1 y luego 3 pasos hasta el final
Input: jumps = [3, 2, 1, 0, 4]
Output: False
Por qué: toda ruta cae en el índice 3, cuyo valor 0 no lleva a ninguna parte
Input: jumps = [0]
Output: True
Por qué: caso límite: ya estás en el último índice
Pistas
0 / 3
Probar cada secuencia de saltos explota. Hazte una pregunta más pequeña: ¿hasta dónde a la derecha puedes llegar, usando cualquiera de los índices que alcanzas?
Recorre de izquierda a derecha y guarda reach, el índice más lejano alcanzable hasta ahora. Todo índice hasta reach es alcanzable, así que cada uno puede extenderlo a i + jumps[i].
Si el recorrido llega a un índice mayor que reach, hay un hueco que no puedes cruzar y la respuesta es False. Si el recorrido termina, el último índice estaba a tu alcance.
- Tiempo objetivo
- O(n)
- Espacio objetivo
- O(1)
Restricciones
- the values are non-negative integers
Solución
Los índices alcanzables siempre forman un solo bloque sin huecos que empieza en 0, porque si puedes caer en el índice i, también puedes detenerte en cualquier punto antes de tu salto completo. Así que todo el estado es un número: el borde derecho de ese bloque. Al recorrer de izquierda a derecha, cada índice dentro del bloque puede empujar el borde más lejos; el primer índice fuera de él demuestra que no se puede alcanzar nada más allá, porque ningún índice alcanzable saltó lo suficiente. Por eso la elección greedy (voraz) es segura: quedarse con el alcance más lejano no pierde información sobre qué ruta llegó ahí. Una pasada, O(n) de tiempo y O(1) de espacio.
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])) # -> True¿Lo que te frena es la idea y no el código? Jump Game lo explica.