唐山网站从哪里找,做网站必须要推广吗,网站建设加盟代理,seo排名哪家公司好本文涉及的基础知识点
二分查找
题目
给你一个二维整数数组 envelopes #xff0c;其中 envelopes[i] [wi, hi] #xff0c;表示第 i 个信封的宽度和高度。 当另一个信封的宽度和高度都比这个信封大的时候#xff0c;这个信封就可以放进另一个信封里#xff0c;如同俄罗…本文涉及的基础知识点
二分查找
题目
给你一个二维整数数组 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::mapint, 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(vectorvector envelopes) { std::mapint, vector mXToYS; for (const auto v : envelopes) { mXToYS[v[0]].emplace_back(v[1]); } std::mapint, int mPreYToNum;//y值对应最大数量y值越大对应的数量越大否则被淘汰了 int iMax 0; for (const auto it : mXToYS) { std::mapint, 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; vectorvector 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的ymYToNum[x取[0,x) y对应最大套娃数量vectorpairint, int vYNum当前x各y对应数量
注意
x相同无法套娃所以必须等当前x处理完毕才能更新mYToNum。 y值越大对应的数量越大否则被淘汰了。所以mYToNum的键和值都是升序。 y小于当前y的不会淘汰当前y因为当前长度就是小于y的最大长度1。 所以只会被相等的y淘汰。 当前y 可能淘汰比当前y大的。
代码
class Solution { public: int maxEnvelopes(vectorvector envelopes) { std::mapint, vector mXToYS; for (const auto v : envelopes) { mXToYS[v[0]].emplace_back(v[1]); } std::mapint, int mYToNum;//y值对应最大数量 int iMax 0; for (const auto it : mXToYS) { vectorpairint, 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(vectorvector envelopes) { std::mapint, vector mWidthToHeights; for (const auto v : envelopes) { mWidthToHeights[v[0]].push_back(v[1]); } int iMax 1; std::mapint, 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 C17 或者 操作系统win10 开
发环境 VS2022 C17
