算法刷题记录 Day45

算法刷题记录 Day45

Date: 2024.04.12

lc 718. 最长重复子数组

class Solution {
public:
    int findLength(vector<int>& nums1, vector<int>& nums2) {
        // 暴力思路：两重循环分别确定两个数组的起始位置，然后再一重循环确定该位置的公共长度；
        // dp. 如何从子问题推出？
        // dp[i][j]表示nums1[i]为结尾的子数组和nums2[j]为结尾的子数组的最大长度
        // dp[i][j] = dp[i-1][j-1] + 1 if(nums1[i] == nums2[j]) else 0;
        int n = nums1.size();
        int m = nums2.size();
        vector<vector<int>> dp(n, vector<int>(m, 0));
        // 初始化: dp[0][j] 和 dp[i][0];
        int max_len = 0;
        for(int i=0; i<n; i++){
            if(nums1[i] == nums2[0]){
                dp[i][0] = 1;
                max_len = 1;
            }
        }
        for(int j=0; j<m; j++){
            if(nums1[0] == nums2[j]){
                dp[0][j] = 1;
                max_len = 1;
            }
        }
      
        for(int i=1; i<n; i++){
            for(int j=1; j<m; j++){
                if(nums1[i] == nums2[j]){
                    dp[i][j] = dp[i-1][j-1] + 1;
                    max_len = max(max_len, dp[i][j]);
                }
                else{
                    dp[i][j] = 0;
                }
            }
        }

        return max_len;
    }
};

lc 674. 最长连续递增序列

class Solution {
public:
    int findLengthOfLCIS(vector<int>& nums) {
        // 1. 暴力：搜索每个节点作为起点；
        // 2. 双指针;
        // 3. dp
        // dp[i]表示以nums[i]结尾的最长子序列长度；
        // dp[i] = dp[i-1] + 1 if(nums[i] > nums[i-1]) else 1;
        int n = nums.size();
        vector<int> dp(n, 1);
        int max_len = 1;
        for(int i=1; i<n; i++){
            if(nums[i] > nums[i-1]){
                dp[i] = dp[i-1] + 1;
                max_len = max(max_len, dp[i]);
            }
            else{
                dp[i] = 1;
            }
        }
        return max_len;
    }
};

// 双指针
class Solution {
public:
    int findLengthOfLCIS(vector<int>& nums) {
        // 1. 暴力：搜索每个节点作为起点；
        // 2. 双指针
        int n = nums.size();
        int right = 1;
        int left = 0;
        int max_len = 1;
        while(right < n){
            if(nums[right] > nums[right-1]){
                right++;
                max_len = max(max_len, right-left);
            }
            else{
                left = right;
                right = right+1;
            }
        }
        return max_len;
    }
};

lc 300. 最长递增子序列

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        // 1.回溯. 不能跳过局部最优。pass
        // dp.
        int n = nums.size();
        //* dp[i] 表示以nums[i]结尾的最长子序列长度。
        vector<int> dp(n);   // (最长长度，当前最大值)
        dp[0] = 1;
        int max_len = 1;
        // dp[i] = for(j < i) max(dp[i], dp[j]+1);
        for(int i=1; i<n; i++){
            dp[i] = 1;  // 以任何值结尾的，长度至少为1。
            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]);
        }

        // for(int i=0; i<n; i++){
        //     cout<<"i:"<<i<<", dp[i]:"<<dp[i]<<endl;
        // }
        return max_len;
        
    }
};