优秀企业网站设计制作,江苏SEO网站建设,设计logo素材,怎么做班级网站题目及解法一#xff1a;
https://blog.csdn.net/he_zhidan/article/details/134362273
分析
第一步#xff0c;选择各3对应的1#xff0c;如果有多个符合对应最小的1#xff0c;记录num[0,j)中的最小值iMin#xff0c;如果nums[j]大于iMin#xff0c;则m3To1 [nums[j…题目及解法一
https://blog.csdn.net/he_zhidan/article/details/134362273
分析
第一步选择各3对应的1如果有多个符合对应最小的1记录num[0,j)中的最小值iMin如果nums[j]大于iMin则m3To1 [nums[j]] iMin否则等于一个不存在的大数比如1000100010001。 第二步枚举2m31的key是3的值value是1的值寻找key大于nums[k]中是否存在value小于nums[k]。如果key1 key0且value1 value0。如果k0大于nums[k]则k1一定大于nums[k]如果value0小于nums[k]则vaule1也小于nums[k]。故key1淘汰了key0。淘汰后key和value都是按升序排序。第一个大于nums[k]的key对应的value最小如果此value不小于nums[k]则其它value更不符合。 先要判断是否被旧值淘汰再看是否淘汰旧值。
核心代码
class Solution{ public: bool find132pattern(vectornums) { m_c nums.size(); const int iNotMayMaxValue 1000 * 1000 * 1000 1; { int iMin iNotMayMaxValue; for (int j 0; j m_c; j) { m3To1[nums[j]] (nums[j] iMin) ? iMin:iNotMayMaxValue; iMin min(iMin, nums[j]); } } //寻找2即nums[k] { std::mapint, int m31; for (int k 0; k m_c; k) { const int iValue nums[k]; auto it m31.upper_bound(iValue); if (m31.end() ! it) { if (it-second nums[k]) { m_iIndex2 k; return true; } } it m31.lower_bound(iValue); const int iOne m3To1[nums[k]]; if ((m31.end()!it)(it-second iOne)) { continue;//被旧值淘汰 } auto ij it; while( it ! m31.begin()) { –it; if (it-second iOne) { it m31.erase(it); } } m31[iValue] iOne; } } return false; } std::unordered_mapint, int m3To1; int m_iIndex2 -1; int m_c; };
测试用例
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() { vector nums; bool res; { Solution slu; nums { 3,5,0,3,4 }; res slu.find132pattern(nums); //Assert(vector{5, 0, 5, 2, 0}, slu.m_v3To1); Assert(4, slu.m_iIndex2); Assert(true, res); } { nums { 1 ,2, 3,4 }; res Solution().find132pattern(nums); Assert(false, res); } { Solution slu; nums { 3,1,4,2 }; res slu.find132pattern(nums); //Assert(vector{4, 4, 0, 1}, slu.m_v3To1); Assert(3, slu.m_iIndex2); Assert(true, res); } { Solution slu; nums { -1,3,2,0 }; res slu.find132pattern(nums); //Assert(vector{4, 0, 0, 0}, slu.m_v3To1); Assert(2, slu.m_iIndex2); Assert(true, res); }
//CConsole::Out(res);}
扩展阅读
视频课程
有效学习明确的目标 及时的反馈 拉伸区难度合适可以先学简单的课程请移步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
