Mach dich fit für Coding-Interviews: Datenstrukturen in Python

1. Bereit? Setze ein. Geh schon.: [MUSIK] Das Programmieren von Interviews ist wirklich einschüchternd. Es gibt schwierige Fragen, knifflige Rätsel und sogar unlösbare Probleme. Es gibt Angriffspläne für jedes Szenario, aber wir werden uns auf das offensichtlichste konzentrieren wenn die Frage einfach ist. Wo es keine Kurvenbälle gibt, keine Tricks. Ich will sichergehen, dass du das Interview bestehst. Hallo! Ich bin Alvin, ein Forscher in der Industrie. Im vergangenen Frühjahr erhielt ich Angebote von Meta, Apple, Amazon, Tesla und anderen. In den letzten Jahren habe ich auch technische Angebote von Google, NVIDIA, Facebook und Lyft erhalten . Die Erfahrung, die ich aus diesen Interviews gesammelt habe , war von unschätzbarem Wert Ich habe mich wirklich hingesetzt, um zu verstehen, welche Teile meine Interviews erfolgreich gemacht haben? Was sind die Grundlagen und die Tricks? Dieser Kurs ist ein Schritt in wichtige Richtungen, ein Schritt vorwärts bei der Vorbereitung eines Vorstellungsgesprächs und ein Schritt vorwärts in der Programmierbeherrschung. Um beides zu erreichen, lernen wir Datenstrukturen kennen. Datenstrukturen sind eine Möglichkeit, Daten zu organisieren. In diesem Kurs sehen Sie Beispiele, wie sie funktionieren und wie Sie sie verwenden. Am Ende des Kurses verfügen Sie über zwei Fähigkeiten, eine für jedes Ziel. Sie können Datenstrukturen auswählen, die für die Codierung von Interviews verwendet werden sollen . Das ist eine große Sache. Anstatt effiziente Algorithmen zu erfinden, nur für Call-In-Umfragen bereit effizienter Algorithmus. Sie werden auch in der Lage sein, diese Datenstrukturen zu implementieren und Implementierungen nach Bedarf zu kombinieren und zu mischen . Das ist auch ein Eins. Implementierungen effektiv kennen, erhalten Sie im Interview einen Startcode, einen freien Vorsprung. Ich hoffe du bist begeistert. Ich weiß, dass ich es bin. Lass uns anfangen. 2. Warum du Datenstrukturen brauchst: Lassen Sie mich erklären, warum Sie insbesondere Datenstrukturen benötigen, warum dieser Kurs über Datenstrukturen für Ihr Wachstum als Programmierer so wichtig ist Ihr Wachstum als Programmierer so wichtig und wie Sie diesen Kurs effektiv nutzen können. Wir werden auf drei wichtige Diskussionspunkte eingehen: Erstens diskutieren wir die Vorteile der Beherrschung dieses Themas, zweitens besprechen wir spezifische Lernziele im Kurs, um Ihre Beherrschung zu beschleunigen, und drittens stellen wir eine Übung , die Ihnen hilft, nach Abschluss des Kurses die Meisterschaft zu erlangen. Hier ist unser erstes Gesprächsthema, warum Sie sich darum kümmern sollten, warum ich diesen Kurs unterrichte, welche Vorteile Sie daraus ziehen werden. Der größte Vorteil dieses Kurses besteht darin, besser auf Interviews vorbereitet zu sein. Es gibt zwei Arten von technischen Interviews: Erstens gibt es Codierungsfragen, sind spezifische Probleme wie, wie kehrt man eine Zeichenfolge um? Wie entfernt man alle doppelten Zahlen? Zweitens gibt es Fragen zum Systemdesign. Dies sind umfassendere Fragen wie Wie würdest du einen Clone von Airbnb erstellen? Im Grunde genommen, wie man Infrastruktur und Software für ein ganzes Produkt entwirft. Beide Interviews können herausfordernd sein, aber Datenstrukturen helfen Ihnen bei diesen beiden technischen Interviews enorm , und so geht's. Hier sind zwei spezifische Vorteile der Kenntnis von Datenstrukturen. Vorteil Nummer 1 ist für Ihr erstes technisches Interview, das Programmieren von Interviews. Ein erheblicher Teil, wahrscheinlich mehr als ein Drittel der Codierungsfragen, bezieht sich auf Datenstrukturen. Wenn Sie Ihre Datenstrukturen kennen, können Sie in Ihren Interviews oft Algorithmen anstelle von Design-Algorithmen anwenden . Das ist riesig. Es ist nicht nötig, Ideen von Grund auf neu zu entwickeln. Wenn Sie wissen, dass Datenstruktur A genau diese Anforderungen erfüllt, sagen Sie einfach: „Ich weiß, dass HashMaps ideal für diesen Anwendungsfall sind Hier erfahren Sie, warum und wie ich es verwenden würde.“ Das ist eine Killer-Antwort auf ein Interview Vorteil Nummer 2 ist für Ihr Systemdesign-Interview, Sie Systeme für Ihre spezifische Anwendung optimieren können , sowohl in Ihren Interviews als auch in der Praxis. Ich spreche nicht von einem 10 Prozent oder 25 Prozent schnelleren System, ich spreche von einem System , das um Größenordnungen effizienter arbeitet , indem die richtige Datenbank, Server oder Serverlose Infrastruktur und mehr. Sie würden sagen: „Wir brauchen gezielte azyklische Graphen. Graphdatenbanken sind speziell für diese Art von Beziehung optimiert , und hier ist der Grund dafür.“ Das ist eine gut informierte und überzeugende Designentscheidung. Vorteil Nummer 3 liegt außerhalb des Interviewprozesses. Mit einem Verständnis der Datenstrukturen werden Sie in der Lage sein, fortgeschrittenere Themen über Ihre Interviews hinaus anzugehen . In der Informatik vermitteln Ihnen diese Themen im Allgemeinen neue Fähigkeiten wie das Erstellen eines Spiels. Eines der beliebtesten Tools zur Spieleerstellung, Unity, verwendet ein sogenanntes datenorientiertes Programmierparadigma. Wie der Name schon sagt, ist das Verständnis Ihrer Datenstrukturen ziemlich wichtig. Zusammenfassend sind hier drei Vorteile für das Verständnis von Datenstrukturen aufgeführt. Lage zu sein, bei Codierungsinterviews anstelle von Design von Grund auf neu anzuwenden , zu optimieren der Lage zu sein, für die Anwendung in Interviews mit Systemdesign und fortgeschrittenere Themen anzugehen neue Türen zu öffnen, die über reine Interviews hinausgehen. In diesem Kurs konzentrieren wir uns auf Vorteil Nummer 1. In jeder zweiten Lektion üben Sie die Anwendung von Datenstrukturen zur Codierung von Interviewfragen. Um diese Vorteile nutzen zu können, müssen Sie sich in diesem Kurs auf zwei Lernziele konzentrieren . Ziel Nummer 1 ist es, zu wissen, wie jede Datenstruktur funktioniert, und die Implementierung jeder Datenstruktur zu üben. Dies ist wichtig, da Sie später möglicherweise Teile dieser Datenstrukturen implementieren oder Datenstrukturen für verschiedene Zwecke kombinieren müssen. Genau wie in meinen anderen Klassen empfehle ich Ihnen dringend, neben mir zu programmieren, dieses Video auf der einen Seite Ihres Bildschirms und Ihren bevorzugten Code-Editor auf der anderen Seite zu platzieren Bildschirms und Ihren bevorzugten . Kopieren Sie meinen Code genau und Sie müssen sich nicht beeilen. Halten Sie das Video an, wann immer Sie müssen. Wichtiger ist, dass Sie das Muskelgedächtnis aufbauen. Ziel Nummer 2 ist es, zu wissen, wie und wann die einzelnen Datenstrukturen verwendet werden müssen. Denken Sie insbesondere an die Vor - und Nachteile jeder Datenstruktur. In der nächsten Lektion stellen wir Ihnen spezifische Rubrikenelemente vor, anhand derer Sie die einzelnen Datenstrukturen beurteilen. Vor- und Nachteile sind nicht verwaschen, sie sind sehr präzise und klar definiert. Zusammenfassend lässt sich sagen, dass Ihre beiden wichtigsten Lernziele darin bestehen, zu wissen, wie Datenstrukturen funktionieren, indem Sie gemeinsam mit mir Implementierungen und Programmieren üben . Zweitens, wissen Sie, wie und wann Daten verwendet werden Strukturen, indem wir uns an die Vor- und Nachteile erinnern, die wir besprechen Unser letztes Gesprächsthema hier ist, wie Sie Ihr Verständnis der Datenstruktur über diesen Kurs hinaus festigen können. Klar, es ist zum Üben, aber es ist nicht wirklich das, was man erwartet. Wir müssen den Spieß umdrehen, so tun, als wären Sie der Interviewer, sagen, dass Sie jetzt die Fragen zur Datenstruktur schreiben. Ihre Aufgabe ist es, das Entwerfen von Datenstrukturfragen zu üben und dies drei Tage lang täglich zu tun. Ziel ist es, dass Sie nach einer guten Nachtruhe nur ein paar Mal über Datenstrukturen nachdenken . Tun Sie dies während Ihrer Ausfallzeit, während des Pendelns, beim Zähneputzen oder während Sie in der Schlange stehen. Fügen Sie dies zu Ihrer Liste „Mach das , wenn mir langweilig ist“ hinzu. Je mehr Sie dies tun, desto mehr Fragen stellen Sie sich, desto besser beherrschen Sie Datenstrukturen. Zusammenfassend haben wir die Vorteile der Kenntnis von Datenstrukturen, einer besseren Bereitschaft für Vorstellungsgespräche und ein Sprungbrett zu fortgeschrittenen Themen erörtert die Vorteile der Kenntnis von Datenstrukturen, besseren Bereitschaft für Vorstellungsgespräche und ein Sprungbrett zu fortgeschrittenen Themen Wir haben Ihre Lernziele besprochen, wissen, wie man Datenstrukturen implementiert und wie man Datenstrukturen benutzt, wir haben endlich eine Möglichkeit besprochen , Ihr Wissen zu vertiefen nach dem Kurs drei Tage lang Entwerfen Sie nach dem Kurs drei Tage lang jeden Tag eine Datenstrukturfrage. Ich ermutige Sie auch, Ihre Frage im Diskussionsbereich zu posten , mein Fehler. Ich meine das wirklich, wirklich ernst. Es ist unglaublich lohnend für mich, die Fragen zu sehen, die Sie stellen, entweder eine Frage, die Sie gestellt haben oder eine Frage zum Kurs, also laden Sie bitte hoch. Darauf freue ich mich. Das war's für den Überblick. Eine Kopie dieser Folien und weiterer Ressourcen finden Sie auf der Kurswebsite. Wir haben den Überblick abgeschlossen und als Nächstes werden wir darüber sprechen, wie Datenstrukturen verglichen werden können. 3. Was ist eine „gute“ Datenstruktur?: Was ist eine gute Datenstruktur? Dies ist für uns von entscheidender Bedeutung, da eines unserer Lernziele darin besteht, zu wissen, wie und wann jede Datenstruktur verwendet werden muss. Aber noch bevor wir diese Frage stellen, müssen wir uns zuerst fragen, was überhaupt eine Datenstruktur ist? Wir können mit der einfachen Definition beginnen. Eine Datenstruktur ist einfach eine Sammlung von Daten. Das klingt einfach, also lassen Sie uns das jetzt ein wenig näher erläutern. Lassen Sie uns diese Definition erweitern, indem einige Erwartungen an eine Datenstruktur hinzufügen. Insbesondere sollten wir in der Lage sein, die enthaltenen Daten zu ändern und darauf zuzugreifen . Eine Datenstruktur ist eine Sammlung von Daten, die geändert werden können und auf die zugegriffen werden kann. Um die Datenstruktur zu ändern, sollten wir in der Lage sein, Daten einzufügen und zu entfernen. Um auf die Daten zugreifen zu können, sollten wir in der Lage sein, Daten zu suchen und abzurufen. Dies sind die vier Aktionen, die jede Datenstruktur unterstützen muss. Jede dieser Aktionen kann je nach Datenstruktur sehr langsam oder sehr schnell sein. Dies bringt uns zu unserem nächsten Abschnitt Wie quantifizieren wir sehr schnell oder sehr langsam? Wie effizient oder ineffizient ist jede dieser Aktionen? Mit anderen Worten, wie bewerten wir Effizienz? Um die Effizienz eines Algorithmus zu bewerten, zählen wir die Anzahl der Operationen, die ein Algorithmus zur Ausführung benötigt. Nehmen wir zum Beispiel an, wir haben diese Liste von Früchten und sagen, wir suchen nach Avocado. Um die Liste zu durchsuchen, müssen wir die Liste nacheinander durchqueren bis wir den gesuchten Artikel gefunden haben. In diesem Fall haben wir drei „Operationen“ durchgeführt, um nach Avocado zu suchen. Wenn Avocado jedoch am Ende steht oder wenn sie überhaupt nicht in der Liste enthalten ist, müsste Ihr Suchalgorithmus alle Elemente in der Liste durchqueren. Bei einer Liste mit n Elementen nimmt die Suche nach einem Wert bis zu n Operationen in Anspruch. Jetzt ist die Definition von Operation vage. Vielleicht ist ein Speicherzugriff eine Operation, vielleicht ist das Überprüfen der String-Gleichheit eine andere Operation. Nehmen wir an, die Anzahl der Operationen für ein einzelnes Element benötigt werden, ist c. Dann werden für die Suche cn-Operationen ausgeführt. Diese Konstante c ist für uns jedoch beim Vergleich von Algorithmen uninteressant. Wir sagen einfach, dass der Algorithmus O von n Operationen ausführt, bei denen die O-Notation alle Konstanten verbirgt. Wir nennen das O of n Statistik, die Laufzeit oder Rechenkomplexität. Hier ist eine andere Möglichkeit zu sehen , was O of n-Komplexität bedeutet. Was wir wissen ist, dass mit zunehmender Liste die Anzahl der Operationen, wie Anzahl der Operationen, auch immer Sie sie zählen, linear wächst. Dies bedeutet, dass die Rechenkomplexität unserer Algorithmen oben und unten durch lineare Funktionen begrenzt werden kann . Jeder Algorithmus, dessen Komplexität innerhalb dieser Grenzen liegt, ist O von n. Infolgedessen weist die Suche in Ihrer Liste O von n Rechenkomplexität auf. Wir wissen jetzt, dass für eine Liste, die auch als Array bezeichnet wird, O von n mal eine Suche benötigt wird. Um genau zu sein, suchen wir nach einem Wert wenn wir nicht wissen, wo sich ein bestimmter Wert in der Liste befindet. Nehmen wir jedoch an, wir wollen genau den ith-Artikel holen. Wir wissen, dass wir das i-te Element wollen und nicht nach einem Wert suchen müssen. Dieser Abruf benötigt eine konstante Zeit oder O von einem, weil wir einfach auf das i-te Element der Liste zugreifen , ohne andere Werte zu betrachten. Insbesondere ändert sich der Aufwand, der zum Abrufen eines Elements erforderlich ist, nicht, wenn die Listenlänge zunimmt . Das ist großartig. Einen Artikel zu holen ist billig. Um die Effizienz zu maximieren, bedeutet dies, dass wir ein Array verwenden sollten, wenn wir häufiger mehr Daten abrufen müssen , als wir nach Daten suchen. Dies ist ein Beispiel für ein praktisches Mitnehmen, und wir werden viele davon im Kurs sehen. Jede dieser Entscheidungen zielt darauf ab , die Effizienz zu maximieren. Wir sollten unsere Definition einer Datenstruktur ändern. Eine Datenstruktur ist eine Sammlung von Daten , die effizient geändert und abgerufen werden können. Basierend auf jeder Anwendung müssen wir Datenstrukturen auswählen , um diese Effizienz sicherzustellen. werden wir die Komplexität einiger Datenstrukturen analysieren diesem Kurs werden wir die Komplexität einiger Datenstrukturen analysieren. Bei der Durchführung dieser Analysen werden wir auf mehrere gängige Wachstumsordnungen stoßen. Wachstumsordnungen sind das O von etwas, das wir zuvor gesehen haben. Wir haben bereits zwei Beispiele für Wachstumsaufträge gesehen. Konstantes zeitliches Wachstum O von eins und lineares Wachstum O von n. Dies sind sechs gängige Wachstumsordnungen , die hier auf dieser Folie dargestellt werden. Aber für die Datenstrukturen und Algorithmen, die wir behandeln, werden wir nur vier Wachstumsordnungen sehen, konstante O von einer, logarithmisches O von log n, lineares O von n und O von n im Quadrat. Wir werden später sehen, wie O of log n aussieht , aber denken Sie vorerst daran, dass Sie ein neues Tool zur Analyse der algorithmischen Komplexität haben und dass diese vier die häufigsten Wachstumsordnungen sind, die Sie finden werden. Eine Kopie dieser Folien und weiterer Ressourcen finden Sie auf der Kurswebsite. Jetzt haben Sie ein neues Tool und Anweisungen zur Wachstumsanalyse, denen Sie die Rechenkomplexität für jeden Algorithmus bewerten können . Noch wichtiger ist, dass Sie Datenstrukturen für verschiedene Anwendungen auswählen können Datenstrukturen für verschiedene Anwendungen je nachdem, wie langsam oder wie schnell eine Datenstruktur zum Einfügen, Löschen, Abrufen und Suchen ist . Im nächsten Abschnitt werden wir die Analyse von Wachstumsaufträgen üben . 4. Aufträge der Growth: Willkommen bei einigen Datenstrukturpraktiken. In dieser Lektion werden wir Datenstrukturen bewerten. Mit anderen Worten, wir bewerten Algorithmen und Datenstrukturen mithilfe eines Systems, das als Orders of Growth bezeichnet wird. Darüber haben wir in der vorherigen Lektion gesprochen. Die Big O-Notation zeigt uns, wie schnell oder wie langsam ein Algorithmus basierend auf seiner Eingabegröße ausgeführt wird. Wir werden die Interviewtaktiken vorerst beiseite legen, zumindest bestimmte Taktiken interviewen. Wir werden sicherlich Tipps zum Thema Vorstellungsgespräche haben, aber wir müssen uns zuerst auf die Grundlagen konzentrieren. Navigieren Sie zunächst zu dieser URL, alvinwan.com/data structures101/oog. Sobald Sie diese Seite sehen, forken Sie das Projekt, um Ihre eigene editierbare Kopie zu erhalten. Klicken Sie dazu oben links auf den Projektnamen, um ein Dropdown zu erhalten. Klicken Sie dann auf die Ellipse oben rechts, um ein weiteres Dropdown zu erhalten. Klicken Sie abschließend auf die Schaltfläche „Fork“. Dann schlage ich vor, Ihre Skillshare- und Repl.it-Fenster nebeneinander zu platzieren , wie hier gezeigt. Sie sollten dann auf der rechten Seite ein Fenster wie meines sehen . Bevor wir uns mit den Problemen befassen, wollen wir uns die Wachstumsreihenfolgen ansehen , über die wir zuvor gesprochen haben. Es gibt vier relevante Wachstumsordnungen. Zur Erinnerung, was ich hier schreibe, ist eine Funktion von n, wobei n die Größe der Eingabe ist. Diese Wachstumsreihenfolgen zeigen uns, um wie viel langsamer die Funktion ausgeführt wird , wenn wir die Eingabegröße n erhöhen. Daher möchten wir, dass die Laufzeiten langsamer wachsen , wenn die Eingabe an Größe zunimmt. Es ist gut, diese Liste der Laufzeiten nach oben zu verschieben. Je langsamer die Reihenfolge des Wachstums ist, desto effizienter und bevorzugter ist der Algorithmus oder die Datenstruktur. Ein Tipp, den ich für Sie habe, ist, diese Laufzeiten auswendig zu kennen Dies sind die vier Kernlaufzeiten , die Sie für jedes einzelne Interview kennen müssen. Die erste O (1) oder konstante Zeit bedeutet, dass unsere Funktion unabhängig von der Eingabegröße immer die gleiche Zeit benötigt. Zweitens wird O (log n) später tatsächlich darüber sprechen. Es ist etwas komplizierter, diese Laufzeit zu erklären. dritte O (n) oder lineare Laufzeit bedeutet, dass sich auch unsere Laufzeit verdoppelt, wenn sich unsere Eingabegröße verdoppelt. Wenn sich unsere Eingabegröße verdreifacht, verdreifacht sich auch unsere Laufzeit. Mit anderen Worten, unsere Funktionslaufzeit wächst tatsächlich linear in Bezug auf n. O (n) quadriert bedeutet hier quadratisch. Wenn wir die Eingabegröße verdoppeln, unsere Funktionslaufzeit oder die Laufzeit vervierfacht sich unsere Funktionslaufzeit oder die Laufzeit des Algorithmus vervierfacht sich. Wenn sich unsere Eingabegröße verdreifacht wächst unsere Laufzeit tatsächlich um das Neunfache, und so weiter und so fort. Lassen Sie uns jetzt direkt in die Übungen eintauchen. Auf der rechten Seite habe ich unsere erste Übung. Wie hoch ist die Laufzeitkomplexität für Folgendes? Hier haben wir nur eine for-Schleife für i im Bereich n. Denken Sie daran, dass der Bereich von n Ihnen eine eingebbare Anzahl von n verschiedenen Elementen bietet. Was ist die Laufzeitkomplexität dieser Funktion? Pausiere das Video hier und probiere es aus und hier ist die Antwort. Diese Funktion wiederholt erneut einmal über jedes einzelne Element in diesem iterierbaren Element von n Elementen. Mit anderen Worten, es iteriert einmal für jeweils n Elemente, es wird n-mal iteriert. Die Laufzeit für diese Funktion oder diesen Algorithmus ist O (n). [LACHEN] Ich habe vergessen, es dir zu zeigen. Hier ist die Liste der vier verschiedenen Laufzeitoptionen, die Sie haben. Ich behalte die hier, während wir diese Übungen durchmachen. Gehen wir nun zur zweiten Übung über. Was ist die Laufzeitkomplexität dieser Funktion, wiederum als Funktion von n. Hier haben wir zwei, für Schleifen. Jeder von ihnen wiederholt bis zu n. Eine andere Möglichkeit, dies zu sehen, wäre zu fragen, wie oft die Druckfunktion aufgerufen wurde? Pausiere das Video hier und versuche es und hier ist die Antwort. Hier wiederholen wir es in wenigen Zeiten. Dann wiederholen wir für jedes einzelne i auch über j n mal. Das ergibt insgesamt n mal n Läufe. Dieser Algorithmus ist O (n) quadriert. Gehen wir zur nächsten Übung über. Wie hoch ist die Laufzeitkomplexität dieser Funktion als Funktion von n? Hier beginnen wir mit n. Dann haben wir in dieser While-Schleife für jeden einzelnen Schritt diesen Wert. Was ist die Laufzeitkomplexität dieser Funktion? Sie können einen Eliminierungsprozess verwenden, um herauszufinden, wie die Laufzeit aussieht. Pausiere das Video hier und probiere es aus und hier ist die Antwort. Die Antwort auf diese Funktion, die wir durch Eliminierungsprozess ableiten können , lautet O (logn). So könnte dieser Eliminierungsprozess funktionieren. Hier sehen wir, dass die Funktion definitiv nicht konstant ist. Es dauert definitiv etwas länger, wenn n zunimmt. Es ist definitiv nicht O (1). Es ist jedoch nicht so langsam wie O (n), weil O (n) einmal iterieren würde. Es würde nacheinander über alle Elemente iterieren, bis zu n. Das tun wir jedoch nicht. Wir halbieren den Wert jedes Mal. Wir springen nur ein bisschen herum. Es ist nicht so langsam wie O (n) und es ist nicht so schnell wie O (1). Die einzige Laufzeit dazwischen ist O (log n). Wir werden das später genauer machen, um zu erklären, wie O (logn) zustande kommt. Aber jetzt sprechen wir über eine visuelle Erklärung. Wie sieht logarithmisches Wachstum aus und was bedeutet logarithmisches Wachstum? logarithmische Wachstum ist wirklich sehr langsam. Um Ihnen eine Vorstellung davon zu geben, wie langsam die Log-Funktion ist. Denken Sie daran, n ist die Eingabegröße, der Wert von log n ist die Laufzeit. Angenommen, unsere Eingabe hat Größe zwei, dann hat die Laufzeit Einheit Eins-Laufzeit. Nehmen wir an, unser Input verdoppelt die Größe vier, die Laufzeit erhöht sich um eins. Wenn sich unser Input erneut auf Größe Acht verdoppelt, erhöht sich die Laufzeit um eins. Wenn sich Ihre Eingabe erneut auf Größe 16 verdoppelt, erhöht sich die Laufzeit immer noch nur um eins. Beachten Sie, dass sich unsere Eingabegröße weiter verdoppeln muss , um die Laufzeit um eins zu erhöhen. Das bedeutet, dass unser Algorithmus ziemlich effizient ist. Optisch sieht das so aus. Wir zeichnen die Eingabegröße entlang der X-Achse, wir zeichnen die Laufzeit entlang der Y-Achse und plotten dann alle Punkte von zuvor. Beachten Sie, dass unsere Funktion ziemlich langsam wächst. Tatsächlich ist hier ein größeres Diagramm mit mehr Werten von x. Sie können sehen, dass unser Diagramm sehr schnell flach wird. Mit anderen Worten, logarithmische Funktionen wachsen sehr langsam. Behalte das im Hinterkopf. Kehren wir zu unserer Funktion zurück. Wir können jetzt sehen, dass i hier dies oder i oder n, sagen wir, n muss sich verdoppeln, um die Anzahl der Iterationen der While-Schleife um eins zu erhöhen . Wenn n zwei ist, die While-Schleife einmal wiederholt. Wenn n gleich vier ist, dies zweimal wiederholt. Wenn n acht ist, wiederholt sich dies dreimal und so weiter und so fort. Dieser Wert n muss jedes Mal verdoppelt werden, um die Laufzeit um nur eins zu erhöhen. Das ist logarithmisches Wachstum. Die andere Möglichkeit, dies zu sehen, besteht darin, dass unsere logarithmische Funktion die Eingabegröße in jedem Schritt halbiert . Wie Sie hier sehen können, halbieren wir jeden einzelnen Schritt, also halbieren wir unsere Arbeitsbelastung jedem einzelnen Schritt. Das ist der Tipp. Logarithmische Funktionen halbieren die Eingabegröße in jedem einzelnen Schritt. Hier ist eine Zusammenfassung der drei Beispiele, die wir gerade durchgesehen haben, und ihrer Laufzeiten. Das war's für die „grundlegenden Beispiele“. Ich meine nicht einfach, da diese einfach sind. Diese Beispiele sind ziemlich verwirrend, besonders wenn Sie sie zum ersten Mal sehen. Ich sage grundlegend, um zu bedeuten, dass alle anderen Beispiele eine Modifikation dieser Grundstruktur sein werden . Um die Laufzeiten in der Zukunft herauszufinden, gibt es zwei Schritte. Beginnen Sie damit, sich zu merken, wie diese „grundlegenden Beispiele“ aussehen. Zweitens, sobald Sie diese Beispiele kennen, können Sie sich die verschiedenen möglichen Änderungen merken . Das ist unser Tipp. Kommen wir nun zu diesen Änderungen, diesen kniffligen Beispielen. Dies sind wiederum Modifikationen der obigen Beispiele , um entweder verwirrend auszusehen oder die Laufzeit zu ändern. Hier sind die vier Laufzeiten zuvor. Gehen wir nun zu den Beispielen über, den kniffligen Beispielen. Wie oft wird print in der folgenden Funktion aufgerufen? Hier haben wir eine verschachtelte Schleife. Dann haben wir diese if-Bedingung, wenn i gleich j ist. Beachten Sie diese if-Anweisung und wie wirkt sie sich auf die Komplexität aus, wenn überhaupt? Pausieren Sie das Video hier und probieren Sie es erneut Wie oft wird Print aufgerufen? Hier ist die Antwort. Print wird nur n-mal aufgerufen. Dies liegt daran, dass unsere innere For-Schleife nur einmal ausgeführt wird. Wenn i gleich Null ist, dann gilt diese if-Bedingung nur, wenn j ebenfalls gleich Null ist. Wenn i gleich eins ist, gilt wiederum diese if-Bedingung nur, wenn j auch gleich eins ist. Das bedeutet, dass für jede einzelne äußere Schleife die innere Schleife nur einmal läuft, das sind also n mal eine Iteration, das ist eine Summe von O (n). Gehen wir nun zu unserem nächsten kniffligen Beispiel über. Wie oft wird print als Funktion von n aufgerufen? Hier haben wir eine geschachtelte for-Schleife, aber beachten Sie, dass die innere für Schleife nur bis i zählt . Wie wirkt sich das auf die Laufzeit aus, wenn überhaupt? Pausiere das Video hier und probiere es aus. Hier ist jetzt die Antwort. Wie sich herausstellt, scheinen wir, obwohl wir nur bis i iterieren, eine schnellere Laufzeitkomplexität zu haben. Es stellt sich heraus, dass wir das nicht tun Das ist immer noch O (n) quadriert. Hier ist der Grund dafür. Ich muss es erklären, indem ich dir ein Bild zeige. Nehmen wir an, wir haben eine normale for-Schleife auf der linken Seite. Dann gehen wir für jeden einzelnen Wert von i j n mal durch. Wir machen das, weil i gleich eins ist, wir iterieren durch alle Werte von j, i ist gleich zwei alle Werte von j und so weiter und so fort. Mach weiter so. Das bedeutet, dass wir insgesamt n Quadrat verschiedener Zeiten drucken. Nehmen wir an, wir drucken i j. Nehmen wir an, wir haben diese neue for-Schleife in der wir nur bis i iterieren. Was das bedeutet, ist hier in dieser ersten Zeile, wenn i gleich eins ist, wir führe j nur einmal aus. Wenn i in der zweiten Reihe gleich zwei ist, führen wir j nur zweimal aus. Wenn i gleich drei ist, führen wir j nur dreimal aus, und so weiter und so fort. Hier haben wir anstelle von n quadrierten Gesamtzeiten, die wir print nennen, 1/2 mal n quadrierte Male, die wir print nennen. 1/2 von n im Quadrat liegt jedoch immer noch in der Größenordnung von n im Quadrat, weshalb diese Funktion in Bezug auf die algorithmische Komplexität immer noch O von n im Quadrat ist . Damit ist dieses knifflige Beispiel abgeschlossen. Wenn Sie Fragen haben oder immer noch verwirrt sind, können Sie gerne eine Frage in den Diskussionsbereich stellen. Dies sind die vier verschiedenen Themen, die wir behandelt haben. Wachstumsordnungen haben wir einige grundlegende Beispiele wiedergefunden, logarithmisches Wachstum und einige knifflige Beispiele sowie wie sie diese grundlegenden Beispiele für ein kniffligeres Beispiel modifiziert haben . Eine Kopie dieser Folien und den fertigen Code für diese Lektion Sie auf der Kurswebsite. Damit ist diese Lektion zur Bewertung von Datenstrukturen abgeschlossen. 5. Sequenzen: Stack vs. Warteschlange: Ein gängiges Format für Daten ist eine Sequenz, und insbesondere gibt es zwei gängige Arten von Sequenzen. Es gibt Stapel, wie ein Stapel Kleidung oder ein Stapel Steine. Es gibt auch Warteschlangen wie eine Reihe von Personen oder einen Autotunnel. Sobald wir sowohl Stacks als auch Warteschlangen analysiert haben, besprechen wir ihre Vor- und Nachteile. An erster Stelle steht ein Stapel. Genau wie bei einem Stapel Steine fügst du Gegenstände oben auf den Stapel. Um dann einen Stein oder einen Gegenstand zu entfernen, entfernst du ihn auch von der Oberseite des Stapels. Wir fassen dies als last in, first out zusammen; das letzte Element, das Sie hinzufügen, ist das erste, das Sie entfernen. Der Einfügevorgang gemäß dieser Logik ist dann einfach. Wir nehmen den Wert, den wir schaffen wollen, wir schieben diesen Wert auf den Stack und das war's. Es dauert eine Konstante oder O von einmal, um einen neuen Wert in den Stapel einzufügen einen neuen Wert in den Stapel da der Aufwand, einfach ein Element einzufügen , gleich ist, egal wie lang der Stapel ist. Beachten Sie, dass wir per Definition nur Werte oben im Stapel einfügen können. Der Löschvorgang ist ebenfalls einfach. Wir nehmen den letzten hier in Grau angezeigten Wert und geben den Wert ein. Dies erfordert auch eine Konstante oder ein O von einem Mal. Da die Länge der Liste die Anzahl der Operationen nicht ändert , wird das Löschen geknetet. Zusammengenommen wissen wir jetzt, dass Stapel konstantes Einfügen und Löschen ermöglichen, sodass Änderungen billig sind. Aber was ist mit dem Zugang? Wie teuer ist die Suche im Stack nach einem Wert? Leider ziemlich langsam. Nehmen wir an, wir suchen nach dem Wert 8. Wir öffnen einen Gegenstand, überprüfen seinen Wert. Ist 7 gleich acht? Ist dies nicht der Fall, also geben wir einen anderen Wert ein und überprüfen dann seinen Wert. Ist 2 gleich 8? Es ist nicht so, dass wir noch einmal auftauchen und dann seinen Wert überprüfen. Ist 8 gleich? Das ist es absolut, also ist unsere Suche abgeschlossen. Befinden sich jedoch n Items im Stapel, müssen wir bis zu n Prüfungen durchführen. Dies bedeutet, dass die Suche linear oder O von n Zeit dauert. Das Abrufen eines bestimmten Elements ist ähnlich. Angenommen, wir wollen das zweite Element mit dem Wert 8 holen. Wir knallen einen Gegenstand, das ist ein Gegenstand, wir öffnen einen anderen Gegenstand, das sind zwei Gegenstände, dann legen wir einen anderen Gegenstand auf, das sind drei Gegenstände. Wir haben endlich den Wert erreicht, den wir wollen. Wenn sich nach wie vor n Gegenstände auf dem Stapel befinden, benötigen wir möglicherweise bis zu n Pops. Dadurch wird Fetch O nicht rechtzeitig ausgeschaltet. Zusammenfassend können wir in konstanter Zeit in einen Stapel einfügen und daraus löschen. Die Änderung ist effizient. Suchen und Abrufen benötigen jedoch lineare Zeit. Der Zugang ist ineffizient. Aber was wäre, wenn wir statt eines Steinstapels eine Reihe von Leuten hätten? Die erste Person , die sich der Linie anschließt sollte die erste sein, die sie verlässt. Dies wird als Warteschlange bezeichnet. Dieses Mal fügen wir einen Wert am Ende der Warteschlange ein und löschen einen Wert von vorne in der Warteschlange. Wir nennen dies eine First-In-, First-Out-Sequenz oder eine Warteschlange. Wie bereits erwähnt, ist das Einfügen einfach. Wir erwägen einen Wert, den wir hinzufügen müssen, und fügen diesen Artikel dann in die Warteschlange ein. Unabhängig von der Länge der Liste wird die Einfachheit des Einfügens nicht beeinträchtigt. Dies ist ein O einer Operation. Das Löschen ist ähnlich. Wir betrachten einen Wert, der in Grau dargestellt entfernt werden soll, und entfernen diesen Wert dann aus der Warteschlange. Dies ist auch ein O einer Operation. Zusammenfassend lässt sich sagen, dass Einfügen und Löschen für eine Warteschlange also beide O einer Zeit sind. Wieder einmal ist die Suche jedoch ziemlich langsam. Angenommen, wir durchsuchen die Warteschlange nach dem Wert 8, wieder entfernen wir die Warteschlange, dann überprüfen Sie, ob 7 gleich 8 ist? Es ist nicht so, dass wir uns wieder aus der Warteschlange entfernen und dann überprüfen Ist 2 gleich 8? Ist es nicht. Wir entfernen die Warteschlange und überprüfen. Ist 8 gleich 8? Ist es. Unsere Suche ist abgeschlossen. Wenn sich jedoch n Elemente in der Warteschlange befinden, benötigen wir möglicherweise bis zu n Überprüfungen. Dies macht Suchen und Warteschlangen zu einem O-of-n-Algorithmus. Fetch ist wieder ähnlich. Angenommen, wir wollen den dritten Gegenstand mit dem Wert 8 holen. Wir entfernen einen Gegenstand aus der Warteschlange, das ist 1, wir entfernen einen anderen Gegenstand, das ist 2, und wir entfernen einen anderen Gegenstand aus der Warteschlange , um schließlich den Wert des dritten Gegenstands abzurufen, der acht ist. Für eine Warteschlange mit n Elementen benötigen wir n Dequeues, also ist das Abrufen O von n. Zusammenfassend lässt sich sagen, eine Warteschlange effizient geändert werden kann, aber der Zugriff ineffizient ist , genau wie bei Stacks. Lassen Sie uns nun die Vor- und Nachteile von Stacks und Warteschlangen analysieren. Ganz links haben wir die vier Operationen, die uns wichtig sind: Einfügen, Löschen, Suchen und Abrufen. In der 2. Spalte haben wir die Laufzeiten für einen Stack und in der 3. Spalte haben wir die Laufzeiten für eine Warteschlange. Leider sind die Laufzeiten selbst nicht besonders interessant, daher müssen wir wissen, welche wir basierend auf der Anwendung verwenden sollen und wie die einzelnen Datenstrukturen definiert wurden. Ein Stack ist beispielsweise ideal, Änderungen zu verfolgen, wie das Rückgängigmachen eines Vorgangs und anschließende Wiederholen dieses Vorgangs. Dies ist ein Stapel, da die letzte hinzugefügte Änderung die erste ist, die Sie rückgängig machen. Eine Warteschlange ist ideal für die sequentielle Verarbeitung, z. B. Bearbeitung von Autos in einer Linie an einer Mautbrücke oder das Herunterladen von Anfragen auf einen Server. Denken Sie an diese Folie, da sie die gesamte Lektion zusammenfasst. Eine Kopie dieser Folien und weiterer Ressourcen finden Sie auf der Kurswebsite. Lassen Sie uns nun diese Datenstrukturen in Aktion sehen. In der nächsten Lektion werden wir sowohl die Verwendung als auch die Implementierung dieser Datenstrukturen üben und unsere beiden Lernziele für diesen Kurs angehen. 6. Sequences: Willkommen zu einer weiteren Übungsstunde. In dieser Lektion behandeln wir Sequenzen, also Stapel und Warteschlangen. Genau wie zuvor werden wir wichtige Interviewtaktiken beiseite legen , wir müssen diese Grundlagen zuerst beherrschen. Beachten Sie, dass diese Fragen ziemlich schwierig sind. Das ist keine coole Anwendung. Dies sind Grundlagen , die Sie für Interviews benötigen , und es ist technisch herausforderndes Material. Navigieren Sie also wie zuvor zu dieser URL, alvinwan.com/datastructures101/sequences. Sobald Sie diese Seite sehen, forken Sie das Projekt, um Ihre eigene editierbare Kopie zu erhalten. Klicken Sie dazu oben links auf den Projektnamen , um ein Dropdown zu erhalten, klicken Sie auf die Ellipse, um ein weiteres Dropdown zu erhalten, und klicken Sie schließlich auf die Schaltfläche Fork. Dann schlage ich vor, Ihre Skillshare- und Replit-Bearbeitungsfenster nebeneinander zu platzieren , wie hier gezeigt. Wir werden über Palmen in drei verschiedenen Kategorien sprechen. Wir werden zunächst über Implementierungsprobleme sprechen. Dies sind Probleme , die Kernfunktionen für eine Datenstruktur implementieren . Zweitens werden wir einige Funktionen implementieren und die richtige Datenstruktur für die Verwendung auswählen , das ist der entscheidende Teil. Wir werden lernen, wie man die Datenstrukturen anhand ihrer Vor- und Nachteile auswählt . Im dritten Fall werden wir Datenstrukturen möglicherweise zu einer neuen Datenstruktur oder einer neuen Anwendung kombinieren möglicherweise zu einer neuen Datenstruktur oder einer neuen , bei der wir mehrere Datenstrukturen für jede ihrer Stärken unter einen Hut bringen müssen . Unabhängig von der Kategorie der Probleme hier einen Profi-Tipp, den Sie immer beachten sollten. In der Tat werden wir diesen Profi-Tipp für die gesamte Lektion und alle folgenden Übungslektionen befolgen. Wir werden alle unsere Fragen zum Lösen von Rätseln auf diese Weise lösen. Sie sollten auch alle Ihre Interviews zum Lösen von Rätseln auf diese Weise führen. Zuerst entwerfen wir den Algorithmus ohne Codierung. Entwerfen Sie den Algorithmus mündlich oder visuell mit Ihrem Interviewer. Auf diese Weise kann Ihr Interviewer Sie und Ihr Denken zur richtigen Antwort führen . Zweitens melden Sie die Laufzeit und die Speicherkomplexität. Das ist wichtig. Zunächst, um Verständnis zu demonstrieren, aber auch um zu sehen, ob Ihr Interviewer eine effizientere Lösung wünscht. Drittens, und schließlich, dann programmieren Sie. Wir strukturieren Ihre Praxis auf diese Weise. Entwerfe den Algorithmus, dann gehe ich die Lösung durch, berichte die Komplexität und dann gehe ich die Lösung und codiere schließlich den Algorithmus, und dann gehen wir noch einmal die Lösung durch. Die Idee ist, dass Sie, selbst wenn Sie einen Teil dieses dreistufigen Prozesses durcheinander bringen , die anderen Schritte üben können. Hier ist unsere allererste Frage. Wir werden Warteschlangen implementieren, aber Stacks verwenden. Bevor Sie jedoch beginnen, lassen Sie mich über einen Tipp sprechen. Denken Sie daran, dass ein Stack als letztes an erster Stelle steht. Das heißt, es ist wie ein Stapel Steine oder ein Stapel Kisten. Der letzte Gegenstand, den du auf diesen Stapel legst , wird der erste sein, den du abnimmst, das ist Stapel. Jetzt ist Warteschlange wie eine Linie, sagen wir mal eine Warteschlange von Autos. Das heißt First-In, First-Out. Das erste Auto, das sich anstellte, ist das erste Auto , das diese Warteschlange verlässt. Behalte das im Hinterkopf. Das, was ich hier geschrieben habe, eine Warteschlange ist First-in-First-Out, ein Stack ist Last Out, First-In. Zugegeben, ich erinnere mich nie an diesen First-In, First-Out, Last-Out, First-In. Woran ich mich stattdessen erinnere, ist so ziemlich genau dass ich mit dem Stapel arbeite, wie ein Stapel Steine, Stapel Kleidung, ein Stapel Kisten, und dann denke ich an eine Warteschlange nur als eine Linie. Wenn Sie das im Hinterkopf behalten, zeigt Ihnen das, in welche Richtung Sie sich bewegen. Die Übung hier besteht erneut darin, eine Warteschlange mithilfe von Stacks zu implementieren. Wenn du in deinem ripl.it nach unten scrollst, siehst du das genau hier. Das müssen Sie implementieren. Also pausiere das Video hier und denke zuerst über den Algorithmus nach. Wie werden Sie das konzeptionell machen ? Also versuch es mal. Hier ist die Antwort. Also werden wir Folgendes tun. Angenommen, wir haben diese Liste hier in Schwarz. Wir haben 9, 8, 2, 7. Neun ist unser erster Artikel. Unser letzter Punkt ist sieben. Um eine Warteschlange zu emulieren, müssen wir das erste Element entfernen, das neun ist, mit dem roten Pfeil genau dort. Unser Ziel, hier rot dargestellt, ist es, den Wert neun zu entfernen und den verbleibenden Stapel 8, 2, 7 zurückzugeben oder zu behalten. Zu wissen, dass das unser Ziel ist, das Einzige, was wir mit einem Stapel tun können, ist das Einzige, was wir mit einem Stapel tun können, vom letzten Gegenstand zu entfernen. Wir können nur Pop Seven. Nun, das ist okay. Das können wir weiter machen. Wir werden sieben, wir machen zwei, wir machen acht und schließlich werden wir neun. Da haben wir's. Wir können jetzt neun zurückgeben. Jetzt können wir uns von einem Stapel entfernen. Wir haben jedoch alle Gegenstände verloren , die zuvor veröffentlicht wurden, alle 8, 2 und 7. Wir brauchen also einen weiteren Stapel , um sie alle aufzunehmen. Also hier, was wir tun werden , ist sieben herauszuholen, aber sie auf den anderen Stapel zu schieben. Dann gehen wir zwei, acht raus, und dann kommen wir endlich neun zurück. Das ist großartig. Wir sind fast da. Wir brauchen jedoch 8, 2, 7 in unserem Stack. Im Moment haben wir die umgekehrten 7, 2, 8. Was wir also tun werden , ist vom zweiten Stapel zu springen und ihn wieder auf den ursprünglichen Stapel zu schieben . Also werden wir das zurückdrängen und los geht's. Wir haben beide Ziele. Wir können neun zurückgeben, als wäre es eine Warteschlange, und wir können einen verbleibenden Stapel 8, 2, 7 so behalten , wie wir wollten. Das scheint eine clevere Lösung zu sein. Ich würde mir wahrscheinlich sagen, dass ich diese Lösung auf keinen Fall finden kann. Wenn Sie dasselbe denken, bin ich ganz bei Ihnen und ich bin hier, um Ihnen zu sagen , dass das kein Problem ist. Es besteht eigentlich keine Notwendigkeit , diese Lösung zu finden. Verstehen Sie es stattdessen gründlich. in Ihren Interviews oder bei den Jobs einfach an die Taktiken, Erinnern Sie sich in Ihren Interviews oder bei den Jobs einfach an die Taktiken, die Ihnen zur Verfügung stehen Konzentrieren Sie also Ihre mentale Energie darauf, die Lösung zu verstehen. Wenn etwas keinen Sinn ergibt, fragen Sie einfach im Diskussionsbereich nach. wissen, dass dies der Algorithmus ist, fahren wir mit dem zweiten Schritt fort. Was ist die algorithmische Komplexität? Was ist die Laufzeitkomplexität und wie hoch ist die Speicherkomplexität? Pausiere das Video hier und versuche es herauszufinden . Hier ist die Antwort. Die algorithmische Komplexität oder Laufzeitkomplexität ist hier O (n). Wir müssen grundsätzlich zwei n Operationen durchführen, das ist O (n) -Zeit. Wir müssen jeden einzelnen Gegenstand in den zweiten Stapel legen, und dann müssen wir jeden einzelnen Gegenstand vom zweiten Stapel zurück in den ersten stapeln. Das ist O (n) für die Laufzeitkomplexität, für die Speicherkomplexität, es ist auch O (n) , einfach weil wir diesen anderen Stack behalten mussten und dieser andere Stapel bis zu n verschiedene Elemente benötigte. Wir haben also O (n) Laufzeitkomplexität, O (n) Speicherkomplexität. Versuchen wir nun, dies in Code zu implementieren. Halten Sie das Video hier erneut an und probieren Sie es zuerst selbst aus. Lassen Sie uns jetzt diese Lösung implementieren. Wir beginnen damit, einen Konstruktor zu schreiben. Dieser Konstruktor nimmt ein iterierbares auf. Hier können wir also sehen, dass dieser Konstruktor ein iterierbares Objekt annimmt, das eine Liste von nur einem Element ist. Aus dem Iterablen bauen wir einen Stack. [NOISE] Um nun [NOISE] in die Warteschlange zu stellen, drücken wir einfach auf den Stack. [NOISE] Ich möchte jedoch die Warteschlange entfernen oder vom Stack entfernen , hier kommt die spezielle Logik ins Spiel. Das ist der gesamte Algorithmus, über den wir hier auf der linken Seite gesprochen haben . Wir beginnen damit, den ursprünglichen Stapel in einen neuen Stapel zu leeren . Hier haben wir den neuen Stack. Dann, während wir Gegenstände im alten Stapel haben, werden wir sie auf den neuen Stapel schieben und wir werden sie vom alten verschieben. Jetzt, wo wir all diese Gegenstände herausgebracht haben, werden wir jetzt endlich den letzten Artikel herausnehmen. Dies wird uns den Wert geben , den wir tatsächlich zurückgeben müssen. Leeren wir nun den neuen Stapel wieder in den ursprünglichen Stapel. Denken Sie daran, dass dies der letzte Schritt war , bei dem wir alles umgekehrt hatten. Wir müssen sie alle zurück in den ursprünglichen Stapel schieben. Jetzt müssen wir, während der Stapel Gegenstände enthält, sie wieder auf den ursprünglichen Stapel schieben. Schließlich geben wir den Wert zurück. Los geht's. Wir haben unseren dreistufigen Algorithmus von früher implementiert. Lassen Sie uns nun prüfen, ob diese Funktion unsere Doctests besteht oder nicht . Sie dazu auf Ausführen, die grüne Schaltfläche ganz oben in Ihrer Datei. Hier können wir sehen, dass wir in allen anderen Funktionen Fehler hatten , aber nicht in dieser. Denken Sie daran, unsere Funktion hier ist Queue via Stack, was in dieser Liste fehlt. Wir sind startklar. Wir haben unsere Doctests für diese Funktion bestanden. Gehen wir jetzt zur nächsten Frage über. In unserer nächsten Frage werden wir das Gegenteil tun. Wir werden einen Stack mithilfe von Warteschlangen implementieren. Auch hier haben wir eine Warteschlange mit Stacks implementiert. Bei unserem nächsten Problem werden wir das Gegenteil tun. Nehmen Sie sich eine Sekunde Zeit, um das Video anzuhalten und zu überlegen welchen Algorithmus Sie dafür erstellen würden. Hier ist eine Lösung. Dies ist dem letzten Problem sehr ähnlich. Wie zuvor werden wir eine zweite Warteschlange instanziieren. Wir nehmen dann jeden Gegenstand in unserer ersten Warteschlange und schieben ihn in die zweite Warteschlange. Sobald wir beim letzten Element angekommen sind, wird dieses Listenelement genau wie ein Stapel zurückgeben. Das ist so ziemlich alles. Nachdem wir den Algorithmus haben, wollen wir über die Speicher- und Laufzeitkomplexität des Algorithmus nachdenken . Pausiere das Video erneut. Hier ist eine konzeptionelle Lösung. Hier wollen wir einen Stack implementieren, wir haben jedoch nur eine Warteschlange. Erinnern Sie sich daran, dass eine Warteschlange nur von Anfang an aus der Warteschlange entfernt werden kann , während wir, um einen Stack zu emulieren, in der Lage sein müssen, vom Ende her zu springen. Wir haben dieses Dilemma, aber wir werden es auf die gleiche oder ähnliche Weise lösen wie zuvor. Wir erstellen eine zweite Warteschlange. Dann werden wir neun aus der Warteschlange entfernen und sie in die zweite Warteschlange stellen. Dann entfernen wir acht und fügen eine zweite Warteschlange hinzu, dann entfernen wir zwei aus der Warteschlange und fügen sie der zweiten Warteschlange hinzu. Schließlich werden wir sieben aus der Warteschlange entfernen und sie zurückgeben. Hier haben wir es tatsächlich geschafft, „Pop Seven“ zu erreichen. Hier ist etwas Neues, anders als zuvor ist unsere zweite Warteschlange bereits in der richtigen Reihenfolge. Denken Sie daran, dass unsere Warteschlange vor 9, 8, 2, 7 war und jetzt 9, 8, 2. Dies ist die genaue und korrekte Reihenfolge. Wir müssen es nicht wie zuvor wieder in die ursprüngliche Warteschlange verschieben . Zu wissen, dass wir jetzt genau wissen können , wie wir diesen Algorithmus implementieren werden. Bevor wir das tun, wollen wir jedoch die Laufzeit und Speicherkomplexität der Funktion melden . Pausiere das Video hier und versuche es herauszufinden. Jetzt ist hier die Lösung. Die Laufzeit und Speicherkomplexität ist o von n, genau wie zuvor. die Laufzeitkomplexität zu gewährleisten, müssen wir jedes einzelne Element in der Liste Warteschlange entfernen und es in die zweite Warteschlange einreihen, also ist es o of n. Aus Gründen der Speicherkomplexität müssen wir nun die zweite Warteschlange beibehalten. Die zweite Warteschlange umfasst im Grunde genommen keinen Speicher bis zu einem Element. Da hast du es. Sowohl die Laufzeit als auch die Speicherkomplexität sind beide o of n. Nun wir endlich zum dritten Schritt über. Versuchen wir, diesen Algorithmus zu codieren. Pausiere das Video hier und versuche es zu codieren. Lassen Sie uns nun über die Lösung sprechen. Lassen Sie uns den Stack mithilfe von Warteschlangen implementieren. Genau wie zuvor werden wir einen Konstruktor erstellen. Dieser Konstruktor wird eine Iterable benötigen. Das Iterable wird der Anfangswert unserer Warteschlangen sein. Dann lasst uns Push für diesen Stack implementieren. Dies ist nur ein Warteschleifen- und Warteschleifenanruf. Die ganze Magie wird jetzt in der Pop-Methode geschehen. Bei dieser Pop-Methode leeren wir zunächst n minus ein Element in der ursprünglichen Warteschlange in die neue Warteschlange. Um das zu tun, erstellen wir eine Warteschlange. Das ist unsere neue Warteschlange. Während unsere alte Warteschlange mindestens einen Gegenstand hat, werden wir ihn weiter entfernen. Hier wird es tatsächlich aus der alten Warteschlange entfernt und in die neue Warteschlange eingefügt. Nachdem wir fast alle aus der Warteschlange entfernt haben, entfernen wir nun das letzte Element aus der alten Warteschlange. Hoppla, das ist Queue, Dequeue. Dieser letzte Punkt wäre zum Beispiel sieben. Dann würden wir diesen Wert zurückgeben. Wie wir bereits gesagt haben, enthält unsere neue Warteschlange alle Elemente, die wir benötigen, in der richtigen Reihenfolge. Wir ersetzen einfach unsere alte Warteschlange durch unsere neue. Jetzt können wir einen Wert zurückgeben. Lass uns weitermachen und versuchen, alle unsere Tests durchzuführen und zu sehen, was passiert. Da haben wir's. Wir können sehen, dass unser Stack via Queue nicht mehr in der Liste der Fehler steht. Tada, wir haben diese Tests bestanden. Gehen wir nun zum nächsten Problem über. Das nächste Problem ist, dass wir eine Datenstruktur verwenden. Ich werde Ihnen nicht sagen, welches Sie verwenden sollen, und es liegt an Ihnen, zu entscheiden, welches. Wir werden entweder Stapel oder Warteschlangen verwenden. Insbesondere um alle Kombinationen der Buchstaben a und b zu drucken. Wir werden alle Kombinationen der Länge k ausdrucken . Hier ist ein Beispiel, print_baba von 2 gibt uns aa, ab, bb. Wenn wir nun print baba von 3 nennen, dann gibt uns das alle drei Buchstaben bestehenden „Wörter“, die die Buchstaben a und b haben. Auch hier sind alle möglichen Kombinationen möglich. Beachten Sie, dass es keine Wiederholungen gibt. Beachten Sie, dass jeder einzelne Wert hier die Länge drei hat. das wissen, lassen Sie uns noch einmal den dreistufigen Prozess durchlaufen , über den wir zuvor gesprochen haben. Lassen Sie uns im ersten Schritt den Algorithmus entwerfen. Pausieren Sie das Video hier und versuchen Sie, den Algorithmus zu entwerfen. Auch hier sollten Sie entweder einen Stack oder eine Warteschlange verwenden. Lassen Sie uns nun konzeptionell über die Lösung sprechen. Hier in dieser speziellen Lösung verwenden wir eine Warteschlange. Ich werde die Warteschlange hier zuerst mit einer einfachen Liste kennzeichnen hier zuerst mit einer einfachen Liste , um zu visualisieren, was vor sich geht. Nehmen wir an, ich habe den Buchstaben A hier drin. Was wir tun werden, ist zuerst den Buchstaben a aus der Warteschlange zu entfernen. Jetzt haben wir eine und wir werden die einzigen zwei möglichen Möglichkeiten, den Buchstaben a zu verlängern, in die Warteschlange stellen. Um von einer Ein-Buchstaben-Sequenz die einzigen zwei möglichen Möglichkeiten, den Buchstaben a zu verlängern, in die Warteschlange stellen. aller möglichen As auszugehen und b steht für alle möglichen Zwei-Buchstaben-Sequenzen von a und b. Wir fügen aa und ab hinzu. Dies berücksichtigt alle möglichen Möglichkeiten eine A- und B-Sequenz von diesem Ausgangspunkt aus zu erstellen. Jetzt können wir das etwas umfangreicher machen. Wir beginnen mit der leeren Zeichenfolge. Dann entfernen wir diesen leeren String aus der Warteschlange. Dann fügen wir die einzigen zwei möglichen Möglichkeiten hinzu, dies zu erweitern, nämlich das Hinzufügen eines a am Ende oder das Hinzufügen eines B am Ende. Dann werden wir aus der Warteschlange entfernt und dann werden wir ein Plus a plus b hinzufügen, also aa ab. Dann machen wir das nochmal. Wir werden den ersten Punkt hier aus der Warteschlange entfernen, der b sein wird. Dann erweitern wir mit ba und bb. Wir machen das weiter. Jetzt haben wir aa, wir entfernen es aus der Warteschlange, und dann fügen wir aa plus aa plus b hinzu, also aaa, aab. Wir machen das weiter. Indem wir zum richtigen Zeitpunkt anhalten, stellen wir sicher, dass wir tatsächlich alle möglichen k-Längensequenzen von As und Bs abgedeckt haben. wissen, dass dies der Algorithmus ist, sprechen wir nun über die Speicher- und Laufzeitkomplexität. Pausieren Sie das Video hier und prüfen Sie, ob Sie sich diese beiden Komplexitäten einfallen lassen können. Lassen Sie uns über die Rechen- und Speicherkomplexität sprechen. Die Rechen- und Speicherkomplexität ist in diesem speziellen Szenario tatsächlich kompliziert, aber wir werden sie trotzdem besprechen. Angesichts dessen, was Sie bisher gewusst haben, kann es sich dieses vielleicht nicht einfallen lassen, aber das ist völlig in Ordnung. Auch hier ist es Ihr Ziel, die Lösung zu verstehen , die ich jetzt vorstelle. Lassen Sie uns darüber sprechen, wie oft es dauert, oder lassen Sie uns zuerst darüber sprechen, wie viele Ergebnisse es hier gibt. Alle möglichen drei Längenfolgen von A's und B's. Hier haben wir zwei Optionen für jeden einzelnen Buchstaben, a oder b mal 2 mal 2. Das heißt, es gibt hier zwei Möglichkeiten von drei verschiedenen Optionen. Wenn wir alle möglichen Sequenzen der Länge k wollen, geben wir zwei bis k verschiedene Antworten aus. Um nun zwei bis k verschiedene Antworten zu erzeugen , mussten wir tatsächlich auch alle beiden Längen- und Ein-Length-Lösungen generieren . In Wirklichkeit müssen wir zwei bis drei verschiedene Optionen generieren. Wir mussten zwei zu den Zwei durchgehen, und dann auch zwei zu dem einen. Das stimmt im Allgemeinen. Wenn wir alle vier Längensequenzen erzeugen wollten, hätten wir zwei zu der einen zwei zu den zwei die drei und zwei zu den vier verschiedenen Kombinationen und so weiter und so fort generiert drei und zwei zu . In Wirklichkeit bedeutet das, dass dies tatsächlich eine Summe von bis zu, sagen wir mal j, Werten ist tatsächlich eine Summe von bis zu, sagen wir mal j, , bei denen höchstens j gleich k ist . Hier haben wir diese fiese Zusammenfassung einer Reihe von Begriffen. Zum Glück für uns kümmert sich die Größenordnungsanalyse jedoch nur um den Begriff der größten Größenordnung. Hier können wir das einfach als o von 2 auf n zusammenfassen , oder ich denke k, da wir k verwenden. Da wir wissen, dass dieser Algorithmus ziemlich langsam ist, ist dies die Rechenkomplexität. Zum Glück für uns ist die Speicherkomplexität leider auch die numerische Komplexität dieselbe. O von 2 zu k. Das ist ein ziemlich langsamer Algorithmus. Es ist auch ein ziemlich teurer Algorithmus, aber wir lassen das, dass es ein hübscher, komplexer Algorithmus ist. Aber zumindest angesichts dessen, was wir bisher gesagt haben, ist dies eine Möglichkeit, dies zu tun, und wir werden es vorerst so machen. Machen Sie weiter und pausieren Sie das Video hier und versuchen Sie, es zu codieren. Jetzt ist hier eine Lösung. Um loszulegen, erstellen wir eine Warteschlange. Genau wie wir zuvor besprochen haben, werden wir die leere Zeichenfolge hinzufügen . Diese leere Zeichenfolge alle möglichen Sätze von Sequenzen der Länge Null. Daraus generieren wir alle möglichen Sätze von Sequenzen einer Länge usw. Während sich etwas in der Warteschlange befindet, werden wir immer wieder generieren. Lass uns weitermachen und die erste Zeichenfolge öffnen oder aus der Warteschlange entfernen. Wenn unser Wort hier genau die Länge k hat, dann drucken wir dieses Wort einfach aus und schon kann es losgehen. Wenn das Wort jedoch noch nicht die Länge k hat, werden wir es erweitern. Wir werden es mit dem Buchstaben a erweitern und wir werden es mit dem Buchstaben b erweitern. Los geht's. Das ist es für unsere Funktion. Dies gibt uns alle möglichen Kalign-Sequenzen da dies sicherstellt, dass wir mit allen Möglichkeiten a und b erweitern , und dies stellt sicher, dass alle Kalign-Sequenzen erfasst werden, sobald sie entstehen. Wenn es etwas längeres als eine Kalign-Sequenz gibt, dann geht es nirgendwohin. Wir werden nicht weiter damit arbeiten. Tatsächlich können Sie tatsächlich beweisen, dass es keine Länge mehr als k geben wird , aber das ist nicht besonders wichtig. Der Punkt ist, dass diese Funktion uns das geben sollte, was wir wollen. Lass uns weitermachen und es jetzt versuchen. oben auf die grüne Schaltfläche „Ausführen“ und Sie sollten sehen, dass print_baba aus dieser Liste der Fehler verschwindet . Da haben wir's. print_BABA ist jetzt aus der Liste der Fehler verschwunden. Wir haben auch diesen Test bestanden. Gehen wir zur nächsten Frage über. In dieser nächsten Frage verwenden wir nun Stapel oder Warteschlangen, um Treppen zu drucken. Drucken Sie insbesondere die Anzahl der Möglichkeiten aus, wie wir k Treppen hinaufsteigen können, wenn Sie jeweils ein oder zwei Schritte ausführen können. Wenn Sie eine Treppe haben, können Sie sie nur in eine Richtung hinaufsteigen. Wenn Sie zwei Treppen haben, können Sie sie in zwei Richtungen hinaufsteigen, entweder Sie machen jeweils einen Schritt oder Sie machen beide Schritte gleichzeitig. Wenn es drei Stufen gibt, dann kannst du entweder 1,1,1 steigen, oder du kannst zwei Stufen und dann eine Stufe hinaufsteigen, oder du kannst eine Stufe und dann zwei Stufen hinaufsteigen, also ist es 1,1,1; 1,2 oder 2,1. Es gibt drei Möglichkeiten , drei Stufen zu erklimmen. Diese Funktion soll die Anzahl der Möglichkeiten berechnen, die zum Treppensteigen erforderlich sind, wenn Sie ein oder zwei Schritte ausführen können . Bevor Sie den Algorithmus in Betracht ziehen, finden Sie hier einen Hinweis. Nun, Sie können das Video hier pausieren , wenn Sie den Hinweis nicht möchten, aber der Hinweis ist der folgende; vor unseren Aktionen ohne Zitat für jedes einzelne Wort, noch nicht die Länge k hatte, wir hatten zwei verschiedene Aktionen. Sie können a oder b hinzufügen. Hier haben Sie etwas Ähnliches. Wenn Sie noch nicht alle k Treppen hinaufgestiegen sind, haben Sie zwei verschiedene Aktionen. Sie können eine Stufe oder zwei Stufen hinaufsteigen. Wenn Sie das wissen und wissen , dass wir die Warteschlange zuvor verwendet um alle möglichen Möglichkeiten zum Aufbau eines Wortes darzustellen, können Sie diese Warteschlange jetzt auch verwenden, um alle möglichen Wege zum Treppensteigen aufzubauen . Pausieren Sie das Video hier und prüfen Sie, ob Sie den Algorithmus herausfinden können. Jetzt ist hier eine Lösung. Die Lösung wird die vorherige Lösung tatsächlich ziemlich genau widerspiegeln. Was wir tun werden, ist für jede einzelne Treppe, sagen wir, wir haben jetzt eine Warteschlange, unser Ziel wird es sein, jeder einzelne Gegenstand in der Warteschlange wird ein anderer Weg sein , dies zu erreichen bestimmte Anzahl von Schritten. Hier ist eine Möglichkeit, es auszudrücken. Nehmen wir an, wir haben Null. Das heißt, dies ist eine Möglichkeit, die Treppe auf Null zu bringen. Dann werden wir diese 0 aus der Warteschlange entfernen. Dann fügen wir der Warteschlange zwei Elemente hinzu. Sie können entweder einen Schritt oder zwei Schritte machen. Wir nehmen 0 plus 1 und 0 plus 2. Dann entfernen Sie den ersten Gegenstand aus der Warteschlange. Dann stellen wir uns wieder in die Warteschlange. Wir sagen, es gibt zwei Möglichkeiten Sie können entweder einen Schritt machen, Sie können 1 plus 1 machen, was 2 ist, oder Sie können zwei Schritte machen, das sind drei. Dann entfernen wir uns wieder aus der Warteschlange. Wir werden die beiden aus der Warteschlange entfernen. Dann sagen wir, hier sind zwei. Ab diesem Zeitpunkt können Sie ein oder zwei Schritte ausführen. Sie können 2 plus 1 oder drei oder 2 plus 2 nehmen, was 4 ist, und dann so weiter und so fort. Du kannst das weiter machen. Was im Grunde passieren wird, ist, wenn Sie zählen , wie oft k in dieser Warteschlange vorkommt, das zeigt Ihnen, wie viele Möglichkeiten es gibt um zu dieser Anzahl von Treppen zu gelangen. Das war's für die konzeptionelle Lösung des Algorithmus. Wir werden tatsächlich die Speicher- und Laufzeitkomplexität für dieses spezielle Problem überspringen die Speicher- und Laufzeitkomplexität , nur weil es ziemlich schwierig zu berechnen ist. Es gibt eine Möglichkeit, dies zu berechnen. Wir werden es vorerst überspringen. Ich werde eine schriftliche Version der Lösung in die endgültige Lösungsdatei aufnehmen . In der Zwischenzeit wollen wir mit der eigentlichen Codierung dieser Funktion fortfahren . Halten Sie das Video hier erneut an und versuchen Sie, die Lösung zu codieren. Lassen Sie uns jetzt die Lösung programmieren. Wir beginnen damit, hier eine Warteschlange mit nur null Elementen zu erstellen . Diese Warteschlange hat jetzt keine Elemente. Wir werden auch initialisieren, dass die Anzahl der Möglichkeiten, wie wir bis zu k Treppen hinaufsteigen können, Null ist. Während wir etwas in der Warteschlange haben, also während es Wege die Treppe hinauf gibt, werden wir uns in eine Richtung die Treppe hinauf aus der Warteschlange entfernen. Dadurch wird eine Richtung die Treppe hinauf aus der Warteschlange entfernt. Wenn wir es dann auf k Schritte geschafft haben, erhöhen wir die Anzahl der möglichen Wege, um bis zu k Schritte zu erreichen, um eins. Wenn wir es noch nicht bis zu k Stufen geschafft haben, also die Treppe weniger als k ist, dann werden wir überlegen, wie wir dorthin gelangen können. Wir werden entweder plus 1 Treppe in Betracht ziehen oder zwei Schritte in Betracht ziehen. Dann geben wir schließlich die Gesamtzahl der Möglichkeiten zurück , die benötigt wurden, um bis zu k Schritte zu erreichen. Jetzt, wo du das hast, lass uns weitermachen und auf „Ausführen“ klicken. Da haben wir's. Wir können jetzt sehen, dass print_stairs nicht mehr in unserer Liste der Fehler enthalten ist. Wir haben alle Testfälle bestanden. Bevor wir zur nächsten Frage übergehen, wollte ich diesen Tipp ansprechen. Der Tipp ist, das Kernproblem zu lösen und dann die Randfälle zu betrachten. Wir haben hier einige der Tipps für Randfälle übersprungen und Sie können sie sehen, wenn Sie zu den Folien zurückkehren, aber die Grundidee ist, sich erneut auf das Kernproblem zu konzentrieren, auf das Kernproblem zu konzentrieren bevor Sie sich mit Edge befasst haben Koffer. Das ist momentan nicht besonders relevant, aber wenn wir Probleme lösen, werden wir immer mehr dieser Randfälle sehen, und manchmal können sie eine Ablenkung sein. Konzentrieren Sie sich erneut darauf, zuerst das Kernproblem zu lösen. Hier werden wir jetzt Stapel und Warteschlangen verwenden , um Klammern zu überprüfen. Eigentlich ist dies das erste Problem, bei dem wir eine Reihe zufälliger Randfälle sehen werden . Hier ist das Problem. Scrollen Sie in Ihrer Datei ein wenig nach unten und Sie werden sehen, dass unser Ziel darin besteht, zu überprüfen, ob die angegebene Zeichenfolge übereinstimmende Klammern enthält. [GELÄCHTER] Ich habe dir hier eigentlich schon einen Hinweis gegeben. Du solltest einen Stack verwenden, aber lass uns reingehen und hier nach unten scrollen und sehen, was das bedeutet. Passende Klammern bedeuten, dass für jede einzelne Startklammer Sie für jede einzelne Startklammer eine entsprechende schließende Klammer haben. Es ist jedoch nicht nur, ob es existiert, es muss in der richtigen Reihenfolge sein. Sehen Sie zum Beispiel, hier haben Sie eine Startklammer. Eigentlich fehlt hier nur eine Endklammer, aber hier ist ein Fall, in dem Sie ungültige Klammern haben. Hier haben Sie Endklammer und dann beginnen Sie mit Klammern. Diese sind nicht ordnungsgemäß geschlossen. Das bedeutet, dass vor jeder einzelnen geschlossenen Klammer Sie vor jeder einzelnen geschlossenen Klammer eine entsprechende Startklammer benötigen. Das ist es, was es bedeutet, zusammenzupassen. Dies ist tatsächlich ein sehr häufiges Problem , das Sie sowohl als Übung als auch möglicherweise sogar im Interview selbst sehen werden. Das ist gut zu wissen, gut zu verstehen, was die Prämisse des Problems ist. Auch hier möchten wir überprüfen, ob die bereitgestellte Zeichenfolge übereinstimmende Klammern enthält. Auch hier ist der Hinweis, einen Stack zu verwenden. Halten Sie das Video hier an und prüfen Sie, ob Sie den Algorithmus finden können. Lassen Sie uns jetzt über die Lösung sprechen. Unsere Lösung besteht, wie wir bereits im Tipp oder im Hinweis erwähnt haben , darin, tatsächlich einen Stack zu verwenden. Nehmen wir an, wir haben diesen Stack genau hier. Dieser Stapel wird darstellen, wie viele Startklammern oder wie tief wir in Klammern stehen. Nehmen wir an, wir iterieren durch die Zeichenfolge und wir haben diese ersten Klammern gesehen, wir werden hier eine Startklammer hinzufügen. Dann sehen wir jetzt eine enge Klammer. Jedes Mal, wenn wir enge Klammern sehen, springen wir vom Stapel ab. Wir sind vom Stapel abgekommen, haben eine Ebene höher entfernt, wir haben diese Gruppe entfernt. Jetzt, wo wir eine weitere Startklammer sehen, fügen wir wieder hinzu, wir sehen eine weitere Startklammer wir wieder hinzufügen werden, und dann sehen wir hier eine geschlossene Klammer, also lass uns mach weiter und entferne das, und dann sehen wir eine weitere Startklammer, also fügen wir das wieder hinzu. Endlich werden wir das wieder schließen. Jetzt können wir ganz am Ende der Funktion sehen , dass wir immer noch eine nicht geschlossene Klammer haben , nämlich diese. Diese Gruppe ist nicht geschlossen. Das bedeutet, dass dies kein übereinstimmender Satz von Klammern ist, wir können false zurückgeben. Im Wesentlichen stellt dieser Stapel tatsächlich dar, wie tief wir uns in diesem verschachtelten Satz von Klammern befinden. Immer wenn du vorbeikommst, bedeutet das, dass wir wieder auf einem Level sind. Wir haben einen verschachtelten Satz Klammern losgeworden. Wenn wir nicht den ganzen Weg wieder hoch und aus den Klammern herausgekommen sind, stimmt es nicht überein. Wenn Sie gleichzeitig so etwas sehen, das mit einer engen Klammer beginnt, ist der Stapel ganz am Anfang der Zeichenfolge leer, sodass nichts zu knallen ist . Dies wird uns sofort sagen, dass dies wiederum ein ungültiger Satz von Klammern ist. So werden wir das konzeptionell machen. Lassen Sie uns nun über die Laufzeitkomplexität und die Speicherkomplexität sprechen . Pausiere das Video hier und versuche es herauszufinden. Hier ist die Antwort. Sowohl für die Laufzeit als auch für die Speicherkomplexität sind beide linear. Während wir hier iterieren , wir im Grunde nur einmal über die Zeichenkette iterieren . Jeder einzelne Gegenstand ist nur einmal zu sehen. Zweitens, um die lineare Speicherkomplexität zu verstehen, stellen Sie sich vor, Sie hätten eine Zeichenfolge, die so aussieht, dann wäre unser Stack einfach all diese Startklammern. Wir haben bis zu N verschiedene Elemente in unserem Stack, das heißt, unsere Speicherkomplexität ist O von N. Gehen wir nun zum dritten Schritt über, fangen wir an, diesen Algorithmus zu codieren. Pausiere das Video hier und versuche es zu codieren. Lass uns reingehen und diesen Algorithmus jetzt programmieren. Hier erstellen wir zunächst einen Stapel, und für jeden einzelnen Buchstaben in der Zeichenfolge überprüfen wir, ob der Buchstabe mit und für jeden einzelnen Buchstaben in der Zeichenfolge überprüfen wir, ob der Buchstabe einem neuen Satz von Klammern beginnt, wir auf den Stapel drücken. Andernfalls können wir davon ausgehen , dass der Buchstabe eine schließende Klammer ist. Das habe ich gerade vorhin geschrieben. Grundsätzlich sollten Sie in einem Interview fragen, ob die Zeichenfolge andere Zeichen wie Zahlen oder Buchstaben und was auch immer enthalten könnte . Nur der Einfachheit halber gehen wir davon aus, dass die Zeichenfolge nur Klammern enthält. Wenn es sich hier nicht um eine öffnende Klammer handelt, ist es eine schließende Klammer. Für jede einzelne schließende Klammer springen wir vom Stapel ab. Wenn der Stack nichts mehr übrig hat, geben wir true zurück. Wenn der Stapel noch etwas übrig hat, bedeutet das, dass wir nicht alle unsere Klammern geschlossen haben, also sollten wir false zurückgeben. Nun, da ich das weiß, ist hier tatsächlich ein Tipp, den ich zuvor oder in den Folien von früher erwähnt zuvor oder in den Folien habe, den ich aber nicht erwähnt habe. Betrachten Sie hier eine leere Sequenz. Was passiert, wenn dein Stack tatsächlich leer ist? Gibt es eine Stelle in Ihrem Code an der Ihr Code kaputt gehen würde? In diesem speziellen Fall ja, stack.pop. Hier überprüfen wir nicht, ob der Stack bereits leer ist, also lass uns das tun. Wenn der Stapel schon leer ist, was machen wir hier? Wenn der Stapel bereits leer ist und wir versuchen, eine öffnende Klammer zu entfernen, bedeutet dies, dass wir eine schließende Klammer gesehen haben, bevor wir die entsprechenden ersten Klammern gesehen haben. das wissen, bedeutet dies wiederum, die Zeichenfolge ungültig ist, also sollten wir false zurückgeben. Das war's wirklich für die Edge Cases. Ungültige Eingaben gelten hier nicht, sodass dieses Problem abgeschlossen ist. Lassen Sie uns nachsehen, ob es alle unsere Tests bestanden hat. den Code ausführen, werden Sie feststellen , dass is_valid_parentheses nicht in dieser Liste von Fehlern enthalten ist . Daher haben wir diese Funktionstests bestanden. Gehen wir zum nächsten Problem über. Hier ist der Tipp, berücksichtige eigentlich fremde Charaktere. Das war hier oben, der Tipp, in einem Interview fragen , ob die Zeichenfolge andere Zeichen für dieses spezielle Problem enthalten könnte . Jetzt solltest du es selbst versuchen. Verwenden Sie Stapel oder Warteschlangen , um zu überprüfen, ob übereinstimmende Klammern und übereinstimmende Klammern vorhanden sind . Hier haben wir Klammern , die sich öffnen und schließen, und wir haben auch Klammern , die sich öffnen und schließen. Dies ist eine gültige Gruppierung, da jedes einzelne Klammerpaar perfekt übereinstimmt. Aber es gibt noch eine zusätzliche Herausforderung. Beachten Sie hier, dass, wenn Sie nur eckige Klammern berücksichtigen, diese korrekt übereinstimmen. Wenn Sie nur die Klammern berücksichtigen, werden sie auch übereinstimmen. Sie werden jedoch feststellen, dass sich diese eckigen Klammern und Klammern überschneiden , was eine ungültige Gruppierung darstellt. In diesem Wissen versuchen wir, einen Algorithmus für dieses Problem zu entwerfen. Halten Sie das Video hier an und versuchen herauszufinden, wie Sie Ihre Datenstrukturen, Stacks oder Warteschlangen verwenden würden , um dieses Problem zu lösen. Auch hier können Sie Ihr vorheriges Problem als Inspiration verwenden. Pausiere das Video hier und probiere es aus. Hier ist eine Lösung. Genau wie zuvor werden wir einen Stack verwenden, außer dass der Stapel diesmal entweder Startklammern oder Startklammern enthält . Es wird immer grundsätzlich die Startinterpunktion enthalten . wissen, dass wir, wann immer wir wollen , eine schließende Klammer sehen, Wenn wir wissen, dass wir, wann immer wir wollen, eine schließende Klammer sehen, versuchen wir, vom Stapel abzuspringen. In diesem Fall ziehen wir diese eckige Klammer ab. Wir sehen derzeit eine schließende Klammer. Schließende Klammern und diese öffnende Klammer stimmen nicht überein, was bedeutet, dass es sich um eine ungültige Gruppierung handelt. Das würde in diesem speziellen Fall der Fall sein. Du würdest auf dem Stapel so etwas sehen. Sie würden eine eckige Klammer sehen, Sie würden eine Klammer sehen, und wenn Sie dann wegspringen, sehen Sie diese öffnenden Klammern im Vergleich zu dieser schließenden Klammer. Wenn diese beiden also nicht übereinstimmen, ist sie jetzt ungültig. Ansonsten sieht der Algorithmus ziemlich genauso aus wie zuvor. Jedes Mal, wenn Sie eine öffnende Interpunktion sehen, fügen Sie sie dem Stapel hinzu, wenn Sie eine schließende Interpunktion sehen, versuchen Sie, sie zu entfernen, und stellen Sie sicher, dass Sie die richtige Eröffnungsinterpunktion verwenden. Das war's für den Algorithmus. Lassen Sie uns nun erneut überlegen, was die Laufzeit und Speicherkomplexität ist. Pausieren Sie das Video hier und sehen Sie, ob Sie es herausfinden können. Nun, hier ist die Antwort. Sowohl für die Laufzeit als auch für die Speicherkomplexität haben wir O von N. Genau wie zuvor wiederholen wir aus Gründen der Rechenkomplexität einfach einmal über jedes einzelne Zeichen, also ist das O von N. Für die Speicherkomplexität wir könnten wieder eine Zeichenfolge mit nur einem Haufen öffnender Interpunktion wie dieser haben. Wenn Sie eine Reihe von öffnenden Interpunktionen wie diese haben, dann ist Ihr Stapel so lang wie Ihre Eingabezeichenfolge. Hier ist auch unsere Speicherkomplexität O von N. Nachdem wir diese ersten beiden Schritte bestanden haben, versuchen wir nun den dritten Schritt. Versuchen wir, diesen Algorithmus zu codieren. Pausiere das Video hier und sieh nach, ob du programmieren kannst. Versuchen wir nun, diese Funktion zu codieren. 7. Listen: Array vs. verlinkte Liste: Unsere erste Kategorie ist für Artikellisten. Wir analysieren zwei Datenstrukturen, insbesondere Arrays und verknüpfte Listen. Wir werden dann auf der Grundlage unserer Analyse ihre Vor - und Nachteile behandeln . Lassen Sie uns damit beginnen, unsere Array-Analyse abzuschließen. Ein Array ist einfach eine Liste von Elementen. Im Speicher werden die Array-Elemente direkt nebeneinander platziert. Zuvor haben wir festgestellt, dass das Durchsuchen eines Arrays O von n dauert, da wir die gesamte Liste ein Element nach dem anderen durchqueren müssen , um den Wert zu finden. Wir fanden auch heraus, dass das Abrufen O von 1 konstanter Zeit benötigt. Beenden wir nun diese Analyse und sehen, wie lange es dauert, ein Element in das Array einzufügen. Angenommen, Sie haben dieses Array von drei Gegenständen. Wir visualisieren jetzt einen Teil Ihres Gedächtnisses in Ihrem Computer. Wir möchten ein neues Element mit dem Wert vier einfügen. Theoretisch könnten wir einfach so einen Platz für vier Personen zuweisen . Möglicherweise hat Ihr Computer diesen Speicherplatz jedoch bereits anderen Daten zugewiesen. Infolgedessen weist die Einfügeoperation einen neuen Speicherblock für Ihre neue Länge für das Array zu, dann kopiert der Algorithmus jedes Element nacheinander. Schließlich wird der Wert des neuen Artikels aktualisiert. Bei einem Array mit n Elementen werden beim Einfügen n Kopien erstellt. Insertion ist somit ein O einer Operation. Zusammenfassend nimmt das Einfügen lineare Zeit in Anspruch. Mal sehen, wie lange das Löschen dauert. Angenommen, Sie haben ein Array von sechs Elementen, Sie möchten das dritte Element löschen, die Nummer 2 hier. Um dies zu tun, verschiebt der Löschalgorithmus alle Zahlen danach nach oben. Es kopiert 3 vorwärts, kopiert 4 vorwärts, kopiert 7 vorwärts und gibt dann den letzten Platz frei. Infolgedessen benötigt das Löschen für ein Array der Länge n n Kopien. Dadurch wird O von n gelöscht. Damit ist unsere Tabelle der Laufzeitkomplexitäten für das Array vervollständigt. Sie werden sofort feststellen, dass das Array sehr effizient zum Abrufen, aber bei allem anderen ineffizient ist. Unser Array ist insbesondere für Änderungen ineffizient weil wir alle Daten im Speicher zusammenhängend halten müssen. Mit anderen Worten, alle Gegenstände müssen so direkt nebeneinander liegen. Aber das können wir ändern. Platzieren wir jedes Element in einer Liste wo immer wir es wollen. Um alle Elemente zu einer Liste zu verbinden, müssen wir Links hinzufügen. Jeder dieser Links wird auch als Zeiger bezeichnet. Jeder Zeiger zeigt auf eine Position für das nächste Element in der Liste. Wir müssen auch eine Markierung hinzufügen , die anzeigt, dass die Liste beendet wurde. Dies nennen wir aufgrund all der Links, die wir eingefügt haben, eine verknüpfte Liste . Diese verlinkte Liste enthält einige wirklich nette Eigenschaften. Analysieren wir nun diese verlinkte Liste. Nehmen wir an, wir wollen einen neuen Wert 3 am Ende der Liste einfügen , dann vergeben wir einfach zwei neue Stellen und stellen sicher, dass 2 Punkte auf 3 gesetzt werden. Unabhängig davon, wie viele Elemente sich in der verknüpften Liste befinden, haben wir einen konstanten Arbeitsaufwand vor uns, um ein neues Element einzufügen, zwei Leerzeichen zuzuweisen und einen Zeiger zu ändern. Infolgedessen ist das Einfügen für verknüpfte Listen O von 1 konstanter Zeit. Die Geschichte ist ähnlich, auch wenn wir einen Wert in die Mitte der Liste einfügen möchten , zwei neue Leerzeichen für den neuen Wert und einen Zeiger zuweisen dann auf den vorherigen Wert 8 bis 3 zeigen auch wenn wir einen Wert in die Mitte der Liste einfügen möchten, zwei neue Leerzeichen für den neuen Wert und einen Zeiger zuweisen und dann auf den vorherigen Wert 8 bis 3 zeigen verweise den neuen Wert 3 auf 2. Da haben wir es. Das Einfügen ist abgeschlossen. Unabhängig von der Länge der verknüpften Liste müssen wir nur zwei Leerzeichen zuweisen und zwei Zeiger ändern. Dies ist immer noch eine konstante Zeit O von 1. Zusammenfassend lässt sich sagen, dass eine verknüpfte Liste eine konstante Zeiteinfügung aufweist. Sehen wir uns jetzt an, wie das Entfernen oder Löschen funktioniert. Angenommen, wir wollen 3, den letzten Artikel, löschen. Das ist einfach. Wir kehren einfach um, was wir für das Einfügen getan haben. Löschen Sie den vorletzten Zeiger. Jetzt ist der Punkt 3 nicht mehr Teil der verknüpften Liste. Um das letzte Element zu löschen, benötigen Sie nur eine Änderung mit einem Zeiger. Dies ist eine konstante Zeit oder O von 1. Das Löschen eines Elements in der Mitte der Liste ist ebenfalls einfach. Angenommen, Sie möchten 3, das dritte Element, löschen, ändern Sie den Zeiger für acht, um 3 zu überspringen. Jetzt ist 3 tatsächlich nicht mehr Teil der verknüpften Liste, und das war's. Um ein Element zu löschen, egal wo es sich befindet, ändern wir einfach einen Zeiger. Dies ist wieder eine konstante Zeit oder O von 1. Zusammenfassend lässt sich sagen, dass eine verknüpfte Liste eine konstante Zeit zum Einfügen und Löschen hat. Sehen wir uns nun an, wie lange der Zugriff auf die verlinkte Liste dauert. Nehmen wir an, wir suchen nach dem Wert 4. Wir müssen die gesamte verknüpfte Liste nacheinander durchqueren , bis wir 4 finden. Zuerst überprüfen wir den ersten Artikel. Ist das 4? 9 ist nicht 4, also greife auf das nächste Element zu. Ist das 4? 8 ist nicht 4, greifen Sie also auf das nächste Element zu. Ist das 4? 3 ist nicht 4 , als nächstes ist 2 nicht 4. Für eine verknüpfte Liste der Länge n benötigen wir also bis zu n Prüfungen. Durchsuchen einer verknüpften Liste dauert O von n Zeit. Zusammenfassend lässt sich sagen, dass eine verknüpfte Liste konstante Zeit für das Einfügen und Löschen hat , aber eine lineare Suchzeit. Leider ist das Abrufen von Elementen aus einer verknüpften Liste auch ziemlich langsam. Nehmen wir an, wir möchten das dritte Element in der verknüpften Liste überprüfen oder abrufen. Es gibt keine Möglichkeit zu wissen, wo das dritte Element im Speicher befindet also müssen wir von vorne beginnen. Wir greifen auf den ersten Gegenstand und folgen dann seinem Zeiger zum nächsten Element. Greifen Sie auf das nächste Element und folgen Sie dann dem Zeiger zum nächsten Element. Greifen Sie schließlich auf diesen Artikel zu. Da dies das dritte Element ist, geben Sie seinen Wert zurück. Für eine verknüpfte Liste der Länge n müssen wir bis zu n Knoten durchqueren. Das Abrufen des Ith-Elements aus einer verknüpften Liste dauert nicht lange. Zusammenfassend haben wir nun Analyse der verknüpften Liste abgeschlossen. Das Ändern der Liste, das Einfügen oder Löschen ist effizient. Der Zugriff auf die Liste, das Suchen oder Abrufen ist ineffizient. Nachdem wir nun sowohl Arrays als auch verknüpfte Listen analysiert haben, wollen wir sehen, wann welche verwendet werden sollen. Dies ist der wichtigste Teil dieser Lektion. Auch wenn Sie alles vergessen, was ich zuvor gesagt habe, bewahren Sie die nächste Folie in Ihrer Gesäßtasche auf. Das ist dein Essen zum Mitnehmen. Hier ist eine Zusammenfassung der Komplexität der Laufzeit. Auf der linken Seite haben wir die vier Operationen, die wir analysiert haben. In der 2. Spalte haben wir Array-Laufzeitkomplexitäten von früher. Auf der rechten Seite haben wir die Komplexität der Laufzeit der Liste verlinkt. Bei einem Array ist die Änderung langsam, aber das Abrufen ist schnell. Dies bedeutet, dass Arrays ideal für viele zufällige Zugriffe auf einen festen Datensatz sind. Für eine verknüpfte Liste ist der Zugriff langsam, aber die Änderung erfolgt schnell. Dies bedeutet, dass verknüpfte Listen aufgrund ihrer dynamischen Größe vorteilhaft sind , um sich ständig ändernde Daten aufzunehmen. Das war's. Dies ist die Zusammenfassungsfolie für diese Lektion. Eine Kopie dieser Folien und weiterer Ressourcen finden Sie auf der Kurswebsite. Lassen Sie uns nun diese Datenstrukturen in Aktion sehen. In der nächsten Lektion werden wir sowohl die Verwendung als auch die Implementierung dieser Datenstrukturen üben und unsere beiden Lernziele für diesen Kurs angehen. 8. Lists Practice: Willkommen zu einer weiteren Übungsstunde. Hier gehen wir zu den Übungslisten. Insbesondere werden wir hauptsächlich verlinkte Listen behandeln. Navigieren Sie wie zuvor zu dieser URL alvinwan.com/datastructures101/lists. Sobald Sie diese Seite sehen, forken Sie das Projekt, um Ihre eigene editierbare Kopie zu erhalten. Klicken Sie dazu oben links auf den Projektnamen , um ein Dropdown zu erhalten, klicken Sie auf die Ellipse, um ein weiteres Dropdown zu erhalten, und klicken Sie schließlich auf die Schaltfläche „Fork“. Dann schlage ich vor, Ihren Skillshare zu platzieren und darauf Fenster nebeneinander zu kräuseln , wie hier gezeigt. Hier sind die verschiedenen Unterthemen, die ich durchgehen möchte. Wir beginnen mit der Aufforderung. Dies ist der Code, Ihr Interviewer Ihnen zur Verfügung stellt. Anschließend werden wir über drei Kategorien von Eingabeaufforderungen sprechen : Implementierung, Verwendung und anschließende Kombination verschiedener Datenstrukturen. Zu Beginn sollten Sie auf der rechten Seite den Code sehen, den Ihr Interviewer Ihnen wahrscheinlich zur Verfügung stellen würde. Hier hättest du einen Stapel, du hättest eine Warteschlange. Nun, ich denke, Stack und Queue würden Sie wahrscheinlich nicht versorgen, aber Sie könnten sie sicherlich verwenden, wenn Sie müssten. Dies ist der Code , den Sie erhalten würden, im Grunde eine Implementierung einer verknüpften Liste. Sie haben etwas, das wie folgt aussieht. Sie hätten den Wert für den Link und Sie hätten auch eine Verbindung zum nächsten Link. Dies hier ist ein Dienstprogramm, das ich bereitgestellt habe , damit Sie Ihre verknüpfte Liste tatsächlich visualisieren können . Dies kann bereitgestellt werden oder nicht. Wenn dies nicht der Fall wäre, könnten Sie diese Implementierung auch verwenden. Fangen wir jetzt mit unserer allerersten Übung an. Nun werden wir für alle unsere Übungen, einschließlich dieser, dieselben drei Schritte ausführen , über die wir zuvor gesprochen haben. Auch dies ist sehr wichtig, um zu beachten und zu üben. Zuerst entwerfen wir den Algorithmus ohne Code mündlich oder visuell. Zweitens berichten wir über die Laufzeit und die Speicherkomplexität. Drittens fangen wir an zu programmieren. Hier wird eine verknüpfte Liste angehängt. Was wir tun werden, ist ein Element an die verknüpfte Liste anzuhängen. Also hier haben wir, sagen wir mal, eine verknüpfte Liste mit 1, 2 und 3. Wir wollen den Wert vier anhängen. Nachdem wir es angehängt haben, haben wir eine verknüpfte Liste, die 1, 2, 3, 4 ist. Halten Sie nun das Video hier an, um festzustellen , welchen Algorithmus Sie verwenden. Konzeptionell, wie die Schritte aussehen werden. Hier ist die Antwort. Konzeptionell werden wir wieder tun, dass wir nur einen Zeiger auf den Anfang der verknüpften Liste haben . Wir folgen diesem Zeiger genau wie hier auf der linken Seite mit diesem schwarzen Linkspfeil . Wir beginnen mit diesem Zeiger, navigieren dann zum nächsten Link und machen weiter , bis Sie das Ende unserer verknüpften Liste erreicht haben . Dann erstellen wir ganz am Ende unserer verlinkten Liste einfach einen neuen Link und hängen ihn an die Liste an. Das ist konzeptionell das, was wir tun werden. Wir gehen zum Ende der verknüpften Liste und fügen dann einen neuen Link hinzu. Wissen, dass wir jetzt wieder den zweiten Schritt in unserem dreistufigen Prozess in Betracht ziehen müssen. Wie hoch ist die Speicher- und Laufzeitkomplexität dieses Append-Algorithmus? Pausiere das Video hier und sieh nach, ob du es herausfinden kannst. Jetzt ist hier die Lösung. Dieser Algorithmus ist linear in Rechenkomplexität, einfach weil Sie die gesamte verknüpfte Liste durchlaufen müssen, die bis zur Länge N reichen kann. Das ist O of N-Rechenkomplexität. Für die Speicherkomplexität haben wir O von 1 Speicherkomplexität, einfach weil wir keinen zusätzlichen Speicher außer Speicher für das aktuelle Element und die vorhandene verknüpfte Liste verwendet Speicher für das aktuelle Element und die haben. Wir haben eigentlich keine neue Datenstruktur erstellt. Wir haben nur diesen Link , der O von 1 kostet. das wissen, lassen Sie uns jetzt den Algorithmus codieren. Halten Sie das Video hier erneut und prüfen Sie, ob Sie es codieren können. Jetzt ist hier eine Lösung. Hier gehen wir zum Ende der Liste. Hier sagen wir, während link.next nicht keiner ist. Das heißt, solange wir einen anderen Link in unserer aktuellen Liste haben , werden wir weiter durchqueren, bis wir am Ende angelangt sind. Dann endlich, ganz am Ende der Liste, also wird dieser Link jetzt nach dieser While-Schleife sein, das letzte Element, also wird es 3. Jetzt haben wir 3, wir schreiben link.next ist gleich unserem neuen Link , der einen Wert 4 enthält. das wissen, lassen Sie uns jetzt unsere Tests durchführen. Wir können jetzt sehen, dass Append in dieser Liste der Fehler fehlt , also haben wir unseren angehängten Test bestanden. Gehen wir nun zur nächsten Frage über. Bevor wir nun zur nächsten Frage übergehen, eigentlich auch für die nächste Frage, sollten Sie sich merken, wie Sie eine verknüpfte Liste durchqueren. Es wird immer fast dasselbe sein. Sie werden eine Zeitschleife haben, Sie werden überprüfen, ob Sie nicht auf ein Objekt vom Typ None zugreifen, dann greifen Sie einfach auf den nächsten Link zu. So durchquerst du so ziemlich immer eine verknüpfte Liste. Denken Sie daran, denn das nächste Problem wird etwas Ähnliches verwenden. Scrollen Sie in Ihrer Datei nach unten und Sie werden sehen, dass hier die Frage zum Einfügen ist. Unser Ziel ist es, nach dem bereitgestellten Index I einzufügen . Nehmen wir an, Sie hatten diese verlinkte Liste 1, 2, 3 und wir wollen hier nach Index 0 einen Link einfügen und wir möchten den Wert 4 einfügen. Hier fügen wir nach Index 0 den Wert 4 ein. Hier haben wir 1, 4, 2, 3. Wenn Sie auf die linke Seite schauen, haben wir uns vorgestellt, wie das aussehen wird , um Ihnen ein wenig zu helfen. [GELÄCHTER] Machen Sie weiter und halten Sie das Video hier an und prüfen Sie, ob Sie feststellen können der Algorithmus aussehen würde. Nun, hier ist die Antwort. Was wir tun werden, ist zuerst die Liste zu durchqueren bis wir den richtigen Link zum Ändern finden. Nehmen wir in diesem Fall an, wir fügen H nach 9 ein, genauso wie wir 4 nach 1 einfügen. Hier navigieren wir zu 9. Sobald wir den Wert 9 erreicht haben , erstellen wir einen neuen Link. Wir verknüpfen 9 mit 8 neu und dann werden wir 8 mit 2 neu verknüpfen. Es gibt drei Schritte. Navigieren Sie zum richtigen Element, den aktuellen Link erneut, und verwenden Sie dann den aktuellen Link, um eine Verbindung mit dem nächsten Link herzustellen. Das ist der Algorithmus. Nun, da Sie wissen, dass dies der Algorithmus ist, pausieren Sie das Video hier und finden Sie heraus, wie hoch die Laufzeit und Speicherkomplexität ist. Die Speicher- und Laufzeitkomplexität hier. Rechenkomplexität wird linear sein. Möglicherweise müssen wir bis zum Ende der Liste gehen, um etwas einzufügen. Speicherkomplexität ist konstant, weil das einzige, was wir erstellen , diese Verbindung selbst ist, was O von 1 konstanten Speicherkosten entspricht. wir das wissen, gehen wir nun zum Code über. Pausiere das Video hier und versuche zu programmieren. Jetzt ist hier eine Lösung. Genau wie zuvor beginnen wir damit, tatsächlich mit einer While-Schleife zu navigieren. Anstatt eine While-Schleife zu verwenden, verwenden wir eine for-Schleife, weil wir genau wissen , wie viele Schritte Sie ausführen werden. Für Link in Bereich i ist link gleich link.next. Ich habe hier einen Unterstrich verwendet, um zu kennzeichnen, dass wir diese Variable nicht verwenden werden . Alles was uns wichtig ist, dass wir im Grunde genommen mal auf.next.next zugreifen.next bis Sie zum richtigen Element kommen. Sobald Sie dort sind, weisen wir ein paar Dinge neu zu. Wir weisen zunächst das nächste Attribut des aktuellen Werts dem neuen Wert neu zu. Aber dann müssen wir diesen neuen Link auch mit dem Rest der verknüpften Liste verbinden . Wir werden dies verwenden, um dem ursprünglichen Link.next zu verbinden. Auch in diesem Beispiel auf der linken Seite zeigte 9 ursprünglich auf 2. Wir gehen jetzt zu Punkt 9 bis 8. Das ist genau hier. Link.next ist gleich unserem neuen Objekt. Dann gehen wir zu Punkt 8 bis 2, und das ist genau hier im zweiten Teil. Wir haben den ursprünglichen link.next und wir ersetzen ihn durch den neuen link.next. Das war's. Dies ist unsere Insert-Funktion. Fahren Sie fort und führen Sie Ihre Tests erneut aus , indem Sie oben auf die grüne Schaltfläche „Ausführen“ klicken. Jetzt können wir sehen, dass es einen Fehler weniger gibt. Wir haben nicht in unsere Liste der Fehler eingefügt, wir haben die Tests erfolgreich bestanden. Gehen wir zum nächsten Problem über. Hier ist ein Tipp, den wir für dieses und für zukünftige Probleme hatten , immer auf keine Werte zu überprüfen. Ein häufiger Fehler , den Sie bei Problemen mit verknüpften Listen erhalten, ist, dass Sie beispielsweise in diesem Link erhalten. Als nächstes erhalten Sie einen Link, der ein NoneType-Objekt ist. Next ist kein Attribut eines NoneType-Objekts. Das ist sehr verbreitet. Sie beim Debuggen und noch vor dem Debuggen, noch bevor Sie den Code ausführen während Sie mit dem Interviewer sprechen , sicher, dass Sie Ihren Code durchgehen und nach Orten suchen, an denen Es gibt möglicherweise keine Werte und stellen Sie sicher, dass Sie nicht.next oder.value für einen NoneType-Wert aufrufen. In dieser speziellen Funktion hier in Zeile 83 und 84 ist es durchaus möglich , dass ich ungültig war. Nehmen wir an, es waren 100. Dann würden wir irgendwann den NoneType-Wert erreichen und wir hatten versucht, den nächsten aufzurufen. Um diese Funktion robuster zu machen, müssten Sie das überprüfen. müsstest du berücksichtigen. In dieser besonders einfachen Implementierung haben wir das nicht getan, sondern nur etwas, das Sie immer im Hinterkopf behalten Überprüfen Sie in Ihren Interviews und jedem Gedicht, das Sie schreiben, immer auf keine Werte . Gehen wir nun zum nächsten Problem über. Unser Ziel ist es nun, einen Stack mithilfe einer verknüpften Liste zu implementieren. Hier haben wir eine verknüpfte Liste, wir haben eins, zwei. Unser Ziel ist es, dies so behandeln zu können , als wäre es ein Stack. Wenn wir darauf Dot Pop nennen, würde es uns den letzten Punkt geben, nämlich zwei. Wenn wir Push aufrufen, drücken wir hier 2, drücken 3, und wenn wir knallen, erhalten wir den letzten Gegenstand zurück, den wir geschoben haben, nämlich drei. Wenn du wieder auftauchst, bekommst du den vorletzten Gegenstand, den du drückst, nämlich zwei. Unser Ziel ist es, einen Stack zu implementieren , aber eine verknüpfte Liste im Backend zu verwenden. Halten Sie das Video hier an und sehen ob Sie herausfinden können, ob der Algorithmus, in diesem Fall der Algorithmus, lautet, wie werden Sie pushen und wie werden Sie platzen? Pausiere das Video hier. Hier ist die Antwort. Konzeptionell gesehen ist dies dem Anfang ziemlich ähnlich. Wenn wir hier pushen sagen, werden wir so ziemlich die Append-Funktion schreiben , über die wir zuvor gesprochen haben. Können wir sagen Pop hier, wir schreiben eine neue Funktion, löschen. Wir haben noch keine Löschfunktion geschrieben, aber sie wird so ziemlich wie jede andere Funktion sein , die aus einer Linkliste löscht. Jetzt, da wir den Algorithmus kennen, pausieren Sie das Video hier und prüfen Sie, ob Sie die Rechen- und Speicherkomplexität herausfinden können . Die Lösung für diesen Teil, Laufzeit und Speicherkomplexität wird tatsächlich die Laufzeitkomplexität linear sein. Wir gehen bis zum Ende der verknüpften Liste und fügen sie dann hinzu. Im Pops-Fall gehen wir bis zum Ende der verknüpften Liste, um sie daraus zu entfernen. Nun, da man das weiß, ist die Speicherkomplexität konstant. Die Speicherkomplexität, alles, was Sie tun, ist eine neue Verbindung herzustellen , und das ist O von einem Speicherpreis. Du erstellst keine ganz neue Liste. Sie erstellen keine weitere Datenstruktur , in der Elemente gespeichert werden. Du erstellst nur einen Link. Die Speicherkosten sind O von eins. Pausiere jetzt das Video hier und versuche es zu codieren. Schreiben wir jetzt den Code auf. Also hier werden wir Push so ziemlich wie das zuvor neu implementierte Append implementieren . Wir definieren zuerst einen lokalen Variablenlink, unsere aktuelle verknüpfte Liste ist , und dann, während link.next nicht keiner ist. Während wir also etwas haben, das verlinkt ist, lasst uns sie durchgehen. [LÄRM] Dann werden wir ganz am Ende einen neuen Link hinzufügen. Das ist so ziemlich alles für die Push-Funktion-Push-Methode. Gehen wir jetzt zum nächsten über. Um etwas zu entfernen, setzen wir diesen lokalen Variablenlink erneut diesen lokalen Variablenlink auf unseren Anfang mit der verknüpften Liste. Dann, während wir eins vom Ende entfernt sind, also nicht wirklich den allerletzten Link wollen, wollen wir den vorletzten Link , weil das unser neuer Schwanz sein wird . Wir werden wieder durchqueren. Dann werden wir an dieser Stelle zuerst den Wert des allerletzten Artikels bevor wir ihn tatsächlich entfernen. Hier wollten wir den Wert des allerletzten Links ermitteln. Als nächstes werden wir es trennen. Jetzt deutet unser vorletzter Link auf nichts hin. Dies ist jetzt unser brandneuer letzter Link, und dann geben wir endlich den Wert zurück. So löschen wir tatsächlich ganz am Ende der verlinkten Liste. Lassen Sie uns weitermachen und auf die grüne Schaltfläche ganz oben klicken, um unsere Datei auszuführen und unsere Tests zu überprüfen . Da haben wir's. Wir können jetzt sehen, dass unser Stack via Linked List tatsächlich weg ist. Es gibt keine Fehler mehr in unserer Liste, daher haben wir diese Tests bestanden. Gehen wir zum nächsten Problem über. Bevor ich auf dieses Problem eingehe, haben wir noch einen Tipp. Sie möchten ganz einfach eine Ihrer eigenen Fragen stellen einfach eine dieser Fragen mischen und abgleichen. Sie haben über drei verschiedene Datenstrukturen, verknüpfte Listen, Stacks und Warteschlangen gesprochen . Um eine neue Frage zu erstellen, implementieren Sie einfach, wählen Sie eine aus und wählen Sie dann eine andere aus. Jede dieser Kombinationen gibt Ihnen ein brandneues Problem , das Sie ausprobieren können. Solange Sie dieselben Tests bestehen können , die Sie für einen Stack geschrieben haben , außer Ihre brandneue Datenstruktur zu verwenden , können Sie loslegen. Das gilt für alles andere. Wenn Sie Tests für die Warteschlange haben, stellen Sie einfach sicher, dass Ihre brandneue Datenstruktur diese Tests bestehen kann, und dann wurden Tests verlinkt Liste usw. Kombinieren Sie jede dieser Kombinationen um ein brandneues Problem zu erhalten. Lassen Sie uns nun die Zyklusentfernung für eine verknüpfte Liste implementieren. Suchen und entfernen Sie insbesondere einen Zyklus in einer verknüpften Liste, falls dieser vorhanden ist. Im Moment können Sie der Einfachheit halber davon ausgehen, dass alle Linkwerte unterschiedlich sind. Dies ist sehr wichtig da die erste Frage, die Sie berücksichtigen werden, wenn Sie den Zyklus Suchen und Entfernen sehen , lautet: Wie werden Sie einen Zyklus erkennen? Eine Möglichkeit, einen Zyklus zu erkennen, wäre, wenn ich diesen Wert schon einmal gesehen habe , dann weiß ich, dass ich einen Zyklus erreicht habe. Ich schätze, um es klarzustellen. Angenommen, Sie bewegen sich entlang dieser verknüpften Liste von links nach rechts. Wenn Sie im weiteren Verlauf plötzlich zweimal drei sehen, wissen Sie, dass Sie einen Zyklus erreicht haben. Aber das können Sie nur sagen, wenn Sie wissen, dass alle Linkwerte unterschiedlich sind. diesem Grund ist die Unterscheidung von Linkwerten eine sehr wichtige Frage für dieses Problem. Ich schrieb, dass hier alle Werte einzigartig sind. Das wird eine Ihrer ersten Fragen an Ihren Interviewer sein. Ihre zweite Frage, und das ist eher eine fortgeschrittene Frage. Sie möchten fragen, gibt es eine maximale Zykluslänge? Das hat mit der Implementierung zu tun, denn wenn Sie alle Werte verfolgen möchten , die Sie bisher gesehen haben, und dann sagen möchten: „In Ordnung, habe ich diesen Wert schon gesehen?“ Dann könnten Sie möglicherweise nie einen Zyklus sehen. Diese gesamte verknüpfte Liste könnte eine Million lang sein und dass es nirgendwo einen Zyklus gibt, dann haben Sie es im Grunde genommen in diesem riesigen Laden mit einer Million Artikeln aufbewahrt , um zu sehen, ob eine dieser Millionen Artikel werden wieder angezeigt. Dies ist eine gute Frage , ob es eine maximale Zykluslänge gibt? Denn auf diese Weise müssten Sie nicht alle Millionen Artikel behalten , wenn Sie wissen, dass die maximale Zykluslänge nur fünf beträgt. Dies sind gute Fragen, die Sie bei diesem Problem beachten sollten. Während Sie diese Probleme weiterentwickeln und üben, werden Sie verstehen, welche Fragen Sie stellen müssen. Wenn Sie also vorerst denken, dass dies aus heiterem Himmel verrückte Fragen sind , können Sie niemals darüber nachdenken, das ist okay. So wie Sie immer mehr davon sehen, werden Sie sich mit den Fragen vertraut machen , die Sie stellen müssen. Lassen Sie uns vorerst sehen, ob Sie sich einen Algorithmus vorstellen können. Ich habe Teile davon weggegeben aber pausiere das Video hier und sehe, ob du eine Möglichkeit finden kannst , Zyklen zu entfernen , und hier ist die Antwort. Im Grunde werden Sie eine Sammlung aller Werte führen , die Sie bereits gesehen haben. Wenn Sie den Wert bereits gesehen haben, wissen Sie, dass dies ein Zyklus ist und Sie können den Zyklus unterbrechen indem Sie link.next einfach entsprechend neu zuweisen. Wenn man das weiß, ist das jetzt der Algorithmus. Wie hoch ist die Laufzeit und Speicherkomplexität? Pausiere das Video hier. Für die Speicher- und Laufzeitkomplexität , insbesondere für die Rechenkomplexität haben Sie O von N. Wir werden die gesamte Liste nacheinander durchgehen . Wir müssen das tun, um herauszufinden, ob es einen Zyklus gibt oder nicht. Die zweite Frage ist, was bedeutet die Speicherkomplexität? Aus Gründen der Speicherkomplexität werden wir erneut eine Sammlung all der verschiedenen Werte führen , die wir bisher gesehen haben. Das ist eine O of N-Speicherkomplexität. O von N Speicherkomplexität und O von N Rechenkomplexität. das wissen, versuchen wir jetzt, es zu codieren. Pausiere das Video hier. Lassen Sie uns jetzt weitermachen und das programmieren. Hier beginnen wir mit Schaffung einer Reihe von Werten. Wenn Sie dies also noch nicht gesehen haben, ist ein Set eine Datenstruktur , mit der Sie in konstanter Zeit nach der Mitgliedschaft suchen können . Das heißt, Sie können so etwas in einer Szene machen, und das, egal wie lang Ihr Set ist, wird immer in konstanter Zeit ausgeführt. Das ist ein Set. Wir werden das Set verwenden, um alle Werte zu verfolgen , die Sie bisher gesehen haben. Es gibt zwar noch etwas anderes in unserer verknüpften Liste, wir werden überprüfen, ob der nächste Wert in unserer Szenenwerteliste steht. Wenn ja, brechen wir die Verbindung mit dem nächsten Link ab. Nochmals, wenn der nächste Link in unserer Liste ist, habe ich Werte gesehen, wir werden diesen Link brechen und wir werden hier enden. Wir gehen davon aus, dass es in unserer Liste nur einen Zyklus gibt. Auch das wäre eine gute Frage, die Sie Ihrem Interviewer stellen sollten. Wird es mehr als einen Zyklus geben? In dieser speziellen Frage werden wir so tun, als gäbe es nur einen Zyklus. seen.add und dann haben wir den Wert genau hier verknüpft. Was wir hier tun, ist, dass wir sagen, in Ordnung, wir haben darüber nachgedacht, dass es hier keinen Zyklus gibt. Da es keinen Zyklus gibt, fügen wir den aktuellen Linkwert zu unserer Liste der Sehwerte hinzu. Schließlich ist dies der Standard für eine verknüpfte Listendurchquerung Wir werden nur auf den nächsten Punkt zugreifen und es wird weitergehen. Das war's. Lassen Sie uns diese Funktion ausführen und sicherstellen, dass unsere Tests erfolgreich sind. Los geht's, wir können sehen, dass der Entfernungszyklus nicht mehr in unserer Liste der fehlgeschlagenen Funktionen enthalten ist. Gehen wir zur nächsten Frage über. Für die nächste Frage, und auch für diese, ist ein Tipp, immer Ihre verknüpften Listen zu zeichnen und nach defekten Links zu suchen. Was ich mit Zeichnen meine sind im Grunde die Illustrationen , die ich zuvor hier hatte. Wenn es eine Mischung sein muss, ziehen Sie diese heraus, um zu verstehen, ob Sie alle auf die richtige Weise verknüpfen. Ich bin ziemlich schnell durch einige dieser Fragen gegangen , weil ich die Lösung bereits geschrieben habe und die Lösungen kenne. Aber wenn Sie ein brandneues Problem haben, ist die Wahrscheinlichkeit, dass Sie einen falschen Link erstellen, im Grunde sehr hoch. Das ist völlig in Ordnung, solange du es herausziehst. Wenn Sie es herausziehen, können Sie die richtigen Links für die Verbindung ausarbeiten . Das ist einer meiner Tipps hier. Zeichne deine verknüpfte Liste und suche nach defekten Links. Nun, zu diesem speziellen Problem werden wir es nur konzeptionell diskutieren. Ich habe tatsächlich eine voll funktionsfähige Lösung im Code für Sie geschrieben , aber weil sie ziemlich komplex ist, werden wir nur algorithmisch darüber sprechen. Für diese Frage ist es unser Ziel, ein neues Dateiobjekt zu verwenden oder zu erstellen indem wir die Datenstrukturen verwenden , die wir bereits gesehen haben. Unser Dateiobjekt wird mit anderen Dateien zusammengeführt. [GELÄCHTER] Ich habe Ihnen gerade einen Teil der Beschreibung der Lösung gezeigt . Ihr Ziel ist es jedoch, ein Dateiobjekt zu erstellen , das offiziell mit anderen Dateien zusammengeführt werden kann. Die Idee ist, dass es viele dieser Dateien gibt. Das bedeutet, dass Sie nicht alle Daten in eine riesige Datei kopieren möchten . Wenn Sie das ganze Kopieren machen, wird es sehr lange dauern. Wie können wir eine Reihe von Dateien kombinieren, ohne sie zu kopieren? Wenn Sie den Hinweis nicht möchten, pausieren Sie das Video hier. Aber ein Hinweis, den ich für Sie habe, ist, dass wir nicht kopieren wollen. Anstatt zu kopieren, speichern wir einen Zeiger auf die nächste Datei. Wir haben Datei 1 und dann sagen wir, aus Datei 1 wissen wir, was die nächste Datei ist Datei 2. Alles was Sie tun werden, ist eine Verbindung oder einen Zeiger zu speichern . Das sollte furchtbar nach einer der Datenstrukturen klingen , die wir gerade behandelt haben und die ich verwendet habe. Halten Sie nun das Video hier an und prüfen Sie, ob Sie den Algorithmus herausfinden können. Jetzt ist hier die Lösung. Im Grunde verwenden wir eine verlinkte Liste. Jede einzelne Datei wird ein Link sein. Jede Datei zeigt dann auf die nächste Datei und sagt, dass dies der nächste zu durchquerende Dateiwert ist. So werden Sie diese riesige zusammengeführte Datei speichern . Aber das ist noch nicht alles, es gibt noch ein bisschen mehr , weil wir diese Zusammenführungsfunktion unterstützen müssen. Zu wissen, wie wir sie lagern, ist großartig. Wir müssen keine Kopien anfertigen, aber wie führt man eigentlich eine neue Datei zusammen? Nun, die neue Datei, genau wie Sie sie zu jeder anderen verknüpften Liste hinzufügen würden. Sie gehen so ziemlich bis zum Ende der verknüpften Liste und fügen die neue Datei hinzu. Das ist so ziemlich alles. Für dieses Problem oder diese Übung die einzige konzeptionelle Schwierigkeit darin , zu erkennen, dass Sie eine verknüpfte Liste verwenden müssen. Das war wirklich das Zeigerproblem. Jetzt, da wir das Zeigerproblem behandelt haben, werden wir weitermachen, nur weil ich dafür eine schriftliche Lösung habe und es zeilenweise Anmerkungen für das gibt , was jeder ist und wie es funktioniert aber die Details sind nicht besonders wichtig. Gehen wir zur nächsten Frage über. Nochmals, ist kein anderes Schiff hier. Verknüpfte Listen, die wir für Sammlungen dynamischer Größe verwenden. In diesem speziellen Fall ist dieser Satz von Dateien ein Satz von Sammlungen mit dynamischer Größe. Wir wissen nicht, wie groß es ist, wir könnten es ein paar Mal ergänzen und wir könnten es sogar ein paar Mal entfernen. Verknüpfte Listen eignen sich hervorragend für diese Sammlungen, da Sie keine Daten kopieren müssen, wenn Sie ein Objekt hinzufügen oder entfernen möchten. Immer wenn Sie einen Link hinzufügen oder entfernen möchten , ist es konstante Zeit. Jetzt eignen sich Arrays jedoch perfekt für den Direktzugriff. Wir haben schon ein wenig darüber gesprochen , aber im Grunde bedeutet das , dass Sie genau wissen, wo es sich im Speicher befindet, wenn Sie auf das ith-Element in einem Array zugreifen möchten . Du gehst direkt zu diesem Teil in der Erinnerung. Wenn Sie jedoch für eine verknüpfte Liste das i-te Element so haben möchten , wie Sie es zuvor gesehen haben, müssen Sie die gesamte Liste durchqueren, also nicht ganz so effizient. Das ist der Tipp. Verknüpfte Listen sind für Sammlungen mit dynamischer Größe vorgesehen, Arrays sind für den Direktzugriff vorgesehen. Für unsere letzte Frage hier ist es Ihr Ziel, Datenstrukturen zu kombinieren, um ein Palindrom in einer verknüpften Liste zu finden. Ein Palindrom ist ein Wort, das genauso rückwärts gezüchtet wird wie Sportarten wie Rennwagen. Wenn du den Rennwagen umdrehst, bekommst du immer noch einen Rennwagen. Hier wird Ihr Wort als verknüpfte Liste dargestellt. Hier haben wir einen Link , der r enthält, und der auf den nächsten Link zeigt, der a enthält, auf den nächsten Link zeigt, der c hat, und dann auf e zeigt, auf c zeigt, auf a zeigt, so weiter und so fort. Unsere verlinkte Liste steht für das Wort Rennwagen. Wir wollen überprüfen, ob es sich bei dieser verlinkten Liste um ein Palindrom handelt. Überlegen Sie, welche anderen Datenstrukturen Sie verwenden können, um in dieser verknüpften Liste ebenfalls ein Palindrom zu sehen. Pausiere das Video hier und sieh nach, ob du es herausfinden kannst. Die konzeptionelle Lösung für diese ziemlich herausfordernde Aufgabe ist dass Sie sowohl einen Stack als auch eine Warteschlange wollen. Während Sie diese verknüpfte Liste durchlaufen, fügen Sie sie sowohl dem Stapel als auch der Warteschlange hinzu. Wenn Sie dann mit der Wartung der gesamten verknüpften Liste fertig sind, einfach die Schrägstrich-Dekeue, entfernen Sie sie einfach aus jeder Stapelwarteschlange und überprüfen Sie dann , ob jede dieser Listen gleich ist. Das ist großartig, weil der Stapel vom Ende entfernt wird, die Warteschlange vom Anfang sodass Sie sich im Grunde genommen rückwärts und vorwärts gleichzeitig entlang der Saite bewegen rückwärts und vorwärts gleichzeitig entlang der Saite gleichzeitig entlang der aus dem Stapel und der Warteschlange entfernen. Das ist perfekt für uns, denn in einem Palindrom besteht eine Möglichkeit, zu überprüfen, ob es sich um ein Palindrom handelt, darin, zu überprüfen ob der erste Charakter ist, dass Sie der letzte sind. Beim zweiten geht man zum vorletzten und so weiter und so fort. aus dem Stapel und der Warteschlange entfernen, erhalten Sie das. Lass uns gleich hier innehalten. Mal sehen, das ist der Algorithmus. Wie hoch ist die Laufzeit und Speicherkomplexität? Hier ist die Antwort. Sowohl für die Laufzeit als auch für Speicherkomplexität haben wir lineare Komplexität. Denn die Speicherkomplexität ist linear, weil wir einen Stack und eine Warteschlange speichern, die jeweils bis zur Länge n haben könnten, und wir haben auch lineare Rechenkomplexität, weil wir iterieren über jeden dieser Buchstaben. Tatsächlich wiederholen wir zweimal, aber es spielt keine Rolle, es ist o of n. Jetzt wir den Algorithmus und die Komplexität kennen, versuchen wir , ihn zu codieren. Pausiere das Video hier und versuche es zu codieren. Lassen Sie uns nun die Lösung behandeln. Wir beginnen damit, sowohl den Stack als auch eine Warteschlange zu initialisieren . Nachdem wir diese beiden Datenstrukturen haben, wir die verknüpfte Liste durch, wie gesagt, und für jeden einzelnen Link werden wir sie zu diesen beiden Datenstrukturen hinzufügen. Hier werde ich den Stack hinzufügen. Ich werde den Stapel pushen und dann werde ich mich auch in die Warteschlange stellen. Dann gehe ich zum nächsten Link. Wie ich bereits sagte, ist dieser Traversal-Code so ziemlich immer derselbe. Nachdem wir das abgeschlossen haben, gehen wir nun diese beiden Datenstrukturen, den Stack und die Warteschlange, durch und stellen sicher , dass sie für jedes einzelne Element, das wir entfernen, genau gleich sind. Während sich etwas im Stapel befindet, gehen vom Stapel und entfernen Sie die Warteschlange aus der Warteschlange. Solange sie übereinstimmen, können wir loslegen. Wenn sie zu keinem Zeitpunkt übereinstimmen, geben wir false zurück. Wenn nichts falsch zurückgibt, alle überein und wir können true zurückgeben. Das war's. Lassen Sie uns jetzt weitermachen und das bewerten. ganz oben auf die grüne Schaltfläche Ausführen und überprüfen Sie, ob alle Ihre Tests bestanden haben. Hier können wir sehen, dass unsere Funktion Palindrome Link ist nirgendwo in der Liste der Fehler zu finden. Wir haben diesen Test erfolgreich bestanden. Diese drei verbleibenden Funktionen sind Bonusfunktionen. Ich habe auch vollständig ausgearbeitete Lösungen für sie und Erklärungen in den Code aufgenommen , sodass Sie diese auch in Ihrer Freizeit ausprobieren können. Wenn Sie Fragen haben, können Sie diese gerne im Diskussionsbereich posten. Das war's für diese Lektion. Gehen Sie weiter zu den Folien, für den vollständig ausgearbeiteten Code und Lösungsart, um die Kurswebsite zu besuchen. Das war's für Listen, sowohl Arrays als auch verknüpfte Listen. 9. Karten: Hashmaps: In dieser Lektion stellen wir eine Datenstruktur für Mappings vor. Ein Mapping ist das, wonach es sich anhört, ein Mapping von einem Element zum anderen. Hier ordnen wir Katze der Nummer fünf zu. Nehmen wir in diesem Fall an, wir kartieren das Tier dem Alter. Tier ist das, was wir den Schlüssel in der Kartierung nennen, und Alter ist das, was wir den Wert in der Kartierung nennen. Wir können auch zusätzliche Schlüsselwertpaare im Mapping haben. Beachten Sie, dass diese Zuordnung keinen Ordnungssinn hat, jedes Schlüsselwertpaar ist vollständig voneinander getrennt. Die Datenstruktur, die dieses Mapping speichert , wird HashMap genannt. Wir erklären, wie eine HashMap funktioniert, diskutieren ihre Vor- und Nachteile und besprechen dann kurz ein Bonuskonzept. Deshalb wird diese Datenstruktur als Hash-Map bezeichnet. Im Kern verwendet eine HashMap eine Funktion, als Hash-Funktion bezeichnet wird. Diese Hash-Funktion nimmt einen Wert mit beliebiger Länge auf, wie cat, und transformiert diese Eingabe dann , um eine Ausgabe mit fester Größe wie zwei zu erzeugen. Diese Hash-Funktion ist wichtig, und so wie diese Ausgabe auch, schauen wir uns an, wie beide verwendet werden. Angenommen, wir wollen einige Schlüssel und Werte in eine Hash-Tabelle einfügen . Auf der rechten Seite haben wir eine Hash-Tabelle, in der Null die Speicheradresse des ersten Steckplatzes ist, eine die Speicheradresse des zweiten Steckplatzes und so weiter und so fort. Wir wollen die Schlüsselkatze dem Wert fünf zuordnen, dazu hashen wir den Wert cat. Dies gibt uns die Speicheradresse 2, also in Position zwei den Wert fünf setzen. Wir wiederholen dies für weitere Daten, um Hund auf drei zuzuordnen, Hash Dog. Dies gibt uns die Speicheradresse 3, also platzieren Sie in Position drei den Wert drei. Wir wiederholen dies noch einmal, um Schwein auf vier, Hash Pig, zuzuordnen. Dies gibt uns die Speicheradresse Null, also in der Position Null den Wert vier setzen. Dieser Prozess benötigt nur eine Konstante oder O von einem Mal für jedes Schlüsselwertpaar, das wir einfügen. Um aus der HashMap zu löschen, wir ähnliche Schritte durch. Um cat aus der HashMap zu löschen, zuerst hash cat, um zwei zu erhalten, dann an der Position zwei den Wert entfernen. Diese Operation ist ebenfalls konstant oder O von einer Zeit. Zusammenfassend lässt sich sagen, dass das Einfügen und Löschen für eine HashMap beide O einer Zeit sind. Sehr schnell. Nehmen wir an, wir wollen jetzt die HashMap durchsuchen, deren Wert cat entspricht. Fast derselbe Vorgang, hashen Sie die Katze, um ihre Speicheradresse zu erhalten, die zwei ist. Sie dann an Position zwei Nehmen Sie dann an Position zwei den Wert fünf und geben Sie ihn zurück. Als Ergebnis sagen wir, dass die Suche nach einer HashMap die Konstante O benötigt, wiederum O von einmal. Zusammenfassend lässt sich sagen, dass das Durchsuchen einer HashMap Konstante O von einer Zeit benötigt. Bei einer HashMap sind Suchen und Abrufen gleich, daher überspringen wir die separate Analyse des Abrufs. Lassen Sie uns nun die Vor- und Nachteile dieser HashMaps verstehen. Zusammenfassend haben HashMaps einige sehr beeindruckende Laufzeiten, konstante Zeit, Änderung und Zugriff. Aufgrund der Funktionsweise von HashMaps sind sie ideal für alle Daten mit eindeutigen Kennungen. Per Definition sind HashMaps nicht für Auftragsdaten ausgelegt. Wie bereits erwähnt, jedes dieser Schlüsselwertpaare vollständig getrennt. Es gibt keinen Sinn für Ordnung, es gibt keine Beziehung zwischen getrennten Schlüsselwertpaaren. Wir haben bereits die ersten beiden Abschnitte besprochen, was eine HashMap ist und wofür sie ideal ist. Wir werden den Bonusbereich besprechen nachdem wir den Kerninhalt abgeschlossen haben. Eine Kopie dieser Folien und weiterer Ressourcen finden Sie auf der Kurswebsite. Damit ist unsere Kerndiskussion zu HashMaps abgeschlossen. Wenn Sie mit diesem Detaillierungsgrad zufrieden sind, können Sie mit der kommenden Lektion mit HashMap-Praxis fortfahren . Ansonsten besprechen wir jetzt den Bonus-Abschnitt. Insbesondere haben wir einen Vorbehalt für HashMaps besprochen , der Hash-Kollisionen genannt wird. Wir haben zuvor gesagt , dass HashMaps eine konstante Zeit für Änderungen und Zugriff sind . Dies ist jedoch nicht immer der Fall. Laufzeit hängt tatsächlich davon ab, wie eine HashMap implementiert wurde und hier ist der Grund dafür. Manchmal tritt dieses Phänomen auf, wenn es zuvor erwähnt wurde, eine Hash-Kollision. Angenommen, wir möchten zwei Schlüsselwertpaare einfügen, Katzen-Maps für fünf und Hundekarten für drei. Nach wie vor hashen wir Katze, um zwei zu bekommen. Auf Position zwei setzen wir dann den Wert fünf, das ist wie zuvor. Um nun unser zweites Schlüsselwertpaar einzufügen, haben wir einen Hash-Dog, um zwei zu erhalten, an Position zwei haben wir jetzt ein Problem. Wir können die vorhandenen Daten nicht überschreiben, daher haben wir zwei Möglichkeiten. Die erste Option heißt offene Adressierung. Bei der offenen Adressierung finden wir einfach einen anderen Slot in der HashMap Wenn dieser nächste Slot leer ist, platzieren Sie Ihren neuen Wert dort. Eine Möglichkeit, einen leeren Slot zu finden, besteht darin, einfach die Slots zu durchqueren, bis Sie einen leeren finden, und dort Ihren Wert zu platzieren. Es gibt auch Strategien für die Slot-Suche, die wir hier nicht eingehen werden. Eine andere völlig andere Technik zur Behandlung von Hash-Kollisionen heißt Chaining. Bei dieser Technik behandeln wir jeden Slot als eine eigene Datenstruktur. Zum Beispiel könnten wir jeden Slot als verknüpfte Liste behandeln Um dann in Position zwei einzufügen, fügen wir einfach drei in die verknüpfte Liste ein. Wir können jeden Slot auch als HashMap behandeln, jede Datenstruktur, die wir machen, jede mit ihren eigenen Kompromissen erneut. Zusammenfassend haben wir eine Hash-Kollision definiert und auch zwei Möglichkeiten gesehen, mit einer Hash-Kollision umzugehen. Offene Adressierung oder wir finden andere leere Slots zur Verwendung oder Verkettung, bei denen wir jeden Slot als seine eigene Datenstruktur behandeln . Damit ist unser Bonusabschnitt hier über Hash-Kollisionen Lesen Sie unbedingt unsere nächste Lektion zum Üben mit HashMaps. 10. Mappings: Willkommen bei der Praxis der Mappings-Datenstruktur. Auch hier werden wir weitere Übungen üben und einige Interviewtipps zur Mapping-Datenstruktur durchgehen . Insbesondere werden diese Datenstrukturen auch Hashmaps genannt. Also werden wir diese Namen oft verwenden, Hashmaps. Navigiere wie zuvor zu dieser URL alvinwan.com/datastructures101/mappings. Das bringt dich zu repl.it. Ich weiß, dass wir jetzt mehrmals über diese Anweisungen gesprochen haben . Ich werde es noch einmal durchgehen, nur für den Fall, dass Sie, sobald Sie diese Seite sehen, das Projekt forken, um Ihre eigene bearbeitbare Kopie zu erhalten. Klicken Sie oben links auf den Projektnamen , um ein Dropdown aufzurufen. Klicken Sie auf die Ellipse, um ein weiteres Dropdown zu erhalten, und klicken Sie dann auf die Schaltfläche „Fork“. Dann schlage ich vor, Ihren Skillshare und die repl.it-Fenster nebeneinander zu platzieren , wie hier gezeigt. Sie sollten dann etwas sehen, das so aussieht, wie Sie es auf der rechten Seite haben. Lassen Sie uns jetzt über die Arten von Übungen sprechen , die Sie sehen werden. Sie haben die Übungen zur Implementierung, Verwendung und Kombination. Wenn Sie nach unten scrollen, sehen Sie, dass unsere allererste Übung hier darin besteht, einen Stack zu implementieren. Wir werden das in drei Schritten machen, genau wie wir es in allen anderen Lektionen getan haben. Wir werden zuerst den Algorithmus ohne Code entwerfen . Wir werden die Laufzeit und Speicherkomplexität melden. Dann werden wir den Algorithmus tatsächlich codieren. Wenden wir diese drei Schritte auf den allerersten Algorithmus an, oder unsere erste Übung hier. Implementieren Sie einen Stack, der alle Werte im Stack auf nur drei Vorkommen begrenzt . Wenn ein Wert verschoben wird , der mehr als drei Vorkommen aufweist, ignorieren Sie diesen Wert einfach. In diesem speziellen Fall haben wir hier ein Beispiel. Wir initialisieren zuerst einen Stack und dann drücken wir den Wert ein,10 mal. Allerdings werden nur die ersten drei Werteinheiten tatsächlich zum Stack hinzugefügt. Alles andere wird ignoriert. Sie können dann andere Werte als einen pushen und es wird normal zum Stack hinzugefügt. Mach weiter und probiere das aus. Entwerfen Sie zunächst den Algorithmus , der diesen Stack tatsächlich mit einem Limit implementiert. Pausieren Sie das Video hier und versuchen Sie, einen Algorithmus herauszufinden. Hier ist die algorithmische Lösung. Was wir tun werden , ist zuerst die Baseline-Stack-Implementierung zu verwenden. Sie können hier also sehen, dass meine Capped Stack-Klasse tatsächlich von der Basis-Stack-Klasse erbt. diesem Wissen werden wir Beschränkungen auferlegen, wann Sie tatsächlich auf einen Stack pushen können , und das war's. Dazu behalten wir eine HashMap ordnen alle Werte ihren Zählungen im Stapel zu. Jedes Mal, wenn Sie pushen, erhöhen Sie diesen Wert. Wenn dieser Wert das Limit überschreitet, ignorieren wir den Wert einfach und Pop wird dann sicherstellen, und Pop wird dann sicherstellen dass diese Anzahl verringert wird. In Push überprüfen Sie die Anzahl, fügen sie hinzu, wenn die Zählung in Ordnung ist, und erhöhen dann die Anzahl. Im Pop dekrementierst du die Anzahl. Das ist also der Algorithmus. Lassen Sie uns nun die Laufzeit und die Speicherkomplexität diskutieren. Pausieren Sie das Video hier und sehen Sie, ob Sie es herausfinden können. Für die Laufzeitkomplexität ist es unabhängig von der Komplexität des ursprünglichen Algorithmus. In diesem speziellen Fall ist Push linear und Pop ist die Art, wie wir es implementiert haben, auch linear. Sowohl Push als auch Pop sind also lineare Operationen. Nun zur eigentlichen Speicherkomplexität, also wie sieht das aus? Nun, wir müssen hier einen neuen Wert schaffen. Es ist nicht genau o von n. Wir haben für jeden neuen Wert einen Wert zur HashMap hinzugefügt, aber das sind nicht so viele wie die Anzahl der Gesamtwerte, die wir hinzugefügt haben. Wir haben nur die Anzahl der eindeutigen Werte in unserer HashMap. Wir müssen einen neuen Brief erfinden. Anstelle von o von n sagen wir zum Beispiel, dass es o von k ist, und wir definieren k als die Anzahl der eindeutigen Werte, die dem Stack hinzugefügt wurden. Wenn du das tatsächlich in einem Interview hättest, würdest du so etwas sagen. Wir müssen tatsächlich eine neue Variable definieren, k, wobei k die Anzahl der eindeutigen Werte ist, und unser Algorithmus, unsere Speicherkomplexität für unseren Algorithmus ist o von. Das war's wegen der Komplexität. Gehen wir nun zum Code über. Also pausiere das Video hier und versuche zu programmieren. Im Konstruktor werden wir einen neuen Zähler initialisieren. Aus Sammlungen importieren, default, dict. Dies ist eine andere Art von Wörterbuch. Dieses Wörterbuch initialisiert diesen Wert mit dieser Funktion, wenn Sie auf einen Schlüssel zugreifen, der keinen aktuellen Wert hat. In diesem speziellen Fall ist 0 für diesen Zähler, wenn wir sagen, wir greifen auf Zähler 0 zu, derzeit kein gültiger Schlüssel für dieses Wörterbuch, also wird es mit dieser int-Funktion initialisiert. Die Standardeinstellung für die int-Funktion ist Null. Standardmäßig gibt mir der Selbstzähler von 0 0 0. In der Tat, Selbstzähler von allem, wird mir auch 0 geben. So funktioniert dieses Standardwörterbuch, und dadurch sieht ein Teil des Codes nur ein bisschen einfacher aus. Jetzt, wo ich das habe, implementieren wir jetzt die Push-Funktion. Wie wir bereits gesagt haben, überprüfen wir zunächst , ob die aktuelle Anzahl unter dem Limit liegt. Wenn es unter dem Limit liegt, fahren wir fort. Wenn es unter dem Limit liegt, erhöhen wir die Anzahl tatsächlich und schieben sie dann tatsächlich auf den Stapel. Im Pop verringern wir einfach die Anzahl. Hier werden wir zuerst den Wert kennenlernen. Hier springen wir vom Stapel, und sobald wir diesen Wert platzen, wird die Anzahl für diesen Wert verringert, und dann geben wir den Wert zurück. Mal sehen, ob unsere Cap-Stack-Tests erfolgreich sind. Ganz oben drücken Sie den grünen Knopf und los geht's, Cap Snack ist jetzt nicht mehr in der Liste der Fehler, also haben wir diesen Test bestanden. Gehen wir zur nächsten Frage über. Ein Tipp ist, dass Hashmaps ideal für Daten mit eindeutigen IDs sind. In diesem speziellen Fall wissen wir, dass jeder einzelne Wert oder die Prämisse des Problems darin besteht, dass wir festlegen , ob wir durch den Wert auf den Stapel pushen sollen oder nicht . Der Wert selbst ist also die eindeutige ID. Da wir diese eindeutige ID haben, waren Hashmaps perfekt für dieses Problem. Hashmaps sind jedoch am schlechtesten für geordnete Daten. Wenn es eine Beziehung zwischen Ihren Daten gibt, nehmen wir an, ich habe eine Folge von Zahlen, eine bis zu 10, und ich muss diese Reihenfolge kennen. Oder eine andere Art, es auszudrücken, sagen wir, ich habe 10 Werte und füge sie in eine Datenstruktur ein. Wenn ich mich an die Reihenfolge erinnern muss, in der ich es eingefügt habe, sind Hashmaps nicht die zu verwendende Datenstruktur, da Hashmaps die gesamte Reihenfolge vergessen. Sie führen lediglich eine Zuordnung von Schlüsseln zu Werten durch. Sie erinnern sich an nichts darüber in welcher Reihenfolge Sie die Schlüssel einsetzen. Das ist also wichtig. Hashmaps sind ideal für Daten mit eindeutigen IDs, aber sie eignen sich nicht so gut für Daten, bei denen die Reihenfolge wichtig ist. für unsere nächste Frage nach unten, Scrollen Sie für unsere nächste Frage nach unten, um die nächste Frage zu sehen. Gibt ein Histogramm aller eindeutigen Buchstaben und ihrer Anzahl von Vorkommen zurück. Ich schätze, das hätte zuerst gehen sollen. Dies ist eine Teilmenge des vorherigen Problems. Sie Halten Sie das Video hier und prüfen Sie, ob Sie den Algorithmus herausfinden können. Die Lösung besteht konzeptionell darin, dass wir eine HashMap als Zähler initialisieren, und jedes Mal, wenn wir über die Zeichenfolge iterieren, und für jeden einzelnen neuen Wert greifen wir auf unseren Zähler zu. Wenn wir diesen Wert bereits gesehen haben, werden wir der Anzahl einen hinzufügen. Wenn wir diesen Wert noch nicht gesehen haben, initialisieren wir die Zählung auf eins. Das ist also der Algorithmus. Wie hoch ist die Laufzeit und Speicherkomplexität? Pausiere das Video hier. Hier ist die Antwort. Die Laufzeitkomplexität ist linear. Wir müssen über jeden einzelnen Buchstaben in der Zeichenfolge iterieren . Daran führt kein Weg vorbei. Die zweite, Speicherkomplexität. Auch hier müssen wir eine brandneue Variable erfinden. Variable ist die Anzahl der eindeutigen Werte, sagen wir k. Dieser Algorithmus ist o von k, wobei k die Anzahl der eindeutigen Werte ist, die in der Zeichenkette enthalten sind. Das war's für die Combine-Serie, versuchen wir jetzt, es zu codieren. Pausiere das Video hier und probiere den Code aus. Lassen Sie uns nun die Lösung im Code behandeln. Hier erstellen wir einen Zähler. Dieser Zähler wird ein Wörterbuch sein. In der Tat werde ich das Standardwörterbuch von früher verwenden. Auf diese Weise wird das Wörterbuch auf Null initialisiert. Hier haben wir aus Sammlungen, Import, Defaultdict. Dann erhöhen wir hier für jeden einzelnen Buchstaben in der Zeichenfolge die entsprechende Anzahl. Hier erhöhen wir die entsprechende Anzahl und geben schließlich den Zähler zurück. Jetzt möchte ich auch die Implementierung ohne dieses Defaultdict zeigen . Nehmen wir an, Sie haben das defaultdict nicht verwendet. Nehmen wir an, Sie erstellen einfach ein normales Wörterbuch. Dann würden wir hier überprüfen, ob der Brief in der Theke ist. Wenn wir diesen Brief schon einmal gesehen haben, erhöhen wir ihn einfach um eins. Wenn wir das noch nie gesehen haben, initialisieren wir es auf eins. Gegenbuchstabe ist gleich Eins. Lassen Sie uns nun weitermachen und dies ausführen, um zu überprüfen, ob unique jetzt ein bestandener Test ist. Da haben wir's. Unique hat jetzt alle Tests bestanden. Wir haben auch diese Übung abgeschlossen. Gehen wir nun zur nächsten Übung über. Ein Tipp ist, sicherzustellen, dass Ihr Schlüssel vorhanden ist, bevor Sie darauf zugreifen. Das haben wir genau hier gemacht. In Zeile 103 haben wir überprüft, ob der Brief im Zähler war. Mit anderen Worten, wenn wir diesen Brief schon einmal gesehen hätten und es bereits einen gültigen Schlüssel in unserer Zuordnung gäbe. Wenn wir das wissen, gehen wir zu der Frage über, die danach kommt. Verwenden Sie unsere Datenstruktur, um den häufigsten Wert in einer Liste ganzer Zahlen zu finden . Ich habe ganze Zahlen angegeben , um das ein bisschen einfacher zu machen. Es gibt jedoch mehrere Fragen , die Sie Ihrem Interviewer stellen sollten. Die erste Frage wäre, wenn sie nicht die ganzen Zahlen angegeben hätten, würden sie es höchstwahrscheinlich nicht tun. Sie würden höchstwahrscheinlich Zahlen sagen. Dann würden Sie fragen wollen, kann es negative Werte geben? Kann es Dezimalwerte geben? Was ist die Reichweite? Was sind die möglichen Werte, die ich möglicherweise sehe? Die zweite Frage , die Sie stellen möchten, ist: Was ist, wenn es ein Unentschieden gibt? Dass die Frage selbst nicht genau definiert ist , wenn es einen Gleichstand gibt. Im Falle eines Gleichstands in dieser Problembeschreibung melden Sie nun eine der Zahlen, die für die größte Häufigkeit gebunden sind. Das wird normalerweise passieren. Aber das sind gute Fragen, die Sie stellen sollten und es gibt Ihnen einige Brownie-Punkte in Ihrem Interview. In dieser speziellen Frage haben wir eine Liste von Zahlen, und ich möchte herausfinden, was die häufigste ist, pausieren Sie das Video hier und sehen Sie, ob Sie den Algorithmus herausfinden können . Hier ist die Lösung. Wir werden etwas sehr Ähnliches wie zuvor tun. Wir werden eine HashMap verwenden , um die Anzahl für jeden einzelnen Wert in unserer Liste zu speichern . Sobald Sie diesen Zähler haben, verwenden Sie den Zähler, um herauszufinden , welcher der beste war. Das wäre eine Möglichkeit, das zu tun. Eine andere Möglichkeit , dies zu tun , für die keine zwei Datendurchläufe erforderlich , besteht darin sind, besteht darin, beim Hinzufügen zum Zähler eine Variable beizubehalten, die den häufigsten Wert darstellt. Wenn Sie einen Wert sehen, der plötzlich mehr Instanzen hat , ersetzen Sie diese Variable. Sie werden das in nur einer Sekunde in Aktion sehen. Konzeptionell besteht die Hauptidee jedoch darin, einen Zähler aller eindeutigen Werte beizubehalten einen Zähler aller eindeutigen Werte und diesen Zähler dann zu verwenden. Nachdem wir den Algorithmus kennen, pausieren Sie das Video hier und prüfen Sie, ob Sie die Laufzeit und die Speicherkomplexität herausfinden können . Hier ist die Antwort. Genau wie zuvor haben wir genau die gleiche Laufzeitspeicherkomplexität und die vorherigen Funktionen. Komplexität der Laufzeit wird linear sein. Sie müssen jedes einzelne Element in der Liste durchgehen . Daran führt kein Weg vorbei. Der zweite ist O von k, wobei k die Anzahl der eindeutigen Werte ist. Ich schätze, das wird jetzt ein Motiv. Aber zumindest für diese Übungen ist O of k das richtige Mal, also behalte das im Hinterkopf. Anzahl der eindeutigen Werte ist linear. Nachdem wir die Komplexität behandelt haben, haben wir den Algorithmus behandelt, das Video hier pausieren und den Code ausprobieren. Hier ist die Lösung. Schreiben wir das jetzt auf. Wir beginnen mit counter und counter wird ein leeres Wörterbuch sein. Der größte Wert wird keiner sein, sagen wir mal. Für den Wert in Zahlen prüfen wir, ob sich der Wert im Zähler befindet. Wenn wir diesen Wert schon einmal gesehen haben, werde ich das eigentlich ein wenig ändern. Wenn der Wert nicht im Zähler ist, initialisieren wir ihn auf Null. Unabhängig davon, was der Wert ist, erhöhen wir um eins. Wenn der Zähler größer als der größte Wert ist, also wenn die aktuelle Anzahl größer als die größte Anzahl , werden wir neu zuweisen und dann den größten Wert zurückgeben. Bevor Sie diese Funktion ausführen, sollten Sie etwas beachten, das eine der Taktiken ist, die ich in einem zukünftigen Kurs ansprechen werde, darin besteht, dass in einem zukünftigen Kurs ansprechen Sie Ihren Code immer virtuell ausführen sollten. Damit meine ich, führe einfach den Code in deinem Kopf aus, als wärst du der Interpreter. Wenn Sie vor dem Ausführen des Codes Fehler feststellen, ist dies normalerweise ein weiterer Grenzpunkt für Sie. In diesem speziellen Fall würden wir hier tatsächlich einen Fehler wegen des größten Zählers sehen . Am größten ist hier keiner und keiner existiert noch nicht im Counter. Dies geht auf unseren vorherigen Tipp zurück. Stellen Sie immer sicher, dass der Schlüssel vorhanden ist, bevor Sie versuchen, darauf zuzugreifen. In diesem speziellen Fall füge ich hier den None-Schlüssel hinzu und setze ihn auf einen negativen. Auf diese Weise ist jeder andere Wert mit einer Zählung größer als dieser. in der allerersten Iteration Ersetzen Sie in der allerersten Iteration den größten Wert durch den aktuellen Wert. Das war's für diese Funktion. Versuchen wir nun, die Tests auszuführen und sicherzustellen, dass die häufigsten Tests nicht mehr als fehlgeschlagener Test angezeigt werden. Klicken Sie ganz oben auf die grüne Schaltfläche „Ausführen“ . Da hast du es. Sie können jetzt sehen, dass am häufigsten kein fehlgeschlagener Test mehr auftritt. Hier wollen wir leere Eingaben betrachten. Es gibt hier einen Fall, in dem möglicherweise etwas Seltsames vor sich geht, wenn Sie eine leere Liste in die häufigste Liste übergeben würden, dann würden Sie einfach keine zurückbekommen, was ein vernünftiger Standard ist. Sie sollten jedoch nur sicherstellen , dass Ihre Funktion nicht unterbrochen wird , wenn Sie leere Eingaben erhalten. In diesem Fall wird unsere Funktion nicht unterbrochen. Es gibt keine zurück. Solange wir also deklarieren , dass die Funktion bei leerer Eingabe keine zurückgibt, ist das vollkommen gültig. Für unsere nächste Frage. Dieser ist konzeptionell ziemlich herausfordernd. Wir werden eine Datenstruktur oder eine beliebige Datenstruktur verwenden , um eine Reihe von Reisen zu sortieren. Eine Reihe von Schritten ist als Quelle und Ziel formatiert. Sie können sich diese als Quell- und Zielstädte vorstellen. Sobald wir das haben, wollen wir den vollständigen Pfad berechnen. Wir wollen die reale Startposition und die reale oder endgültige Endposition finden . Sie können vorerst davon ausgehen, dass es nur einen Pfad gibt und dass es einen vollständigen Pfad gibt. Das bedeutet, dass es keine Lücken gibt. Ende niemals an einer zufälligen Position in der Mitte mit einer Reihe von Schritten, die nichts miteinander zu tun haben, und es gibt keine Zyklen. Du wirst niemals von eins auf zwei zurück zu eins gehen. Wenn Sie von eins auf zwei gehen, werden Sie immer mit drei, vier usw. fortfahren . Ihr Ziel ist es, die Reihenfolge der Schritte vom ersten bis zum letzten zu drucken . Hier haben wir ein paar Schritte. Wir gingen von drei auf zwei, eins auf drei und zwei auf fünf. Ihr Ziel ist es herauszufinden, wie die richtige Abfolge von Schritten ist. Hier ist die richtige Reihenfolge eins bis drei, dann drei bis zwei, dann zwei bis fünf. Halten Sie das Video hier an, sehen Sie, welche Datenstrukturen Sie verwenden möchten und wie Sie sie verwenden würden. Hier ist die Lösung. Konzeptionell werden wir zuerst herausfinden, was die ultimative Ausgangsposition ist. Um das zu tun, werden wir eine Reihe von Hashmaps erstellen. Diese Hashmaps werden vom Ziel zur Quelle zugeordnet. Dann starten wir von jedem beliebigen Ziel aus. Von diesem Ziel aus überprüfen wir, ist die Quelle in der HashMap? Ist die aktuelle Quelle ein weiteres Steps-Ziel? Wenn ja, dann gehen wir zu diesem Schritt Ziel und Quelle, und Sie machen das weiter. Nehmen wir zum Beispiel an, wir beginnen bei zwei und sagen dann, ist drei in unserem Mapping? Es ist, drei sind in unserer Kartierung. Schauen wir uns die entsprechende Quelle an. Erstens, ist einer in unserer Kartierung? Nein, es steht nicht in unserer Kartierung. Das bedeutet also, dass man die ultimative Ausgangsposition ist . Das werden wir tun. Wir erstellen ein Mapping vom Ziel zur Quelle.. Dann werden wir es weiter durchqueren, bis wir zur ultimativen Quelle kommen. Sobald Sie dort angekommen sind, ist das der erste Schritt. Wir haben die ultimative Quelle. Wir müssen diese Reihe von Schritten jetzt tatsächlich ausdrucken. Wir müssen rückwärts gehen, wir müssen von der Quelle ausgehen und weiter durchqueren. Wir fangen bei eins an, wir gehen zu drei, dann schauen wir nach drei. Wir sehen drei, dann gehen wir zu zwei. Wir schauen nach zwei, zwei sind da. Dann machen wir das weiter. Sie bewegen sich weiter in Vorwärtsrichtung. Sie benötigen eine Reihe von Hashmaps, die Ihnen die umgekehrte Richtung geben. Dann müssen Sie HashMap einrichten, die Ihnen die Vorwärtsrichtung gibt. machen wir. Ich werde zwei Hashmaps erstellen. Eine HashMap verlinkt immer vom Ziel zur Quelle. Man verlinkt immer von Quelle zu Ziel, das ist also unser Algorithmus. Was ist nun die Laufzeit und Speicherkomplexität? Pausiere das Video hier. Hier ist die Antwort. Unsere Speicherkomplexität ist linear in der Anzahl der Schritte, da wir sie für jeden einzelnen Schritt zu diesen beiden Hashmaps oder beiden Wörterbüchern hinzufügen . Nun zu unserer Laufzeitkomplexität, dasselbe. Die Anzahl der Schritte ist linear, da wir mindestens einmal auf jeden einzelnen dieser Schritte zugreifen müssen, und zum Glück für uns nur einmal. wir das wissen, schreiben wir jetzt die Funktion, den Code, auf. Pausieren Sie das Video hier und probieren Sie den Code aus. Lassen Sie uns nun die Lösung behandeln. Hier werden wir zwei Hashmaps oder zwei Wörterbücher initialisieren . Einer wird vorwärts sein, einer wird rückwärts sein. Für jedes einzelne Paar von Quelle und Ziel in unseren Schritten werden wir beide füllen. Das Forward-Mapping wird von der Quelle zum Ziel gehen. Die Rückwärtszuordnung erfolgt vom Ziel zur Quelle. Nachdem wir diese beiden Mappings aufgefüllt haben, gehen wir von jeder beliebigen Quelle zurück zur ultimativen Quelle. Die Quelle ist zwar rückwärts, und das ist wohl ein bisschen unklar, aber hier werde ich es nur klarstellen. Hier haben wir, dass source gleich dem ersten Schritt ist, und dann wird es die Quelle des ersten Schritts sein. Während die Quelle rückwärts ist, werden wir weiter durchqueren. Sobald diese While-Loop abgeschlossen ist, befindet sich Source nicht mehr im Backward Mapping, das bedeutet, dass Source die ultimative Quelle ist, der erste Ort, an den wir jemals gegangen sind. Solange sich source dann im Forward Dictionary oder im Forward Mapping befindet, drucken wir sie aus. Hier werden wir f-Strings in Python verwenden. Sie können dies ausdrucken, wie Sie möchten und dann gehen wir diesen Weg. Solange sich unsere Quelle im Forward-Mapping befindet, greifen wir im Forward-Mapping für sein Ziel auf dieses Element zu. Das ist so ziemlich alles. Lassen Sie uns nun diese Funktion ausführen und sicherstellen, dass wir diese Funktion übergeben, um den Pfad aus Tests zu erhalten. Los geht's, wir haben nur einen Satz fehlgeschlagener Tests, die sich in einer anderen Funktion befinden, also haben wir diese Übung erfolgreich bestanden. Lassen Sie uns nicht über diese Herausforderungsfrage sprechen. Diese Frage ist auch ziemlich schwierig, also werden wir nur algorithmisch darüber sprechen, wir werden sie nicht wirklich codieren. Auch hier habe ich Lösungen für Sie geschrieben, aber wir werden hier einfach nicht über den Code sprechen. Ich habe jede einzelne Zeile in den Lösungen kommentiert , damit Sie sie durchgehen und verstehen können sie durchgehen und verstehen Der wichtigste Teil hier ist jedoch der Algorithmus. Für dieses Problem werden wir ein Wörterbuch mit einer maximalen Größe erstellen , das als am wenigsten verwendetes Bargeld fungiert . In diesem Wörterbuch löschen Sie jedes Mal, wenn Sie einen Schlüssel einfügen , aktualisieren oder darauf zugreifen, der als Verwendung dieses Schlüssels gilt, und wenn das Wörterbuch mehr Schlüssel als die maximale Größe hat , werden Sie den zuletzt zuletzt verwendeten löschen verwendeter Schlüssel. Sehen wir uns ein Beispiel dafür an. Nehmen wir an, ich habe dieses neue Wörterbuch und füge den Wert 1 mit dem Schlüssel a ein, also schauen wir uns hier nur die Schlüssel an, die Werte spielen keine große Rolle. Wir haben einen Wert für Schlüssel a eingefügt und dann fügen wir einen Wert für Schlüssel b ein. An dieser Stelle ist b der zuletzt verwendete Wert und 1 ist der am wenigsten verwendete Wert. Allerdings greife ich hier auf a. Jetzt wird a der zuletzt verwendete Wert , hier haben wir ihn getauscht. Einer entspricht a, also ist a der zuletzt verwendete und der andere Wert wird am wenigsten verwendet. Jetzt weisen wir dem Schlüssel c einen neuen Wert zu und Sie werden feststellen, dass b zu diesem Zeitpunkt hier der am wenigsten verwendete Wert war, also wird b gelöscht und jetzt haben wir nur noch a und c übrig. In diesem speziellen Wörterbuch betrug die maximale Größe zwei. So haben wir tatsächlich gesehen, wie einer der Schlüssel fallen gelassen wurde. Denken Sie daran, dass jedes Mal, wenn Sie auf einen Wert für einen Schlüssel zugreifen, ihn aktualisieren oder einfügen , der als Zugriff auf diesen Wert gilt oder diesen Wert verwendet, und jedes Mal, wenn Sie einfügen, wenn Sie die maximale Größe überschreiten, Sie in letzter Zeit am wenigsten verlieren verwendeter Wert. all dies wissen, denken wir nun darüber nach, wie wir das algorithmisch gestalten können. Pausieren Sie das Video hier und prüfen Sie, ob Sie einen Algorithmus entwickeln können. Hier ist die Lösung. Um diesen Cache tatsächlich zu implementieren, werden wir tatsächlich eine doppelt verknüpfte Liste führen . Bevor wir über eine verknüpfte Liste sprechen, behält eine verknüpfte Liste einen Link zum nächsten Link bei, sodass Sie ungefähr so aussehen würden. Sie hätten eine, die mit zwei verknüpft ist, Links zu drei. Eine doppelt verknüpfte Liste enthält jedoch tatsächlich beide Richtungen, drei wissen, dass ihr vorheriger Wert zwei ist, zwei wissen, dass ihr vorheriger Wert eins ist. Der Grund, warum Sie diese doppelt verknüpfte Liste wünschen, liegt darin , dass wir möchten, dass die verknüpfte Liste die Reihenfolge zwischen all unseren Daten verfolgt , und diese Bestellung zeigt uns, dass die zuletzt verwendete und die am wenigsten verwendeten Werte sind. Glücklicherweise ist es mit einer verknüpften Liste sehr einfach, einen Wert einzufügen und jeweils einen Wert zu entfernen. Beides sind konstante Zeitoperationen. Beachten Sie, dass dies für ein Array nicht zutrifft. Wenn Sie in einem Array umziehen möchten, sagen wir drei. Nehmen wir an, wir hatten das. Nehmen wir an, wir hatten 1, 2, 3, 4, 5 und nehmen wir an, dass fünf jetzt der zuletzt verwendete Wert ist. Ihre neue Liste müsste 5, 1, 2, 3, 4 sein. Bei einer doppelt verknüpften Liste ist dies ein konstanter Zeitvorgang. Alles, was Sie tun, ist die Verbindungen neu zuzuweisen , wie wir zuvor besprochen haben. Für ein Array müssten Sie jedoch die Position von 1-2 kopieren, 2-3, 3-4, 4-5, und dann fünf an den Anfang kopieren. Sie müssten n Kopien, n Operationen machen , um diese Liste neu zu mischen. Bei einer doppelt verknüpften Liste müssen Sie jedoch nichts davon tun. Es ist eine konstante Zeitoperation. diesem Grund möchten wir, dass eine doppelt verknüpfte Liste mit unserem Mapping kombiniert wird, oder eine HashMap, um diesen am wenigsten verwendeten Cache zu implementieren. wir wissen, dass wir eine doppelt verknüpfte Liste wollen, wie werden wir sie tatsächlich verwenden? Lassen Sie uns über die beiden Funktionen sprechen, die wir tatsächlich benötigen. Wir haben zwei verschiedene Funktionen. Ich werde diese Funktionen nicht vollständig konkretisieren , aber ich werde hier etwas Pseudocode hinzufügen, nur damit Sie wissen, wie die allgemeine Struktur des Codes aussehen würde. Hier hätten wir die Möglichkeit, einen Gegenstand zu bekommen , und wir hätten auch eine andere Funktion hier auch eine andere Funktion, die uns die Möglichkeit geben würde, einen Gegenstand festzulegen. Die Grundidee hier ist, dass wir unter diesen beiden Funktionen den Schlüssel aktualisieren, wir würden etwas sagen wie den neuesten Schlüssel erstellen und dann dasselbe hier. Wir werden auch den neuesten Schlüssel erstellen, und das ist so ziemlich alles für die High-Level-Logik. Das meiste Wesentliche wäre hier passiert. In der Funktion make last last last hier würden Sie tatsächlich die gesamte Neuzuweisung vornehmen, die erforderlich ist, um sowohl ein Element aus der verknüpften Liste zu entfernen als auch es dann ganz am Anfang wieder einzufügen ist es. Dies ist die konzeptionelle Lösung für dieses Problem. Sie würden eine doppelt verknüpfte Liste und auch eine Map verwenden. Das scheint ziemlich komplex zu sein, ich werde nicht codieren, zumindest nicht hier in der Lektion. Ich habe die Lösungen bereits geschrieben und die Lösungen werden Ihnen mit vollständig kommentiertem Code zur Verfügung stehen . Der wichtigste Teil dieser Frage war jedoch dieser Frage war die Verwendung der doppelt verknüpften Liste. wird es einige Fragen wie diese geben, bei denen Sie sich eine Ihren Interviews wird es einige Fragen wie diese geben, bei denen Sie sich eine neuartige Kombination verschiedener Datenstrukturen einfallen lassen neuartige Kombination verschiedener Datenstrukturen einfallen verschiedener Datenstrukturen um Ihre Ziele zu erreichen. In diesem speziellen Fall wollten wir einen Cache, der am wenigsten verwendet wurde, und wir möchten, dass er sehr effizient Verwendung dieser doppelt verknüpften Liste ermöglicht es uns, diese Funktion effizient zu halten. Das bringt uns zu unserem zweiten Teil der Frage. Wie hoch ist die Laufzeit und Speicherkomplexität unseres Algorithmus? Insbesondere, wie hoch ist die Laufzeit Ihrer Speicherkomplexität beim Einfügen und anschließenden Zugriff auf einen Wert? Pausiere das Video hier, und hier ist die Lösung. Den Wert zu bekommen ist ziemlich einfach. Den Wert selbst zu bekommen, nur auf einen Wert in einer HashMap zuzugreifen , ist alles eins, es ist konstante Zeit. Die eigentliche Frage ist jedoch, wie lange dauert es, den neuesten Wert zu aktualisieren? Denn das beinhaltet das Entfernen aus und das erneute Einfügen in eine doppelt verknüpfte Liste. Nun, glücklicherweise ist das Einfügen und Löschen aus einer verknüpften Liste eine konstante Zeit. Angesichts dessen wissen wir, dass dieser Algorithmus, diese Datenstruktur eine konstante Zugriffszeit ist . Das ist großartig. Wir haben die Effizienz einer HashMap beibehalten und was ist nun mit der Zuweisung? Was aktualisiert diese HashMap? Nun, zum Glück ist das auch immer noch konstante Zeit. Es ist konstante Zeit, eine HashMap selbst und erneut zu aktualisieren, um dieses Schlüssel- und Wertepaar zum neuesten zu machen. Diese Operation selbst ist wieder konstante Zeit, genau wie wir bereits erwähnt haben. Aufgrund dieser konstanten Zeitoperation bedeutet das Erstellen von etwas Neuem nur das Einfügen und Entfernen aus einer doppelt verknüpften Liste. Um dies zu sagen, haben wir uns eine schöne Kombination von Datenstrukturen ausgedacht eine schöne Kombination von , um Zeit, Einfügen und Zugriff für eine Datenstruktur konstant zu halten . Das ist die effizienteste, die Sie bekommen können. Ich denke, die Erkenntnis hier ist, dass die Kenntnis der richtigen Datenstrukturen wirklich einen Unterschied in der Größenordnung bedeuten kann , einen Unterschied in der Größenordnung zwischen einer effizienten Implementierung. und ineffizient. In diesem Fall hat uns die Verwendung einer doppelt verknüpften Liste eine Effizienz verschafft, und dies ist eine nützliche Fähigkeit für Interviews, vielleicht weniger für die Arbeit, aber wenn Sie ein riesiges Produktionssystem hatten, wenn Sie ein systemkritische Anwendung , die ineffiziente Datenstrukturen verwendete, dann hätten Sie die Möglichkeit, massive geschäftliche Auswirkungen zu erzielen. Das war's für diese Übung. Um auf all diese groben Folien zu allen Lösungen zugreifen zu können, sollten Sie auf die Kurswebsite zugreifen. Damit ist die Übungsstunde HashMap-Slash-Mappings abgeschlossen. 11. Bäume: Breadth vs. Tiefe: In dieser Lektion besprechen wir eine Möglichkeit, Daten hierarchisch zu speichern. Eine Datenstruktur, die als Baum bezeichnet wird. Wir erklären, wie ein Baum funktioniert, wie man einen Baum durchquert, wie man einen Baum organisiert, was O (long) time bedeutet. Abschließend werden wir die Vor- und Nachteile dieser neuen Datenstruktur diskutieren . Fangen wir damit an, was ein Baum ist. Ein Baum besteht aus einem Wurzelknoten. Dieser Stammknoten hat zwei untergeordnete Knoten. Jeder dieser Knoten hat dann jeweils zwei weitere untergeordnete Knoten. Diese Struktur nennen wir einen Baum. Da jeder Knoten zwei Kinder hat, nennen wir ihn einen Binärbaum. Angenommen, Sie möchten nach einem Wert suchen oder wir möchten diesen Baum ändern, wir müssen wissen, wie man einen Baum durchquert. Hier sind zwei verschiedene Möglichkeiten, dies zu erreichen. Die erste Methode heißt Breadth First Traversal, kurz BFS. In BFS durchqueren wir die Knoten Ebene von links nach rechts. Zuerst greifen wir auf drei zu. Wir haben das erste Level abgeschlossen, also lasst uns zum nächsten Level übergehen. Dann greifen wir auf 7 zu, dann auf 2, wir haben das zweite Level beendet. Gehen wir also zum letzten Level über. Wir greifen auf Null, Eins, Neun und Acht zu. Wir haben das letzte Level beendet, also sind wir fertig mit BFS. Unsere zweite Art, diesen Baum zu durchqueren heißt Depth-First Traversal, kurz DFS. Hier greifen wir vom Root-Knoten aus zu, drei, wir greifen auch auf sieben zu. Wir gehen weiter tiefer, also greifen wir auf zwei zu. Jetzt, wo wir in eine Sackgasse geraten sind, gehen wir zurück zu sieben und erforschen so tief wie möglich. Also greifen wir auf einen zu. Wieder sind wir in einer Sackgasse. Also gehen wir zurück zu sieben, gehen zurück zu drei und erforschen erneut so tief wie möglich. Wir greifen auf zwei dann auf neun zu. Wir sind in einer Sackgasse. Gehen Sie also zurück zu zwei und greifen Sie schließlich auf acht zu. Und das sind die beiden Möglichkeiten, einen Baum zu durchqueren, Breite zuerst oder die Tiefe zuerst. Wir erklären nun eine Möglichkeit, Daten in einem Baum zu organisieren. Dies wird als binärer Suchbaum bezeichnet. Beachten Sie, dass wir die Werte neu angeordnet haben. Insbesondere haben wir sie so angeordnet, dass das linke Kind immer kleiner ist als das Elternteil. Zum Beispiel ist drei hier weniger als fünf und zwei ist weniger als drei. Wir haben diese Werte auch so angeordnet, dass das richtige Kind immer größer ist als das übergeordnete Element. Zum Beispiel ist acht größer als fünf. Das rechte Kind ist also immer größer und das linke Kind ist immer weniger. Diese geordnete Struktur ermöglicht es uns, Daten sehr effizient zu verwalten. Nehmen wir an, wir möchten Daten in den Baum einfügen. Hier wollen wir sechs einfügen. Beginnen Sie dazu mit dem Stammknoten fünf. Von hier aus suchen wir iterativ nach einem Zuhause für sechs Personen. Da sechs größer als fünf ist, wissen wir, dass sechs zur Rechten gehören müssen. Jetzt haben wir den Wert Acht. Da sechs weniger als acht sind, wissen wir, dass sechs zur Linken gehören müssen. Es gibt hier keinen Knoten, also ist das jetzt Six's Zuhause. Damit ist der Einfüge-Algorithmus abgeschlossen. Nehmen wir an, die Tiefe des Baums ist d, dann nimmt dieser Algorithmus bis zu d Operationen auf. Infolgedessen benötigt das Einfügen O von d Zeit, um ausgeführt zu werden. Zusammenfassend dauert das Einfügen O (d) -Zeit. Sehen wir uns nun an, wie das Löschen funktioniert. Angenommen, wir löschen sechs rot angezeigte. Nun, das ist ziemlich einfach. Löschen Sie einfach diesen Knoten und den Zeiger von seinem übergeordneten Knoten. Nehmen wir jedoch an, wir haben aus der Mitte des Baumes gelöscht. Insbesondere wollen wir fünf streichen. Lass uns versuchen, was wir letztes Mal gemacht haben, lass uns fünf fallen. Jetzt gibt es jedoch ein Loch im Baum. Wir können jedes Kind benutzen, um die Lücke zu füllen , drei oder acht. Hier verwenden wir das richtige Kind acht. Also schieb acht nach oben. Jetzt gibt es jedoch eine Lücke , in der früher acht waren. Um konsistent zu sein, verwenden wir das rechte Kind von Acht, neun. Schieben Sie erneut neun nach oben. Jetzt gibt es ein Ganzes, in dem früher neun waren, aber das ist okay. Es gibt keine Kinder mehr. Wir können also einfach den zusätzlichen Zeiger löschen. Genau wie beim vorherigen Algorithmus. Dieser Algorithmus nimmt bis zu d Operationen auf. Das Löschen nimmt also O. d Zeit in Anspruch. Um das Einfügen und Löschen für einen binären Suchbaum zusammenzufassen , benötigen beide O of d-Zeit. Unser Ziel ist es, nach dem Wert sechs zu suchen. Wir beginnen mit dem Wurzelknoten fünf, wie beim Einfügen vergleichen wir unseren Sollwert sechs mit dem aktuellen Knoten fünf. Sechs ist größer als fünf, also gehen wir nach rechts. Jetzt greifen wir auf acht zu. Wir vergleichen, sechs ist weniger als acht, also gehen wir nach links. Jetzt greifen wir auf sechs zu, sechs ist der Wert, den wir suchen. Also sind wir mit der Suche fertig. Dieser Algorithmus kann bis zu d Operationen aufnehmen. Die Suche ist also O von d. Zusammenfassend weist ein binärer Suchbaum eine O of d-Änderung und einen Zugriff auf. Beachten Sie, dass es in einem Baum keinen direkten Abruf des achten Knotens gibt, da es keine globale Reihenfolge der Knoten gibt und Sie nicht wissen, wo sich die Knoten im Speicher befinden. Daher gibt es keine Fetch-Laufzeitanalyse. Damit ist unsere Analyse von Bäumen abgeschlossen. Wir haben jedoch noch einen zu tun. Wir möchten diese Laufzeiten übersetzen. Alle unsere Laufzeiten werden als Funktion der Baumtiefe ausgedrückt oder d. Visualisiert, hier ist ein Baum und hier ist die Tiefe des Baumes. In diesem Fall haben wir eine Tiefe von vier. Wir möchten diese Laufzeiten in Form von n, der Anzahl der Knoten, ausdrücken , in diesem Fall gibt es 15 Knoten. Dies liegt daran, dass die Laufzeiten für alle unsere vorherigen Datenstrukturen in n, der Anzahl der Elemente, ausgedrückt wurden . Daher sollten wir unsere neuen Laufzeiten auch in n ausdrücken , um sicherzustellen, dass diese Laufzeiten vergleichbar sind. Hier ist derselbe Baum. Versuchen wir, die Beziehung zwischen d und n zu verstehen . Betrachten Sie die erste Schicht. Dies ist Depth 1 mit einem Knoten. Betrachten Sie die ersten beiden Schichten. Dies ist Depth 2 mit drei Knoten. Die ersten drei Schichten, das ist Depth 3 mit sieben Knoten. Betrachten Sie alle Ebenen. Dies ist Depth 4 mit 15 Knoten. Es kann schwierig sein, ein Muster zu erkennen. Anstatt also die Anzahl der Knoten zu zählen, zähle ich die Anzahl der Knoten plus eins. Wenn Sie sich die Zahlen in Rot ansehen , sehen Sie ein Muster? Wie Sie vielleicht bemerkt haben, verdoppelt sich die Anzahl der Rottöne und die Anzahl der Knoten ungefähr. Als Ergebnis können wir sagen, dass n ungefähr zwei Potenzen von d ist . Jetzt haben wir eine mathematische Beziehung zwischen d und n. Da wir d in unsere Laufzeitkomplexitäten einbinden wollen , lass uns nach d lösen. Um nach d zu lösen, schreiben wir zuerst die Gleichung wenden dann Logarithmen auf beide Seiten an. Denken Sie daran, dass wir mit Protokollen den Exponenten d als Koeffizienten außerhalb des Logs bewegen können . Dann ignorieren wir einfach die Konstante log zwei. Jetzt bekommen wir, dass log von n ungefähr d ist . Wir können jetzt einstecken. Zuvor hatten wir diese Laufzeiten in Form von d. Das Einstecken von d ist gleich logn. Wir erhalten jetzt O of log n für alle Änderungs- und Zugriffslaufzeiten. Lassen Sie uns nun anhand dieser Analyse die Vor- und Nachteile von binären Suchbäumen diskutieren . Binäre Suchbäume haben in einigen beeindruckende Laufzeiten, nur O (logn). In der Praxis liegt O of log n sehr nahe an o einer konstanten Zeit. Binäre Suchbäume sind von ideal für Zufallssequenzen. Je gleichmäßiger verteilt, desto besser. Binäre Suchbäume sind jedoch die schlechtesten für sequenzielle Daten, und hier ist der Grund dafür. Nehmen wir an, ich habe eine Folge von Zahlen von 0-10. Zuerst erstellen wir den Wurzelknoten 0, dann haben wir eins beantwortet, dann zwei, dann drei, dann vier, dann fünf. Die Liste geht weiter, und wie Sie sehen können, haben wir im Grunde eine gerade Linie anstelle eines gefüllten binären Suchbaums. Dies bedeutet, dass die Tiefe jetzt nicht mehr log n ist, sondern dass die Tiefe genau der Anzahl der Knoten entspricht. Das heißt, alle unsere Algorithmen benötigen jetzt O von n oder linearer Zeit. Zusammenfassend lässt sich sagen, dass binäre Suchbäume für sequenzielle Daten wirklich ineffizient sind. Zusammenfassend haben wir besprochen, was ein Baum ist, Breite zuerst versus Tiefe zuerst durchlaufen, was ein binärer Suchbaum ist, was das O der Log-n-Zeit bedeutet und einige Vor- und Nachteile von binären Suchbäumen. Eine Kopie dieser Folien und Ressourcen Sie auf der Kurswebsite. Lassen Sie uns nun diese Datenstrukturen in Aktion sehen. In der nächsten Lektion werden wir die Verwendung und Implementierung dieser Datenstrukturen üben Verwendung und Implementierung dieser Datenstrukturen unsere beiden Lernziele für diesen Kurs angehen. 12. Trees: Willkommen zur abschließenden Übungsstunde für diesen Kurs. In dieser Lektion werden wir mit Bäumen üben, insbesondere mit der Suche nach Breite und Tiefe zuerst. Lass uns weitermachen und hier loslegen. Navigiere wie zuvor zu alvinwan.com/datastructures101/trees. Unter diesem Link sehen Sie so etwas. Leiten Sie das Projekt weiter, um Ihre eigene Kopie zu erhalten, klicken Sie auf den Projektnamen, klicken Sie auf die Ellipse und dann auf Fork. Ich schlage vor, Ihr Skillshare- und Antwortfenster nebeneinander zu platzieren , damit Sie beim Codieren mitprogrammieren können. Sie sollten dann einen Bildschirm wie diesen sehen, nach unten scrollen und Sie gelangen zur ersten Übung hier, die bfs oder breadth-First-Suche genannt wird. Ein Tipp, bevor wir beginnen, ist, sich zu merken wie man die Breath-First - und Depth-First-Suche durchführt, hier abgekürzt als bfs und dfs, weil es immer dasselbe sein wird. In diesem speziellen Fall verwenden wir keine Technik, die Rekursion genannt wird. Also ohne Rekursion sieht der Weg, bfs und dfs zu machen, immer so aus. diesem Wissen versuchen wir nun, die Suche nach Breite an erster Stelle zu implementieren. So sieht eine Suche nach der Breite zuerst durch einen Baum aus. Hier haben wir einen Baum, 1, 2, 3, 4. Lassen Sie mich gehen und veranschaulichen, wie das aussieht. Hier hättest du eins, und dann hättest du hier ein Kind , das zwei wären, und dann hättest du ein weiteres Kind genau dort, das wären drei. Dann hast du auch einen Baum wie diesen. So sieht der Baum aus. Du hättest im Grunde eine der Wurzeln, es ist das linke Kind wird zwei sein, und dann werden das linke Kind von zwei drei sein. Dann ist dies das richtige Kind von einem. So sieht der Baum aus. Zu wissen, dass dieser Baum so aussieht, hier sieht die Suche in der Breite zuerst aus. Die erste Breite gibt uns zuerst eine und dann zwei und dann vier und dann drei. Es ist Traversieren und es wird auch Level Order Traversal genannt, also bewegen wir uns hier im Grunde genommen die Stufen auf einmal nach unten, 1, 2, 4, 3. Wenn wir hier unten zum Beispiel fünf gehabt hätten, dann hätten wir 1, 2, 4, 3, 5 und so weiter und so fort. So sieht das aus. Wissen, dass dies jetzt eine Durchquerung der Breite an erster Stelle ist, ist hier ein Hinweis. Pausieren Sie das Video jetzt und versuchen Sie es selbst, wenn Sie den Hinweis nicht möchten. Der Hinweis ist, dass Sie eine der Datenstrukturen verwenden müssen eine der Datenstrukturen verwenden , über die wir zuvor gesprochen haben. Insbesondere müssen Sie dazu einen Stack oder eine Warteschlange verwenden . Machen Sie weiter und pausieren Sie das Video hier und versuchen Sie, den Algorithmus für eine Durchquerung der Breite zuerst zu entwerfen . Jetzt ist hier die Lösung. Die Lösung wird die Verwendung einer Warteschlange beinhalten. Was wir tun werden, ist in dieser Warteschlange, wir beginnen mit dem Hinzufügen des Roots. Sobald wir die Wurzel hinzugefügt haben, nehmen wir die Wurzel und stellen alle untergeordneten Elemente für diesen Stamm in die Warteschlange ein. Sobald wir das getan haben, entfernen wir uns aus der Warteschlange. Dequeuing wird uns hier den allerersten Punkt geben. Dann stellen wir all seine Kinder in die Warteschlange. Das werden drei sein und was auch immer ist ein Kind von zwei Jahren. Tatsächlich besteht eine Möglichkeit, dies zu tun , darin , eine Visualisierung einzubeziehen. Hier haben wir einen, wir werden einen aus der Warteschlange entfernen und wir werden alle seine Kinder zwei und vier hinzufügen. Dann werden wir zwei aus der Warteschlange entfernen und dann die Kinder in die Warteschlange stellen, die nur drei sind. Dann sagen wir mal, vielleicht gibt es noch einen, sagen wir mal, es sind fünf. Hier hätten wir drei und fünf. Dann würden wir endlich unsere nehmen. Dann vier stellten wir alle seine Kinder in die Warteschlange, was nichts ist und so weiter. Die Idee ist, dass Sie feststellen werden, dass die Reihenfolge des Dequeuings 1, 2, 4 war. Danach werden es drei und fünf sein, was genau das ist, was bfs ist. Die Warteschlange gibt uns genau eine Baumdurchquerung der Breite an erster Stelle. das wissen, wollen wir nun sehen, wie die Laufzeit in Bezug auf die Speicherkomplexität ist Pausiere das Video hier. Hier ist die Lösung. Die Laufzeit und Speicherkomplexität werden beide o of n sein. Sie denken vielleicht, was ist n hier? Nun, n ist die Anzahl der Knoten. Das ist wichtig. Vorher hatten wir diesen Fall, in dem wir eine Variable selbst definiert haben. Wir definieren eine Variable als eine Anzahl von eindeutigen Werten, die eingegeben werden. In diesem Fall ist diese Variable n standardmäßig für einen Baum ist diese Variable n die Anzahl der Knoten im Baum. Sie könnten es auch neu definieren, Sie könnten das n als die Höhe des Baums neu definieren oder Sie können es als etwas anderes definieren , aber normalerweise ist n die Anzahl der Knoten im Baum. wissen, dass Sie, wenn Sie Ihre Laufzeitspeicherkomplexität für einen Baum melden, in Bezug auf die Anzahl der Knoten angeben sollten, was für uns o von n sein wird, weil Sie darüber gehen müssen Jeder einzelne Knoten, das ist ein Breath-First-Traversal und zweitens müssen Sie all diese Knoten zu Ihrer Warteschlange hinzufügen. Irgendwann, tut mir leid, dass ich ein bisschen gelogen habe, wird Ihre Warteschlange niemals die maximale Breite des Baumes überschreiten. Wir werden später sehen, was Breite bedeutet, aber wir werden vorerst nur sagen, dass o von n die Speicherkomplexität ist. Wir können später mit dieser Nuance spielen, ich erkläre warum, es gibt eine bessere Antwort. Halten Sie das Video vorerst an und versuchen Sie , es zu codieren. Schreiben wir die Lösung auf. Hier definieren wir eine Warteschlange und der erste Wert der Warteschlange wird tatsächlich die Wurzel sein. Während etwas in der Warteschlange ist, werden wir aus der Warteschlange entfernt. Dann werden wir es erweitern, also stellen wir uns tatsächlich in die Warteschlange. Für jeden Zweig in den Zweigen des Baumes wir uns in die Warteschlange, also stellen Sie den Zweig in die Warteschlange. Dann drucken wir endlich den aktuellen Wert. Dies wird uns eine Durchquerung der Breite an erster Stelle geben. Lassen Sie uns nun überprüfen, ob dies unsere Tests besteht. Klicken Sie auf die grüne Schaltfläche Ausführen ganz oben und Sie können jetzt sehen , dass bfs nicht mehr in unserer Liste der fehlgeschlagenen Funktionen enthalten ist. Sie haben diesen Test erfolgreich bestanden. Gehen wir zur nächsten Frage über. Bevor wir zur nächsten Frage übergehen, ist ein Tipp, dass Sie immer neu verwenden sollten, warten Sie. Einer der Tipps ist , dass Sie immer eine Warteschlange für die Breite zuerst verwenden sollten . Das haben Sie hier als Beispiel gesehen. Du hast gesehen, wie man es benutzt. Behalte das im Hinterkopf. So wird es so ziemlich immer sein, wie Sie bfs ohne Rekursion implementieren. Wir werden in einem zukünftigen Kurs über Rekursion sprechen. diesem Wissen implementieren wir jetzt die Tiefensuche. Die Tiefensuche sieht wie folgt aus. Nehmen wir an, wir hatten diesen Baum und dieser Baum hat so ziemlich dieselbe Struktur. Es ist eigentlich eine etwas andere Struktur. Lassen Sie mich das für Sie herausarbeiten. Hier haben wir die Wurzel 1. Das linke Kind wird 2 und das linke Kind von 2 wird 3 sein. Dann sind keine anderen Kinder hier. Das richtige Kind von 1 wird 4 Jahre alt, genau hier. Dann wird das linke Kind von 4 5 sein . Hier werden wir zuschlagen. Eine Sache zu beachten ist, dass ich immer wieder sage, dass linkes und rechtes Kind darin Baumprobleme normalerweise um Ihren Binärbaum herum aufgebaut sind , wo Sie nur ein linkes und ein rechtes Kind haben. So wie wir hier einen Baum implementiert haben, können wir unbegrenzt viele Zweige haben. Du bist nicht auf Links und Rechts beschränkt. Technisch gesehen ist 5 kein linkes Kind von 4, 5 ist der einzige Zweig von 4. Ich habe gerade aus Gewohnheit links und rechts gesagt, aber das ist nicht wirklich wichtig. Der Punkt ist, dass der Baum ungefähr so aussieht. Wir haben 1 an der Wurzel , die Kinder sind 2 und 4 und dann ist das einzige Kind von 2 3, das einzige Kind von 4 ist 5. Wenn Sie das wissen, durchqueren Sie zuerst die Tiefe oder gehen Sie zuerst einen dieser Pfade entlang. So wie wir es implementiert haben, wird 1 zuerst diesen Weg hier hinuntergehen 4 und dann gehen wir zu 5 hinunter, bevor wir den ganzen Weg wieder hochkommen und andere Wege erkunden. So wird die Tiefendurchquerung zuerst aussehen. Es wird bis zu einem Blatt erforscht. Wiederum ist ein Blatt ein Knoten im Baum, der keine Kinder, keine Zweige hat. Es wird zuerst den ganzen Weg nach unten erkunden und dann wieder hochkommen und anfangen , andere Wege zu erkunden. So sieht eine Tiefendurchquerung aus. Du siehst hier unten wird es 1, 4, 5 gehen , und dann geht es wieder hoch und erforscht 2 und dann 3. Das ist eine Tiefendurchquerung. Lassen Sie uns versuchen, einen Algorithmus zu entwickeln. Pausiere das Video hier. Hier ist die Lösung. Für die Durchquerung der Tiefe zuerst haben wir zuvor eine Warteschlange für die Durchquerung der Breite zuerst verwendet. Für die Tiefendurchquerung verwenden wir einen Stack. Der Stack wird auf sehr ähnliche Weise funktionieren. Wir werden weiterhin Gegenstände zum Stapel hinzufügen und wir werden immer wieder vom Stapel springen. So wird es aussehen. Wenn ich mit 1 anfange, gehen wir zu Pop 1 und dann fügen wir die Kinder 2 und 4 hinzu. Jetzt, wo wir 2 und 4 haben, werden wir den letzten Gegenstand veröffentlichen, der 4 ist. Dann fügen wir seine untergeordneten Elemente hinzu, das sind 5. Dann gehen wir zu Pop 5. Sie können sehen, wohin das führt. Bisher haben wir 1, 4, 5 durchgemacht. Sobald wir mit 5 fertig sind, gehen wir zu Pop 2. Dies gibt uns unsere erste Tiefendurchquerung mit einem Stapel. wissen, dass dies der Algorithmus ist, sprechen wir über die Speicher - und Laufzeitkomplexität. Wie hoch ist die Laufzeit der Speicherkomplexität? Pausiere das Video hier und hier ist die Antwort. Die Speicherkomplexität wird hier linear in der Anzahl der Knoten sein. Für die Speicherkomplexität werden wir die Speicherkomplexität verdauen. Für die Rechenkomplexität werden wir eine lineare Rechenkomplexität haben, da wir durch all diese Knoten iterieren müssen. Dieselbe Einschränkung, die ich zuvor für die Speicherkomplexität erwähnt habe , ist eigentlich nicht linear in der Anzahl der Knoten, aber wir werden später mehr darüber sprechen. Lassen Sie uns nun versuchen, diese Funktion zu codieren. Pausiere das Video hier und probiere es aus. Lass uns weitermachen und diese Funktion programmieren. Hier in unserer Tiefen-First-Durchquerung beginnen wir mit der Initialisierung eines Stacks. In diesem Stack wird sich unser Root-Node befinden. Dann werden wir es wiederholen. Solange wir etwas im Stapel haben, springen wir dann vom Stapel. Dann für jeden einzelnen Zweig unseres aktuellen Knotens. Für Zweige in aktuellen Top-Branchen schieben wir diesen Zweig dann auf unseren Stapel und drucken dann unseren aktuellen Wert. Das ist so ziemlich alles für unsere Tiefendurchquerung. Lass uns weitermachen und überprüfen, ob das funktioniert. Drücken Sie ganz oben auf die grüne Schaltfläche „Ausführen“. Nun, dfs ist nicht mehr in unserer Fehlerliste , daher haben wir die DFS-Tests erfolgreich bestanden. Der Tipp hier ist, dass Sie einen Stapel für die Tiefendurchquerung verwenden sollten . Gehen wir nun zur nächsten Frage über. für jeden einzelnen Knoten in der Struktur Fügen Sie für jeden einzelnen Knoten in der Struktur ein neues Attribut namens parent hinzu, das auf seinen übergeordneten Knoten verweist. Hier werden wir bfs oder dfs für die übergeordnete Zuweisung verwenden. Dieses Attribut parent zeigt auf das übergeordnete Element des Knotens in der Struktur. Lass uns weitermachen und den Baum noch einmal zeichnen. Nehmen wir an, wir haben diesen Baum genau hier. Wir haben hier 1, und das einzige Kind ist 2 und 2 hat zwei Kinder , 3 und 4. Es wird ungefähr so aussehen und es gibt keine anderen Zweige, nur diese Leute. Jetzt, wo du das hast, werden wir die Eltern tatsächlich bevölkern. Wir werden dies so implementieren, dass jeder einzelne Baum hier auf sein übergeordnetes Element zurückzeigt. 2 zeigt also auf 1, 3 zeigt auf 2, 4 zeigt auf 2. das wissen, lassen Sie uns darüber nachdenken und einen Algorithmus dafür entwerfen . Pausiere das Video hier. Lassen Sie uns über die Lösung sprechen. Für diese Frage spielt es eigentlich keine Rolle, ob Sie bfs oder dfs verwenden. In beiden Fällen können Sie dafür sorgen, dass dies funktioniert. Im Grunde wird der Algorithmus sein, wir werden einige Traversal durchführen und wenn Sie oben schauen, haben wir tatsächlich über alle Kinder oder alle Zweige für ihren aktuellen Status iteriert alle Kinder oder alle Knoten. Während Sie diese Iteration durchführen, aktualisieren Sie diesen Zweig so, dass aktualisieren Sie diesen Zweig auf den aktuellen Knoten verweist, der der übergeordnete Knoten ist. Es spielt keine Rolle , welche Traversal Sie verwenden. Das ist der Algorithmus und in der Tat ist das so ziemlich die Codelösung. Überlegen Sie sich jetzt, was ist die Speicher- und Laufzeitkomplexität? Pausiere das Video hier. Genau wie zuvor, da wir DFS und BFS effektiv verwenden, die Laufzeit und die Rechenkomplexität dieselbe wie zuvor. Rechenkomplexität ist O von N und Speicherkomplexität, sagen wir vorerst, ist im Grunde O von N. Wenn wir das wissen, wollen wir jetzt weitermachen und den Code ausprobieren. Pausiere das Video hier und probiere es zuerst aus. Lassen Sie uns nun die Lösung durchgehen. Ich werde ein bisschen schummeln. Ich werde eigentlich nur von der vorherigen Funktion kopieren und einfügen, die bereits DFS ausgeführt hat. Lass uns weitermachen und das unten einfügen. Ich werde diese Druckanweisung entfernen und dann werde ich branch.parent gleich current zuweisen. Das war's. Lassen Sie uns überprüfen, ob diese Funktion korrekt ist. Wir drücken ganz oben auf den grünen „Run“ -Button . Da haben wir's. Wir können jetzt sehen, dass bevölkerte Eltern nicht mehr in der Liste der fehlgeschlagenen Tests stehen. Wir haben alle diese Tests erfolgreich bestanden. Wie ich bereits sagte, BFS, DFS, solange Sie sich diese Implementierung merken, werden Sie das sehr oft sehen. Zumindest ohne Rekursion wird es so aussehen, also stellen Sie sicher, dass Sie diese Implementierung kennen . Tipp von früher, berücksichtige immer auch leere Eingaben. In diesem speziellen Fall, wenn unser Baum leer wäre, würde unsere Funktion fehlschlagen , denn hier werden wir platzen , wir werden aktuell, aktuell wird keiner sein und dann gehen wir um zu versuchen, auf.branches davon zuzugreifen. Auch hier sollten Sie bei all Ihren Interviews und bei all Ihren Fragen überlegen, was Sie mit leeren Eingaben tun würden. In diesem speziellen Fall hätten wir sagen sollen, wenn Baum keiner ist, dann tun wir einfach nichts, kehren einfach zurück. Das ist wichtig im Hinterkopf zu behalten. Gehen wir zur nächsten Frage über. Hier verwenden wir BFS oder DFS, um den Maximalwert in einem extrem breiten, aber flachen Baum zu berechnen . Lassen Sie uns das Folgende in Betracht ziehen. Überlegen Sie, was dies für Ihre Wahl der Durchquerung bedeutet. Was ist die maximale Raumkomplexität der Breite-First-Suche oder der Tiefensuche? Geht schon weiter. Dies hängt tatsächlich mit der Nuance zusammen, über die wir zuvor gesprochen haben. Pausieren Sie das Video hier und überlegen Sie zuerst, bevor Sie den Algorithmus in Betracht ziehen können. Eigentlich, wie Sie den Algorithmus in Betracht ziehen. [LÄRM] Hier ist die nächste Frage. Wir werden den maximalen Wert von einem extrem breiten, aber flachen Baum erhalten. Der wichtige Teil dieser Frage besteht darin, zu überlegen, was ein extrem breiter, aber flacher Baum mit Ihrem Algorithmus macht. Warum ist das wichtig? Was bedeutet das für Ihre Wahl der Durchquerung? Wir haben vorhin über eine subtile Nuance über die Raum- oder Gedächtniskomplexität Ihrer Art der Durchquerung gesprochen . Diese Frage geht wirklich darauf ein, um zu verstehen, was diese Nuance für Ihren Algorithmus bedeutet. Pausieren Sie das Video hier und sehen Sie, ob Sie das herausfinden können. Was ist der Unterschied zwischen extrem breiten, aber flachen Baum und einem tiefen Baum, aber einem sehr schmalen Baum für BFS oder DFS? Pausiere das Video hier. Hier ist die Antwort. Für einen extrem breiten, aber flachen Baum sollten Sie DFS verwenden. Der Grund dafür ist, dass BFS oder Breath-First-Traversal, Platzkomplexität oder die maximale Anzahl von Elementen in der Warteschlange oder dem Stapel oder einer anderen Sammlung, die Sie verwenden, die Breite der Baum. Während für die Tiefensuche oder DFS der maximale Speicherplatz, den wir verwenden, der Tiefe des Baums entspricht. Wenn ich einen extrem flachen Baum habe, sollten Sie, dass DFS Ihren Platzverbrauch minimiert. Denn wenn Sie einen sehr flachen Baum haben, müssen Sie eine sehr kurze Sammlung berücksichtigen. wir das wissen, entwerfen wir den Algorithmus so , dass er den Maximalwert erhält. Pausieren Sie das Video hier und versuchen Sie, den Algorithmus zu entwerfen. Hier ist die Lösung. Für den Algorithmus nehmen wir einfach den Maximalwert an , wenn Sie einen Knoten durchqueren. Jedes Mal, wenn Sie einen Knoten durchqueren, vergleichen Sie den Wert dieses Knotens mit einem global größten Wert. Wenn Ihr aktueller Wert größer ist, ersetzen Sie ihn einfach. Dies ist dem Beispiel für die maximale Frequenz sehr ähnlich Beispiel für die maximale Frequenz das wir zuvor gesprochen haben. In diesem Fall betrachten wir den Maximalwert. Nachdem wir uns den Algorithmus angesehen haben, haben wir uns die Art des Durchlaufens angesehen. Halten Sie das Video hier an und prüfen Sie, ob Sie die Speicher- und Laufzeitkomplexität ermitteln können . Hier ist die Antwort. Was die Laufzeitkomplexität betrifft, ist es wiederum linear in der Anzahl der Knoten, es ist O von N. Für die Speicherkomplexität haben wir bereits darüber gesprochen, weshalb wir DFS für dieses Problem ausgewählt haben. Ihre Raumkomplexität oder Speicherkomplexität wird die Tiefe des Baums sein. Das ist nicht gerade O von N. Es ist auch, zumindest vorerst, nicht klar, wie tief der Baum genau sein würde. Wir weisen ihr einfach eine neue Variable zu. Wir sagen, D ist die Tiefe des Baums, also ist unser Algorithmus o von d. Jetzt versuchen wir es zu codieren. Pausiere das Video hier. Jetzt, da wir eine DFS-Implementierung haben, werde ich wieder faul sein. Ich kopiere es einfach und füge es ein. Scrollen wir hier zurück und dann kopieren wir diese DFS-Implementierung, und dann scrollen wir wieder nach unten und fügen sie ein. Jetzt, da wir diese DFS-Implementierung haben, werden wir die Druckanweisung tatsächlich entfernen. Wie bereits erwähnt, werden wir für jeden einzelnen Knoten , den wir in Betracht ziehen, den Maximalwert aktualisieren. Nehmen wir an, der Höchstwert am Anfang ist nur der Roots-Wert. Wenn wir dann jeden einzelnen Knoten untersuchen, nehmen wir das Maximum zwischen dem aktuellen Wert und dem größten Wert. Schließlich geben wir den Maximalwert zurück. Versuchen wir, diese Funktion auszuführen, und stellen Sie sicher, dass sie alle Tests besteht. Fahren Sie fort und klicken Sie ganz oben auf die grüne Schaltfläche „Ausführen“ . Da haben wir's. Wir können jetzt sehen, dass get maximum nicht mehr in der Liste der fehlgeschlagenen Tests steht. Gehen wir nun zur nächsten Frage über. Wir werden Datenstrukturen kombinieren, um die Baumbreite zu berechnen. Mal sehen, wie groß die Baumbreite ist. Die Breite des Baums ist die maximale Anzahl von Knoten in einer bestimmten Tiefe oder einer bestimmten Ebene. Lass uns diesen Baum nochmal kritzeln. Hier haben wir eins und eines hat ein Kind, das sind nur zwei, und zwei haben zwei Kinder, das sind drei und vier. Hier haben wir drei, und dann haben wir vier. So sieht dieser Baum aus. Die Breite dieses Baums beträgt dann zwei , da diese Ebene zwei Elemente enthält. Wenn wir jetzt noch einen hier hätten, sagen wir, wir hätten fünf, und dann hätten wir noch einen, sechs, sagen wir, dann wäre die Breite dieses Baumes drei, weil Sie höchstens drei haben auf einer einzigen Ebene. das wissen, lasst uns weitermachen und aktualisieren. Lassen Sie uns den Algorithmus besprechen. Machen Sie weiter und halten Sie das Video hier an und sehen Sie, wie Sie die Breite dieses Baums berechnen würden . Hier ist eine Lösung. Zum Glück haben wir einen Traversalmodus, der es für uns viel einfacher macht , die Tiefe zu berechnen, die Level Order Traversal oder BFS sein wird. Es gibt zwei Möglichkeiten , dies zu tun. Zum einen können Sie eine andere Datenstruktur verwenden , um zu verfolgen wie viele Knoten sich in einer bestimmten Tiefe befinden. Das zweite ist das modifizierte BFS, sodass Sie jeweils ein Level durchqueren und im Grunde verfolgen , wann Sie das nächste Level beginnen . Das sind Ihre beiden Optionen. Das sind zwei verschiedene Algorithmen. Wir werden die erste implementieren, bei der wir eine andere Datenstruktur verwenden, wenn Sie ein Mapping verwenden. Nachdem Sie darüber gesprochen haben, sprechen wir über die Laufzeit und die Speicherkomplexität. Pausieren Sie das Video hier und sehen Sie, ob Sie es herausfinden können. Hier ist die Antwort. Aus Gründen der Laufzeitkomplexität werden beide Algorithmen, unabhängig davon, welchen Sie ausgewählt haben, unabhängig davon, welchen Sie ausgewählt haben, O von N sein, wobei n die Anzahl der Knoten ist. Beide Berechnungskomplexitäten sind linear in der Anzahl der Knoten. Wenn Sie sich nun dafür entscheiden, mehrere Datenstrukturen zu verfolgen, bei denen Sie ein Mapping von der Tiefe bis zur Anzahl beibehalten , wird dies eine zusätzliche Raumkomplexität von O of D in der Tiefe sein . Sie werden linear in der Tiefe sein, weil Sie für jede einzelne Tiefe einen Wert speichern. Wenn Sie jedoch den Algorithmus verwenden, bei dem Sie BFS an Ort und Stelle ändern, wäre Ihr Algorithmus O der Breite. Beide Algorithmen haben mindestens O Breite, denn die Grundlinie ist genau so, wie das ursprüngliche BFS funktioniert. Der Algorithmus, der zusätzlich eine HashMap verwendet, um dieses Mapping von Tiefe zu Zählung zu speichern, wird jedoch zusätzlich eine HashMap verwendet, um dieses Mapping von Tiefe zu Zählung zu speichern , wird O der Breite plus O der Tiefe sein. Wir werden die weniger effiziente implementieren, was rückwärts erscheinen würde, aber ich habe die effiziente bereits in der Lösung implementiert , sodass Sie das überprüfen können, wenn Sie möchten die effizientere Umsetzung. Aber im Moment werde ich die weniger effiziente implementieren. Machen Sie weiter und pausieren Sie das Video hier und prüfen Sie, ob Sie den Code selbst erstellen können. Hier ist unsere Lösung. Lass uns weitermachen und schreiben. Wir werden hier unsere bevorzugte Datenstruktur verwenden. Wir verwenden ein Standardwörterbuch. Wir beginnen mit der Initialisierung einer Warteschlange. Jedes einzelne Element in dieser Warteschlange wird zusätzlich zum Knoten selbst eine Tiefe des aktuellen Knotens sein Knoten selbst eine Tiefe des aktuellen Knotens , da wir die Tiefe verfolgen müssen, um zu wissen, welche Anzahl in unserem Zähler ist. von Breiten, die tatsächlich aktualisiert werden sollen. Hier ist unser Zähler, Breiten, und er wird alle Breiten auf Null initialisieren. Während wir etwas in der Warteschlange haben, werden wir die Warteschlange entfernen und dann das Widths-Wörterbuch aktualisieren, indem wir diesen Wert um eins erhöhen. Schließlich werden wir für jeden Zweig die um eins inkrementierte Tiefe und den Knoten selbst in die Warteschlange stellen . Jedes Mal, wenn Sie vom Elternteil zum Kind wechseln, erhöhen wir die Tiefe um eins. Schließlich geben wir die maximale Breite zurück, die wir sehen. Dies gibt uns die maximale Breite und alle Breiten , die wir hochgezählt haben. Lassen Sie uns das jetzt ausführen und sicherstellen, dass alle unsere Tests bestanden wurden. Da haben wir's. Mangelnde Ausgabe bedeutet, dass alle unsere Doc-Tests bestanden haben. Du hast endlich alle Übungen für diese Lektion abgeschlossen . Für all diese Folien, Komplettlösungen und weitere Übungsübungen besuchen Sie unbedingt diese Website. Das ist es für unsere Praxis für Bäume, Breite versus Tiefe versus Durchquerung. Sie haben hier eine Menge Probleme gesehen. Sie haben auch in früheren Übungsstunden eine Reihe von Problemen gesehen . Ich hoffe, dass diese sehr nützlich waren. Gehen wir nun zu unserer allerletzten Lektion , in der wir das alles abschließen. 13. Schlussbemerkung: Herzlichen Glückwunsch zum Abschluss des Kurses. Wir haben eine Menge Themen behandelt, Wachstumsreihenfolgen, Stapel und Warteschlangen, verknüpfte Listen, Hashmaps und Bäume. Das war ein ziemlich schwieriger Kurs mit einer Menge Inhalt und einigen wirklich brutalen Fragen. Du hast 20 Übungen in der Tiefe abgeschlossen, 20 Interviewtipps und übst die dreistufige Methode, um immer wieder Rätsel zu lösen . Das war eine Menge Inhalt und die Zusammenfassungsfolien sind großartige Werkzeuge zum Auswendiglernen. Die wichtigste Erkenntnis ist jedoch der dreistufige Prozess. Interviews angeht, ist das der Schlüssel. Hier ist der dreistufige Prozess einmal: Entwerfen Sie Algorithmen ohne Code, meldet Laufzeit- und Speicherkomplexitäten und codieren Sie schließlich den Algorithmus. Um Ihr Verständnis für drei Tage nach dem Kurs wirklich zu festigen , entwerfen Sie jeden Tag eine Datenstrukturfrage. Ich ermutige Sie auch, Ihre Frage im Diskussionsbereich zu stellen. Sie brauchen nur etwas Schlaf zwischendurch, wenn Sie über Datenstrukturen nachdenken. Es muss nicht die beste Arbeit deines Lebens sein. Jede Frage wird beantwortet und im Diskussionsbereich veröffentlicht . Ich freue mich wirklich darauf, sie zu sehen und das war's. Fantastische Arbeit. Dies ist der Beginn Ihrer Interviewvorbereitung und Sie stehen auf einem starken Fundament. meinem Skillshare finden Sie weitere Kurse zu Data Science, maschinellem Lernen und anderen wichtigen Programmierkonzepten. Für mehr Interviewvorbereitung folgen Sie mir auf Skillshare, um weitere Updates zu erhalten, da wir häufiger verwendete Programmierrätsel und Interviews mit spezifischen Tricks behandeln häufiger verwendete Programmierrätsel werden. Nochmals herzlichen Glückwunsch, dass Sie es bis zum Ende des Kurses und bis zum nächsten Mal geschafft haben.