天天看點
傳回

8.2 資料結構---字元串（查找）

最長公共子序列 & 最長公共子串的差別：

找兩個字元串的最長公共子串，這個子串要求在原字元串中是連續的。而最長公共子序列則并不要求連續。

一、最長連續公共子串

題目:  找出兩個字元串的最長連續公共子串

例: abccade 和 dgcadde ==> cad

思路：動态規劃 

考慮兩種情況：

M[i+1][j+1]=0,             s1[i+1] != s2[j+1]

M[i+1][j+1]=M[i][j]+1,  s1[i+1] == s2[j+1]

時間複雜度O(M*N)

空間複雜度O(M*N)

代碼如下：

def getMaxSubStr(s1,s2):
    len_s1 = len(s1)
    len_s2 = len(s2)
    sb = ''
    maxs = 0 #記錄最長公共子串的長度
    maxI = 0 #記錄最長公共子串的最後一個字元的位置
    M = [([None] * (len_s2+1)) for i in range(len_s1+1)]
    i = 0
    while i < len_s1 + 1:
        M[i][0] = 0
        i += 1
    j = 0
    while j < len_s2 + 1:
        M[0][j] = 0
        j += 1
    #通過利用遞歸公式填寫建立的二維數組
    i = 1
    while i < len_s1 + 1:
        j = 1
        while j < len_s2 + 1:
            if list(s1)[i-1] == list(s2)[j-1]:
                M[i][j] = M[i-1][j-1] + 1
                if M[i][j] > maxs:
                    maxs = M[i][j]
                    maxI = i
            else:
                M[i][j] = 0
            j += 1
        i += 1
    i = maxI - maxs
    while i < maxI:
        sb = sb + list(s1)[i]
        i += 1
    return sb

s1 = 'abcdefg'
s2 = 'bdeg'
res = getMaxSubStr(s1,s2)
print(res)

結果如下：

8.2 資料結構---字元串（查找）

二、最長公共子序列(非必須連續)

題目: 找出兩個字元串的最長公共子序列（非連續）

舉例: abcbdab和bdcaba ==》 bcba

思路：動态規劃，

　　　　M[i][j]=0,　　  　　　　　　　　i=0,j=0

　　　　M[i][j]=M[i-1][j-1] + 1         　　  i,j>0,xi=yi

　　　　M[i][j]=max{M[i-1][j],M[i][j-1]}   i,j>0,xi!=yi

　　      S[i][j]=1        s1[i] == s2[j]

　　　  S[i][j]=2        s1[i] != s2[j] 且 M[i-1][j] >=M[i][j-1]

　　　  S[i][j]=3        s1[i] != s2[j] 且 M[i-1][j] < M[i][j-1]

def LCS(s1,s2):
    #s1行，s2列
    len_s1 = len(s1)
    len_s2 = len(s2)
    sb = ''
    M = [([None] * (len_s2+1)) for i in range(len_s1+1)]
    S = [([None] * (len_s2+1)) for i in range(len_s1+1)]
    i = 0
    while i < len_s1 + 1:
        M[i][0] = 0
        S[i][0] = 0
        i += 1
    j = 0
    while j < len_s2 + 1:
        M[0][j] = 0
        S[0][j] = 0
        j += 1
    #通過利用遞歸公式填寫建立的二維數組
    i = 1
    while i < len_s1 + 1:
        j = 1
        while j < len_s2 + 1:
            if s1[i-1] == s2[j-1]:
                M[i][j] = M[i-1][j-1] + 1
                S[i][j] = 1
            elif M[i-1][j] >= M[i][j-1]:
                M[i][j] = M[i-1][j]
                S[i][j] = 2
            else:
                M[i][j] = M[i][j-1]
                S[i][j] = 3
            j += 1
        i += 1
    # print(M)
    return M[-1][-1],S

def cLCS(i,j,S,s1):
    if i == 0 or j == 0:
        return
    if S[i][j] == 1:
        cLCS(i-1,j-1,S,s1)
        print (s1[i - 1], end='')
    elif S[i][j] == 2:
        cLCS(i-1,j,S,s1)
    else:
        cLCS(i,j-1,S,s1)

