最长序列
300. 最长递增子序列【中等】
- 方法一：动态规划
时间复杂度：O(n^2)
空间复杂度：O(n)
1、确定dp数组及其含义
dp[i]表示0~i索引的最长上升子序列长度
2、确定状态转移方程
if(nums[i] > nums[j]) dp[i] = max(dp[i], dp[j]+1);
3、dp初始化
dp[i] = 1;，只要nums有长度，至少为1
class Solution { public: int lengthOfLIS(vector<int>& nums) { if(nums.size() <= 1) return nums.size(); // dp初始化 vector<int> dp(nums.size(), 1); int maxLen = 0; for (int i = 1; i < nums.size(); ++i) { //以i结尾的nums的最长上升子序列 for (int j = 0; j < i; ++j) { if (nums[j] < nums[i]) { dp[i] = max(dp[i], dp[j] + 1); } } maxLen = max(maxLen, dp[i]); } return maxLen; } };
方法二：贪心+二分查找
时间复杂度：O(nlogn)
空间复杂度：O(n)
674. 最长连续递增序列【简单】
思路一：动态规划
时间复杂度：O(n)
空间复杂度：O(n)
1、确定dp数组及其下标含义
dp[i]是索引0~i时连续递增子序列长度
2、确定递推公式
if(nums[i] > nums[i-1]) dp[i] = dp[i-1] + 1;
3、dp初始化
vector<int> dp(nums.size(), 1);
class Solution { public: int findLengthOfLCIS(vector<int>& nums) { if (nums.size() <= 1) return nums.size(); int maxLen = 1; vector<int> dp(nums.size() ,1); for (int i = 1; i < nums.size(); i++) { if (nums[i] > nums[i-1]) // 连续记录 dp[i] = dp[i-1] + 1; maxLen = max(maxLen, dp[i]); } return maxLen; } };
- 思路二：贪心
时间复杂度：O(n)
空间复杂度：O(1)
class Solution { public: int findLengthOfLCIS(vector<int>& nums) { if (nums.size() <= 1) return nums.size(); int maxLen = 1; int count = 1; for (int i = 1; i < nums.size(); i++) { if (nums[i] > nums[i-1]) count++; else count = 1; maxLen = max(maxLen, count); } return maxLen; } };
思路三：双指针
时间复杂度：O(n)
空间复杂度：O(1)
class Solution { public: int findLengthOfLCIS(vector<int>& nums) { if (nums.size() <= 1) return nums.size(); int maxLen = 1; int start = 0; for(int end = 1; end < nums.size(); ++end){ if(nums[end] <= nums[end-1]){ maxLen = max(maxLen, end - start); start = end; } } //最后一节 if(nums.size() - start > maxLen) maxLen = nums.size() - start; return maxLen; } };
718. 最长重复子数组【中等】
思路：动态规划
时间复杂度：O(mn)
空间复杂度：O(mn)
1、确定dp数组及其下标含义
dp[i][j]：以下标i-1结尾的A，j-1结尾的B，它们的最长重复子数组长度
2、确定递推公式
dp[i][j] = dp[i-1][j-1] + 1;
3、dp初始化
dp[i][0] = 0;
dp[0][j] = 0;
class Solution { public: int findLength(vector<int>& A, vector<int>& B) { vector<vector<int>> dp (A.size() + 1, vector<int>(B.size() + 1, 0)); int maxLen = 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; } maxLen = max(maxLen, dp[i][j]); } } return maxLen; } };
思路二：空间优化，滚动数组
class Solution { public: int findLength(vector<int>& A, vector<int>& B) { vector<int> dp(vector<int>(B.size() + 1, 0)); int maxLen = 0; for (int i = 1; i <= A.size(); i++) { for (int j = B.size(); j > 0; j--) { if (A[i - 1] == B[j - 1]) { dp[j] = dp[j - 1] + 1; } else dp[j] = 0; // 注意这里不相等的时候要有赋0的操作 maxLen = max(maxLen, dp[j]); } } return maxLen; } };
1143. 最长公共子序列【中等】
- 思路：动态规划
时间复杂度：O(mn)
空间复杂度：O(mn)
1、确定dp数组以及下标含义
dp[i][j]：索引为0-i的text1与0-j的text2的最长公共子序列
2、确定递推公式
if(text1[i-1] == text2[j-1]) dp[i][j] = dp[i-1][j-1] + 1;
if(text1[i-1] != text2[j-1]) dp[i][j] != max(dp[i-1][j], dp[i][j-1]);
3、dp初始化
vector<vector<int>> dp(text1.size(), vector<int>(text2.size(), 0));
class Solution { public: int longestCommonSubsequence(string text1, string text2) { vector<vector<int>> dp(text1.size()+1, vector<int>(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()]; } };
