九龙坡集团网站建设,seo优化是什么职位,怎么让别人找你做网站,怎么看一个网站做的好不好文章目录 一、718、最长重复子数组二、1143、最长公共子序列三、完整代码 所有的LeetCode题解索引#xff0c;可以看这篇文章——【算法和数据结构】LeetCode题解。 一、718、最长重复子数组 思路分析#xff1a;
第一步#xff0c;动态数组的含义。 d p [ i ] [ j ] dp[i]… 文章目录 一、718、最长重复子数组二、1143、最长公共子序列三、完整代码 所有的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)。
三、完整代码
# 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;}
};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);cout result endl;system(pause);return 0;
}end
