網(wǎng)站運營與管理的內(nèi)容包括網(wǎng)絡(luò)營銷渠道建設(shè)方案
1 問題
給定一個字符串“S”，找出其中不含有重復(fù)字符的最長子串的長度。例如：S=‘ABCABCBB’，則不含重復(fù)字符的最長字串長度為3.。S=‘ABCDFG’,則不含重復(fù)字符的最長字串長度為6。要求設(shè)計一個Python程序?qū)崿F(xiàn)該功能？
2 方法
按照一般方法，可以采取暴力求解，即把所有不重復(fù)的字串全部找出來，再在其中找出最長的字串?？墒窃摲椒ǖ臅r間復(fù)雜度和空間復(fù)雜度都十分大，面對較長的字符串則會浪費過多時間。
對于該現(xiàn)象，即可使用“滑動窗口”算法。滑動窗口算法也是一種思想，是雙指針的拓展和延伸?；瑒?#xff1a;指這個窗口是移動的，也就是移動是按照一定方向來的。窗口：窗口大小并不是固定的，可以不斷擴容直到滿足一定的條件；也可以不斷縮小，直到找到一個滿足條件的最小窗口；當(dāng)然也可以是固定大小。
面對前面所提出的問題，使用“滑動窗口”算法，大致思路為：
設(shè)置兩個指針和一個空列表
固定左指針，不斷右移右指針，同時更新最長不重復(fù)字符串長度
如果出現(xiàn)重復(fù)字符，再右移左指針，如此重復(fù)，直到遍歷完字符串的所有字符。
最后輸出最長不重復(fù)字符串長度即可。
這樣就降低了問題的復(fù)雜度，也降低了循環(huán)的嵌套深度。
代碼清單 1
| ''' 通過固定左端元素，再右端元素不斷右移，算出左端和右端間的總數(shù) 然后左端再不斷右移，不斷計算之間的總數(shù)。最后算出最長長度 ''' s = input() # 輸入字符串 max_length =float('-inf') # 定義一個初指為負無窮 start = 0 # 定義左指針為0 l = list() # 定義一個空列表，用于是否重復(fù)的判斷 for end in range(len(s)): # 右指針通過for循環(huán)，逐步向右移動 ? ?while s[end] in l: # 當(dāng)右指針移到某個值時，且該值已經(jīng)在前面出現(xiàn)過 ? ? ? ?l.remove(s[start]) # 移除左指針對應(yīng)的重復(fù)值 ? ? ? ?start += 1 # 并且將左指針向右移動一個單位 ? ?max_length = max(max_length, end-start+1) # 每次右指針移動后，統(tǒng)計不重復(fù)的字符串的最長長度 ? ?l.append(s[end]) # 將右指針每次遍歷過的值加入列表中，用于重復(fù)判斷 if max_length == float('-inf'): # 如果最大值對于負無窮，則代表無最長不重復(fù)字符串 ? ?print('0') else: ? ?print(max_length) # 打印最大不重復(fù)字符串長度 ''' 測試結(jié)果： abcabcbb 輸出：3 aaaaaaaa 輸出：1 ''' |
3 結(jié)語
通過測試，發(fā)現(xiàn)“滑動窗口”算法可以很好的解決該問題，與此同時，相對于暴力求解，其時間復(fù)雜度和空間復(fù)雜度也得到了優(yōu)化。總結(jié)發(fā)現(xiàn)，一般給出的數(shù)據(jù)結(jié)構(gòu)是數(shù)組或者字符串，且求取某個子串或者子序列最長最短等最值問題或者求某個目標(biāo)值時。都可以使用“滑動窗口”算法。