北京公司摇号政策,win7系统优化大师,蛋糕店网站设计模板,佛山外贸网站建设公司本题不同解法
包括题目及代码C二分查找算法#xff1a;132 模式解法一枚举3C二分查找算法#xff1a;132 模式解法二枚举2代码简洁C二分查找算法#xff1a;132 模式解法三枚举1性能最佳C单调向量算法#xff1a;132 模式解法三枚举1代码更简洁C二分查找算法#xff1a;1…本题不同解法
包括题目及代码C二分查找算法132 模式解法一枚举3C二分查找算法132 模式解法二枚举2代码简洁C二分查找算法132 模式解法三枚举1性能最佳C单调向量算法132 模式解法三枚举1代码更简洁C二分查找算法132模式枚举3简洁版代码简洁性能优越C单调向量132模式枚举1简洁版
分析
时间复杂度
枚举1一轮总时间复杂度O(n)。
步骤
for循环分三步 一if语句判断是否存在比iValue大的2。 二while循环更新iMax2。 三if语句当前值加到vRight中。
变量解释
iMax2所有的合法2的最大值vRight记录nums[i1,m_c)中除了已经作为合法2外的值。已经做为合法的2那从vRight中删除不影响结果。删除后都是大于等于iValue值故vRight是降序。
代码
核心代码
class Solution {
public:bool find132pattern(vectorint nums) {m_c nums.size();const int iNotMayMinValue -1000 * 1000 * 1000 - 1;int iMax2 iNotMayMinValue;vectorint vRight;for (int i m_c - 1; i 0; i--){const int iValue nums[i];if (iValue iMax2){m_iIndex1 i;return true;}while (vRight.size() (vRight.back() iValue)){iMax2 max(iMax2, vRight.back());vRight.pop_back();}if (vRight.empty() || (vRight.back() ! iValue)){vRight.emplace_back(iValue);}}return false;}std::unordered_mapint, int m3To2;int m_iIndex1 -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(0, slu.m_iIndex1); 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(1, slu.m_iIndex1); Assert(true, res); } { Solution slu; nums { -1,3,2,0 }; res slu.find132pattern(nums); //Assert(vector{4, 0, 0, 0}, slu.m_v3To1); Assert(0, slu.m_iIndex1); Assert(true, res); } { Solution slu; nums { 1, 0, 1, -4, -3 }; res slu.find132pattern(nums); //Assert(vector{4, 0, 0, 0}, slu.m_v3To1); Assert(-1, slu.m_iIndex1); Assert(false, 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
我想对大家说的话闻缺陷则喜是一个美好的愿望早发现问题早修改问题给老板节约钱。子墨子言之事无终始无务多业。也就是我们常说的专业的人做专业的事。如果程序是一条龙那算法就是他的是睛
