微信平台制作网站开发,信息发布类网站模板,网站管理助手4.1,网上商城英文目录
1143.最长公共子序列
1035.不相交的线
53. 最大子序和 1143.最长公共子序列
力扣题目链接(opens new window)
给定两个字符串 text1 和 text2#xff0c;返回这两个字符串的最长公共子序列的长度。
一个字符串的 子序列 是指这样一个新的字符串#xff1a;它是由原…目录
1143.最长公共子序列
1035.不相交的线
53. 最大子序和 1143.最长公共子序列
力扣题目链接(opens new window)
给定两个字符串 text1 和 text2返回这两个字符串的最长公共子序列的长度。
一个字符串的 子序列 是指这样一个新的字符串它是由原字符串在不改变字符的相对顺序的情况下删除某些字符也可以不删除任何字符后组成的新字符串。
例如ace 是 abcde 的子序列但 aec 不是 abcde 的子序列。两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。
若这两个字符串没有公共子序列则返回 0。
示例 1:
输入text1 abcde, text2 ace输出3解释最长公共子序列是 ace它的长度为 3。
示例 2:
输入text1 abc, text2 abc输出3解释最长公共子序列是 abc它的长度为 3。
示例 3:
输入text1 abc, text2 def输出0解释两个字符串没有公共子序列返回 0。 思路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]); class Solution {
public:int longestCommonSubsequence(string text1, string text2) {int ntext1.size();int mtext2.size();vectorvectorintdp(n1,vectorint(m1,0));for(int i1;in;i){for(int j1;jm;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[n][m];}
}; 1035.不相交的线
力扣题目链接
我们在两条独立的水平线上按给定的顺序写下 A 和 B 中的整数。
现在我们可以绘制一些连接两个数字 A[i] 和 B[j] 的直线只要 A[i] B[j]且我们绘制的直线不与任何其他连线非水平线相交。
以这种方法绘制线条并返回我们可以绘制的最大连线数。 思路 直线不能相交这就是说明在字符串A中 找到一个与字符串B相同的子序列且这个子序列不能改变相对顺序只要相对顺序不改变链接相同数字的直线就不会相交。 拿示例一A [1,4,2], B [1,2,4]为例相交情况如图 其实也就是说A和B的最长公共子序列是[1,4]长度为2。 这个公共子序列指的是相对顺序不变即数字4在字符串A中数字1的后面那么数字4也应该在字符串B数字1的后面 这么分析完之后大家可以发现本题说是求绘制的最大连线数其实就是求两个字符串的最长公共子序列的长度 class Solution {
public:int maxUncrossedLines(vectorint nums1, vectorint nums2) {vectorvectorintdp(nums1.size()1, vector(nums2.size()1,0));for(int i1;inums1.size();i){for(int 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[nums1.size()][nums2.size()];}
}; 53. 最大子序和
力扣题目链接(opens new window)
给定一个整数数组 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]是依赖于dp[i - 1]的状态dp[0]就是递推公式的基础。 dp[0]应该是多少呢? 根据dp[i]的定义很明显dp[0]应为nums[0]即dp[0] nums[0]。 class Solution {
public://贪心当总和0时立马重新置零求和int maxSubArray(vectorint nums) {int result0;int count 0;for(int i0;inums.size();i){countnums[i];if(countresult){resultcount;}if(count0) count0;}return result;}
};
class Solution {
public://动态规划int maxSubArray(vectorint nums) {if(nums.size()0)return 0;vectorintdp(nums.size()1,0);dp[0]nums[0];int result dp[0];for(int i1;inums.size();i){dp[i]max(nums[i]dp[i-1],nums[i]);if(dp[i]result)resultdp[i];}return result;}
}; 参考代码随想录
