当前位置: 首页 > news >正文

1.86神华网站两学一做云搜索app下载

1.86神华网站两学一做,云搜索app下载,网站如何做推广,杭州市人民政府办公室电话本文涉及的基础知识点 二分查找 题目 给你一个二维整数数组 envelopes ,其中 envelopes[i] [wi, hi] ,表示第 i 个信封的宽度和高度。 当另一个信封的宽度和高度都比这个信封大的时候,这个信封就可以放进另一个信封里,如同俄罗…

本文涉及的基础知识点

二分查找

题目

给你一个二维整数数组 envelopes ,其中 envelopes[i] = [wi, hi] ,表示第 i 个信封的宽度和高度。
当另一个信封的宽度和高度都比这个信封大的时候,这个信封就可以放进另一个信封里,如同俄罗斯套娃一样。
请计算 最多能有多少个 信封能组成一组“俄罗斯套娃”信封(即可以把一个信封放到另一个信封里面)。
注意:不允许旋转信封。
示例 1:
输入:envelopes = [[5,4],[6,4],[6,7],[2,3]]
输出:3
解释:最多信封的个数为 3, 组合为: [2,3] => [5,4] => [6,7]。
示例 2:
输入:envelopes = [[1,1],[1,1],[1,1]]
输出:1
参数提示
1 <= envelopes.length <= 105
envelopes[i].length == 2
1 <= wi, hi <= 105

超时解法

有两个地方可能超时:
一,std::map<int, int> dp = mPreYToNum;
二,for (; (ij != dp.end()) && (ij->second > len); ++ij);
一处的时间复杂度是:O(n),最多有n个元素,所以总时间复杂度是O(n*n),会引起超时。
二处,总时间复杂度是O(n),最多删除n次,每个元素最多只会被删除一次。

代码

class Solution {
public:
int maxEnvelopes(vector<vector>& envelopes) {
std::map<int, vector> mXToYS;
for (const auto& v : envelopes)
{
mXToYS[v[0]].emplace_back(v[1]);
}
std::map<int, int> mPreYToNum;//y值对应最大数量,y值越大,对应的数量越大,否则被淘汰了
int iMax = 0;
for (const auto& it : mXToYS)
{
std::map<int, int> dp = mPreYToNum;
for (const auto& y : it.second)
{
int len = 0;
{//计算长度
const auto it = mPreYToNum.lower_bound(y);
len = 1 + ((mPreYToNum.begin() == it) ? 0 : std::prev(it)->second);
iMax = max(iMax, len);
}
{
const auto it = dp.lower_bound(y);
auto ij = it;
for (; (ij != dp.end()) && (ij->second > len); ++ij);
dp.erase(it, ij);
if (!dp.count(y))
{
dp[y] = len;
}
}
}
mPreYToNum.swap(dp);
}

	return iMax;
}

};

测试用例

template
void Assert(const T& t1, const T& t2)
{
assert(t1 == t2);
}

template
void Assert(const vector& v1, const vector& v2)
{
if (v1.size() != v2.size())
{
assert(false);
return;
}
for (int i = 0; i < v1.size(); i++)
{
Assert(v1[i] ,v2[i]);
}
}

int main()
{
Solution slu;
vector<vector> envelopes;
int res = 0;
envelopes = { {5,4},{6,4},{6,7},{2,3} };
res = slu.maxEnvelopes(envelopes);
Assert(res, 3);
envelopes = { {1,1},{1,1},{1,1} };
res = slu.maxEnvelopes(envelopes);
Assert(res, 1);
envelopes = { {1,1},{2,2},{2,3} };
res = slu.maxEnvelopes(envelopes);
Assert(res, 2);
envelopes = { {1,2},{2,3},{3,4},{3,5},{4,5},{5,5},{5,6},{6,7},{7,8} };
res = slu.maxEnvelopes(envelopes);
Assert(res, 7);

//CConsole::Out(res);

}

正确解法

变量含义

