给n个信封的长度和宽度。如果信封A的长和宽都小于信封B,那么信封A可以放到信封B里,请求出信封最多可以嵌套多少层。-笔试面试资料
这是qklbishe.com第6227 篇笔试面试资料
提供答案分析,通过本文《给n个信封的长度和宽度。如果信封A的长和宽都小于信封B,那么信封A可以放到信封B里,请求出信封最多可以嵌套多少层。-笔试面试资料》可以理解其中的代码原理,这是一篇很好的求职学习资料
本站提供程序员计算机面试经验学习,笔试经验,包括字节跳动/头条,腾讯,阿里,美团,滴滴出行,网易,百度,京东,小米,华为,微软等互联网大厂真题学习背诵。
答案:
给n个信封的长度和宽度。如果信封A的长和宽都小于信封B,那么信封A可以放到信封B里,请求出信封最多可以嵌套多少层。

class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
*
* @param letters intvector<vector<>>
* @return int
*/
static bool cmp(const vector<int> a,const vector<int> b)
{
if(a[0]==b[0])
return a[1]>=b[1];//宽度相等时按照高度降序排列
else
return a[0]<b[0];//按照宽度升序排列
}
int LIS(vector<int> vec,int n)//经典的最长上升子序列问题,当然还可用二分优化
{
vector<int> dp(n,0);
dp[0]=1;
for(int i=1;i<n;i++)
{
for(int j=0;j<i;j++)
{
if(vec[i]>vec[j])
dp[i]=max(dp[i],dp[j]);
}
dp[i]++;
}
return *max_element(dp.begin(),dp.end());
}
int maxLetters(vector<vector<int> >& letters) {
// write code here
int n=letters.size();
sort(letters.begin(),letters.end(),cmp);//排序
vector<int> height;
for(int i=0;i<n;i++)
{
height.push_back(letters[i][1]);
}
int res=LIS(height,n);//按照高度最长上升子序列
return res;
}
};
public:
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
*
* @param letters intvector<vector<>>
* @return int
*/
static bool cmp(const vector<int> a,const vector<int> b)
{
if(a[0]==b[0])
return a[1]>=b[1];//宽度相等时按照高度降序排列
else
return a[0]<b[0];//按照宽度升序排列
}
int LIS(vector<int> vec,int n)//经典的最长上升子序列问题,当然还可用二分优化
{
vector<int> dp(n,0);
dp[0]=1;
for(int i=1;i<n;i++)
{
for(int j=0;j<i;j++)
{
if(vec[i]>vec[j])
dp[i]=max(dp[i],dp[j]);
}
dp[i]++;
}
return *max_element(dp.begin(),dp.end());
}
int maxLetters(vector<vector<int> >& letters) {
// write code here
int n=letters.size();
sort(letters.begin(),letters.end(),cmp);//排序
vector<int> height;
for(int i=0;i<n;i++)
{
height.push_back(letters[i][1]);
}
int res=LIS(height,n);//按照高度最长上升子序列
return res;
}
};
今天 02:23:11 回复(0)
文章部分来自互联网,侵权联系删除
www.qklbishe.com
区块链毕设网(www.qklbishe.com)全网最靠谱的原创区块链毕设代做网站部分资料来自网络,侵权联系删除!资源收费仅为搬运整理打赏费用,用户自愿支付 !
qklbishe.com区块链毕设代做网专注|以太坊fabric-计算机|java|毕业设计|代做平台 » 给n个信封的长度和宽度。如果信封A的长和宽都小于信封B,那么信封A可以放到信封B里,请求出信封最多可以嵌套多少层。-笔试面试资料
qklbishe.com区块链毕设代做网专注|以太坊fabric-计算机|java|毕业设计|代做平台 » 给n个信封的长度和宽度。如果信封A的长和宽都小于信封B,那么信封A可以放到信封B里,请求出信封最多可以嵌套多少层。-笔试面试资料