子序列总结篇

发布于：2025-03-27 ⋅ 阅读:(55) ⋅ 点赞:(0)

leetcode系列

文章目录

提示：小白个人理解，如有错误敬请谅解！

一、300.最长递增子序列

  1. 首先是从一个序列中找到最长的子序列，最少都是1，因为本题的序列可以不连续，对每个数字都要从0开始检查一遍是否小于该数字，如果小于才更新当前dp的大小，并取dp[i]和dp[j]+1中较大的那一个
  2. 因为是在整个序列中找最长的，所以还需要额外的res来记录最大的dp[i]

代码如下：

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

二、674. 最长连续递增序列

  1. 和上面一样的，结果最少都是1，相对于上一个来说，由于是连续递增的，所以只需要和前面的一个比较就可以
  2. 同样由于是在整个序列中找最长的，要用res来保存最大的结果

代码如下：

class Solution {
public:
    int findLengthOfLCIS(vector<int>& nums) {
        if(nums.size()==1)return 1;
        int res=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]>res)res=dp[i];
        }
        return res;
    }
};

三、718. 最长重复子数组

  1. 两个数组里面万一没有相等的，则最少是0，判断两个数组中的公共最长的连续子序列，因为是连续的，所以只需要关注前一个，但是是二维的，所以是对角线方向上逐步+1，一旦不相等了就得从0开始+1
  2. 同样是是在整个序列中找最长的，要用res来保存最大的结果

代码如下：

class Solution {
public:
    int findLength(vector<int>& nums1, vector<int>& nums2) {
        int res=0;
        vector<vector<int>> dp(nums1.size()+1,vector<int>(nums2.size()+1,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;
    }
};

四、1143.最长公共子序列

  1. 这题的子序列也不是连续的，所以需要通过不相等时的赋值把之前的结果传递到后面，或者说模拟 把当前元素删除的过程，所以不相等时，dp[i][j]取dp[i-1][j]和dp[i][j-1]里面最大的那个，相等的时候也是在对角线方向上+1就行
  2. 由于通过不相等时的赋值把之前的结果传递到后面，所以不用res来记录最大值，直接取最末尾的就是最后的结果

代码如下：

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int res=0;
        vector<vector<int>> dp(text1.size()+1,vector<int>(text2.size()+1,0));
        for(int i=1;i<=text1.size();i++)
        {
            for(int j=1;j<=text2.size();j++)
            {
                if(text1[i-1]==text2[j-1])dp[i][j]=dp[i-1][j-1]+1;
                else dp[i][j]=max(dp[i][j-1],dp[i-1][j]);
                if(dp[i][j]>res)res=dp[i][j];
            }
        }
        return res;
    }
};

五、1035.不相交的线

  1. 由于线不能相交，也就是要保证元素间的相对顺序，其实就是找两个序列的最长公共子序列，和四一样的

代码如下：

class Solution {
public:
    int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
        int res=0;
        vector<vector<int>> dp(nums1.size()+1,vector<int>(nums2.size()+1,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;
                else dp[i][j]=max(dp[i][j-1],dp[i-1][j]);
                if(dp[i][j]>res)res=dp[i][j];
            }
        }
        return res;
    }
};

六、53. 最大子序和

  1. 求连续子序列的最大和，由于是连续的，只需要和后一个比较一下就行，是加上后一个元素更大还是直接用后一个元素更大（如果当前序列的和是负数则会减小子序列的总和）
  2. 由于没有进行结果传递，所以需要res来保存最大的值，res初始化为序列第一个数即可

代码如下：

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

七、392.判断子序列

  1. 判断子序列其实就是看看(四)两个序列的最长公共子序列 是不是那个目标子序列的长度，但是区别在于目标子序列是不可以删除的，所以仍然要传递结果，只不过传递一边的结果，当不相等时，dp[i][j]=dp[i][j-1]即可，相等的话还是在对角线的基础上+1
  2. 由于又是将前面的结果传递过来，所以右下角的结果就是最长公共子序列的长度，最后比较一下即可

代码如下：

class Solution {
public:
    bool isSubsequence(string s, string t) {
        vector<vector<int>> dp(s.size()+1,vector<int>(t.size()+1,0));
        for(int i=1;i<=s.size();i++)
        {
            for(int j=1;j<=t.size();j++)
            {
                if(s[i-1]==t[j-1])dp[i][j]=dp[i-1][j-1]+1;
                else dp[i][j]=dp[i][j-1];
            }
        }
        if(dp[s.size()][t.size()]==s.size())return true;
        return false;
    }
};

