C++单调向量算法:132 模式解法三枚举1

简介: C++单调向量算法:132 模式解法三枚举1

本题不同解法

分析

时间复杂度

2轮循环时间复杂度都是O(n)。

步骤

第一步

枚举32,再将2to3,转成3to2。枚举2。v3ValueIndex|记录nums[0,k)所有的值的索引。然后在v3ValueIndex中寻找值大于iValue,如果有多个结果取索引最大的。如果value0 <= value1且index0 <= index1,则value0被index0淘汰。能选取vaule0则必定能选择vaule1,而index1比index0大。淘汰后,值按降序排序,3Index按升序排序。由于索引是越来越大,所以只会淘汰旧值,不会被旧值淘汰。由于淘汰值小的,所以可以从末尾淘汰。按索引升序插入,而索引是按升序排序的,所以插入也在末尾。故可以用栈或向量代替有序映射。在尾部增加、删除时间复杂度都是O(1)。

第二步

枚举1。如果m3IndexTo2Value(i,m_c)中存在比nums[i]大的值,则存在132模式,否则不存在。注意:m3IndexTo2Value 有些key会不存在。std::unordered_map不存在的值是0,而本题的值可能是负数。

关于2to3转成3to2

计算2to3的过程中,会淘汰一些组合,不影响结果。2to3转成3to2的时候,也会淘汰一些组合,被淘汰的不影响最终结果。m3IndexTo2Value, 3Index相同,淘汰值小的。如果值小的都大于nums[i],那么值的一定大于nums[i]。我们只要确保没被淘汰的组合都被枚举到,旧可以了。

代码

核心代码

