Algorithmen und Datenstrukturen
Ich beabsichtige, dieses Repository als Practice Playground (KATA) sowie an einige gemeinsame, einfache, aber leistungsstarke Algorithmen zu erinnern. Wo elegant ich Clojure -Wandler verwenden, die großartige Elektrowerkzeuge sind, um Sequenzen zu verarbeiten. Obwohl dieses Dokument ausführlich erscheinen mag, beabsichtige ich, es als Liste zu verwenden, zu der ich jederzeit zurückkommen kann, wenn ich studieren muss. Ich habe hier nicht alles implementiert.
Schreibstil
Code hier ist nicht in dem Stil geformt, den ich für die professionelle Codierung verwenden würde. Jedes Team hat einige Kultur und Meinungen über den Code -Stil und es ist besser, sich an diese gemeinsamen Richtlinien zu halten. Darüber hinaus wird der Code in erster Linie geschrieben, um von anderen Personen gelesen zu werden, oder alle von uns würden in der Versammlung für maximale Leistung codieren, wenn wir nur auf eine maschinelle Leserschaft abzielen würden. Der Code, den ich als Teil eines Teams schreibe, soll von irgendjemand anderem in diesem Team geschrieben worden sein.
Der Code hier wird dank EMACs und Org-Mode in Last-Programmierung geschrieben. Dies bedeutet, dass der in Clojure geschriebene Code aus den Textdateien abgeleitet ist, in denen die Argumentation dahinter erfasst wird. Ich hoffe, es macht es einfacher zu lesen.
Python
Vorbereitungen für ein neues Problem
./dev-resources/new-problem.sh
--problem-path neetcode_practice_2024/arrays_and_hashing/problem_4_anagram_groups
Siehe --help .
Wenn das Initialisierungsskript abgeschlossen ist, wird am Ende ein vorgeschlagener Befehl für Tests angezeigt:
poetry run ptw -- --
src/neetcode_practice_2024/arrays_and_hashing/problem_4_anagram_groups.py
tests/neetcode_practice_2024/arrays_and_hashing/problem_4_anagram_groups_test.py
Mit Poesie und Pytest interagieren
Zum Beispiel, um Tests während der Entwicklung zu sehen:
poetry run ptw
poetry run ptw -- -- --memray
poetry run ptw -- -- --benchmark-only
poetry run ptw -- -- --benchmark-skip
Der kleine Tanz herum -- -- könnte wahrscheinlich vermieden werden, aber ich bevorzuge es sehr explizit, was läuft, also halte ich poetry als links vordere Argumentation.
Um einen Speicherflamegraph zu erhalten:
poetry run memray run -m neetcode_practice_2024.arrays_and_hashing.problem_1_contains_duplicate --integer_array " 1, 2, 3, 4 "
poetry run python -m memray flamegraph memray-neetcode_practice_2024.arrays_and_hashing.problem_1_contains_duplicate.554244.bin
Um einen CPU Flamgraph (oder andere Grafiken) zu erhalten:
poetry run python -m cProfile -o program.prof -m neetcode_practice_2024.arrays_and_hashing.problem_1_contains_duplicate --integer_array " 1, 2, 3, 4, 4 "
poetry run snakeviz program.prof
Benchmarks ausführen und eine grafische Zusammenfassung erhalten:
poetry run pytest --benchmark-only --benchmark-histogram
Lernliste
Sortieren von Algorithmen
- Implementieren Sie von Grund auf neu: Bubble -Sortierung, Zusammenführen der Sortierung, schnelle Sortierung, Haufensart.
- Finden Sie bei einer Reihe von Ganzzahlen das kTH kleinste Element mit dem Quick Select -Algorithmus.
- Implementieren Sie den Zähl -Sort -Algorithmus, um eine Reihe von Ganzzahlen mit einem bekannten Wertebereich zu sortieren.
- Lösen Sie das Problem "Drei-Wege-Partition" mit der Schnellsorte, um ein Array effizient mit doppelten Werten zu sortieren.
Suchen von Algorithmen
- Implementieren Sie von Grund auf neu: Binäre Suche (für ein sortiertes Array), lineare Suche.
- Finden Sie bei einem gedrehten sortierten Array das Zielelement mit einer modifizierten Binärsuche.
Diagramm, Baum und Algorithmen des Traversals davon
- Implementieren Sie von Grund auf neu: Breadth-First Search (BFS), Tiefe-First-Suche (DFS), Dijkstra-Algorithmus, Bellman-Ford-Algorithmus.
- Implementieren Sie verschiedene Darstellungen: Adjazenzmatrix, Adjazenzliste.
- Finden Sie den kürzesten Weg zwischen zwei Knoten in einem gewichteten Diagramm mit dem Algorithmus von Dijkstra.
- Implementieren Sie einen binären Suchbaum und führen Sie grundlegende Operationen wie Einfügen, Löschung und Suche durch.
- Überprüfen Sie bei einem gerichteten Diagramm, ob zwischen zwei Knoten eine Route vorhanden ist.
- Finden Sie die Anzahl der angeschlossenen Komponenten in einem ungerichteten Diagramm.
- Implementieren Sie die topologische Sortierung für eine gerichtete Acyclic Graph (DAG).
- Finden Sie den niedrigsten gemeinsamen Vorfahren (LCA) von zwei Knoten in einem binären Baum.
- Überprüfen Sie bei einem binären Baum, ob es sich um einen gültigen Binär -Suchbaum (BST) handelt.
- Finden Sie bei einem Diagramm alle stark verbundenen Komponenten (SCCs) unter Verwendung des Algorithmus von Kosaraju oder Tarjans Algorithmus.
- Implementieren Sie den Floyd-Warshall-Algorithmus, um die kürzesten Wege in einem gewichteten Diagramm zu finden.
- Führen Sie bei einem N-Ary-Baum einen Traversal oder eine Tiefenquelle (z. B. Vorbestellung, Nachbestellung) durch.
Dynamische Programmierung
- Verständnis des Konzepts, ein Problem in kleinere überlappende Unterprobleme zu unterteilen und Memoisierung oder Tabellierung zu verwenden.
- Lösen Sie das klassische "Fibonacci" -Problem mit rekursiven und dynamischen Programmieransätzen.
- Finden Sie bei einem Satz von Elementen mit Gewichten und Werten den Maximalwert, der mit einem gegebenen maximalen Gewicht unter Verwendung von 0-1 Knapsack-Problemen erhalten werden kann.
Gierige Algorithmen
- Das Verständnis von Problemen, bei denen lokal optimale Entscheidungen zu einer global optimalen Lösung führen.
- Implementieren Sie eine Lösung für das "Aktivitätsauswahlproblem", bei dem Sie die maximale Anzahl von Aktivitäten auswählen müssen, die sich nicht überschneiden.
- Finden Sie bei einer Reihe von Münzen mit unterschiedlichen Konfessionen und einer Menge die Mindestanzahl von Münzen, die benötigt werden, um diesen Betrag mit gierigem Ansatz zu erreichen.
Backtracking -Algorithmen
- Lösen Sie das Problem "N-Queens", um N Queens auf ein N × N-Schachbrett zu legen, ohne sich gegenseitig anzugreifen.
- Implementieren Sie einen Sudoku -Solver, um ein teilweise gefülltes Sudoku -Puzzle zu lösen.
String Manipulationsalgorithmen
- String Matching
- String -Umkehrung
- Palindrome prüft
- Überprüfen Sie bei zwei Saiten, ob eine eine Permutation des anderen ist.
- Implementieren Sie den Algorithmus "Rabin-Karp", um in einem bestimmten Text ein Muster zu finden.
Bitmanipulationsalgorithmen
- Bitgewise Operations, das einzelne einzigartige Element in einem Array finden.
- Finden Sie bei einem Array, in dem alle Zahlen zweimal auftreten, die einzelne eindeutige Zahl.
- Implementieren Sie eine Funktion, um die Anzahl der Bits zu zählen, die in einer Ganzzahl auf 1 gesetzt sind.
Algorithmen teilen und erobern
- Binäre Suche, die maximale Subareray -Summe finden.
- Implementieren Sie den Karatsuba -Algorithmus zur schnellen Multiplikation von DIVIS -Ganzzahlen.
- Finden Sie das nächstgelegene Punktpaar unter einer Reihe von Punkten im 2D -Raum mit dem Ansatz der Kluft und des Erobers.
Randomisierte Algorithmen
- Mischen Sie ein Array zufällig an der Stelle.
- Implementieren Sie den Algorithmus "Randomisierter Auswahl", um das kleinste KTH -Element in einem Array zu finden.
Schiebefenstertechnik
- Finden Sie bei einer Reihe von Ganzzahlen die maximale Summe einer zusammenhängenden Subtarray der Größe k.
- Finden Sie das längste Substring mit höchstens k unterschiedlichen Zeichen in einer bestimmten Zeichenfolge.
Intervallprobleme
- Bei einer Liste von Intervallen verschmelzen überlappende Intervalle.
- Suchen Sie die Mindestanzahl von Besprechungsräumen, die erforderlich sind, um eine Liste von Intervallen zu planen.
Versuche
- Implementieren Sie eine Trie -Datenstruktur für eine effiziente String -Suche und -Ar -Abruf.
- Finden Sie bei einer Liste von Wörtern das längste gemeinsame Präfix mit einem Trie.
- Implementieren Sie eine automatische Vervollständigung mit einem Trie für einen bestimmten Satz von Wörtern.
- Finden Sie bei einer Liste von Wörtern alle Wortpaare so, dass die Verkettung ein Palindrom bildet.
Hashing
- Implementierung von Hash -Funktionen, Kollisionsauflösungstechniken und Anwendungsfällen.
- Implementieren Sie eine Hash -Tabelle mit Kollisionsauflösung (z. B. Erketten oder offener Adressierung).
- Finden Sie das erste nicht wiederholte Zeichen in einer Zeichenfolge mit einer Hash-Karte.
- Implementieren Sie den Rabin-Karp-Algorithmus für die String-Übereinstimmung mit mehreren Mustern.
- Finden Sie das längste Substring, ohne Zeichen mit einer Hash -Karte für die Charakterfrequenz zu wiederholen.
Haufen
- Implementierung von Min-Häpsen und Max-Häpten und deren Anwendungen (z. B. vorrangige Warteschlangen).
- Implementieren Sie einen Min-heap oder max-heap von Grund auf neu.
- Finden Sie bei einer Reihe von Elementen das KTH größte Element unter Verwendung eines haufensbasierten Ansatzes.
Matrixmanipulation
- Drehen Sie sie mit einer M × N-Matrix um 90 Grad ein.
- Finden Sie bei einer Matrix von 0 und 1 das größte Quadrat von 1s (maximale Größe quadratischer Submatrix) und geben Sie seine Fläche zurück.
Rot-schwarze Bäume oder AVL-Bäume
- Implementieren Sie Insertions- und Löschvorgänge für einen rot-schwarzen Baum oder einen AVL-Baum.
- Führen Sie Rotationen durch, um einen unausgeglichenen binären Suchbaum auszugleichen.
Datenstrukturimplementierungen
- Arrays und Listen: Implementieren von Arrays, verknüpften Listen und deren Operationen.
- Stapel und Warteschlangen: Implementieren von Stapel- und Warteschlangendatenstrukturen und deren Anwendungen.
- Hash -Karten: Implementierung von Hash -Karten und Verständnis ihrer Zeitkomplexität.
Werkzeuge
Algorithmen und Datenstrukturen werden durch eine einfache, erholsame API für eine realistischere Einstellung und einen robusteren Test ausgesetzt:
(Die hier aufgeführten Tools sind möglicherweise spezifisch für einige Sprachen)
