„Talk with You', Serie Nr. 2

Einführung

Heute beginnen wir mit unserem Überblick über Konzepte, die zur Lösung verschiedener algorithmischer Probleme verwendet werden. Das Verständnis eines bestimmten Konzepts könnte Ihnen eine Vorstellung davon geben, aus welchem ​​Blickwinkel Sie über die mögliche Lösung nachdenken sollten.

Es gibt verschiedene, aber nicht allzu viele Konzepte. Heute werde ich Ihre Aufmerksamkeit dem Schiebefensterkonzept widmen.

Schiebefenster

Das Konzept des Schiebefensters ist etwas komplizierter als auf den ersten Blick. Das werde ich anhand praktischer Beispiele demonstrieren. Denken Sie vorerst daran, dass die konzeptionelle Idee darin besteht, dass wir ein Fenster haben, das wir verschieben müssen. Beginnen wir gleich mit dem Beispiel.

Angenommen, Sie haben ein Array von Ganzzahlen und eine vordefinierte Größe der Unterarrays. Sie werden gebeten, ein solches Unterarray (auch Fenster genannt) zu finden, dessen Summe der Werte unter anderem maximal wäre.

array = [1, 2, 3]
window_size = 2

# conceptually
subarray_1 = [1, 2] --> sum 3
subarray_2 = [2, 3] --> sum 5

maximum_sum = 5

Na ja, sieht ganz einfach aus:
(1) Schiebefenster der Größe 2
(2) 2 Unterarrays
(3) Zählen Sie die Summe jedes
(4) Finden Sie das Maximum zwischen ihnen

Lasst es uns umsetzen.

def foo(array: List[int], size: int) -> int:
    maximum = float("-inf")

    for idx in range(size, len(array)+1):
        left, right = idx-size, idx
        window = array[left:right]
        maximum = max(maximum, sum(window))

    return maximum 

Nun, es scheint, dass wir das Konzept des Schiebefensters gerade effizient genutzt haben. Eigentlich nicht ganz. Wir könnten einen „Beweis“ dafür erhalten, indem wir die zeitliche Komplexität der Lösung verstehen.

Die Komplexität beträgt O(l)*O(w), wobei l die Anzahl der Fenster im Array und w die Anzahl der Elemente im Fenster ist. Mit anderen Worten, wir müssen l Fenster durchlaufen und für jedes l-te Fenster die Summe von w Elementen berechnen.

Was ist hier fragwürdig? Lassen Sie uns die Iterationen zur Beantwortung der Frage konzeptionell darstellen.

array = [1, 2, 3, 4]
window_size = 3

iterations
1 2 3 4 5
|___|
  |___|
    |___|  

Die Antwort ist, dass wir, obwohl wir das Array verschieben, bei jeder Iteration k-1 Elemente „neu berechnen“ müssen, die bereits bei der vorherigen Iteration berechnet wurden.

Grundsätzlich sollte uns diese Erkenntnis dazu veranlassen, eine Frage zu stellen:

"Gibt es eine Möglichkeit, die Berechnungen aus dem vorherigen Schritt zu nutzen?"

Die Antwort ist ja. Wir können die Summe der Elemente des Fensters erhalten, indem wir das erste und das übernächste Element nach den Fensterelementen addieren und subtrahieren. Lassen Sie mich diese Idee in den Code integrieren.

def foo(array: List[int] = None, size: int = 0) -> int
    window_start, max_, window_sum_ = 0, float("-inf"), 0
    for window_end in range(len(array)):
        if window_end > size - 1:
            window_sum_ -= array[window_start]
            window_start += 1
        window_sum_ += array[window_end]
        max_ = max(max_, window_sum_)
    return max_

assert foo(array=[1, 2, 3, 4], size=3) == 9

Hier können wir sehen, dass wir an dem Punkt, an dem wir das Subarray der Länge der Größe erstellt haben, damit begonnen haben, das allererste Element von der Fenstersumme zu subtrahieren, was es uns ermöglicht, Berechnungen aus dem vorherigen Schritt wiederzuverwenden.

Nun können wir sagen, dass wir das Konzept des Schiebefensters effizient genutzt haben, während wir einen Beweis erhalten haben, der die Zeitkomplexität überprüft, die von O(l*w) auf O(l) reduziert wurde, wobei l die Anzahl der Fenster ist, die wir verwenden werden Folie.

Die Hauptidee, die ich hervorheben möchte, das Schiebefensterkonzept, besteht nicht nur darin, das Iterierbare mit dem Fenster einer bestimmten Größe zu zerlegen.

Lassen Sie mich Ihnen einige Probleme nennen, bei denen wir lernen, wie Sie das Problem erkennen können, das möglicherweise ein Schiebefensterkonzept betrifft, und was genau Sie mit dem Fenster selbst tun könnten.

Problemübersicht

Da ich hier nur über Konzepte spreche, würde ich „wie man etwas innerhalb des Fensters zählt“ überspringen.

Problem eins

Ermitteln Sie bei einem gegebenen Array den Durchschnitt aller angrenzenden Unterarrays der Größe K darin.

1. Schiebefenster? - contiguous subarrays das erste Schlüsselwort, was bedeutet, dass wir uns um Fenster kümmern sollten, die ein oder mehrere zusammenhängende Subarrays darstellen würden.
2. Kennen wir die Größe des Schiebefensters? - Ja, K, wir haben die Größe des Fensters, die der Länge von K entsprechen sollte.
3. Was genau sollen wir im Schiebefenster verwalten/überprüfen? - Finden Sie den Durchschnitt von ...