八、115.不同的子序列

  1. 不相等的时候，要把之前的结果传递过来，因为本题目标子序列用 j 来表示，所以只用动另外一边，即dp[i][j]=dp[i-1][j]，但是如果当前比较的结果相等，除了直接等于对角线上的前一个，还要加上dp[i-1][j]，即dp[i][j]=dp[i-1][j-1]+dp[i-1][j]
  2. 初始化的时候dp[i][0]表示当目标子序列为空时，另外一个序列的子序列包含目标子序列的个数，应该都填上1，而dp[0][j]表示当目标子序列不为空时，一个空集包含目标子序列的个数，那肯定是0
  3. 由于本题也是用了传递，所以最后右下角就是结果

代码如下：

class Solution {
public:
    int numDistinct(string s, string t) {
        vector<vector<uint64_t>> dp(s.size()+1,vector<uint64_t>(t.size()+1));
        for(int j=0;j<=t.size();j++)dp[0][j]=0;
        for(int i=0;i<=s.size();i++)dp[i][0]=1;
        for(int i=1;i<=s.size();i++)
        {
            for(int j=1;j<=t.size();j++)
            {
                if(s[i-1]==t[j-1])dp[i][j]=dp[i-1][j-1]+dp[i-1][j];
                else dp[i][j]=dp[i-1][j];
            }
        }
        return dp[s.size()][t.size()];
    }
};

九、583. 两个字符串的删除操作

  1. 由于是找最小的步数，则相等的时候什么都不用操作，把对角线上的前一个拿过来就可以，但是如果不相等的话就要进行删除操作，选择dp[i][j-1]和dp[i-1][j]中较少的那一个+1即可
  2. 初始话的时候dp[i][0]表示一个字符串要多少步才能变成空字符，答案是i，j也是同理
  3. 由于也进行了传递操作，右下角的值就是结果

代码如下：

class Solution {
public:
    int minDistance(string word1, string word2) {
        vector<vector<int>> dp(word1.size()+1,vector<int>(word2.size()+1,0));
        for(int i=0;i<=word1.size();i++)dp[i][0]=i;
        for(int j=0;j<=word2.size();j++)dp[0][j]=j;
        for(int i=1;i<=word1.size();i++)
        {
            for(int j=1;j<=word2.size();j++)
            {
                if(word1[i-1]==word2[j-1])dp[i][j]=dp[i-1][j-1];
                else dp[i][j]=min(dp[i][j-1]+1,dp[i-1][j]+1);
            }
        }
        return dp[word1.size()][word2.size()];
    }
};

也可以再用四中的最长公共子序列，统计出来之后用这两个字符串的长度减去两个最长公共子序列的长度也可以
代码如下：

class Solution {
public:
    int minDistance(string word1, string word2) {
        vector<vector<int>> dp(word1.size()+1,vector<int>(word2.size()+1,0));
        for(int i=1;i<=word1.size();i++)
        {
            for(int j=1;j<=word2.size();j++)
            {
                if(word1[i-1]==word2[j-1])dp[i][j]=dp[i-1][j-1]+1;
                else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
            }
        }
        return (word1.size()-dp[word1.size()][word2.size()])+(word2.size()-dp[word1.size()][word2.size()]);
    }
};

十、72. 编辑距离

  1. 找最小的步数，则相等的时候什么都不用操作，把对角线上的前一个拿过来就可以，但是如果不相等的话就要进行删除或者替换操作（增加操作其实就是相当于对另外一个序列进行删除操作），删除的话选择dp[i][j-1]和dp[i-1][j]中较少的那一个+1即可，还有一个是替换，即在dp[i-1][j-1]
    的基础上+1，所以是这三个操作里面选一个最小的
  2. 初始话的时候dp[i][0]表示一个字符串要多少步才能变成空字符，答案是i，j也是同理
  3. 由于也进行了传递操作，右下角的值就是结果

代码如下：

class Solution {
public:
    int minDistance(string word1, string word2) {
        vector<vector<int>> dp(word1.size()+1,vector<int>(word2.size()+1,0));
        for(int i=0;i<=word1.size();i++)dp[i][0]=i;
        for(int j=0;j<=word2.size();j++)dp[0][j]=j;
        for(int i=1;i<=word1.size();i++)
        {
            for(int j=1;j<=word2.size();j++)
            {
                if(word1[i-1]==word2[j-1])dp[i][j]=dp[i-1][j-1];
                else dp[i][j]=min(min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1])+1;
            }
        }
        return dp[word1.size()][word2.size()];
    }
};

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布