Jump Game

+10

Ti trovi all'indice 0 dell'array nums. Dall'indice i puoi saltare in avanti di un numero di passi compreso tra 1 e nums[i], quindi nums[i] è il salto più lungo che puoi fare da lì e uno 0 significa che non puoi muoverti. Restituisci true se una sequenza di salti permette di raggiungere l'ultimo indice, e false altrimenti.

Funzione

canJump(nums: integer-array) → boolean

numsinteger-array: il salto più lungo che puoi fare da ciascun indice
Restituisceboolean: true se puoi arrivare all'ultimo indice partendo dall'indice 0, altrimenti false

Vincoli

1 ≤ nums.length ≤ 10⁴
0 ≤ nums[i] ≤ 10⁵
Un salto può essere più corto di nums[i], quindi un salto lungo non ti costringe mai a superare l'ultimo indice.

Esempi

Input: nums = [2, 0, 3, 1, 0, 2]
Output: true
Spiegazione: Dall'indice 0 puoi raggiungere l'indice 1 o 2. L'indice 1 contiene 0 ed è un vicolo cieco, ma l'indice 2 contiene 3 e raggiunge l'indice 5, l'ultimo indice.

+18 test nascosti all’invio

Per approfondire

Conta le diverse sequenze di salti che arrivano all'ultimo indice, modulo 10^9+7, sempre in tempo O(n).

Suggerimenti

Aprili uno alla volta. Ognuno rivela un po’ di più.

0 di 3 aperti

Soluzione

Il numero di percorsi possibili cresce in modo esponenziale, quindi controllare i percorsi uno per uno non può funzionare con array lunghi. Il fatto fondamentale è che gli indici che puoi raggiungere formano sempre un unico blocco continuo che inizia dall'indice 0. Un solo numero, l'estremo destro di quel blocco, contiene tutto ciò che ti serve, e un'unica scansione determina la risposta.

Prova ogni salto

Corretto, ma non termina sui test più grandi

Intuizione

L'idea più diretta è simulare il percorso. Posizionati all'indice 0 e prova, uno alla volta, ogni punto di arrivo consentito dal salto. Ripeti lo stesso procedimento da ogni punto di arrivo. Se un ramo raggiunge l'ultimo indice, la risposta è true. Se ogni ramo finisce in un vicolo cieco, è false.

Nel primo esempio, l'indice 0 contiene 2, quindi provi l'indice 1 e l'indice 2. L'indice 1 contiene 0, un vicolo cieco, quindi torni indietro e provi l'indice 2. L'indice 2 contiene 3 e raggiunge l'indice 5, l'ultimo indice, e la ricerca si conclude con true.

La ricerca è corretta perché esamina ogni percorso. Questo è anche il suo problema: non memorizza mai un indice già esplorato, quindi esplora di nuovo lo stesso indice per ogni percorso che lo raggiunge. Quando la risposta è false, deve escludere ogni percorso. In [4, 3, 2, 1, 0, 5] ogni indice prima dello 0 può raggiungere lo 0, generando 8 percorsi diversi che lo raggiungono. Con 30 indici di questo tipo ci sono più di 500 milioni di percorsi, e i test più grandi hanno 10.000 elementi. Un percorso così lungo causa anche l'overflow dello stack delle chiamate in alcuni linguaggi: Python si ferma a 1.000 chiamate annidate per impostazione predefinita.

Algoritmo

Scrivi una funzione di supporto reach(i) che risponda alla domanda: puoi arrivare dall'indice i all'ultimo indice?
Se i è l'ultimo indice, restituisci true.
Altrimenti prova ogni punto di atterraggio next da i+1 a min(i+nums[i], n-1) e restituisci true non appena lo fa reach(next).
Se nessun punto di atterraggio funziona, restituisci false.
La risposta è 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)

Ricorda quali indici possono terminare

Corretto, ma non termina sui test più grandi

Intuizione

La ricerca qui sopra pone ripetutamente la stessa domanda: «l’indice j può arrivare alla fine?». La risposta per j non cambia mai, quindi calcolala una volta e memorizzala. Chiama buono un indice se da lì puoi raggiungere l’ultimo indice. L’ultimo indice è buono. Qualsiasi altro indice i è buono se almeno uno degli indici su cui può arrivare, da i+1 a i+nums[i], è buono.

Ogni indice dipende solo dagli indici alla sua destra, quindi riempi una tabella good da destra verso sinistra. Nel primo esempio, l’indice 5 è buono. L’indice 4 contiene 0, quindi non è buono. L’indice 3 raggiunge solo l’indice 4: non è buono. L’indice 2 raggiunge gli indici 3, 4 e 5, e 5 è buono, quindi 2 è buono. L’indice 1 contiene 0: non è buono. L’indice 0 raggiunge 1 e 2, e 2 è buono, quindi la risposta è true.

Ora ogni indice viene deciso una sola volta, ma per deciderlo si possono comunque scandire fino a n celle. In [9998, 9997, …, 1, 0, 7] ogni indice può raggiungere lo 0 e niente oltre, quindi ciascuno scandisce tutto il suo intervallo senza trovare nulla di buono. Sono circa 5 × 10^7 controlli per 10.000 elementi, e i test più grandi sono costruiti proprio così. Il lavoro cresce con il quadrato della lunghezza, quindi l’esecuzione va fuori tempo su questi test.

Algoritmo

Crea un array booleano good di lunghezza n e imposta good[n-1] su true.
Scorri i da n-2 fino a 0.
Esamina j da i+1 a min(i+nums[i], n-1). Se un qualsiasi good[j] è true, imposta good[i] su true e interrompi la scansione.
Restituisci 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]

