如何在虚拟机中建设网站,搬瓦工快照恢复wordpress,郑州媒体网站定制开发,网站设计成品网站代码随想录算法训练营第五十二天| 300.最长递增子序列#xff0c;674. 最长连续递增序列#xff0c;718. 最长重复子数组 300.最长递增子序列674. 最长连续递增序列718. 最长重复子数组 300.最长递增子序列
题目链接#xff1a;最长递增子序列 这里是不用处理if nums[i] 674. 最长连续递增序列718. 最长重复子数组 300.最长递增子序列674. 最长连续递增序列718. 最长重复子数组 300.最长递增子序列
题目链接最长递增子序列 这里是不用处理if nums[i] nums[j]:的情况的直接默认了碰到这种情况就直接放弃有点奇怪但也说得通。 这样的话其实dp[i]并不是nums[:(i1)]最长严格递增子序列的长度而是 以nums[i]为结尾的递增子序列的长度
class Solution:def lengthOfLIS(self, nums: List[int]) - int:# dp[i] nums[:(i1)]最长严格递增子序列的长度dp [1] * len(nums)for i in range(1,len(nums)):for j in range(i):if nums[i] nums[j]:dp[i] max(dp[i],dp[j]1)#print(dp)return max(dp)674. 最长连续递增序列
题目链接最长连续递增序列 和上一题一样这里的dp[i]其实是以nums[i]为结尾的连续递增子序列的长度并不是nums[:(i1)]里的最长连续递增子序列的长度
class Solution:def findLengthOfLCIS(self, nums: List[int]) - int:# dp[i] nums[:(i1)]中最长且连续递增的子序列dp [1]*len(nums)for i in range(1,len(nums)):if nums[i] nums[i-1]:dp[i] dp[i-1]1return max(dp)718. 最长重复子数组
题目链接最长重复子数组
i/j3214711213112213
这个题的顺序是斜着走的只要能保证左上方是遍历过的就可以了。
class Solution:def findLength(self, nums1: List[int], nums2: List[int]) - int:#dp[i][j] nums1[:i]和nums2[:j]的两个数组中公共的长度最长的子数组的长度dp [[0]*len(nums2) for _ in range(len(nums1))]m 0for i in range(len(nums1)):if nums1[i] nums2[0]:dp[i][0] 1m 1for j in range(len(nums2)):if nums2[j] nums1[0]:dp[0][j] 1m 1for i in range(1,len(nums1)):for j in range(1,len(nums2)):if nums1[i] nums2[j]:dp[i][j] dp[i-1][j-1]1m max(dp[i][j],m)#print(dp)#print(m)return m
