Kodierungsmuster: ein intelligenterer Ansatz zur Kodierung der Vorbereitung auf Vorstellungsgespräche

Die Vorbereitung auf Coding-Interviews kann eine echte Herausforderung sein, da Entwickler oft mehrere Wochen damit verbringen, neues Material zu überprüfen und zu lernen.

Die Wahrheit ist, dass sich die meisten Entwickler nie ganz auf ihre Programmiergespräche vorbereitet fühlen. Es ist nicht ungewöhnlich, dass Entwickler wochenlang Probleme mit LeetCode lösen und sich dennoch unvorbereitet fühlen. Offensichtlich gibt es bei diesem Ansatz Probleme.

Werfen wir einen genaueren Blick auf einige Probleme, die mit der herkömmlichen Vorbereitung von Codierungsinterviews verbunden sind.

Die Fallstricke der traditionellen Vorbereitung auf Vorstellungsgespräche

Eine der häufigsten Fallstricke bei der herkömmlichen Vorbereitung auf Vorstellungsgespräche ist das „Grinding“. Bei diesem Ansatz geht es darum, möglichst viele LeetCode- Probleme ohne einen klaren Plan oder eine klare Strategie zu lösen. Obwohl dies wie eine produktive Strategie erscheint, hat sie mehrere Nachteile.

Wenn Sie Probleme ohne strukturierten Ansatz lösen, erkennen Sie möglicherweise Ihre Schwächen nicht. Es gibt keinen bewussten Plan für Ihr Studium; Das Ziel besteht einfach darin, so viele Probleme wie möglich zu lösen. Dadurch haben Sie möglicherweise das Gefühl, viel gelernt zu haben, es könnten jedoch erhebliche Wissenslücken bestehen.

Darüber hinaus besteht das Problem darin, dass es im Wesentlichen darum geht, Lösungen für eine Vielzahl von Problemen auswendig zu lernen. Der Versuch, sich Lösungen für hundert verschiedene Codierungsprobleme zu merken, erweist sich als wirkungslos, wenn Interviewer Fragen stellen, die auch nur geringfügig von denen abweichen, denen Sie zuvor begegnet sind. Dies kann dazu führen, dass Sie das Gefühl haben, nicht auf die Bewältigung von Problemvarianten vorbereitet zu sein.

Mein letztes Problem mit dieser Strategie ist, dass sie auf lange Sicht mehr Stress und Kopfschmerzen verursacht. Wenn Sie jedes Mal, wenn Sie den Job wechseln möchten, die gleiche mehrwöchige Pauksitzung absolvieren müssen, werden Sie jedes Mal Schwierigkeiten haben. Sie werden Wochen damit verbringen, Dinge neu zu lernen und die gleichen Probleme wie zuvor zu lösen.

Angesichts dieser Herausforderungen muss es einen besseren Weg geben.

Ein besserer Weg: Codierungsmuster berücksichtigen

Gibt es also einen effektiveren und nachhaltigeren Ansatz zur Codierung der Interviewvorbereitung? Die Antwort liegt im Verstehen und Nutzen von Codierungsmustern.

Wenn ich mich auf Codierungsinterviews vorbereite, lege ich Wert darauf, die zugrunde liegenden Problemmuster zu erfassen. Diese Muster, zu denen Techniken wie Two-Pointers , Sliding Window , Modified Binary Search , Topological Sort und viele mehr gehören, bieten einen vielseitigen und leistungsstarken Rahmen für die Bewältigung einer Vielzahl von Codierungsproblemen. Der Schwerpunkt verlagert sich vom Auswendiglernen von Lösungen hin zu bewährten Problemlösungstechniken.

Indem Sie sich auf Codierungsmuster konzentrieren, können Sie Ihre Vorbereitung auf Vorstellungsgespräche deutlich rationalisieren und effizienter machen.

Denken Sie daran: Bereiten Sie sich intelligenter vor, nicht härter.

Was zu erwarten ist?

In diesem Artikel habe ich das zusammengestellt Top 15 Codierungsmuster die Sie wissen müssen, um jede Programmierfrage beantworten zu können. Ich werde aufschlüsseln, was jedes Muster ist und wie es funktioniert. Teilen Sie Schlüsselindikatoren mit, die Ihnen helfen, das Muster zu erkennen, und bieten Sie schließlich detaillierte Grafiken mit Vorlagencode an, um Ihr Verständnis zu festigen.

Obwohl ich in diesem Artikel viel behandele, können Sie sich unseren umfassenden Vorbereitungskurs für Coding-Interviews auf Techinterviews.io ansehen, wenn Sie tiefergehende Schulungen, Erklärungen und Programmierübungen wünschen. Wir behandeln auch wichtige Themen wie Datenstrukturen , Verhaltensinterviews und sogar Gehaltsverhandlungen .

Lassen Sie uns nun in diese Codierungsmuster eintauchen.

1. Umkehrung der verknüpften Liste

Bei der Umkehrung verknüpfter Listen wird die Richtung von Zeigern in einer verknüpften Liste geändert, um die Reihenfolge der Elemente umzukehren. Es handelt sich um eine grundlegende Operation in Datenstrukturen, die häufig eine sorgfältige Manipulation der Knotenreferenzen erfordert.

Dies ist nützlich, wenn es sich um eine verknüpfte Liste handelt und die Einschränkung darin besteht, sie an Ort und Stelle umzukehren.

Der Prozess zum Umkehren einer verknüpften Liste an Ort und Stelle ist wie folgt:

1. Beginnen Sie mit der Definition von drei Variablen: current , previous und next . Legen Sie current als Kopf der verknüpften Liste fest und initialisieren Sie previous und next als None.

2. Während die aktuelle Variable nicht None ist, gehen Sie wie folgt vor:

   1. Speichern Sie den nächsten Knoten in einer temporären Variablen.
   2. Kehren Sie den Zeiger des aktuellen Knotens um, um auf den vorherigen Knoten zu zeigen.
   3. Aktualisieren Sie previous als aktuellen Knoten und current als nächsten Knoten.

3. Setzen Sie abschließend den Kopf der umgekehrten Liste auf den zuletzt erreichten Knoten, der in der vorherigen Variablen gespeichert ist.

Schlüsselindikatoren:

• Sie müssen die Reihenfolge der Elemente in einer verknüpften Liste umkehren.
• Probleme bestehen bei der Suche nach Palindromen in verknüpften Listen.
• Sie möchten die Reihenfolge der Elemente in einer bestimmten Unterliste innerhalb der Liste umkehren.

Vorlagencode:

Python

 def reverse_linked_list(head): curr = head prev = None while curr: next_node = curr.next curr.next = prev prev = curr curr = next_node return prev

JS

 function reverseLinkedList(head) { let curr = head; let prev = null; while (curr) { const nextNode = curr.next; curr.next = prev; prev = curr; curr = nextNode; } return prev; }

Java

 public ListNode reverseLinkedList(ListNode head) { ListNode curr = head; ListNode prev = null; while (curr != null) { ListNode nextNode = curr.next; curr.next = prev; prev = curr; curr = nextNode; } return prev; }

2. Modifizierte binäre Suche

Die modifizierte binäre Suche passt den klassischen binären Suchalgorithmus an, um verschiedene Probleme zu lösen. Zu den Variationen gehören die Suche nach dem ersten/letzten Vorkommen eines Elements oder die Suche in gedrehten Arrays. Es erfordert einen sorgfältigen Umgang mit Mittelpunkten und Bedingungen.

Wenn Sie jemals ein sortiertes Array, eine verknüpfte Liste oder eine Matrix erhalten, sollten Sie die Verwendung einer modifizierten binären Suche in Betracht ziehen.

Hier ist eine Aufschlüsselung, wie dieses Muster auf eine sortierte Datenstruktur angewendet wird:

