JavaScript-Algorithmen und Datenstrukturen

Dieses Repository enthält JavaScript Beispiele für viele gängige Algorithmen und Datenstrukturen.

Jeder Algorithmus und jede Datenstruktur hat eine eigene README mit zugehörigen Erklärungen und weiterführenden Links (einschließlich zu YouTube-Videos).

Lies dies in anderen Sprachen: English 简体中文, 繁體中文, 한국어, 日本語, Polski, Français, Español, Português, Русский, Türk, Italiana, Bahasa Indonesia, Українська, Arabic, Uzbek עברית

Datenstrukturen

Eine Datenstruktur ist eine bestimmte Art und Weise, Daten in einem Computer so zu organisieren und zu speichern, dass sie effizient erreicht und verändert werden können. Genauer gesagt, ist eine Datenstruktur eine Sammlung von Werten, den Beziehungen zwischen ihnen und den Funktionen oder Operationen, die auf die Daten angewendet werden können.

B - Anfänger:innen, A - Fortgeschrittene

• B Verkettete Liste (Linked List)
• B Doppelt verkettete Liste (Doubly Linked List)
• B Warteschlange (Queue)
• B Stapelspeicher (Stack)
• B Hashtabelle (Hash Table)
• B Heap-Algorithmus (Heap) - max und min Heap-Versionen
• B Vorrangwarteschlange (Priority Queue)
• A Trie (Trie)
• A Baum (Tree)
• A Binärer Suchbaum (Binary Search Tree)
• A AVL-Baum (AVL Tree)
• A Rot-Schwarz-Baum (Red-Black Tree)
• A Segment-Baum (Segment Tree) - mit Min/Max/Summenbereich-Abfrage Beispiel
• A Fenwick Baum (Fenwick Tree) (Binär indizierter Baum / Binary Indexed Tree)
• A Graph (Graph) (sowohl gerichtet als auch ungerichtet)
• A Union-Find-Struktur (Disjoint Set)
• A Bloomfilter (Bloom Filter)

Algorithmen

Ein Algorithmus ist eine eindeutige Spezifikation, wie eine Klasse von Problemen zu lösen ist. Er besteht aus einem Satz von Regeln, die eine Abfolge von Operationen genau definieren.

B - Anfänger:innen, A - Fortgeschrittene

Algorithmen nach Thema

