建设网站源码,赣州做网站的公司有哪家好,百度一下你就知道手机版官网,网站开发好后要做什么1143.最长公共子序列
力扣题目链接(opens new window)
给定两个字符串 text1 和 text2#xff0c;返回这两个字符串的最长公共子序列的长度。
一个字符串的 子序列 是指这样一个新的字符串#xff1a;它是由原字符串在不改变字符的相对顺序的情况下删除某些字符#xff0…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。
提示:
1 text1.length 10001 text2.length 1000 输入的字符串只含有小写英文字符。
#思路
本题和动态规划718. 最长重复子数组 (opens new window)区别在于这里不要求是连续的了但要有相对顺序即ace 是 abcde 的子序列但 aec 不是 abcde 的子序列。
继续动规五部曲分析如下
确定dp数组dp table以及下标的含义
dp[i][j]长度为[0, i - 1]的字符串text1与长度为[0, j - 1]的字符串text2的最长公共子序列为dp[i][j]
有同学会问为什么要定义长度为[0, i - 1]的字符串text1定义为长度为[0, i]的字符串text1不香么
这样定义是为了后面代码实现方便如果非要定义为长度为[0, i]的字符串text1也可以我在 动态规划718. 最长重复子数组 (opens new window)中的「拓展」里 详细讲解了区别所在其实就是简化了dp数组第一行和第一列的初始化逻辑。
确定递推公式
主要就是两大情况 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]);
}dp数组如何初始化
先看看dp[i][0]应该是多少呢
test1[0, i-1]和空串的最长公共子序列自然是0所以dp[i][0] 0;
同理dp[0][j]也是0。
其他下标都是随着递推公式逐步覆盖初始为多少都可以那么就统一初始为0。
代码
vectorvectorint dp(text1.size() 1, vectorint(text2.size() 1, 0));确定遍历顺序
从递推公式可以看出有三个方向可以推出dp[i][j]如图 那么为了在递推的过程中这三个方向都是经过计算的数值所以要从前向后从上到下来遍历这个矩阵。
举例推导dp数组
以输入text1 abcde, text2 ace 为例dp状态如图 最后红框dp[text1.size()][text2.size()]为最终结果
以上分析完毕C代码如下
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()];}
};时间复杂度: O(n * m)其中 n 和 m 分别为 text1 和 text2 的长度空间复杂度: O(n * m)
1035.不相交的线
力扣题目链接(opens new window)
我们在两条独立的水平线上按给定的顺序写下 A 和 B 中的整数。
现在我们可以绘制一些连接两个数字 A[i] 和 B[j] 的直线只要 A[i] B[j]且我们绘制的直线不与任何其他连线非水平线相交。
以这种方法绘制线条并返回我们可以绘制的最大连线数。 #思路
相信不少录友看到这道题目都没啥思路我们来逐步分析一下。
绘制一些连接两个数字 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的后面
这么分析完之后大家可以发现本题说是求绘制的最大连线数其实就是求两个字符串的最长公共子序列的长度
那么本题就和我们刚刚讲过的这道题目动态规划1143.最长公共子序列 (opens new window)就是一样一样的了。
一样到什么程度呢 把字符串名字改一下其他代码都不用改直接copy过来就行了。
其实本题就是求最长公共子序列的长度介于我们刚刚讲过动态规划1143.最长公共子序列 (opens new window)所以本题我就不再做动规五部曲分析了。
如果大家有点遗忘了最长公共子序列就再看一下这篇动态规划1143.最长公共子序列(opens new window)
本题代码如下
class Solution {
public:int maxUncrossedLines(vectorint A, vectorint B) {vectorvectorint dp(A.size() 1, vectorint(B.size() 1, 0));for (int i 1; i A.size(); i) {for (int j 1; j B.size(); j) {if (A[i - 1] B[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[A.size()][B.size()];}
};时间复杂度: O(n * m)空间复杂度: O(n * m)
#总结
看到代码大家也可以发现其实就是求两个字符串的最长公共子序列但如果没有做过1143.最长公共子序列 (opens new window)本题其实还有很有难度的。
这是Carl为什么要先讲1143.最长公共子序列 (opens new window)再讲本题大家会发现一个正确的刷题顺序对算法学习是非常重要的
这也是Carl做了很多题目包括ACM和力扣才总结出来的规律大家仔细体会一下哈。 53. 最大子序和
力扣题目链接(opens new window)
给定一个整数数组 nums 找到一个具有最大和的连续子数组子数组最少包含一个元素返回其最大和。
示例:
输入: [-2,1,-3,4,-1,2,1,-5,4]输出: 6解释: 连续子数组 [4,-1,2,1] 的和最大为 6。
#思路
这道题之前我们在讲解贪心专题的时候用贪心算法解决过一次贪心算法最大子序和 (opens new window)。
这次我们用动态规划的思路再来分析一次。
动规五部曲如下
确定dp数组dp table以及下标的含义
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数组如何初始化
从递推公式可以看出来dp[i]是依赖于dp[i - 1]的状态dp[0]就是递推公式的基础。
dp[0]应该是多少呢?
根据dp[i]的定义很明显dp[0]应为nums[0]即dp[0] nums[0]。
确定遍历顺序
递推公式中dp[i]依赖于dp[i - 1]的状态需要从前向后遍历。
举例推导dp数组
以示例一为例输入nums [-2,1,-3,4,-1,2,1,-5,4]对应的dp状态如下 注意最后的结果可不是dp[nums.size() - 1] 而是dp[6]。
在回顾一下dp[i]的定义包括下标i之前的最大连续子序列和为dp[i]。
那么我们要找最大的连续子序列就应该找每一个i为终点的连续最大子序列。
所以在递推公式的时候可以直接选出最大的dp[i]。
以上动规五部曲分析完毕完整代码如下
class Solution {
public:int maxSubArray(vectorint nums) {if (nums.size() 0) return 0;vectorint dp(nums.size());dp[0] nums[0];int result 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]; // result 保存dp[i]的最大值}return result;}
};时间复杂度O(n)空间复杂度O(n)
#总结
这道题目用贪心也很巧妙但有一点绕需要仔细想一想如果想回顾一下贪心就看这里吧贪心算法最大子序和(opens new window)
动规的解法还是很直接的。
