【完虐算法系列】「字串 – 滑動視窗」覆盤總結

語言: CN / TW / HK

讀前福利:幾百本經典書籍 https://www.johngo689.com/2158/

原文連結: https://www.johngo689.com/2264/

LeetCode 刷題的進展有段時間沒有更新了,過去的一篇文章有過這方面的解釋,今天再來說一下。

穿插一句,今天文末再送書哈...

迴歸正題:

兩點原因,第一點就是有讀者說過去文章太長,是否可以考慮截取出來,分類討論。這一點我是有考慮的,事實上本身文章已經是一個類別了,比如說動態規劃,整個介紹超過萬字,自我感覺才把一個問題描述的比較清楚。所以,後面考慮再細分,使得想要表述的問題更加調理清楚,可讀性更強。

另外一點原因呢,就是關於文章頁面展示。也是關於一個可讀性的方面,這個是真真切切花了將近一個月搞的一個事情。就是重新打理了一個網站(www.johngo689.com,感覺還是比較漂亮的,每天都要看幾眼、、哈哈)。

這中間還有人問到為什麼域名起這樣的一個名字,還穿插著數字,咱們還是後面有空在說說(later。。。)

今天咱們一起要討論的是關於「字串」的第一塊內容。

字串 - 滑動視窗

今天再把整個的刷題腦圖放出來,前面的已經細化,後面一塊一塊逐漸會整理出來。

可以看在整個大的腦圖當中 「字串 - 滑動視窗」 這一塊。

上面是整個 LeetCode 演算法刷題計劃,圖中只細化了 二叉樹、動態規劃和字串 相關理論分析和題目的講解。所以,沒有加入的同學們可以私信我,即使現在沒有計劃刷題的也可以加入進來,當個看客也不錯,身處網際網路,遲早會用到。

之前說到過, 「字串」 這一塊會出 10 篇覆盤總結,今天是第一篇 「字串 - 滑動視窗」

「字串 - 滑動視窗」這一塊咱們安排了四個問題,準備用這四個問題將滑動視窗的使用以及相關題目討論清楚。

【簡單】滑動視窗數字之和(引例)

【中等】567.字串的排列 https://leetcode-cn.com/problems/permutation-in-string/

【困難】239.滑動視窗最大值 https://leetcode-cn.com/problems/sliding-window-maximum/

【中等】3.無重複字元的最長子串 https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/

滑動視窗-引例

滑動視窗演算法一般是作用在 字串 或者 陣列 上,通過不斷的滑動邏輯視窗,在特定視窗大小內進行計算的過程。

滑動視窗的方式可以降低時間複雜度,從而減短計算的執行時間。

引例:比如說在字串 s="5189623196" 中,視窗大小 w=5 ,找出每個視窗字元子串的和。

普通的計算方式:每 5 個進行一次求個計算,時間複雜度方面能夠達到 O(N^2)

利用視窗的方式:可很大程度可以減小時間方面的消耗。就拿引例來說,時間複雜度應該是 O(N) 的線性複雜度。

該案例核心思路是:視窗在每一次的滑動前後,中間元素內容沒有改變,僅僅改變的是開頭和結尾元素。

即: 下一視窗內元素之和 = 上一視窗元素和 - 離開視窗元素值 + 新加入視窗元素值

下面分步驟進行討論,將最終結果寫入到 res 中。

步驟一:直接計算視窗內元素和,res = [29]

步驟二:在上一步驟的基礎上,減去離開視窗的元素,加上新加入視窗的元素。

步驟三:繼續在上一步驟的基礎上,減去離開視窗的元素,加上新加入視窗的元素

相同邏輯繼續執行....

步驟六:滑動視窗將最後一個元素包含進來

上述每一步驟中,將 sum 值都新增到最終的結果變數 res 中。

滑動視窗這樣的思維方式就很巧妙的進行在視窗的不斷移動,進而產生各元素在視窗邊界進進出出,利用這一點,在時間複雜度方面進行了一個很大提升!

程式碼簡單的寫一下,還是利用 Python,也是因為 Python 的話,絕大多數人還是比較熟悉。

class Solution(object):
    def sumSlidingWindow(self, s, w):
        sum = 0
        res = []
        # 計算第一個視窗數字之和
        for item in range(5):
            sum += s[item]
        res.append(sum)
        # 後面利用滑動視窗思想進行計算
        for item in range(w, len(s)):
            sum -= s[item-w]
            sum += s[item]
            res.append(sum)
        return res

下面咱們用三個 LeetCode 經典案例進一步闡述滑動視窗這類題目。

滑動視窗經典題目

567.字串的排列【中等】

給你兩個字串 s1 和 s2 ,寫一個函式來判斷 s2 是否包含 s1 的排列。如果是,返回 true ;否則,返回 false 。

