Jump Game

Q: ¿Por qué funciona el enfoque voraz para el Juego del salto?

Como se permiten saltos más cortos, llegar al índice i significa que puedes llegar a todos los índices hasta i+nums[i] . Esos tramos siempre se superponen con la parte a la que ya se ha llegado, así que los índices alcanzables forman un único bloque que empieza en 0. El recorrido voraz solo sigue el extremo derecho de ese bloque, que lo describe por completo, por lo que nunca descarta una ruta que podría haber funcionado.

MedioVoraz Programación dinámica

+10

Estás en el índice 0 del array nums. Desde el índice i puedes saltar hacia delante cualquier número de pasos del 1 hasta nums[i], así que nums[i] es tu salto más largo desde allí y un 0 significa que no puedes moverte. Devuelve true si alguna secuencia de saltos llega al último índice y false en caso contrario.

Función

canJump(nums: integer-array) → boolean

numsinteger-array: el salto más largo que puedes hacer desde cada índice
Devuelveboolean: verdadero si puedes llegar al último índice empezando desde el índice 0; de lo contrario, falso

Restricciones

1 ≤ nums.length ≤ 10⁴
0 ≤ nums[i] ≤ 10⁵
Un salto puede ser más corto que nums[i], así que un salto largo nunca te obliga a pasar del último índice.

Ejemplos

Entrada: nums = [2, 0, 3, 1, 0, 2]
Salida: true
Explicación: Desde el índice 0 puedes llegar al índice 1 o 2. El índice 1 contiene 0 y es un callejón sin salida, pero el índice 2 contiene 3 y llega al índice 5, el último índice.

+18 pruebas ocultas al enviar

Para ir más allá

Cuenta las distintas secuencias de saltos que llegan al último índice, módulo 10^9+7, todavía en tiempo O(n).

Pistas

Ábrelas de una en una. Cada una revela un poco más.

0 de 3 abiertas

Solución

El número de rutas posibles crece exponencialmente, así que comprobar las rutas una por una no funciona con arreglos largos. El dato clave es que los índices a los que puedes llegar siempre forman un bloque continuo que empieza en el índice 0. Un número, el extremo derecho de ese bloque, contiene todo lo que necesitas, y una sola pasada determina la respuesta.

Prueba todos los saltos

Correcto, pero no termina con las pruebas más grandes

Intuición

La idea más directa es representarlo. Colócate en el índice 0 e intenta, uno por uno, todos los puntos de aterrizaje que permite tu salto. Desde cada punto de aterrizaje, haz lo mismo de nuevo. Si alguna rama llega al último índice, la respuesta es true. Si todas las ramas llegan a un callejón sin salida, es false.

En el primer ejemplo, el índice 0 contiene 2, así que pruebas el índice 1 y el índice 2. El índice 1 contiene 0, un callejón sin salida, así que retrocedes y pruebas el índice 2. El índice 2 contiene 3 y llega al índice 5, el último índice, y la búsqueda se detiene con true.

La búsqueda es correcta porque examina todas las rutas. Ese también es su problema: nunca recuerda un índice que ya haya explorado, así que explora el mismo índice de nuevo por cada ruta que llega a él. Cuando la respuesta es false, tiene que descartar todas las rutas. En [4, 3, 2, 1, 0, 5], todos los índices anteriores al 0 pueden llegar al 0, lo que da 8 rutas diferentes hasta él. Con 30 índices de este tipo hay más de 500 millones de rutas, y las pruebas más grandes tienen 10,000 elementos. Una ruta tan larga también desborda la pila de llamadas en algunos lenguajes: Python se detiene en 1,000 llamadas anidadas de forma predeterminada.

Algoritmo

Escribe una función auxiliar reach(i) que responda: ¿puedes llegar desde el índice i hasta el último índice?
Si i es el último índice, devuelve true.
De lo contrario, prueba cada posición de aterrizaje next desde i+1 hasta min(i+nums[i], n-1), y devuelve true en cuanto lo haga reach(next).
Si ninguna posición de aterrizaje funciona, devuelve false.
La respuesta es reach(0).