1. Beginnen Sie damit, den Mittelpunkt zwischen der Start- und Endposition zu ermitteln. Um einen möglichen Ganzzahlüberlauf zu vermeiden, ist es sicherer, die Mitte wie folgt zu berechnen: middle = start + (end - start) / 2 .
2. Überprüfen Sie, ob der Schlüssel mit dem Element am mittleren Index übereinstimmt. Wenn dies der Fall ist, geben Sie als Ergebnis den mittleren Index zurück.
3. Wenn der Schlüssel nicht mit dem Element am mittleren Index übereinstimmt, fahren Sie mit den nächsten Schritten fort.
4. Bewerten Sie, ob der Schlüssel kleiner als das Element in der Indexmitte ist. Wenn dies der Fall ist, schränken Sie Ihren Suchbereich ein, indem Sie Ende auf Mitte - 1 aktualisieren.
5. Wenn umgekehrt der Schlüssel größer als das Element am Index middle ist, passen Sie Ihren Suchbereich an, indem Sie start auf middle + 1 aktualisieren.

Schlüsselindikatoren:

• Sie arbeiten mit einer sortierten Datenstruktur.
• Sie müssen bestimmte Elemente, Grenzen oder Drehpunkte effizient finden.
• Probleme bestehen bei der Suche in gedrehten sortierten Arrays.

Vorlagencode:

Python

 def binary_search(arr: List[int], target: int) -> int: left, right = 0, len(arr) - 1 first_true_index = -1 # Perform binary search until left and right pointers meet while left <= right: mid = (left + right) // 2 if feasible(mid): # If the condition is true at mid index, update first_true_index first_true_index = mid right = mid - 1 else: # If the condition is false at mid index, narrow down the search space left = mid + 1 return first_true_index