換句話說,s1 的排列之一是 s2 的 子串 。

輸入:s1 = "ab" s2 = "eidbaooo"
輸出:true
解釋:s2 包含 s1 的排列之一 ("ba").

首先,兩個字串的排列,首先可以想到字典,根據字典去比較。

詞典可根據兩個不同字串將給到的字元進行計數,因此,這樣很同容易進行比較。

另外,在遍歷 s2 的時候,使用滑動視窗,該視窗的長度是字串 s1 的長度,遍歷 s2 使得字元不斷的出入,在此過程中比較兩個字典。

整個過程,記 s1 的長度為 size1s2 的長度為 size2 ,視窗大小為 size1 ,不斷遍歷 s2 ,直到 s2 的結尾。

s1 的字典為 dict_s1 ,記 s1 的字典為 dict_s2 ,在遍歷 s2 的過程中,每滑動一次視窗,比較 dict_s1dict_s2 是否相等。

視窗滑動過程中,需要 刪除滑出視窗的元素 以及 新增滑入視窗的元素

刪除滑出視窗的元素:廣義上是從字典 dict_s2 中刪除,注意此處不能直接刪除,因為可能會有重複元素存在,比如: {'a':2} ,所以只能是將 value 值減 1。之後再判斷 value 值為否為 0,如果為 0 了,這個時候就可以直接將該元素從字典中刪除。

新增滑入視窗的元素:直接將滑入視窗的元素新增進字典中。

下面用幾個圖清晰的一步一步操作:

初始化 s1 對應的字典 dict_s1={'a':1,'b':1}

s2 對應的字典為圖中視窗中的元素 dict_s2={'e':1,'i':1}

最後判斷 dict_s1 != dict_s2

② 向右滑動視窗,由於元素 e 的 value 值為 1,直接刪除該元素,加入新元素 d ,此時, dict_s2={'i':1,'d':1}

最後判斷 dict_s1 != dict_s2

③ 繼續向右滑動視窗,由於元素 i 的 value 值為 1,直接刪除該元素,加入新元素 b ,此時, dict_s2={'d':1,'b':1}

最後判斷 dict_s1 != dict_s2

③ 繼續向右滑動視窗,由於元素 d 的 value 值為 1,直接刪除該元素,加入新元素 a ,此時, dict_s2={'b':1,'a':1}

最後判斷 dict_s1 == dict_s2 ,此時可以直接返回 True 。不用在繼續視窗滑動了。

這個題雖然在 LeetCode 中標記為中等,但是用滑動視窗的方式去解決還是非常容易理解的。

下面是 Python 程式碼的實現:

class Solution(object):
    def checkInclusion(self, s1, s2):
        size1 = len(s1)
        size2 = len(s2)
        if size1 > size2:
            return False

        dict_s1 = collections.Counter(s1)
        dict_s2 = collections.Counter(s2[:size1-1])
        left = 0
        for right in range(size1-1, size2):
            # 增加新新增的元素
            dict_s2[s2[right]] += 1
            # 判斷如果字典相同,則返回 True
            if dict_s1 == dict_s2:
                return True
            # 刪除左邊剔除的元素(首先需要將左邊元素的 value 值減 1)
            dict_s2[s2[left]] -= 1
            # value 值為 0 的時候,就可以刪除該元素了
            if dict_s2[s2[left]] == 0:
                del(dict_s2[s2[left]])
            # 視窗整體向右移動一格
            left += 1
            right += 1
        return False

下面再看一個稍微複雜一點的,也是滑動視窗的典型例題。

239.滑動視窗最大值【困難】

給你一個整數陣列 nums,有一個大小為 k 的滑動視窗從陣列的最左側移動到陣列的最右側。你只可以看到在滑動視窗內的 k 個數字。滑動視窗每次只向右移動一位。

返回滑動視窗中的最大值。

輸入:nums = [1,3,-1,-3,5,3,6,7], k = 3
輸出:[3,3,5,5,6,7]
解釋:
滑動視窗的位置                最大值
---------------             -----
[1  3  -1] -3  5  3  6  7      3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

滑動視窗最大值是一道典型的滑動視窗的例題。該題被標記為困難,可能就在於 最大值 的判斷,如果使用傳統方式的話,時間複雜度就會很高。

關於 最大值 ,可是嘗試使用 優先佇列 去解決,即 構造大頂堆 ,也可以使用 雙向佇列 解決問題。

以下用兩種方式都來解決一下。

方法一:優先佇列解決

由於題目要求是選擇視窗內的最大值,因此需要構造了大頂堆,此時得出來隊首元素就是整個佇列的最大值。

