python如何進(jìn)行l(wèi)eetcode無重復(fù)字符的最長字串的實(shí)現(xiàn)，很多新手對此不是很清楚，為了幫助大家解決這個難題，下面小編將為大家詳細(xì)講解，有這方面需求的人可以來學(xué)習(xí)下，希望你能有所收獲。

創(chuàng)新互聯(lián)主要從事成都做網(wǎng)站、網(wǎng)站建設(shè)、外貿(mào)營銷網(wǎng)站建設(shè)、網(wǎng)頁設(shè)計(jì)、企業(yè)做網(wǎng)站、公司建網(wǎng)站等業(yè)務(wù)。立足成都服務(wù)芮城,十多年網(wǎng)站建設(shè)經(jīng)驗(yàn),價格優(yōu)惠、服務(wù)專業(yè),歡迎來電咨詢建站服務(wù):028-86922220

無重復(fù)字符的最長字串是一道字符串處理算法的題目，在日常編程中，處理字符串是常見任務(wù)。用Python來實(shí)現(xiàn)leetcode這道算法題，該題目會涉及到一個概念“滑動窗口”。

一、題目描述

給定一個字符串，請你找出其中不含有重復(fù)字符的 最長子串 的長度(Longest substring without repeating characters)。

示例 1:
輸入: "abcabcbb"
輸出: 3
解釋: 因?yàn)闊o重復(fù)字符的最長子串是 "abc"，所以其長度為 3。

示例 2:

輸入: "bbbbb"
輸出: 1
解釋: 因?yàn)闊o重復(fù)字符的最長子串是 "b"，所以其長度為 1。

示例 3:

輸入: "pwwkew"
輸出: 3
解釋: 因?yàn)闊o重復(fù)字符的最長子串是 "wke"，所以其長度為 3。
請注意，你的答案必須是 子串 的長度，"pwke" 是一個子序列，不是子串。

二、解題思路

先來定義一下“子串”，根據(jù)題目描述，“子串”就是字符串中截取某一部分，長度從1到該字符串的長度。比如“abc”的子串集合是：

[‘a(chǎn)’, ‘b’, ‘c’, ‘a(chǎn)b’, ‘bc’, ‘a(chǎn)bc’]

用 Python 生成這個集合很容易，你是否想到了？

def subs(s: str):
    results = []
    for begin in range(len(s)):
        for length in range(len(s)-begin):
            results.append(s[begin:begin + length + 1])
    return results
z = subs('abcde')
print(z)

那么問題來了，任意長度為n的字符串一共有多少個這樣的“子串”呢？答案是：(n+1) * n / 2 。從上面的例子很容易得出這個答案：begin等于0時，長度可以有 n – 0 個，begin等于1時，長度可以有 n – 1個，以此類推，總數(shù)就是：

n + (n-1) + … + 1 => (n+1)*n / 2

（1）暴力解法

明白了“子串”的概念和獲取方法，自然而然的就得到了最樸素也是最“暴力”的解法：遍歷字符串得到所有“子串”，然后判斷每個“子串”是否有重復(fù)字符，最終就會得到無重復(fù)最長子串了。

這個“暴力”算法中，計(jì)算所有子串的時間復(fù)雜度是 O(n2)，而判斷一個子字符串是否有重復(fù)字符，又要從頭到尾遍歷一遍該字符串，所有最終的時間復(fù)雜度可以達(dá)到 O(n3)。

這個解法是不能被接受的，提到它全是因?yàn)榍懊鎸Α白哟钡慕忉尲捌鋽?shù)量計(jì)算，來練習(xí)Python對字符串的操作。

（2）滑動窗口

“滑動窗口”這個概念在計(jì)算機(jī)算法中非常常見。該算法可以把嵌套的循環(huán)轉(zhuǎn)化為單循環(huán)從而降低時間復(fù)雜度。它在很多不同的領(lǐng)域都有應(yīng)用：

TCP協(xié)議的滑動窗口進(jìn)行流量控制

NLP（自然語言處理）中的 N-gram

圖像處理中的物體識別

有興趣的同學(xué)可以深入了解上面提到的應(yīng)用領(lǐng)域。

下面我們看看，“滑動窗口”如何進(jìn)行字符串處理。結(jié)合題目中的例子“abcabcbb”這個字符串，我們來看看如何找它的無重復(fù)最長子串。

首先，我們定義窗口的兩端：begin和end，分別表示要找的子串的開頭和結(jié)尾。

開始的時候，begin和end都指向0的位置即‘a(chǎn)’，然后end不斷后移（窗口變寬），當(dāng)遇到第二個‘a(chǎn)’時（遇見重復(fù)字符）就得到一個子串，其長度就是end和begin位置的差。

不重復(fù)最長字串算法演示

如何判斷是否遇到了重復(fù)字符‘a(chǎn)’呢？需要一個字典作為輔助數(shù)據(jù)結(jié)構(gòu)，把end從頭開始遇到的每個字符及其索引位置都放到字典里面，end每次移動到新字符就查一下字典即可。

通過字典，我們遇到第二個‘a(chǎn)’時就可以找到存在字典里面的第一個‘a(chǎn)’的位置。為了繼續(xù)尋找無重復(fù)子串，begin就要指向第一個‘a(chǎn)’后面一個的位置即‘b’。然后end繼續(xù)后移到‘b’，有發(fā)現(xiàn)它與前面的‘b’重復(fù)，計(jì)算子串長度賦值給大長度（需要比較），同時begin要移動第一個‘b’后面的位置即‘c’。

這樣依次移動end到字符串末尾就可以找到最長的子串，“子串窗口”也就從頭移到了末尾。而只需要end從頭到尾的一次循環(huán)即可。

把這個過程用Python實(shí)現(xiàn)如下：

class Solution:
    def lengthofLongestSubstring(self, s: str) -> int:
        maxlen = 0
        memo = dict()
        begin, end = 0, 0
        n = len(s)
        while end < n:
            last = memo.get(s[end])
            memo[s[end]] = end
            if last is not None:
                maxlen = max(maxlen, end-begin)
                begin = max(begin, last + 1)
            end += 1
        maxlen = max(maxlen, end-begin)
        return maxlen

提交后就可以看到結(jié)果?！皥?zhí)行時間”還只是個參考，再一次提交相同代碼結(jié)果不是圖中的擊敗91%，而變成了百分之十幾。

看完上述內(nèi)容是否對您有幫助呢？如果還想對相關(guān)知識有進(jìn)一步的了解或閱讀更多相關(guān)文章，請關(guān)注創(chuàng)新互聯(lián)-成都網(wǎng)站建設(shè)公司行業(yè)資訊頻道，感謝您對創(chuàng)新互聯(lián)的支持。

網(wǎng)站標(biāo)題：python如何進(jìn)行l(wèi)eetcode無重復(fù)字符的最長字串的實(shí)現(xiàn)-創(chuàng)新互聯(lián)
標(biāo)題網(wǎng)址：http://aaarwkj.com/article30/codiso.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)頁設(shè)計(jì)公司、商城網(wǎng)站、虛擬主機(jī)、網(wǎng)站改版、云服務(wù)器、響應(yīng)式網(wǎng)站

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)