深圳网站优化搜索,好的网站你知道,代理招商平台,网页设计实训总结600字1143.最长公共子序列
题目要求#xff1a;给定两个字符串 text1 和 text2#xff0c;返回这两个字符串的最长公共子序列的长度。
一个字符串的 子序列 是指这样一个新的字符串#xff1a;它是由原字符串在不改变字符的相对顺序的情况下删除某些字符#xff08;也可以不删…1143.最长公共子序列
题目要求给定两个字符串 text1 和 text2返回这两个字符串的最长公共子序列的长度。
一个字符串的 子序列 是指这样一个新的字符串它是由原字符串在不改变字符的相对顺序的情况下删除某些字符也可以不删除任何字符后组成的新字符串。
例如ace 是 abcde 的子序列但 aec 不是 abcde 的子序列。两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。
若这两个字符串没有公共子序列则返回 0。
示例 1:
输入text1 abcde, text2 ace输出3解释最长公共子序列是 ace它的长度为 3。
思路
这里不要求子序列是连续的。
dp[i][j]长度为[0, i - 1]的字符串text1与长度为[0, j - 1]的字符串text2的最长公共子序列为dp[i][j]。这样能够简化数组在第一行和第一列的初始化逻辑。
主要就是两大情况 text1[i - 1] 与 text2[j - 1]相同text1[i - 1] 与 text2[j - 1]不相同
如果text1[i - 1] 与 text2[j - 1]相同那么找到了一个公共元素所以dp[i][j] dp[i - 1][j - 1] 1;
如果text1[i - 1] 与 text2[j - 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]);
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]);
}
class Solution {
public:int longestCommonSubsequence(string text1, string text2) {vectorvectorint dp(text1.size() 1, vectorint(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.不相交的线
题目要求我们在两条独立的水平线上按给定的顺序写下 A 和 B 中的整数。
现在我们可以绘制一些连接两个数字 A[i] 和 B[j] 的直线只要 A[i] B[j]且我们绘制的直线不与任何其他连线非水平线相交。
以这种方法绘制线条并返回我们可以绘制的最大连线数。 思路
直线不能相交这就是说明在字符串A中 找到一个与字符串B相同的子序列且这个子序列不能改变相对顺序只要相对顺序不改变链接相同数字的直线就不会相交。
这么分析完之后大家可以发现本题说是求绘制的最大连线数其实就是求两个字符串的最长公共子序列的长度所以直接copy代码就可以了。 时间复杂度: O(n * m)空间复杂度: O(n * m)
53. 最大子序和
题目要求给定一个整数数组 nums 找到一个具有最大和的连续子数组子数组最少包含一个元素返回其最大和。
示例:
输入: [-2,1,-3,4,-1,2,1,-5,4]输出: 6解释: 连续子数组 [4,-1,2,1] 的和最大为 6。
思路
dp[i]包括下标i以nums[i]为结尾的最大连续子序列和为dp[i]。
dp[i]只有两个方向可以推出来
dp[i - 1] nums[i]即nums[i]加入当前连续子序列和nums[i]即从头开始计算当前连续子序列和
一定是取最大的所以dp[i] max(dp[i - 1] nums[i], nums[i]);
根据dp[i]的定义很明显dp[0]应为nums[0]即dp[0] nums[0]。
class Solution {
public:int maxSubArray(vectorint nums) {vectorint dp(nums.size() 1, 0);dp[0] nums[0];int result max(INT_MIN, dp[0]);for (int i 1; i nums.size(); i) {dp[i] max(dp[i-1] nums[i], nums[i]);if (dp[i] result) result dp[i];}return result;}
};
时间复杂度O(n)空间复杂度O(n)
