总结一下三道求子序列长度的题
1 最长递增子序列
300. 最长递增子序列
给你一个整数数组 nums ,找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如,[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
法一:动态规划(dp)
分析一波:
(1)dp数组的的含义:dp[i]表示长度为i+1(数组下标是从0开始的)数组的最长递增子序列长度是dp[i];
(2)dp数组的初始化:长度至少都是1;
(3)递推公式:
位置i的最长升序子序列等于j从0到i-1各个位置的最长升序子序列 + 1 的最大值,即
if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);
(4)遍历顺序:遍历顺序肯定是由前到后,递推公式也可以看出。
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
int len = nums.size();
if (len == 1) {
return len;
}
int res = 0; // 记录最长的
vector<int> dp(len, 1);
// dp[i]表示长度为i+1的数组,最长的递增子序列是dp[i]
dp[0] = 1;
// 递推公式:nums[i] > nums[j]时(i>j),dp[i] = max(dp[j] + 1, dp[i])
for (int i = 1; i < len; i++) {
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j]) {
dp[i] = max(dp[i], dp[j] + 1);
}
res = max(res, dp[i]);
}
}
return res;
}
};
法二:评论区
力扣
贴上代码,还没理解-_-!-_-!-_-!-_-!-_-!-_-!-_-!
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
int len = nums.size();
int maxL = 0;
vector<int> dp(len);
for (int i = 0; i < len; i++) {
int left = 0, right = maxL;
while (left < right) {
int mid = left + (right - left) / 2;
if (dp[mid] < nums[i]) {
left = mid + 1;
} else {
right = mid;
}
}
dp[left] = nums[i];
if (left == maxL) {
maxL++;
}
}
return maxL;
}
};
2 最长连续递增子序列
674. 最长连续递增序列
给定一个未经排序的整数数组,找到最长且 连续递增的子序列,并返回该序列的长度。
连续递增的子序列 可以由两个下标 l 和 r(l < r)确定,如果对于每个 l <= i < r,都有 nums[i] < nums[i + 1] ,那么子序列 [nums[l], nums[l + 1], ..., nums[r - 1], nums[r]] 就是连续递增子序列。
分析一波:
这里要的是连续递增,还是用动态规划解决。
(1)dp数组的的含义:dp[i]表示长度为i+1(数组下标是从0开始的)数组的最长连续递增子序列长度是dp[i];
(2)dp数组的初始化:长度至少都是1;
(3)递推公式:
nums[i + 1] > nums[i],那么以 i+1 为结尾的数组的连续递增的子序列长度 一定等于 以i为结尾的数组的连续递增的子序列长度 + 1 。即:
dp[i + 1] = dp[i] + 1;
(4)遍历顺序:遍历顺序:遍历顺序肯定是由前到后,同样的,递推公式也可以看出。
class Solution {
public:
int findLengthOfLCIS(vector<int>& nums) {
int len = nums.size();
vector<int> dp(len, 1);
// dp[i + 1] = dp[i] + 1;
int res = 1; // 记录最长的
for (int i = 0; i < len - 1; i++) {
if (nums[i + 1] > nums[i]) {
dp[i + 1] = dp[i] + 1;
}
res = max(res, dp[i + 1]);
}
return res;
}
};
3 最长连续序列
128. 最长连续序列
给定一个未排序的整数数组 nums ,找出数字连续的最长序列(不要求序列元素在原数组中连续)的长度。
请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
这个题是某次某个公司的笔试题,当时理解错题意了,没有做出来,好像只AC的一点点。
示例1
输入:nums = [100,4,200,1,3,2]
输出:4
解释:最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。
分析一下我当时犯的错误,以示例1为例。
示例1的结果是1,2,3,4。我当时想的是,要是后面还有10,12,14,16,18,...这样的序列,那该怎么求,看了这道题的解法才发现,让求的是差值为1的最长子序列???
代码
class Solution {
public:
int longestConsecutive(vector<int>& nums) {
int len = nums.size();
if (len == 0) {
return 0;
}
int res = 1; // 返回结果
int count = 1; // 计数
sort(nums.begin(), nums.end()); // 排序
for (int i = 1; i < len; i++) {
if (nums[i] == nums[i - 1]) {
continue;
}
if (nums[i] == nums[i - 1] + 1) {
count++;
res = max(res, count);
} else {
count = 1;
}
}
return res;
}
};
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)