Diagramm, nicht oft getestet
Definition
Knoten, die in Form eines Netzwerks miteinander verbunden sind
der Begriff
Kante: Kante, ein Knotenpaar
Interviewbezogen
Implementieren Sie zuerst die Breiten- und Tiefensuche
Überprüfen Sie, ob es sich bei dem Diagramm um einen Baum handelt
Zählen Sie die Anzahl der Kanten in einem Diagramm
Finden Sie den kürzesten Abstand zwischen zwei Eckpunkten
Monotoner Stapel Monotoner Stapel wird selten getestet
Doppelendige Warteschlange Deque, selten getestet
Union Find wird selten getestet
Liniensegmentbäume werden selten getestet
Baumarray Binary Indexed Tree, BIT, selten getestet
Wörterbuchbaumversuch, selten getestet
Definition
Auch bekannt als: Präfixbaum, eine spezielle baumartige Datenstruktur
verwenden
Sehr effektiv bei der Lösung von Saitenproblemen
Bieten Sie eine schnelle Suche
Suchen Sie ein Wort in einem Wörterbuch
Automatische Vorschläge in Suchmaschinen
Interview
Zählen Sie die Gesamtzahl der Wörter im Wörterbuchbaum
Drucken Sie alle im Wörterbuchbaum gespeicherten Wörter
Sortieren Sie Elemente in einem Array mithilfe eines Wörterbuchbaums
Bilden Sie mithilfe eines Wörterbuchbaums Wörter aus einem Wörterbuch
T9-Wörterbuch erstellen: Wörterbuchbaum DFS
Hash-Tabelle/Hash Map Hash-Tabelle, oft getestet
Definition
Speichern Sie eindeutig identifizierte Objekte in Form von Schlüssel-Wert-Paaren
Wörterbuch: eine Sammlung von Schlüssel-Wert-Paaren
Objektwert mit Schlüssel suchen
HashSet/HashMap in Java, unordered_map in C, dict in Python
Unterstützte Operationen: O(1) Einfügen / O(1) Suchen / O(1) Löschen
Wie Hash-Tabellen funktionieren
<br>Funktionsprinzip: Für Set. Der Schlüssel erhält über die Hash-Funktion einen Index und der Wert wird dann im Array gespeichert. <br>Suchen Sie für get den Index über die Schlüssel- und Hash-Funktionen und rufen Sie den Wert ab.
Warum kann die zeitliche Komplexität verschiedener Hash-Operationen nicht einfach als O(1) betrachtet werden?
Der Schlüssel kann eine Zeichenfolge, eine Ganzzahl oder etwas unbekannter Länge sein. Daher ist es angemessen, O(L) zu verwenden; im strengen Sinne beträgt die Zeitkomplexität jeder Operation O(keySize) und nicht O(1)<br>
So implementieren Sie eine Hash-Funktion
So lösen Sie eine Hash-Kollision (Kollision)
Kollision bedeutet, dass zwei verschiedene Schlüssel nach der Berechnung durch die Hash-Funktion zwei identische Werte erhalten. Es gibt im Wesentlichen zwei Möglichkeiten, Konflikte zu lösen:<br>Offenes Hashing. Das bedeutet, dass in dem Array, auf dem die Hash-Tabelle basiert, jede Position der Kopfknoten einer verknüpften Liste ist. Auf diese Weise werden widersprüchliche <Schlüssel, Wert>-Tupel in derselben verknüpften Liste platziert. <br>Geschlossenes Hashing. Dies bedeutet, dass bei einem Konflikt die nachfolgenden Elemente zur nächsten Position wechseln, um einen leeren Raum zu finden<br>
Wie lässt sich die Hash-Tabelle kontinuierlich erweitern?
Leistungsfaktoren
Methode zur Kollisionsbehandlung
Interview
Finden Sie symmetrische Schlüssel-Wert-Paare in einem Array
Wird die Hash-Tabelle flexibel eingesetzt, um das Problem zu lösen?
Beherrschen Sie die Grundprinzipien von Hash-Tabellen?
Verfolgen Sie zur Vereinfachung den gesamten Pfad
Finden Sie heraus, ob ein Array eine Teilmenge eines anderen Arrays ist
Überprüft, ob die angegebenen Arrays disjunkt sind
134. LRU-Cache-Strategie<br>657. Insert Delete GetRandom O(1)<br>954. Duplikate zulässig<br>209
Datenstrom-Klassenprobleme<br>960. Erste eindeutige Zahl in einem Stream II<br>138. Summe der Subarrays<br>171 124. längste fortlaufende Sequenz
Suche sortieren
Sortieren
Zusammenführen, sortieren
Finden
statische Nachschlagetabelle
dynamische Nachschlagetabelle
Datenstrukturdefinition: Eine Datenstruktur kann als eine Datenspeichersammlung und mehrere für diese Sammlung definierte Operationen (Funktionen) betrachtet werden.
Testmethode 1: Fragen Sie nach den Grundprinzipien einer bestimmten Datenstruktur und bitten Sie um deren Umsetzung
Beispiel: Sprechen Sie über das Prinzip von Hash und implementieren Sie eine Hash-Tabelle
Testmethode 2: Verwenden Sie eine Datenstruktur, um Dinge zu vervollständigen
Beispiel: K geordnete Arrays zusammenführen
Testmethode 3: Implementieren Sie eine Datenstruktur, um einige spezifische Funktionen bereitzustellen
Beispiel: Das K-Item-Problem mit der höchsten Häufigkeit
Zeitkomplexität:
Beschreiben Sie die zeitliche Komplexität mehrerer Schnittstellen<br>
Beispielsweise müssen Sie eine Set-Datenstruktur entwerfen
Algorithmus 1:O(n) untereGrenze O(1) add
Implementierungsmethode: Array-Speicher verwenden, jedes Mal vergleichen und direkt am Ende des Arrays einfügen
Algorithmus 2:O(logn) untereGrenze O(logn) add
Implementierungsmethode: Verwenden Sie den Red-Black-Tree-Speicher, TreeSet in Java und die Karte in C
Array Array, am häufigsten getestet
Typ
Unterarray
Interview Fragen
41. 42,43, Maximales Subarray<br>44. Minimales Subarray<br>138
Problem mit Array-Intervallen
Interview Fragen
30. Bereiche einfügen<br>793. Überschneidung mehrerer Arrays<br>156
Externes Sortierproblem
Definition: Der externe Sortieralgorithmus bezieht sich auf einen Algorithmus zum Sortieren von Daten, die in einer oder mehreren großen Dateien gespeichert sind, wenn nicht genügend Speicher vorhanden ist. <br>
Zwei grundlegende Schritte:<br>Schneiden Sie die große Datei in mehrere kleine Dateien und verwenden Sie den Speicher, um sie entsprechend zu sortieren.<br>Verwenden Sie den K-Way-Merge-Algorithmus (k-way merge), um mehrere kleine Dateien zu einer großen Datei zusammenzuführen
Interview Fragen
486. K sortierte Arrays zusammenführen<br>104. K sortierte Listen zusammenführen
Bitoperationen
Definition: Operationen an binären Bits
Interview Fragen
365. Wie viele Einsen gibt es im Binärsystem?<br>
Baumarrays werden selten berücksichtigt
Auch bekannt als: Fenwick Tree Englischer Name: Binary Indexed Tree Abkürzung: BIT wird basierend auf Präfix und Informationen implementiert<br>
Obwohl der Name Tree lautet, wird er in einem Array (Array) gespeichert.<br>BIT ist ein Multibaum und die Eltern-Kind-Beziehung stellt die Einschlussbeziehung dar.<br>Verwenden Sie getPrefixSum(k), um getRangeSum(x, y) zu implementieren )
Zeitkomplexität
Log(n) Ändern Sie den Wert an jeder Position<br>Log(n) Fragen Sie die Summe eines beliebigen Intervalls ab
Merkmale
Für ein Array mit N Zahlen werden die folgenden Funktionen unterstützt:<br>update(index, val) //Aktualisieren Sie den Wert an einer Position im Array innerhalb von logN-Zeiten. getPrefixSum(k) //Erhalten Sie ihn innerhalb von log(K)-Zeiten Die Summe der ersten K Zahlen im Array
Interview Fragen
817. Summenvariable des Bereichsmatrixelements<br>249. Zählt die Anzahl der vorherigen Zahlen, die kleiner als sie selbst sind
Interviewbezogen
Finden Sie das zweitkleinste Element in einem Array
Finden Sie die erste sich nicht wiederholende ganze Zahl
Ordnen Sie positive und negative Werte in einem Array neu an
65. Median zweier sortierter Arrays, schwieriges Problem<br>
6. Sortierte Arrays zusammenführen<br>64. Sortierte Arrays zusammenführen<br>839. K sortierte Intervalllisten zusammenführen<br>547 zwei Arrays<br>548. Schnittmenge mehrerer Arrays<br>654. Median von K sortierten Arrays<br>149 Zeit<br>405. Submatrix, deren Summe Null ist<br>943. Maximale Submatrix-Summe<br>665
Stack Stack, nicht oft getestet
Definition
LIFO. Beispielsweise wird bei der Logistikverladung zunächst die später geladene Ware entladen.
Unterstützte Operationen: O(1) Push / O(1) Pop / O(1) Top
Anwendung
Wird zum nicht rekursiven Durchlaufen von Binärbäumen, zum Berechnen umgekehrter polnischer Ausdrücke usw. verwendet.
Die Hauptdatenstruktur der nicht rekursiven Implementierung von DFS
Bei der Breitensuche (BFS) werden die zu expandierenden Knoten erfasst.
Mithilfe von Warteschlangen können Nachrichtenwarteschlangen implementiert werden, um asynchrone Aufgaben auszuführen.
Wenn die Geschwindigkeit der Nachrichtenproduktion und des Nachrichtenverbrauchs inkonsistent ist, ist eine Nachrichtenwarteschlange erforderlich, um gesendete, aber nicht empfangene Nachrichten vorübergehend zu speichern.
Implementieren Sie den Stapelmodus
Verwenden Sie eine Speicherstruktur (häufig verwendete Arrays, gelegentlich verknüpfte Listen), um Elemente zu speichern
Ein Array verwenden, um drei Stapel zu implementieren?
Einen Stack mit zwei Warteschlangen implementieren? <br>
der Unterschied
Arrays bieten eine bessere Leistung für den Direktzugriff. <br>Verknüpfte Listen bieten eine bessere Leistung beim Einfügen und Löschen von Elementen.
Übungen<br>
Lintcode: 495. Stapel implementieren
494. Implementierungsstapel mit zwei Warteschlangen<br>
224. Verwenden Sie ein Array, um drei Stapel zu implementieren<br>
arbeiten
drücken, Element oben einsetzen
pop kehrt zurück und entfernt das oberste Element des Stapels
isEmptyDer Stapel ist leer und gibt true zurück
top gibt das oberste Element zurück, ohne es zu entfernen
Java verwendet java.util.Stack, das aus der Vector-Klasse hervorgeht und Operationen wie push(), pop(), peek(), empty() und search() unterstützt.
C, verwenden Sie einfach den Stapel in <Stack>. Die Methode ähnelt Java, außer dass peek() in C top() heißt und bei pop() der Rückgabewert leer ist.
Verwenden Sie in Python die Liste direkt, verwenden Sie Slicing-Operationen wie [-1], um den oberen Rand des Stapels anzuzeigen, verwenden Sie list.pop(), um den oberen Rand des Stapels zu öffnen, und verwenden Sie list.append(), um den oberen Rand des Stapels zu verschieben . <br>
Interviewbezogen
Verwenden des Stacks zum Auswerten von Postfix-Ausdrücken
Sortieren Sie die Elemente des Stapels
Bestimmen Sie, ob ein Ausdruck in Klammern ausgeglichen ist
QueueQueue, oft getestet
Definition
FIFO-First-In-First-Out-sequentieller Speicher, lineare Datenstruktur, Supermarktkasse
Unterstützte Operationen: O(1) Push / O(1) Pop / O(1) Top
Anwendung
Wird als Hauptdatenstruktur für den BFS-Algorithmus verwendet
arbeiten
Fügen Sie Elemente am Ende der Enqueue-Warteschlange ein
dequeue entfernt das Kopfelement der Warteschlange
Die Spalte „isEmpty“ ist leer und gibt „true“ zurück
top gibt das erste Element der Warteschlange zurück
Methode zur Verwirklichung
Warteschlange mithilfe einer verknüpften Liste implementieren?
Eine Warteschlange mit zwei Stapeln implementieren? <br>
Warteschlange mit kreisförmigem Array implementieren?
Übung: 955. Queue durch kreisförmiges Array implementieren<br>
Interview
Verwenden Sie die Warteschlange, um den Stapel darzustellen
Kehren Sie die ersten k Elemente der Warteschlange um
Verwenden Sie eine Warteschlange, um Binärzahlen von 1 bis n zu generieren
642. Gleitender Durchschnitt aus Datenstrom<br>
955. Warteschlange durch kreisförmiges Array implementieren<br>
Verlinkte Liste, oft getestet
Definition
Knotenkette: Jeder Knoten enthält Daten und Zeiger auf nachfolgende Knoten
verwenden
Implementieren Sie Dateisystem, Hash-Tabelle und Adjazenzliste
Typ
einseitig verknüpfte Liste
arbeiten
isEmpty, ist leer, gibt true zurück
Interview
Umgekehrt verknüpfte Liste
Erkennen Sie Zyklen in verknüpften Listen
Gibt den n-ten Knoten vom letzten in der verknüpften Liste zurück
Entfernen Sie Duplikate aus der verknüpften Liste
BaumBaum
Definition
hierarchische Datenstruktur
Bestehend aus Eckpunkten und Kanten
Wie in der Grafik dargestellt, gibt es im Baum keine Zyklen
der Begriff
untergeordneter untergeordneter Knoten
Typ
Liniensegmentbäume werden grundsätzlich nicht getestet, sie sind universell.
Binärbaum, oft getestet
binärer Suchbaum
Definition: Der linke Teilbaum ist kleiner als der Wurzelknoten und der Wurzelknoten ist kleiner als der rechte Teilbaum. Der Effekt ist: Die linke Seite ist immer kleiner als die rechte Seite
ausgeglichener Binärbaum
Ausgeglichener Baum (AVL-Baum)
Definition:
Es handelt sich um einen leeren Baum oder der absolute Wert des Höhenunterschieds zwischen seinem linken und rechten Teilbaum überschreitet nicht 1, und der linke und der rechte Teilbaum sind beide ausgeglichene Binärbäume.
Implementierung
Rotschwarzer Baum, AVL, Sündenbockbaum, Treap, sich ausbreitender Baum
Haufen
Definition: Ein Heap ist ein ausgeglichener Binärbaum. Die überschüssigen untergeordneten Knoten werden so weit wie möglich auf dem linken untergeordneten Knoten platziert. Es besteht keine Größenbeziehung zwischen dem linken und dem rechten untergeordneten Knoten. Kann mithilfe von Arrays implementiert werden<br>
Unterstützte Operationen: O(log N) Add / O(log N) Remove / O(1) Min oder Max
Wertmerkmale: Für den Min-Heap ist der übergeordnete Knoten kleiner als der untergeordnete Knoten, und es besteht keine Größenbeziehung zwischen dem linken und rechten untergeordneten Knoten. Für den maximalen Heap-Typ ist der übergeordnete Knoten größer als der untergeordnete Knoten Es besteht keine Größenbeziehung zwischen dem linken und dem rechten untergeordneten Knoten.
Strukturmerkmale: Es handelt sich um einen Binärbaum mit einer Höhe von logN
Zeitkomplexität: Lösch- und Pop-Komplexität sind alle logN, minimale oder maximale Komplexität finden O(1)<br>
Einfügemethode: Immer von links einfügen, um einen ausgeglichenen Binärbaum sicherzustellen. Wenn die eingefügte Zahl klein ist, verschieben Sie sie nach oben und der übergeordnete Knoten wird nach unten verschoben. Die maximale Komplexität beträgt also logN<br>
Die Löschmethode ist ähnlich
Implementierungsmethode: Übung: Lintcode 130 Heapify<br>
Fragen zur Vorstellungsgesprächspraxis
104. K sortierte Listen zusammenführen<br>612. K nächste Punkte<br>613. Hervorragende Ergebnisse<br>486. Im Datenfluss Ziffern<br>544. Top K größte Zahlen<br>401 Die k-te Zahl in der Sortiermatrix
Segmentbaum<br>
Definition: Der Liniensegmentbaum ist eine erweiterte Datenstruktur und eine Baumstruktur, genauer gesagt ein Binärbaum. Es kann Probleme wie Abfragen zur Intervalländerung effizient bearbeiten. <br>
Hinweis: Es ist grundsätzlich nicht getestet, aber wenn Sie es beherrschen, können Sie viele Probleme auf einmal lösen. Der Liniensegmentbaum basiert auf der Divide-and-Conquer-Methode und kann als gute Übung für die Division verwendet werden und Eroberungsmethode.
Interview
Ermitteln Sie die Höhe eines Binärbaums
Finden Sie den k-ten Maximalwert in einem binären Suchbaum
Finden Sie den Knoten, der den Abstand k vom Wurzelknoten hat
Finden Sie die Vorfahrenknoten eines bestimmten Knotens in einem Binärbaum
104. K-sortierte Listen zusammenführen<br>
3 Möglichkeiten
Methode 1: PriorityQueue verwenden
Methode 2: Divide-and-Conquer-Algorithmus ähnlich der Merge-Sortierung
Methode 3: Paarweiser Bottom-up-Merging-Algorithmus
Die Zeitkomplexität beträgt O(NlogK)
Kombiniert mit: Jiuzhang-Algorithmus
Bei den Übungsfragen handelt es sich ausschließlich um Lintcode-Fragen
Wondershare EdrawMind
![[Studiennotizen] Datenstrukturbaum](https://edrawcloudpublicus.s3.amazonaws.com/work/5635373/2024-5-15/1715741862/thumb.png?x-oss-process=image/resize,w_300,m_lfit)
