做网站需要买域名吗,全民体育世界杯,wordpress网站更换空间,企业官方网站制作推广软件文章目录 一、718、最长重复子数组二、1143、最长公共子序列三、1035、不相交的线四、392、判断子序列五、115、不同的子序列六、完整代码 所有的LeetCode题解索引#xff0c;可以看这篇文章——【算法和数据结构】LeetCode题解。 一、718、最长重复子数组 思路分析#xff1… 文章目录 一、718、最长重复子数组二、1143、最长公共子序列三、1035、不相交的线四、392、判断子序列五、115、不同的子序列六、完整代码 所有的LeetCode题解索引可以看这篇文章——【算法和数据结构】LeetCode题解。 一、718、最长重复子数组 思路分析
第一步动态数组的含义。 d p [ i ] [ j ] dp[i][j] dp[i][j]代表以下标 i − 1 i - 1 i−1为结尾的nums1和以下标 j − 1 j - 1 j−1为结尾的nums2最长重复子数组长度为 d p [ i ] [ j ] dp[i][j] dp[i][j]。第二步递推公式。根据 d p [ i ] [ j ] dp[i][j] dp[i][j]的定义 d p [ i ] [ j ] dp[i][j] dp[i][j]的状态只能由 d p [ i − 1 ] [ j − 1 ] dp[i - 1][j - 1] dp[i−1][j−1]推导出来。 if (nums1[i - 1] nums2[j - 1]) dp[i][j] dp[i - 1][j - 1] 1;第三步元素初始化。dp数组中的所有元素都初始化为0。第四步递归顺序。一共有两层循环先遍历nums1或者先遍历nums2都可以。第五步打印结果。题目要求长度最长的子数组的长度。所以在遍历的时候顺便把 d p [ i ] [ j ] dp[i][j] dp[i][j]的最大值记录下来。 程序如下
// 718、最长重复子数组
class Solution {
public:int findLength(vectorint nums1, vectorint nums2) {vectorvectorint dp(nums1.size() 1, vectorint(nums2.size() 1, 0));int result 0;for (int i 1; i nums1.size(); i) {for (int j 1; j nums2.size(); j) {if (nums1[i - 1] nums2[j - 1]) dp[i][j] dp[i - 1][j - 1] 1;if (dp[i][j] result) result dp[i][j];}}return result;}
};复杂度分析
时间复杂度 O ( n ∗ m ) O(n*m) O(n∗m) n n n和 m m m分别是两个数组的长度。空间复杂度 O ( n ∗ m ) O(n*m) O(n∗m)。
二、1143、最长公共子序列 思路分析
第一步动态数组的含义。 d p [ i ] [ j ] dp[i][j] dp[i][j]代表以下标 i − 1 i - 1 i−1为结尾的text1和以下标 j − 1 j - 1 j−1为结尾的text2最长公共子序列长度为 d p [ i ] [ j ] dp[i][j] dp[i][j]。第二步递推公式。 d p [ i ] [ j ] dp[i][j] dp[i][j]可以由两种情况推导出来 t e x t 1 [ i − 1 ] text1[i - 1] text1[i−1]与 t e x t 2 [ j − 1 ] text2[j - 1] text2[j−1]相同那么找到一个公共元素 d p [ i ] [ j ] d p [ i − 1 ] [ j − 1 ] 1 dp[i][j] dp[i - 1][j - 1] 1 dp[i][j]dp[i−1][j−1]1。 t e x t 1 [ i − 1 ] text1[i - 1] text1[i−1] 与 t e x t 2 [ j − 1 ] text2[j - 1] text2[j−1]不相同那么 t e x t 1 [ 0 , i − 2 ] text1[0, i - 2] text1[0,i−2]与 t e x t 2 [ 0 , j − 1 ] text2[0, j - 1] text2[0,j−1]的最长公共子序列和 t e x t 1 [ 0 , i − 1 ] text1[0, i - 1] text1[0,i−1]与 t e x t 2 [ 0 , j − 2 ] text2[0, j - 2] text2[0,j−2]的最长公共子序列取最大的。 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数组中的所有元素都初始化为0。第四步递归顺序。一共有两层循环从前往后进行遍历。第五步打印结果。题目要求最长公共子序列的长度。所以在遍历的时候顺便把 d p [ i ] [ j ] dp[i][j] dp[i][j]的最大值记录下来。 程序如下
// 1143、最长公共子序列
class Solution2 {
public:int longestCommonSubsequence(string text1, string text2) {vectorvectorint dp(text1.size() 1, vectorint(text2.size() 1, 0));int result 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]);if(dp[i][j] result) result dp[i][j];}}return result;}
};复杂度分析
时间复杂度 O ( n ∗ m ) O(n*m) O(n∗m) n n n和 m m m分别是两个序列的长度。空间复杂度 O ( n ∗ m ) O(n*m) O(n∗m)。
三、1035、不相交的线 思路分析本题要求绘制的最大连线数实际上就是求两个字符串的最长公共子序列的长度即1143、最长公共子序列这道题。我们将字符串改成数组代码完全一样直接copy过来。 程序如下
// 1035、不相交的线
class Solution3 {
public:int maxUncrossedLines(vectorint nums1, vectorint nums2) {vectorvectorint dp(nums1.size() 1, vectorint(nums2.size() 1, 0));int result 0;for (int i 1; i nums1.size(); i) {for (int j 1; j nums2.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]);if (dp[i][j] result) result dp[i][j];}}return result;}
};复杂度分析
时间复杂度 O ( n ∗ m ) O(n*m) O(n∗m) n n n和 m m m分别是两个数组的长度。空间复杂度 O ( n ∗ m ) O(n*m) O(n∗m)。
四、392、判断子序列 思路分析本题的思路和1143、最长公共子序列的分析思路差不多主要区别在于本题判断的是“ 最长公共子序列是不是另一个字符串的子串”。那么我们找到二者的最长公共子串判断其长度是否等于s的长度即可。
第一步动态数组的含义。 d p [ i ] [ j ] dp[i][j] dp[i][j]代表以下标 i − 1 i - 1 i−1为结尾的s和以下标 j − 1 j - 1 j−1为结尾的t最长公共子序列长度为 d p [ i ] [ j ] dp[i][j] dp[i][j]。第二步递推公式。 d p [ i ] [ j ] dp[i][j] dp[i][j]可以由两种情况推导出来 s [ i − 1 ] s[i - 1] s[i−1]与 t [ j − 1 ] t[j - 1] t[j−1]相同那么找到一个公共元素 d p [ i ] [ j ] d p [ i − 1 ] [ j − 1 ] 1 dp[i][j] dp[i - 1][j - 1] 1 dp[i][j]dp[i−1][j−1]1。 s [ i − 1 ] s[i - 1] s[i−1] 与 t [ j − 1 ] t[j - 1] t[j−1]不相同那么 d p [ i ] [ j ] dp[i][j] dp[i][j]等于 s [ 0 , i − 1 ] s[0, i - 1] s[0,i−1]与 t [ 0 , j − 2 ] t[0, j - 2] t[0,j−2]的最长公共子序列。 if (s[i - 1] t[j - 1]) dp[i][j] dp[i - 1][j - 1] 1;else dp[i][j] dp[i][j - 1]; // 与1143不同的地方第三步元素初始化。dp数组中的所有元素都初始化为0。第四步递归顺序。一共有两层循环从前往后进行遍历。第五步打印结果。题目要求最长公共子序列的长度。所以在遍历的时候顺便把 d p [ i ] [ j ] dp[i][j] dp[i][j]的最大值记录下来在用三目运算符返回。 return result s.size() ? true : false; // 与1143不同的地方程序如下
// 392、判断子序列-动态规划
class Solution4 {
public:bool isSubsequence(string s, string t) {vectorvectorint dp(s.size() 1, vectorint(t.size() 1, 0));int result 0;for (int i 1; i s.size(); i) {for (int j 1; j t.size(); j) {if (s[i - 1] t[j - 1]) dp[i][j] dp[i - 1][j - 1] 1;else dp[i][j] dp[i][j - 1]; // 与1143不同的地方if (dp[i][j] result) result dp[i][j];}}return result s.size() ? true : false; // 与1143不同的地方}
};复杂度分析
时间复杂度 O ( n ∗ m ) O(n*m) O(n∗m) n n n和 m m m分别是两个字符串的长度。空间复杂度 O ( n ∗ m ) O(n*m) O(n∗m)。
五、115、不同的子序列 思路分析本题的思路和1143、最长公共子序列的分析思路差不多。本题统计字符串t在字符串s中出现的次数我们可以理解为删除掉字符串s中的部分字符使得字符串s和字符串t相同的方法数量。 第一步动态数组的含义。 d p [ i ] [ j ] dp[i][j] dp[i][j]代表以下标 j − 1 j - 1 j−1为结尾的t在以下标 i − 1 i - 1 i−1为结尾的s中出现的次数为 d p [ i ] [ j ] dp[i][j] dp[i][j]即 t [ 0 , j − 1 ] t[0, j-1] t[0,j−1]在 s [ 0 , i − 1 ] s[0, i-1] s[0,i−1]中出现的次数。 第二步递推公式。 d p [ i ] [ j ] dp[i][j] dp[i][j]可以由两种情况推导出来 s [ i − 1 ] s[i - 1] s[i−1]与 t [ j − 1 ] t[j - 1] t[j−1]相同此时的 d p [ i ] [ j ] dp[i][j] dp[i][j]由两部分组成。一部分是用 s [ i − 1 ] s[i-1] s[i−1]来匹配相当于在 s [ 0 , i − 2 ] s[0, i-2] s[0,i−2]中寻找 t [ 0 , j − 2 ] t[0, j-2] t[0,j−2]的个数剩下一个字符 s [ i − 1 ] s[i - 1] s[i−1]与 t [ j − 1 ] t[j - 1] t[j−1]已经匹配了即 d p [ i − 1 ] [ j − 1 ] dp[i-1][j-1] dp[i−1][j−1]另一部分是不用 s [ i − 1 ] s[i-1] s[i−1]来匹配相当于在 s [ 0 , i − 2 ] s[0, i-2] s[0,i−2]中寻找 t [ 0 , j − 1 ] t[0, j-1] t[0,j−1]的个数即 d p [ i − 1 ] [ j ] dp[i-1][j] dp[i−1][j]。 s [ i − 1 ] s[i - 1] s[i−1] 与 t [ j − 1 ] t[j - 1] t[j−1]不相同那么 s [ 0 , i − 2 ] s[0, i - 2] s[0,i−2]中 t [ 0 , j − 1 ] t[0, j - 1] t[0,j−1]的数量和 s [ 0 , i − 1 ] s[0, i - 1] s[0,i−1]中 t [ 0 , j − 1 ] t[0, j - 1] t[0,j−1]的数量相同。 d p [ i ] [ j ] d p [ i − 1 ] [ j ] dp[i][j] dp[i-1][j] dp[i][j]dp[i−1][j] if (s[i - 1] t[j - 1]) dp[i][j] dp[i - 1][j - 1] dp[i - 1][j]; else dp[i][j] dp[i - 1][j];例子s“bageg”,t“bag”。那么用s[4]g组成bag的方法数量相当于在s[0, 3]bage中寻找中t[0, 1]ba的个数只有s[0]s[1]s[4]这一种。而不用s[4]g组成bag的方法数量相当于在s[0,3] bage中寻找t[0,2]bag的个数即dp[4, 3]只有s[0]s[1]s[2]这一种。说明dp[4,2]1代表在s[0,3] bage中t[0,1]ba的个数为1。 第三步元素初始化。 d p [ i ] [ 0 ] dp[i][0] dp[i][0]第一列表示字符串 s [ 0 , i − 1 ] s[0, i-1] s[0,i−1]中可以随便删除元素出现空字符串的个数。 d p [ 0 ] [ j ] dp[0][j] dp[0][j]第一行表示空字符串 s s s出现字符串 t [ 0 , j − 1 ] t[0, j-1] t[0,j−1]的个数。其中空字符串s中空字符串t的个数为1。那么 d p [ 0 ] [ 0 ] 1 , d p [ i ] [ 0 ] 1 , d p [ 0 ] [ j ] 0 dp[0][0]1, dp[i][0] 1, dp[0][j] 0 dp[0][0]1,dp[i][0]1,dp[0][j]0。第四步递归顺序。一共有两层循环从前往后进行遍历。第五步打印结果。 程序如下
// 115、不同的子序列-动态规划
class Solution5 {
public:int numDistinct(string s, string t) {vectorvectoruint64_t dp(s.size() 1, vectoruint64_t(t.size() 1, 0));for (int i 0; i s.size(); i) dp[i][0] 1; // 第一列初始化为1, dp[0][0]为1for (int j 1; j t.size(); j) dp[0][j] 0; // 第一行初始化为0, 可以省略for (int i 1; i s.size(); i) {for (int j 1; j t.size(); j) {if (s[i - 1] t[j - 1]) dp[i][j] dp[i - 1][j - 1] dp[i - 1][j]; else dp[i][j] dp[i - 1][j];}}return dp[s.size()][t.size()];}
};复杂度分析
时间复杂度 O ( n ∗ m ) O(n*m) O(n∗m) n n n和 m m m分别是两个字符串的长度。空间复杂度 O ( n ∗ m ) O(n*m) O(n∗m)。
六、完整代码
# include iostream
# include vector
# include string
using namespace std;// 718、最长重复子数组
class Solution {
public:int findLength(vectorint nums1, vectorint nums2) {vectorvectorint dp(nums1.size() 1, vectorint(nums2.size() 1, 0));int result 0;for (int i 1; i nums1.size(); i) {for (int j 1; j nums2.size(); j) {if (nums1[i - 1] nums2[j - 1]) dp[i][j] dp[i - 1][j - 1] 1;if (dp[i][j] result) result dp[i][j];}}return result;}
};// 1143、最长公共子序列
class Solution2 {
public:int longestCommonSubsequence(string text1, string text2) {vectorvectorint dp(text1.size() 1, vectorint(text2.size() 1, 0));int result 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]);if (dp[i][j] result) result dp[i][j];}}return result;}
};// 1035、不相交的线-动态规划
class Solution3 {
public:int maxUncrossedLines(vectorint nums1, vectorint nums2) {vectorvectorint dp(nums1.size() 1, vectorint(nums2.size() 1, 0));int result 0;for (int i 1; i nums1.size(); i) {for (int j 1; j nums2.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]);if (dp[i][j] result) result dp[i][j];}}return result;}
};// 392、判断子序列-动态规划
class Solution4 {
public:bool isSubsequence(string s, string t) {vectorvectorint dp(s.size() 1, vectorint(t.size() 1, 0));int result 0;for (int i 1; i s.size(); i) {for (int j 1; j t.size(); j) {if (s[i - 1] t[j - 1]) dp[i][j] dp[i - 1][j - 1] 1;else dp[i][j] dp[i][j - 1]; // 与1143不同的地方if (dp[i][j] result) result dp[i][j];}}return result s.size() ? true : false; // 与1143不同的地方}
};// 115、不同的子序列-动态规划
class Solution5 {
public:int numDistinct(string s, string t) {vectorvectoruint64_t dp(s.size() 1, vectoruint64_t(t.size() 1, 0));for (int i 0; i s.size(); i) dp[i][0] 1; // 第一列初始化为1, dp[0][0]为1for (int j 1; j t.size(); j) dp[0][j] 0; // 第一行初始化为0, 可以省略for (int i 1; i s.size(); i) {for (int j 1; j t.size(); j) {if (s[i - 1] t[j - 1]) dp[i][j] dp[i - 1][j - 1] dp[i - 1][j]; else dp[i][j] dp[i - 1][j];}}return dp[s.size()][t.size()];}
};int main() {//vectorint nums1 { 1, 2, 3, 2, 1 }, nums2 { 3, 2, 1, 4, 7 }; // 测试案例//Solution s1;//int result s1.findLength(nums1, nums2);//string text1 abcde, text2 ace; // 测试案例//Solution2 s1;//int result s1.longestCommonSubsequence(text1, text2);//vectorint nums1 { 1, 4, 2 }, nums2 { 1, 2, 4 }; // 测试案例//Solution3 s1;//int result s1.maxUncrossedLines(nums1, nums2);//string s abc, t ahbgdc; // 测试案例//Solution4 s1;//int result s1.isSubsequence(s, t);string s babgbag, t bag; // 测试案例Solution5 s1;int result s1.numDistinct(s, t);cout result endl;system(pause);return 0;
}end
