微网站 建设,泗阳城乡建设局网站,深圳做网站乐云seo598,凡客东西网目录
LeetCode 300. 最长递增子序列
LeetCode 674. 最长连续递增序列
LeetCode 718. 最长重复子数组
LeetCode 1143. 最长公共子序列
LeetCode 1035. 不相交的钱
LeetCode 53. 最大子序和
LeetCode 392. 判断子序列
总结 LeetCode 300. 最长递增子序列
题目链接#…目录
LeetCode 300. 最长递增子序列
LeetCode 674. 最长连续递增序列
LeetCode 718. 最长重复子数组
LeetCode 1143. 最长公共子序列
LeetCode 1035. 不相交的钱
LeetCode 53. 最大子序和
LeetCode 392. 判断子序列
总结 LeetCode 300. 最长递增子序列
题目链接LeetCode 300. 最长递增子序列
思想依然用动归五部曲来分析第一个dp数组的定义。这里把dp[i]表示i之前包括i的以nums[i]结尾的最长递增子序列的长度。在做递增比较的时候比较两个子序列的结尾才能算递增比较完一个再比较结尾也可以保证是递增的。其次就是状态转移方程位置i的最长升序子序列等于j从0到i-1各个位置的最长升序子序列1的最大值。所以状态转移方程是if(nums[i] nums[j]) dp[i]max(dp[i],dp[j]1)。初始化就把dp数组全初始化为1因为本身也是一个子序列。这里有两层循环先从前往后遍历整个nums数组内层遍历就从前往后遍历到外层下标-1就行了。
代码如下 int lengthOfLIS(vectorint nums) {if (nums.size() 1) return 1;vectorint dp(nums.size(), 1);int result 0;for (int i 1; i nums.size(); i) {for (int j 0; j i; j) {if (nums[i] nums[j]) dp[i] max(dp[i], dp[j] 1);}result dp[i] result ? dp[i] : result;}return result;}
时间复杂度O(n^2)空间复杂度O(n)。
LeetCode 674. 最长连续递增序列
题目链接LeetCode 674. 最长连续递增序列
思想本题跟上题基本上情况都是一模一样的除了子序列变成了连续连续也就是说任何递增序列的元素在原数组必须要相邻。那么把上述循环中的if判断条件修改了就行改为if(dp[j1]dp[j])然后再进行状态判断如果不满足递增的话dp[i]就等于1就行了因为要重新进行计算。
代码如下 int findLengthOfLCIS(vectorint nums) {if (nums.size() 1) return 1;vectorint dp(nums.size(), 1);int result 0;for (int i 1; i nums.size(); i) {for (int j 0; j i; j) {if (nums[j1] nums[j]) dp[i] max(dp[i], dp[j]1);else dp[i] 1;}result dp[i] result ? dp[i] : result;}return result;}
时间复杂度O(n^2)空间复杂度O(n)。
LeetCode 718. 最长重复子数组
题目链接LeetCode 718. 最长重复子数组
思想本题没有强调连续的话子数组就相当于子序列。那么还是动归五部曲第一个确定dp[i]。dp[i][j]是以下标i-1为结尾的A和下标j-1为结尾的B最长重复子数组长度为dp[i][j]。第二个就是确定递推公式dp[i][j]需要i-1和j-1的状态推导出来那么当A[i-1]B[j-1]的时候dp[i][j] dp[i-1][j-1]1。初始化的话就把每一个初始化为0就行了循环就外层遍历一个数组内层遍历另一个数组就可以了。
代码如下 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;result dp[i][j] result ? dp[i][j] : result;}}return result;}
时间复杂度O(n^2)空间复杂度O(n^2)。
LeetCode 1143. 最长公共子序列
题目链接LeetCode 1143. 最长公共子序列
思想其实本题跟上题是差不多的主要差别就是递推公式上相等的就是一样的递推公式这里存在着不等不等的话就看i-1和j-1状态上的数值谁大谁大就取谁。即dp[i][j] max(dp[i-1][j], dp[i][j-1]。
代码如下 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][j-1], dp[i-1][j]);result dp[i][j] result ? dp[i][j] : result;}}return result;}
时间复杂度O(n^2)空间复杂度O(n^2)。
LeetCode 1035. 不相交的钱
题目链接LeetCode 1035. 不相交的钱
思想本题跟上题一模一样。遂不再重复。
代码如下 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]);result dp[i][j] result ? dp[i][j] : result;}}return result;}
时间复杂度O(n^2)空间复杂度O(n^2)。
LeetCode 53. 最大子序和
题目链接LeetCode 53. 最大子序和
思想还是动归五部曲吧第一步确定dp数组。这里dp[i]表示包括下标i的最大连续子序列和dp[i]。其次就是递推公式dp[i]只有两个方向可以推出来第一个状态当前nums[i]加入子序列即dp[i] dp[i-1] nums[i]第二个状态是重新开始计算子序列即dp[i] nums[i]。这俩个状态取最大就行了。初始化只需要初始化dp[0]就行了dp[0]很明显要等于nums[0]。遍历顺序就直接从前往后遍历就行了。
代码如下 int maxSubArray(vectorint nums) {if (nums.size() 1) return nums[0];vectorint dp(nums.size(), INT_MIN);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]);result dp[i] result ? dp[i] : result;}return result;}
时间复杂度O(n)空间复杂度O(n)。
LeetCode 392. 判断子序列
题目链接LeetCode 392. 判断子序列
思想本题其实跟判断最长子序列是一个道理只需最后判断得出的长度是否等于s的长度就行了。遂不再讲解了。
代码如下 bool isSubsequence(string s, string t) {if (s.size() t.size()) return false;vectorvectorint dp(s.size()1, vectorint (t.size()1, 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] max(dp[i][j-1], dp[i-1][j]);}}if (dp[s.size()][t.size()] s.size()) return true;return false;}
时间复杂度O(n^2)空间复杂度O(n^2)。
总结
我还是不会