JS

 function binarySearch(arr, target) { let left = 0; let right = arr.length - 1; let firstTrueIndex = -1; // Perform binary search until left and right pointers meet while (left <= right) { const mid = Math.floor((left + right) / 2); if (feasible(mid)) { // If the condition is true at mid index, update firstTrueIndex firstTrueIndex = mid; right = mid - 1; } else { // If the condition is false at mid index, narrow down the search space left = mid + 1; } } return firstTrueIndex; }

Java

 public int binarySearch(int[] arr, int target) { int left = 0; int right = arr.length - 1; int firstTrueIndex = -1; // Perform binary search until left and right pointers meet while (left <= right) { int mid = left + (right - left) / 2; if (feasible(mid)) { // If the condition is true at mid index, update firstTrueIndex firstTrueIndex = mid; right = mid - 1; } else { // If the condition is false at mid index, narrow down the search space left = mid + 1; } } return firstTrueIndex; }

3. Zwei Hinweise

Die Zwei-Zeiger-Technik beinhaltet die Verwaltung von zwei Zeigern, die eine Datenstruktur durchlaufen, typischerweise Arrays oder verknüpfte Listen, die häufig für Probleme mit Paaren oder Unterarrays verwendet werden. Es optimiert Probleme, die einen Vergleich zwischen Elementen an verschiedenen Positionen erfordern.

Der Vorteil dieser Technik liegt in ihrer Einfachheit und Effizienz, insbesondere beim Umgang mit linearen Datenstrukturen wie Arrays oder Strings, bei denen Sie zunächst möglicherweise nur einen Zeiger verwenden. Durch die Verwendung von zwei Zeigern können Sie redundante Vorgänge umgehen und die Laufzeiteffizienz erheblich steigern, indem Sie sie möglicherweise von O(n^2) auf O(n) reduzieren.

Das „Two Pointers“ -Muster umfasst mehrere Variationen, die jeweils auf bestimmte Szenarien zugeschnitten sind. Zu diesen Variationen gehören die gleiche Richtung , die entgegengesetzte Richtung und eine einzigartige Methode, die als „schnell und langsam“ bekannt ist und oft als „Schildkröten-und-Hase“ -Technik bezeichnet wird, bei der sich zwei Zeiger mit unterschiedlichen Geschwindigkeiten durch eine Datenstruktur bewegen, was besonders für die Erkennung nützlich ist Fahrräder.

Wenn Sie zum Durchlaufen einer Datenstruktur mehrere Zeiger verwenden, können Sie Ihren Ansatz nach dem Muster „Zwei Zeiger“ kategorisieren.

Schlüsselindikatoren:

• Sie müssen Elemente an verschiedenen Positionen vergleichen oder bearbeiten.
• Probleme erfordern die Suche nach Elementpaaren in einem sortierten Array.
• Sie möchten Duplikate effizient aus einem sortierten Array entfernen.
• Wenn Sie mit linearen Datenstrukturen (Arrays, Strings oder verknüpften Listen) arbeiten und mit einer quadratischen Zeitkomplexität ( O(n^2) Brute-Force-Lösung) konfrontiert sind, sollten Sie die Verwendung von zwei Zeigern in Betracht ziehen.

Vorlagencode:

Vorlage für die Variante „entgegengesetzte Richtung“.

Python

 def two_pointers_opposite(arr): left = 0 right = len(arr) - 1 ans = 0 while left < right: # Perform logic using the left and right pointers if CONDITION: left += 1 else: right -= 1 return ans

JS

 function twoPointersOpposite(arr) { let left = 0; let right = arr.length - 1; let ans = 0; while (left < right) { // Perform logic using the left and right pointers if (CONDITION) { left++; } else { right--; } } return ans; }

Java

 public int twoPointersOpposite(int[] arr) { int left = 0; int right = arr.length - 1; int ans = 0; while (left < right) { // Perform logic using the left and right pointers if (CONDITION) { left++; } else { right--; } } return ans; }

4. Schiebefenster

Bei der Sliding-Window-Technik wird ein dynamisches Fenster über einer linearen Datenstruktur wie Arrays, Strings oder verknüpften Listen verwaltet. Die Größe des Fensters kann je nach Implementierung variieren und kann auch als fester Wert festgelegt werden. Das Hauptziel dieses Fensters ist die kontinuierliche Überwachung und Erfassung von Daten, die bestimmte Kriterien erfüllen, was es besonders wertvoll für die effiziente Lösung von Subarray- oder Substring-Problemen macht.

Dieses Muster verwendet häufig eine Hash-Map, um die Verfolgung einzelner Daten innerhalb des Fensters zu erleichtern. Es ist jedoch wichtig zu beachten, dass dieser Ansatz zu einer Raum-Zeit-Komplexität von O(n) führen kann.

Schlüsselindikatoren:

• Sie müssen zusammenhängende oder nicht zusammenhängende Subarrays oder Teilzeichenfolgen analysieren.
• Probleme bestehen bei der Verfolgung von Sequenzen variabler Länge innerhalb eines größeren Datensatzes.
• Sie möchten das maximale Summen-Subarray fester Länge ermitteln.
• Die Problemeingabe ist eine lineare Datenstruktur wie ein Array, eine verknüpfte Liste oder ein String.

Vorlagencode:

Python

 def slidingWindow(nums): # Initialize necessary variables left = 0 window = [] # Initialize the window ans = 0 # Initialize the answer variable for right in range(len(nums)): window.append(nums[right]) # Expand the window to the right while invalid(window): # Condition to shrink the window from the left until it is valid again window.pop(0) # Remove the left element from the window left += 1 ans = max(ans, len(window)) # Update the answer, can vary on your implementation return ans

JS

 function slidingWindow(nums) { let left = 0; const window = []; // Initialize the window let ans = 0; // Initialize the answer variable for (let right = 0; right < nums.length; right++) { window.push(nums[right]); // Expand the window to the right while (invalid(window)) { // Condition to shrink the window from the left until it is valid again window.shift(); // Remove the left element from the window left++; } ans = Math.max(ans, window.length); // Update the answer , can vary on your implementation } return ans; }

Java

 public static int slidingWindow(int[] nums) { int left = 0; List<Integer> window = new ArrayList<>(); // Initialize the window int ans = 0; // Initialize the answer variable for (int right = 0; right < nums.length; right++) { window.add(nums[right]); // Expand the window to the right while (invalid(window)) { // Condition to shrink the window from the left until it is valid again window.remove(0); // Remove the left element from the window left++; } ans = Math.max(ans, window.size()); // Update the answer , can vary on your implementation } return ans; }

5. Top-K-Elemente

Bei diesem Muster geht es darum, die K größten oder kleinsten Elemente in einer Sammlung zu finden, was häufig mithilfe von Datenstrukturen wie Heaps oder Prioritätswarteschlangen implementiert wird. Dies ist nützlich, um eine Teilmenge von Elementen basierend auf ihrem Wert oder ihrer Häufigkeit auszuwählen.

Immer wenn wir aufgefordert werden, die häufigsten, kleinsten oder obersten „K“-Elemente in einem bestimmten Datensatz zu finden, können wir die Verwendung dieses Musters in Betracht ziehen.

Die Funktionsweise ist einfach:

1. Wir fügen „K“-Elemente in unseren Min- oder Max-Heap ein (dies hängt von der Implementierung ab).
2. Jedes Mal, wenn wir unseren Heap erweitern, müssen wir Anpassungen vornehmen, damit jederzeit die häufigsten/kleinsten/obersten „K“-Elemente beibehalten werden.

Das Schöne an diesem Ansatz liegt in seiner Effizienz; Sie müssen nicht auf Sortieralgorithmen zurückgreifen, da der Heap selbst natürlich die erforderliche Reihenfolge für Sie aufrechterhält.

Schlüsselindikatoren:

• Sie müssen die K größten oder kleinsten Elemente in einer Sammlung identifizieren.
• Probleme erfordern eine Rangfolge von Elementen anhand bestimmter Kriterien.
• Sie möchten die K-häufigsten Elemente in einem Datensatz finden.

Vorlagencode:

Python

 import heapq def top_k_elements(arr, k): heap = [] for num in arr: # Define your own criteria and logic to push elements onto the heap # For example, if you want to find the top k largest elements, push (-num, num) onto the heap heapq.heappush(heap, (-CRITERIA, num)) if len(heap) > k: heapq.heappop(heap) return [num for _, num in heap]

JS

 function topKElements(arr, k) { const minHeap = []; for (const num of arr) { // Define your own criteria and logic to push elements onto the heap // For example, if you want to find the top k smallest elements, push num onto the heap minHeap.push(CRITERIA); if (minHeap.length > k) { minHeap.sort((a, b) => a - b).shift(); } } return minHeap.sort((a, b) => a - b); }

Java

 import java.util.*; public List<Integer> topKElements(int[] arr, int k) { PriorityQueue<Integer> heap = new PriorityQueue<>(Comparator.comparingInt(a -> -CRITERIA)); for (int num : arr) { // Define your own criteria and logic to push elements onto the heap // For example, if you want to find the top k largest elements, push -num onto the heap heap.offer(-CRITERIA); if (heap.size() > k) { heap.poll(); } } List<Integer> topK = new ArrayList<>(); while (!heap.isEmpty()) { topK.add(-heap.poll()); } Collections.reverse(topK); return topK; }

6. Zwei Haufen

Zwei Heaps nutzen zwei Heaps (einen Max-Heap und einen Min-Heap), um bestimmte Probleme zu optimieren, beispielsweise das Finden von Medianwerten in einem Datensatz. Dieses Muster ist besonders nützlich, um eine ausgewogene Struktur aufrechtzuerhalten.

So funktioniert das:

1. Verwenden Sie zwei Heaps: einen Max Heap, um das größte Element zu identifizieren, und einen Min Heap, um das kleinste zu lokalisieren.
2. Füllen Sie den Max Heap mit der ersten Hälfte der Zahlen und versuchen Sie, die größte davon zu finden.
3. Füllen Sie den Min Heap mit der zweiten Hälfte der Zahlen, um die kleinste in diesem Teil zu ermitteln.
4. Der Median der aktuellen Zahlenmenge kann jederzeit berechnet werden, indem die obersten Elemente beider Heaps untersucht werden.

Schlüsselindikatoren:

• Für eine effiziente Medianermittlung müssen Sie eine ausgewogene Struktur beibehalten.
• Zu den Problemen gehört die Behandlung von Schiebefensterproblemen mit dynamischen Medianen.
• Sie möchten Elemente in einer Sammlung basierend auf ihren Werten priorisieren.

Vorlagencode:

Python

 import heapq class TwoHeaps: def __init__(self): self.min_heap = [] # Right heap to store larger half self.max_heap = [] # Left heap to store smaller half def add_num(self, num): if not self.max_heap or num <= -self.max_heap[0]: heapq.heappush(self.max_heap, -num) else: heapq.heappush(self.min_heap, num) # Balance the heaps if necessary if len(self.max_heap) > len(self.min_heap) + 1: heapq.heappush(self.min_heap, -heapq.heappop(self.max_heap)) elif len(self.min_heap) > len(self.max_heap): heapq.heappush(self.max_heap, -heapq.heappop(self.min_heap)) def find_median(self): if len(self.max_heap) == len(self.min_heap): return (-self.max_heap[0] + self.min_heap[0]) / 2.0 else: return -self.max_heap[0] # Usage: two_heaps = TwoHeaps() two_heaps.add_num(1) two_heaps.add_num(2) median = two_heaps.find_median() print("Median:", median)

JS

 class TwoHeaps { constructor() { this.minHeap = []; // Right heap to store larger half this.maxHeap = []; // Left heap to store smaller half } addNumber(num) { if (this.maxHeap.length === 0 || num <= -this.maxHeap[0]) { this.maxHeap.push(-num); } else { this.minHeap.push(num); } // Balance the heaps if necessary if (this.maxHeap.length > this.minHeap.length + 1) { this.minHeap.push(-this.maxHeap.shift()); } else if (this.minHeap.length > this.maxHeap.length) { this.maxHeap.push(-this.minHeap.shift()); } } findMedian() { if (this.maxHeap.length === this.minHeap.length) { return (-this.maxHeap[0] + this.minHeap[0]) / 2; } else { return -this.maxHeap[0]; } } } // Usage: const twoHeaps = new TwoHeaps(); twoHeaps.addNumber(1); twoHeaps.addNumber(2); const median = twoHeaps.findMedian(); console.log("Median:", median);

Java

 import java.util.*; class TwoHeaps { private PriorityQueue<Integer> minHeap; // Right heap to store larger half private PriorityQueue<Integer> maxHeap; // Left heap to store smaller half public TwoHeaps() { minHeap = new PriorityQueue<>(); maxHeap = new PriorityQueue<>(Collections.reverseOrder()); } public void addNumber(int num) { if (maxHeap.isEmpty() || num <= -maxHeap.peek()) { maxHeap.offer(-num); } else { minHeap.offer(num); } // Balance the heaps if necessary if (maxHeap.size() > minHeap.size() + 1) { minHeap.offer(-maxHeap.poll()); } else if (minHeap.size() > maxHeap.size()) { maxHeap.offer(-minHeap.poll()); } } public double findMedian() { if (maxHeap.size() == minHeap.size()) { return (-maxHeap.peek() + minHeap.peek()) / 2.0; } else { return -maxHeap.peek(); } } } // Usage: TwoHeaps twoHeaps = new TwoHeaps(); twoHeaps.addNumber(1); twoHeaps.addNumber(2); double median = twoHeaps.findMedian(); System.out.println("Median: " + median);

7. Monotoner Stapel

Monoton – (einer Funktion oder Größe), die so variiert, dass sie entweder nie abnimmt oder nie zunimmt.

Der monotone Stapel verwaltet einen Stapel von Elementen in nicht aufsteigender oder nicht absteigender Reihenfolge und wird häufig zum Auffinden der nächsten kleineren/größeren Elemente in einem Array verwendet. Es ist ein leistungsstarkes Tool zur Optimierung bestimmter Probleme.

Die Reihenfolge ist streng: Immer wenn wir auf ein Element stoßen, das kleiner (oder größer) ist als das, was sich oben im Stapel befindet, müssen wir aus dem monotonen Stapel herausspringen, bis das Element, das wir hinzufügen möchten, das kleinste (oder größte) Element ist ihnen.

Schlüsselindikatoren:

• Sie müssen Elemente in nicht aufsteigender oder nicht absteigender Reihenfolge verwalten.
• Probleme bestehen darin, das nächstgelegene kleinere oder größere Element zu finden.
• Sie möchten stapelbasierte Abläufe optimieren und gleichzeitig die Ordnung wahren.

Vorlagencode:

Python

 def monotonic_stack(items): stack = [] for item in items: # Adjust the condition for comparisons to suit your needs while stack and stack[-1] <= item: stack.pop() # Do something with the popped item here stack.append(item)

JS

 function monotonicStack(items) { const stack = []; for (const item of items) { // Adjust the condition for comparisons to suit your needs while (stack.length > 0 && stack[stack.length - 1] <= item) { stack.pop(); // Do something with the popped item here } stack.push(item); } return stack; }

Java

 import java.util.*; public static int[] monotonicStack(int[] items) { Deque<Integer> stack = new ArrayDeque<>(); for (int item : items) { // Adjust the condition for comparisons to suit your needs while (!stack.isEmpty() && stack.peekLast() <= item) { stack.pollLast(); // Do something with the popped item here } stack.offerLast(item); } int[] result = new int[stack.size()]; int i = stack.size() - 1; while (!stack.isEmpty()) { result[i--] = stack.pollLast(); } return result; }

8. Tiefensuche

DFS oder Depth-First Search ist eine Traversal-Methode, bei der Sie einen Zweig so tief wie möglich erkunden, bevor Sie ihn zurückverfolgen. Es wird häufig bei Problemen mit Bäumen und Graphen eingesetzt, insbesondere bei Traversierungs- und Suchoperationen.

Um DFS für einen Baum auszuführen, müssen Sie im Stammverzeichnis beginnen. Befolgen Sie dann die folgenden Schritte:

1. Erkunden Sie den aktuellen Knoten, indem Sie seine untergeordneten Knoten besuchen, normalerweise von links nach rechts .
2. Wenden Sie den DFS-Prozess rekursiv auf jeden untergeordneten Knoten an und gehen Sie tiefer in den Baum.
3. Sobald alle untergeordneten Knoten besucht wurden, kehren Sie zum übergeordneten Knoten zurück .
4. Wiederholen Sie die Schritte 1–3 für jedes nicht besuchte untergeordnete Element des aktuellen Knotens, bis alle Knoten im Baum besucht wurden.

Unterschied zu DFS in einem Diagramm: Der Hauptunterschied zwischen Baum-DFS und Diagramm-DFS liegt im Vorhandensein von Zyklen. In einem Baum gibt es per Definition keine Zyklen, daher stellt das Baum-DFS sicher, dass jeder Knoten genau einmal besucht wird, und endet auf natürliche Weise, wenn der gesamte Baum durchlaufen wird. Im Gegensatz dazu muss Graph-DFS zusätzliche Maßnahmen zur Handhabung zyklischer Strukturen innerhalb eines Graphen integrieren. Um zu vermeiden, dass Knoten in einem Zyklus auf unbestimmte Zeit erneut besucht werden, erfordert Graph DFS Mechanismen wie das Markieren besuchter Knoten und die entsprechende Handhabung des Backtrackings . Diese Unterscheidung macht Graph-DFS komplexer als Baum-DFS, da bei Vorhandensein von Zyklen die Möglichkeit von Endlosschleifen besteht.

Schlüsselindikatoren:

• Sie haben es mit Baumstrukturen zu tun und müssen bestimmte Durchlaufreihenfolgen erkunden.
• Zu den Problemen gehören das Finden von Pfaden, das Berechnen der Tiefe oder das Durchführen von Durchquerungen vor/in der Reihenfolge/nach der Bestellung.
• Sie möchten prüfen, ob zwischen zwei Knoten ein Pfad existiert.

Vorlagencode:

Python

 def dfs(root, target): if root is None: # Base case: Check if the current node is None return None if root.val == target: # Base case: Check if the current node value matches the target return root left = dfs(root.left, target) # Recursively search the left subtree if left is not None: # If the target is found in the left subtree, return the result return left return dfs(root.right, target) # Recursively search the right subtree

JS

 function dfs(root, target) { if (root === null) { // Base case: Check if the current node is null return null; } if (root.val === target) { // Base case: Check if the current node value matches the target return root; } let left = dfs(root.left, target); // Recursively search the left subtree if (left !== null) { // If the target is found in the left subtree, return the result return left; } return dfs(root.right, target); // Recursively search the right subtree }

Java

 public TreeNode dfs(TreeNode root, int target) { if (root == null) { // Base case: Check if the current node is null return null; } if (root.val == target) { // Base case: Check if the current node value matches the target return root; } TreeNode left = dfs(root.left, target); // Recursively search the left subtree if (left != null) { // If the target is found in the left subtree, return the result return left; } return dfs(root.right, target); // Recursively search the right subtree }

9. Breitensuche

BFS ist eine Traversierungstechnik für Bäume und Diagramme, die alle Knoten in der aktuellen Tiefe untersucht, bevor sie zur nächsten Ebene übergeht.

Um BFS für einen Baum durchzuführen, müssen Sie im Stammverzeichnis beginnen. Befolgen Sie dann die folgenden Schritte:

1. Initialisieren Sie eine leere Warteschlangendatenstruktur, um den Überblick über die zu besuchenden Knoten zu behalten.

2. Stellen Sie den Root-Knoten in die Warteschlange.

3. Geben Sie eine Schleife ein, bis die Warteschlange leer ist:

   1. Entfernen Sie den Knoten an der Spitze der Warteschlange.
   2. Verarbeiten Sie den aus der Warteschlange entfernten Knoten (z. B. besuchen Sie ihn oder führen Sie eine Operation daran aus).
   3. Stellen Sie alle untergeordneten Knoten des Knotens (falls vorhanden) in die Warteschlange.

4. Wiederholen Sie die Schritte 3a–3c , bis die Warteschlange leer ist.

5. Der BFS-Durchlauf ist abgeschlossen, wenn alle Knoten im Baum stufenweise von links nach rechts besucht wurden.

Im Wesentlichen untersucht BFS in einem Baum Knoten Ebene für Ebene , beginnend bei der Wurzel und zu den untergeordneten Knoten, bevor zur nächsten Ebene übergegangen wird. Dadurch wird sichergestellt, dass Knoten auf jeder Ebene besucht werden, bevor zur nächsten Ebene gewechselt wird. Dies macht es besonders nützlich für Aufgaben wie das Finden des kürzesten Pfads in einem ungewichteten Baum oder das Erkunden eines Baums Ebene für Ebene.

Unterschied zu BFS in einem Diagramm: Ähnlich wie DFS passt sich Diagramm-BFS an das Vorhandensein von Zyklen und mehreren Pfaden zwischen Knoten an. Es nutzt Mechanismen wie die Markierung besuchter Knoten und spezielle Beendigungsbedingungen, um effizient durch das komplexe Beziehungsnetzwerk innerhalb von Diagrammen zu navigieren.

Schlüsselindikatoren:

• Sie müssen einen Baum Ebene für Ebene durchlaufen.
• Probleme bestehen darin, den kürzesten Weg in ungewichteten Diagrammen zu finden.
• Sie möchten einen Baum oder ein Diagramm zunächst in der Breite untersuchen.

Vorlagencode:

Python

 from collections import deque def bfs(root): # Create a queue and initialize it with the root node queue = deque([root]) # Perform breadth-first search until the queue is empty while len(queue) > 0: # Dequeue the front node from the queue node = queue.popleft() # Process the current node for child in node.children: if is_goal(child): # If the goal condition is satisfied, return the child node return FOUND(child) # Enqueue the child node to explore it in the next iterations queue.append(child) # Return NOT_FOUND if the goal is not reached return NOT_FOUND

JS

 function bfs(root) { const queue = []; // Create a queue and initialize it with the root node queue.push(root); while (queue.length > 0) { // Perform breadth-first search until the queue is empty const node = queue.shift(); // Dequeue the front node from the queue for (const child of node.children) { // Process the current node if (isGoal(child)) { // If the goal condition is satisfied, return the child node return `FOUND ${child}`; } queue.push(child); // Enqueue the child node to explore it in the next iterations } } return 'NOT_FOUND'; // Return NOT_FOUND if the goal is not reached }

Java

 import java.util.LinkedList; import java.util.Queue; public String bfs(Node root) { Queue<Node> queue = new LinkedList<>(); // Create a queue and initialize it with the root node queue.offer(root); while (!queue.isEmpty()) { // Perform breadth-first search until the queue is empty Node node = queue.poll(); // Dequeue the front node from the queue for (Node child : node.getChildren()) { // Process the current node if (isGoal(child)) { // If the goal condition is satisfied, return the child node return "FOUND(child)"; } queue.offer(child); // Enqueue the child node to explore it in the next iterations } } return "NOT_FOUND"; // Return NOT_FOUND if the goal is not reached }

10. Unionsfindung (Disjunkte Union)

Die Union-Find- Datenstruktur, auch bekannt als Disjoint Set Union (DSU) , wird verwendet, um Probleme mit disjunkten Mengen oder verbundenen Komponenten effizient zu verwalten und zu lösen. Es bietet Operationen zum Zusammenführen von Mengen (Vereinigung) und zum Bestimmen der Menge, zu der ein Element gehört (Suchen). Union-Find wird häufig in Algorithmen wie Kruskals Minimum Spanning Tree und der Zykluserkennung in Diagrammen verwendet.

Union Find wird wie folgt implementiert:

1. Initialisierung: Beginnen Sie mit einer Sammlung von Elementen, die jeweils als separate disjunkte Menge betrachtet werden. Weisen Sie jeder Menge einen eindeutigen Vertreter (häufig das Element selbst) zu.
2. Union-Operation: Um zwei Mengen zusammenzuführen, führen Sie die Union-Operation aus. Wählen Sie den Vertreter einer Gruppe aus (häufig basierend auf bestimmten Kriterien wie Rang oder Größe) und machen Sie ihn zum übergeordneten Element des Vertreters der anderen Gruppe. Dadurch werden die beiden Sets effektiv miteinander verbunden.
3. Suchvorgang: Wenn Sie die Menge bestimmen müssen, zu der ein Element gehört, verwenden Sie den Suchvorgang. Beginnen Sie mit dem betreffenden Element und durchlaufen Sie den Baum nach oben, um den Wurzelknoten (Repräsentanten) seiner Menge zu finden. Die Pfadkomprimierungstechnik kann hier angewendet werden, um zukünftige Suchvorgänge zu optimieren, indem die Elemente entlang des Pfads direkt auf die Wurzel verweisen.
4. Zykluserkennung: Union-Find wird häufig zum Erkennen von Zyklen in Diagrammen verwendet. Wenn bei der Vereinigungsoperation beide Elemente zur gleichen Menge gehören (d. h. sie haben denselben Repräsentanten), deutet dies darauf hin, dass das Hinzufügen einer Kante zwischen Knoten einen Zyklus im Diagramm erzeugen würde.
5. Optimierung: Verschiedene Optimierungstechniken können angewendet werden, um die Effizienz von Union-Find-Operationen zu verbessern, z. B. Union nach Rang und Pfadkomprimierung.

Vorlagencode:

Python

 class UnionFind: def __init__(self): self.id = {} def find(self, x): y = self.id.get(x, x) if y != x: self.id[x] = y = self.find(y) return y def union(self, x, y): self.id[self.find(x)] = self.find(y)

JS

 class UnionFind { constructor() { this.id = {}; } /** * Find the root parent of an element in the set. * Implements path compression for better efficiency. * @param x The element to find the root parent for. * @returns The root parent of the element. */ find(x) { let y = this.id[x] || x; if (y !== x) { this.id[x] = y = this.find(y); } return y; } /** * Union two elements into the same set. * @param x The first element. * @param y The second element. */ union(x, y) { this.id[this.find(x)] = this.find(y); } }

Java

 import java.util.*; class UnionFind { private Map<String, String> id; public UnionFind() { id = new HashMap<>(); } /** * Find the root parent of an element in the set. * Implements path compression for better efficiency. * @param x The element to find the root parent for. * @return The root parent of the element. */ public String find(String x) { String y = id.getOrDefault(x, x); if (!y.equals(x)) { id.put(x, find(y)); } return y; } /** * Union two elements into the same set. * @param x The first element. * @param y The second element. */ public void union(String x, String y) { id.put(find(x), find(y)); } }

11. Topologische Sortierung

Ein gerichteter azyklischer Graph (DAG) ist ein gerichteter Graph ohne gerichtete Zyklen.

Topologische Sortierung ist ein Algorithmus zum Anordnen der Knoten eines gerichteten azyklischen Graphen ( DAG ) in einer linearen Reihenfolge, wobei jeder Knoten vor seinen Nachfolgern erscheint. Es ist von entscheidender Bedeutung für Aufgaben wie das Planen von Abhängigkeiten, das Kompilieren von Code und das Analysieren der Priorität von Aufgaben in verschiedenen Anwendungen.

Hier ist eine schrittweise Aufschlüsselung der topologischen Sortierung:

1. Initialisierung: Beginnen Sie mit einem gerichteten azyklischen Graphen ( DAG ), der Aufgaben oder Knoten mit Abhängigkeiten darstellt. Initialisieren Sie eine Warteschlange, um die sortierten Knoten aufzunehmen.

2. In-Grad-Berechnung: Berechnen Sie den In-Grad (die Anzahl der eingehenden Kanten) für jeden Knoten im Diagramm. Knoten mit einem In-Grad von 0 haben keine Abhängigkeiten und eignen sich als Ausgangspunkt der topologischen Sortierung.

3. Anfängliches Füllen der Warteschlange: Alle Knoten mit einem In-Grad von 0 werden in die Warteschlange gestellt. Diese Knoten können zuerst bearbeitet werden.

4. Topologische Sortierschleife: Führen Sie die folgenden Schritte aus, während die Warteschlange nicht leer ist:

   1. Entfernen Sie einen Knoten vom Anfang der Warteschlange.
   2. Verarbeiten Sie den Knoten (z. B. fügen Sie ihn der sortierten Liste hinzu).
   3. Dekrementieren Sie für jeden Nachbarn des Knotens (Knoten, auf den er zeigt) den In-Grad um 1.
   4. Wenn der In-Grad eines Nachbarn durch die Dekrementierung 0 wird, wird er in die Warteschlange eingereiht.

5. Abschluss: Sobald die topologische Sortierschleife abgeschlossen ist, ist die Warteschlange leer und die sortierte Liste enthält alle Knoten in einer gültigen topologischen Reihenfolge.

6. Zykluserkennung: Wenn zu irgendeinem Zeitpunkt während des topologischen Sortiervorgangs keine Knoten mit einem In-Grad von 0 in der Warteschlange mehr vorhanden sind, weist dies auf das Vorhandensein von Zyklen im Diagramm hin, wodurch eine topologische Sortierung unmöglich wird.

Das Ergebnis der topologischen Sortierung ist eine lineare Reihenfolge der Knoten, die ihre Abhängigkeiten berücksichtigt, wodurch sie sich für die Planung von Aufgaben oder die Analyse der Ausführungsreihenfolge in verschiedenen Anwendungen eignet.

Schlüsselindikatoren:

• Das Problem besteht darin, Aufgaben mit Abhängigkeiten zu planen oder anzuordnen.
• Sie arbeiten mit einem gerichteten azyklischen Graphen (DAG).
• Aufgaben müssen in einer bestimmten Reihenfolge und unter Einhaltung ihrer Abhängigkeiten ausgeführt werden.

Vorlagencode:

Python

 from collections import deque def find_indegree(graph): # Calculate the indegree of each node in the graph indegree = {node: 0 for node in graph} for node in graph: for neighbor in graph[node]: indegree[neighbor] += 1 return indegree def topological_sort(graph): result = [] queue = deque() indegree = find_indegree(graph) # Add nodes with 0 indegree to the queue for node in indegree: if indegree[node] == 0: queue.append(node) while queue: node = queue.popleft() result.append(node) # Update the indegree of neighboring nodes for neighbor in graph[node]: indegree[neighbor] -= 1 if indegree[neighbor] == 0: queue.append(neighbor) # If all nodes are visited, return the result if len(graph) == len(result): return result else: return None

JS

 /** * Finds the indegree of each node in the graph. * @param {object} graph - The input graph. * @returns {object} - The indegree of each node. */ function findIndegree(graph) { const indegree = {}; for (const node in graph) { indegree[node] = 0; } for (const node in graph) { for (const neighbor of graph[node]) { indegree[neighbor]++; } } return indegree; } /** * Performs topological sorting on the given graph. * @param {object} graph - The input graph. * @returns {array|null} - The sorted nodes in topological order or null if a cycle is detected. */ function topologicalSort(graph) { const result = []; const queue = []; const indegree = findIndegree(graph); // Add nodes with no incoming edges to the queue for (const node in indegree) { if (indegree[node] === 0) { queue.push(node); } } while (queue.length > 0) { const node = queue.shift(); result.push(node); // Decrement the indegree of neighbors and enqueue if indegree becomes zero for (const neighbor of graph[node]) { indegree[neighbor]--; if (indegree[neighbor] === 0) { queue.push(neighbor); } } } // Check if all nodes have been visited (no cycles) if (Object.keys(graph).length === result.length) { return result; } else { return null; } }

Java

 import java.util.*; /** * Finds the indegree of each node in the graph. * @param graph - The input graph. * @return The indegree of each node. */ public Map<String, Integer> findIndegree(Map<String, List<String>> graph) { Map<String, Integer> indegree = new HashMap<>(); for (String node : graph.keySet()) { indegree.put(node, 0); } for (String node : graph.keySet()) { for (String neighbor : graph.get(node)) { indegree.put(neighbor, indegree.getOrDefault(neighbor, 0) + 1); } } return indegree; } /** * Performs topological sorting on the given graph. * @param graph - The input graph. * @return The sorted nodes in topological order or null if a cycle is detected. */ public List<String> topologicalSort(Map<String, List<String>> graph) { List<String> result = new ArrayList<>(); Queue<String> queue = new LinkedList<>(); Map<String, Integer> indegree = findIndegree(graph); // Add nodes with no incoming edges to the queue for (String node : indegree.keySet()) { if (indegree.get(node) == 0) { queue.offer(node); } } while (!queue.isEmpty()) { String node = queue.poll(); result.add(node); // Decrement the indegree of neighbors and enqueue if indegree becomes zero for (String neighbor : graph.get(node)) { indegree.put(neighbor, indegree.get(neighbor) - 1); if (indegree.get(neighbor) == 0) { queue.offer(neighbor); } } } // Check if all nodes have been visited (no cycles) if (graph.size() == result.size()) { return result; } else { return null; } }

12. Versuche (Präfixbaum)

Ein Trie ist eine baumartige Datenstruktur, die für den effizienten String-Abgleich und die Speicherung von Wörtern verwendet wird. Es eignet sich hervorragend für Probleme, bei denen Sie Zeichenfolgen mit gemeinsamen Präfixen speichern und suchen müssen.

So implementieren Sie einen Trie:

1. Initialisierung: Beginnen Sie mit einem leeren Trie, der normalerweise aus einem Wurzelknoten ohne zugehöriges Zeichen besteht.

2. Einfügen: Um ein Wort in den Trie einzufügen, beginnen Sie am Wurzelknoten und durchlaufen Sie den Baum zeichenweise nach unten. Für jedes Zeichen im Wort:

   1. Überprüfen Sie, ob unter dem aktuellen Knoten ein untergeordneter Knoten mit diesem Zeichen vorhanden ist.
   2. Wenn dies der Fall ist, wechseln Sie zum untergeordneten Knoten.
   3. Wenn nicht, erstellen Sie einen neuen untergeordneten Knoten mit dem Charakter und verschieben Sie ihn dorthin.

3. Wortvervollständigung: Um zu überprüfen, ob ein Wort im Trie vorhanden ist, durchlaufen Sie es auf ähnliche Weise wie beim Einfügen. Stellen Sie sicher, dass jedes Zeichen im Wort einem untergeordneten Knoten des aktuellen Knotens entspricht. Wenn der Durchlauf das Ende des Wortes erreicht und am letzten Zeichenknoten eine gültige Endmarkierung (z. B. ein boolesches Flag) vorhanden ist, existiert das Wort im Trie.

4. Präfixsuche: Trie zeichnet sich durch die Präfixsuche aus. Um alle Wörter mit einem bestimmten Präfix zu finden, beginnen Sie die Durchquerung am Wurzelknoten und bewegen Sie sich entlang der Baumstruktur nach unten, indem Sie den Zeichen des Präfixes folgen. Sobald Sie das letzte Zeichen des Präfixes erreicht haben, können Sie von diesem Knoten aus eine Tiefensuche (DFS) durchführen, um alle Wörter zu finden, die dasselbe Präfix haben.

5. Löschen: Um ein Wort aus dem Trie zu löschen, führen Sie eine Suche nach dem Wort durch. Wenn Sie das Ende des Wortes erreicht haben, entfernen Sie die Endmarkierung (falls vorhanden). Wenn der Knoten keine anderen untergeordneten Knoten hat, können Sie den gesamten Zweig des Trie, der das Wort darstellt, sicher entfernen.

Versuche können speicherintensiv sein, insbesondere bei großen Vokabularien. Um den Speicher zu optimieren, können Techniken wie Komprimierung (z. B. Verwendung einer Karte anstelle eines Zeichenarrays in jedem Knoten) und Bereinigung (Entfernen von Knoten ohne Nachkommen) angewendet werden.

Versuche sind besonders nützlich für den effizienten String-Abgleich, Vorschläge zur automatischen Vervollständigung, Rechtschreibprüfung und die Indizierung von Wörtern mit gemeinsamen Präfixen. Sie bieten eine schnelle und platzsparende Möglichkeit, Wörter oder Zeichenfolgen mit gemeinsamen Präfixen in einer baumartigen Struktur zu speichern und zu suchen.

Schlüsselindikatoren:

• Sie haben es mit Strings zu tun und benötigen einen effizienten String-Matching.
• Zu den Problemen gehören Autovervollständigungsvorschläge, Rechtschreibprüfungen oder die Suche nach Wörtern mit gemeinsamen Präfixen.
• Sie möchten Wörter effizient speichern und suchen.

Vorlagencode:

Python

 class TrieNode: def __init__(self, value): self.value = value self.children = {} def insert(self, s, idx): # idx: index of the current character in s if idx != len(s): self.children.setdefault(s[idx], TrieNode(s[idx])) self.children.get(s[idx]).insert(s, idx + 1)

JS

 class TrieNode { constructor(value) { this.value = value; this.children = {}; } insert(s, idx) { // idx: index of the current character in s if (idx !== s.length) { if (!this.children[s[idx]]) { this.children[s[idx]] = new TrieNode(s[idx]); } this.children[s[idx]].insert(s, idx + 1); } } }

Java

 import java.util.*; class TrieNode { char value; Map<Character, TrieNode> children; TrieNode(char value) { this.value = value; this.children = new HashMap<>(); } void insert(String s, int idx) { // idx: index of the current character in s if (idx != s.length()) { char c = s.charAt(idx); if (!children.containsKey(c)) { children.put(c, new TrieNode(c)); } children.get(c).insert(s, idx + 1); } } }

13. Dynamische Programmierung

Dynamische Programmierung ist eine leistungsstarke Problemlösungstechnik, die in der Informatik und Mathematik zur effizienten Lösung einer Vielzahl komplexer Probleme eingesetzt wird. Besonders wertvoll ist es, wenn ein Problem in einfachere Teilprobleme zerlegt werden kann und die Lösungen dieser Teilprobleme zur Lösung des Gesamtproblems kombiniert werden können.

Hier sind seine Hauptmerkmale und seine Funktionsweise:

Optimaler Unterbau:

• Dieses Merkmal bezieht sich auf die Eigenschaft, dass eine optimale Lösung für ein größeres Problem aus optimalen Lösungen für seine kleineren Teilprobleme konstruiert werden kann.
• Mit anderen Worten: DP-Probleme weisen eine rekursive Struktur auf, bei der die optimale Lösung für ein Problem auf den optimalen Lösungen seiner Teilprobleme beruht.
• Wenn Sie beispielsweise den kürzesten Weg zwischen zwei Punkten in einem Diagramm finden, sollte auch der kürzeste Weg zwischen zwei beliebigen Zwischenpunkten optimal sein.

Überlappende Teilprobleme:

• Überlappende Teilprobleme treten auf, wenn dieselben Teilprobleme während der Berechnung mehrmals gelöst werden, was zu redundanter Arbeit führt.
• Die dynamische Programmierung zielt darauf ab, dieses Problem zu lösen, indem die Lösungen für Teilprobleme in einer Datenstruktur (häufig einer Tabelle oder einem Memoization-Array) gespeichert werden, um eine Neuberechnung zu vermeiden.
• Durch diese Speicherung und Wiederverwendung von Teilproblemlösungen wird die zeitliche Komplexität des Algorithmus erheblich reduziert.

So funktioniert dynamische Programmierung:

1. Teilprobleme identifizieren: Der erste Schritt bei der Lösung eines Problems mithilfe von DP besteht darin, die Teilprobleme zu identifizieren. Teilen Sie das Problem in kleinere, überschaubare Teilprobleme auf, die, wenn sie gelöst werden, zur Lösung des Hauptproblems beitragen.
2. Rekursive Lösung: Entwickeln Sie eine rekursive Lösung, die die Lösung eines größeren Problems in Form von Lösungen für kleinere Teilprobleme ausdrückt. Diese rekursive Formulierung erfasst die optimale Unterstruktur.
3. Auswendiglernen oder Tabellieren: Um überlappende Teilprobleme anzugehen, können Sie zwischen zwei gängigen Techniken wählen:
   • Memoisierung: Speichern Sie die Ergebnisse von Teilproblemen in einer Datenstruktur (normalerweise einem Array oder einer Hash-Tabelle), während sie berechnet werden. Wenn ein Teilproblem erneut auftritt, rufen Sie dessen Lösung aus dem Speicher ab, anstatt sie neu zu berechnen. Dies wird auch als Top-Down -Ansatz bezeichnet.
   • Tabellierung: Erstellen Sie eine Tabelle (häufig ein 2D-Array), um Lösungen für Teilprobleme von unten nach oben zu speichern. Beginnen Sie mit der Lösung der kleinsten Teilprobleme und steigern Sie sich schrittweise zum Hauptproblem.
4. Optimale Lösung: Sobald alle Teilprobleme gelöst sind, kann die Lösung des Hauptproblems durch Kombinieren der Lösungen seiner Teilprobleme gemäß der rekursiven Struktur des Problems erhalten werden.

Dynamische Programmierung wird auf eine Vielzahl von Problemen angewendet, darunter das Finden der kürzesten Pfade in Diagrammen, das Optimieren der Ressourcenzuweisung, das Zählen von Kombinationen, das Lösen von Rucksackproblemen und vieles mehr. Seine Fähigkeit, Lösungen zu optimieren, indem komplexe Probleme in einfachere Teile zerlegt und redundante Berechnungen vermieden werden, macht es zu einer grundlegenden Technik beim Entwurf und der Optimierung von Algorithmen.

Wichtige Konzepte: Bottoms-Up-Ansatz, Top-Down, Auswendiglernen, Tabellierung

Schlüsselindikatoren:

• Das Problem kann in kleinere, überlappende Teilprobleme zerlegt werden.
• Es besteht Optimierungsbedarf durch Speicherung und Wiederverwendung von Lösungen für Teilprobleme.
• Sie möchten Optimierungs- oder Zählprobleme lösen.

Vorlagencode:

Eine Vorlage für die Top-Down-Memoisierung ist eine von vielen Möglichkeiten, dynamische Programmierung zu implementieren.

Python

 def top_down_memo(arr): def dp(state): # Base case(s): Define your own base case(s) for the problem if base_case: return 0 # Check if the state has already been memoized if state in memo: return memo[state] # Calculate the result using recurrence relation and memoize it result = recurrence_relation(state) memo[state] = result return result memo = {} # Memoization table to store calculated results return dp(initial_state)

JS

 function topDownMemo(arr) { function dp(state) { // Base case(s): Define your own base case(s) for the problem if (baseCase) { return 0; } // Check if the state has already been memoized if (memo.has(state)) { return memo.get(state); } // Calculate the result using recurrence relation and memoize it const result = recurrenceRelation(state); memo.set(state, result); return result; } const memo = new Map(); // Memoization map to store calculated results return dp(initialState); }

Java

 import java.util.HashMap; import java.util.Map; public int topDownMemo(int[] arr) { Map<StateType, Integer> memo = new HashMap<>(); // Memoization map to store calculated results return dp(initialState, memo); } private int dp(StateType state, Map<StateType, Integer> memo) { // Base case(s): Define your own base case(s) for the problem if (baseCase) { return 0; } // Check if the state has already been memoized if (memo.containsKey(state)) { return memo.get(state); } // Calculate the result using recurrence relation and memoize it int result = recurrenceRelation(state); memo.put(state, result); return result; }

14. Zurückverfolgen

Backtracking ist eine allgemeine algorithmische Technik zur schrittweisen Lösung von Problemen, indem verschiedene Möglichkeiten ausprobiert und rückgängig gemacht werden, wenn sie nicht zu einer Lösung führen. Es wird verwendet, wenn eine umfassende Suche erforderlich ist.

Hier finden Sie einen detaillierten Einblick in die Funktionsweise von Backtracking:

1. Problemraumerkundung: Beim Backtracking wird der Problemraum erkundet, indem schrittweise und Stück für Stück eine Lösung erstellt wird. Bei jedem Schritt trifft es eine Entscheidung und geht voran.
2. Rekursive Struktur: Backtracking beinhaltet oft eine Rekursion. Es beginnt mit einer ersten Teillösung und erkundet alle möglichen Erweiterungsmöglichkeiten. Dieser Prozess wird rekursiv fortgesetzt, bis eine vollständige Lösung gefunden wird oder offensichtlich wird, dass keine gültige Lösung existiert.
3. Entscheidungspunkte: Bei jedem Schritt gibt es Entscheidungspunkte, an denen der Algorithmus aus den verfügbaren Optionen auswählen muss. Diese Entscheidungen führen zu einer Verzweigung im Explorationsprozess.
4. Lösungsvalidierung: Nach der Auswahl prüft der Algorithmus, ob die aktuelle Teillösung gültig ist. Wenn es gültig ist, fährt der Algorithmus mit dem nächsten Schritt fort. Wenn nicht, wird ein Rückschritt durchgeführt, die vorherige Auswahl rückgängig gemacht und andere Optionen geprüft.
5. Beendigungsbedingungen: Das Backtracking wird fortgesetzt, bis eine von zwei Bedingungen erfüllt ist:
   • Es wird eine gültige Lösung gefunden. In diesem Fall stoppt der Algorithmus und gibt die Lösung zurück.
   • Es wird festgestellt, dass keine gültige Lösung existiert. An diesem Punkt kehrt der Algorithmus zu einem vorherigen Entscheidungspunkt zurück und prüft verschiedene Optionen.
6. Pruning: Um die Suche zu optimieren, beinhaltet das Backtracking oft Pruning-Strategien. Beim Pruning wird die Erkundung von Pfaden vermieden, die garantiert zu ungültigen Lösungen führen, wodurch der Suchraum erheblich reduziert wird.

Anwendungen von Backtracking:

Backtracking wird in verschiedenen Problembereichen eingesetzt, darunter:

• Lösen von Rätseln wie Sudoku und N-Queens.
• Generieren von Permutationen und Kombinationen.
• Suche nach Pfaden in Diagrammen und Bäumen.
• Probleme mit der Zufriedenheit mit Einschränkungen (z. B. das Problem des Handlungsreisenden).
• Spielalgorithmen (z. B. Schach-KI).

Schlüsselindikatoren:

• Das Problem besteht darin, mehrere Möglichkeiten schrittweise zu erkunden.
• Es gibt Entscheidungspunkte oder Einschränkungen, die das Ausprobieren verschiedener Optionen erforderlich machen.
• Sie müssen alle möglichen Lösungen finden oder durch eine umfassende Suche bestimmte Bedingungen erfüllen.

Vorlagencode:

Python

 def backtrack(curr, OTHER_ARGUMENTS...): if BASE_CASE: # Modify the answer according to the problem's requirements return ans = 0 for ITERATE_OVER_INPUT: # Modify the current state according to the problem's requirements ans += backtrack(curr, OTHER_ARGUMENTS...) # Undo the modification of the current state (backtrack) return ans

JS

 function backtrack(curr, ...OTHER_ARGUMENTS) { if (BASE_CASE) { // Modify the answer according to the problem's requirements return; } let ans = 0; for (let i = 0; i < ITERATE_OVER_INPUT.length; i++) { const item = ITERATE_OVER_INPUT[i]; // Modify the current state according to the problem's requirements ans += backtrack(curr, ...OTHER_ARGUMENTS); // Undo the modification of the current state (backtrack) } return ans; }

Java

 public int backtrack(StateType curr, OtherArgumentType... OTHER_ARGUMENTS) { if (BASE_CASE) { // Modify the answer according to the problem's requirements return; } int ans = 0; for (int i = 0; i < ITERATE_OVER_INPUT.length; i++) { ItemType item = ITERATE_OVER_INPUT[i]; // Modify the current state according to the problem's requirements ans += backtrack(curr, OTHER_ARGUMENTS); // Undo the modification of the current state (backtrack) } return ans; }

15. Intervalle zusammenführen

Beim Zusammenführen von Intervallen werden überlappende oder benachbarte Intervalle zu einem konsolidierten Satz zusammengefasst. Dies wird häufig bei Problemen mit Zeitintervallen oder der Planung verwendet. Es vereinfacht intervallbasierte Vorgänge.

Hier sehen Sie genauer, wie das Zusammenführen von Intervallen funktioniert:

1. Intervalldarstellung: Intervalle werden normalerweise als Paare von Start- und Endpunkten dargestellt (z. B. [Start, Ende] ).
2. Sortieren: Um Intervalle effizient zusammenzuführen, sortieren Sie sie zunächst nach ihren Startpunkten. Dadurch wird sichergestellt, dass überlappende oder benachbarte Intervalle in der sortierten Liste nebeneinander liegen.
3. Zusammenführungsprozess: Initialisieren Sie eine leere Liste, um die zusammengeführten Intervalle aufzunehmen. Dann durchlaufen Sie die sortierten Intervalle nacheinander:
   • Wenn sich das aktuelle Intervall nicht mit dem vorherigen überschneidet, fügen Sie es der Liste der zusammengeführten Intervalle hinzu.
   • Wenn es eine Überlappung gibt, aktualisieren Sie den Endpunkt des vorherigen zusammengeführten Intervalls, um sowohl das aktuelle als auch das vorherige Intervall zu umfassen und sie effektiv zusammenzuführen.
4. Abschluss: Nach der Verarbeitung aller Intervalle enthält die Liste der zusammengeführten Intervalle nicht überlappende und konsolidierte Intervalle.

Anwendungen von Zusammenführungsintervallen:

Zusammenführungsintervalle werden häufig verwendet in:

• Planungs- und Zeitmanagementanwendungen.
• Erkennung überlappender Ereignisse in Kalendersystemen.
• Intervallbasierte Datenanalyse, beispielsweise bei Datenbankabfragen.
• Lösen von Problemen im Zusammenhang mit der Ressourcenzuweisung und der Besprechungsplanung.

Durch die Zusammenführung überlappender Intervalle vereinfacht diese Technik intervallbasierte Vorgänge und steigert die Effizienz in verschiedenen Anwendungen.

Schlüsselindikatoren:

• Sie haben es mit Intervallen oder zeitbasierten Daten zu tun.
• Probleme bestehen darin, überlappende oder benachbarte Intervalle zusammenzuführen.
• Sie möchten intervallbasierte Vorgänge vereinfachen oder die Ereignisplanung optimieren.

Vorlagencode:

Python

 def merge_intervals(intervals): # 1. Sort the intervals based on their start values. intervals.sort(key=lambda x: x[0]) # 2. Initialize an empty list to store merged intervals. merged_intervals = [] # 3. Iterate through the sorted intervals. for interval in intervals: # 4. If the merged_intervals list is empty or the current interval does not overlap with the last merged interval: if not merged_intervals or interval[0] > merged_intervals[-1][1]: merged_intervals.append(interval) else: # 5. If the current interval overlaps with the last merged interval, merge them. merged_intervals[-1][1] = max(merged_intervals[-1][1], interval[1]) # 6. Return the merged_intervals list. return merged_intervals

JS

 function mergeIntervals(intervals) { // 1. Sort the intervals based on their start values. intervals.sort((a, b) => a[0] - b[0]); // 2. Initialize an empty array to store merged intervals. const mergedIntervals = []; // 3. Iterate through the sorted intervals. for (const interval of intervals) { // 4. If the mergedIntervals array is empty or the current interval does not overlap with the last merged interval: if (mergedIntervals.length === 0 || interval[0] > mergedIntervals[mergedIntervals.length - 1][1]) { mergedIntervals.push(interval); } else { // 5. If the current interval overlaps with the last merged interval, merge them. mergedIntervals[mergedIntervals.length - 1][1] = Math.max(mergedIntervals[mergedIntervals.length - 1][1], interval[1]); } } // 6. Return the mergedIntervals array. return mergedIntervals; }

Java

 public class MergeIntervals { public int[][] merge(int[][] intervals) { // 1. Sort the intervals based on their start values. Arrays.sort(intervals, (a, b) -> a[0] - b[0]); // 2. Create a list to store merged intervals. List<int[]> mergedIntervals = new ArrayList<>(); // 3. Iterate through the sorted intervals. for (int[] interval : intervals) { // 4. If the mergedIntervals list is empty or the current interval does not overlap with the last merged interval: if (mergedIntervals.isEmpty() || interval[0] > mergedIntervals.get(mergedIntervals.size() - 1)[1]) { mergedIntervals.add(interval); } else { // 5. If the current interval overlaps with the last merged interval, merge them. mergedIntervals.get(mergedIntervals.size() - 1)[1] = Math.max(mergedIntervals.get(mergedIntervals.size() - 1)[1], interval[1]); } } // 6. Convert the list to an array and return it. return mergedIntervals.toArray(new int[mergedIntervals.size()][]); } }

Möchten Sie mehr erfahren?

Wenn Sie mehr über diese Muster erfahren möchten und erfahren möchten, wie Sie sie bei Ihrem nächsten Coding-Interview effektiver umsetzen können, dann schauen Sie sich noch heute techinterviews.io an! Wir bieten einen umfassenden Lehrplan, um Sie auf Ihr nächstes Programmiergespräch vorzubereiten und Themen wie Datenstrukturen , Algorithmen , Verhaltensinterviews und sogar Gehaltsverhandlungen abzudecken. Wir haben sogar einen integrierten Codierungsarbeitsbereich, in dem Sie üben können.

Verbessern Sie Ihre Vorbereitung auf Programmiergespräche noch heute mit unserem Aktionscode TECH30 für 30 $ Rabatt!