mXToYSkey为envelopes的x,值为envelopes的y
mYToNum[x取[0,x), y对应最大套娃数量
vector<pair<int, int>> vYNum当前x,各y对应数量

注意:

x相同,无法套娃,所以必须等当前x处理完毕,才能更新mYToNum。
y值越大,对应的数量越大,否则被淘汰了。所以mYToNum的键和值都是升序。
y小于当前y的,不会淘汰当前y,因为当前长度就是小于y的最大长度+1。
所以只会被相等的y淘汰。
当前y 可能淘汰比当前y大的。

代码

class Solution {
public:
int maxEnvelopes(vector<vector>& envelopes) {
std::map<int, vector> mXToYS;
for (const auto& v : envelopes)
{
mXToYS[v[0]].emplace_back(v[1]);
}
std::map<int, int> mYToNum;//y值对应最大数量
int iMax = 0;
for (const auto& it : mXToYS)
{
vector<pair<int, int>> vYNum;
for (const auto& y : it.second)
{
const auto it = mYToNum.lower_bound(y);
const int num = 1 + ((mYToNum.begin() == it) ? 0 : std::prev(it)->second);
iMax = max(iMax, num);
vYNum.emplace_back(y, num);
}
for(const auto[y,num]: vYNum)
{
const auto it = mYToNum.lower_bound(y);
auto ij = it;
for (; (ij != mYToNum.end()) && (ij->second <= num); ++ij);
mYToNum.erase(it, ij);
if (!mYToNum.count(y))
{
mYToNum[y] = num;
}
}
}
return iMax;
}
};

2023年1月旧代码

class Solution {
public:
int maxEnvelopes(vector<vector>& envelopes) {
std::map<int, vector> mWidthToHeights;
for (const auto& v : envelopes)
{
mWidthToHeights[v[0]].push_back(v[1]);
}
int iMax = 1;
std::map<int, int> mHeightNum;
for ( auto& it : mWidthToHeights)
{
sort(it.second.begin(), it.second.end(),std::greater());
for (auto& height : it.second)
{
auto it = mHeightNum.lower_bound(height);
int iNum =1;
if (mHeightNum.begin() != it)
{//没有套
auto ij = it;
–ij;
iNum = ij->second + 1;
}
iNum = max(iNum,mHeightNum[height]);
auto ij = it;
while ( (ij != mHeightNum.end())&& ( ij->second < iNum))
{
ij++;
}
mHeightNum.erase(it, ij);
mHeightNum[height] = max(mHeightNum[height], iNum);
iMax = max(iMax, mHeightNum[height]);
}
}
return iMax;
}
};

扩展阅读

视频课程

有效学习:明确的目标 及时的反馈 拉伸区(难度合适),可以先学简单的课程,请移步CSDN学院,听白银讲师(也就是鄙人)的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快

速形成战斗了,为老板分忧,请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

相关下载

想高屋建瓴的学习算法,请下载《闻缺陷则喜算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653

充满正能量得对大家说
闻缺陷则喜是一个美好的愿望,早发现问题,早修改问题,给老板节约钱。
墨家名称的来源:有所得以墨记之。
算法终将统治宇宙,而我们统治算法。《喜缺全书》

测试环境

操作系统:win7 开发环境: VS2019 C++17
或者 操作系统:win10 开

发环境: VS2022 C++17

http://www.ritt.cn/news/18939.html

相关文章:

  • 常见的网页布局有哪些惠州seo排名收费
  • 自己做简单的网站在线培训管理系统
  • 网站开发的人怎么样百度seo系统
  • a做爰视频免费观费网站新网站推广最直接的方法
  • 新做好的网站如何做seo电脑培训班电脑培训学校
  • 大兴企业官网网站建设职业技能培训
  • 网站设计的毕业论文结论怎么写新闻稿在线
  • 西安网站的建设企业网站快速排名
  • 北京网站建设推广海外推广服务
  • vs做网站怎么加文件夹google chrome浏览器
  • 如何做提卡网站怎样申请自己的电商平台
  • 好看的个人网站主页推广引流渠道
  • 网站备案是怎么回事seo推广seo技术培训
  • 阜宁做网站网络营销的基本内容有哪些
  • 分公司可以建设网站电商网站seo
  • 高明网站设计多少钱seo快速排名关键词
  • 网站首页滚动图片怎么做百度一下首页网页百度
  • 醴陵网站设计线上营销推广方案模板
  • 南昌网站建设服务真实有效百度关键词优化的意思
  • 东莞网站建设怎么样靠谱的免费建站
  • 开鲁企业网站建设十大品牌营销策划公司
  • 怎么做简历的网站谷歌网站优化
  • 优惠券网站cms建设怎么制作自己的网站网页
  • 重庆市全面解封百度seo搜索引擎优化方案
  • 做网站流程如何推广一个产品
  • 网站开发接单百度新闻官网
  • 毕设网站建设学it学费大概多少钱
  • 怎么做简单的企业网站营销手机都有什么功能啊
  • 网站备案信息被工信部删除河源市seo点击排名软件价格
  • 常见的网站推广方案今日的头条新闻