Disporre una determinata stringa a forma di Z dall'alto verso il basso e da sinistra a destra in base al numero di righe specificato. Successivamente, l'output deve essere letto riga per riga da sinistra a destra per generare una nuova stringa.

Scorri su ss da sinistra a destra, aggiungendo ogni carattere alla riga appropriata. La riga appropriata può essere tracciata utilizzando la riga corrente e le variabili di direzione corrente. La direzione corrente cambierà solo quando ci spostiamo verso l'alto o verso il basso verso la riga inferiore.

soluzione di classe { public String convert(String s, int numRighe) { if (numRighe == 1) restituisce s; List<StringBuilder> rows = new ArrayList<>(); //Memorizza i caratteri di ogni riga dopo la trasformazione for (int i = 0; i < Math.min(numRighe, s.lunghezza()); i ) righe.add(nuovo StringBuilder()); int curRow = 0; booleano goingDown = false; for (char c : s.toCharArray()) { //Attraversa s direttamente, convertilo in un array di caratteri e assegnalo a c uno per uno righe.get(curRow).append(c); if (curRow == 0 || curRow == numRows - 1) goingDown = !goingDown; curRow = andandoGiù 1: -1; } StringBuilder ret = new StringBuilder(); for (StringBuilder riga: righe) ret.append(riga); return ret.toString(); } }

Tempo O(n), dove n=len(s), spazio O(n)

L'importazione si trova all'inizio del file, dopo il commento del file. L'importazione è solitamente un'importazione a riga singola o da ... importa

1. Importazione della libreria standard 2. Importazioni rilevanti da terzi 3. Importazioni di applicazioni/librerie locali specifiche Inserire una riga vuota tra ciascun gruppo di importazione. Le importazioni assolute sono consigliate perché sono più leggibili; è possibile utilizzare importazioni relative esplicite invece di importazioni assolute quando si ha a che fare con layout di pacchetti complessi, che sono troppo dettagliati

1.int(x)

2.float(x)

3.str(x)

mappa(valutazione,elenco)

se tipo(n) == tipo(123):

stack.append()

stack.pop()

Non esiste un metodo di visualizzazione nell'elenco. Puoi solo prima visualizzarlo e poi aggiungerlo.

coda.append()

coda.pop(0)

coda.append()

coda.popleft()

Man mano che il livello di sviluppo di tutti migliora e la complessità del programma aumenta, nel programma verranno utilizzati sempre più moduli e librerie di terze parti. Il motivo di questo errore è che la libreria "XX" non è installata, pip install ww

Scarica il pacchetto di installazione di terze parti corrispondente e accedi alla directory di download per installare il nome completo del file scaricato.

Installa Microsoft Visual C 14.0, il blog ha l'indirizzo di download visualcppbuildtools_full

rotella di installazione pip3

Se viene richiesto quale file del modulo presenta un errore, trova questo modulo, eliminalo e sostituiscilo con lo stesso file di un amico che può essere eseguito.

1. Il nome del file è in conflitto con le parole chiave di Python e simili.

2. Due file py si importano a vicenda, provocando l'eliminazione di uno di essi.

Il problema della versione pip 10.0 non ha main(), È necessario eseguire il downgrade della versione: python -m pip install –upgrade pip==9.0.1

Alcune API sono cambiate dopo Pip v10, con conseguente incompatibilità tra la vecchia e la nuova versione, che influisce sulla nostra installazione e aggiornamento dei pacchetti. Basta aggiornare l'IDE e il gioco è fatto! Durante l'aggiornamento, l'IDE ci ha fornito anche suggerimenti amichevoli. PyCharm -> Aiuto -> Controlla aggiornamenti

Non aggiornare la versione crackata, altrimenti le informazioni di attivazione non saranno più valide.

Hai chiamato un file asyncio py Se il controllo non è il primo, devi controllare la tua versione di Python perché Python3.7 e versioni successive supportano solo il metodo run. 1 Aggiorna la versione di Python 2 run viene riscritta come segue loop = asyncio.get_event_loop() risultato = loop.run_until_complete(coro)

Sostituisci i file delle costanti in asyncio

t=('a','b','c') per i nell'intervallo(t):

Tipico problema di errore di tipo. Nel codice precedente, la funzione range() prevede che il parametro in entrata sia un numero intero (intero), ma il parametro in entrata è una tupla (tupla). il numero di tuple può essere di tipo intero len(t) Ad esempio, modificare range(t) nel codice precedente in range(len(t))

Causato dal tentativo di modificare il valore di una stringa, che è un tipo di dati immutabile

s[3] = 'a' diventa s = s[:3] 'a' s[4:]

Causato dal tentativo di concatenare un valore non stringa con una stringa, basta eseguire il cast del valore non stringa in una stringa con str()

Quando si utilizza la funzione set per costruire un insieme, gli elementi nell'elenco di parametri fornito non possono contenere elenchi come parametri.

Quando si passa da python2 a python3, si incontreranno inevitabilmente alcuni problemi. Le stringhe Unicode in python3 sono nel formato predefinito (tipo str) e le stringhe con codifica ASCII (tipo byte) Il tipo bytes contiene valori byte e in realtà non lo è un carattere. String, tipo array di byte python3 e bytearray) deve essere preceduto dall'operatore b o B; in python2 è il contrario, la stringa codificata ASCII è l'impostazione predefinita e la stringa Unicode deve essere preceduta dall'operatore u o U.

import chardet #È necessario importare questo modulo e rilevare il formato di codifica codifica_tipo = chardet.detect(html) html = html.decode(encode_type['encoding']) #Decodifica di conseguenza e assegnalo all'identificatore originale (variabile)

>>> f=aperto ("ciao.py") >>> f.write ("prova")

La causa dell'errore è che il parametro della modalità di lettura-scrittura mode non viene aggiunto ai parametri in entrata di open("hello.py"), il che significa che il modo predefinito per aprire il file è di sola lettura.

La soluzione è cambiare la modalità modalità in modalità scrittura autorizzazione w, f = open("ciao. py", "w ")

Causato dalla dimenticanza di aggiungere i due punti alla fine di istruzioni come if, elif, else, for, while, class e def

Utilizzo errato di "=" invece di "==". Nei programmi Python, "=" è un operatore di assegnazione e "==" è un'operazione di confronto uguale.

Nella maggior parte dei casi ciò accade perché il file non è codificato UTF8 (ad esempio, potrebbe essere codificato GBK) e il sistema utilizza la decodifica UTF8 per impostazione predefinita. La soluzione è passare al metodo di decodifica corrispondente: con open('acl-metadata.txt','rb') come dati:

open(percorso, '-modalità-', codifica='UTF-8') ovvero open(percorso nome file, modalità lettura-scrittura, codifica)

Modalità di lettura e scrittura comunemente utilizzate

Quando si chiama una funzione, non ci sono abbastanza variabili per accettare il valore restituito.

1. Riavvia Pycharm (praticamente inutile)

2. Imposta num_works su 0 (forse inutile)

3. Aumenta la dimensione del file di paging (risolvi completamente il problema)

1. Non solo è in esecuzione un progetto, ma è in esecuzione anche il programma Python di un altro progetto, basta spegnerlo.

2. Il sistema operativo Windows non supporta il funzionamento multiprocesso di Python. La rete neurale utilizza più processi nel caricamento del set di dati, quindi imposta il parametro num_workers in DataLoader su 0.

0. Recentemente, mentre stavo eseguendo un progetto scrapy, il framework scrapy installato ha segnalato improvvisamente un errore e sono stato colto di sorpresa.

1. Poiché non è difficile installare Scrapy in Anaconda, non è così semplice ed efficiente come reinstallarlo per trovare una soluzione.

2. Non riesco a disinstallarlo completamente utilizzando semplicemente il comando conda rimuovi scrapy. Il motivo potrebbe essere che ho installato scrapy due volte utilizzando rispettivamente pip e conda. I lettori possono provare sia i comandi di disinstallazione pip che conda.

pip disinstalla scrapy conda rimuovi lo scrapy

Reinstallare pip install scrapy

Abbiamo modificato solo A.x, perché è stato modificato anche C.x? Nei programmi Python, le variabili di classe vengono trattate internamente come dizionari, che seguono l'ordine di risoluzione del metodo comunemente citato (MRO). Quindi nel codice sopra, poiché l'attributo x nella classe C non viene trovato, cercherà la sua classe base (sebbene Python supporti l'ereditarietà multipla, c'è solo A nell'esempio sopra). In altre parole, la classe C non ha un proprio attributo x, che è indipendente da A. Pertanto, C.x è in realtà un riferimento ad A.x

1. La variabile locale x non ha valore iniziale e la variabile esterna X non può essere introdotta internamente.

Fool non ha assegnato un valore a lst, ma pazzo2 lo ha fatto. Sai, lst = [5] è l'abbreviazione di lst = lst [5] e stiamo cercando di assegnare un valore a lst (Python lo tratta come una variabile locale). Inoltre, la nostra assegnazione a lst è basata su lst stesso (che ancora una volta viene trattato come una variabile locale da Python), ma non è stato ancora definito, quindi si verifica un errore! Quindi qui dobbiamo distinguere tra l’uso di variabili locali e variabili esterne.

0.Chiedi aiuto

0. Cambia la sorgente pip

1. Installare la libreria specificata

2. Installare la versione specificata della libreria specificata

3. Controllare quali librerie sono installate

4. Visualizza le informazioni specifiche della biblioteca

5.Dove è installato pip?

6. Libreria di installazione batch

7. Installare la libreria utilizzando il file wheel

8. Disinstallare la libreria

9.Aggiornamento della libreria

10. Salvare l'elenco delle librerie nel file specificato

11. Controlla le librerie che devono essere aggiornate

12. Verifica eventuali problemi di compatibilità

13. Scarica la libreria in locale

pyinstaller -F nomefile.py

1. Parametri

2. Chiama

3.Metodo

sottoargomento

1. Espressione di più e meno infinito

1. In Python / significa divisione normale con resto, // significa divisione intera senza resto.

2. Non! in Python è rappresentato da not

3.Il quadrato in Python è **

1. È necessario aggiungere i due punti dopo tutte le istruzioni relative alle parole chiave: tranne return

2. Non è necessario aggiungere () alle condizioni nei cicli, nei giudizi e in altre istruzioni simili e non ci sono {} nei blocchi di istruzioni. Utilizzare il rientro per rappresentare rigorosamente il formato.

1. Commento a riga singola n.

2. Commenti su più righe ''' o """

dp = [[float('inf') for _ in range(n)] for _ in range(n)]

linea, = ax.plot(x, np.sin(x))

Commenti a riga singola#

È anche il tasto di scelta rapida per il blocco QQ. Annulla l'impostazione in QQ.

1.Barra di navigazione della barra di navigazione

1.aspetto generale dello stile

2.impostazioni di sistemaimpostazioni di sistema

1. È possibile effettuare la ricerca direttamente in base alla visualizzazione del sistema (nota di commento)

1. Carattere del codice carattere (dimensione regolabile)

2. Combinazione colori dell'area codice combinazione colori

3. Stile codice stile codice

4.Ispezioni

5.Modelli di file e codice Modelli di file e codice

6.Codifica file codifica file

7.Modelli dinamici di Live Templates (facili da usare e padroneggiare)

1.Project Interpret interprete di progetto

1.Archivio

2.Nuovo file Scratch

3.Directory

4.File Python

5. Quando crei un nuovo file HTML, puoi fare clic con il pulsante destro del mouse su di esso e aprirlo in un browser per vedere l'effetto di visualizzazione.

1. È uguale al CMD di sistema. Puoi installare il pacchetto direttamente qui e utilizzare il comando dos.

Puoi scrivere direttamente il codice Python, eseguirlo in modo interattivo e modificarlo riga per riga.

È equivalente a un promemoria. Scrivi TODO ('') nel punto di codice, in modo da poterlo trovare rapidamente e continuare a lavorare. Può essere utilizzato per la cooperazione reciproca.

È possibile regolare la severità del controllo del codice. La modalità di risparmio energetico equivale a posizionare la freccia all'estrema sinistra. Tutti gli errori grammaticali non verranno controllati.

max_v, m_i = float(-inf), 0 #Combina un oggetto dati attraversabile (come una lista, una tupla o una stringa) in una sequenza di indici, Elenca i pedici dei dati e i dati allo stesso tempo for i, v in enumerate(nums): se v > max_v: max_v = v m_i = io

max_v = max(numeri) m_i = numeri.indice(max_v)

1. Finché vedi che l'array fornito nella domanda dell'intervista è un array ordinato, puoi pensare se puoi utilizzare il metodo della dicotomia

2. Gli elementi dell'array sono continui nell'indirizzo di memoria Un elemento dell'array non può essere cancellato singolarmente, ma solo sovrascritto.

for (int i = 0; i < numeri.lunghezza; i ) { for (int j = i 1; j < numeri.lunghezza; j ) {

Quando c'è un vincolo che la testa e la coda non possono essere allo stesso tempo, scomponi la matrice circolare in diversi problemi di matrice ordinaria e trova il valore massimo

1. Sinistra chiusa e destra chiusa [sinistra, destra]

2. Chiudi a sinistra e apri a destra [sinistra, destra)

for (int i = 0; i < numeri.lunghezza; i ) { complemento int = target - nums[i]; if (map.containsKey(complemento) && map.get(complemento) != i)

1. In caso di inversione dell'ordine: l'eventuale carry issue dell'ultima aggiunta deve essere considerata separatamente.

2. In sequenza in avanti: invertire l'elenco collegato/utilizzare la struttura dei dati dello stack per ottenere l'inversione

Supponiamo che l'endpoint sinistro dell'elenco collegato corrente sia a sinistra, l'endpoint destro sia a destra e che la relazione di inclusione sia "chiusa a sinistra, aperta a destra". L'elenco collegato fornito è un elenco collegato unidirezionale. È molto facile accedervi elementi successivi, ma non può accedere direttamente agli elementi precedenti. Pertanto, dopo aver trovato il nodo mediano a metà dell'elenco collegato, se si imposta la relazione "sinistra chiusa, destra aperta", è possibile utilizzare direttamente (sinistra, metà) e (mid.next, destra) per rappresentare la lista corrispondente a i sottoalberi sinistro e destro Non è necessario mid.pre e l'elenco iniziale può anche essere convenientemente rappresentato da (head, null)

Set hash: Set<Carattere> occ = new HashSet<Carattere>();

int somma = riporto x y; int riporto = somma/10;

Per "estrarre" e "spingere" i numeri senza l'aiuto di uno stack/array ausiliario, possiamo usare la matematica, eliminare prima l'ultima cifra, quindi dividere per 10 per rimuovere l'ultima cifra, invertire il numero e continuare a moltiplicarsi dopo 10 , aggiungi l'ultima cifra eliminata e determina prima se andrà in overflow.

Fai un passo a sinistra, poi continua a camminare a destra finché non puoi andare oltre

s = set(ls); lt = lista(i)

lt = tupla(ls)

Se un problema presenta molti sottoproblemi sovrapposti, la programmazione dinamica è la più efficace.

1. Determinare il significato dell'array dp (tabella dp) e degli indici 2. Determinare la formula di ricorsione 3.Come inizializzare l'array dp 4. Determinare l'ordine di attraversamento 5. Derivazione dell'array dp con esempi

Perché determinare prima la formula di ricorsione e poi considerare l'inizializzazione? Perché in alcuni casi la formula ricorsiva determina come inizializzare l'array dp

1. Stampa l'array dp e vedi se viene dedotto secondo le tue idee.

2. Prima di scrivere il codice, assicurati di simulare la situazione specifica del trasferimento di stato sull'array dp e assicurati che il risultato finale sia quello desiderato.

Quando l'equazione ricorsiva è correlata solo a pochi numeri adiacenti, è possibile utilizzare una matrice mobile per ottimizzare la complessità dello spazio su O(1)

Condizione di terminazione della ricorsione, cosa fa questa ricorsione e cosa restituisce

L'indice di un array è un array implicitamente utile, specialmente quando si contano alcuni numeri (trattando il valore dell'array corrispondente come l'indice temp[arr[i]] del nuovo array) o per determinare se compaiono alcuni numeri interi

1. Quando ti forniamo una stringa di lettere e ti chiediamo di determinare il numero di volte in cui queste lettere appaiono, possiamo usare queste lettere come pedici Durante l'attraversamento, se la lettera a viene attraversata, allora arr[a] può essere aumentata di 1. Cioè, arr[a]. Grazie a questo uso intelligente dei pedici, non abbiamo bisogno di giudicare lettera per lettera.

2. Ti vengono forniti n array di numeri interi non ordinati arr e l'intervallo di valori di questi numeri interi è compreso tra 0 e 20. È necessario ordinare questi n numeri da piccolo a grande con complessità temporale O(n). ordine e utilizzare il valore corrispondente come indice dell'array. Se questo numero è apparso in precedenza, aggiungere 1 all'array corrispondente.

Quando si attraversa l'array, verrà eseguita una valutazione di fuori limite. Se il pedice è quasi fuori limite, lo imposteremo su 0 e lo attraverseremo nuovamente. Soprattutto in alcuni array ad anello, come le code implementate con array pos = (pos 1) % N

Per i puntatori doppi è particolarmente utile quando si pongono domande su elenchi collegati singolarmente.

1. Determina se una lista concatenata singolarmente ha un ciclo

2. Come trovare il nodo centrale dell'elenco collegato in un attraversamento

3. Il nodo k-esimo dall'ultimo in un elenco collegato singolarmente

sottoargomento

1. A volte quando eseguiamo operazioni di divisione o moltiplicazione, come n/2, n/4, n/8, possiamo utilizzare il metodo di spostamento per eseguire l'operazione. Attraverso l'operazione di spostamento, la velocità di esecuzione sarà più veloce

2. Esistono anche alcune operazioni come & (e) e | (o), che possono anche velocizzare l'operazione.

1. Per determinare se un numero è dispari, sarà molto più veloce utilizzare l'operazione AND.

1. Nelle questioni correlate alle liste collegate, spesso impostiamo un puntatore head e questo puntatore head non memorizza alcun dato valido. Solo per comodità di funzionamento, possiamo chiamare questo puntatore head bit sentinella.

2. Quando si utilizza un array, è anche possibile impostare una sentinella, utilizzando arr[0] come sentinella.

1. Quando vogliamo eliminare il primo nodo, se non è impostato un bit sentinella, l'operazione sarà diversa dall'operazione di eliminazione del secondo nodo. Ma abbiamo predisposto una sentinella, quindi eliminare il primo nodo ed eliminare il secondo nodo sono gli stessi nel funzionamento, senza esprimere giudizi aggiuntivi. Naturalmente lo stesso vale quando si inseriscono i nodi

2. Quando vuoi giudicare se due elementi adiacenti sono uguali, impostare una sentinella non ti preoccuperà dei problemi transfrontalieri puoi direttamente arr[i] == arr[i-1]. Non aver paura di oltrepassare il confine quando i = 0

1. Quando utilizziamo la ricorsione per risolvere un problema, è facile calcolare ripetutamente lo stesso sottoproblema. In questo momento dobbiamo considerare la conservazione dello stato per evitare calcoli ripetuti.

2.Esempi

1. Per i problemi ricorsivi, di solito si procede dall'alto verso il basso finché la ricorsione non raggiunge il fondo, quindi si restituisce il valore strato per strato.

2. Tuttavia, a volte quando n è relativamente grande, come quando n = 10000, è necessario eseguire la ricorsione verso il basso di 10000 livelli fino a n <= 2 prima di restituire lentamente il risultato. Se n è troppo grande, lo spazio dello stack potrebbe non esserlo Abbastanza

3. Per questa situazione, possiamo effettivamente considerare un approccio dal basso verso l'alto.

4. Questo approccio dal basso verso l'alto è anche chiamato ricorsione

In Python, i parametri possono restituire direttamente parte dell'array nums[:i]. Non è necessario riprogettare un metodo per intercettare l'array in base al pedice come in Java.

for i, v in enumerate(nums):

Uno stack in cui gli elementi nello stack aumentano o diminuiscono in modo monotono. Uno stack monotono può essere utilizzato solo nella parte superiore dello stack.

1. Gli elementi nello stack monotono sono monotoni.

2. Prima che gli elementi vengano aggiunti allo stack, tutti gli elementi che distruggono la monotonia dello stack verranno eliminati dalla cima dello stack.

3. Usa lo stack monotono per trovare l'elemento e attraversa a sinistra fino al primo elemento che è più piccolo di esso (stack incrementale)/trova l'elemento e attraversa a sinistra fino al primo elemento che è più grande di esso.

1. Le chiavi di tutti i nodi del sottoalbero sinistro sono inferiori al nodo radice

2. Le parole chiave di tutti i nodi del sottoalbero destro sono maggiori del nodo radice

3. I sottoalberi sinistro e destro sono ciascuno un albero di ordinamento binario.

L'attraversamento in ordine può ottenere una sequenza ordinata crescente

1. Albero binario bilanciato: il valore assoluto della differenza di altezza tra i sottoalberi sinistro e destro di qualsiasi nodo non supera 1

2. Fattore di equilibrio: la differenza di altezza tra i sottoalberi sinistro e destro del nodo -1,0,1

Ogni albero che consiste solo degli archi di G e contiene tutti i vertici di G è chiamato albero di copertura di G.

Insieme di punti: c'è un bordo che collega due punti qualsiasi.

Insieme di punti: tra due punti qualsiasi non esiste alcun bordo

Un grafo non orientato va da un punto iniziale specificato a un punto finale specificato, passando per tutti gli altri nodi una sola volta. Un percorso hamiltoniano chiuso è chiamato ciclo hamiltoniano, mentre un percorso contenente tutti i vertici del grafico è chiamato percorso hamiltoniano.

Un algoritmo di attraversamento gerarchico simile a un albero binario, che dà priorità al primo nodo scoperto.

Similmente all'attraversamento preordinato di un albero, viene data priorità all'ultimo nodo scoperto.

1. Le due strutture dati "queue" e "stack" possono essere implementate utilizzando elenchi concatenati o array. Se lo implementi con un array, devi affrontare il problema dell'espansione e della contrazione; se lo implementi con una lista concatenata, non hai questo problema, ma hai bisogno di più spazio di memoria per memorizzare i puntatori dei nodi.

2. Due metodi di rappresentazione del "grafico", l'elenco di adiacenza è un elenco collegato e la matrice di adiacenza è un array bidimensionale. La matrice di adiacenza determina rapidamente la connettività e può eseguire operazioni sulla matrice per risolvere alcuni problemi, ma richiede molto spazio se il grafico è scarso. Le liste di adiacenza risparmiano spazio, ma molte operazioni non sono sicuramente efficienti quanto le matrici di adiacenza.

3. La "tabella hash" mappa le chiavi su un array di grandi dimensioni tramite una funzione hash. E come metodo per risolvere i conflitti di hash, il metodo zip richiede caratteristiche di elenco concatenato, che è semplice da utilizzare, ma richiede spazio aggiuntivo per memorizzare i puntatori; il metodo di sondaggio lineare richiede caratteristiche di array per facilitare l'indirizzamento continuo e non richiede spazio di archiviazione per i puntatori , ma l'operazione è un po' complicata

4. L'"albero", implementato con un array, è un "heap", poiché l'"heap" è un albero binario completo. L'utilizzo di un array per l'archiviazione non richiede puntatori ai nodi e l'operazione è relativamente semplice utilizzando un elenco collegato implementarlo è un "albero" molto comune, perché non è necessariamente un albero binario completo, quindi non è adatto per l'archiviazione di array. Per questo motivo, sono stati derivati ​​vari progetti ingegnosi basati su questa struttura ad "albero" di elenchi concatenati, come alberi di ricerca binari, alberi AVL, alberi rosso-neri, alberi a intervalli, alberi B, ecc., per affrontare diversi problemi.

1. Poiché gli array sono compatti e di archiviazione continua, è possibile accedervi in ​​modo casuale, gli elementi corrispondenti possono essere trovati rapidamente tramite gli indici e lo spazio di archiviazione viene relativamente risparmiato. Ma a causa della memorizzazione continua, lo spazio di memoria deve essere allocato in una sola volta. Pertanto, se l'array vuole espandersi, deve riallocare uno spazio più grande e quindi copiare lì tutti i dati se si desidera Durante l'inserimento e l'eliminazione al centro dell'array, tutti i dati successivi devono essere spostati ogni volta per mantenere la continuità. La complessità temporale è O(N).

2. Poiché gli elementi di un elenco collegato non sono continui, ma si basano su puntatori per puntare alla posizione dell'elemento successivo, non vi è alcun problema di espansione dell'array se si conosce il predecessore e il successore di un determinato elemento, è possibile eliminarlo l'elemento o inserire un nuovo elemento utilizzando il puntatore Complessità temporale O(1). Tuttavia, poiché lo spazio di archiviazione non è continuo, non è possibile calcolare l'indirizzo dell'elemento corrispondente in base a un indice, quindi l'accesso casuale non è possibile e poiché ciascun elemento deve memorizzare un puntatore alla posizione dell'elemento precedente e precedente, esso consumerà relativamente più spazio di archiviazione.

1.Array

2. Elenco collegato

3. Albero binario

4.Albero N-ario

attraversamento vuoto(radice TreeNode) { // Attraversamento del preordine traversa(root.left) // Attraversamento in ordine traversa(root.right) // Attraversamento postordine }

La forma generale del problema di programmazione dinamica consiste nel trovare il valore ottimale. La programmazione dinamica è in realtà un metodo di ottimizzazione nella ricerca operativa, ma è più comunemente utilizzata nei problemi informatici. Ad esempio, ti chiede di trovare la sottosequenza crescente più lunga e la distanza di modifica minima.

Il problema principale è l’esaurimento. Poiché richiediamo il valore migliore, dobbiamo enumerare in modo esaustivo tutte le possibili risposte e quindi trovare tra queste il valore migliore.

1. Sottoproblemi sovrapposti

2. Sottostruttura ottimale

3. Equazione di transizione di stato

1.Codice

2. Albero ricorsivo

3. Complessità temporale di algoritmi ricorsivi

1. Poiché il motivo che richiede tempo sono i calcoli ripetuti, possiamo creare un "memo". Non tornare indietro dopo aver calcolato la risposta a una determinata sotto-domanda, annotarla nel "memo" prima di tornare ogni volta incontri una sotto-domanda, controlla prima il problema in "Memo". Se trovi che il problema è stato risolto in precedenza, prendi semplicemente la risposta e usala invece di perdere tempo a fare calcoli.

2. Generalmente, come "memo" viene utilizzato un array. Naturalmente è anche possibile utilizzare una tabella hash (dizionario).

3.Codice

4. Albero ricorsivo

5. Complessità

6.Confronto con la programmazione dinamica

7. Dall'alto verso il basso

8. Dal basso verso l'alto

1. Pensieri

2.Codice

3. Equazione di transizione di stato

4. Compressione dello stato

Ti vengono date k monete con valore nominale di c1, c2...ck. La quantità di ciascuna moneta è illimitata. Quindi ti viene data una somma totale di denaro. Ti chiedo quante monete ti servono almeno per recuperare tale importo. Se è impossibile recuperare l'importo, l'algoritmo restituisce -1

1. Innanzitutto, questo problema è un problema di programmazione dinamica perché ha una "sottostruttura ottimale". Per rispettare la "sottostruttura ottimale", i sottoproblemi devono essere indipendenti l'uno dall'altro.

2. Tornando al problema della riscossione del resto, perché si dice che sia in linea con la sottostruttura ottimale? Ad esempio, se vuoi trovare il numero minimo di monete quando importo = 11 (domanda originale), se conosci il numero minimo di monete quando importo = 10 (sottodomanda), devi solo aggiungere uno alla risposta a la sotto-domanda (scegli un'altra moneta da 1 valore nominale) è la risposta alla domanda originale. Poiché il numero di monete è illimitato, non esiste alcun controllo reciproco tra i sottoproblemi ed essi sono indipendenti l’uno dall’altro.

3. Quattro passi principali

4. Pseudocodice

5.Codice

6.Equazione di transizione di stato

7. Albero ricorsivo

8. Complessità

1.Codice

2. Complessità

1.Definizione di array dp

2.Codice

3. Processo

4.Dettagli

Simile all'iterazione dell'attraversamento in ordine, con lievi modifiche

soluzione di classe { public List<Integer> preorderTraversal(TreeNode root) { List<Integer> res = new ArrayList<Integer>(); //Stack è implementato in base a array dinamici, mentre LinkedList è implementato in base a elenchi collegati bidirezionali è più efficiente nell'aggiunta, eliminazione e modifica rispetto a Stack Deque<TreeNode> stk = new LinkedList<TreeNode>();//Coda a doppia estremità //Il nodo non è vuoto o lo stack non è vuoto e il ciclo continua while (root!= null || !stk.isEmpty()) { mentre (radice!= null) { res.add(root.val);//Si accede direttamente al nodo root e quindi lo si inserisce nello stack stk.push(root); root = root.left;//Dopo che il nodo radice termina, accedi al suo figlio sinistro e diventa il nuovo nodo radice } root = stk.pop();//Quando si salta fuori dal ciclo, è stato effettuato l'accesso a tutti i figli di sinistra, quindi si accede al figlio di destra radice = radice.destra; } restituire ris; } }

Soluzione di classe: def preorderTraversal(self, root: TreeNode) -> List[int]: res = lista() se non root: ritorno ris pila = [] nodo=radice while stack o nodo:#Il nodo non è vuoto oppure lo stack non è vuoto e il ciclo continua mentre nodo: res.append(node.val) #Si accede direttamente al nodo radice e quindi lo si inserisce nello stack stack.append(nodo) node = node.left #Dopo che il nodo radice termina, accedi al suo figlio sinistro e diventa il nuovo nodo radice node = stack.pop() #Quando si esce dal ciclo, è stato effettuato l'accesso a tutti i figli di sinistra, quindi si accede al figlio di destra nodo = nodo.destra ritorno ris

Partendo dal nodo radice, ogni iterazione estrae l'elemento superiore dello stack corrente e spinge il suo nodo figlio nello stack, premendo prima il figlio destro e poi il figlio sinistro.

soluzione di classe { public List<Integer> preorderTraversal(TreeNode root) { Stack LinkedList<TreeNode> = new LinkedList<>(); LinkedList<Integer> output = nuova LinkedList<>(); se (radice == null) { uscita di ritorno; } stack.add(root); while (!stack.isEmpty()) { TreeNode node = stack.pollLast();//Recupera e rimuove l'ultimo elemento di questo elenco output.add(nodo.val); if (node.right!= null) {//Spingi nello stack solo un figlio destro e uno sinistro del nodo corrente, indipendentemente dagli altri stack.add(nodo.destra); } if (nodo.sinistra!= null) { stack.add(nodo.sinistra); } } uscita di ritorno; } }

Tempo: O(n), Spazio: O(n)

1. Accedi ai nodi predecessori dell'attraversamento del preordine dal nodo corrente verso il basso e ciascun nodo predecessore viene visitato esattamente due volte.

2. Per prima cosa inizia dal nodo corrente, fai un passo verso il figlio sinistro e poi visita tutto il basso lungo il figlio destro fino a raggiungere un nodo foglia (il nodo predecessore trasversale in ordine del nodo corrente), quindi aggiorniamo il output e crea un predecessore pseudo edge right = root aggiorna il punto successivo di questo predecessore. Se visitiamo il nodo precedente per la seconda volta, poiché punta già al nodo corrente, rimuoviamo lo pseudo spigolo e passiamo al vertice successivo

3. Se il movimento a sinistra nel primo passaggio non esiste, aggiorna direttamente l'output e spostati a destra

soluzione di classe { public List<Integer> preorderTraversal(TreeNode root) { List<Integer> res = new ArrayList<Integer>(); TreeNode predecessor = null;//Il nodo predecessore del nodo corrente, il nodo più a destra del sottoalbero sinistro mentre (radice!= null) { //A seconda che sia presente un figlio sinistro, determina se trovare il nodo predecessore o accedere direttamente al figlio destro se (root.sinistra!= null) { //Trova prima il predecessore, quindi assegna un valore al figlio destro e quindi attraversa il figlio sinistro del nodo corrente //Il nodo predecessore è il nodo radice corrente, fai un passo a sinistra e poi continua a camminare a destra finché non può più andare. predecessore = root.sinistra; while (predecessore.destra!= null && predecessore.destra!= root) { predecessore = predecessore.destra; } //A seconda che il figlio destro del predecessore sia vuoto, determina se accedere direttamente al sottoalbero sinistro e quindi assegnare il valore, oppure se l'accesso al sottoalbero sinistro è completato. //Lascia che il puntatore destro del predecessore punti alla radice e continui ad attraversare il sottoalbero sinistro if (predecessore.destra == null) { res.add(root.val); predecessore.destra = radice; radice = radice.sinistra; } //Indica che il sottoalbero sinistro è stato visitato. Dobbiamo disconnettere il collegamento e continuare a visitare il sottoalbero destro. altro { predecessore.destra = null; radice = radice.destra; } } // Se non è presente il figlio sinistro, accede direttamente al figlio destro altro { res.add(root.val); radice = radice.destra; } } restituire ris; } }

Soluzione di classe: def preorderTraversal(self, root: TreeNode) -> List[int]: res = lista() se non root: ritorno ris p1 = radice mentre p1: p2 = p1.left #Il nodo predecessore del nodo corrente, il nodo più a destra del sottoalbero sinistro if p2: #A seconda se c'è un figlio sinistro, determina se trovare il suo nodo predecessore o accedere direttamente al figlio destro mentre p2.right e p2.right != p1: p2 = p2.destra #A seconda che il figlio destro di p2 sia vuoto, determinare se accedere direttamente al sottoalbero sinistro e quindi assegnare il valore, oppure se l'accesso al sottoalbero sinistro è completato. if not p2.right:#Lascia che il puntatore destro di p2 punti a p1 e continua ad attraversare il sottoalbero sinistro res.append(p1.val) p2.destra = p1 p1 = p1.sinistra Continua else: #Indica che il sottoalbero di sinistra è stato visitato, dobbiamo disconnettere il collegamento e continuare a visitare il sottoalbero di destra p2.right = Nessuno else: #Se non c'è il figlio sinistro, accedi direttamente al figlio destro res.append(p1.val) p1 = p1.destra ritorno ris

Tempo: O(n), Spazio: O(1)

Questo albero viene attraversato visitando il sottoalbero sinistro - nodo radice - sottoalbero destro e quando visitiamo il sottoalbero sinistro o il sottoalbero destro, attraversiamo allo stesso modo finché non viene attraversato l'albero completo. Pertanto, l'intero processo di attraversamento è naturalmente ricorsivo. Possiamo utilizzare direttamente funzioni ricorsive per simulare questo processo.

soluzione di classe { public List<Integer> inorderTraversal(TreeNode root) { List<Integer> res = new ArrayList<Integer>(); ordine(root, res); restituire ris; } public void inorder(TreeNode root, List<Integer> res) { se (radice == null) { ritorno; } inorder(root.left, res); res.add(root.val); inorder(root.right, res); } }

Soluzione di classe: def preorderTraversal(self, root: TreeNode) -> List[int]: def dfs(cur): se non cur: ritorno # Ricorsione di preordine res.append(cur.val) dfs(cur.sinistra) dfs(cur.destra) # # Ricorsione in ordine #dfs(cur.sinistra) # res.append(cur.val) #dfs(cur.destra) # # Ricorsione postordine #dfs(cur.sinistra) #dfs(cur.destra) # res.append(cur.val) ris = [] dfs(radice) ritorno ris

Complessità temporale: O(n), dove n è il numero di nodi dell'albero binario. Nell'attraversamento dell'albero binario, ciascun nodo verrà visitato una e una sola volta.

Complessità spaziale: O(n). La complessità dello spazio dipende dalla profondità dello stack della ricorsione e la profondità dello stack raggiungerà il livello O(n) quando l'albero binario è una catena.

Possiamo anche implementare la funzione ricorsiva del metodo 1 in modo iterativo. La differenza è che uno stack viene mantenuto implicitamente durante la ricorsione e dobbiamo simulare esplicitamente questo stack durante l'iterazione.

soluzione di classe { public List<Integer> inorderTraversal(TreeNode root) { List<Integer> res = new ArrayList<Integer>(); //Stack è implementato in base a array dinamici, mentre LinkedList è implementato in base a elenchi collegati bidirezionali è più efficiente nell'aggiunta, eliminazione e modifica rispetto a Stack Deque<TreeNode> stk = new LinkedList<TreeNode>();//Coda a doppia estremità //Il nodo non è vuoto o lo stack non è vuoto e il ciclo continua while (root!= null || !stk.isEmpty()) { // Attraversa prima il figlio sinistro finché il figlio sinistro non è vuoto e termina il ciclo mentre (radice!= null) { stk.push(root); radice = radice.sinistra; } //Quando si esce dal ciclo, il figlio sinistro è vuoto. In questo momento, quello uscito dallo stack è equivalente al nodo radice, quindi tocca al figlio destro. root = stk.pop(); res.add(root.val); radice = radice.destra; } restituire ris; } }

Soluzione di classe: def inorderTraversal(self, root: TreeNode) -> Lista[int]: res = lista() se non root: ritorno ris pila = [] nodo=radice while stack o nodo:#Il nodo non è vuoto oppure lo stack non è vuoto e il ciclo continua mentre nodo: stack.append(node) #Attraversa prima il figlio sinistro finché il figlio sinistro non è vuoto e termina il ciclo nodo = nodo.sinistra node = stack.pop() #Il figlio sinistro è vuoto quando salta fuori dal ciclo. In questo momento, quello uscito dallo stack è equivalente al nodo radice, quindi tocca al figlio destro. res.append(nodo.val) nodo = nodo.destra ritorno ris

Tempo: O(n), Spazio: O(n)

1. Se x non ha un figlio sinistro, aggiungi prima il valore di x all'array di risposte, quindi accedi al figlio destro di x, ovvero x=x.right

2. Se x ha un figlio sinistro, trova il nodo più a destra sul sottoalbero sinistro di x (ovvero, l'ultimo nodo del sottoalbero sinistro nell'attraversamento in ordine e il nodo predecessore di x nell'attraversamento in ordine) , che registriamo come predecessore. A seconda che il figlio destro del predecessore sia vuoto, eseguire le seguenti operazioni

3. Se il figlio destro del predecessore è vuoto, puntare il figlio destro su x, quindi accedere al figlio sinistro di x, ovvero x=x.left

4. Se il figlio destro del predecessore non è vuoto, allora il suo figlio destro punta a x in questo momento, indicando che abbiamo attraversato il sottoalbero sinistro di x. Lasciamo vuoto il figlio destro del predecessore, aggiungiamo il valore di x all'array di risposte, quindi accedere al figlio destro di x, ovvero x=x.right

5. Ripetere le operazioni precedenti fino alla visita dell'albero completo

6. In effetti, faremo un ulteriore passo nell'intero processo: assumendo che il nodo attualmente attraversato sia x, puntiamo il figlio destro del nodo più a destra nel sottoalbero sinistro da x a x, in modo che dopo l'attraversamento del sottoalbero sinistro sia completato, utilizzeremo questo puntatore a Resi

soluzione di classe { public List<Integer> inorderTraversal(TreeNode root) { List<Integer> res = new ArrayList<Integer>(); TreeNode predecessor = null;//Il nodo predecessore del nodo corrente, il nodo più a destra del sottoalbero sinistro mentre (radice!= null) { //A seconda che sia presente un figlio sinistro, determina se trovare il nodo predecessore o accedere direttamente al figlio destro se (root.sinistra!= null) { //Trova prima il predecessore, quindi assegna un valore al figlio destro e quindi attraversa il figlio sinistro del nodo corrente //Il nodo predecessore è il nodo radice corrente, fai un passo a sinistra e poi continua a camminare a destra finché non può più andare. predecessore = root.sinistra; while (predecessore.destra!= null && predecessore.destra!= root) { predecessore = predecessore.destra; } //Determina se l'assegnazione o l'accesso al sottoalbero sinistro termina in base al fatto che il figlio destro del predecessore sia vuoto. //Lascia che il puntatore destro del predecessore punti alla radice e continui ad attraversare il sottoalbero sinistro if (predecessore.destra == null) { predecessore.destra = radice; radice = radice.sinistra; } //Indica che il sottoalbero sinistro è stato visitato A questo punto, visitare il nodo radice, quindi disconnettere il collegamento e continuare a visitare il sottoalbero destro. altro { res.add(root.val); predecessore.destra = null; radice = radice.destra; } } // Se non è presente il figlio sinistro, accede direttamente al figlio destro altro { res.add(root.val); radice = radice.destra; } } restituire ris; } }

Soluzione di classe: def inorderTraversal(self, root: TreeNode) -> Lista[int]: res = lista() se non root: ritorno ris p1 = radice mentre p1: p2 = p1.left #Il nodo predecessore del nodo corrente, il nodo più a destra del sottoalbero sinistro if p2: #A seconda se c'è un figlio sinistro, determina se trovare il suo nodo predecessore o accedere direttamente al figlio destro mentre p2.right e p2.right != p1: p2 = p2.destra #A seconda che il figlio destro di p2 sia vuoto, determinare se accedere direttamente al sottoalbero sinistro e quindi assegnare il valore, oppure se l'accesso al sottoalbero sinistro è completato. if not p2.right:#Lascia che il puntatore destro di p2 punti a p1 e continua ad attraversare il sottoalbero sinistro p2.destra = p1 p1 = p1.sinistra Continua else: #Indica che il sottoalbero sinistro è stato visitato A questo punto, visitare il nodo radice, quindi disconnettere il collegamento e continuare a visitare il sottoalbero destro. res.append(p1.val) p2.right = Nessuno else: #Se non c'è il figlio sinistro, accedi direttamente al figlio destro res.append(p1.val) p1 = p1.destra ritorno ris

Complessità temporale: O(n), dove n è il numero di nodi nell'albero di ricerca binario. Ogni nodo nell'attraversamento di Morris verrà visitato due volte, quindi la complessità temporale totale è O(2n)=O(n)

Complessità spaziale: O(1)

0. Ha l'efficienza del metodo di iterazione dello stack ed è conciso e facile da comprendere come il metodo ricorsivo, cosa ancora più importante, questo metodo può scrivere codice completamente coerente per l'attraversamento del pre-ordine, del mid-order e del post-order.

1. Utilizza i colori per contrassegnare lo stato dei nodi. I nuovi nodi sono bianchi e i nodi visitati sono grigi. Se il nodo incontrato è bianco, contrassegnalo come grigio, quindi inserisci il nodo figlio destro, se stesso e il nodo figlio sinistro nello stack in sequenza. Se il nodo incontrato è grigio, viene emesso il valore del nodo

2. Se desideri implementare l'attraversamento pre-ordine e post-ordine, devi solo regolare l'ordine di sovrapposizione dei nodi figlio sinistro e destro.

Soluzione di classe: def inorderTraversal(self, root: TreeNode) -> Lista[int]: BIANCO, GRIGIO = 0, 1 #BIANCO non è stato visitato, GRIGIO ha visitato ris = [] pila = [(BIANCO, radice)] mentre pila: colore, nodo = stack.pop() se il nodo è Nessuno: continua se colore == BIANCO: #L'ordine di metà ordine è radice sinistra destra, e l'ordine di spingere nello stack è radice destra sinistra. Regola l'ordine per completare altri attraversamenti. stack.append((BIANCO, nodo.destra)) stack.append((GRAY, node)) #Il nodo corrente diventa grigio ed è stato visitato stack.append((BIANCO, nodo.sinistra)) altro: res.append(nodo.val) ritorno ris

Tempo: O(n), Spazio: O(n)

Quando si ritorna al nodo radice, contrassegnare il nodo corrente per determinare se tornare dal sottoalbero sinistro o dal sottoalbero destro. Quando si ritorna dal sottoalbero destro, iniziare ad attraversare il nodo

soluzione di classe { public List<Integer> postorderTraversal(TreeNode root) { List<Integer> res = new ArrayList<Integer>(); Stack<NodoAlbero> stack = nuovo Stack<>(); //Il pre-nodo viene utilizzato per registrare il nodo precedentemente visitato, distinguendo tra la restituzione del nodo radice dal sottoalbero sinistro o dal sottoalbero destro. TreeNode pre = null; while(root!=null || !stack.empty()){ mentre(root!=null){ stack.push(root); //Spinge continuamente il nodo sinistro nello stack radice = radice.sinistra; } root = stack.peek();// Ritorna dal sottoalbero di sinistra, ottieni solo il nodo radice e non visualizzarlo, non è stato ancora visitato if(root.right==null || root.right==pre){ //Se il nodo destro è vuoto o il nodo destro è stato visitato res.add(root.val); //Puoi accedere al nodo root in questo momento pre = radice; pila.pop(); root = null; // In questo momento, non inserire il sottoalbero sinistro nello stack nel ciclo successivo. È già stato inserito e determinare direttamente l'elemento superiore dello stack. }altro{ root = root.right; //Non rimuoverlo ancora dallo stack, inserisci il suo nodo destro nello stack } } restituire ris; } }

Soluzione di classe: def postorderTraversal(self, root: TreeNode) -> List[int]: se non root: lista restituita() res = lista() pila = lista() prev = None #Il nodo prev viene utilizzato per registrare il nodo visitato in precedenza, che distingue se restituire il nodo radice dal sottoalbero sinistro o dal sottoalbero destro. mentre root o stack: mentre root: stack.append(root) #Spinge continuamente il nodo sinistro nello stack radice = radice.sinistra #Questa applicazione viene visualizzata, ma non esiste un metodo simile nell'elenco. Puoi solo visualizzarlo prima e poi aggiungerlo. root = stack.pop() #Ritorna dal sottoalbero di sinistra, non è stato ancora visitato e verrà aggiunto allo stack in seguito. if not root.right o root.right == prev:#Se il nodo destro è vuoto o il nodo destro è stato visitato res.append(root.val) #Puoi accedere al nodo root in questo momento prev = root #Registra il nodo corrente root = None #In questo momento, non inserire il sottoalbero sinistro nello stack nel ciclo successivo. È già stato inserito e determina direttamente l'elemento superiore dello stack. altro: stack.append(root) #Se non è stato effettuato l'accesso prima, aggiungilo allo stack radice = radice.destra ritorno ris

//Modifica il codice per scrivere i nodi nell'elenco collegato dei risultati nel codice di attraversamento del preordine: cambia l'inserimento alla fine della coda con l'inserimento nell'inizio della coda //Modifica la logica di controllo prima del nodo sinistro e poi del nodo destro nel codice di attraversamento del preordine: cambia per controllare prima il nodo destro e poi il nodo sinistro. //L'attraversamento pre-ordine è costituito dalle radici sinistra e destra, l'ordine inverso è la radice destra-sinistra e l'attraversamento post-ordine è costituito dalle radici sinistra e destra. soluzione di classe { public List<Integer> postorderTraversal(TreeNode root) { ListaLinked res = nuova ListaLinked(); Stack<NodoAlbero> stack = nuovo Stack<>(); TreeNode pre = null; while(root!=null || !stack.empty()){ mentre(root!=null){ res.addFirst(root.val); //Inserisci il primo della coda stack.push(root); root = root.right; //Prima a destra poi a sinistra } radice = stack.pop(); radice = radice.sinistra; } restituire ris; } }

Tempo: O(n), Spazio: O(n)

1. L'idea centrale del Morris Traversal è quella di utilizzare un gran numero di puntatori liberi nell'albero per ottenere la massima riduzione dello spazio in testa. Le regole successive per l'attraversamento del postorder sono riassunte come segue:

2. Se il nodo figlio sinistro del nodo corrente è vuoto, attraversare il nodo figlio destro del nodo corrente.

3. Se il nodo figlio sinistro del nodo corrente non è vuoto, trova il nodo predecessore del nodo corrente sotto l'attraversamento in ordine nel sottoalbero sinistro del nodo corrente.

4. Se il nodo figlio destro del nodo predecessore è vuoto, impostare il nodo figlio destro del nodo predecessore sul nodo corrente e aggiornare il nodo corrente sul nodo figlio sinistro del nodo corrente.

5. Se il nodo figlio destro del nodo predecessore è il nodo corrente, reimpostare il nodo figlio destro su vuoto. Visualizza tutti i nodi sul percorso dal nodo figlio sinistro del nodo corrente al nodo predecessore in ordine inverso. Il nodo corrente viene aggiornato al nodo figlio destro del nodo corrente

soluzione di classe { public List<Integer> postorderTraversal(TreeNode root) { List<Integer> res = new ArrayList<Integer>(); se (radice == null) { restituire ris; } TreeNode p1 = radice, p2 = null; //p1 nodo corrente, p2 nodo predecessore mentre (p1!= nullo) { p2 = p1.sinistra; se (p2!= nullo) { while (p2.destra!= null && p2.destra!= p1) { p2 = p2.destra; } se (p2.destra == null) { p2.destra = p1; p1 = p1.sinistra; Continua; } altro { p2.destra = nullo; addPath(res, p1.sinistra); } } p1 = p1.destra; } addPath(res, root); restituire ris; } public void addPath(List<Integer> res, nodo TreeNode) { conteggio intero = 0; while (nodo!= null) { contare; res.add(nodo.val); nodo = nodo.destra; } //Inverte i nodi appena aggiunti int sinistra = res.size() - conteggio, destra = res.size() - 1; mentre (sinistra < destra) { int temp = res.get(sinistra); res.set(sinistra, res.get(destra)); res.set(destra, temp); Sinistra ; Giusto--; } } }

Soluzione di classe: def postorderTraversal(self, root: TreeNode) -> List[int]: def addPath(nodo: TreeNode): conteggio = 0 mentre nodo: conteggio = 1 res.append(nodo.val) nodo = nodo.destra #Inverti i nodi appena aggiunti i, j = len(res) - conteggio, len(res) - 1 mentre io < j: res[i], res[j] = res[j], res[i] #Non sono richieste variabili intermedie io=1 j -= 1 se non root: lista restituita() res = lista() p1 = radice mentre p1: p2 = p1.left #p2 nodo predecessore se p2: mentre p2.right e p2.right != p1: p2 = p2.destra se non p2.right: p2.destra = p1 p1 = p1.sinistra Continua altro: p2.right = Nessuno addPath(p1.left) p1 = p1.destra aggiungiPercorso(radice) ritorno ris

Tempo: O(n), Spazio: O(1)

1. Se conosciamo la profondità massima l e r del sottoalbero sinistro e del sottoalbero destro, allora la profondità massima dell'albero binario è max(l,r) 1

2. La profondità massima del sottoalbero sinistro e del sottoalbero destro può essere calcolata allo stesso modo. Pertanto, quando calcoliamo la profondità massima dell'albero binario corrente, possiamo prima calcolare ricorsivamente la profondità massima del suo sottoalbero sinistro e del sottoalbero destro, quindi calcolare la profondità massima dell'albero binario corrente in tempo O(1). La ricorsione termina quando viene raggiunto un nodo vuoto

soluzione di classe { public int maxDepth(radice TreeNode) { if(root==null) return 0;//Quando l'ultimo 1 è un nodo foglia, l'altezza verrà restituita a 1 return Math.max(maxDepth(root.left),maxDepth(root.right)) 1; } }

Soluzione di classe: def maxDepth(self, root: TreeNode) -> int: se non root: restituisce 0 lefth = self.maxDepth(root.left) #Devi usare self.self quando chiami te stesso destra = self.maxProfondità(root.destra) return max(sinistra,destra) 1

Complessità temporale: O(n), dove n è il numero di nodi dell'albero binario. Ogni nodo viene attraversato una sola volta nella ricorsione

Complessità spaziale: O(altezza), dove altezza rappresenta l'altezza dell'albero binario. Le funzioni ricorsive richiedono spazio nello stack e lo spazio nello stack dipende dalla profondità della ricorsione, quindi la complessità dello spazio è equivalente all'altezza dell'albero binario

La coda della ricerca in ampiezza memorizza "tutti i nodi dello strato corrente". Ogni volta che espandiamo il livello successivo, a differenza della ricerca in ampiezza, che elimina dalla coda solo un nodo alla volta, dobbiamo eliminare tutti i nodi della coda per l'espansione, in modo da garantire che la coda venga espansa ogni volta vengono memorizzati tutti i nodi del livello corrente, ovvero espandiamo livello per livello Infine, utilizziamo una variabile ans per mantenere il numero di espansioni. La profondità massima dell'albero binario è ans

soluzione di classe { public int maxDepth(radice TreeNode) { se (radice == null) { restituire 0; } Queue<TreeNode> coda = new LinkedList<TreeNode>(); coda.offerta(root); int ans = 0; while (!queue.isEmpty()) { int dimensione = coda.dimensione(); while (size > 0) { //opera uno strato di elementi alla volta Nodo TreeNode = coda.poll(); if (nodo.sinistra!= null) { coda.offerta(nodo.sinistra); } if (nodo.destra!= null) { coda.offerta(nodo.destra); } misurare--; } ans ;//Dopo aver completato un livello di operazione, il numero di livelli è 1 } ritorno e; } }

collezioni di importazione Soluzione di classe: def maxDepth(self, root: TreeNode) -> int: se non root: restituisce 0 coda = collezioni.deque() coda.append(root) ans = 0 durante la coda: as = 1 for _ in range(len(queue)): #Attraversa ogni volta gli elementi di un livello nodo = coda.popleft() se nodo.sinistra: coda.append(nodo.sinistra) se nodo.destra: coda.append(nodo.destra) ritorno es

Complessità temporale: O(n), dove n è il numero di nodi nell'albero binario. Stessa analisi del metodo 1, ogni nodo verrà visitato una sola volta

Complessità spaziale: il consumo di spazio di questo metodo dipende dal numero di elementi memorizzati nella coda, che nel caso peggiore raggiungerà O(n)

Iniziamo dal nodo radice, attraversiamo ricorsivamente l'albero e iniziamo prima a sfogliare dai nodi foglia. Se i sottoalberi sinistro e destro della radice del nodo attualmente attraversato sono stati invertiti, allora dobbiamo solo scambiare le posizioni dei due sottoalberi per completare l'inversione dell'intero sottoalbero con radice come nodo radice.

soluzione di classe { public TreeNode invertTree(TreeNode root) { se (radice == null) { restituire null; } //Attraversa l'albero in modo ricorsivo e inizia prima a sfogliare dai nodi foglia TreeNode sinistra = invertTree(root.left); TreeNode destra = invertTree(root.right); radice.sinistra = destra; radice.destra = sinistra; restituisce radice; } }

Soluzione di classe: def invertTree(self, root: TreeNode) -> TreeNode: se non root: restituisce radice #Attraversa l'albero in modo ricorsivo e inizia prima a sfogliare dai nodi foglia sinistra = self.invertTree(root.sinistra) destra = self.invertTree(root.right) radice.sinistra, radice.destra = destra, sinistra restituisce radice

Complessità temporale: O(N), dove N è il numero di nodi dell'albero binario. Attraverseremo ogni nodo dell'albero binario e per ogni nodo scambieremo i suoi due sottoalberi in tempo costante

Complessità spaziale: O(N). Lo spazio utilizzato è determinato dalla profondità dello stack di ricorsione, che è uguale all'altezza del nodo corrente nell'albero binario. In circostanze medie, l'altezza di un albero binario ha una relazione logaritmica con il numero di nodi, che è O(logN). Nel caso peggiore, l’albero forma una catena e la complessità spaziale è O(N)

Dato un intero n, quanti alberi di ricerca binari ci sono con 1...n come nodi?

1. Attraversa ogni numero i, usa il numero come radice dell'albero, usa la sequenza 1⋯(i−1) come sottoalbero sinistro e usa la sequenza (i 1)⋯n come sottoalbero destro. Quindi possiamo costruire ricorsivamente il sottoalbero sinistro e il sottoalbero destro nello stesso modo

2. Poiché i valori della radice sono diversi, possiamo garantire che ciascun albero di ricerca binario sia unico

3. Il problema originale può essere scomposto in due sottoproblemi più piccoli e le soluzioni ai sottoproblemi possono essere riutilizzate. La programmazione dinamica può essere utilizzata per risolvere questo problema

4. Possiamo definire due funzioni: G(n): Il numero di diversi alberi binari di ricerca che possono essere formati da una sequenza di lunghezza n. F(i,n): il numero di diversi alberi binari di ricerca con i come radice e lunghezza della sequenza n (1≤i≤n). Si può vedere che G(n) è la funzione che dobbiamo risolvere

5. Il numero totale di diversi alberi binari di ricerca G(n) è la somma di F(i,n) che attraversa tutti i(1≤i≤n)

6. Per i casi limite, quando la lunghezza della sequenza è 1 (solo la radice) o 0 (albero vuoto), c'è solo una situazione, vale a dire: G(0)=1, G(1)=1

7. Seleziona il numero i come radice, quindi l'insieme di tutti gli alberi di ricerca binari con la radice i è il prodotto cartesiano dell'insieme del sottoalbero sinistro e dell'insieme del sottoalbero destro

8. Combina le due formule:

soluzione di classe { public int numTrees(int n) { int[] G = nuovo int[n 1]; G[0] = 1; G[1] = 1; for (int i = 2; i <= n; i) { for (int j = 1; j <= i; j) { G[i] = G[j - 1] * G[i - j]; } } ritorna G[n]; } }

Soluzione di classe: def numAlberi(self, n): G = [0]*(n 1) #Lista di lunghezza n 1 G[0], G[1] = 1, 1 for i in range(2, n 1): #Traversa da G[2] a n for j in range(1, i 1): #Formula di somma corrispondente da 1 a n G[i] = G[j-1] * G[i-j] restituire G[n]

Complessità temporale: O(n^2), dove n rappresenta il numero di nodi nell'albero di ricerca binario. La funzione G(n) ha un totale di n valori che devono essere risolti. Ciascuna soluzione richiede una complessità temporale O(n), quindi la complessità temporale totale è O(n^2).

Complessità spaziale: O(n). Abbiamo bisogno di spazio O(n) per memorizzare l'array G

1. Il valore della funzione G(n) derivata nel metodo 1 è matematicamente chiamato numero catalano Cn ​

soluzione di classe { public int numTrees(int n) { // Suggerimento: qui è necessario utilizzare il tipo lungo per evitare l'overflow durante il calcolo. lungo C = 1; for (int i = 0; i < n; i) { C = C * 2 * (2 * i 1) / (i 2); } ritorno (int) C; } }

classe Soluzione(oggetto): def numAlberi(self, n): C=1 per i nell'intervallo(0, n): C = C * 2*(2*i 1)/(i 2) ritorno int(C)

Complessità temporale: O(n), dove n rappresenta il numero di nodi nell'albero di ricerca binario. Dobbiamo eseguirlo in loop solo una volta

Complessità spaziale: O(1). Abbiamo solo bisogno di spazio costante per memorizzare diverse variabili

Dato un numero intero n, genera tutti gli alberi di ricerca binari costituiti dai nodi 1...n

1. Supponiamo che la lunghezza della sequenza corrente sia n, e se enumeriamo il valore del nodo radice come i, allora in base alle proprietà dell'albero di ricerca binario, possiamo sapere che l'insieme dei valori del nodo ​​​​del il sottoalbero di sinistra è [1...i−1] e l'insieme dei valori dei nodi del sottoalbero di destra è [1...i−1]. L'insieme dei valori dei nodi dell'albero è [ io 1…n]. Rispetto al problema originale, la generazione del sottoalbero sinistro e del sottoalbero destro è un sottoproblema con lunghezza di sequenza ridotta, quindi possiamo pensare di utilizzare metodi ricorsivi per risolvere questo problema.

2. Definire la funzione generateTrees(start, end) per indicare che il valore corrente impostato è [start, end] e restituire tutti gli alberi di ricerca binari possibili generati dalla sequenza [start, end]. Secondo l'idea di cui sopra, consideriamo che il valore ii nell'enumerazione [inizio, fine] è la radice dell'albero binario di ricerca corrente, quindi la sequenza è divisa in due parti: [inizio, i−1] e [i 1 , FINE]. Chiamiamo queste due parti in modo ricorsivo, vale a dire generateTrees(start, i - 1) e generateTrees(i 1, end), per ottenere tutti i sottoalberi sinistri fattibili e i sottoalberi destri fattibili. Quindi, nell'ultimo passaggio, dobbiamo solo raccogliere i sottoalberi sinistri fattibili sottoalberi dai possibili sottoalberi di sinistra Selezionane uno, quindi selezionane uno dall'insieme di sottoalberi di destra possibili e uniscilo al nodo radice e inserisci l'albero di ricerca binario generato nell'array di risposte.

3. Il punto di ingresso della ricorsione è generateTrees(1, n), e il punto di uscita è quando \textit{start}>\textit{end}start>end, l'albero di ricerca binario corrente è vuoto, restituisce semplicemente un nodo vuoto.

Soluzione di classe: def generateTrees(self, n: int) -> Lista[NodoAlbero]: def generareAlberi(inizio, fine): se inizio > fine: ritorno [Nessuno,] tutti gli alberi = [] for i in range(start, end 1): # Enumera i nodi radice ammissibili #Completa prima la costruzione ricorsiva dei sottoalberi sinistro e destro, quindi utilizza l'insieme completo dei sottoalberi sinistro e destro per costruire un albero completo leftTrees = generateTrees(start, i - 1) # Ottieni l'insieme di tutti i sottoalberi a sinistra possibili rightTrees = generateTrees(i 1, end) # Ottieni l'insieme di tutti i sottoalberi destri possibili # Seleziona un sottoalbero sinistro dal set di sottoalberi sinistro, seleziona un sottoalbero destro dal set di sottoalberi destro e uniscili al nodo radice per l in leftTrees: #Relazione del prodotto di Cartesio per r in rightTrees: currTree = TreeNode(i) #Nodo radice currTree.sinistra = l currTree.right = r allTrees.append(currTree) restituisce tutti gli alberi return generateTrees(1, n) if n else []

Complessità temporale: la complessità temporale dell'intero algoritmo dipende dal "numero di alberi binari di ricerca fattibili" e il numero di alberi binari di ricerca generati per n punti è equivalente all'ennesimo "numero di Cattleya" in matematica, utilizzando G_n mezzi. I lettori sono invitati a verificare da soli i dettagli specifici del numero Cattleya. Non entrerò qui nei dettagli e fornirò solo la conclusione. La generazione di un albero di ricerca binario richiede una complessità temporale O(n). Ci sono G_n alberi di ricerca binari in totale, ovvero O(nG_n).

Complessità spaziale: ci sono Gn alberi di ricerca binari generati da n punti, ogni albero ha n nodi, quindi lo spazio di archiviazione richiede O(nG_n)

Dati due alberi binari, immagina che quando ne sovrapponi uno all'altro, alcuni dei nodi dei due alberi binari si sovrappongono. È necessario unirli in un nuovo albero binario. La regola della fusione è che se due nodi si sovrappongono, i loro valori vengono aggiunti come nuovo valore dopo l'unione del nodo. Altrimenti, il nodo che non è NULL verrà utilizzato direttamente come nodo del nuovo albero binario.

1. Attraversare due alberi binari contemporaneamente partendo dal nodo radice e unire i nodi corrispondenti I nodi corrispondenti dei due alberi binari possono avere le seguenti tre situazioni e utilizzare metodi di unione diversi per ciascuna situazione.

2. Se i nodi corrispondenti dei due alberi binari sono vuoti, anche i nodi corrispondenti dell'albero binario unito saranno vuoti.

3. Se solo uno dei nodi corrispondenti dei due alberi binari è vuoto, il nodo corrispondente dell'albero binario unito sarà il nodo non vuoto.

4. Se i nodi corrispondenti dei due alberi binari non sono vuoti, il valore del nodo corrispondente dell'albero binario unito è la somma dei valori dei nodi corrispondenti dei due alberi binari In questo momento, i due i nodi devono essere uniti esplicitamente.

5. Dopo aver unito un nodo, è necessario unire rispettivamente i sottoalberi sinistro e destro del nodo. Questo è un processo ricorsivo

soluzione di classe { public TreeNode mergeTrees(TreeNode t1, TreeNode t2) { se (t1 == nullo) { restituire t2; } se (t2 == nullo) { restituire t1; } //Prima unisci il nodo corrente, quindi ricorsivi i suoi sottoalberi sinistro e destro TreeNode unito = nuovo TreeNode(t1.val t2.val); merged.left = mergeTrees(t1.left, t2.left); merged.right = mergeTrees(t1.right, t2.right); ritorno unito; } }

Soluzione di classe: def mergeTrees(self, t1: TreeNode, t2: TreeNode) -> TreeNode: se non t1: restituire t2 se non t2: restituire t1 #Prima di tutto unisci il nodo corrente, quindi ricorsivi i suoi sottoalberi sinistro e destro uniti = TreeNode(t1.val t2.val) merged.left = self.mergeTrees(t1.left, t2.left) merged.right = self.mergeTrees(t1.right, t2.right) restituire unito

Complessità temporale: O(min(m,n)), dove m e n sono rispettivamente il numero di nodi dei due alberi binari. La ricerca approfondita viene eseguita su due alberi binari contemporaneamente. Solo quando i nodi corrispondenti nei due alberi binari non sono vuoti, il nodo verrà unito esplicitamente. Pertanto, il numero di nodi visitati non supererà il numero di albero binario più piccolo

Complessità spaziale: O(min(m,n)), dove m e n sono rispettivamente il numero di nodi dei due alberi binari. La complessità dello spazio dipende dal numero di livelli di chiamate ricorsive. Il numero di livelli di chiamate ricorsive non supererà l'altezza massima dell'albero binario più piccolo. Nel peggiore dei casi, l'altezza dell'albero binario è uguale al numero di nodi .

Implementare un iteratore dell'albero di ricerca binario. Inizializzerai l'iteratore utilizzando il nodo radice dell'albero di ricerca binario. La chiamata a next() restituirà il numero più piccolo successivo nell'albero di ricerca binaria

1. Il modo più semplice per implementare un iteratore è su un'interfaccia contenitore simile ad un array. Se abbiamo un array, abbiamo solo bisogno di un puntatore o indice per implementare facilmente le funzioni next() e hasNext()

2. Utilizzare un array aggiuntivo ed espandere l'albero di ricerca binario per memorizzarlo. Vogliamo che gli elementi dell'array siano ordinati in ordine crescente, quindi dovremmo eseguire un attraversamento in ordine dell'albero di ricerca binario e quindi costruire una funzione iteratore nell'array

3. Una volta che tutti i nodi sono nell'array, abbiamo solo bisogno di un puntatore o indice per implementare le funzioni next() e hasNext. Ogni volta che viene chiamato hasNext(), dobbiamo solo verificare se l'indice raggiunge la fine dell'array. Ogni volta che viene chiamato next(), restituiamo semplicemente l'elemento puntato dall'indice e andiamo avanti di un passo per simulare l'avanzamento dell'iteratore

classe BSTIteratore { ArrayList<Integer> nodesSorted; indice intero; pubblico BSTIterator(radice TreeNode) { this.nodesSorted = new ArrayList<Integer>(); this.indice = -1; this._inorder(root); } private void _inorder(radice TreeNode) { if (root == null) ritorno; this._inorder(root.left); this.nodesSorted.add(root.val); this._inorder(root.right); } pubblico int successivo() { restituisce this.nodesSorted.get( this.index); } booleano pubblico hasNext() { restituisce this.index 1 < this.nodesSorted.size(); } }

classe BSTIteratore: self.nodi_ordinati = [] indice.self = -1 self._inorder(radice) def __init__(self, root: TreeNode): self.nodi_ordinati = [] self.indice = -1 self._inorder(radice) def _inorder(self, root): se non root: ritorno self._inorder(root.left) self.nodes_sorted.append(root.val) self._inorder(root.right) def successivo(self) -> int: self.indice = 1 restituisce self.nodi_ordinati[self.indice] def hasNext(self) -> bool: return self.index 1 < len(self.nodes_sorted)

Complessità temporale: il tempo impiegato per costruire l'iteratore è O(N). L'enunciazione del problema richiede solo di analizzare la complessità delle due funzioni, ma quando si implementa la classe, dobbiamo prestare attenzione anche al tempo richiesto per inizializzare l'oggetto della classe. ; in questo caso Sotto, la complessità temporale è correlata linearmente al numero di nodi nell'albero di ricerca binario: next(): O(1), hasNext(): O(1)

Complessità spaziale: O(N), poiché abbiamo creato un array per contenere tutti i valori dei nodi nell'albero di ricerca binario, che non soddisfa i requisiti nella dichiarazione del problema, la complessità spaziale massima di qualsiasi funzione dovrebbe essere O(h) , dove h si riferisce all'altezza dell'albero Per un albero di ricerca binario bilanciato, l'altezza è solitamente logN

1. Il metodo utilizzato in precedenza ha una relazione lineare nello spazio con il numero di nodi nell'albero binario di ricerca. Tuttavia, il motivo per cui dobbiamo utilizzare questo approccio è che possiamo eseguire l'iterazione sull'array e non possiamo mettere in pausa la ricorsione per poi avviarla ad un certo punto. Tuttavia, se possiamo simulare la ricorsione controllata con attraversamento in ordine, in realtà non abbiamo bisogno di utilizzare altro spazio oltre a quello sullo stack utilizzato per simulare la ricorsione

2. Utilizzare un metodo iterativo per simulare l'attraversamento in ordine invece di un metodo ricorsivo, nel fare ciò, possiamo facilmente implementare le chiamate di queste due funzioni invece di utilizzare altro spazio aggiuntivo;

3. Inizializzare uno stack vuoto S, utilizzato per simulare l'attraversamento in ordine di un albero di ricerca binario. Per l'attraversamento in ordine utilizziamo lo stesso metodo di prima, tranne per il fatto che ora utilizziamo il nostro stack invece dello stack del sistema. Poiché utilizziamo una struttura dati personalizzata, la ricorsione può essere messa in pausa e ripresa in qualsiasi momento

4. Deve essere implementata anche una funzione di supporto, che verrà richiamata più e più volte durante l'implementazione. Questa funzione è chiamata _inorder_left e aggiunge allo stack tutti i figli sinistri di un dato nodo finché il nodo non ha figli sinistri.

5. Quando la funzione next() viene chiamata per la prima volta, deve essere restituito l'elemento minimo dell'albero binario di ricerca, quindi simuliamo la ricorsione e dobbiamo andare avanti di un passo, cioè spostarci all'elemento minimo successivo di l'albero binario di ricerca. La parte superiore dello stack contiene sempre l'elemento restituito dalla funzione next(). hasNext() è facile da implementare poiché dobbiamo solo verificare se lo stack è vuoto

6. Innanzitutto, dato il nodo radice dell'albero di ricerca binario, chiamiamo la funzione _inorder_left, che garantisce che la parte superiore dello stack contenga sempre l'elemento restituito dalla funzione next()

7. Supponiamo di chiamare next(), dobbiamo restituire il successivo elemento più piccolo nell'albero di ricerca binario, che è l'elemento in cima allo stack. Ci sono due possibilità: Uno è che il nodo in cima allo stack è un nodo foglia. Questo è lo scenario migliore perché non dobbiamo fare altro che estrarre il nodo dallo stack e restituirne il valore. Quindi questa è un'operazione a tempo costante. Un altro caso è quando il nodo in cima allo stack possiede il nodo giusto. Non abbiamo bisogno di controllare il nodo sinistro perché è già stato aggiunto allo stack. L'elemento superiore dello stack non ha un nodo sinistro oppure il nodo sinistro è stato elaborato. Se c'è un nodo destro in cima allo stack, allora dobbiamo chiamare la funzione helper sul nodo destro. La complessità temporale dipende dalla struttura dell'albero

classe BSTIteratore { Pila<NodoAlbero> pila; pubblico BSTIterator(radice TreeNode) { this.stack = new Stack<TreeNode>();//Usa lo stack per simulare la ricorsione this._leftmostInorder(root);//L'algoritmo inizia con la chiamata della funzione helper } //Funzione di supporto, aggiunge tutti i nodi secondari di sinistra allo stack private void _leftmostInorder(radice TreeNode) { mentre (radice!= null) { this.stack.push(root); radice = radice.sinistra; } } pubblico int successivo() { TreeNode topmostNode = this.stack.pop();//L'elemento superiore dello stack è l'elemento più piccolo //Mantieni l'elemento superiore dello stack come l'elemento più piccolo Se il nodo ha un figlio destro, chiama la funzione di aiuto if (topmostNode.right!= null) { this._leftmostInorder(topmostNode.right); } restituisce topmostNode.val; } booleano pubblico hasNext() { restituisce this.stack.size() > 0; } }

classe BSTIteratore: def __init__(self, root: TreeNode): self.stack = [] #Utilizza lo stack per simulare la ricorsione self._leftmost_inorder(root) #L'algoritmo inizia con la chiamata della funzione helper Funzione #Help, aggiungi tutti i nodi secondari di sinistra allo stack def _leftmost_inorder(self, root): mentre root: self.stack.append(root) radice = radice.sinistra def successivo(self) -> int: topmost_node = self.stack.pop() #L'elemento in cima allo stack è l'elemento più piccolo #Mantieni l'elemento superiore dello stack come l'elemento più piccolo Se il nodo ha un figlio destro, chiama la funzione helper se topmost_node.right: self._leftmost_inorder(topmost_node.right) restituisce topmost_node.val def hasNext(self) -> bool: restituisce len(self.stack) > 0

Complessità temporale: hasNext(): se ci sono ancora elementi nello stack, restituisce true, altrimenti restituisce false. Quindi questa è un'operazione O(1). next(): contiene due passaggi principali. Uno è quello di estrarre un elemento dallo stack, che è l'elemento più piccolo successivo. Questa è un'operazione O(1). Tuttavia, dobbiamo chiamare la funzione helper _inorder_left, che deve essere ricorsiva, aggiungendo il nodo sinistro allo stack, che è un'operazione temporale lineare, O(N) nel caso peggiore. Ma lo chiamiamo solo sul nodo che contiene il nodo giusto e non sempre elaborerà N nodi. Solo se abbiamo un albero inclinato ci saranno N nodi. Pertanto, la complessità temporale media di questa operazione è ancora O(1), il che è in linea con i requisiti del problema.

Complessità spaziale: O(h), utilizzando uno stack per simulare la ricorsione

Dato un array di interi positivi arr, consideriamo tutti gli alberi binari che soddisfano le seguenti condizioni: Ogni nodo ha 0 o 2 nodi figli. I valori nell'array arr corrispondono uno a uno ai valori di ciascun nodo foglia nell'attraversamento in ordine dell'albero. Il valore di ciascun nodo non foglia è uguale al prodotto del valore massimo del nodo foglia nel suo sottoalbero sinistro e nel sottoalbero destro. In tutti questi alberi binari, restituisce la più piccola somma possibile dei valori di ciascun nodo non foglia

Il nocciolo di questa domanda è: Devi sapere che l'attraversamento in ordine determina che tutti gli elementi di sinistra (incluso se stesso) dell'elemento k-esimo nell'array arr (0...n-1) sono nel sottoalbero di sinistra e i suoi elementi di destra sono tutti in il sottoalbero destro e in questo momento il prodotto dei valori massimi selezionati dai sottoalberi sinistro e destro è la radice in questo momento, che è il nodo non foglia menzionato nella domanda, quindi possiamo supporre che da da i a j, la somma minima può essere: k in questo momento Il sottoproblema prodotto del valore massimo degli elementi sui lati sinistro e destro di k è il valore minimo del sottoproblema k sulla sinistra (i, k), il valore minimo del lato destro di k cifre (k 1, j), Cioè: dp[i][j]=min(dp[i][j], dp[i][k] dp[k 1][j] max[i][k]*max[k 1][ J ]) Questa domanda è la stessa di leetcode1039

soluzione di classe { public int mctFromLeafValues(int[] arr) { int n = arr.lunghezza; //Trova il valore massimo degli elementi in arr da i a j e memorizzalo in max[i][j]. i e j possono essere uguali. int[][]max = nuovo int[n][n]; for (int j=0;j<n;j) { intvaloremax = arr[j]; for (int i=j;i>=0;i--) { valoremax = Math.max(valoremax, arr[i]); max[i][j] = valoremax; } } int[][] dp = nuovo int[n][n]; for (int j=0; j<n; j ) { for (int i=j; i>=0; i--) { //k è un valore compreso tra i e j, i<=k<j int min = intero.MAX_VALUE; for (int k=i; k 1<=j; k ) { min = Math.min(min,dp[i][k] dp[k 1][j] max[i][k]*max[k 1][j]); dp[i][j] = min;//Mantieni sempre la somma minima tra i e j } } } ritorna dp[0][n-1]; } }

Soluzione di classe: def mctFromLeafValues(self, arr: Lista[int]) -> int: n = len(arr) dp = [[float('inf') for _ in range(n)] for _ in range(n)] # Imposta il valore iniziale al massimo maxval = [[0 for _ in range(n)] for _ in range(n)] # Imposta il valore massimo della query dell'intervallo iniziale su 0 for i in range(n):# Trova l'elemento più grande nell'intervallo [i, j] per j nell'intervallo(i, n): maxval[i][j] = max(arr[i:j 1]) for i in range(n):# I nodi foglia non partecipano al calcolo dp[i][i] = 0 for l in range(1, n): # Lunghezza dell'intervallo di enumerazione for s in range(n - l): # Enumera il punto iniziale dell'intervallo for k in range(s, s l):# Enumera e divide due sottoalberi, k è un valore compreso tra s e l dp[s][s l] = min(dp[s][s l], dp[s][k] dp[k 1][s l] maxval[s][k] * maxval[k 1][s l]) ritorna dp[0][n - 1]

Tempo: O(n^3), Spazio: O(n^2)

1. Se si desidera ridurre al minimo il valore mct, i nodi foglia con valori più piccoli dovrebbero essere posizionati il ​​più in basso possibile e i nodi foglia con valori più grandi dovrebbero essere posizionati il ​​più in alto possibile. Perché i nodi foglia in basso servono per la moltiplicazione più volte. Ciò determina che dobbiamo trovare un valore minimo. Puoi trovare un valore minimo mantenendo uno stack monotonicamente decrescente, perché poiché è uno stack monotonicamente decrescente, il nodo a sinistra deve essere maggiore del nodo in cima allo stack e il nodo corrente (a destra) è anche maggiore del nodo in cima allo stack (perché il nodo corrente è più piccolo della cima dello stack), viene inserito direttamente nello stack)

2. Dopo aver trovato questo valore minimo, è necessario guardare a sinistra e a destra per vedere quale valore è più piccolo a sinistra o a destra. Lo scopo è posizionare il valore più piccolo il più in basso possibile.

soluzione di classe { public int mctFromLeafValues(int[] arr) { Stack<Intero> st = new Stack(); st.push(Integer.MAX_VALUE); int mct = 0; //Inizia a costruire uno stack decrescente Se l'elemento corrente è maggiore dell'elemento in cima allo stack, l'elemento in cima allo stack verrà estratto dallo stack e sarà possibile trovare il valore minimo. for (int i = 0; i < arr.lunghezza; i ) { while (arr[i] >= st.peek()) { //L'elemento superiore dello stack viene estratto dallo stack e combinato con gli elementi più piccoli sui lati sinistro e destro mct = st.pop() * Math.min(st.peek(), arr[i]); } st.push(arr[i]); } while (st.dimensione() > 2) { mct = st.pop() * st.peek(); } ritorno mct; } }

Soluzione di classe: def mctFromLeafValues(self, A: Lista[int]) -> int: res, n = 0, len(A) stack = [float('inf')] #Metti il ​​valore massimo per primo nello stack #Inizia a costruire uno stack decrescente. Se l'elemento corrente è maggiore dell'elemento superiore dello stack, l'elemento superiore dello stack verrà estratto dallo stack. È possibile trovare il valore minimo. per una in A: mentre a >= pila[-1]: mid = stack.pop() #L'elemento superiore dello stack viene estratto dallo stack e combinato con gli elementi più piccoli sui lati sinistro e destro res = mid * min(stack[-1], a) stack.append(a) while len(stack) > 2: res = stack.pop() * stack[-1] ritorno ris

Tempo: O(n), Spazio: O(n)

Converte un array ordinato in ordine crescente in un albero di ricerca binario con altezza bilanciata. Un albero binario con altezza bilanciata significa che il valore assoluto della differenza di altezza tra i sottoalberi sinistro e destro di ciascun nodo di un albero binario non supera 1.

1. Selezionare il numero centrale come nodo radice dell'albero di ricerca binario, in modo che il numero di numeri assegnati ai sottoalberi sinistro e destro sia lo stesso o differisca solo di 1, il che può mantenere l'albero bilanciato.

2. Dopo aver determinato il nodo radice dell'albero di ricerca binario bilanciato, i numeri rimanenti si trovano rispettivamente nel sottoalbero sinistro e nel sottoalbero destro dell'albero di ricerca binario bilanciato. Anche il sottoalbero sinistro e il sottoalbero destro sono rispettivamente alberi di ricerca binari bilanciati può creare un albero di ricerca binario bilanciato in modo ricorsivo

3. Perché si può garantire che tale risultato sarà "equilibrato"? Qui puoi fare riferimento a "1382. Bilancia l'albero di ricerca binario"

4. La situazione di base della ricorsione è che l'albero di ricerca binario bilanciato non contiene alcun numero. In questo momento, l'albero di ricerca binario bilanciato è vuoto.

5. Nel caso di un dato array di sequenze attraversali in ordine, i numeri in ciascun sottoalbero devono essere continui nell'array. I numeri contenuti nel sottoalbero possono essere determinati dall'intervallo dell'indice dell'array. L'intervallo dell'indice è contrassegnato come [sinistra , destra], quando sinistra>destra, l'albero di ricerca binaria bilanciata è vuoto

Soluzione di classe: def sortedArrayToBST(self, nums: List[int]) -> TreeNode: def aiutante(sinistra, destra): se sinistra > destra: #Condizione di terminazione della dicotomia ritorno Nessuno mid = (sinistra destra) // 2 #Seleziona sempre il numero a sinistra della posizione centrale come nodo radice root = TreeNode(nums[mid]) #Determina prima il nodo radice, quindi ricorsivi i sottoalberi sinistro e destro root.left = helper(sinistra, metà - 1) root.right = helper(metà 1, destra) restituisce radice return helper(0, len(nums) - 1)

Complessità temporale: O(n), dove n è la lunghezza dell'array. Visita ciascun numero una sola volta

Complessità spaziale: O(logn), dove n è la lunghezza dell'array. La complessità dello spazio non considera il valore restituito, quindi la complessità dello spazio dipende principalmente dalla profondità dello stack ricorsivo. La profondità dello stack ricorsivo è O(logn)

Tempo: O(n), Spazio: O(n)

1. Impostare l'intervallo di chiusura sinistra e apertura destra

2. Utilizzare i puntatori veloce e lento per trovare la mediana

3. Costruire ricorsivamente l'albero

Soluzione di classe: def sortedListToBST(self, head: ListNode) -> TreeNode: def getMedian(sinistra: ListNode, destra: ListNode) -> ListNode: veloce=lento=sinistra while fast != right and fast.next != right:#Definisce l'intervallo come chiuso a sinistra e aperto a destra fast = fast.next.next#Il puntatore veloce si muove due volte e il puntatore lento si muove una volta lento = lento.successivo return slow #Il puntatore slow è la mediana in questo momento def buildTree(sinistra: ListNode, destra: ListNode) -> TreeNode: se sinistra == destra: ritorno Nessuno mid = getMedian(left, right) #L'intervallo è chiuso a sinistra e aperto a destra root = TreeNode(mid.val) #Determina prima il nodo radice, quindi costruisci i sottoalberi sinistro e destro root.left = buildTree(left, mid) #Non è necessario mid.pre root.right = buildTree(mid.next, destra) restituisce radice restituisce buildTree(head, None)

Complessità temporale: O(nlogn), dove n è la lunghezza dell'elenco concatenato. Supponiamo che il tempo per costruire un albero di ricerca binario da un elenco concatenato di lunghezza n sia T(n) e che la formula di ricorrenza sia T(n)=2⋅T(n/2) O(n). teorema, T(n)= O(nlogn)

Complessità dello spazio: O(logn), qui viene calcolato solo lo spazio diverso dalla risposta restituita. L'altezza dell'albero binario bilanciato è O(logn), che è la profondità massima dello stack durante il processo ricorsivo, che è lo spazio richiesto.

1. Supponiamo che il numero dell'endpoint sinistro dell'elenco collegato corrente sia sinistro, il numero dell'endpoint destro sia destro, la relazione di inclusione sia "doppia chiusa", il numero dei nodi dell'elenco collegato sia [0, n) e l'ordine di attraversamento in ordine è "sottoalbero sinistro - nodo radice - sottoalbero destro", quindi nel processo di divisione e conquista, non dobbiamo affrettarci a trovare il nodo mediano dell'elenco collegato, ma utilizzare un nodo segnaposto e quindi inserisci il suo valore quando il nodo viene attraversato in ordine

2. Eseguire l'attraversamento di ordine medio calcolando l'intervallo numerico: il numero corrispondente al nodo mediano è mid=(sinistra destra 1)/2 e gli intervalli numerici corrispondenti ai sottoalberi sinistro e destro sono [sinistra, metà−1] e [mid 1 rispettivamente. ,right], se sinistra>destra, allora la posizione attraversata corrisponde a un nodo vuoto, altrimenti corrisponde a un nodo nell'albero binario di ricerca.

3. Conosciamo già la struttura di questo albero di ricerca binario e la domanda fornisce il risultato dell'attraversamento in ordine. Quindi dobbiamo solo eseguire un attraversamento in ordine su di esso per ripristinare l'intero albero di ricerca binario.

4. Diagramma del processo ricorsivo

Soluzione di classe: def sortedListToBST(self, head: ListNode) -> TreeNode: def getLength(head: ListNode) -> int: ret = 0 mentre testa: ret=1 testa = testa.successivo ritorno ret def buildTree(sinistra: int, destra: int) -> TreeNode: se sinistra > destra: #Condizione finale dell'attraversamento di ordine intermedio ritorno Nessuno metà = (sinistra destra 1) // 2 radice = TreeNode() #Utilizzare l'attraversamento in ordine, costruire prima il sottoalbero sinistro, quindi ritornare al nodo radice e quindi costruire il sottoalbero destro, iniziando dal primo elemento root.left = buildTree(sinistra, metà - 1) head non locale #può modificare la variabile esterna non globale head root.val = head.val #Inizia ad assegnare i valori dal primo nodo testa = testa.successivo root.right = buildTree(metà 1, destra) restituisce radice lunghezza = getLunghezza(testa) restituisce buildTree(0, lunghezza - 1)

Complessità temporale: O(n), dove n è la lunghezza dell'elenco concatenato. Supponiamo che il tempo per costruire un albero di ricerca binario da un elenco concatenato di lunghezza n sia T(n) e che la formula di ricorrenza sia T(n)=2⋅T(n/2) O(1). teorema, T(n)= O(n)

Complessità dello spazio: O(logn), qui viene calcolato solo lo spazio diverso dalla risposta restituita. L'altezza dell'albero binario bilanciato è O(logn), che è la profondità massima dello stack durante il processo ricorsivo, che è lo spazio richiesto.

La serializzazione è l'operazione di conversione di una struttura di dati o di un oggetto in bit continui. I dati convertiti possono quindi essere archiviati in un file o in memoria e possono anche essere trasmessi a un altro ambiente informatico attraverso la rete e ricostruiti nel modo opposto dati. Si prega di progettare un algoritmo per implementare la serializzazione e la deserializzazione degli alberi binari. La logica di esecuzione dell'algoritmo di sequenza/deserializzazione non è limitata qui. Devi solo assicurarti che un albero binario possa essere serializzato in una stringa e deserializzare la stringa nella struttura ad albero originale.

1. Serializzazione

2.Deserializzazione

codice di classe: def serialize(self, root): #Preorder attraversal implementa la serializzazione se root == Nessuno: restituisce 'X,' leftserilized = self.serialize(root.left) dirittiserilizzati = self.serialize(root.right) return str(root.val) ',' leftserilized rightserilized def deserialize(self, data): dati = dati.split(',') root = self.buildTree(dati) restituisce radice def buildTree(sé, dati): val = data.pop(0) #pop il primo carattere if val == 'X': return None #Restituisce un nodo vuoto nodo = TreeNode(val) nodo.sinistra = self.buildTree(dati) nodo.destra = self.buildTree(dati) nodo di ritorno

Tempo: O(n), Spazio: O(n)

Dati i nodi radice p e q di due alberi binari, scrivere una funzione per verificare se i due alberi sono uguali

1. Se entrambi gli alberi binari sono vuoti, allora i due alberi binari sono gli stessi. Se uno e solo uno dei due alberi binari è vuoto, allora i due alberi binari non devono essere uguali

2. Se entrambi gli alberi binari non sono vuoti, determinare innanzitutto se i valori dei relativi nodi radice sono uguali. Se non sono uguali, i due alberi binari devono essere diversi. Se sono uguali, determinare se i sottoalberi sinistro e destro dei due alberi binari sono gli stessi. Questo è un processo ricorsivo, quindi puoi utilizzare la ricerca approfondita per determinare ricorsivamente se due alberi binari sono uguali.

Soluzione di classe: def isSameTree(self, p: TreeNode, q: TreeNode) -> bool: se non p e non q: #Entrambi gli alberi sono vuoti e uguali restituire Vero elif not p o not q: #Solo uno degli alberi è vuoto, i due alberi non sono uguali restituire Falso elif p.val != q.val: restituire Falso altro: return self.isSameTree(p.left, q.left) e self.isSameTree(p.right, q.right)

Complessità temporale: O(\min(m,n))O(min(m,n)), dove mm e n sono rispettivamente il numero di nodi dei due alberi binari. Eseguire una ricerca approfondita su due alberi binari contemporaneamente. Si accederà al nodo solo quando i nodi corrispondenti nei due alberi binari non saranno vuoti, quindi il numero di nodi visitati non supererà il numero di nodi nel più piccolo. albero binario.

Complessità dello spazio: O(\min(m,n))O(min(m,n)), dove mm e n sono rispettivamente il numero di nodi dei due alberi binari. La complessità dello spazio dipende dal numero di livelli di chiamate ricorsive. Il numero di livelli di chiamate ricorsive non supererà l'altezza massima dell'albero binario più piccolo. Nel peggiore dei casi, l'altezza dell'albero binario è uguale al numero di nodi .

1. Determinare innanzitutto se i due alberi binari sono vuoti. Se entrambi gli alberi binari non sono vuoti, avviare la ricerca in ampiezza dai nodi radice dei due alberi binari.

2. Utilizzare due code per memorizzare rispettivamente i nodi di due alberi binari. Inizialmente, i nodi radice dei due alberi binari vengono aggiunti rispettivamente alle due code. Ogni volta viene estratto un nodo dalle due code e viene eseguita la successiva operazione di confronto. Confronta i valori di due nodi. Se i valori dei due nodi non sono uguali, i due alberi binari devono essere diversi; Se i valori di due nodi sono uguali, determinare se i nodi figli dei due nodi sono vuoti Se solo il nodo figlio sinistro di un nodo è vuoto, o il nodo figlio destro di un solo nodo è vuoto, le strutture dei due alberi binari sono diversi Pertanto i due alberi binari devono essere diversi; Se le strutture dei nodi figli dei due nodi sono le stesse, aggiungi rispettivamente i nodi figli non vuoti dei due nodi alle due code. È necessario prestare attenzione all'ordine quando si aggiungono i nodi figli alla coda i nodi figlio sinistro e destro non sono vuoti, aggiungi prima il nodo figlio sinistro, quindi aggiungi il nodo figlio destro

3. Se entrambe le code sono vuote contemporaneamente alla fine della ricerca, i due alberi binari sono gli stessi. Se solo una coda è vuota, la struttura dei due alberi binari è diversa, quindi i due alberi binari sono diversi

Soluzione di classe: def isSameTree(self, p: TreeNode, q: TreeNode) -> bool: se non p e non q: #Entrambi gli alberi sono vuoti e uguali restituire Vero se non p o non q: #Solo uno degli alberi è vuoto, i due alberi non sono uguali restituire Falso coda1 = collezioni.deque([p]) coda2 = collezioni.deque([q]) mentre coda1 e coda2: nodo1 = coda1.popleft() nodo2 = coda2.popleft() se nodo1.val!= nodo2.val: restituire Falso sinistra1, destra1 = nodo1.sinistra, nodo1.destra sinistra2, destra2 = nodo2.sinistra, nodo2.destra if (non left1) ^ (non left2): # ^ significa XOR, se sono diversi, sono 1, se sono uguali, sono 0 restituire Falso if (non giusto1) ^ (non giusto2): restituire Falso if left1: #Inserisci il nodo in coda quando non è vuoto coda1.append(sinistra1) se giusto1: coda1.append(right1) se lasciato2: coda2.append(sinistra2) se giusto2: coda2.append(right2) restituisce non coda1 e non coda2

Complessità temporale: O(\min(m,n))O(min(m,n)), dove mm e n sono rispettivamente il numero di nodi dei due alberi binari. Eseguire una ricerca in ampiezza su due alberi binari contemporaneamente. Si accederà al nodo solo quando i nodi corrispondenti nei due alberi binari non saranno vuoti, quindi il numero di nodi visitati non supererà il numero di nodi nel più piccolo. albero binario.

Complessità dello spazio: O(\min(m,n))O(min(m,n)), dove mm e n sono rispettivamente il numero di nodi dei due alberi binari. La complessità dello spazio dipende dal numero di elementi nella coda. Il numero di elementi nella coda non supererà il numero di nodi dell'albero binario più piccolo.

1. Per qualsiasi albero, la forma di attraversamento del preordine è sempre [Nodo radice, [risultato dell'attraversamento in preordine del sottoalbero sinistro], [risultato dell'attraversamento in preordine del sottoalbero destro]] Cioè, il nodo radice è sempre il primo nodo nell'attraversamento del preordine. La forma di attraversamento in ordine è sempre [ [Risultato dell'attraversamento in ordine del sottoalbero sinistro], nodo radice, [Risultato dell'attraversamento in ordine del sottoalbero destro] ]

2. Finché individuiamo il nodo radice nell'attraversamento in ordine, possiamo conoscere il numero di nodi rispettivamente nel sottoalbero sinistro e nel sottoalbero destro. Poiché le lunghezze dell'attraversamento in preordine e dell'attraversamento in ordine dello stesso sottoalbero sono ovviamente le stesse, possiamo corrispondere ai risultati dell'attraversamento in preordine e individuare tutte le parentesi sinistre e destre nella forma precedente.

3. In questo modo, conosciamo i risultati dell'attraversamento in preordine e dell'attraversamento in ordine del sottoalbero sinistro, e i risultati dell'attraversamento in preordine e dell'attraversamento in ordine del sottoalbero destro Possiamo costruire ricorsivamente il sottoalbero sinistro e il sottoalbero destro, quindi collegare questi due sottoalberi alle posizioni sinistra e destra del nodo radice

4. Ottimizzazione: quando si individua il nodo radice nell'attraversamento in ordine, un metodo semplice consiste nel scansionare direttamente l'intero risultato dell'attraversamento in ordine e trovare il nodo radice list.index(x), ma la complessità temporale di tale operazione è relativamente alto alto. Possiamo prendere in considerazione l'utilizzo di una HashMap per aiutarci a individuare rapidamente il nodo radice. Per ogni coppia chiave-valore nella mappa hash, la chiave rappresenta un elemento (il valore del nodo) e il valore rappresenta la sua posizione di occorrenza nell'attraversamento in ordine. Prima di costruire l'albero binario, possiamo scansionare l'elenco attraversato per costruire una volta questa mappa hash. Nel successivo processo di costruzione dell'albero binario, abbiamo bisogno solo di tempo O(1) per individuare il nodo radice.

1. Ufficialmente ottimizzato, ma ci sono molti parametri. Puoi utilizzare due parametri. Vedi la combinazione di post-ordine e metà ordine.

2. Versione semplice

Complessità temporale: O(n), dove n è il numero di nodi nell'albero

Complessità dello spazio: O(n), oltre allo spazio O(n) richiesto per restituire la risposta, dobbiamo anche usare lo spazio O(n) per memorizzare la mappa hash e O(h) (dove h è l'altezza dell'albero) lo spazio rappresenta lo spazio dello stack durante la ricorsione

1. Usiamo uno stack e un puntatore per assistere nella costruzione dell'albero binario. Inizialmente, il nodo radice (il primo nodo dell'attraversamento in preordine) viene memorizzato nello stack e il puntatore punta al primo nodo dell'attraversamento in ordine "il nodo finale raggiunto dal nodo corrente che si sposta continuamente verso sinistra ."

2. Enumerare ciascun nodo nell'attraversamento del preordine tranne il primo nodo. Se l'indice punta al nodo superiore dello stack, estraiamo continuamente il nodo superiore dello stack e spostiamo l'indice a destra e utilizziamo il nodo corrente come figlio destro dell'ultimo nodo estratto

3. Se l'indice è diverso dal nodo superiore dello stack, utilizziamo il nodo corrente come figlio sinistro del nodo superiore dello stack.

4. Non importa quale sia la situazione, alla fine inseriremo il nodo corrente nello stack

Soluzione di classe: def buildTree(self, preordine: Lista[int], ordine: Lista[int]) -> TreeNode: se non preordinato: ritorno Nessuno root = TreeNode(preordine[0]) pila = [radice] inorderIndex = 0 #Il nodo finale raggiunto dal nodo corrente che si sposta continuamente verso sinistra, coerente con l'attraversamento in ordine for i in range(1, len(preorder)):#Attraversa l'attraversamento del preordine a partire dal secondo nodo preordineVal = preordine[i] nodo = stack[-1] #Il nodo superiore dello stack if node.val != inorder[inorderIndex]: #Quando il nodo superiore dello stack non è uguale, è il figlio sinistro node.left = TreeNode(preorderVal) #Costruisce direttamente il figlio sinistro stack.append(node.left) #Spingi il figlio sinistro nello stack else: #Quando i nodi superiori dello stack sono uguali, è stato attraversato fino al punto più a sinistra e deve essere estratto dallo stack e quindi attraversato fino al figlio destro di un determinato nodo. while stack e stack[-1].val == inorder[inorderIndex]: node = stack.pop() #L'elemento in cima allo stack viene estratto dallo stack inorderIndex = 1 #Sostituisci l'elemento più a sinistra node.right = TreeNode(preorderVal) #Quando i due sono diversi, viene trovato il nodo genitore dell'elemento corrente stack.append(node.right) #Spinge anche l'elemento corrente nello stack restituisce radice

Complessità temporale: O(n), dove n è il numero di nodi nell'albero

Complessità dello spazio: O(n). Oltre allo spazio O(n) richiesto per la risposta restituita, dobbiamo anche utilizzare lo spazio O(h) (dove h è l'altezza dell'albero) per memorizzare lo stack.

1. L'ultimo elemento dell'array attraversato in post-ordine rappresenta il nodo radice e quindi suddiviso in attraversamenti in ordine.

2. Tieni presente che esiste una relazione di dipendenza in cui è necessario creare prima il sottoalbero destro e poi il sottoalbero sinistro. Si può capire che nell'array di attraversamento post-ordine, l'intero array memorizza prima i nodi del sottoalbero sinistro, poi i nodi del sottoalbero destro e infine il nodo radice Se si seleziona "l'ultimo nodo del post-ordine. order traversal" come radice di ogni nodo temporale, il primo costruito dovrebbe essere il sottoalbero destro

1.Ufficiale: due parametri

2. Versione semplice

Complessità temporale: O(n), dove n è il numero di nodi nell'albero

Complessità dello spazio: O(n), oltre allo spazio O(n) richiesto per restituire la risposta, dobbiamo anche usare lo spazio O(n) per memorizzare la mappa hash e O(h) (dove h è l'altezza dell'albero) lo spazio rappresenta lo spazio dello stack durante la ricorsione

1. Se inverti l'attraversamento in ordine, otterrai un attraversamento in ordine inverso, ovvero attraverserai ogni volta il figlio destro, quindi attraverserai il nodo radice e infine attraverserai il figlio sinistro. Se inverti l'attraversamento post-ordine, otterrai l'attraversamento pre-ordine inverso, ovvero attraverserai ogni volta il nodo radice, quindi attraverserai il figlio destro e infine attraverserai il figlio sinistro.

2. La differenza rispetto alla domanda precedente è: tutti i figli di sinistra diventano figli di destra, tutti i figli di destra diventano figli di sinistra e l'attraversamento dell'ordine in avanti viene cambiato in attraversamento dell'ordine inverso.

Soluzione di classe: def buildTree(self, inorder: Lista[int], postorder: Lista[int]) -> TreeNode: se non postordina: ritorno Nessuno root = TreeNode(postordine[-1]) pila = [radice] inorderIndex = -1 #Il nodo finale raggiunto dal nodo corrente che si sposta continuamente verso destra, coerente con l'attraversamento in ordine for i in range(len(postorder)-2, -1,-1):#Attraversa l'attraversamento post-ordine a partire dal penultimo nodo postorderVal = postorder[i] nodo = stack[-1] #Il nodo superiore dello stack if node.val != inorder[inorderIndex]: #Quando il nodo superiore dello stack non è uguale, è il figlio destro node.right = TreeNode(postorderVal) #Costruisce direttamente il figlio destro stack.append(node.right) #Spingi il figlio destro nello stack else: #Quando i nodi superiori dello stack sono uguali, è stato attraversato fino al punto più a destra. Deve essere estratto dallo stack e quindi attraversato fino al figlio sinistro di un determinato nodo. while stack e stack[-1].val == inorder[inorderIndex]: node = stack.pop() #L'elemento in cima allo stack viene estratto dallo stack inorderIndex -= 1 #Sostituisci l'elemento più a destra node.left = TreeNode(postorderVal) #Quando i due sono diversi, viene trovato il nodo genitore dell'elemento corrente stack.append(node.left) #Spinge anche l'elemento corrente nello stack restituisce radice

Complessità temporale: O(n), dove n è il numero di nodi nell'albero

Complessità dello spazio: O(n). Oltre allo spazio O(n) richiesto per la risposta restituita, dobbiamo anche utilizzare lo spazio O(h) (dove h è l'altezza dell'albero) per memorizzare lo stack.

Un percorso è definito come una sequenza che parte da qualsiasi nodo dell'albero, si collega lungo il nodo genitore-nodo figlio e raggiunge qualsiasi nodo. Lo stesso nodo appare al massimo una volta in una sequenza di percorsi. Il percorso contiene almeno un nodo e non passa necessariamente attraverso il nodo radice. La somma del percorso è la somma dei valori di ciascun nodo del percorso. Fornisce la radice del nodo radice di un albero binario e restituisce la somma del percorso massimo

1. Innanzitutto, considera l'implementazione di una funzione semplificata maxGain(node), che calcola il valore del contributo massimo di un nodo nell'albero binario. Nello specifico, cerca il nodo come punto iniziale nel sottoalbero con il nodo come nodo radice. un percorso che massimizza la somma dei valori dei nodi sul percorso

2. Nello specifico, la funzione viene calcolata come segue. Il valore massimo del contributo di un nodo vuoto è pari a 00. Il valore di contributo massimo di un nodo non vuoto è uguale alla somma del valore del nodo e del valore di contributo massimo nei suoi nodi figli (per i nodi foglia, il valore di contributo massimo è uguale al valore del nodo

3. Il processo di calcolo sopra è un processo ricorsivo Pertanto, chiamando la funzione maxGain sul nodo radice, è possibile ottenere il valore massimo del contributo di ciascun nodo.

4. Dopo aver ottenuto il valore massimo del contributo di ciascun nodo secondo la funzione maxGain, come ottenere la somma massima del percorso dell'albero binario? Per un nodo in un albero binario, la somma massima del percorso del nodo dipende dal valore del nodo e dal valore di contributo massimo dei nodi figlio sinistro e destro del nodo. Se il valore di contributo massimo del nodo figlio è positivo, è incluso nella somma massima dei percorsi del nodo, altrimenti non sarà incluso nella somma massima dei percorsi del nodo. Mantenere una variabile globale maxSum per memorizzare la somma massima del percorso e aggiornare il valore di maxSum durante il processo ricorsivo. Il valore finale di maxSum è la somma massima del percorso nell'albero binario.

Soluzione di classe: def __init__(self): self.maxSum = float("-inf") #Il valore massimo viene inizializzato su infinito negativo def maxPathSum(self, root: TreeNode) -> int: def maxGain(node): #Ottiene il valore massimo del contributo del nodo se non nodo: restituire 0 # Calcola ricorsivamente il valore massimo del contributo dei nodi figli sinistro e destro # Solo quando il valore del contributo massimo è maggiore di 0, verrà selezionato il nodo figlio corrispondente Guadagnosinistra = max(Guadagnomax(nodo.sinistra), 0) Guadagnodestro = max(Guadagnomax(nodo.destra), 0) # Prima ottieni il valore massimo del percorso con il nodo corrente come nodo radice, quindi restituisci il valore massimo del contributo del nodo #La somma massima del percorso di un nodo dipende dal valore del nodo e dal valore massimo del contributo dei nodi figli sinistro e destro del nodo priceNewpath = node.val leftGain rightGain self.maxSum = max(self.maxSum, prezzoNuovopercorso) # Aggiorna la risposta # Restituisce il valore massimo del contributo del nodo, che è determinato dal maggiore tra il valore del nodo e il sottoalbero sinistro/sottoalbero destro restituisce nodo.val max(guadagnosinistro, guadagnodestro) guadagno massimo(radice) restituisce self.maxSum

Complessità temporale: O(N)O(N), dove NN è il numero di nodi nell'albero binario. Non più di 2 visite a ciascun nodo

Complessità spaziale: O(N)O(N), dove NN è il numero di nodi nell'albero binario. La complessità dello spazio dipende principalmente dal numero di livelli di chiamata ricorsiva. Il numero massimo di livelli è pari all'altezza dell'albero binario. Nel peggiore dei casi, l'altezza dell'albero binario è pari al numero di nodi dell'albero binario .

Dato un array di numeri interi senza elementi duplicati. Un albero binario massimo costruito direttamente e ricorsivamente da questo array è definito come segue: La radice dell'albero binario è l'elemento più grande nell'array nums. Il sottoalbero sinistro è il più grande albero binario costruito ricorsivamente attraverso la parte sinistra del valore massimo dell'array. Il sottoalbero destro è il più grande albero binario costruito ricorsivamente attraverso la parte destra del valore massimo dell'array. Restituisce l'albero binario più grande costruito con i numeri dell'array specificati

Ancora una trilogia 1. Condizione di terminazione della ricorsione: quando gli array del sottoalbero sinistro e del sottoalbero destro sono entrambi vuoti 2. Cosa fa questa ricorsione: elimina il valore massimo dell'array, divide l'array in array sinistro e destro in base al valore massimo, quindi esegue l'assegnazione ricorsiva 3. Cosa viene restituito: il nodo radice del sottoalbero

Soluzione di classe: def buildMaximumBinaryTree(self, nums: List[int]) -> TreeNode: se non sono numeri: restituisci Nessuno # Applicabile quando sono presenti elementi ripetuti # max_v, m_i = float(-inf), 0 # per i, v in enumerate(nums): # se v>max_v: #v_massimo = v #m_i = io max_v = max(numeri) m_i = numeri.indice(max_v) radice = TreeNode(max_v) root.left = self.constructMaximumBinaryTree(nums[:m_i]) root.right = self.constructMaximumBinaryTree(nums[m_i 1:]) restituisce radice

Complessità temporale: O(n^2), il costrutto del metodo viene chiamato n volte in totale. Ogni volta che cerchi ricorsivamente il nodo radice, devi attraversare tutti gli elementi nell'intervallo dell'indice corrente per trovare il valore massimo. In generale, la complessità di ogni attraversamento è O(logn) e la complessità totale è O(nlogn). Nel peggiore dei casi, l'array numsnums viene ordinato e la complessità totale è O(n^2)

Complessità spaziale: O(n)O(n). La profondità della chiamata ricorsiva è nn. In media, la profondità della chiamata ricorsiva per un array di lunghezza n è O(logn)

1. Costruisci una pila decrescente e inseriscila nella pila in sequenza Se l'elemento in cima alla pila è più piccolo dell'elemento corrente, l'elemento in cima alla pila viene estratto dalla pila.

2. Confronta la dimensione dell'elemento in alto dopo essere stato estratto dallo stack con la dimensione dell'elemento corrente. Se è più grande dell'elemento corrente, l'elemento corrente viene utilizzato come nodo genitore e l'elemento estratto viene utilizzato come nodo figlio sinistro; se l'elemento superiore dello stack è più piccolo dell'elemento corrente, l'elemento superiore dello stack viene utilizzato come nodo genitore e lo estrae dallo stack. L'elemento precedentemente estratto viene utilizzato come figlio destro e continua finché il nodo corrente non viene inserito nello stack.

3. Fino alla fine dell'ultimo elemento, viene formato uno stack decrescente e lo stack viene estratto in sequenza vengono utilizzati come figli giusti. L'ultimo estratto dallo stack è il nodo radice .

Esempio

public TreeNode buildMaximumBinaryTree(int[] nums) { TreeNode root = null, nodo = null; Stack LinkedList<TreeNode> = new LinkedList<>(); for (int i = 0; i < numeri.lunghezza; i) { nodo = nuovo TreeNode(nums[i]); //Costruisce uno stack decrescente Quando l'elemento superiore dello stack è più piccolo dell'elemento corrente, l'elemento superiore dello stack verrà estratto dallo stack. while (!stack.isEmpty() && stack.peek().val < node.val) { root = stack.pop();//L'elemento superiore dello stack corrente, il valore più piccolo //Confronta la dimensione della parte superiore dello stack dopo l'estrazione con la dimensione dell'elemento corrente. Se è più grande dell'elemento corrente, l'elemento corrente verrà utilizzato come nodo genitore. if (stack.isEmpty() || stack.peek().val > node.val) { nodo.sinistra = radice; } else {//Se è inferiore all'elemento corrente, l'elemento superiore dello stack verrà utilizzato come nodo principale stack.peek().right = root; } } stack.push(node);//Spinge l'elemento corrente nello stack } // Lo stack decrementale è completamente formato e può essere estratto come figlio destro. while (!stack.isEmpty()) { radice = stack.pop(); if (!stack.isEmpty()) { stack.peek().right = root; } } return root;//L'ultima cosa che esce dallo stack è root, ritorna a questo nodo }

Complessità temporale: O(n), Complessità spaziale: O(n)

Definizione massima di albero: un albero in cui il valore di ciascun nodo è maggiore di qualsiasi altro valore nel suo sottoalbero dà il nodo radice radice dell'albero più grande. Come la domanda precedente, l'albero dato è costruito ricorsivamente dalla lista A, non ci viene dato A direttamente, solo un nodo radice root, assumendo che B sia una copia di A con il valore val aggiunto alla fine. I dati della domanda garantiscono che i valori in B siano diversi. Costrutto di ritorno(B)

Ogni volta che viene confrontato con il nodo testa, se è più piccolo, viene controllato il suo nodo destro. Aggiornamento: 1) Il nodo esistente diventa il nodo sinistro del nuovo nodo, 2) il nuovo nodo diventa il nodo destro del nodo genitore

def insertIntoMaxTree(self, root: TreeNode, val: int) -> TreeNode: # dummy variabile fittizia, il suo figlio destro punta al nodo radice fittizio = TreeNode(0) manichino.destra = radice # search Se il valore corrente del nodo radice è maggiore di val, continua a interrogare il suo figlio destro p, c = manichino, manichino.giusto mentre c e c.val > val: p, c = c, c.destra # insert In questo momento, val è maggiore del nodo radice, val viene utilizzato come figlio destro del nodo radice precedente e il nodo radice corrente viene utilizzato come figlio sinistro di val n = NodoAlbero(val) p.destra = n n.sinistra = c return dummy.right #dummy non è cambiato, il suo figlio destro punta al nodo radice

La stessa elaborazione viene eseguita quando è maggiore del nodo radice. Quando è inferiore al nodo radice, il figlio destro del nodo radice viene elaborato in modo ricorsivo.

def insertIntoMaxTree(self, root: TreeNode, val: int) -> TreeNode: se root è None: # Condizione di terminazione ricorsiva returnTreeNode(val) if val > root.val: #Come gestire val maggiore del nodo radice corrente tmp = TreeNode(val) tmp.sinistra = radice restituire tmp # Elabora ricorsivamente il figlio destro del nodo radice root.right = self.insertIntoMaxTree(root.right, val) return root # Valore restituito ricorsivo, nodo root

Dato un albero binario, determinare se si tratta di un albero binario con altezza bilanciata. In questa domanda, un albero binario con altezza bilanciata è definito come: il valore assoluto della differenza di altezza tra i sottoalberi sinistro e destro di ciascun nodo di un albero binario non supera 1

1. Definire la funzione altezza, che viene utilizzata per calcolare l'altezza di qualsiasi nodo p nell'albero binario.

2. Similmente all'attraversamento in preordine di un albero binario, ovvero, per il nodo attualmente attraversato, calcolare prima l'altezza dei sottoalberi sinistro e destro. Se la differenza di altezza tra i sottoalberi sinistro e destro non supera 1, allora attraversa ricorsivamente rispettivamente i sottonodi sinistro e destro e determina se i sottoalberi sinistro e destro sono bilanciati. Questo è un processo ricorsivo top-down

Soluzione di classe: #Top-down, simile all'attraversamento del preordine, calcolerà ripetutamente l'altezza dei sottoalberi sinistro e destro def isBalanced(self, root: TreeNode) -> bool: def altezza(root: TreeNode) -> int: se non root: restituire 0 return max(altezza(root.sinistra), altezza(root.right)) 1 se non root: restituire Vero return abs(altezza(radice.sinistra) - altezza(radice.destra)) <= 1 e self.isBalanced(root.left) e self.isBalanced(root.right)

Complessità temporale: O(n), dove n è il numero di nodi nell'albero binario. Utilizzando la ricorsione dal basso verso l'alto, l'altezza di calcolo di ciascun nodo e il giudizio se è bilanciato devono essere elaborati solo una volta. Nel peggiore dei casi, tutti i nodi dell'albero binario devono essere attraversati, quindi la complessità temporale è O(. N)

Complessità spaziale: O(n), dove n è il numero di nodi nell'albero binario. La complessità dello spazio dipende principalmente dal numero di livelli di chiamate ricorsive. Il numero di livelli di chiamate ricorsive non supererà nn.

1. Poiché il metodo uno è ricorsivo top-down, la funzione \texttt{height}height verrà chiamata ripetutamente per lo stesso nodo, con conseguente elevata complessità temporale. Se viene utilizzato l'approccio bottom-up, la funzione \texttt{height}height verrà chiamata solo una volta per ciascun nodo.

2. L'approccio ricorsivo dal basso verso l'alto è simile all'attraversamento post-ordine. Per il nodo attualmente attraversato, determinare prima in modo ricorsivo se i suoi sottoalberi sinistro e destro sono bilanciati, quindi determinare se il sottoalbero con radice nel nodo corrente è bilanciato. Se un sottoalbero è bilanciato, viene restituita la sua altezza (l'altezza deve essere un numero intero non negativo), altrimenti viene restituito -1−1. Se è presente un sottoalbero sbilanciato, l'intero albero binario deve essere sbilanciato

Soluzione di classe: #Bottom-up, simile all'attraversamento post-ordine, determinare prima i sottoalberi sinistro e destro, quindi determinare il nodo radice, assicurandosi che l'altezza di ciascun nodo venga calcolata solo una volta def isBalanced(self, root: TreeNode) -> bool: def altezza(root: TreeNode) -> int: se non root: restituire 0 altezzasinistra = altezza(root.sinistra) altezzadestra = altezza(radice.destra) se leftHeight == -1 o rightHeight == -1 o abs(leftHeight - rightHeight) > 1: ritorno -1 altro: return max(altezzasinistra, altezzadestra) 1 restituisce altezza(radice) >= 0

Complessità temporale: O(n), dove n è il numero di nodi nell'albero binario. Utilizzando la ricorsione dal basso verso l'alto, l'altezza di calcolo di ciascun nodo e il giudizio se è bilanciato devono essere elaborati solo una volta. Nel peggiore dei casi, tutti i nodi dell'albero binario devono essere attraversati, quindi la complessità temporale è O(. N)

Complessità spaziale: O(n), dove n è il numero di nodi nell'albero binario. La complessità dello spazio dipende principalmente dal numero di livelli di chiamate ricorsive. Il numero di livelli di chiamate ricorsive non supererà nn.

Dato un albero binario, determinarne la profondità minima. La profondità minima è il numero di nodi sul percorso più breve dal nodo radice al nodo foglia più vicino

1. La chiave di questa domanda è capire la condizione finale ricorsiva La definizione di nodo foglia è che quando sia il figlio sinistro che quello destro sono nulli, viene chiamato nodo foglia. Quando i figli sinistro e destro del nodo radice sono vuoti, restituisce 1 Quando uno dei figli sinistro e destro del nodo radice è vuoto, restituisce la profondità del nodo figlio che non è vuoto. Quando entrambi i figli sinistro e destro del nodo radice sono vuoti, restituiscono i valori del nodo della profondità minore dei figli sinistro e destro.

Soluzione di classe: def minDepth(self, root: TreeNode) -> int: se non root: restituire 0 #Quando entrambi i sottoalberi sinistro e destro sono vuoti, si tratta di un nodo foglia e la distanza di ritorno è 1 se non root.left e non root.right: ritorno 1 profondità_min = 10**9 se root.left: #Il sottoalbero sinistro esiste, confronta la distanza minima del sottoalbero sinistro con la distanza minima corrente profondità_min = min(self.profonditàmin(root.sinistra), profondità_min) se root.destra: profondità_min = min(self.profonditàmin(root.right), profondità_min) restituisce min_profondità 1

Complessità temporale: O(n), dove n è il numero di nodi nell'albero. Visita ogni nodo una volta

Complessità spaziale: O(h), dove h è l'altezza dell'albero. La complessità dello spazio dipende principalmente dal sovraccarico dello spazio dello stack durante la ricorsione. Nel peggiore dei casi, l'albero appare a forma di catena e la complessità dello spazio è O(n). In media, l’altezza dell’albero è positivamente correlata al logaritmo del numero di nodi e la complessità spaziale è O(logN)

Quando troviamo un nodo foglia, restituiamo direttamente la profondità del nodo foglia. La natura della ricerca in ampiezza garantisce che la profondità del primo nodo foglia cercato sia la più piccola.

Soluzione di classe: def minDepth(self, root: TreeNode) -> int: se non root: restituire 0 que = collezioni.deque([(root, 1)]) mentre que: nodo, profondità = que.popleft() #Il primo nodo foglia deve essere il nodo foglia più vicino se non node.left e non node.right: profondità di ritorno se nodo.sinistra: que.append((nodo.sinistra, profondità 1)) se nodo.destra: que.append((nodo.destra, profondità 1)) restituire 0

Complessità temporale: O(n), dove n è il numero di nodi nell'albero. Visita ogni nodo una volta

Complessità spaziale: O(n), dove n è il numero di nodi nell'albero. La complessità dello spazio dipende principalmente dal sovraccarico della coda. Il numero di elementi nella coda non supererà il numero di nodi nell'albero.

La definizione di dp[i] è: il valore di Fibonacci dell'i-esimo numero è dp[i]

Equazione di transizione di stato dp[i] = dp[i - 1] dp[i - 2]

La domanda ci fornisce anche direttamente come inizializzare dp[0] = 0;dp[1] = 1;

dp[i] dipende da dp[i - 1] e dp[i - 2], quindi l'ordine di attraversamento deve essere dalla parte anteriore a quella posteriore.

Quando N è 10, l'array dp dovrebbe essere la seguente sequenza: 0 1 1 2 3 5 8 13 21 34 55 Se il codice viene scritto e il risultato risulta errato, stampare l'array dp per vedere se è coerente con la sequenza che abbiamo derivato.

C'è un modo per salire le scale fino al primo piano e ci sono due modi per salire le scale fino al secondo piano. Quindi fai altri due gradini sulla prima rampa di scale per raggiungere il terzo piano, e un altro gradino sulla seconda rampa di scale per raggiungere il terzo piano. Quindi lo stato delle scale fino al terzo piano si può dedurre dallo stato delle scale fino al secondo piano e dallo stato delle scale fino al primo piano, quindi si può pensare ad una programmazione dinamica.

dp[i]: Ci sono modi dp[i] per salire alla i-esima scala

Dalla definizione di dp[i] si vede che dp[i] può essere derivato in due direzioni. Il primo è dp[i - 1]. Ci sono dp[i - 1] modi per salire le scale i-1, quindi saltare un gradino alla volta è dp[i]. C'è anche dp[i - 2]. Ci sono dp[i - 2] modi per salire le scale i-2. Quindi saltare due gradini in un unico gradino è dp[i]. Allora dp[i] è la somma di dp[i - 1] e dp[i - 2]! Quindi dp[i] = dp[i - 1] dp[i - 2]

Quindi se i è 0, cosa dovrebbe essere dp[i] Ci sono molte spiegazioni per questo, ma fondamentalmente sono spiegate direttamente nella risposta.

Ad esempio, esiste un modo per sforzarsi di consolarsi e salire allo 0° piano. Anche non fare nulla è un modo: dp[0] = 1, che equivale a stare direttamente in cima all'edificio.

Pensavo che quando correvo al piano 0, il metodo era 0. Potevo fare solo uno o due passi alla volta. Tuttavia, il piano era 0. Stavo semplicemente in cima all'edificio, quindi non esisteva alcun metodo dp[0] dovrebbe essere 0.

La maggior parte dei motivi per cui dp[0] dovrebbe essere 1 sono in realtà perché se dp[0]=1, posso superare il problema partendo da 2 durante il processo di ricorsione e quindi fare affidamento sul risultato per spiegare dp[0] = 1

La domanda afferma che n è un numero intero positivo, ma non dice affatto che n sia 0. Pertanto, questa domanda non dovrebbe discutere l'inizializzazione di dp[0].

Il mio principio è: non considerare l'inizializzazione di dp[0], inizializzare solo dp[1] = 1, dp[2] = 2, quindi iniziare la ricorsione da i = 3, in modo che soddisfi la definizione di dp[i ]

Si vede dalla formula ricorsiva dp[i] = dp[i - 1] dp[i - 2] che l'ordine di attraversamento deve essere dal davanti al dietro.

Quando N è 10, l'array dp dovrebbe essere la seguente sequenza: 0 1 1 2 3 5 8 13 21 34 55