一些子序列问题
(持续补充)
最长上升子序列
题目
给定一个无序的整数数组,找到其中最长上升子序列的长度。
示例:
输入: [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() 空间复杂度 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%的用户
在纸上写明白,动态规划转移过程
然后倒序遍历返回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() ,空间复杂度
中心扩展法,很有趣的想法,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)次
时间复杂度,空间复杂度
最长回文串
给定一个包含大写字母和小写字母的字符串,找到通过这些字母构造成的最长的回文串。
在构造过程中,请注意区分大小写。比如 "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
网友评论