def canJump(nums):
    last = len(nums) - 1

    def reach(i):
        # Can you get from index i to the last index?
        if i == last:
            return True
        for nxt in range(i + 1, min(i + nums[i], last) + 1):
            if reach(nxt):
                return True
        return False

    return reach(0)

Recuerda qué índices pueden terminar

Correcto, pero no termina con las pruebas más grandes

Intuición

La búsqueda anterior plantea una y otra vez la misma pregunta: «¿puede llegar hasta el final el índice j?». La respuesta para j nunca cambia, así que calcúlala una vez y guárdala. Llama bueno a un índice si desde él puedes llegar al último índice. El último índice es bueno. Cualquier otro índice i es bueno si al menos uno de los índices a los que puede llegar, desde i+1 hasta i+nums[i], es bueno.

Cada índice depende solo de los índices que están a su derecha, así que rellena una tabla good de derecha a izquierda. En el primer ejemplo, el índice 5 es bueno. El índice 4 contiene 0, así que no es bueno. El índice 3 solo llega al índice 4: no es bueno. El índice 2 llega a los índices 3, 4 y 5, y el 5 es bueno, así que el 2 es bueno. El índice 1 contiene 0: no es bueno. El índice 0 llega al 1 y al 2, y el 2 es bueno, así que la respuesta es true.

Ahora cada índice se decide una sola vez, pero para decidirlo todavía se pueden recorrer hasta n celdas. En [9998, 9997, …, 1, 0, 7], todos los índices pueden llegar al 0 y a nada más allá de él, así que cada uno recorre todo su rango y no encuentra ningún índice bueno. Eso equivale a unos 5 × 10^7 comprobaciones para 10 000 elementos, y las pruebas más grandes están construidas como esta. El trabajo crece con el cuadrado de la longitud, así que el tiempo se agota con ellas.

Algoritmo

Crea un arreglo booleano good de longitud n y establece good[n-1] en true.
Recorre i desde n-2 hasta 0.
Examina j desde i+1 hasta min(i+nums[i], n-1). Si algún good[j] es true, establece good[i] en true y deja de examinar.
Devuelve good[0].

def canJump(nums):
    n = len(nums)
    good = [False] * n  # good[i]: from i you can reach the last index
    good[n - 1] = True
    for i in range(n - 2, -1, -1):
        for j in range(i + 1, min(i + nums[i], n - 1) + 1):
            if good[j]:
                good[i] = True
                break
    return good[0]

Rastrea el índice más lejano al que se puede llegar

Intuición

Fíjate en los índices a los que puedes llegar, no en las rutas. Desde el índice i puedes llegar a cualquier índice entre i+1 y i+nums[i], sin saltarte ninguno. Así que, una vez que se puede llegar al índice i, también se puede llegar a todos los índices hasta i+nums[i]. Empieza solo con el índice 0 y sigue añadiendo estos tramos. Cada tramo nuevo empieza dentro del bloque que ya tienes, así que los índices alcanzables siempre forman un único bloque continuo, [0, farthest].

Por eso basta con un número. Recorre i de izquierda a derecha. Mientras i ≤ farthest, se puede llegar al índice i, así que amplía farthest hasta max(farthest, i+nums[i]). Si i llega a superar farthest, ningún índice alcanzable puede saltar hasta i. El bloque no puede crecer más allá de ese hueco, así que no se puede llegar a nada a su derecha, incluido el último índice. Si el recorrido llega al final sin encontrar ningún hueco, se puede llegar al último índice.

En el segundo ejemplo, farthest es 0, luego pasa a 1 después del índice 0 y después a 4 tras el índice 1. Los índices 2, 3 y 4 contienen 0 y lo mantienen en 4. El índice 5 está más allá de 4, así que la respuesta es false. En el primer ejemplo, el índice 2 lleva farthest hasta 5 y ningún índice lo supera, así que la respuesta es true.

