與你交談系列#2

簡介

今天我們將開始概述用於解決各種演算法問題的概念。對某個概念的理解可能會給您一種從哪個角度開始思考潛在解決方案的直覺。

有不同但沒有太多的概念。今天我將讓您專注於滑動視窗概念。

滑動視窗

滑動視窗的概念比乍看之下要複雜一些。我將透過實際例子來證明這一點。現在，請記住，概念性的想法是我們將有一些必須移動的視窗。讓我們立即從範例開始。

假設您有一個整數數組和預先定義的子數組大小。您被要求找到這樣一個子數組（也稱為視窗），其值總和將是最大的。

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

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

maximum_sum = 5

嗯，看起來很簡單：
(1) 尺寸為 2 的滑動視窗
(2) 2 個子數組
(3) 計算每個
的總和 (4) 求它們之間的最大值

讓我們實現它。

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 

嗯，看來我們剛剛有效地使用了滑動視窗的概念。事實上，不完全是。透過了解解決方案的時間複雜度，我們可以得到「證明」。

複雜度為 O(l)*O(w)，其中 l 是陣列中視窗的數量，w 是視窗中元素的數量。換句話說，我們需要遍歷l個窗口，對於每個第l個窗口，我們需要計算w個元素的總和。

這裡有什麼問題嗎？讓我們概念性地描述回答問題的迭代。

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

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

答案是，即使我們滑動數組，在每次迭代中我們都需要「重新計算」在上一次迭代中已經計算過的 k-1 個元素。

基本上，這種見解應該建議我們提出一個問題：

「有沒有辦法利用上一步的計算？」

答案是肯定的。我們可以透過將視窗元素的第一個和下一個元素相加和相減來得到視窗元素的總和。讓我把這個想法寫入程式碼中。

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

在這裡我們可能會看到，當我們建構長度為 size 的子數組時，我們開始從視窗總和中減去第一個元素，這使得我們可以重複使用上一步的計算。

現在，我們可以說我們有效地利用了滑動視窗的概念，同時我們得到了檢查時間複雜度的證明，時間複雜度從O(l*w) 降低到O(l)，其中l 是我們將要使用的視窗數量幻燈片。

我想強調的主要思想，滑動視窗概念不僅僅是用特定大小的視窗來切片可迭代物件。

讓我給你一些問題，我們將學習如何檢測問題可能涉及滑動視窗概念以及你到底可以對視窗本身做什麼。

問題概述

由於我在這裡只討論概念，因此我會跳過「如何計算視窗內的某些內容」。

問題一

給定一個數組，求其中所有大小為 K 的連續子數組的平均值。

1. 滑動視窗？ -連續子數組第一個關鍵字，這意味著我們應該處理窗口，它代表一個連續的子數組。
2. 我們知道滑動視窗的大小嗎？ - 是的，K，我們得到了視窗的大小，它應該是 K 的長度。
3. 我們到底該在滑動視窗內管理/檢查什麼？ - 求出...的平均值

好，現在我們可以這樣定義這個方法：使用大小為 K 的視窗迭代輸入陣列。在每次迭代中計算視窗的平均值...

問題二

給定一個正數數組和一個正數 K，找出大小為 K 的任何連續子數組的最大和。

1. 滑動視窗？ - 再次是連續子數組，第一個關鍵字，這意味著我們應該處理窗口，它代表一個連續的子數組。
2. 我們知道滑動視窗的大小嗎？ - 是的，K，我們得到了視窗的大小，它應該是 K 的長度。
3. 我們到底該在滑動視窗內管理/檢查什麼？ - ..總和...

現在：使用大小為 K 的視窗遍歷輸入陣列。在每次迭代中計算視窗的總和...

問題三

給定一個正數數組和一個正數 S，求其總和大於或等於 S 的最小連續子數組的長度。

1. 滑動視窗？ - 再次是連續子數組，第一個關鍵字，這意味著我們應該處理窗口，它代表一個連續的子數組。
2. 我們知道滑動視窗的大小嗎？ - 其實不行，我們需要弄清楚。
3. 我們到底該在滑動視窗內管理/檢查什麼？ - ...總和>=到S ...

現在，我們可以這樣定義該方法：「首先，迭代輸入數組並構造這樣的第一個窗口，它將滿足條件（總和> = S）。完成後，移動窗口，管理窗口開始和結束. ..”

問題四

給定一個字串，找出其中不超過 K 個不同字元的最長子字串的長度。

1. 滑動視窗？ - 最長的子字串，第一個關鍵字，這意味著我們應該處理代表子字串的視窗。
2. 我們知道滑動視窗的大小嗎？ - 不，我們需要弄清楚。
3. 我們到底該在滑動視窗內管理/檢查什麼？ - ...不同字元的數量...

這裡的方法有點複雜，所以我在這裡跳過它。

問題五

給定一個整數數組，其中每個整數代表一棵果樹，給你兩個籃子，你的目標是在每個籃子裡放入最大數量的水果。唯一的限制是每個籃子只能放一種水果。
你可以從任何一棵樹開始，但一旦開始你就不能跳過一棵樹。您將從每棵樹上採摘一種水果，直到您無法採摘為止，也就是說，當您必須採摘第三種水果時，您將停止。
寫一個函數，傳回兩個籃子中水果的最大數量。

似乎不是那麼明顯，我們先簡化一下條件。

有一個輸入數組。陣列可能只包含 2 個不同的數字（桶）。請您找出長度最大的連續子數組。

現在更容易看出我們可能會使用滑動視窗概念。

1. 滑動視窗？ - 連續子數組
2. 我們知道滑動視窗的大小嗎？ - 不，我們需要弄清楚。
3. 我們到底該在滑動視窗內管理/檢查什麼？ - ...數字是否不同以及視窗的長度...

問題六

給定一個字串和一個模式，找出該字串是否包含該模式的任何排列。

首先，我們有 2 個字串，原始字串和模式字串。我們知道我們以某種方式比較了原始和模式，這導致了這個想法，我們需要建立模式大小的視窗並進一步執行排列檢查。這意味著，我們可以使用滑動視窗概念。

尾奏

當您處理滑動視窗時，請記住以下問題：

• 你了解視窗的大小嗎
• 你知道如何建造窗戶嗎
• 你知道如何移動/縮小視窗
• 你知道什麼是有效/無效視窗
• 你知道如何讓無效視窗變成有效視窗嗎

以上是與你交談系列#2的詳細內容。更多資訊請關注PHP中文網其他相關文章！