力扣第1035题-不相交的线1.本题和力扣第1143题-最长公共子序列一模一样不能让线相交本质上就是不能走回头路相对顺序不能改变即公共子序列需要按顺序排列。完整代码如下1. int maxUncrossedLines(int* nums1, int nums1Size, int* nums2, int nums2Size) { 2. // 一维滚动dp数组dp[j]表示nums1前i个数字、nums2前j个数字能绘制的最多不相交连线 3. int dp[nums2Size 1]; 4. memset(dp, 0, sizeof(dp)); 5. 6. for (int i 1; i nums1Size; i){ 7. // pre存储二维dp[i-1][j-1]的值即本轮更新前的dp[j-1] 8. int pre dp[0]; 9. for (int j 1; j nums2Size; j){ 10. // 保存更新前dp[j]作为下一轮j1的pre 11. int cur dp[j]; 12. if (nums1[i - 1] nums2[j - 1]){ 13. // 数字相等可以连线数量等于左上角状态1 14. dp[j] pre 1; 15. } else { 16. // 数字不等继承上方或左侧更大的连线数 17. dp[j] fmax(dp[j], dp[j - 1]); 18. } 19. pre cur; 20. } 21. } 22. 23. return dp[nums2Size]; 24. }该算法时间复杂度为O(nums1Size * nums2Size)空间复杂度为O(nums2Size)。力扣第392题-判断子序列1.可以使用双指针t的指针cur2一直1s的指针cur1只有在两个指针所指字符相等的时候才1最后如果cur1 len1就说明s是t的子集否则就不是。完整代码如下1. bool isSubsequence(char* s, char* t) { 2. int len1 strlen(s); 3. int len2 strlen(t); 4. // s长度大于t不可能是子序列 5. if (len1 len2) return false; 6. 7. // cur1s匹配指针cur2t遍历指针 8. int cur1 0, cur2 0; 9. while (cur1 len1 cur2 len2){ 10. // 字符匹配s指针后移 11. if (s[cur1] t[cur2]){ 12. cur1; 13. } 14. // t指针持续后移 15. cur2; 16. } 17. 18. // s全部匹配完成则为子序列 19. if (cur1 len1) return true; 20. return false; 21. }该算法时间复杂度为O(m n)空间复杂度为O(1)m和n为字符串s和t的长度。2.本题也可以使用动态规划本质上和力扣第1143题-最长公共子序列一模一样只不过字符串s一定不会删除字符。最后只需要判断dp[len2]是否等于len1即可判断是否全部匹配。完整代码如下1. bool isSubsequence(char* s, char* t) { 2. int len1 strlen(s); 3. int len2 strlen(t); 4. // s更长一定不可能是子序列直接返回false 5. if (len1 len2) return false; 6. 7. // 一维滚动dp数组dp[j]代表s前i个字符、t前j个字符的最长公共子序列长度 8. int dp[len2 1]; 9. memset(dp, 0, sizeof(dp)); 10. for (int i 1; i len1; i){ 11. // pre保存二维dp[i-1][j-1]更新前左上角的值 12. int pre dp[0]; 13. for (int j 1; j len2; j){ 14. // 记录更新前dp[j]作为下一轮j1的pre 15. int cur dp[j]; 16. if (s[i - 1] t[j - 1]){ 17. // 字符匹配公共子序列长度 左上角值 1 18. dp[j] pre 1; 19. } else { 20. // 字符不匹配取上方旧值或左侧新值较大者 21. dp[j] fmax(dp[j], dp[j - 1]); 22. } 23. pre cur; 24. } 25. } 26. // 若最长公共子序列长度等于s全长说明s是t的子序列 27. return dp[len2] len1; 28. }该算法时间复杂度为O(m * n)空间复杂度为O(n)。