网站建设项目创业计划书,微信网站开发登录,wordpress首页显示vip标签,廊坊网站制作服务300. 最长递增子序列
给你一个整数数组 nums #xff0c;找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列#xff0c;删除#xff08;或不删除#xff09;数组中的元素而不改变其余元素的顺序。例如#xff0c;[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子…300. 最长递增子序列
给你一个整数数组 nums 找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列删除或不删除数组中的元素而不改变其余元素的顺序。例如[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列
思路由题意得知子序列是可以删除数组中的元素的即一段长为s的序列的最长子序列可能与若干个元素都无关因此 长度为s的序列的最长子序列的状态依赖于在这之前的所有长度为123。。。s-1的状态。转移方程由于要求的是最长严格递增子序列那么不难想到如果当前的元素比遍历到的元素的元素大那么就可以将其放到该元素的后面形成一个严格递增子序列。既然如此dp数组的定义就定义为dp[i] 为 以 nums[i]结尾的最长子序列转移方程为 if nums[i] nums[j], dp[i] max(dp[i], dp[j] 1),初始化为1. 使用result来记录dp数组中的最大值。
class Solution:def lengthOfLIS(self, nums: List[int]) - int:dp [1 for _ in range(len(nums))]result 1for i in range(1, len(dp)):for j in range(i):if nums[i] nums[j]:dp[i] max(dp[i], dp[j] 1)result max(dp[i], result)return result 674. 最长连续递增序列
给定一个未经排序的整数数组找到最长且 连续递增的子序列并返回该序列的长度。
连续递增的子序列 可以由两个下标 l 和 rl r确定如果对于每个 l i r都有 nums[i] nums[i 1] 那么子序列 [nums[l], nums[l 1], ..., nums[r - 1], nums[r]] 就是连续递增子序列。
思路与上一题类似dp[i]的定义为 以nums[i]为结尾的连续递增子序列长度转移方程为当nums[i] nums[i-1], dp[i] dp[j] 1, 以result记录dp数组最大值
class Solution:def findLengthOfLCIS(self, nums: List[int]) - int:dp [1 for _ in range(len(nums))]result 1for i in range(1, len(dp)):if nums[i] nums[i-1]:dp[i] dp[i-1] 1result max(dp[i], result)return result718. 最长重复子数组
给两个整数数组 nums1 和 nums2 返回 两个数组中 公共的 、长度最长的子数组的长度 。
思路设置dp[i][j] 为 nums1 前i -1个元素 和 nums2 前 j -1个元素 的公共最长重复子数组那么转移方程为 if nums1[i-1] nums2[j-1] , dp[i][j] dp[i-1][j-1], 由于dp数组的设置遍历时由1开始len(nums1)1 结束 左闭右开
二维dp
class Solution:def findLength(self, nums1: List[int], nums2: List[int]) - int:dp [[0] * (len(nums2) 1) for _ in range(len(nums1) 1)]result 0for i in range(1, len(nums1) 1):for j in range(1, len(nums2) 1):if nums1[i-1] nums2[j-1]:dp[i][j] dp[i-1][j-1] 1result max(result, dp[i][j])return result
一维dp
class Solution:def findLength(self, nums1: List[int], nums2: List[int]) - int:dp [0] * (len(nums2) 1)result 0# 遍历数组 nums1for i in range(1, len(nums1) 1):# 倒序遍历数组 nums2for j in range(len(nums2), 0, -1):if nums1[i-1] nums2[j-1]:dp[j] dp[j-1] 1result max(dp[j], result)else:dp[j] 0return result