注意點:我們這裡由於採用 Python 的 heapq 庫來實現,而 heapq 庫只能構造小頂堆。

因此,可以換一個思路進行實現,例如列表 [1,-3,12]:

首先,每個元素的負值都插入到優先佇列中,構造小頂堆,產生的結果是這樣的 [-12, 3, -1]

然後,將隊首元素去除並且取反,得到的結果是 12。這就是我們想要的結果,取到了其中的最大值。

關於 Python 使用優先佇列的方式,可以檢視這一篇文章【 https://mp.weixin.qq.com/s/94Rnnt7R5_kTfoAW0j-wyQ】,有詳細的使用方式。

首先,初始化一個視窗大小的優先佇列 window ,並且記錄元素( 注意這裡要取反 )以及元素下標,組裝成一個元祖 (-num, index)

然後,當不斷向右移動視窗,把新加進來的元素(元祖)加入到優先佇列中。

最後,判斷當前優先佇列中的隊首元素對應的 index ,是否在固定視窗內,如果在,則取值並且取反;否則,刪除隊首元素,繼續判斷。

下面依舊用幾個圖清晰的一步一步操作:

我們用字串為 nums=[12, -3, 1, -1, 9, 5], k = 3 來進行說明。

初始化 res 用來儲存每個視窗最大值。

① 初始化優先佇列 window=[(-12, 0), (3, 1), (-1, 2)],判斷隊首元素的下標值 value=0 在當前視窗內。

所以,取出隊首元素 -12 ,並且取反, res=[12]

② 優先佇列 window=[(-12, 0), (-1, 2), (1, 3), (3, 1)],判斷隊首元素的下標值 value=0 不在當前視窗內,彈出隊首元素。

此時,window=[(-12, 0), (-1, 2), (1, 3), (3, 1)],再判斷此時隊首元素的下標值 value=2 在當前視窗內。

所以,取出隊首元素 -1 ,並且取反, res=[12, 1]

③ 優先佇列 window=[(-9, 4), (-1, 2), (3, 1), (1, 3)],判斷隊首元素的下標值 value=4 在當前視窗內。

所以,取出隊首元素 -9 ,並且取反, res=[12, 1, 9]

④優先佇列 window=[(-9, 4), (-5, 5), (3, 1), (1, 3), (-1, 2)],判斷隊首元素的下標值 value=4 在當前視窗內。

所以,取出隊首元素 -9 ,並且取反, res=[12, 1, 9, 9]

這個時候就都所有取數完成了!

中間關於 Python 的 hepq 庫構造大頂堆有點繞,這點稍微理解下,對於後面的解題幫助特別大。

思路描述完了,再看下程式碼實現:

def maxSlidingWindow(self, nums, k):
        size = len(nums)
        window = [(-nums[i], i) for i in range(k)]
        heapq.heapify(window)
        res = [-window[0][0]]

        for i in range(k, size):
            heapq.heappush(window, (-nums[i], i))
            while window[0][1] <= i-k:
                heapq.heappop(window)
            res.append(-window[0][0])
        return res

感覺描述了一堆,但是程式碼倒是很簡潔。

說完方法一,下面看看方法二...

方法二:雙向佇列解決

為什麼要使用雙向佇列呢?在演算法執行過程中,需要兩邊進行入隊和出隊的操作。

大致思路也比較容易:

首先,初始化一個空佇列 queue;

然後,逐個入隊,但當下一個元素入隊時,判斷與隊尾元素大小。如果小於隊尾元素,則入隊。否則,隊尾依次出隊,直到大於要入隊的元素;

最後,判斷隊首元素是否是在視窗內,如果在視窗內,直接取值,否則,隊首元素出隊。

下面依舊用幾個圖清晰的一步一步操作:

① 元素 12 入隊;視窗範圍 [0, 0]

未形成視窗,不取值;

② 元素 -3 入隊;視窗範圍 [0, 1]

比隊尾元素 12 小,直接入隊;

未形成視窗,不取值;

③ 元素 1 入隊;視窗範圍 [0, 2]

比隊尾元素 -3 大,所以,隊尾元素出隊,元素 1 入隊。而且隊首元素 12 下標 0 在視窗內

取隊首元素 12

④ 元素 -1 入隊;視窗範圍 [1, 3]

比隊尾元素 1 小,元素 -1 入隊。隊首元素 12 下標 0 不在視窗內,元素 12 出隊;取隊首元素 1 的下標 2 在視窗內;

取隊首元素 1

⑤ 元素 9 入隊;視窗範圍 [2, 4]

比隊尾元素 -11 都大,所以,比他小的隊尾元素均出隊,元素 9 入隊。而且隊首元素 9 下標 4 在視窗內

取隊首元素 9

