Jump Game

+10

Tu te trouves à l’indice 0 du tableau nums. Depuis l’indice i, tu peux avancer d’un nombre quelconque de pas compris entre 1 et nums[i] ; nums[i] correspond donc à la longueur maximale de ton saut depuis cet indice, et un 0 signifie que tu ne peux pas avancer. Renvoie true si une séquence de sauts permet d’atteindre le dernier indice, et false sinon.

Fonction

canJump(nums: integer-array) → boolean

numsinteger-array: le plus grand saut que tu peux effectuer depuis chaque indice
Renvoieboolean: vrai si tu peux arriver au dernier indice en partant de l’indice 0, sinon faux

Contraintes

1 ≤ nums.length ≤ 10⁴
0 ≤ nums[i] ≤ 10⁵
Un saut peut être plus court que nums[i], donc un long saut ne vous oblige jamais à dépasser le dernier indice.

Exemples

Entrée: nums = [2, 0, 3, 1, 0, 2]
Sortie: true
Explication: Depuis l’index 0, tu peux atteindre l’index 1 ou 2. L’index 1 contient 0 et est une impasse, mais l’index 2 contient 3 et mène à l’index 5, le dernier index.

+18 tests cachés à la soumission

Pour aller plus loin

Comptez les différentes séquences de sauts qui atterrissent sur le dernier indice, modulo 10^9+7, toujours en O(n) temps.

Indices

Ouvrez-les un par un. Chacun en dévoile un peu plus.

0 sur 3 ouverts

Solution

Le nombre de trajets possibles croît de façon exponentielle, donc vérifier les trajets un par un ne peut pas fonctionner sur de longs tableaux. Le fait essentiel est que les indices que vous pouvez atteindre forment toujours un bloc continu commençant à l’indice 0. Un seul nombre, l’extrémité droite de ce bloc, contient tout ce dont vous avez besoin, et un seul parcours suffit à déterminer la réponse.

Essaie chaque saut

Correcte, mais ne termine pas sur les plus gros tests

Intuition

L’idée la plus directe est de mettre cela en scène. Place-toi à l’index 0 et essaie, un par un, chaque point d’atterrissage que ton saut permet d’atteindre. Depuis chaque point d’atterrissage, recommence. Si une branche atteint le dernier index, la réponse est true. Si toutes les branches aboutissent à une impasse, la réponse est false.

Dans le premier exemple, l’index 0 contient 2, donc tu essaies les index 1 et 2. L’index 1 contient 0, une impasse : tu reviens donc en arrière et essaies l’index 2. L’index 2 contient 3 et permet d’atteindre l’index 5, le dernier index ; la recherche s’arrête alors avec true.

La recherche est correcte parce qu’elle examine tous les itinéraires. C’est aussi là que réside le problème : elle ne mémorise jamais un index déjà exploré et explore donc de nouveau le même index pour chaque itinéraire qui y mène. Lorsque la réponse est false, elle doit écarter tous les itinéraires. Dans [4, 3, 2, 1, 0, 5], chaque index situé avant le 0 peut atteindre le 0, ce qui crée 8 itinéraires différents qui y mènent. Avec 30 index de ce type, il y a plus de 500 millions d’itinéraires, et les tests les plus grands comportent 10 000 éléments. Un itinéraire aussi long provoque également un dépassement de la pile d’appels dans certains langages : Python s’arrête par défaut après 1 000 appels imbriqués.

Algorithme

Écrivez une fonction auxiliaire reach(i) qui répond à la question suivante : peut-on atteindre le dernier indice à partir de l’indice i ?
Si i est le dernier indice, renvoyez true.
Sinon, essayez chaque position d’arrivée next de i+1 à min(i+nums[i], n-1), et renvoyez true dès que reach(next) le fait.
Si aucune position d’arrivée ne fonctionne, renvoyez false.
La réponse est 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)

N’oubliez pas quels indices peuvent terminer

Correcte, mais ne termine pas sur les plus gros tests

Intuition

La recherche ci-dessus pose sans cesse la même question : « l’indice j peut-il finir ? ». La réponse pour j ne change jamais, alors calcule-la une fois et stocke-la. Un indice est bon lorsqu’on peut atteindre le dernier indice à partir de celui-ci. Le dernier indice est bon. Tout autre indice i est bon lorsqu’au moins un indice qu’il peut atteindre, de i+1 à i+nums[i], est bon.

Chaque indice dépend uniquement des indices situés à sa droite, alors remplis un tableau good de droite à gauche. Dans le premier exemple, l’indice 5 est bon. L’indice 4 contient 0, donc il ne l’est pas. L’indice 3 atteint uniquement l’indice 4 : il n’est pas bon. L’indice 2 atteint les indices 3, 4 et 5, et 5 est bon, donc 2 est bon. L’indice 1 contient 0 : il n’est pas bon. L’indice 0 atteint 1 et 2, et 2 est bon, donc la réponse est true.

Chaque indice est maintenant évalué une seule fois, mais cette évaluation peut encore parcourir jusqu’à n cases. Dans [9998, 9997, …, 1, 0, 7], chaque indice peut atteindre le 0 et rien au-delà, donc chacun parcourt toute sa plage et n’y trouve aucun indice bon. Cela représente environ 5 × 10^7 vérifications pour 10 000 éléments, et les plus grands tests sont construits comme celui-ci. Le travail augmente avec le carré de la longueur, donc l’exécution dépasse le temps imparti pour ces tests.

Algorithme

Créez un tableau booléen good de longueur n et définissez good[n-1] sur true.
Parcourez i de n-2 à 0.
Parcourez j de i+1 à min(i+nums[i], n-1). Si un good[j] est true, définissez good[i] sur true et arrêtez le parcours.
Retournez 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]

Suivre l’indice le plus éloigné atteignable