• Mathe
• B Bitmanipulation (Bit Manipulation) - Bits setzen/lesen/aktualisieren/löschen, Multiplikation/Division durch zwei negieren usw..
• B Faktoriell (Factorial)
• B Fibonacci-Zahl (Fibonacci Number) - Klassische und geschlossene Version
• B Primfaktoren (Prime Factors) - Auffinden von Primfaktoren und deren Zählung mit Hilfe des Satz von Hardy-Ramanujan (Hardy-Ramanujan's theorem)
• B Primzahl-Test (Primality Test) (Probedivision / trial division method)
• B Euklidischer Algorithmus (Euclidean Algorithm) - Berechnen des größten gemeinsamen Teilers (ggT)
• B Kleinstes gemeinsames Vielfaches (Least Common Multiple) (kgV)
• B Sieb des Eratosthenes (Sieve of Eratosthenes) - Finden aller Primzahlen bis zu einer bestimmten Grenze
• B Power of two (Is Power of Two) - Prüft, ob die Zahl eine Zweierpotenz ist (naive und bitweise Algorithmen)
• B Pascalsches Dreieck (Pascal's Triangle)
• B Komplexe Zahlen (Complex Number) - Komplexe Zahlen und Grundoperationen mit ihnen
• B Bogenmaß & Grad (Radian & Degree) - Umrechnung von Bogenmaß in Grad und zurück
• B Fast Powering Algorithmus (Fast Powering)
• B Horner-Schema (Horner's method) - Polynomauswertung
• B Matrizen (Matrices) - Matrizen und grundlegende Matrixoperationen (Multiplikation, Transposition usw.)
• B Euklidischer Abstand (Euclidean Distance) - Abstand zwischen zwei Punkten/Vektoren/Matrizen
• A Ganzzahlige Partitionierung (Integer Partition)
• A Quadratwurzel (Square Root) - Newtonverfahren (Newton's method)
• A Liu Hui π Algorithmus (Liu Hui π Algorithm) - Näherungsweise π-Berechnungen auf Basis von N-gons
• A Diskrete Fourier-Transformation (Discrete Fourier Transform) - Eine Funktion der Zeit (ein Signal) in die Frequenzen zerlegen, aus denen sie sich zusammensetzt
• Sets
• B Kartesisches Produkt (Cartesian Product) - Produkt aus mehreren Mengen
• B Fisher-Yates-Verfahren (Fisher–Yates Shuffle) - Zufällige Permutation einer endlichen Folge
• A Potenzmenge (Power Set) - Alle Teilmengen einer Menge (Bitweise und Rücksetzverfahren Lösungen(backtracking solutions))
• A Permutation (Permutations) (mit und ohne Wiederholungen)
• A Kombination (Combinations) (mit und ohne Wiederholungen)
• A Problem der längsten gemeinsamen Teilsequenz (Longest Common Subsequence) (LCS)
• A Längste gemeinsame Teilsequenz (Longest Increasing Subsequence)
• A Der kürzeste gemeinsame String (Shortest Common Supersequence) (SCS)
• A Rucksackproblem (Knapsack Problem) - "0/1" und "Ungebunden"
• A Das Maximum-Subarray Problem (Maximum Subarray) - "Brute-Force-Methode" und "Dynamische Programmierung" (Kadane' Algorithmus)
• A Kombinationssumme (Combination Sum) - Alle Kombinationen finden, die eine bestimmte Summe bilden
• Zeichenketten (Strings)
• B Hamming-Abstand (Hamming Distance) - Anzahl der Positionen, an denen die Symbole unterschiedlich sind
• A Levenshtein-Distanz (Levenshtein Distance) - Minimaler Editierabstand zwischen zwei Sequenzen
• A Knuth-Morris-Pratt-Algorithmus (Knuth–Morris–Pratt Algorithm) (KMP Algorithmus) - Teilstringsuche (Mustervergleich / Pattern Matching)
• A Z-Algorithmus (Z Algorithm) - Teilstringsuche (Mustervergleich / Pattern Matching)
• A Rabin-Karp-Algorithmus (Rabin Karp Algorithm) - Teilstringsuche
• A Längstes häufiges Teilzeichenfolgenproblem (Longest Common Substring)
• A Regulärer Ausdruck (Regular Expression Matching)
• Suchen
• B Lineare Suche (Linear Search)
• B Sprungsuche (Jump Search) (oder Blocksuche) - Suche im sortierten Array
• B Binäre Suche (Binary Search) - Suche in einem sortierten Array
• B Interpolationssuche (Interpolation Search) - Suche in gleichmäßig verteilt sortiertem Array
• Sortieren
• B Bubblesort (Bubble Sort)
• B Selectionsort (Selection Sort)
• B Einfügesortierenmethode (Insertion Sort)
• B Haldensortierung (Heap Sort)
• B Mergesort (Merge Sort)
• B Quicksort (Quicksort) - in-place und non-in-place Implementierungen
• B Shellsort (Shellsort)
• B Countingsort (Counting Sort)
• B Fachverteilen (Radix Sort)
• Verkettete Liste (Linked List)
• B Gerade Traversierung (Straight Traversal)
• B Umgekehrte Traversierung (Reverse Traversal)
• Bäume
• B Tiefensuche (Depth-First Search) (DFS)
• B Breitensuche (Breadth-First Search) (BFS)
• Graphen
• B Tiefensuche (Depth-First Search) (DFS)
• B Breitensuche (Breadth-First Search) (BFS)
• B Algorithmus von Kruskal (Kruskal’s Algorithm) - Finden des Spannbaum (Minimum Spanning Tree / MST) für einen gewichteten ungerichteten Graphen
• A Dijkstra-Algorithmus (Dijkstra Algorithm) - Finden der kürzesten Wege zu allen Knoten des Graphen von einem einzelnen Knotenpunkt aus
• A Bellman-Ford-Algorithmus (Bellman-Ford Algorithm) - Finden der kürzesten Wege zu allen Knoten des Graphen von einem einzelnen Knotenpunkt aus
• A Algorithmus von Floyd und Warshall (Floyd-Warshall Algorithm) - Die kürzesten Wege zwischen allen Knotenpaaren finden
• A Zykluserkennung (Detect Cycle) - Sowohl für gerichtete als auch für ungerichtete Graphen (DFS- und Disjoint-Set-basierte Versionen)
• A Algorithmus von Prim (Prim’s Algorithm) - Finden des Spannbaums (Minimum Spanning Tree / MST) für einen gewichteten ungerichteten Graphen
• A Topologische Sortierung (Topological Sorting) - DFS-Verfahren
• A Artikulationspunkte (Articulation Points) - Algorithmus von Tarjan (Tarjan's algorithm) (DFS basiert)
• A Brücke (Bridges) - DFS-basierter Algorithmus
• A Eulerkreisproblem (Eulerian Path and Eulerian Circuit) - Algorithmus von Fleury (Fleury's algorithm) - Jede Kante genau einmal durchlaufen.
• A Hamiltonkreisproblem (Hamiltonian Cycle) - Jeden Eckpunkt genau einmal durchlaufen.
• A Starke Zusammenhangskomponente (Strongly Connected Components) - Kosarajus Algorithmus
• A Problem des Handlungsreisenden (Travelling Salesman Problem) - Kürzestmögliche Route, die jede Stadt besucht und zur Ausgangsstadt zurückkehrt
• Kryptographie
• B Polynomiale Streuwertfunktion(Polynomial Hash) - Rollierende Streuwert-Funktion basierend auf Polynom
• B Schienenzaun Chiffre (Rail Fence Cipher) - Ein Transpositionsalgorithmus zur Verschlüsselung von Nachrichten
• B Caesar-Verschlüsselung (Caesar Cipher) - Einfache Substitutions-Chiffre
• B Hill-Chiffre (Hill Cipher) - Substitutionschiffre basierend auf linearer Algebra
• Maschinelles Lernen
• B Künstliches Neuron (NanoNeuron) - 7 einfache JS-Funktionen, die veranschaulichen, wie Maschinen tatsächlich lernen können (Vorwärts-/Rückwärtspropagation)
• B Nächste-Nachbarn-Klassifikation (k-NN) - k-nächste-Nachbarn-Algorithmus
• B k-Means (k-Means) - k-Means-Algorithmus
• Image Processing
• B Inhaltsabhängige Bildverzerrung (Seam Carving) - Algorithmus zur inhaltsabhängigen Bildgrößenänderung
• Unkategorisiert
• B Türme von Hanoi (Tower of Hanoi)
• B Rotationsmatrix (Square Matrix Rotation) - In-Place-Algorithmus
• B Jump Game (Jump Game) - Backtracking, dynamische Programmierung (Top-down + Bottom-up) und gierige Beispiele
• B Eindeutige Pfade (Unique Paths) - Backtracking, dynamische Programmierung und Pascalsches Dreieck basierte Beispiele
• B Regenterrassen (Rain Terraces) - Auffangproblem für Rege