Gut, jetzt könnten wir den Ansatz folgendermaßen definieren: Iterieren Sie über das Eingabearray mit dem Fenster der Größe K. Zählen Sie bei jeder Iteration den Durchschnitt des Fensters ...

Problem zwei

Bestimmen Sie bei einem gegebenen Array positiver Zahlen und einer positiven Zahl K die maximale Summe eines beliebigen zusammenhängenden Unterarrays der Größe K.

1. Schiebefenster? - Wieder zusammenhängende Subarrays, das erste Schlüsselwort, was bedeutet, dass wir uns um Fenster kümmern sollten, die ein oder mehrere zusammenhängende Subarrays darstellen würden.
2. Kennen wir die Größe des Schiebefensters? - Ja, K, wir haben die Größe des Fensters, die der Länge von K entsprechen sollte.
3. Was genau sollen wir im Schiebefenster verwalten/überprüfen? - .. die Summe ...

Jetzt: Durchlaufen Sie das Eingabearray mit dem Fenster der Größe K. Zählen Sie bei jeder Iteration die Summe von Fenster ...

Problem drei

Bestimmen Sie bei einem gegebenen Array positiver Zahlen und einer positiven Zahl S die Länge des kleinsten zusammenhängenden Subarrays, dessen Summe größer oder gleich S ist.

1. Schiebefenster? - Wieder zusammenhängende Subarrays, das erste Schlüsselwort, was bedeutet, dass wir uns um Fenster kümmern sollten, die ein oder mehrere zusammenhängende Subarrays darstellen würden.
2. Kennen wir die Größe des Schiebefensters? - eigentlich nein, wir müssen es herausfinden.
3. Was genau sollen wir im Schiebefenster verwalten/überprüfen? - ... Summe ist >= zu S ...

Nun könnten wir den Ansatz folgendermaßen definieren: „Zuerst iterieren wir über das Eingabearray und erstellen ein solches erstes Fenster, das die Bedingungen erfüllen würde (Summe ist >= zu S). Sobald dies erledigt ist, verschieben Sie das Fenster und verwalten das Fenster.“ Anfang und Ende ...“

Problem vier

Ermitteln Sie bei einer gegebenen Zeichenfolge die Länge der längsten Teilzeichenfolge darin mit nicht mehr als K unterschiedlichen Zeichen.

1. Schiebefenster? - längster Teilstring, das erste Schlüsselwort, was bedeutet, dass wir uns um Fenster kümmern sollten, die einen Teilstring darstellen würden.
2. Kennen wir die Größe des Schiebefensters? - Nein, wir müssen es herausfinden.
3. Was genau sollen wir im Schiebefenster verwalten/überprüfen? - ... Anzahl unterschiedlicher Zeichen ...

Der Ansatz hier ist etwas komplizierter, daher überspringe ich ihn hier.

Problem fünf

Anhand eines Arrays von Ganzzahlen, wobei jede Ganzzahl einen Obstbaum darstellt, erhalten Sie zwei Körbe, und Ihr Ziel besteht darin, die maximale Anzahl an Früchten in jeden Korb zu legen. Die einzige Einschränkung besteht darin, dass jeder Korb nur eine Obstsorte enthalten darf.
Sie können mit jedem Baum beginnen, aber Sie können einen Baum nicht überspringen, wenn Sie einmal begonnen haben. Sie werden von jedem Baum eine Frucht pflücken, bis Sie es nicht mehr können, d. h. Sie hören auf, wenn Sie eine dritte Fruchtsorte pflücken müssen.
Schreiben Sie eine Funktion, um die maximale Anzahl an Früchten in beiden Körben zurückzugeben.

Scheint nicht so offensichtlich, vereinfachen wir zunächst die Bedingungen.

Es gibt ein Eingabearray. Das Array enthält möglicherweise nur zwei unterschiedliche Ziffern (Buckets). Sie werden gebeten, ein solches zusammenhängendes Subarray zu finden, dessen Länge die maximale Länge wäre.

Jetzt ist es mal einfacher zu erkennen, dass wir mit dem Schiebefensterkonzept arbeiten könnten.

1. Schiebefenster? - zusammenhängendes Subarray
2. Kennen wir die Größe des Schiebefensters? - Nein, wir müssen es herausfinden.
3. Was genau sollen wir im Schiebefenster verwalten/überprüfen? - ... ob Ziffern unterschiedlich sind und die Länge des Fensters ...

Problem sechs

Stellen Sie anhand einer Zeichenfolge und eines Musters fest, ob die Zeichenfolge eine Permutation des Musters enthält.

Erstens haben wir zwei Saiten, Original und Muster. Wir wissen, dass wir Original und Muster irgendwie vergleichen müssen, was zu der Idee geführt hat, dass wir das Größenfenster des Musters konstruieren und außerdem eine Permutationsprüfung durchführen müssen. Das bedeutet, dass wir möglicherweise das Schiebefensterkonzept verwenden.

Outro

Wenn Sie sich mit Schiebefenstern befassen, denken Sie an folgende Fragen:

• Verstehen Sie die Größe des Fensters?
• Verstehen Sie, wie man das Fenster baut?
• Verstehen Sie, wie man das Fenster verschiebt/verkleinert?
• Verstehen Sie, was ein gültiges/ungültiges Fenster ist?
• Verstehen Sie, wie man ein ungültiges Fenster zu einem gültigen macht?

Das obige ist der detaillierte Inhalt von„Talk with You', Serie Nr. 2. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!