网站是怎么制作出来的,企业网站建设常见问题,二次元网站开发的意义,广州快速排名leetcode 300. 最长递增子序列
题目链接#xff1a;最长递增子序列
dp数组及下标的含义 dp[i]表示i之前包括i的以nums[i]结尾的最长递增子序列的长度递推公式 位置i的最长升序子序列等于j从0到i-1各个位置的最长升序子序列 1 的最大值 所以if (nums[i] nums[j]) dp[i]…leetcode 300. 最长递增子序列
题目链接最长递增子序列
dp数组及下标的含义 dp[i]表示i之前包括i的以nums[i]结尾的最长递增子序列的长度递推公式 位置i的最长升序子序列等于j从0到i-1各个位置的最长升序子序列 1 的最大值 所以if (nums[i] nums[j]) dp[i] max(dp[i], dp[j] 1)dp数组初始化 每一个i对应的dp[i]即最长递增子序列起始大小至少都是1遍历顺序 从前向后遍历
for (int i 1; i nums.size(); i) {for (int j 0; j i; j) {if (nums[i] nums[j]) dp[i] max(dp[i], dp[j] 1);}if (dp[i] result) result dp[i]; // 取长的子序列
}整体代码如下
class Solution {
public:int lengthOfLIS(vectorint nums) {if (nums.size() 1) return nums.size();vectorint dp(nums.size(), 1);int result 0;for (int i 1; i nums.size(); i) {for (int j 0; j i; j) {if (nums[i] nums[j]) dp[i] max(dp[i], dp[j] 1);}if (dp[i] result) result dp[i]; // 取长的子序列}return result;}
};时间复杂度: O(n^2) 空间复杂度: O(n)
leetcode 674. 最长连续递增序列
题目链接最长连续递增序列 本题要求子序列是连续递增所以只需要比较 nums[i]和 nums[i-1]
class Solution {
public:int findLengthOfLCIS(vectorint nums) {if (nums.size() 0) return 0;int result 1;vectorint dp(nums.size() ,1);for (int i 1; i nums.size(); i) {if (nums[i] nums[i - 1]) { // 连续记录dp[i] dp[i - 1] 1;}if (dp[i] result) result dp[i];}return result;}
};时间复杂度O(n) 空间复杂度O(n)
leetcode 718. 最长重复子数组
题目链接最长重复子数组
dp数组及下标的含义 dp[i][j] 以下标i - 1为结尾的A和以下标j - 1为结尾的B最长重复子数组长度为dp[i][j]确定递推公式 当A[i - 1] 和B[j - 1]相等的时候dp[i][j] dp[i - 1][j - 1] 1dp数组初始化 dp[i][0] 和dp[0][j]初始化为0遍历顺序 外层for循环遍历A内层for循环遍历B
版本一二维数组
class Solution {
public:int findLength(vectorint nums1, vectorint nums2) {vectorvectorint dp (nums1.size() 1, vectorint(nums2.size() 1, 0));int res 0;for (int i 1; i nums1.size(); i) {for (int j 1; j nums2.size(); j) {if (nums1[i - 1] nums2[j - 1]) {dp[i][j] dp[i - 1][j - 1] 1;}if (dp[i][j] res) res dp[i][j];}}return res;}
};时间复杂度O(n × m)n 为A长度m为B长度 空间复杂度O(n × m)
版本二滚动数组
dp[i][j]由dp[i - 1][j - 1]推出压缩为一维数组dp[j]由dp[j - 1]推出。 遍历B数组的时候就要从后向前遍历这样避免重复覆盖
class Solution {
public:int findLength(vectorint A, vectorint B) {vectorint dp(vectorint(B.size() 1, 0));int res 0;for (int i 1; i A.size(); i) {for (int j B.size(); j 0; j--) {if (A[i - 1] B[j - 1]) {dp[j] dp[j - 1] 1;} else dp[j] 0; // 注意这里不相等的时候要有赋0的操作if (dp[j] res) res dp[j];}}return res;}
};时间复杂度O(n × m)n 为A长度m为B长度 空间复杂度O(m)