⑤ 元素 5 入隊;視窗範圍 [3, 5]

比隊尾元素 9 小,元素 5 入隊。而且隊首元素 9 下標 4 在視窗內

取隊首元素 9

利用雙向佇列的方式也將視窗內最大元素取出來了!

上面是整體的思路,具體到程式碼中,是把進入佇列的元素替換為元素的下標,這樣實現起來更加容易!

看下 Python 程式碼的實現:

class Solution(object):
    def maxSlidingWindow1(self, nums, k):
        size = len(nums)
        queue = collections.deque()
        res = []
        for i in range(0, size):
            # 新元素進隊,在隊不空的情況下,需要判斷與隊尾元素的大小
            while queue and nums[i] > nums[queue[-1]]:
                queue.pop()
            queue.append(i)
            # 在已經形成視窗(i+1>=k)的前提下,判斷隊首是否在視窗內
            while queue[0] < i-k+1:
                queue.popleft()
            # 從形成視窗的時刻開始將元素置於結果集 res 中
            if i+1 >= k:
                res.append(nums[queue[0]])
        return res

無論是利用優先佇列還是雙向佇列,都需要注意所取的元素是否在當前的視窗內。

3.無重複字元的最長子串【中等】

給定一個字串 s ,請你找出其中不含有重複字元的 最長子串 的長度。

輸入: s = "abcabcbb"
輸出: 3 
解釋: 因為無重複字元的最長子串是 "abc",所以其長度為 3。

想要判斷字元是否存在,通常會使用到字典結構來判斷是否存在。

首先,初始化視窗左右端 left=0right=0 ,初始化字典 words 用來存放已加入字元的元素(key)和元素下標(value),例如, words={'a':0,'b':1,'c':2}

然後, right 指標向右移動,判斷新加入元素是否存在於字典中,如果存在,讓視窗左邊界指向字典對應 value 值的下一個位置,並且更新字典中對應元素的下標值(value);如果不存在,則加入字典 words 中;

注意點:

中間有可能 left 已經更新到後邊,而新判斷的元素可能在前面,會導致 left 變小,所以需要採用 max 來進行判斷

舉例:abba,執行到第二個 b 的時候,left=2,此時words={'a':0,'b':2}。後面再判斷最後的 a 的時候,就會使得 left=0+1=1

因此,需要 left = max(words.get(v) + 1, left)

最後,每一步驟記錄最長子串長度。

依舊用幾個圖清晰的一步一步操作:

① left=0, right=0, 加入新元素 'a' ,words={'a':0}, 視窗長度為1

② left=0, right=1, 加入新元素 'b' ,words={'a':0, 'b':1}, 視窗長度為2

③ left=0, right=2, 加入新元素 'c' ,words={'a':0, 'b':1, 'c':2}, 視窗長度為3

④ left=0, right=3, 加入新元素 'a' ;

發現 a 已經在 words={'a':0, 'b':1, 'c':2} 存在;

則更新 left=max(words.get('a') + 1, left)=1,words={'a':3, 'b':1, 'c':2}

視窗長度為3

⑤ left=1, right=4, 加入新元素 'b' ;

發現 'b' 已經在 words={'a':3, 'b':1, 'c':2} 存在;

則更新 left=max(words.get('b') + 1, left)=2,words={'a':3, 'b':4, 'c':2}

視窗長度為3

⑥ left=2, right=5, 加入新元素 'c' ;

發現 'c' 已經在 words={'a':3, 'b':4, 'c':2} 存在;

則更新 left=max(words.get('c') + 1, left)=3,words={'a':3, 'b':4, 'c':5}

視窗長度為3

⑦ left=3, right=6, 加入新元素 'b' ;

發現 b 已經在 words={'a':3, 'b':4, 'c':5} 存在;

則更新 left=max(words.get('b') + 1, left)=5,words={'a':3, 'b':6, 'c':5}

視窗長度為2

⑧ left=5, right=7, 加入新元素 'b' ;

發現 'b' 已經在 words={'a':3, 'b':6, 'c':5} 存在;

則更新 left=max(words.get('b') + 1, left)=7,words={'a':3, 'b':7, 'c':5}

視窗長度為1

左右步驟描述完畢!

根據每一步驟記錄的視窗長度,可得到 最長視窗為 3

下面就由上述邏輯得到最終的程式碼:

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        if not s:
            return 0
        left, right = 0, 0
        length = 1
        words = {}
        for right, v in enumerate(s):
            if s[right] in words.keys():
                print(words.get(v) + 1, left)
                left = max(words.get(v) + 1, left)
            length = max(right-left+1, length)
            # 將當前值的 value 值覆蓋
            words[v] = right
        print(words)
        return length

</https:></https:>