代码随想录算法训练营第52天 |300.最长递增子序列、674. 最长连续递增序列、718. 最长重复子数组

TFTree 发布于 2023-03-28 2,106 次阅读

AI 摘要

Sorry, I need the full text of the article to generate an excerpt. Please provide me with the full text.

300. 最长递增子序列 - 力扣（Leetcode）

思路:

  • 使用动态规划

    1. 确定dp数组以及下标的含义

      • dp[i]的定义为：到i为止包括i以nums[i]为结尾的递增子序列长度

    2. 确定递推公式

      // 状态转移方程
// 要逐个比较nums[i]和nums[i]之前的所有元素
// 如果nums[i]比nums[i]之前的元素要大
// 那么就取dp[i]和dp[j] + 1中更大的一个
// 因为如果nums[i] > nums[j]
// 就说明nums[i]可以排在nums[j]后面
for(int j = 0; j < i; ++j) {
    if(nums[i] > nums[j]) {
        dp[i] = max(dp[i], dp[j] + 1);
    }
}

    3. dp数组如何初始化

      // 因为默认结果最小是1，所以全部初始化为1
vector<int> dp(nums.size(), 1);
int ans = 1;

    4. 确定遍历顺序

      // 从 i = 1 开始往后遍历，因为 i = 0 已经初始化过了，同时要找出dp[i]中最大的一个作为答案
// 因为dp[i]的意思不是到i为止的递增子序列最大值，而是以nums[i]为结尾的递增子序列最大值

我的AC代码

// 时间复杂度O(n2),空间复杂度O(n)
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        vector<int> dp(nums.size(), 1);
        int ans = 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);
                }
            }
            ans = max(dp[i], ans);
        }
        return ans;
    }
};

标准答案

// 时间复杂度O(n2),空间复杂度O(n)
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        if (nums.size() <= 1) return nums.size();
        vector<int> 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;
    }
};

674. 最长连续递增序列 - 力扣（Leetcode）

思路:

  • 使用动态规划

    1. 确定dp数组以及下标的含义

      • dp[i]的定义为：以nums[i]为结尾的最长连续子序列长度

    2. 确定递推公式

      // 状态转移方程
if(nums[i] > nums[i - 1]) {
    dp[i] = dp[i - 1] + 1;
}
// 找出其中最大的值
ans = max(ans, dp[i]);

    3. dp数组如何初始化

      // 因为默认最小为1，所以全部初始化为1
vector<int> dp(nums.size(), 1);
// 用来记录答案
int ans = 1;

    4. 确定遍历顺序

      // 从 i = 1 开始往后遍历

我的AC代码

高空间复杂度

// 时间复杂度O(n),空间复杂度O(n)
class Solution {
public:
    int findLengthOfLCIS(vector<int>& nums) {
        vector<int> dp(nums.size(), 1);
        int ans = 1;
        for(int i = 1; i < nums.size(); ++i) {
            if(nums[i] > nums[i - 1]) {
                dp[i] = dp[i - 1] + 1;
            }
            ans = max(ans, dp[i]);
        }
        return ans;
    }
};

优化空间复杂度

// 时间复杂度O(n),空间复杂度O(1)
class Solution {
public:
    int findLengthOfLCIS(vector<int>& nums) {
        int dp = 1;
        int ans = 1;
        for(int i = 1; i < nums.size(); ++i) {
            if(nums[i] > nums[i - 1]) {
                dp++;
            }
            else {
                dp = 1;
            }
            ans = max(ans, dp);
        }
        return ans;
    }
};

标准答案

// 时间复杂度O(n),空间复杂度O(n)
class Solution {
public:
    int findLengthOfLCIS(vector<int>& nums) {
        if (nums.size() == 0) return 0;
        int result = 1;
        vector<int> 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;
    }
};

718. 最长重复子数组 - 力扣（Leetcode）

思路:

  • 使用动态规划

    1. 确定dp数组以及下标的含义

      • dp[i][j]的定义为：以nums1[i - 1]和nums2[j - 1]为结尾的最长重复子数组长度(为了方便写代码，具体可参考标准答案版本一和版本三的代码区别)

    2. 确定递推公式

      // 状态转移方程
// 当nums1[i - 1] == nums2[j - 1]时
// 要增加dp[i][j]所代表的最长重复子数组长度
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;
        }
        ans = max(ans, dp[i][j]);
    }
}

    3. dp数组如何初始化

      // 因为要考虑两个数组的所有情况
// 所以使用二维数组
vector< vector<int> > dp(nums1.size() + 1, vector<int>(nums2.size() + 1, 0));
// 用来存储最大的答案
int ans = 0;

    4. 确定遍历顺序

      // 因为dp[i][j]与 i - 1有关
// 所以要从 i = 1 和 j = 1 从前往后开始遍历

我的AC代码

// 时间复杂度：O(n × m)，n 为A长度，m为B长度
// 空间复杂度：O(n × m)
class Solution {
public:
    int findLength(vector<int>& nums1, vector<int>& nums2) {
        vector< vector<int> > dp(nums1.size() + 1, vector<int>(nums2.size() + 1, 0));
        int ans = 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;
                }
                ans = max(ans, dp[i][j]);
            }
        }
        return ans;
    }
};

标准答案

高空间复杂度(普通做法)

// 版本一
// 时间复杂度：O(n × m)，n 为A长度，m为B长度
// 空间复杂度：O(n × m)
class Solution {
public:
    int findLength(vector<int>& nums1, vector<int>& nums2) {
        vector<vector<int>> dp (nums1.size() + 1, vector<int>(nums2.size() + 1, 0));
        int result = 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] > result) result = dp[i][j];
            }
        }
        return result;
    }
};

滚动数组

// 版本二
// 时间复杂度：O(n × m)，n 为A长度，m为B长度
// 空间复杂度：O(m)
class Solution {
public:
    int findLength(vector<int>& A, vector<int>& B) {
        vector<int> dp(vector<int>(B.size() + 1, 0));
        int result = 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] > result) result = dp[j];
            }
        }
        return result;
    }
};

不位移版本

即dp[i][j]代表以nums1[i]和nums2[j]为结尾的最长重复子数组长度

// 版本三
// 时间复杂度：O(n × m)，n 为A长度，m为B长度
// 空间复杂度：O(n × m)
class Solution {
public:
    int findLength(vector<int>& nums1, vector<int>& nums2) {
        vector<vector<int>> dp (nums1.size() + 1, vector<int>(nums2.size() + 1, 0));
        int result = 0;

        // 要对第一行，第一列经行初始化
        for (int i = 0; i < nums1.size(); i++) if (nums1[i] == nums2[0]) dp[i][0] = 1;
        for (int j = 0; j < nums2.size(); j++) if (nums1[0] == nums2[j]) dp[0][j] = 1;

        for (int i = 0; i < nums1.size(); i++) {
            for (int j = 0; j < nums2.size(); j++) {
                if (nums1[i] == nums2[j] && i > 0 && j > 0) { // 防止 i-1 出现负数
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }
                if (dp[i][j] > result) result = dp[i][j];
            }
        }
        return result;
    }
};