0003 無(wú)重復(fù)字符的最長(zhǎng)字串

這道題讓我想起了算法課講起的一個(gè)問(wèn)題，什么樣的問(wèn)題適合用分治，什么樣的問(wèn)題適合用遞歸。

問(wèn)題描述

給定一個(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è)子序列，不是子串。

來(lái)源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

解題思路

采用 分治法 果然最難的是如何合并兩個(gè)分支。 做到兩點(diǎn)也沒(méi)做出來(lái)

class Solution:
    @classmethod
    def lengthOfMid(self,s:str) -> int:
        # print(s,'len(s)=',len(s))
        #取最靠近中間的為初始數(shù)組
        if len(s)%2 ==0  :
            ll = len(s)//2-1
            lr = len(s)//2
        else :
            ll = lr = len(s)//2+1
        # midstring= s[ll:lr]
        # print("ll,lr = ",ll, lr)
        lml1 = 0
        lmr1 = 0
        lml2 = 0
        lmr2 = 0

        i = 0
       
        # print(i)
        while not (  lmr1 and lmr2) : 
        #先更新左邊界再更新右邊界 ，如果兩個(gè)右邊界都更新了就結(jié)束循環(huán)
            neg = -1
            
            # 第一次循環(huán)時(shí)lml1、lmr1 的值就不會(huì)為零了  所以只修改lml2、lmr2
            if (lr + 1) >= len(s)  or (ll-1) < 0  :
                lml2 = -1
                lmr2 = -1
            '''
            print("lml1,lml2,lmr1,lmr2",lml1,lml2,lmr1,lmr2)
            # print("lr+i*neg",lr+i*neg)
            # print("ll+i*neg",ll+i*neg)
            '''
            # 如果左邊一位不在中間子串中 就把左邊界左移一位
            if s[ll+i*neg] in s[ll:lr+1]:
                if lml1 == 0:
                    lml1 = ll
                else : 
                    lml2 = ll
            else:
                ll -=1
                # print("左邊界左移一位")
            neg *= -1
            # 如果右邊一位不在中間子串中 就把右邊界右移一位
            if s[lr+i*neg] in s[ll:lr+1]:
                if  lmr1 == 0:
                    lmr1 = lr  
                else : 
                    lmr2 = lr 

                
            else:
                lr +=1
                # print("右邊界右移一位")
           
        lm = max(lmr1-lml1+1,max(lmr2-lml1+1, lmr1-lml2+1) )
        # print("lm",lm)
        return lm
    @classmethod
    def lengthOfLongestSubstring(self, s: str) -> int:
        
        
        if len(s)==1:
            
            return 1
        else:
            ll = self.lengthOfLongestSubstring(s[:len(s)//2])
            lr = self.lengthOfLongestSubstring(s[len(s)//2:])
            return max(lr,max(ll,self.lengthOfMid(s)))
        

string1 = "abcabcbb"
a = Solution.lengthOfLongestSubstring(string1)
print(a)

這個(gè)代碼跑不同樣例 卡在一個(gè)部分

圖片.png

查看了官方結(jié)題思路

方法一：

逐個(gè)檢查所有的子字符串 ，看它是否含有重復(fù)的字符。

1. 假設(shè)字串從i到j(luò) 那么，所有的字串是 0 <= i <= j <= n,那么 i從0到n-1循環(huán)，j從 i+1 到 n-1 循環(huán)
2. 檢查是否包含有重復(fù)的字符的實(shí)現(xiàn)。對(duì)于一個(gè)字符串，從第一個(gè)開(kāi)始放入一個(gè)集合中，每次放入的時(shí)候判斷是否包含重復(fù)的字串。

class Solution:

     def lengthOfLongestSubstring(self, s: str) -> int:
          longest = 0
          max_Long = 0
          for i in range(len(s)):
               myset = ''
               myset += s[i]
               longest = 1
               max_Long = max_Long if max_Long > longest else longest
               for j in range(i+1,len(s)):
                    # print('Solution.isRepeat(s[i:j]) is  {}'.format(Solution.isRepeat(s[i:j])))
                    #  if not Solution.isRepeat(s[i:j]):
                    if s[j] not in myset:
                         myset += s[j]
                         if (len(myset)  > longest ):
                         longest = len(myset)
                         max_Long = max_Long if max_Long > longest else longest
                    else:
                         break
          return max_Long

圖片.png

方法二：滑動(dòng)窗口的方法

1. 假設(shè)有個(gè)從零開(kāi)始的窗口，這個(gè)窗口在字符串的開(kāi)始位置，加入這個(gè)窗口可以向右增長(zhǎng)，而且窗口內(nèi)的字符串不重復(fù)，那么窗口就一直增長(zhǎng)，直到不能再增長(zhǎng)為止。
2. 這時(shí)，把窗口中重復(fù)的那個(gè)字符及之前的字符丟棄，如果這時(shí)候窗口長(zhǎng)度可以增長(zhǎng)，就增長(zhǎng)窗口長(zhǎng)度直到不能增長(zhǎng)為止，然后再向右移動(dòng)窗口，如此循環(huán)往復(fù)，直到窗口到達(dá)字符串的最右端。
   方法一修改以下就是滑動(dòng)窗口方法

class Solution:

    def lengthOfLongestSubstring(self, s: str) -> int:
        longest = 0
        i = 0
        j = i + 1
        if len(s) == 0 : return 0
        myset = s[0]
        while (j < len(s)):
            if s[j] not in myset:
                j += 1
            else:
                i = i + myset.index( s[j] ) + 1
                j += 1
            myset = s[i:j]
            if (len(myset)  > longest ):
                longest = len(myset)                
        return longest 

圖片.png

其中有兩個(gè)地方是比較耗時(shí)的

1. 判斷是否在myset中
2. 查找在 myset中的index
   二者可以同時(shí)進(jìn)行
   改為

            # if s[j] not in myset:
            #     j += 1
            # else:
            #     i = i + myset.index( s[j] ) + 1
            #     j += 1
            
            try :
                i = i + myset.index( s[j] ) + 1
            except :
                pass
            j += 1

圖片.png

待更

如何改進(jìn)