Grafico, non testato spesso
definizione
Nodi collegati tra loro sotto forma di rete
il termine
Bordo: bordo, una coppia di nodi
Algoritmo di attraversamento
Prima ricerca in ampiezza DFS
Profondità Prima ricerca TFS
Intervista relativa
Implementare prima la ricerca in ampiezza e profondità
Controlla se il grafico è un albero
Contare il numero di archi in un grafico
Trova la distanza più breve tra due vertici
Stack monotono Lo stack monotono viene testato raramente
Deque a coda doppia, raramente testato
Union Find viene testato raramente
Gli alberi dei segmenti di linea vengono testati raramente
Array di alberi Albero indicizzato binario, BIT, raramente testato
Albero del dizionario Trie, raramente testato
definizione
Conosciuto anche come: albero dei prefissi, una speciale struttura dati ad albero
utilizzo
Molto efficace nel risolvere i problemi relativi alle stringhe
Fornire una ricerca rapida
Cerca una parola in un dizionario
Suggerimenti automatici nei motori di ricerca
colloquio
Contare il numero totale di parole nell'albero del dizionario
Stampa tutte le parole memorizzate nell'albero del dizionario
Ordina gli elementi in un array utilizzando un albero del dizionario
Formare parole da un dizionario utilizzando un albero del dizionario
Costruisci dizionario T9: albero del dizionario DFS
Tabella hash/Mappa hash Tabella hash, spesso testata
definizione
Archiviare oggetti identificati in modo univoco sotto forma di coppie chiave-valore
Dizionario: una raccolta di coppie chiave-valore
Cerca il valore dell'oggetto utilizzando la chiave chiave
HashSet/HashMap in Java, unordered_map in C, dict in Python
Operazioni supportate: O(1) Inserisci / O(1) Trova / O(1) Elimina
Come funzionano le tabelle hash
<br>Principio di funzionamento: per set. La chiave ottiene un indice tramite la funzione hash, quindi il valore viene archiviato nell'array. <br>Per get, trova l'indice tramite le funzioni chiave e hash e ottieni il valore.
Perché la complessità temporale delle varie operazioni sull’hash non può essere semplicemente considerata pari a O(1)?
La chiave può essere una stringa, un numero intero o qualcosa di lunghezza sconosciuta. Pertanto è opportuno utilizzare O(L); in senso stretto, la complessità temporale di qualsiasi operazione è O(keySize) anziché O(1)<br>
Come implementare la funzione hash
Come risolvere la collisione di hash (Collisione)
Collisione significa che due chiavi diverse ottengono due valori identici dopo il calcolo tramite la funzione hash. Esistono due modi principali per risolvere i conflitti:<br>Aprire l'hashing. Significa che nell'array su cui si basa la tabella hash, ogni posizione è il nodo testa di una Linked List. In questo modo, le tuple <chiave, valore> in conflitto vengono inserite nello stesso elenco collegato. <br>Hashing chiuso. Ciò significa che quando si verifica un conflitto, gli elementi successivi andranno alla posizione successiva per trovare uno spazio vuoto<br>
Come espandere continuamente la tabella hash?
fattori di prestazione
Dimensioni della tabella hash
Metodo di gestione delle collisioni
colloquio
Trova coppie chiave-valore simmetriche in un array
La tabella hash verrà utilizzata in modo flessibile per risolvere il problema?
Conosci i principi di base delle tabelle hash?
Traccia il percorso completo per comodità
Scopri se un array è un sottoinsieme di un altro array
Controlla se gli array specificati sono disgiunti
526. Bilanciatore del carico<br>
134. Strategia cache LRU<br>657. Inserisci Elimina GetRandom O(1)<br>954. Inserisci Elimina GetRandom O(1) - Duplicati consentiti<br>209
Problemi di classe del flusso di dati<br>960. Primo numero univoco in uno stream II<br>138 Somma di sottoarray<br>105 Copia di un elenco collegato con puntatori casuali<br>171 Stringa fuori ordine 124. sequenza continua più lunga
Ordina la ricerca
ordinare
ordinamento di inserimento
ordinamento della selezione
Trovare
tabella di ricerca statica
tabella di ricerca dinamica
Definizione della struttura dati: una struttura dati può essere considerata come una raccolta di dati e diverse operazioni (funzioni) definite su questa raccolta.
Metodo di prova 1: chiedere informazioni sui principi di base di una determinata struttura dati e chiederne l'implementazione
Esempio: parlare del principio Hash e implementare una tabella Hash
Metodo di test 2: utilizzare un qualche tipo di struttura dati per completare le cose
Esempio: unisci K array ordinati
Metodo di test 3: Implementare una struttura dati per fornire alcune funzioni specifiche
Esempio: il problema dell'elemento K con la frequenza più alta
complessità temporale:
Descrivi la complessità temporale di più interfacce<br>
Ad esempio, è necessario progettare una struttura dati Set
Algoritmo 1:O(n) lowerBound O(1) add
Metodo di implementazione: utilizzare l'archiviazione dell'array, confrontare ogni volta e inserire direttamente alla fine dell'array
Algoritmo 2:O(logn) lowerBound O(logn) add
Metodo di implementazione: utilizzare l'archiviazione dell'albero rosso-nero, TreeSet in Java, mappa in C
Array Array, più comunemente testato
tipo
sottoarray
Domande di un'intervista
41. 42,43, Sottoarray massimo<br>44. Sottoarray minimo<br>138
Problema dell'intervallo dell'array
Domande di un'intervista
30. Inserimento di intervalli<br>793. Intersezione di più array<br>156
problema di ordinamento esterno
Definizione: l'algoritmo di ordinamento esterno si riferisce a un algoritmo per l'ordinamento dei dati archiviati in uno o più file di grandi dimensioni quando la memoria non è sufficiente. <br>
Due passaggi fondamentali:<br>Tagliare il file di grandi dimensioni in diversi file di piccole dimensioni e utilizzare la memoria per ordinarli rispettivamente<br>Utilizzare l'algoritmo di unione K-way (k-way merge) per ordinare diversi file di piccole dimensioni Unire in un unico file di grandi dimensioni
Domande di un'intervista
486. Unisci array ordinati K<br>104
Operazioni sui bit
Definizione: operazioni su bit binari
Domande di un'intervista
365. Quanti 1 ci sono in binario<br>
Gli array di alberi vengono raramente considerati
Conosciuto anche come: Fenwick Tree Nome inglese: Binary Indexed Tree Abbreviazione: BIT è implementato in base al prefisso e alle informazioni<br>
Sebbene il nome sia Tree, è memorizzato in un array (Array)<br>BIT è un multi-albero e la relazione genitore-figlio rappresenta la relazione di inclusione<br>Utilizza getPrefixSum(k) per implementare getRangeSum(x, y )
complessità temporale
Log(n) Modifica il valore in qualsiasi posizione<br>Log(n) Interroga la somma di qualsiasi intervallo
Caratteristiche
Per un array con N numeri, sono supportate le seguenti funzioni:<br>update(index, val) //Aggiorna il valore in una posizione nell'array entro logN tempo getPrefixSum(k) //Ottienilo entro log(K) tempo La somma dei primi K numeri nell'array
Domande di un'intervista
817. Variabile-somma elemento matrice intervallo<br>249 Conta il numero di numeri precedenti inferiori a se stesso
Intervista relativa
Trova il secondo elemento più piccolo in un array
Trova il primo numero intero non ripetitivo
Riorganizzare i valori positivi e negativi in un array
65. Mediana di due array ordinati, problema difficile<br>
6. Unisci array ordinati II<br>64. Unisci array ordinati<br>839 Unisci due elenchi di intervalli ordinati<br>486. Unisci elenchi di intervalli ordinati K<br>577 due array<br>548. Intersezione di due array II<br>793. Intersezione di più array<br>654 Moltiplicazione di matrici sparse<br>931 Mediana di K array ordinati<br>149 tempo<br>405. Sottomatrice la cui somma è zero<br>944. Sottomatrice massima<br>943 Query somma intervallo - Immutabile<br>665 Somma intervallo variabile del piano
Stack Stack, non testato spesso
definizione
LIFO. Ad esempio, nel carico logistico, le merci caricate successivamente vengono scaricate per prime.
Operazioni supportate: O(1) Push / O(1) Pop / O(1) Top
applicazione
Utilizzato per l'attraversamento non ricorsivo di alberi binari, il calcolo di espressioni polacche inverse, ecc.
La struttura dati principale dell'implementazione non ricorsiva di DFS
Nella ricerca in ampiezza (BFS), vengono registrati i nodi da espandere.
Le code possono essere utilizzate per implementare code di messaggi per completare attività asincrone.
Quando la velocità di produzione e consumo dei messaggi non è costante, è necessaria una coda di messaggi per archiviare temporaneamente i messaggi che sono stati inviati ma non ricevuti.
Implementare la modalità stack
Utilizzare una struttura di archiviazione (array di uso comune, elenchi occasionalmente collegati) per archiviare gli elementi
Utilizzare un array per implementare tre stack?
Implementare uno stack utilizzando due code? <br>
la differenza
Gli array hanno prestazioni migliori per l'accesso casuale. <br>Gli elenchi collegati hanno prestazioni migliori per l'inserimento e l'eliminazione di elementi.
Esercizi<br>
lintcode: 495. Implementa lo stack
494. Stack di implementazione della coda doppia<br>
224. Utilizza un array per implementare tre stack<br>
operare
spingere, inserire l'elemento in alto
pop ritorna e rimuove l'elemento in cima allo stack
isEmptyLo stack è vuoto e restituisce true
top restituisce l'elemento superiore senza rimuoverlo
Java utilizza java.util.Stack, che si estende dalla classe Vector e supporta operazioni come push(), pop(), peek(), empty() e search().
C, basta usare lo stack in <stack>. Il metodo è simile a Java, tranne per il fatto che peek() in C è chiamato top() e quando pop() il valore restituito è vuoto.
Python, usa list direttamente, usa operazioni di slicing come [-1] per visualizzare la parte superiore dello stack, usa list.pop() quando estrai la parte superiore dello stack e usa list.append() quando spingi la parte superiore dello stack . <br>
Intervista relativa
Utilizzo dello stack per valutare le espressioni suffisse
Ordina gli elementi della pila
Determina se un'espressione è bilanciata tra parentesi
QueueQueue, spesso testato
definizione
FIFO struttura dati lineare di archiviazione sequenziale first-in-first-out, cassa del supermercato
Operazioni supportate: O(1) Push / O(1) Pop / O(1) Top
applicazione
Utilizzato come struttura dati principale per l'algoritmo BFS
operare
Inserisci gli elementi alla fine della coda di accodamento
dequeue rimuove l'elemento head della coda
La colonna isEmpty è vuota e restituisce true
top restituisce il primo elemento della coda
Metodo per realizzare
Implementare la coda utilizzando l'elenco collegato?
Implementare una coda con due stack? <br>
Implementare la coda utilizzando l'array circolare?
Esercizio: 955. Implementa la coda tramite array circolare<br>
colloquio
Usa la coda per rappresentare lo stack
Invertire i primi k elementi della coda
Utilizza una coda per generare numeri binari da 1 a n
642. Media mobile dal flusso di dati<br>
955. Implementa la coda tramite array circolare<br>
Elenco collegato, spesso testato
definizione
Catena di nodi: ogni nodo contiene dati e puntatori ai nodi successivi
utilizzo
Implementare file system, tabella hash, elenco di adiacenze
tipo
elenco collegato unidirezionale
Elenco doppiamente collegato
operare
isEmpty, è vuoto, restituisce true
colloquio
Rileva cicli in elenchi collegati
Restituisce l'ennesimo nodo dall'ultimo nell'elenco collegato
Rimuovi i duplicati dall'elenco collegato
AlberoAlbero
definizione
struttura gerarchica dei dati
Costituito da vertici e spigoli
Non ci sono cicli nell'albero come mostrato nel grafico
tipo
Gli alberi dei segmenti di linea sostanzialmente non sono testati, sono universali.
Albero binario, spesso testato
albero di ricerca binario
Definizione: il sottoalbero sinistro è più piccolo del nodo radice e il nodo radice è più piccolo del sottoalbero destro. L'effetto è: il lato sinistro è sempre più piccolo del lato destro
albero binario bilanciato
Albero bilanciato (albero AVL)
definizione:
È un albero vuoto oppure il valore assoluto della differenza di altezza tra i sottoalberi sinistro e destro non supera 1 e i sottoalberi sinistro e destro sono entrambi alberi binari bilanciati.
Implementazione
Albero rosso-nero, AVL, albero del capro espiatorio, Treap, albero che si diffonde
mucchio
Definizione: un heap è un albero binario bilanciato. Il nodo genitore è più piccolo del nodo figlio in eccesso vengono posizionati il più possibile sul nodo figlio sinistro. Non esiste alcuna relazione di dimensione tra i nodi figlio sinistro e destro. Può essere implementato utilizzando gli array<br>
Operazioni supportate: O(log N) Aggiungi / O(log N) Rimuovi / O(1) Min o Max
Heap massimo vs Heap minimo
Caratteristiche del valore: per l'heap minimo, il nodo padre è più piccolo del nodo figlio e non esiste alcuna relazione di dimensione tra i nodi figlio sinistro e destro, per l'heap di tipo massimo, il nodo padre è più grande del nodo figlio e lì non esiste alcuna relazione di dimensione tra i nodi secondari sinistro e destro;
Caratteristiche strutturali: È un albero binario con altezza logN
Complessità temporale: la complessità di eliminazione e pop sono tutte logN, trova complessità minima o massima O(1)<br>
Metodo di inserimento: inserisci sempre da sinistra, garantendo un albero binario bilanciato. Se il numero inserito è piccolo, spostalo verso l'alto e il nodo genitore si sposta verso il basso. Quindi la complessità massima è logN<br>
Il metodo di eliminazione è simile a
Metodo di implementazione: Esercizio: lintcode 130 heapify<br>
Domande pratiche per l'intervista
104. Unisci K elenchi ordinati<br>612. K punti più vicini<br>545. Top K Big Numbers II<br>613 Risultati eccellenti<br>486 cifre<br>544. Primi K numeri grandi<br>401 Il numero k-esimo dal piccolo al grande nella matrice di ordinamento
Albero dei segmenti<br>
Definizione: l'albero dei segmenti di linea è una struttura dati avanzata e una struttura ad albero, per essere precisi, è un albero binario. Può gestire in modo efficiente problemi come le query di modifica dell'intervallo. <br>
Nota: Fondamentalmente non è testato, ma se riesci a padroneggiarlo, puoi risolvere molti problemi in una volta sola. L'albero dei segmenti di linea è implementato in base al metodo divide et impera e può essere utilizzato come buona pratica per la divisione e metodo di conquista.
colloquio
Trova l'altezza di un albero binario
Trova il k-esimo valore massimo in un albero di ricerca binario
Trova il nodo che dista k dal nodo radice
Trova i nodi antenati di un dato nodo in un albero binario
104. Unisci elenchi ordinati K<br>
3 modi
Metodo 1: utilizzare PriorityQueue
Metodo 2: algoritmo di divisione e conquista simile all'ordinamento di unione
Metodo 3: algoritmo di fusione a coppie dal basso verso l'alto
La complessità temporale è O(NlogK)
Combinato con: algoritmo Jiuzhang
Le domande pratiche sono tutte domande lintcode
Wondershare EdrawMind
