沈阳住房和城乡建设厅网站,网站设计问题,深圳网警,成都网站建设scyiyouLeetCode 1143- 最长公共子序列
题目链接#xff1a;力扣#xff08;LeetCode#xff09;官网 - 全球极客挚爱的技术成长平台
题目描述#xff1a;给定两个字符串 text1 和 text2#xff0c;返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 #xff…LeetCode 1143- 最长公共子序列
题目链接力扣LeetCode官网 - 全球极客挚爱的技术成长平台
题目描述给定两个字符串 text1 和 text2返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 返回 0 。
一个字符串的 子序列 是指这样一个新的字符串它是由原字符串在不改变字符的相对顺序的情况下删除某些字符也可以不删除任何字符后组成的新字符串。
例如ace 是 abcde 的子序列但 aec 不是 abcde 的子序列。
两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。
解题思路
确定dp数组dp table以及下标的含义
dp[i][j]代表字符串1 从0到i-1 字符串2 从0到j-1为止两个字符的最长公共子序列。
为什么要这样定义呢方便dp数组的初始化若dp[i][j]代表从0-i最长公共子序列那我们dp[0][i]就都得判断看是否两个对应位置字符相等来进行初始化。
确定递推公式
和上一题一样如果两个对应位字符相等则使得
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]);
确定遍历顺序
从递归公式其实已经可以看出一定是从前向后遍历。
举例推导dp数组
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()];}
};
总结
如果当前俩字符不想等时取前面字符的最大值这是和上一题不同的地方。
LeetCode 1035- 不相交的线
题目链接力扣LeetCode官网 - 全球极客挚爱的技术成长平台
题目描述在两条独立的水平线上按给定的顺序写下 nums1 和 nums2 中的整数。
现在可以绘制一些连接两个数字 nums1[i] 和 nums2[j] 的直线这些直线需要同时满足满足
nums1[i] nums2[j]且绘制的直线不与任何其他连线非水平线相交。
请注意连线即使在端点也不能相交每个数字只能属于一条连线。
以这种方法绘制线条并返回可以绘制的最大连线数。
解题思路
本题和上一题一模一样因为我们这题要找不相交的所以我们找到两个数组的最长公共子序列就一定可以。
1.确定dp数组dp table以及下标的含义
dp[i][j]代表字符串1 从0到i-1 字符串2 从0到j-1为止两个字符的最长公共子序列。
为什么要这样定义呢方便dp数组的初始化若dp[i][j]代表从0-i最长公共子序列那我们dp[0][i]就都得判断看是否两个对应位置字符相等来进行初始化。
2.确定递推公式
和上一题一样如果两个对应位字符相等则使得
3.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]);
4.确定遍历顺序
从递归公式其实已经可以看出一定是从前向后遍历。
5.举例推导dp数组
class Solution {
public:int maxUncrossedLines(vectorint nums1, vectorint nums2) {int s1 nums1.size();int s2 nums2.size();vectorvectorint dp(s11,vectorint(s21,0));for(int i1;is1;i){for(int j1;js2;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[s1][s2];}
};
总结
和上一题一样的
LeetCode 53- 最大子数组和
题目链接力扣LeetCode官网 - 全球极客挚爱的技术成长平台
题目描述给你一个整数数组 nums 请你找出一个具有最大和的连续子数组子数组最少包含一个元素返回其最大和。
子数组 是数组中的一个连续部分。
解题思路
确定dp数组dp table以及下标的含义
dp[i]以i为结尾的连续子数组的最大的和。
确定递推公式
dp[i] max(dp[i-1]nums[i],nums[i]);
dp[i - 1] nums[i]即nums[i]加入当前连续子序列和nums[i]即从头开始计算当前连续子序列和
dp数组如何初始化
全部初始化为0
确定遍历顺序
顺序遍历
举例推导dp数组
class Solution {
public://没AC是因为开始把res设置为了int的最小值应该设置为nums[0]的int maxSubArray(vectorint nums) {vectorint dp(nums.size(),0);int res nums[0];if(nums.size() 1) return nums[0];dp[0] nums[0];for(int i1;inums.size();i){dp[i] max(dp[i-1]nums[i],nums[i]); res max(res,dp[i]);}return res;}
};
总结
本题开始一直错是初始化res错了一直初始化成int最小值那么如果就两个数的时候它就会取第二个数。因为我们i是从1开始的所以一直错。
