社保网站上怎么做减员,怎么加入电商平台卖货,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;}
};
