Das Coding-Interview knacken: Teil des Sliding-Window-Musters

In diesem zweiten Teil unserer Serie tauchen wir in eines der vielseitigsten Muster zur Lösung von Codierungsinterviewfragen ein: das Sliding Window. Diese Technik ist unglaublich nützlich für die Optimierung von Problemen, die Subarrays oder Teilstrings zusammenhängender Elemente betreffen, wie etwa das Maximieren von Summen, das Finden spezifischer Bedingungen innerhalb einer Sequenz oder das Arbeiten mit Teilstrings in Strings.

Bevor wir beginnen: Wenn Sie auf der Suche nach einem umfassenden Leitfaden zur Vorbereitung auf Coding-Interviews sind, schauen Sie sich „Cracking the Coding Interview“ an, ein unverzichtbares Buch für jeden, der ernsthaft einen Job bei führenden Technologieunternehmen anstrebt.

Überblick über das Schiebefenstermuster

Das Sliding Window-Muster ist eine Technik, mit der Sie Probleme effizient lösen können, bei denen Sie eine Teilmenge von Daten aus einem größeren Datensatz berücksichtigen müssen (z. B. ein Unterarray eines Arrays oder eine Teilzeichenfolge einer Zeichenfolge). Anstatt die Teilmenge jedes Mal neu zu berechnen, wenn Sie das Fenster verschieben, verwaltet diese Technik eine laufende Summe oder Bedingung und gleitet über die Daten, um unnötige Arbeit zu minimieren.

Wann man Schiebefenster verwendet:

• Das Problem betrifft zusammenhängende Subarrays oder Teilstrings.
• Sie müssen die maximale oder minimale Summe, Anzahl oder andere Bedingungen innerhalb eines gleitenden Bereichs des Datensatzes finden.
• Es handelt sich um eine feste Fenstergröße oder es ist ein dynamisches Fenster erforderlich, das erweitert oder verkleinert wird.

---

Arten von Schiebefenster-Ansätzen

1. Schiebefenster mit fester Größe

• Was es ist: Ein Fenster mit fester Größe, das über das Array oder die Zeichenfolge gleitet und dabei eine laufende Bedingung wie Summe oder Produkt beibehält.
• Beispiel: Finden Sie die maximale Summe eines Unterarrays der Größe k.

Beispielproblem: Finden Sie bei einem gegebenen Array von ganzen Zahlen und einer Zahl k die maximale Summe eines beliebigen Unterarrays der Größe k.

def max_sum_subarray(arr, k):
    # Initialize variables to store the maximum sum and the current window sum.
    max_sum = 0
    window_sum = 0

    # First, calculate the sum of the initial window (first 'k' elements).
    for i in range(k):
        window_sum += arr[i]

    # Set the max_sum to the initial window's sum.
    max_sum = window_sum

    # Now, slide the window across the array. 
    # Start from the kth element and move until the end of the array.
    for i in range(k, len(arr)):
        # Slide the window by subtracting the element that is no longer in the window 
        # (arr[i - k]) and adding the new element (arr[i]).
        window_sum += arr[i] - arr[i - k]

        # Update max_sum if the current window sum is greater than the previous max_sum.
        max_sum = max(max_sum, window_sum)

    # Return the maximum sum found.
    return max_sum

Erklärung:

• Ein Fenster der Größe k wird initialisiert.
• Wenn sich das Fenster über das Array bewegt, wird der Gleiteffekt dadurch erreicht, dass das Element, das sich nicht mehr im Fenster befindet, subtrahiert und das neue Element hinzugefügt wird, das in das Fenster eintritt.
• Dies optimiert das Problem von einem Brute-Force-Ansatz von O(n*k) zu O(n), da wir nicht mehr das gesamte Fenster für jede Iteration aufsummieren müssen.

---

2. Dynamisches Schiebefenster

• Was es ist: Dies wird verwendet, wenn die Fenstergröße nicht festgelegt ist. Das Fenster erweitert oder verkleinert sich je nach den Anforderungen des Problems (z. B. der Erfüllung einer Summe oder Bedingung).
• Beispiel: Finden Sie das kleinste Subarray mit einer Summe größer oder gleich S.

