当前位置：网站首页>leetcode-子序列/子串問題

leetcode-子序列/子串問題

2022-06-22 13:21:00 【林沖風雪山神廟】

力扣https://leetcode-cn.com/problems/longest-palindromic-subsequence/solution/dai-ma-sui-xiang-lu-dai-ni-xue-tou-dpzi-dv83q/

leetcode-最大最小問題-v2_MaYingColdPlay的博客-CSDN博客300. 最長上昇子序列class Solution(object): def lengthOfLIS(self, nums): """ :type nums: List[int] :rtype: int """ if nums== []: return 0 dp=[1 for _ in range(len(nums))] for i in range(lhttps://blog.csdn.net/MaYingColdPlay/article/details/109143223

動態規劃5部曲：

1.dp數組含義

2.遞推公式

3.初始化

4.遍曆順序

5.舉例推到dp數組

5.最長回文子串

動態規劃

class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        max_len=1
        start=0
        dp=[[0 for _ in range(len(s))] for _ in range(len(s))]
        for i in range(len(s)):
            dp[i][i]=1
        for i in range(len(s)-1,-1,-1):
            for j in range(i+1,len(s)):
                if s[i]==s[j]:
                    if j-i+1==2:
                        dp[i][j]=True
                    else:
                        dp[i][j]=dp[i+1][j-1]
                if dp[i][j]==True:
                    cur_len=j-i+1
                    if cur_len>max_len:
                        max_len=cur_len
                        start=i
        return s[start:start+max_len]

516.最長回文子序列

動態規劃

class Solution(object):
    def longestPalindromeSubseq(self, s):
        """
        :type s: str
        :rtype: int
        """
        #dp[i][j]=dp[i+1][j-1]+2
        #注意遍曆的順序
        dp=[[0 for _ in range(len(s))] for _ in range(len(s))]
        for i in range(len(s)):
            dp[i][i]=1
        for i in range(len(s)-1,-1,-1):
            for j in range(i+1,len(s)):
                if s[i]==s[j]:
                    dp[i][j]=dp[i+1][j-1]+2
                else:
                    dp[i][j]=max(dp[i+1][j],dp[i][j-1])
        return dp[0][-1]

最長遞增子序列

劍指offer-leetcode-最大最小問題-思路篇_MaYingColdPlay的博客-CSDN博客https://blog.csdn.net/MaYingColdPlay/article/details/106035602

673. 最長遞增子序列的個數

動態規劃

力扣https://leetcode-cn.com/problems/number-of-longest-increasing-subsequence/solution/python3-dong-tai-gui-hua-by-caiji-ud-xqam/

class Solution(object):
    def findNumberOfLIS(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        dp=[1 for _ in range(len(nums))]
        cnt=[1 for _ in range(len(nums))]
        for i in range(len(nums)):
            for j in range(i):
                if nums[i]>nums[j]:
                    if dp[j]+1>dp[i]:
                        dp[i]=dp[j]+1
                        cnt[i]=cnt[j]
                    elif dp[j]+1==dp[i]:
                        cnt[i]=cnt[i]+cnt[j]
                    else:
                        continue
        res=0
        for i in range(len(nums)):
            if dp[i] == max(dp):
                res+=cnt[i]
        return res

72.編輯距離

動態規劃

leetcode-買賣股票/背包問題_MaYingColdPlay的博客-CSDN博客122. 買賣股票的最佳時機 II貪心https://blog.csdn.net/MaYingColdPlay/article/details/108184505

代碼隨想錄認准代碼隨想錄，學習算法不迷路https://programmercarl.com/0072.%E7%BC%96%E8%BE%91%E8%B7%9D%E7%A6%BB.html#%E6%80%9D%E8%B7%AF

class Solution(object):
    def minDistance(self, word1, word2):
        """
        :type word1: str
        :type word2: str
        :rtype: int
        """
        #其實與最長公共子序列有億點點類似。
        #dp[i][j]錶示word1[:i]和word2[:j]之間的編輯距離
        dp=[[0 for i in range(len(word2)+1)] for _ in range(len(word1)+1)]
        #初始化
        for i in range(len(word2)+1):
            dp[0][i]=i 
        for i in range(len(word1)+1):
            dp[i][0]=i
        #兩層循環
        for i in range(1,len(word1)+1):
            for j in range(1,len(word2)+1):
                if word1[i-1]==word2[j-1]:
                    dp[i][j]=dp[i-1][j-1]
                else:
                    #word1删去一個元素
                    c1=dp[i-1][j]+1
                    #word2删去一個元素
                    c2=dp[i][j-1]+1
                    #改變一個元素
                    c3=dp[i-1][j-1]+1
                    dp[i][j]=min(c1,c2,c3)
        return dp[-1][-1]

583.兩個字符串的删除操作

思路：和編輯距離一樣，就是條件少了一個。編輯距離是删除，增加，或者改變，這個題目只有删除。所以在代碼裏把“改變”的那個去掉就可以了。

class Solution(object):
    def minDistance(self, word1, word2):
        """
        :type word1: str
        :type word2: str
        :rtype: int
        """
        dp=[[0 for i in range(len(word2)+1)] for _ in range(len(word1)+1)]
        #初始化
        for i in range(len(word2)+1):
            dp[0][i]=i 
        for i in range(len(word1)+1):
            dp[i][0]=i
        #兩層循環
        for i in range(1,len(word1)+1):
            for j in range(1,len(word2)+1):
                if word1[i-1]==word2[j-1]:
                    dp[i][j]=dp[i-1][j-1]
                else:
                    #word1删去一個元素
                    c1=dp[i-1][j]+1
                    #word2删去一個元素
                    c2=dp[i][j-1]+1
                    dp[i][j]=min(c1,c2)
        return dp[-1][-1]

115.不同的子序列

代碼隨想錄認准代碼隨想錄，學習算法不迷路https://programmercarl.com/0115.%E4%B8%8D%E5%90%8C%E7%9A%84%E5%AD%90%E5%BA%8F%E5%88%97.html#_115-%E4%B8%8D%E5%90%8C%E7%9A%84%E5%AD%90%E5%BA%8F%E5%88%97

class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        dp = [[0] * (len(t)+1) for _ in range(len(s)+1)]
        for i in range(len(s)):
            dp[i][0] = 1
        for j in range(1, len(t)):
            dp[0][j] = 0
        for i in range(1, len(s)+1):
            for j in range(1, len(t)+1):
                if s[i-1] == t[j-1]:
                    dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
                else:
                    dp[i][j] = dp[i-1][j]
        return dp[-1][-1]
1

力扣

最長公共子序列/子串

劍指offer-leetcode-最大最小問題-思路篇_MaYingColdPlay的博客-CSDN博客1.無重複字符最長子串雙指針法，用一個left指針，指向最左邊，一個cur指針，指向當前，記錄兩者之間的距離。用一個列錶來記錄當前無重複字符。如果有重複的子串，移動left指針。不用兩個指針也可，直接用一個list來判斷就行了。list+從左邊pop出當前存在的。...https://blog.csdn.net/MaYingColdPlay/article/details/106035602

940. 不同的子序列 II

 力扣

重複的是前一個相同元素，之前的。不包含前一個相同的元素在內。

因為，前一個重複元素，本身這個值時可以包括在新增元素範圍內的，兩者重複的只有他之前的那些。

class Solution(object):
    def distinctSubseqII(self, s):
        """
        :type s: str
        :rtype: int
        """
        maps = collections.defaultdict(int)
        dp = [0 for _ in range(len(s)+1)]
        for i in range(1,len(s)+1):
            dp[i] = dp[i-1]*2 + 1
            if s[i-1] in maps:
                pre = maps[s[i-1]]
                dp[i] = dp[i] - pre - 1
            #重複的是前一個相同元素，之前的。不包含前一個相同的元素在內。
            maps[s[i-1]]=dp[i-1]
        return dp[-1] % (10**9+7)

1987. 不同的好子序列數目

#基本思路和940一樣。dp[i]錶示以i結尾的子序列的數量，從前往後找，dp[i]=2*dp[i-1]-dp[last]
#dp[i]=2*dp[i-1]-dp[last]。以s[i]結尾的子序列數量，是以s[i-1]結尾的子序列的數量+s[i-1]結尾的子序列的數量_尾部加上s[i]，再加上s[i]本身
#减去重複的，s[i]上一次出現之前的子序列的數量，再减去上一次出現的s[i]本身
#這個題只有1和0，分類討論，記錄上一次以1結尾的子序列的數量，和上一次以0結尾的子序列的數量。
# leetcode submit region begin(Prohibit modification and deletion)
class Solution:
    def numberOfUniqueGoodSubsequences(self, binary: str) -> int:
        count1 = 0
        count0 = 0
        if_has0 = 0
        for i in range(len(binary)):
            if binary[i] == "1":
                count1 = count1 + count0 + 1
            if binary[i] == "0":
                count0 = count0 + count1
                if_has0 = 1
        return (count1+count0+if_has0)%(10**9+7)

2262. 字符串的總引力

 與940.不同的子序列2 思考方式類似，從左到右遍曆，在前一個的末尾添加當前元素。

 

 

class Solution(object):
    def appealSum(self, s):
        """
        :type s: str
        :rtype: int
        """
        # dp[i]錶示以i結尾的子字符串總引力
        dp = [0 for _ in range(len(s)+1)]
        maps = {}
        for i in range(1,len(s)+1):
            #s[i-1]結尾的字符串一共i個
            dp[i] = dp[i-1] + i
            if s[i-1] in maps:
                last = maps[s[i-1]]
                #s[start:i-1],當start在上一次出現元素之前時，都要去重
                dp[i] = dp[i]  - last
            maps[s[i-1]] = i
        return sum(dp)

828. 統計子串中的唯一字符

思路同940

力扣

力扣

class Solution(object):
    def uniqueLetterString(self, s):
        """
        :type s: str
        :rtype: int
        """
        #以s[i]結尾的子串的唯一字符，和以s[i-1]結尾的子串的唯一字符，的關系
        #如果s[i]之前沒有出現過，以s[i-1]結尾的子串的唯一字符，都要加上1
        #如果s[i]之前出現過一次，出現的最後比特置是j，s[j:i]之前加一
        #如果s[i]之前出現過大於等於2次，出現的最後比特置是j1,j2，s[j:i]之前加一
        dp = [0 for _ in range(len(s)+1)]
        maps = collections.defaultdict(list)
        for i in range(1,len(s)+1):
            dp[i] = dp[i-1] + i 
            if s[i-1] in maps:
                last_list = maps[s[i-1]]
                if len(last_list) == 1:
                    dp[i] = dp[i] - 2*last_list[-1]
                else:
                    dp[i] = dp[i] - last_list[-1]-(last_list[-1] - last_list[-2])
            maps[s[i-1]].append(i)
        return sum(dp)

128. 最長連續序列

 set查詢o(1)

原网站

版权声明
本文为[林沖風雪山神廟]所创，转载请带上原文链接，感谢
https://yzsam.com/2022/173/202206221230105973.html

边栏推荐

猜你喜欢

随机推荐