网站在百度上搜不到,沈阳建设局网站,运营商app下载,网站建设上市公司本文涉及知识点
贪心 决策包容性
LeetCode757. 设置交集大小至少为2
给你一个二维整数数组 intervals #xff0c;其中 intervals[i] [starti, endi] 表示从 starti 到 endi 的所有整数#xff0c;包括 starti 和 endi 。 包含集合 是一个名为 nums 的数组#xff0c;并…本文涉及知识点
贪心 决策包容性
LeetCode757. 设置交集大小至少为2
给你一个二维整数数组 intervals 其中 intervals[i] [starti, endi] 表示从 starti 到 endi 的所有整数包括 starti 和 endi 。 包含集合 是一个名为 nums 的数组并满足 intervals 中的每个区间都 至少 有 两个 整数在 nums 中。 例如如果 intervals [[1,3], [3,7], [8,9]] 那么 [1,2,4,7,8,9] 和 [2,3,4,8,9] 都符合 包含集合 的定义。返回包含集合可能的最小大小。 示例 1 输入intervals [[1,3],[3,7],[8,9]] 输出5 解释nums [2, 3, 4, 8, 9]. 可以证明不存在元素数量为 4 的包含集合。 示例 2 输入intervals [[1,3],[1,4],[2,5],[3,5]] 输出3 解释nums [2, 3, 4]. 可以证明不存在元素数量为 2 的包含集合。 示例 3 输入intervals [[1,2],[2,3],[2,4],[4,5]] 输出5 解释nums [1, 2, 3, 4, 5]. 可以证明不存在元素数量为 4 的包含集合。 提示 1 intervals.length 3000 intervals[i].length 2 0 starti endi 108
决策包容性
令intervals[i1]的end最小。假定其在某个最优解包括的数为x1,x2。我们将x1和x2换成endi1和endi1-1也必定是最优解。 对于 ∀ \forall ∀i 包括x2那说明begini x2 endi 。由于 endi1 x2 且endi1endi。故endi1也包括。 对于 ∀ \forall ∀i 如果包括x1和x2x1 x2 endi ,故endi1-1 endi ,endi1-1 x1 。即endi1-1也包括。 故 setHas 记录已有数字。 按end升序处理如果setHas包括两个数字则忽略。 如果包括一个数字将endi加入。 如果包括0个数字将endi和endi-1也加入。
cnt2 如何判断setHas需要多少个数字 it setHas.lower(begin); if( it合法 ⋆ \star ⋆it end ){ cnt–; it; 如果合法且 ⋆ \star ⋆it end ,再–。 时间复杂度O(nlogn) 二分查找的时间复杂度O(logn)。
错误
{1,3}{3,7}{5,7} {5,7}时试图 增加7但7已经存在。 当end相等的时候begin大的再前面或end相等时忽略begin小的。 当setHas有0个数时自然不包括endi和endi-1。 有一个数时 如果不存在相等的endi则setHas一定不包括endi。 如果相等的endibegini大的在前。 当前一定包括两个数无需处理。
代码
核心代码
class Solution {
public:int intersectionSizeTwo(vectorvectorint intervals) {sort(intervals.begin(), intervals.end(), [](vectorint v1, vectorint v2) {return (v1[1] v2[1])||(( v1[1] v2[1])(v1[0] v2[0])); });setint setHas;for (const auto v : intervals) {auto it setHas.lower_bound(v[0]);int cnt 2;if ((setHas.end() ! it) (*it v[1])) {cnt--;it;if ((setHas.end() ! it) (*it v[1])) {cnt--;}}if (cnt 1 ) {setHas.emplace(v[1]);}if (2 cnt) {setHas.emplace(v[1]-1);}}return setHas.size();}
};
单元测试 templateclass T1, class T2
void AssertEx(const T1 t1, const T2 t2)
{Assert::AreEqual(t1, t2);
}
void AssertEx( double t1, double t2)
{auto str std::to_wstring(t1) std::wstring(1,32) std::to_wstring(t2);Assert::IsTrue(abs(t1 - t2) 1e-5,str.c_str() );
}templateclass T
void AssertEx(const vectorT v1, const vectorT v2)
{Assert::AreEqual(v1.size(), v2.size());for (int i 0; i v1.size(); i){Assert::AreEqual(v1[i], v2[i]);}
}templateclass T
void AssertV2(vectorvectorT vv1, vectorvectorT vv2)
{sort(vv1.begin(), vv1.end());sort(vv2.begin(), vv2.end());Assert::AreEqual(vv1.size(), vv2.size());for (int i 0; i vv1.size(); i){AssertEx(vv1[i], vv2[i]);}
}namespace UnitTest
{vectorvectorint intervals;TEST_CLASS(UnitTest){public:TEST_METHOD(TestMethod00){intervals { {1,3},{3,7},{8,9} };auto res Solution().intersectionSizeTwo(intervals);AssertEx(5, res);}TEST_METHOD(TestMethod01){intervals { {1,3},{1,4},{2,5},{3,5} };auto res Solution().intersectionSizeTwo(intervals);AssertEx(3, res);}TEST_METHOD(TestMethod02){intervals { {1,2},{2,3},{2,4},{4,5} };auto res Solution().intersectionSizeTwo(intervals);AssertEx(5, res);}TEST_METHOD(TestMethod03){intervals { {1,3},{3,7},{5,7},{7,8} };auto res Solution().intersectionSizeTwo(intervals);AssertEx(5, res);}};
}扩展阅读
视频课程
先学简单的课程请移步CSDN学院听白银讲师也就是鄙人的讲解。 https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了为老板分忧请学习C#入职培训、C入职培训等课程 https://edu.csdn.net/lecturer/6176
相关推荐
我想对大家说的话《喜缺全书算法册》以原理、正确性证明、总结为主。按类别查阅鄙人的算法文章请点击《算法与数据汇总》。有效学习明确的目标 及时的反馈 拉伸区难度合适 专注闻缺陷则喜(喜缺)是一个美好的愿望早发现问题早修改问题给老板节约钱。子墨子言之事无终始无务多业。也就是我们常说的专业的人做专业的事。如果程序是一条龙那算法就是他的是睛
测试环境
操作系统win7 开发环境 VS2019 C17 或者 操作系统win10 开发环境 VS2022 C17 如无特殊说明本算法用**C**实现。