Beispielproblem: Finden Sie bei einem gegebenen Array von ganzen Zahlen und einer Zahl S das kleinste zusammenhängende Unterarray, dessen Summe größer oder gleich S ist.

  def smallest_subarray_with_sum(arr, S):
    # Initialize variables:
    # window_sum: to store the sum of the current window.
    # min_length: to store the length of the smallest subarray found.
    # window_start: the starting index of the sliding window.
    window_sum = 0
    min_length = float('inf')  # Start with a large number to compare minimum lengths.
    window_start = 0

    # Iterate over the array with window_end being the right boundary of the window.
    for window_end in range(len(arr)):
        # Add the current element to the window_sum.
        window_sum += arr[window_end]

        # While the current window's sum is greater than or equal to S:
        while window_sum >= S:
            # Calculate the current window size and update min_length if smaller.
            min_length = min(min_length, window_end - window_start + 1)

            # Shrink the window from the left by removing the element at window_start.
            window_sum -= arr[window_start]

            # Move the start of the window to the right.
            window_start += 1

    # If min_length was updated, return it; otherwise, return 0 (meaning no valid subarray was found).
    return min_length if min_length != float('inf') else 0

Erklärung:

• Das Fenster wird durch Erhöhen von window_end erweitert, bis die Summe S überschreitet oder diesem entspricht.
• Sobald die Bedingung erfüllt ist, beginnt sich das Fenster von links zu verkleinern (window_start), um die minimale Subarray-Größe zu ermitteln.
• Dieser Ansatz ist effizient, da er das Problem von O(n^2) auf O(n) reduziert, indem Neuberechnungen vermieden werden.

---

Schritte zur Implementierung von Schiebefensterlösungen

1. Definieren Sie die Fenstergrenzen: Sie müssen den Anfang und das Ende des Fensters definieren.

2. Legen Sie eine Anfangsbedingung fest: Initialisieren Sie bei festen Fenstern die Summe/das Produkt/die Bedingung für das erste Fenster. Bei dynamischen Fenstern hängt der Anfangszustand vom Ziel des Problems ab.

3. Fenster schieben:

   • Für feste Fenstergröße: Verschieben Sie das Fenster, indem Sie das nächste Element hinzufügen und das Element entfernen, das sich nicht mehr im Fenster befindet.
   • Für dynamische Fenster: Erweitern oder verkleinern Sie das Fenster basierend auf der Bedingung, die Sie erfüllen möchten.

4. Ergebnisse prüfen und aktualisieren: Aktualisieren Sie nach jeder Fensterbewegung das Ergebnis (z. B. maximale Summe, minimale Länge usw.) nach Bedarf.

---

Häufige Fragen im Vorstellungsgespräch mit Sliding Window

1. Längste Teilzeichenfolge ohne sich wiederholende Zeichen

   • Problem: Ermitteln Sie bei gegebener Zeichenfolge s die Länge der längsten Teilzeichenfolge ohne sich wiederholende Zeichen.
   • Muster: Verwenden Sie ein dynamisches Schiebefenster, um es zu erweitern, bis ein doppeltes Zeichen gefunden wird, und verkleinern Sie dann das Fenster, bis die Bedingung erfüllt ist.

2. Maximalsummen-Subarray der Größe K

   • 問題：給定一個整數數組和一個整數 k，找出任何大小為 k 的子數組的最大和。
   • 模式：使用固定大小的滑動視窗來維護 k 個元素的總和，並在陣列上滑動視窗時更新最大總和。

3. 給定總和的最小子數組

   • 問題：給定一個正整數數組和一個數字S，求其總和大於或等於S的最小連續子數組的長度。
   • 模式：使用動態滑動窗口，擴展以找到有效的子數組並收縮以最小化其長度。

---

面試的滑動視窗技巧

1. 考慮視窗邊界：先考慮視窗應該從哪裡開始和結束。這可以幫助您確定正在使用的確切範圍。

2. 對動態視窗使用雜湊圖或集合：處理子字串或唯一元素時，使用集合來追蹤視窗中的元素。

3. 從暴力開始，然後優化：在某些問題中，從暴力方法開始（例如檢查每個可能的子數組）可以幫助您想像滑動視窗如何減少不必要的工作。

4. 尋找最佳條件：如果問題具有最佳化成分（例如最小化或最大化總和或長度），則滑動視窗可能是一個不錯的選擇。

---

結論

滑動視窗模式是解決許多編碼面試問題的強大工具，尤其是涉及陣列或字串等序列的問題。透過掌握固定大小和動態滑動窗口，您可以更有效地解決各種問題。

在下一篇文章中，我們將探討雙指標技術，這是另一種高效的策略，通常在涉及元素之間配對或比較的問題中補充滑動視窗方法。

敬請期待第三部！

Das obige ist der detaillierte Inhalt vonDas Coding-Interview knacken: Teil des Sliding-Window-Musters. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!