代码随想Day52 | 300.最长递增子序列、674. 最长连续递增序列、718. 最长重复子数组

发布时间:2023年12月29日

300.最长递增子序列

这道题目的重点在于动态数组的定义

dp[i]:以nums[i]为结尾的最长递增子序列,因为这样定义可以进行递推;

递推:j从0-i进行对比,如果nums[i]大于nums[j],dp[i]=dp[j]+1;

初始化:所有的元素向初始化为1;

遍历顺序:从前到后;

详细代码如下:

class Solution {
public:
int lengthOfLIS(vector<int>& nums) 
{
    if(nums.size()==0) return 0;
    vector<int>dp(nums.size(), 1); //init as 1
    int max_len = 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);
        }
        max_len = max(max_len, dp[i]);
    }
    return max_len;
}
};

674.?最长连续递增序列

这道题的相比上一题,因为是连续递增,所以只需要和前一个num[i-1]相比即可,不再进行详细分析,详细代码如下:

class Solution {
public:
int findLengthOfLCIS(vector<int>& nums)
{
    if(nums.size()==0) return 0;
    vector<int>dp(nums.size(), 1);
    int max_len = 1;
    for(int i = 1; i < nums.size(); i++) 
    {
        if (nums[i] > nums[i - 1]) dp[i] = dp[i - 1] + 1;
        max_len = max(max_len, dp[i]);
    }
    return max_len;
}

};

718.?最长重复子数组

这道题是对两个数组进行判断,因此需要二维数组,分析如下:

dp[i][j]:以A[i-1]为结尾和以B[j-1]为结尾的数组的最长重复子数组长度;i-1的结尾的原因,是这样初始化方便写,而不需要进行额外的判断。

递推:如果两个值相等,则dp[i][j]=dp[i-1][j-1];

初始化:根据递推公式,dp[0][0]应该是0,否则后续就无法得到想要的状态结果;

遍历:进行两层嵌套,从前往后即可;

详细代码如下:

class Solution {
public:
int findLength(vector<int>& nums1, vector<int>& nums2) 
{
    //二维dp
    //dp[i][j]:以A的i-1结尾,B的j-1结尾的最长重复长度
    //注意这里是为了初始化更方便
    vector<vector<int>>dp(nums1.size()+1, vector<int>(nums2.size() + 1, 0));
    int max_len = 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;
            max_len = max(max_len, dp[i][j]);
        }
    }
    return max_len;
}

};

注意,上述代码可以进行空间优化,因为dp[i][j]仅和左上角元素有关,所以可以压缩维度,把i维度压缩,运用滚动数组即可,要注意的是同01背包问题一样,为了不把数据踩踏,里层的循环需要逆向,这样就不会篡改上一层的数据导致错误。

详细代码如下:

class Solution {
public:
int findLength(vector<int>& nums1, vector<int>& nums2)
{
    vector<int>dp(nums2.size() + 1, 0); //压缩第一个维度
    int max_len = 0;
    for (int i = 1; i <= nums1.size(); i++) 
    {
        for (int j =nums2.size(); j >= 1; j--) //防止踩踏数据
        {
            if (nums1[i - 1] == nums2[j - 1]) dp[j] = dp[j - 1] + 1;
            else dp[j] = 0; //不相等需要赋值以便下次使用
            max_len = max(max_len, dp[j]);
        }
    }
    return max_len;

}
文章来源:https://blog.csdn.net/juantingliu_01/article/details/135297635
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。