网站建设 有限公司,怎么搜 织梦的网站,做网站公司 衡阳公司,中国室内设计师官网说明
本篇是视频课程的讲义#xff0c;可以看直接查看视频。也可以下载源码#xff0c;包括空源码。 本文涉及的基础知识点
二分查找算法合集
本题不同解法
包括题目及代码C二分查找算法#xff1a;132 模式解法一枚举3C二分查找算法#xff1a;132 模式解法二枚举2代码…说明
本篇是视频课程的讲义可以看直接查看视频。也可以下载源码包括空源码。 本文涉及的基础知识点
二分查找算法合集
本题不同解法
包括题目及代码C二分查找算法132 模式解法一枚举3C二分查找算法132 模式解法二枚举2代码最简洁C二分查找算法132 模式解法三枚举1性能最佳C单调向量算法132 模式解法三枚举1代码更简洁C二分查找算法132模式枚举3简洁版代码简洁性能优越C单调向量132模式枚举1简洁版 题目
给你一个整数数组 nums 数组中共有 n 个整数。132 模式的子序列 由三个整数 nums[i]、nums[j] 和 nums[k] 组成并同时满足i j k 和 nums[i] nums[k] nums[j] 。
如果 nums 中存在 132 模式的子序列 返回 true 否则返回 false 。
示例 1
输入nums [1,2,3,4]
输出false
解释序列中不存在 132 模式的子序列。
示例 2
输入nums [3,1,4,2]
输出true
解释序列中有 1 个 132 模式的子序列 [1, 4, 2] 。
示例 3
输入nums [-1,3,2,0]
输出true
解释序列中有 3 个 132 模式的的子序列[-1, 3, 2]、[-1, 3, 0] 和 [-1, 2, 0] 。
参数范围
n nums.length
1 n 2 * 105
-109 nums[i] 109
分析
分两步。
第一步计算12存储到m_v2To1。m_v2To1[j]等于i表示nums[j] nsum[i]如果有多个合法的i取最小值如果不存在m_v2To1[j]m_c。mValueIndex的key对应数组值nums[i]value对应数组索引ii取[0,j)。由于是从左向右寻找小于某数的数如果i1i0且nums[i1] nums[i0]则i1被淘汰。淘汰后mValueIndex中的数组值按升序排序数组索引按降序排序。如果mValueIndex中存在数组值小于iValue的数那说明存在值、索引都比i小的数i被淘汰。大于等于i的索引还未添加。如果不存在不需要判断当前值和索引是否淘汰已有值因为索引是按从小到大添加的。添加时需要判断当真值是否存在。如果存在则其索引一定小于当前索引无需添加。
第二步遍历m_v2To1寻找是否存在k。mValueIndex的key对应数组值nums[k]value对应数组索引kj取[0,i)。由于是从右向左寻找大于某数的数所以数组值和索引都小的值和索引被淘汰。淘汰后mValueIndex中的数组值按升序排序数组索引按降序排序。由于mValueIndex已有数据中的索引小于当前索引所以只需要考虑淘汰旧值数组值小于等于当前数组值。k需要符合以下三个条件 条件一 nums[k] nums[j] 条件二 k i(即v2To1[j]) 条件三 k j 一定符合不符合的还没添加)
auto it mValueIndex.upper_bound(iValue);
后[it, mValueIndex.end()) 都符合条件一由于索引是降序排序所以只需要判断it-second是否大于i。
核心代码
class Solution {
public: bool find132pattern(vectorint nums) { m_c nums.size(); m_v2To1.assign(m_c, m_c); { mapint, int mValueIndex;//key按升序value按降序排序 for (int j 0; j m_c; j) { const int iValue nums[j]; auto it mValueIndex.lower_bound(iValue); if (mValueIndex.begin() ! it) { auto itPre std::prev(it); m_v2To1[j] itPre-second; continue;//key和value都小于等于iValue和ii被淘汰 } //删除key和value都大于等于iValue和i if (!mValueIndex.count(nums[j])) { mValueIndex[nums[j]] j; } } } //遍历v[2]看是否存在3 { mapint, int mValueIndex;//132的3,从右向左找大于2的值。key按升序value按降序排序 for (int j 0; j m_c; j) { const int iValue nums[j]; auto it mValueIndex.upper_bound(iValue); if (mValueIndex.end() ! it) { if (it-second m_v2To1[j]) { m_iIndex3 it-second; return true; } } while (mValueIndex.size() (mValueIndex.begin()-first iValue)) { mValueIndex.erase(mValueIndex.begin()); } mValueIndex[iValue] j; } } return false; } vectorint m_v2To1;//v[i]等于j表示nums[i] nsum[j]如果有多个合法的j取最小值如果不存在v[i]m_c。 int m_iIndex3-1; int m_c;
};
测试用例
templateclass T
void Assert(const T t1, const T t2)
{ assert(t1 t2);
} templateclass T
void Assert(const vectorT v1, const vectorT v2)
{ if (v1.size() ! v2.size()) { assert(false); return; } for (int i 0; i v1.size(); i) { Assert(v1[i], v2[i]); }
} int main()
{ vectorint nums; bool res; { Solution slu; nums { 3,5,0,3,4 }; res slu.find132pattern(nums); Assert(vectorint{5, 0, 5, 2,0}, slu.m_v2To1); Assert(1, slu.m_iIndex3); 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(vectorint{4, 4, 0, 1}, slu.m_v2To1); Assert(2, slu.m_iIndex3); Assert(true, res); } { Solution slu; nums { -1,3,2,0 }; res slu.find132pattern(nums); Assert(vectorint{4, 0, 0, 0}, slu.m_v2To1); Assert(1, slu.m_iIndex3); Assert(true, res); } //CConsole::Out(res);
} 其它
学院课程 基础算法的C实现课程请点击下面的CSDN学院的链接。讲义有算法详解。 2024年1月15之前完全免费之后绝大部分免费 https://edu.csdn.net/course/detail/38771 C#入职培训 此课程的目的让新同事更快完成从学生到C#程序员的转换更快上手完成C#的开发工作。 https://edu.csdn.net/course/detail/38768 C入职培训 让新同事更快完成从学生到C程序员的转换更快上手完成C的开发工作。 https://edu.csdn.net/course/detail/32049
运行验证环境
Win10 VS2022 Ck17 或win7 VS2019 C17 每天都补充正能量 好好学习天天向上。 事无终始无务多业。 是故置本不安者无务丰末。
相关下载
如果你时间宝贵只想看精华请到CSDN下载频道下载《闻缺陷则喜算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653