Intuition

Regarde les indices que tu peux atteindre, pas les itinéraires. Depuis l’indice i, tu peux atterrir sur n’importe quel indice de i+1 à i+nums[i], sans laisser de trou. Ainsi, dès que l’indice i est atteignable, tous les indices jusqu’à i+nums[i] le sont aussi. Commence avec le seul indice 0 et continue d’ajouter ces intervalles. Chaque nouvel intervalle commence à l’intérieur du bloc que tu as déjà, donc les indices atteignables forment toujours un bloc continu, [0, farthest].

C’est pourquoi un seul nombre suffit. Parcours i de gauche à droite. Tant que i ≤ farthest, l’indice i est atteignable, alors étends farthest à max(farthest, i+nums[i]). Si i dépasse un jour farthest, aucun indice atteignable ne permet d’atteindre i. Le bloc ne peut pas s’étendre au-delà de ce trou, donc aucun indice situé à sa droite n’est atteignable, y compris le dernier indice. Si le parcours arrive à la fin sans rencontrer de trou, le dernier indice est atteignable.

Dans le deuxième exemple, farthest vaut 0, puis 1 après l’indice 0, puis 4 après l’indice 1. Les indices 2, 3 et 4 contiennent 0 et le laissent à 4. L’indice 5 est au-delà de 4, donc la réponse est false. Dans le premier exemple, l’indice 2 porte farthest à 5 et aucun indice ne le dépasse, donc la réponse est true.

Pourquoi est-il sûr de ne conserver que la portée maximale ? Tu ne t’engages jamais à effectuer un saut. Le bloc contient tous les indices qu’un itinéraire quelconque peut atteindre, et chaque point d’arrivée plus proche se trouve à l’intérieur. Ne garder que l’extrémité droite ne fait perdre aucune information.

Algorithme

Définissez farthest = 0.
Pour chaque indice i de gauche à droite : si i > farthest, renvoyez false.
Sinon, définissez farthest = max(farthest, i+nums[i]).
Si la boucle se termine, tous les indices étaient accessibles, alors renvoyez 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

Pièges et cas limites

La plupart des mauvaises réponses viennent du fait qu’on lit nums[i] comme étant le seul saut possible, ou de l’ordre des deux vérifications dans la boucle.

Toujours sauter exactement nums[i] cases ou toujours faire le saut le plus long. Avec [2, 5, 0, 0], le saut complet depuis l’indice 0 atterrit sur un 0, tandis que le saut d’une case jusqu’à l’indice 1 permet d’atteindre la fin.
Renvoyer false dès que tu vois un 0. Un 0 n’a d’importance que si aucun saut précédent ne le dépasse : [2, 0, 1] saute par-dessus le 0 et la réponse est true.
Mettre à jour farthest avant de vérifier i > farthest. Un indice que tu ne peux pas atteindre ne doit pas étendre la portée ; vérifie donc d’abord, puis mets à jour.
Considérer un tableau à un seul élément comme un échec. Tu te trouves déjà sur le dernier indice, donc la réponse est true, même si cet élément vaut 0.
Utiliser la récursivité sur de longs tableaux. Un parcours peut comporter 10,000 sauts, ce qui provoque un dépassement de la pile d’appels dans plusieurs langages. Le parcours unique n’utilise pas la récursivité.

Questions fréquentes4

Quelle est la complexité temporelle de Jump Game ?

Le parcours jusqu'à la portée la plus éloignée visite chaque indice une seule fois, donc sa complexité temporelle est de O(n) et il utilise un espace supplémentaire de O(1). L'approche par tableau est en O(n²) dans le pire des cas, et essayer tous les itinéraires a une complexité exponentielle.

Pourquoi l’approche gloutonne fonctionne-t-elle pour Jump Game ?

Comme les sauts plus courts sont autorisés, atteindre l’indice i signifie que tu peux atteindre tous les indices jusqu’à i+nums[i]. Ces segments chevauchent toujours la partie déjà atteinte, de sorte que les indices accessibles forment un seul bloc commençant à 0. Le passage glouton suit uniquement l’extrémité droite de ce bloc, qui décrit le bloc entier, et n’écarte donc jamais un chemin qui aurait pu fonctionner.

Le problème Jump Game relève-t-il de la programmation dynamique ?

On peut résoudre ce problème avec la programmation dynamique : marquez chaque indice comme étant bon si l’un de ses points d’atterrissage est bon, en remplissant le tableau de droite à gauche. Cela coûte O(n²). Remarquez que seul l’indice bon le plus à gauche compte, car tout indice qui atteint un indice bon atteint aussi celui le plus à gauche. Ne conservez que cet indice, goal, et déplacez-le vers i chaque fois que i+nums[i] ≥ goal. La réponse consiste à déterminer si goal finit à 0 ; c’est un parcours en O(n) qui reproduit la stratégie gloutonne.

Comment trouver le nombre minimum de sauts ?

Utilisez la même idée de portée maximale, par couches. Gardez en mémoire la fin du bloc que vous pouvez atteindre avec le nombre actuel de sauts et l’indice le plus éloigné que le prochain saut peut atteindre. Lorsque i dépasse la fin du bloc actuel, vous avez besoin d’un saut supplémentaire, et le bloc suivant se termine à cet indice le plus éloigné. Il s’agit toujours d’un seul parcours en O(n).

Python

def canJump(nums):
    # Écrivez le code ici

Cas de test

Cas 1

Cas 2

Cas 3

Entrée

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

Attendu

true

Jump Game

Fonction

Contraintes

Exemples

Indices

Solution

Essaie chaque saut

N’oubliez pas quels indices peuvent terminer

Suivre l’indice le plus éloigné atteignable

Pièges et cas limites

Questions fréquentes4

Problèmes similaires