数据结构学习 Leetcode356 俄罗斯套信封
2023-12-26 12:45:53
关键词:动态规划 最长递增子序列 贪心 二分查找
其实就是最长递增子序列。比较难的是需要理解题目用并想起来用这个方法。
可以看看这位大神写的方法,循序渐进,我觉得很好。
里面提到的四种方法的总结就是:
- 第一种方法就是降维(控制第一维)+最长上升子序列。
- 第二种方法就是降维(控制第一维)+最长上升子序列+控制第二维
- 第三种方法就是降维(控制第一维)+贪心。
- 第四种方法就是降维(控制第一维)+贪心+二分查找。
我在下面写的解法一 对应 第一种方法。
?我在下面写的解法二 对应 第四种方法。
题目:
解法一:暴力的最长递增子序列
这个方法,我做到某个用例的时候超时了。
思路:
降维:一般的最长递增子序列只能用于一维,然而这个是二维的,所以我们可以控制第一维(给第一维排序),然后对第二位进行最长递增子序列的计算。
控制第一维的理由:
状态和转移方程:
复杂度计算:
时间复杂度O(n^2) 排序nlogn 遍历并求最大值n^2
空间复杂度O(n) dp列表
代码:
class Solution {
public:
int maxEnvelopes(vector<vector<int>>& envelopes) {
std::sort(envelopes.begin(),envelopes.end());
vector<int> dp(envelopes.size());
int result=0;
for(int i=0;i<envelopes.size();++i)
{
int max=0;
for(int j=0;j<i;++j)
{
if(envelopes[i][0]>envelopes[j][0]&&envelopes[i][1]>envelopes[j][1])
{
max=std::max(max,dp[j]+1);
}
}
dp[i]=max;
result=std::max(max,result);
}
return result+1;
}
};
解法二:贪心 二分查找
这个方法基本和我之前学的最长上升子序列的题目一样,我有写笔记,这个对应笔记的方法二。
这个方法其实就是我最上面给到的链接的第四种方法。第四种方法其实是第2 3种方法的优化版本。
思路:
具体思路看我提供的链接吧。
关键就是开一个序列存最小的状态。然后二分。
复杂度计算:
时间复杂度O(nlogn) 排序nlogn,遍历信封列表需要 O(N),计算每一个信封插入位置需要?O(logN)
空间复杂度O(n) dp列表
代码:
class Solution {
public:
int maxEnvelopes(vector<vector<int>>& envelopes) {
std::sort(envelopes.begin(),envelopes.end(),[](vector<int>&a,vector<int>&b)
{
if(a[0]==b[0]) return a[1]>b[1];
return a[0]<b[0];
});
vector<int> dp(envelopes.size());
int len=0;
dp[0]=envelopes[0][1];
for(int i=1;i<envelopes.size();++i)
{
if(dp[len]<envelopes[i][1])
{
len++;
dp[len]=envelopes[i][1];
}
else if(dp[len]>envelopes[i][1])
{
int l=0;
int r=len;
while(l<r)
{
int mid=(r+l)/2;
if(envelopes[i][1]>dp[mid])
{
l=mid+1;
}
else
{
r=mid;
}
}
dp[r]=envelopes[i][1];
}
}
return len+1;
}
};
文章来源:https://blog.csdn.net/rainssssss/article/details/135216851
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!