¿Por qué es seguro conservar solo el alcance máximo? Nunca te comprometes a dar un salto. El bloque contiene todos los índices a los que se puede llegar por cualquier ruta, y todos los puntos de llegada más cercanos quedan dentro de él. Descartar todo salvo el extremo derecho no hace que se pierda información.

Algoritmo

Establece farthest = 0.
Para cada índice i de izquierda a derecha: si i > farthest, devuelve false.
De lo contrario, establece farthest = max(farthest, i+nums[i]).
Si el bucle termina, se podía alcanzar cada índice, así que devuelve true.

def canJump(nums):
    farthest = 0  # every index up to farthest can be reached
    for i, jump in enumerate(nums):
        if i > farthest:
            return False  # nothing reachable jumps to i
        farthest = max(farthest, i + jump)
    return True

Errores comunes y casos límite

La mayoría de las respuestas incorrectas se deben a interpretar nums[i] como el único salto posible o al orden de las dos comprobaciones dentro del bucle.

Saltar siempre exactamente nums[i] pasos o tomar siempre el salto más largo. Con [2, 5, 0, 0], el salto completo desde el índice 0 cae en un 0, mientras que el salto de 1 paso hasta el índice 1 llega al final.
Devolver false en cuanto veas un 0. Un 0 solo importa cuando nada antes de él lo salta: [2, 0, 1] salta por encima del 0 y la respuesta es true.
Actualizar farthest antes de comprobar i > farthest. Un índice al que no puedes llegar no debe ampliar el bloque, así que comprueba primero y actualiza después.
Considerar que un arreglo de un elemento es un fracaso. Ya estás en el último índice, así que la respuesta es true, incluso cuando ese elemento es 0.
Usar recursión con arreglos largos. Una ruta puede tener 10,000 saltos, lo que desborda la pila de llamadas en varios lenguajes. El recorrido en una sola pasada no usa recursión.

Preguntas frecuentes4

¿Cuál es la complejidad temporal de Jump Game?

El pase que alcanza más lejos visita cada índice una vez, por lo que se ejecuta en tiempo O(n) y con espacio adicional O(1). El enfoque de tabla es O(n²) en el peor caso, y probar todas las rutas tiene complejidad exponencial.

¿Por qué funciona el enfoque voraz para el Juego del salto?

Como se permiten saltos más cortos, llegar al índice i significa que puedes llegar a todos los índices hasta i+nums[i]. Esos tramos siempre se superponen con la parte a la que ya se ha llegado, así que los índices alcanzables forman un único bloque que empieza en 0. El recorrido voraz solo sigue el extremo derecho de ese bloque, que lo describe por completo, por lo que nunca descarta una ruta que podría haber funcionado.

¿Es Jump Game un problema de programación dinámica?

Se puede resolver con programación dinámica: marca como bueno cada índice cuando uno de sus posibles destinos sea bueno, rellenando la tabla de derecha a izquierda. Eso cuesta O(n²). Observa que solo importa el índice bueno más a la izquierda, ya que cualquier índice que llegue a un índice bueno también llega al más a la izquierda. Conserva solo ese índice, goal, y muévelo a i siempre que i+nums[i] ≥ goal. La respuesta es si goal termina en 0; se trata de un recorrido O(n) que refleja el enfoque voraz.

¿Cómo encuentras el número mínimo de saltos?

Usa la misma idea del mayor alcance por capas. Mantén el final del bloque al que puedes llegar con el número actual de saltos y el índice más lejano al que puede llegar el siguiente salto. Cuando i pasa el final del bloque actual, necesitas un salto más, y el siguiente bloque termina en ese índice más lejano. Sigue siendo un recorrido de O(n).

Python

def canJump(nums):
    # Escribe el código aquí

Casos de prueba

Caso 1

Caso 2

Caso 3

Entrada

nums = [2, 0, 3, 1, 0, 2]

Esperado

true

Jump Game

Función

Restricciones

Ejemplos

Pistas

Solución

Prueba todos los saltos

Recuerda qué índices pueden terminar

Rastrea el índice más lejano al que se puede llegar

Errores comunes y casos límite

Preguntas frecuentes4

Problemas similares