class Solution {
public:
  bool find132pattern(vector<int>& nums) {
    m_c = nums.size();
    const int iNotMayMinValue = -1000 * 1000 * 1000 - 1;
    {
      vector < std::pair<int, int>> v3ValueIndex;//3Value的值按降序排序,3Index按升序排序
      for (int k =0 ; k < m_c ; k++ )
      {
        const int& iValue = nums[k];
        while (v3ValueIndex.size() && (v3ValueIndex.back().first <= iValue))
        {
          v3ValueIndex.pop_back();
        }
        if (v3ValueIndex.size())
        {
          const int i3Index = v3ValueIndex.back().second;
          if (!m3IndexTo2Value.count(i3Index) || (m3IndexTo2Value[i3Index] < iValue))
          {
            m3IndexTo2Value[i3Index] = iValue;
          }
        }
        v3ValueIndex.emplace_back(iValue, k);
      }
    }
    //寻找1,即nums[i]
    {
      int iMaxTow = iNotMayMinValue;
      for (int i = m_c - 1; i >= 0; i--)
      {
        const int& iValue = nums[i];
        if( iMaxTow > iValue )
        {
          m_iIndex1 = i;
          return true;
        }
        if (m3IndexTo2Value.count(i))
        {
          iMaxTow = max(iMaxTow, m3IndexTo2Value[i]);
        }
      }
    }
    return false;
  }
  std::unordered_map<int, int> m3IndexTo2Value;
  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

洒家想对大家说的话
闻缺陷则喜是一个美好的愿望,早发现问题,早修改问题,给老板节约钱。
墨家名称的来源:有所得以墨记之。
如果程序是一条龙,那算法就是他的是睛

测试环境

操作系统:win7 开发环境: VS2019 C++17

或者 操作系统:win10 开发环境: VS2022 C++17


相关文章
|
1月前
|
存储 算法 测试技术
【C++数据结构——树】二叉树的遍历算法(头歌教学实验平台习题) 【合集】
本任务旨在实现二叉树的遍历,包括先序、中序、后序和层次遍历。首先介绍了二叉树的基本概念与结构定义,并通过C++代码示例展示了如何定义二叉树节点及构建二叉树。接着详细讲解了四种遍历方法的递归实现逻辑,以及层次遍历中队列的应用。最后提供了测试用例和预期输出,确保代码正确性。通过这些内容,帮助读者理解并掌握二叉树遍历的核心思想与实现技巧。
48 2
|
2月前
|
存储 算法 安全
基于红黑树的局域网上网行为控制C++ 算法解析
在当今网络环境中,局域网上网行为控制对企业和学校至关重要。本文探讨了一种基于红黑树数据结构的高效算法,用于管理用户的上网行为,如IP地址、上网时长、访问网站类别和流量使用情况。通过红黑树的自平衡特性,确保了高效的查找、插入和删除操作。文中提供了C++代码示例,展示了如何实现该算法,并强调其在网络管理中的应用价值。
|
1月前
|
存储 算法 安全
基于哈希表的文件共享平台 C++ 算法实现与分析
在数字化时代,文件共享平台不可或缺。本文探讨哈希表在文件共享中的应用,包括原理、优势及C++实现。哈希表通过键值对快速访问文件元数据(如文件名、大小、位置等),查找时间复杂度为O(1),显著提升查找速度和用户体验。代码示例展示了文件上传和搜索功能,实际应用中需解决哈希冲突、动态扩容和线程安全等问题,以优化性能。
|
2月前
|
算法 搜索推荐
如何用CRDT算法颠覆文档协作模式?
在局域网环境下,高效文档协同编辑面临版本冲突等核心技术挑战,影响协作效率和成果质量。为解决此问题,可采用基于CRDT的算法,允许多用户无冲突实时编辑;或将协同操作模块化,通过任务看板优化协作流程,减少冲突,提高团队效率。未来,局域网协同编辑将更加场景化与个性化,深入探索组织协作文化。
|
4月前
|
存储 算法 C++
高精度算法(加、减、乘、除,使用c++实现)
高精度算法(加、减、乘、除,使用c++实现)
1108 0
高精度算法(加、减、乘、除,使用c++实现)
|
4月前
|
前端开发 算法 JavaScript
无界SaaS模式深度解析:算力算法、链接力、数据确权制度
私域电商的无界SaaS模式涉及后端开发、前端开发、数据库设计、API接口、区块链技术、支付和身份验证系统等多个技术领域。本文通过简化框架和示例代码,指导如何将核心功能转化为技术实现,涵盖用户管理、企业店铺管理、数据流量管理等关键环节。
|
4月前
|
存储 算法 决策智能
【算法】博弈论(C/C++)
【算法】博弈论(C/C++)
|
1月前
|
C++ 芯片
【C++面向对象——类与对象】Computer类(头歌实践教学平台习题)【合集】
声明一个简单的Computer类,含有数据成员芯片(cpu)、内存(ram)、光驱(cdrom)等等,以及两个公有成员函数run、stop。只能在类的内部访问。这是一种数据隐藏的机制,用于保护类的数据不被外部随意修改。根据提示,在右侧编辑器补充代码,平台会对你编写的代码进行测试。成员可以在派生类(继承该类的子类)中访问。成员,在类的外部不能直接访问。可以在类的外部直接访问。为了完成本关任务,你需要掌握。
68 19
|
1月前
|
存储 编译器 数据安全/隐私保护
【C++面向对象——类与对象】CPU类(头歌实践教学平台习题)【合集】
声明一个CPU类,包含等级(rank)、频率(frequency)、电压(voltage)等属性,以及两个公有成员函数run、stop。根据提示,在右侧编辑器补充代码,平台会对你编写的代码进行测试。​ 相关知识 类的声明和使用。 类的声明和对象的声明。 构造函数和析构函数的执行。 一、类的声明和使用 1.类的声明基础 在C++中,类是创建对象的蓝图。类的声明定义了类的成员,包括数据成员(变量)和成员函数(方法)。一个简单的类声明示例如下: classMyClass{ public: int
50 13
|
1月前
|
编译器 数据安全/隐私保护 C++
【C++面向对象——继承与派生】派生类的应用(头歌实践教学平台习题)【合集】
本实验旨在学习类的继承关系、不同继承方式下的访问控制及利用虚基类解决二义性问题。主要内容包括: 1. **类的继承关系基础概念**:介绍继承的定义及声明派生类的语法。 2. **不同继承方式下对基类成员的访问控制**:详细说明`public`、`private`和`protected`继承方式对基类成员的访问权限影响。 3. **利用虚基类解决二义性问题**:解释多继承中可能出现的二义性及其解决方案——虚基类。 实验任务要求从`people`类派生出`student`、`teacher`、`graduate`和`TA`类,添加特定属性并测试这些类的功能。最终通过创建教师和助教实例,验证代码
50 5