Individua l’indice più lontano raggiungibile

Intuizione

Guarda gli indici che puoi raggiungere, non i percorsi. Dall'indice i puoi atterrare su qualsiasi indice da i+1 a i+nums[i], senza salti. Quindi, una volta raggiunto l'indice i, sono raggiungibili anche tutti gli indici fino a i+nums[i]. Parti dal solo indice 0 e continua ad aggiungere queste estensioni. Ogni nuova estensione inizia all'interno del blocco che hai già, quindi gli indici raggiungibili formano sempre un unico blocco continuo, [0, farthest].

Ecco perché basta un solo numero. Scorri i da sinistra a destra. Finché i ≤ farthest, l'indice i è raggiungibile, quindi estendi farthest a max(farthest, i+nums[i]). Se i supera mai farthest, nessun indice raggiungibile può saltare fino a i. Il blocco non può crescere oltre quel divario, quindi non è raggiungibile nulla alla sua destra, incluso l'ultimo indice. Se la scansione arriva alla fine senza incontrare divari, l'ultimo indice è raggiungibile.

Nel secondo esempio, farthest è 0, poi diventa 1 dopo l'indice 0 e poi 4 dopo l'indice 1. Gli indici 2, 3 e 4 contengono 0 e lo lasciano a 4. L'indice 5 supera 4, quindi la risposta è false. Nel primo esempio, l'indice 2 porta farthest a 5 e nessun indice lo supera, quindi la risposta è true.

Perché è sicuro tenere solo la portata massima? Non ti impegni mai a fare un salto. Il blocco contiene tutti gli indici che qualsiasi percorso può raggiungere, e ogni punto di arrivo più vicino si trova al suo interno. Scartare tutto tranne l'estremo destro non fa perdere informazioni.

Algoritmo

Imposta farthest = 0.
Per ogni indice i da sinistra a destra: se i > farthest, restituisci false.
Altrimenti imposta farthest = max(farthest, i+nums[i]).
Se il ciclo termina, ogni indice era raggiungibile, quindi restituisci 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

Trappole e casi limite

La maggior parte delle risposte errate dipende dal leggere nums[i] come l’unico salto possibile o dall’ordine dei due controlli all’interno del ciclo.

Saltare sempre esattamente nums[i] posizioni oppure scegliere sempre il salto più lungo. Con [2, 5, 0, 0], il salto completo dall’indice 0 atterra su uno 0, mentre il salto di 1 posizione fino all’indice 1 raggiunge la fine.
Restituire false appena vedi uno 0. Uno 0 è importante solo se nessun salto precedente lo supera: [2, 0, 1] salta oltre lo 0 e la risposta è true.
Aggiornare farthest prima di controllare i > farthest. Un indice che non puoi raggiungere non deve estendere l’intervallo, quindi controlla prima e poi aggiorna.
Considerare un array con un solo elemento come un fallimento. Sei già sull’ultimo indice, quindi la risposta è true, anche quando quell’elemento è 0.
Usare la ricorsione su array lunghi. Un percorso può essere lungo 10.000 salti, causando l’overflow dello stack delle chiamate in diversi linguaggi. Il singolo passaggio non usa la ricorsione.

Domande frequenti4

Qual è la complessità temporale di Jump Game?

La passata con portata massima visita ogni indice una volta, quindi ha una complessità temporale di O(n) e usa uno spazio aggiuntivo di O(1). L’approccio con la tabella ha una complessità di O(n²) nel caso peggiore, mentre provare ogni percorso ha una complessità esponenziale.

Perché l’approccio greedy funziona per Jump Game?

Poiché sono consentiti salti più brevi, raggiungere l’indice i significa che puoi raggiungere ogni indice fino a i+nums[i]. Questi tratti si sovrappongono sempre alla parte già raggiunta, quindi gli indici raggiungibili formano un unico blocco che inizia da 0. Il passaggio greedy tiene traccia solo dell’estremità destra del blocco, che descrive l’intero blocco, perciò non scarta mai un percorso che avrebbe potuto funzionare.

Jump Game è un problema di programmazione dinamica?

Si può risolvere con la programmazione dinamica: contrassegna ogni indice come buono quando una delle posizioni in cui si può atterrare è buona, riempiendo la tabella da destra a sinistra. Il costo è O(n²). Nota che conta solo l’indice buono più a sinistra, poiché qualsiasi indice che raggiunge un indice buono raggiunge anche quello più a sinistra. Mantieni solo quell’indice, goal, e spostalo su i ogni volta che i+nums[i] ≥ goal. La risposta è se goal termina in 0: una passata O(n) che rispecchia quella greedy.

Come trovi il numero minimo di salti?

Usa la stessa idea della massima distanza raggiungibile a livelli. Tieni traccia della fine del blocco che puoi raggiungere con il numero attuale di salti e dell’indice più lontano che il salto successivo può raggiungere. Quando i supera la fine del blocco attuale, ti serve un altro salto e il blocco successivo termina all’indice più lontano raggiungibile. È comunque un’unica passata O(n).

Python

def canJump(nums):
    # Scrivi il codice qui

Casi di test

Caso 1

Caso 2

Caso 3

Input

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

Atteso

true

Jump Game

Funzione

Vincoli

Esempi

Suggerimenti

Soluzione

Prova ogni salto

Ricorda quali indici possono terminare

Individua l’indice più lontano raggiungibile

Trappole e casi limite

Domande frequenti4

Problemi simili