【完虐算法系列】「字串 – 滑動視窗」覆盤總結
讀前福利:幾百本經典書籍 http://www.johngo689.com/2158/
原文連結: http://www.johngo689.com/2264/
LeetCode 刷題的進展有段時間沒有更新了,過去的一篇文章有過這方面的解釋,今天再來說一下。
穿插一句,今天文末再送書哈...
迴歸正題:
兩點原因,第一點就是有讀者說過去文章太長,是否可以考慮截取出來,分類討論。這一點我是有考慮的,事實上本身文章已經是一個類別了,比如說動態規劃,整個介紹超過萬字,自我感覺才把一個問題描述的比較清楚。所以,後面考慮再細分,使得想要表述的問題更加調理清楚,可讀性更強。
另外一點原因呢,就是關於文章頁面展示。也是關於一個可讀性的方面,這個是真真切切花了將近一個月搞的一個事情。就是重新打理了一個網站(www.johngo689.com,感覺還是比較漂亮的,每天都要看幾眼、、哈哈)。
這中間還有人問到為什麼域名起這樣的一個名字,還穿插著數字,咱們還是後面有空在說說(later。。。)
今天咱們一起要討論的是關於「字串」的第一塊內容。
字串 - 滑動視窗
今天再把整個的刷題腦圖放出來,前面的已經細化,後面一塊一塊逐漸會整理出來。
可以看在整個大的腦圖當中 「字串 - 滑動視窗」 這一塊。
上面是整個 LeetCode 演算法刷題計劃,圖中只細化了 二叉樹、動態規劃和字串 相關理論分析和題目的講解。所以,沒有加入的同學們可以私信我,即使現在沒有計劃刷題的也可以加入進來,當個看客也不錯,身處網際網路,遲早會用到。
之前說到過, 「字串」 這一塊會出 10 篇覆盤總結,今天是第一篇 「字串 - 滑動視窗」 。
「字串 - 滑動視窗」這一塊咱們安排了四個問題,準備用這四個問題將滑動視窗的使用以及相關題目討論清楚。
【簡單】滑動視窗數字之和(引例)
【中等】567.字串的排列 http://leetcode-cn.com/problems/permutation-in-string/
【困難】239.滑動視窗最大值 http://leetcode-cn.com/problems/sliding-window-maximum/
【中等】3.無重複字元的最長子串 http://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
的長度為 size1
, s2
的長度為 size2
,視窗大小為 size1
,不斷遍歷 s2
,直到 s2
的結尾。
記 s1
的字典為 dict_s1
,記 s1
的字典為 dict_s2
,在遍歷 s2
的過程中,每滑動一次視窗,比較 dict_s1
和 dict_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 使用優先佇列的方式,可以檢視這一篇文章【 http://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]
比隊尾元素 -1
和 1
都大,所以,比他小的隊尾元素均出隊,元素 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=0
和 right=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:>
- 『學了就忘』Linux許可權管理 — 56、不可改變位許可權(chattr)
- 文字分類:Keras RNN vs傳統機器學習
- 面試官問我HTTP,我真的是
- 多工學習中的資料分佈問題(一)
- 痞子衡嵌入式:深扒IAR啟動函式流程之段初始化實現中可用的壓縮選項
- 密碼學之前後向安全性
- Orika - 類複製工具
- Promise(resolve,reject)的基本使用
- 『學了就忘』Linux許可權管理 — 54、sudo授權
- C# 將Excel轉為PDF時自定義表格紙張大小
- uniapp增加自定義埋點功能
- 併發程式設計中,你加的鎖未必安全
- vue3 學習筆記(九)——script setup 語法糖用了才知道有多爽
- 異或運算的巧用 → 不用額外的變數,如何交換兩個變數的值?
- 深入理解Redis 資料結構—簡單動態字串sds
- 圖片處理看這篇就完了「GitHub 熱點速覽 v.21.48」
- .net打獨立執行環境遇到無法trim遇到的bug
- Java設計模式之(十)——組合模式
- 全連線神經網路學習筆記
- Spring IOC XML配置