代码随机化算法训练营第 50 天

题目：1143.最长公共子序列、1035.不相交的线、53. 最大子序和、392.判断子序列

参考链接：代码随想录

1143.最长公共子序列

思路：本题要注意**子序列和子数组的区别：子数组必须是连续的，子序列可以不连续，比如abcde的字序列可以为ace。**同样dp五部曲，dp数组，dp[i][j]表示text1[0,i-1]和text2[0,j-1]的最长公共子序列长度，这里设置为i-1和j-1同样是方便初始化，和上一题子数组相同；递推公式，当text1[i-1]和text2[j-1]相同时，dp[i][j]=dp[i-1][j-1]+1，不同时，那么就在text1[0,i-2]和text2[0,j-1]以及text1[0,i-1]和text2[0,j-2]中找最大的，即dp[i][j]=max(dp[i-1][j],dp[i][j-1])，注意这里与上一题子数组的区别，上一题对于不等的情况没有任何操作，依旧是初始值0，因为只要不等那么一定构不成连续的子数组；初始化，全部初始化为0，由于我们对dp数组预留了第一行和第一列，不需要特别初始化，在递推公式计算text1[0]和text2[0]时，可以直接根据是否相同往后推出来；遍历顺序，顺序遍历；举例略。本题无需ans，因为遍历的过程中最大值会逐渐往后传递。时间复杂度O(mn)。

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        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-1][j],dp[i][j-1]);
                }
            }
        }
        return dp[text1.size()][text2.size()];
    }
};

1035.不相交的线

思路：本题实际上就是最长公共子序列，因为线不相交就相当于序列的顺序不能打乱，方法同上题。dp五部曲：dp数组，dp[i][j]表示nums1[0…i-1]和nums2[0…j-1]的最长公共子序列长度；递推公式，当nums1[i-1]==nums2[j-1]时，dp[i][j]=dp[i-1][j-1]+1，不相等时，dp[i][j]=max(dp[i-1][j],dp[i][j-1])；初始化，全部为0；遍历顺序，顺序遍历；举例略。时间复杂度O(mn)。

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

53. 最大子序和

思路：首先回顾一下贪心算法，本题是求最大连续子数组和，可以直接从左往右加，当遇到和为负数的时候，直接结果置0，从下一位开始重新加，因为负数只会拉低结果，这就是贪心的点。然后是dp方法，dp五部曲：dp数组，dp[i]表示以nums[i]结尾的最大子序列和；递推公式，本题求的是最大和，所以递推的时候取最大值，推出dp[i]有两种方式，首先是加上前面的dp[i-1]+nums[i]，或者直接重新开始，即nums[i]，其实看dp[i-1]的正负即可，不过这样有一点贪心的味道在里面；初始化，dp[0]初始化为nums[0]；遍历顺序，顺序遍历；举例略。注意返回值不是最终的结果，而是整个dp数组的最大值，我们在遍历过程中记录。时间复杂度O(n)。

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

392.判断子序列

思路：先说说比较好想到的双指针法，标答里没写，即用两个指针i,j分别指向s和t，然后从头开始往后匹配，如果相等，则将i++，开始匹配t的下一位，不管相不相等每次匹配后都要j++，即t需要从头匹配到结尾，如果遍历完t后s没有遍历完，则说明不是子串，否则是子串。时间复杂度O(n)。

class Solution {
public:
    bool isSubsequence(string s, string t) {
        int i,j;
        for(i=0,j=0;i<s.size(),j<t.size();j++){
            if(s[i]==t[j]){
                i++;
            }
        }
        return i==s.size();
    }
};

然后是dp方法，本题是编辑距离的入门，dp五部曲：dp数组，dp[i][j]表示s以i-1结尾，t以j-1结尾的相同子序列长度，用i-1和j-1的原因同最长子数组那题，方便初始化；递推公式，如果s[i-1]与t[j-1]相等，则说明找到了一个相同字符，则dp[i][j]=dp[i-1][j-1]+1，如果不相等，说明t需要删除这个元素，继续往后匹配，即删除t[j-1]，则这时的结果即为前一位的匹配结果dp[i][j-1]，可以发现这里和相同子序列那题一样，只不过本题只能删t的元素；初始化，全部为0；遍历顺序，顺序遍历；举例略。时间复杂度O(mn)。双指针的复杂度低一点。

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];
                }
            }
        }
        return dp[s.size()][t.size()]==s.size();
    }
};