admin 管理员组文章数量: 1184232
力扣300.最长递增子序列
力扣674.最长连续递增子序列【easy】
力扣1143.最长公共子序列【medium】
力扣718.最长重复子数组【medium】
一、力扣300.最长递增子序列【medium】
题目链接：
视频链接：
题解链接：
1、思路
- 构造选 n u m s [ i ] nums[i] n u m s [ i ] 为子列的末尾元素，再遍历[1,i) ，选出 n u m s [ j ] < n u m s [ i ] nums[j] < nums[i] n u m s [ j ] < n u m s [ i ]
- d f s ( i ) dfs(i) df s ( i ) ：表示以 n u m s [ i ] nums[i] n u m s [ i ] 结尾的LIS长度
2、代码
1）记忆化搜索
- 时间复杂度： O ( n 2 ) O(n^2) O ( n 2 )
- 空间复杂度： O ( n ) O(n) O ( n )
classSolution:deflengthOfLIS(self, nums: List[int])->int:@cachedefdfs(i:int)->int:
res =0for j inrange(i):if nums[j]< nums[i]:
res =max(res, dfs(j))return res +1returnmax(dfs(i)for i inrange(len(nums)))- 时间复杂度： O ( n 2 ) O(n^2) O ( n 2 )
- 空间复杂度： O ( n ) O(n) O ( n )
classSolution:deflengthOfLIS(self, nums: List[int])->int:
n =len(nums)
f =[0]* n
for i, x inenumerate(nums):for j, y inenumerate(nums[: i]):if y < x:
f[i]=max(f[i], f[j])
f[i]+=1returnmax(f)- 时间复杂度： O ( n l o g n ) O(nlogn) O ( n l o g n ) ，二分法是 l o g n logn l o g n
- 空间复杂度： O ( n ) O(n) O ( n )
classSolution:deflengthOfLIS(self, nums: List[int])->int:
g =[]for x in nums:
j = bisect_left(g, x)if j ==len(g):
g.append(x)else:
g[j]= x
returnlen(g)3、代码问题
二、力扣674.最长连续递增子序列【easy】
题目链接：
1、思路
- 这题是连续！
- 可以用贪心更简单！！
- 时间复杂度： O ( n ) O(n) O ( n )
2、代码
1）贪心
classSolution:deffindLengthOfLCIS(self, nums: List[int])->int:
n =len(nums)
ans =1
count =1for i inrange(1, n):if nums[i -1]<nums[i]:
count +=1
ans =max(count, ans)else:
count =1return ans
2）dp：动态规划
classSolution:deffindLengthOfLCIS(self, nums: List[int])->int:
n =len(nums)
ans =1
f =[1]* n
for i inrange(1, n):if nums[i -1]< nums[i]:
f[i]= f[i -1]+1
ans =max(f[i], ans)return ans
三、力扣1143.最长公共子序列【medium】
题目链接：
视频链接：
题解链接：
1、思路
- 时间复杂度： O ( n m ) O(nm) O ( nm )
2、代码
1）记忆化搜索
classSolution:deflongestCommonSubsequence(self, text1:str, text2:str)->int:
m, n =len(text1),len(text2)@cachedefdfs(i:int, j:int)->int:if i <0or j <0:return0if text1[i]== text2[j]:return dfs(i -1, j -1)+1else:returnmax(dfs(i -1, j), dfs(i, j -1))return dfs(m -1, n -1)2）dp
classSolution:deflongestCommonSubsequence(self, text1:str, text2:str)->int:
m, n =len(text1),len(text2)
f =[[0]*(n +1)for _ inrange(m +1)]for i, x inenumerate(text1):for j, y inenumerate(text2):
f[i +1][j +1]= f[i][j]+1if x == y elsemax(f[i +1][j], f[i][j +1])return f[m][n]3）空间优化：一个数组
classSolution:deflongestCommonSubsequence(self, text1:str, text2:str)->int:
m, n =len(text1),len(text2)
f =[0]*(n +1)for x in text1:
pre =0for j, y inenumerate(text2):
tmp = f[j +1]
f[j +1]= pre +1if x == y elsemax(f[j], f[j +1])
pre = tmp #保证 pre 是 f 数组上一行的数据，不是当前行的数据。return f[n]四、力扣718.最长重复子数组【medium】
题目链接：
left =x300
视频链接：
1、思路
- 时间复杂度： O ( m ∗ n ) O(m * n) O ( m ∗ n )
2、代码
1）记忆化搜索
classSolution:deffindLength(self, nums1: List[int], nums2: List[int])->int:
m, n =len(nums1),len(nums2)
ans =0@cachedefdfs(i:int, j:int)->int:if i <0or j <0:return0if nums1[i]== nums2[j]:
count = dfs(i -1, j -1)+1else:
count =0nonlocal ans
ans =max(count, ans)return count
for i inrange(m):for j inrange(n):
dfs(i, j)return ans
2）dp
classSolution:deffindLength(self, nums1: List[int], nums2: List[int])->int:
m, n =len(nums1),len(nums2)
ans =0
f =[[0]*(n +1)for _ inrange(m +1)]for i, x inenumerate(nums1):for j, y inenumerate(nums2):# 当前字符相等时，继承左上方值 +1，否则重置为 0if x == y:
f[i +1][j +1]= f[i][j]+1
ans =max(f[i +1][j +1], ans)else:
f[i +1][j +1]=0# 不连续时直接置零return ans
3）空间优化：一个数组
classSolution:deffindLength(self, nums1: List[int], nums2: List[int])->int:
m, n =len(nums1),len(nums2)
ans =0
f =[0]*(n +1)for i, x inenumerate(nums1):
pre =0for j, y inenumerate(nums2):
tmp = f[j +1]# 当前字符相等时，继承左上方值 +1，否则重置为 0if x == y:
f[j +1]= pre +1
ans =max(f[j +1], ans)else:
f[j +1]=0# 不连续时直接置零
pre = tmp
return ans
版权声明：本文标题：SWF文件编辑与优化策略全揭秘：提升效率的实用工具推荐 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.roclinux.cn/b/1770629804a3535835.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论