s1 = 'abcbdab'
s2 = 'bdcaba'
max,S = LCS(s1,s2)
print(S)
# print(len(S),len(S[0]))
cLCS(len(S)-1,len(S[0])-1,S,s1)
# print(max)
8.2 資料結構---字元串（查找）

三、求字元串裡的最長回文子串

題目：給定一個字元串 ​

​s​

​，找到 ​

​s​

​ 中最長的回文子串。你可以假設 ​

​s​

​ 的最大長度為 1000。

舉例：'cdca'的最長回文字元串為'cdc'

思路：周遊字元串的每個元素,然後以該元素為中心點進行左右擴充,取長度最大的

class Solution():
    def __init__(self):
        self.max_len = 0
        self.res = ''

    def getLongestPalindrome(self,s):
        if len(s) == 1:
            return
        start = 0
        for i in range(1,len(s)):
            tmp1 = self.max_side(s,i,i) #以這個數為中心點進行擴充
            if tmp1 > self.max_len:
                self.max_len = tmp1
                start = i - tmp1 // 2

            tmp2 = self.max_side(s,i-1,i)#從這個數和前面的數=以兩個數為中心點進行擴充
            if tmp2 > self.max_len:
                self.max_len = tmp2
                start = i - tmp2 // 2
        self.res = s[start:start+self.max_len]
        return s[start:start+self.max_len]

    def max_side(self,s,i,j):
        maxs = 0
        if i == j: #單數是以一個數為中心
            maxs  = 1
            i -= 1
            j += 1

        while i >= 0 and j < len(s) and s[i] == s[j]: #雙數以兩個一樣的字元為中心
            maxs += 2
            i -= 1
            j += 1
        return maxs

    #leetcode速度最快的代碼
    def longestPalindrome_best(self, s):
        """
        :type s: str
        :rtype: str
        """
        length = len(s)
        if length < 2 or s == s[::-1]: return s
        max_len, begin = 1, 0
        for i in range(1, length):
            odd = s[i - max_len - 1:i + 1]
            even = s[i - max_len:i + 1]
            if i - max_len >= 1 and odd == odd[::-1]:
                begin = i - max_len - 1
                max_len += 2
                continue
            if i - max_len >= 0 and even == even[::-1]:
                begin = i - max_len
                max_len += 1
        return s[begin:begin + max_len]

S = Solution()
res = S.longestPalindrome_best(s='abaad')
print(res)

結果如下：aba

四、和為0的最長連續子串長度

題目：一個一維數組中隻有1和-1，實作程式，求和為0的最長子串長度，并在注釋中給出時間和空間複雜度

思路：在i從0到n，計算sum(i)，sum(i)表示從0到i的元素之和。并儲存在字典dic中，value是索引i，在往後的周遊中每得到一個sum(i)就檢視dic的keys是否已有此sum(i)值，如果有則用目前i位置減去儲存的i，并與maxLen比較，取大的那個。周遊結束，給出結果。時間複雜度O(n)，空間複雜度O(1)

def min_len(l):
    dic = {0: -1}
    sum = 0
    maxLen = 0
    for x in range(0, len (l)):
        sum += l[x]
        print(dic)
        if sum in dic:#如果有一樣的數出現,說明兩個數之間的數和第二個數之和等于0
            maxLen = max(maxLen, x - dic[sum])
        else:
            dic[sum] = x
    return maxLen

print(min_len([3,5,-1,-6,2]))
8.2 資料結構---字元串（查找）

【擴充】和為給定值的最長連續子串

思路：周遊，找和為s的子串，留長度最大的

def findarr(s,nums):
    if not nums:
        return 0
    res = -2 ** 31
    for i in range(4,len(nums)):
        pos = i + 1
        while pos < len(nums)-2 and sum(nums[i:pos+1]) < s:
            pos += 1
        if sum(nums[i:pos+2]) == s and pos - i + 1 > res:
            print(i,pos)
            res = pos - i + 1
    print(res)

s = 7
nums = [2,3,0,2,4,2,0,0,1,2,0,0,2,2]
findarr(s,nums)
8.2 資料結構---字元串（查找）

　　

五、和大于等于給定值的最短連續子串

題目：給定一個含有 n 個正整數的數組和一個正整數 s ，找出該數組中滿足其和 ≥ s 的長度最小的連續子數組。如果不存在符合條件的連續子數組，傳回 0。

