本文主要是介绍代码随想录算法训练营Day52 | 300.最长递增子序列、674.最长连续递增序列、718.最长重复子数组,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
300.最长递增子序列
这题的重点是DP数组的定义,子序列必须以nums[i]为最后一个元素,这样dp数组中后面的元素才能与前面的元素进行对比
1、DP数组定义:dp[i]表示以nums[i]为最后一个元素的最长递增子序列长度
2、DP数组初始化:全部初始化为1(子序列最少也有自身一个)
3、递推公式:与 i 前所有元素进行对比,如果nums[i] > nums[j],那么更新dp[i]
· 基本——dp[j]:位置 j 处的最长递增子序列
· 新增—— +1:算上nums[i],多了一个递增元素
· 最后的递推公式:dp[i]取较大值:dp[i] = std::max(dp[i], dp[j] + 1)
4、遍历顺序:从前向后遍历
int lengthOfLIS(vector<int>& nums) {// dp[i]表示以nums[i]为最后一个元素的最长递增子序列长度// 全部初始化为1(子序列最少也有自身一个)vector<int> dp(nums.size(), 1);int ans = 1;for (int i = 1; i < nums.size(); ++i) {// 与i之前的所有元素做比较for (int j = 0; j < i; ++j) {// 不断更新dp[i],寻找以nums[i]为最后一个元素的最长递增子序列长度if (nums[i] > nums[j])dp[i] = std::max(dp[i], dp[j] + 1);}// 记录过程中的最长子序列if (dp[i] > ans)ans = dp[i];}return ans;
}
674.最长连续递增序列
整体和上一题差不多,但由于要求是“连续”子序列,所以简单不少。主要差别在遍历过程中,为了保持序列连续,只需要与前一个元素对比即可(上一题需要与前面所有元素对比)。
int findLengthOfLCIS(vector<int>& nums) {vector<int> dp(nums.size(), 1);int ans = 1;for (int i = 1; i < nums.size(); ++i) {// 只需要与 i - 1 比较if (nums[i] > nums[i - 1]) {dp[i] = dp[i - 1] + 1;ans = std::max(ans, dp[i]);}}return ans;
}// 压缩空间写法
iint findLengthOfLCIS(vector<int>& nums) {int dp = 1;int ans = 1;for (int i = 1; i < nums.size(); ++i) {if (nums[i] > nums[i - 1])ans = std::max(ans, ++dp);elsedp = 1;}return ans;
}
718.最长重复子数组
写暴力超时了,剪剪枝可能有机会过?
int findLength0(vector<int>& nums1, vector<int>& nums2) {// 尝试用哈希表来加快索引// key:值// value:出现值的下标unordered_map<int, vector<int>> mapNum2;for (int i = 0; i < nums2.size(); ++i) {auto it = mapNum2.find(nums2[i]);if (it == mapNum2.end())mapNum2.insert({ nums2[i], {i} });elseit->second.push_back(i);}vector<int> dp(nums1.size(), 0);int ans = 0;// 暴力两层循环 + 最内层判断重复子序列长度for (int i = 0; i < nums1.size(); ++i) {auto it = mapNum2.find(nums1[i]);if (it == mapNum2.end())continue;ans = std::max(ans, 1);for (int k : it->second) {int len = 1;for (int j = 1; i + j < nums1.size() && k + j < nums2.size(); ++j) {if (nums1[i + j] == nums2[k + j]) {dp[i + j] = std::max(dp[i + j], ++len);ans = std::max(ans, dp[i + j]);}elsebreak;}}}return ans;
}
动规写法:
这题重点也是DP数组的定义:两个序列所以DP数组用二维
1、DP数组定义:两个维度表示两个数组的索引,dp[i][j]表示以nums1[i - 1]和nums2[j - 1]为结尾的两个字符串的最长重复子数组长度
(子序列问题一般都定义为 i - 1 和 j - 1,目的是精简初始化的步骤)
2、DP数组初始化:首行与首列元素无意义,但为了递推公式将其初始化为0,其余元素随意
3、递推公式:如果nums1[i - 1] == nums2[j - 1],那么dp[i][j] = dp[i - 1][j - 1] + 1
· 基本——dp[i - 1][j - 1]:以nums1[i - 2]和nums2[j - 1]为结尾的两个字符串的最长重复子数组长度
· 新增—— +1:加上新的这对匹配元素
· 最后的递推公式:dp[i] = std::max(dp[i], dp[j] + 1)
4、遍历顺序:从上到下从左到右遍历,先遍历nums1或nums2都可以
int findLength(vector<int>& nums1, vector<int>& nums2) {// dp[i][j]表示以nums1[i - 1]和nums2[j - 1]为结尾的两个字符串的最长重复子数组长度// 首行与首列元素无意义,为了递推公式将其初始化为0vector<vector<int>> dp(nums1.size() + 1, vector<int>(nums2.size() + 1, 0));int ans = 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]递推得到dp[i][j] = dp[i - 1][j - 1] + 1;ans = std::max(ans, dp[i][j]);}}}return ans;
}
这篇关于代码随想录算法训练营Day52 | 300.最长递增子序列、674.最长连续递增序列、718.最长重复子数组的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!