子序列问题

2020-11-18 本文已影响0人锦绣拾年

一些子序列问题

（持续补充）

最长上升子序列

题目

给定一个无序的整数数组，找到其中最长上升子序列的长度。

示例:

输入: [10,9,2,5,3,7,101,18]
输出: 4 
解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。
说明:

可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。
你算法的时间复杂度应该为 O(n2) 。
进阶: 你能将算法的时间复杂度降低到 O(n log n) 吗?

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-increasing-subsequence
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

dp数组，每一个数组记录前面最长的上升序列长度。

和标程对比

标程在第一层循环i时，append数字
标程返回 max(dp)

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        dp = [1 for i in range(len(nums))]
        if len(nums)==0:
            return 0
        if len(nums)==1:
            return 1
        for i in range(1,len(nums)):
            for j in range(0,i):
                if nums[i]>nums[j]:
                    dp[i]=max(dp[j]+1,dp[i])
        dp.sort()
        # print(dp)
        return dp[len(nums)-1]

时间复杂度O( $n^2$ ) 空间复杂度 O(n)

这个题这个解法不难，主要是贪心算法+二分查找的思想还没弄清楚

最长公共子序列

题目

1143. 最长公共子序列
给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。

若这两个字符串没有公共子序列，则返回 0。

 

示例 1:

输入：text1 = "abcde", text2 = "ace" 
输出：3  
解释：最长公共子序列是 "ace"，它的长度为 3。
示例 2:

输入：text1 = "abc", text2 = "abc"
输出：3
解释：最长公共子序列是 "abc"，它的长度为 3。
示例 3:

输入：text1 = "abc", text2 = "def"
输出：0
解释：两个字符串没有公共子序列，返回 0。

题解

执行用时：360 ms, 在所有 Python3 提交中击败了95.75%的用户

内存消耗：20.9 MB, 在所有 Python3 提交中击败了51.62%的用户

在纸上写明白，动态规划转移过程

$if \quad i==j,\quad dp(i,j)=dp(i+1,j+1)+1$

$if \quad text[i] \neq text[j] \quad dp(i,j)=max(dp(i+1,j),dp(i,j+1))$

然后倒序遍历返回dp[0][0]

(不过倒序有点奇怪，也可以正序，返回dp[n-1][n-1])

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        if len(text1)==0 or len(text2)==0:
            return 0
        t1 = len(text1)
        t2 = len(text2)
        dp =[[0]*t2 for i in range(t1)]#t1横 t2 纵
        # for i in range(t1):
        #     if text1[i]==text2[t2-1]:
        #         dp[i][t2-1]=1
        # for i in range(t2):
        #     if text2[i]==text1[t1-1]:
        #         dp[t1-1][i]=1
        i=t1-2
        j=t2-2
        if text1[t1-1]==text2[t2-1]:
            dp[t1-1][t2-1]=1
        while i>=0:
            if text1[i]==text2[t2-1]:
                dp[i][t2-1]=1
            else:
                dp[i][t2-1]=dp[i+1][t2-1]
            i-=1
        while j>=0:
            if text2[j]==text1[t1-1]:
                dp[t1-1][j]=1
            else:
                dp[t1-1][j]=dp[t1-1][j+1]
            j-=1
        # print(dp)
        i=t1-2
        j=t2-2

        while i >=0:
            while j>=0:
                if text1[i]==text2[j]:
                    dp[i][j]=dp[i+1][j+1]+1
                else:
                    dp[i][j] = max(dp[i][j+1],dp[i+1][j])
                j-=1
            i-=1
            j=t2-2
        # print(dp)
        return dp[0][0]

返回最长回文子串

题目

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1：

输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
示例 2：

输入: "cbbd"
输出: "bb"

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-palindromic-substring
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

之前用C++写过，这里用python写。

dp数组存放，子问题字符串是否是回文子串。
存放目前回文子串最长是多少，以及开始位置。
在纸上把表格画出来会比较清楚

同样的算法，C++正常，

执行用时：300 ms, 在所有 C++ 提交中击败了49.40%的用户

内存消耗：11.5 MB, 在所有 C++ 提交中击败了67.46%的用户

python超时。

class Solution:
    def longestPalindrome(self, s: str) -> str:
        if not s:
            return ""
        dp = [[0]*len(s) for i in range(len(s))]
        res = s[0]
        maxnum = 1
        index = 0
        #dp这里记录长度，其实可以记录是否
        for i in range(len(s)):
            dp[i][i]=1
            if i+1<len(s):
                if s[i]==s[i+1]:
                    dp[i][i+1] = 1
                    maxnum = 2
                    index =i
        i = 3
        while i<=len(s):
            j=0
            while j+i-1<=len(s)-1:
                je=j+i-1
                if s[j]==s[je] and dp[j+1][je-1]==1:#子串是的话ok，子串不是的话木有任何用
                    dp[j][je]=1
                    maxnum = i
                    index =j
                j+=1              
            i+=1

        res = s[index:index+maxnum]
        return res

时间复杂度 O( $n^2$ ) ，空间复杂度 $O(n^2)$

中心扩展法，很有趣的想法，python没有超时：

class Solution:
    def expandAroundCenter(self, s, left, right):
        while left >= 0 and right < len(s) and s[left] == s[right]:#通过while从1开始扩展
            left -= 1
            right += 1
        return left + 1, right - 1

    def longestPalindrome(self, s: str) -> str:
        start, end = 0, 0
        for i in range(len(s)):
            left1, right1 = self.expandAroundCenter(s, i, i)
            left2, right2 = self.expandAroundCenter(s, i, i + 1)
            if right1 - left1 > end - start:
                start, end = left1, right1
            if right2 - left2 > end - start:
                start, end = left2, right2
        return s[start: end + 1]

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/longest-palindromic-substring/solution/zui-chang-hui-wen-zi-chuan-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

长度为 1 和 2 的回文中心分别有 n和 n-1个，每个回文中心最多会向外扩展O(n)次

时间复杂度 $O(n^2)$ ,空间复杂度 $O(1)$

最长回文串

给定一个包含大写字母和小写字母的字符串，找到通过这些字母构造成的最长的回文串。

在构造过程中，请注意区分大小写。比如 "Aa" 不能当做一个回文字符串。

注意:
假设字符串的长度不会超过 1010。

示例 1:

输入:
"abccccdd"

输出:
7

解释:
我们可以构造的最长的回文串是"dccaccd", 它的长度是 7。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-palindrome
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

很无聊的一个题，然后我还把题意想的比较复杂。

class Solution:
    def longestPalindrome(self, s: str) -> int:
        c_dict = {}
        for i in range(len(s)):
            if s[i] in c_dict.keys():
                c_dict[s[i]]+=1
            else:
                c_dict[s[i]]=1
        count = 0
        maxodd=0
        # print(c_dict)
        for key,value in c_dict.items():
            if value%2==0:
                count+=value
            elif maxodd==0:
                maxodd+=1
                count+=value
            else:
                count+=value-1
                

        # count = count+maxodd
        return count