Lektionen
Algorithmen und Datenstrukturen in sinnvoller Reihenfolge. Jede Lektion geht echten Code Zeile für Zeile durch.
Big-O: Wachstum messen
gratisArrays und Hashmaps
gratis- Algorithmusgratis
Array an Ort und Stelle umkehren
Tausche die beiden Enden und arbeite dich zur Mitte vor. Kein zweites Array nötig.
- Zeit
- O(n)
- Speicher
- O(1)
- Algorithmusgratis
Two Sum mit einer Hashmap
Finde in einem Durchlauf zwei Zahlen mit einer Zielsumme, auch in einem unsortierten Array.
- Zeit
- O(n)
- Speicher
- O(n)
Grundlagen des Sortierens
gratisZwei Zeiger und Sliding Window
gratis- Algorithmusgratis
Zwei Zeiger
Finde in einem sortierten Array ein Paar, das eine Zielsumme ergibt, in einem einzigen Durchlauf.
- Zeit
- O(n)
- Speicher
- O(1)
- Algorithmusgratis
Sliding Window
Finde die größte Summe von k aufeinanderfolgenden Zahlen, ohne das Fenster jedes Mal neu aufzusummieren.
- Zeit
- O(n)
- Speicher
- O(1)
Stacks, Queues und verkettete Listen
gratis- Datenstrukturgratis
Stack
Eine Sammlung nach dem Prinzip „last in, first out“: Du arbeitest immer nur oben.
- Zeit
- O(1)
- Speicher
- O(n)
- Datenstrukturgratis
Queue
Eine Sammlung nach dem Prinzip „first in, first out“: hinten anstellen, vorne entnehmen.
- Zeit
- O(1)
- Speicher
- O(n)
- Algorithmusgratis
Verkettete Liste umkehren
Drehe jeden next-Zeiger an Ort und Stelle um, mit drei Zeigern: prev, curr und nxt.
- Zeit
- O(n)
- Speicher
- O(1)
Rekursion
pro- Algorithmuspro
Rekursion: Fakultät
Eine Funktion, die sich selbst mit einer kleineren Eingabe aufruft, bis sie einen Fall direkt beantworten kann.
- Zeit
- O(n)
- Speicher
- O(n)
- Algorithmuspro
Rekursion: der Fibonacci-Aufrufbaum
Zwei rekursive Aufrufe pro Schritt lassen einen Baum aus Aufrufen wachsen und zeigen viel doppelte Arbeit.
- Zeit
- O(2ⁿ)
- Speicher
- O(n)
Binäre Suche
proBäume: BFS und DFS
pro- Algorithmuspro
Tiefensuche im Baum
Durchlaufe einen binären Suchbaum in-order: linker Teilbaum, dann der Knoten, dann der rechte Teilbaum.
- Zeit
- O(n)
- Speicher
- O(h)
- Algorithmuspro
Breitensuche im Baum
Durchlaufe einen Baum Ebene für Ebene und merke dir mit einer Queue, welcher Knoten als Nächstes dran ist.
- Zeit
- O(n)
- Speicher
- O(n)
Dynamische Programmierung
pro- Algorithmuspro
Dynamische Programmierung: Treppensteigen
Zähle die Wege eine Treppe hinauf mit Schritten von 1 oder 2 Stufen, aufgebaut aus kleineren Antworten.
- Zeit
- O(n)
- Speicher
- O(n)
- Algorithmuspro
Dynamische Programmierung: Münzwechsel
Finde die wenigsten Münzen für einen Betrag, ein Problem, bei dem es schiefgeht, immer die größte Münze zu nehmen.
- Zeit
- O(n·m)
- Speicher
- O(n)
- Algorithmuspro
Dynamische Programmierung: Wege im Raster
Zähle die Wege durch ein Raster, die sich nur nach rechts oder unten bewegen.
- Zeit
- O(n·m)
- Speicher
- O(n·m)