1.滑動(dòng)窗口
滑動(dòng)窗口是一個(gè)很實(shí)用的算法(思想)充易,關(guān)于字符串類型的許多題都可以用這個(gè)算法來(lái)解決。
今天找到一個(gè)用來(lái)解釋滑動(dòng)窗口算法的很直觀的例子:轉(zhuǎn)載鏈接
原文作者給出了一個(gè)很形象的類比:卷尺
滑動(dòng)窗口中的這個(gè)“窗口”指的就是卷尺伸出來(lái)的部分,窗口的的頭對(duì)應(yīng)卷尺的頭,窗口的尾就是卷尺伸出來(lái)部分的末尾盏檐,“滑動(dòng)窗口”就是卷尺在一個(gè)給定字符串上移動(dòng)和伸縮的過(guò)程。
2. 應(yīng)用
1. 無(wú)重復(fù)字符的最長(zhǎng)子串
問題描述:給定一個(gè)字符串驶悟,請(qǐng)你找出其中不含有重復(fù)字符的 最長(zhǎng)子串 的長(zhǎng)度胡野。
示例 1:
輸入: "abcabcbb"
輸出: 3
解釋: 因?yàn)闊o(wú)重復(fù)字符的最長(zhǎng)子串是 "abc",所以其長(zhǎng)度為 3痕鳍。
示例 2:
輸入: "bbbbb"
輸出: 1
解釋: 因?yàn)闊o(wú)重復(fù)字符的最長(zhǎng)子串是 "b"给涕,所以其長(zhǎng)度為 1。
示例 3:
輸入: "pwwkew"
輸出: 3
解釋: 因?yàn)闊o(wú)重復(fù)字符的最長(zhǎng)子串是 "wke"额获,所以其長(zhǎng)度為 3够庙。
請(qǐng)注意,你的答案必須是子串的長(zhǎng)度抄邀,"pwke" 是一個(gè)子序列耘眨,不是子串。
問題分析:轉(zhuǎn)載鏈接(有在原文基礎(chǔ)上改動(dòng))
一個(gè)字符串境肾,要在里面找出最長(zhǎng)且沒有重復(fù)字符的子串剔难,就像拿著卷尺在上面不停地移動(dòng)、伸縮測(cè)量奥喻。
子串就是這個(gè)卷尺的伸出部分偶宫,即一個(gè)窗口,左邊縮進(jìn)环鲤,右邊拉出纯趋。
因?yàn)椴荒苡兄貜?fù)的字符,在右端逐漸拉長(zhǎng)的過(guò)程中冷离,每新增加的一個(gè)新字符都要拿來(lái)和左側(cè)子串中的所有字符做對(duì)比吵冒。
在下面的程序里,用 left 指向卷尺頭部西剥,用 right 指向卷尺尾部痹栖,k 則作為子串中字符的索引。
每次對(duì)比開始時(shí)瞭空,用 left 的值初始化 k(即從當(dāng)前窗口左側(cè)第一個(gè)字符開始對(duì)比)揪阿,如發(fā)現(xiàn)重復(fù)字符疗我,就將 k + 1的值賦給 left,即直接將窗口的左側(cè)移動(dòng)到現(xiàn)在窗口中重復(fù)字符的下一個(gè)字符位置南捂。
窗口右側(cè)每次向右滑動(dòng)一格碍粥,如果窗口中子串包含窗口右側(cè)下一個(gè)字符,左側(cè)滑動(dòng)一格或多格黑毅。
與枚舉法相比嚼摩,由于利用了子串中重復(fù)字符的位置,直接將窗口左側(cè)跳到該字符的下一個(gè)位置矿瘦,每次檢查出重復(fù)減少了 k - left 個(gè)子串的自檢枕面。
代碼實(shí)現(xiàn)(Python):
class Solution(object):
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
left = 0 #窗口左端
right = 0 #窗口右端
windowLengh = 0 #窗口長(zhǎng)度
maxLength = 0 #最長(zhǎng)無(wú)重復(fù)子串長(zhǎng)度
length = len(s)
if(length == 0):
return 0
for right in range(0, length):
if(length-left < maxLength):
return maxLength #如果窗口左端到字符串末尾的總長(zhǎng)度小于現(xiàn)在的最長(zhǎng)無(wú)重復(fù)子串長(zhǎng)度,那么就無(wú)需繼續(xù)比較了
windowLengh +=1
if(right == length-1): ##達(dá)到最右端
break
for k in range(left, right+1): #從窗口左端開始比較
if(s[k] == s[right+1]): #如果重復(fù)
if(windowLengh > maxLength): #如果窗口長(zhǎng)度大于目前最長(zhǎng)無(wú)重復(fù)子串長(zhǎng)度
maxLength = windowLengh #更新最長(zhǎng)無(wú)重復(fù)字符串長(zhǎng)度
left = k+1 #移動(dòng)窗口左端
windowLengh = right - left + 1 #重新計(jì)算窗口長(zhǎng)度
break
if(windowLengh > maxLength):
return windowLengh
else:
return maxLength