医院网站源码asp,新兴网站建设,版面设计排版,网络seo招聘本文讲解最长递增子序列以及最长不下降子序列的最优解#xff0c;以及一些扩展题目。本文中讲述的是最优解#xff0c;时间复杂度是O(n*logn)#xff0c;空间复杂度O(n)#xff0c;好实现、理解难度不大。这个问题也可以用线段树来求解#xff0c;时间和空间复杂度和本节讲…本文讲解最长递增子序列以及最长不下降子序列的最优解以及一些扩展题目。本文中讲述的是最优解时间复杂度是O(n*logn)空间复杂度O(n)好实现、理解难度不大。这个问题也可以用线段树来求解时间和空间复杂度和本节讲的最优解没有区别。 下面通过一些题目来加深理解。 题目一
测试链接https://leetcode.cn/problems/longest-increasing-subsequence/
分析这道题的基本做法是非常简单和常见的所以下面给出基本做法以及优化时间复杂度的做法。基本做法的时间复杂度是O(n²)。代码如下。
class Solution {
public:int dp[2500];int lengthOfLIS(vectorint nums) {int length nums.size();int ans 1;dp[0] 1;for(int i 1;i length;i){dp[i] 1;for(int j 0;j i;j){if(nums[i] nums[j]){dp[i] dp[i] dp[j] 1 ? dp[i] : dp[j] 1;}}ans ans dp[i] ? ans : dp[i];}return ans;}
};
优化时间复杂度之后能做到O(n*logn)。通过一个end数组end[i]表示长度为i1的严格递增子序列的最小结尾故可以知道end数组是有序的对于有序数组的查找可以采用二分查找法这也是优化时间复杂度所在。最后end数组的长度就是最长严格递增子序列的长度。代码如下。
class Solution {
public:int end[2500];int get_index(int len, int num){int ans -1;int l 0, r len - 1, m;while (l r){m l (r - l) / 2;if(end[m] num){ans m;r m - 1;}else{l m 1;}}return ans;}int lengthOfLIS(vectorint nums) {int length nums.size();int len 1, find;end[0] nums[0];for(int i 1;i length;i){find get_index(len, nums[i]);if(find -1){end[len] nums[i];}else{end[find] nums[i];}}return len;}
}; 题目二
测试链接https://leetcode.cn/problems/russian-doll-envelopes/
分析这道题的思路较为难想其实只需要对于每个信封宽度从小到大排序相同宽度的对于高度从大到小排序然后仅对高度求一个最长递增子序列即可。代码如下。
class Solution {
public:int end[100000];int get_index(int len, int num){int ans -1;int l 0, r len - 1, m;while (l r){m l (r - l) / 2;if(end[m] num){ans m;r m - 1;}else{l m 1;}}return ans;}int maxEnvelopes(vectorvectorint envelopes) {auto cmp [](vector int v1, vectorint v2){return v1[0] v2[0] || (v1[0] v2[0] v1[1] v2[1]);};sort(envelopes.begin(), envelopes.end(), cmp);int length envelopes.size();int len 1, find;end[0] envelopes[0][1];for(int i 1;i length;i){find get_index(len, envelopes[i][1]);if(find -1){end[len] envelopes[i][1];}else{end[find] envelopes[i][1];}}return len;}
}; 题目三
测试链接https://leetcode.cn/problems/minimum-operations-to-make-the-array-k-increasing/
分析这道题其实是将一个数组分为了k个子数组然后只需要对每个子数组求一个最长不下降子序列然后用子数组长度减去这个最长不下降子序列的长度就是需要操作的次数将每一个子数组的操作次数求和即可得到答案。代码如下。
class Solution {
public:int nums[100000];int end[100000];int kIncreasing(vectorint arr, int k) {int length arr.size();int ans 0;int size;for(int i 0;i k;i){size 0;for(int j i;j length;j k){nums[size] arr[j];}ans (size - get_num(size));}return ans;}int get_num(int size){end[0] nums[0];int len 1;for(int i 1, find;i size;i){find get_index(nums[i], len);if(find -1){end[len] nums[i];}else{end[find] nums[i];}}return len;}int get_index(int num, int len){int ans -1;int m;int l 0;int r len - 1;while (l r){m (l r) / 2;if(end[m] num){ans m;r m - 1;}else{l m 1;}}return ans;}
}; 题目四
测试链接https://leetcode.cn/problems/maximum-length-of-pair-chain/
分析因为结果中后一个数对的第一个数一定会比前一个数对的第一个数大所以我们先对第一个数从小到大排序。然后对于去end数组查找的数选用数对的第一个数但对end数组进行赋值的时候我们选用数对的第二个数这是因为题目要求后一个数对的第一个数必须比前一个数对的第二个数大。代码如下。
class Solution {
public:int end[1000];int findLongestChain(vectorvectorint pairs) {sort(pairs.begin(), pairs.end(), [](vectorint v1, vectorint v2)-bool{return v1[0] v2[0];});int length pairs.size();end[0] pairs[0][1];int len 1;for(int i 0, find;i length;i){find get_index(len, pairs[i][0]);if(find -1){end[len] pairs[i][1];}else{end[find] end[find] pairs[i][1] ? pairs[i][1] : end[find];}}return len;}int get_index(int len, int num){int ans -1;int m, l 0, r len - 1;while (l r){m (l r) / 2;if(end[m] num){ans m;r m - 1;}else{l m 1;}}return ans;}
};
这道题的最优解法是贪心。对于数对的第二个数从小到大排序然后从一个开始寻找符合条件数对遍历完即可得到答案。代码如下。
class Solution {
public:int findLongestChain(vectorvectorint pairs) {sort(pairs.begin(), pairs.end(), [](vectorint v1, vectorint v2)-bool{return v1[1] v2[1];});int pre -2000;int ans 0;int length pairs.size();for(int i 0;i length;i){if(pairs[i][0] pre){pre pairs[i][1];ans;}}return ans;}
}; 题目五
测试链接https://www.luogu.com.cn/problem/P8776
分析这道题需要理解被修改的数和被修改为的数紧靠在一起求得的答案和原题目没有区别。这样被修改的数和被修改为的数就组成了一个子数组。对子数组的左边求得以子数组左边下标为结尾的最长不下降子序列的长度且这个最长不下降子序列的最大值不能超过这个被修改为的数对于这个子数组的右边求得以子数组右边为开头的最长不下降子序列的长度。将两个最长不下降子序列的长度相加再加上k就是这个子数组求得的答案遍历数组即可得到最大值。代码如下。
#include iostream
using namespace std;
int N, K;
int arr[100000];
int Right[100000];
int End[100000];
int get_index1(int num, int len){int ans -1;int m, l 0, r len - 1;while (l r){m (l r) / 2;if(End[m] num){ans m;r m - 1;}else{l m 1;}}return ans;
}
void get_right(){End[0] arr[N-1];int len 1;Right[N-1] 1;for(int i N-2, find;i K;--i){find get_index1(arr[i], len);if(find -1){End[len] arr[i];Right[i] len;}else{End[find] arr[i];Right[i] find1;}}
}
int get_index2(int num, int len){int ans -1;int m, l 0, r len - 1;while (l r){m (l r) / 2;if(End[m] num){ans m;r m - 1;}else{l m 1;}}return ans;
}
int main(void){scanf(%d%d, N, K);for(int i 0;i N;i){scanf(%d, arr[i]);}get_right();int ans K Right[K];End[0] arr[0];int len 1;for(int i K1, find;i N;i){find get_index2(arr[i], len);find find -1 ? len : find;ans ans (find K Right[i]) ? ans : (find K Right[i]);find get_index2(arr[i-K], len);if(find -1){End[len] arr[i-K];}else{End[find] arr[i-K];}}printf(%d, ans);
}