舉例：輸入: s = 7, nums = [2,3,1,2,4,3]      輸出: 2

解釋: 子數組 [4,3] 是該條件下的長度最小的連續子數組。

思路1：周遊每位，找和大于等于給定值的長度，然後依次向後周遊，直到周遊完所有的位置。

思路2：滑動視窗，從左往右加到大于s的數，然後從左開始删,若删除之後還能得到大于s的數，則記錄目前的長度,若不能，就繼續右移,加數

思路1代碼如下：

def findarr(s,nums):
    # nums.sort() #[4,3,3,2,2,1]
    if not nums:
        return 0
    res = 2 ** 31
    for i in range(len(nums)):
        pos = i + 1
        while pos < len(nums)-2 and sum(nums[i:pos+1]) < s:
            pos += 1
        if pos - i + 1 < res:
            print(i,pos)
            res = pos - i + 1
    print(res)

 思路2代碼如下：

def minSubArrayLen2(s, nums):
    cur_sum = 0
    n = len (nums)
    res = float ("inf")
    l = 0
    for i in range (n):
        cur_sum += nums[i]
        while cur_sum >= s:
            res = min (res, i - l + 1)
            cur_sum -= nums[l]
            l += 1
    return res if res != float ("inf") else 0

s = 7
nums = [2,3,1,2,4,3]
res = minSubArrayLen2(s,nums)
print(res)

結果：res = 2　　

六、連續最大子序和

 題目：給定一個整數數組 nums ，找到一個具有最大和的連續子數組（子數組最少包含一個元素），傳回其最大和。

示例: 輸入: [-2,1,-3,4,-1,2,1,-5,4],  輸出: 6

解釋: 連續子數組 [4,-1,2,1] 的和最大,為 6。

進階: 如果你已經實作複雜度為 O(n) 的解法，嘗試使用更為精妙的分治法求解。 O(n)

思路1：始終保留最大值，如果目前和比n還小，目前和就取n；否則，和加上這個數，然後用c_res記錄最大子序列

def maxSubArray1(nums):
    s, ts = - 2 ** 31, - 2 ** 31
    res_ = []
    c_res = []
    for n in nums:
        if n > ts + n:  #如果目前和比n還小，目前最大和就取n
            ts = n
            res_ = [n]
        else:   #否則，取n+ts
            ts = n + ts
            res_.append(n)
        if s < ts:
            s = ts
            c_res = list(tuple(res_))
            print("c_res=%s,res_=%s"%(c_res,res_))#c_res記錄最大子序列
    return s

# res = maxSubArray1([1,-2])
# print(res)

思路2：如果把數組分成左右兩段，那麼加和最大的連續子序列，要麼出現在數組的左半部分，要麼出現在數組的右半部分，要麼出現在中間，即從左半部分和右半部分相鄰的地方各區一段。是以可以用分治法來求解，具體實作時需要借助遞歸

import math
def CalMax(a, b, c):#三個數比較大小
    if a > b:
        if a > c:
            return a
        else:
            return c
    else:
        if b > c:
            return b
        else:
            return c


MaxLeftSum = 0
MaxRightSum = 0
number = [7, 0, 6, -1, 1, -6, 7, -5]


def MaxCalculator(left, right):
    middle = int(math.modf((left + right) / 2)[1])
    if left == right:
        if number[left] > 0:
            return number[left]
        else:
            return 0

    MaxLeftSum = MaxCalculator(left, middle)
    MaxRightSum = MaxCalculator(middle + 1, right)
    MLASum = 0
    MRASum = 0
    MSum = 0

    i = middle
    while i >= left:
        MSum += number[i]
        if MSum > MLASum:
            MLASum = MSum
        i = i - 1
    MSum = 0

    i = middle + 1
    while i <= right:
        MSum += number[i]
        if MSum > MRASum:
            MRASum = MSum
        i = i + 1
    return CalMax(MaxLeftSum, MaxRightSum, MLASum + MRASum)

n=6
result = MaxCalculator(0,n-1)
print(result)

結果：13

字元串 子數組 數組 子串 最長公共子串
上一篇: Qt中不規則窗體和部件的實作
下一篇: Win10 pycharm中顯示PyTorch tensorboard圖

繼續閱讀