域名和网站建设实训报告,微信文章 wordpress,网站排名工具,怎么做自己的手机网站刷题记录 *1143. 最长公共子序列1035. 不相交的线53. 最大子数组和392. 判断子序列 *1143. 最长公共子序列
leetcode题目地址
本题和718. 最长重复子数组相似#xff0c;只是本题不要求连续#xff0c;需要记录前面最长的子序列#xff0c;在此基础上累计长度。
dp[i][j]… 刷题记录 *1143. 最长公共子序列1035. 不相交的线53. 最大子数组和392. 判断子序列 *1143. 最长公共子序列
leetcode题目地址
本题和718. 最长重复子数组相似只是本题不要求连续需要记录前面最长的子序列在此基础上累计长度。
dp[i][j]表示到text1串i-1之前与text2到j-1之前的最长公共子序列的长度。
时间复杂度 O ( n 2 ) O(n^2) O(n2) 空间复杂度 O ( n 2 ) O(n^2) O(n2)
// c
class Solution {
public:int longestCommonSubsequence(string text1, string text2) {vectorvectorint dp(text1.size()1, vectorint(text2.size()1, 0));int i,j;for(i1; itext1.size(); i){for(j1; jtext2.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[i-1][j-1];}
};1035. 不相交的线
leetcode题目地址
本题和上题完全一致。
时间复杂度 O ( n 2 ) O(n^2) O(n2) 空间复杂度 O ( n 2 ) O(n^2) O(n2)
// c
class Solution {
public:int maxUncrossedLines(vectorint nums1, vectorint nums2) {vectorvectorint dp(nums1.size()1, vectorint(nums2.size()1, 0));int i,j;for(i1; inums1.size(); i){for(j1; jnums2.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[i-1][j-1];}
};53. 最大子数组和
leetcode题目地址
dp[i]表示在下标i之前的最大子数组和。这里需要注意题目要求子数组最少包含一个元素因此不能将子序列和跟0比而要跟当前元素比表示从当前位置开始为子数组头。
时间复杂度 O ( n ) O(n) O(n) 空间复杂度 O ( n ) O(n) O(n)
// c
class Solution {
public:int maxSubArray(vectorint nums) {vectorint dp(nums.size(), 0);int i, resnums[0];dp[0] nums[0];for(i1; inums.size(); i){dp[i] max(nums[i], dp[i-1] nums[i]);if(dp[i]res) res dp[i];}return res;}
};392. 判断子序列
leetcode题目地址
时间复杂度 O ( n ) O(n) O(n) 空间复杂度 O ( 1 ) O(1) O(1)
// c
class Solution {
public:bool isSubsequence(string s, string t) {if(t.size()s.size()) return false;int last 0;for(int i0; is.size(); i){bool flag false;for(int jlast; jt.size(); j){if(s[i]t[j]) {flag true;last j1;break;}}if(!flag) return false;}return true;}
};
