【动态规划】LeetCode2552：优化了6版的1324模式

本文涉及的基础知识点

C++算法：前缀和、前缀乘积、前缀异或的原理、源码及测试用例 包括课程视频
动态规划

本题其它解法

C++前缀和算法的应用：统计上升四元组

类似题解法

包括题目及代码C++二分查找算法：132 模式解法一枚举3
C++二分查找算法：132 模式解法二枚举2
代码简洁C++二分查找算法：132 模式解法三枚举1
性能最佳C++单调向量算法：132 模式解法三枚举1
代码更简洁C++二分查找算法：132模式枚举3简洁版
代码简洁，性能优越C++单调向量：132模式枚举1简洁版

题目

给你一个长度为 n 下标从 0 开始的整数数组 nums ，它包含 1 到 n 的所有数字，请你返回上升四元组的数目。
如果一个四元组 (i, j, k, l) 满足以下条件，我们称它是上升的：
0 <= i < j < k < l < n 且
nums[i] < nums[k] < nums[j] < nums[l] 。
示例 1：
输入：nums = [1,3,2,4,5]
输出：2
解释：

  • 当 i = 0 ，j = 1 ，k = 2 且 l = 3 时，有 nums[i] < nums[k] < nums[j] < nums[l] 。
  • 当 i = 0 ，j = 1 ，k = 2 且 l = 4 时，有 nums[i] < nums[k] < nums[j] < nums[l] 。
    没有其他的四元组，所以我们返回 2 。
    示例 2：
    输入：nums = [1,2,3,4]
    输出：0
    解释：只存在一个四元组 i = 0 ，j = 1 ，k = 2 ，l = 3 ，但是 nums[j] < nums[k] ，所以我们返回 0 。
    参数范围：
    4 <= nums.length <= 4000
    1 <= nums[i] <= nums.length
    nums 中所有数字 互不相同 ，nums 是一个排列。

第一版

分析

1324模式，第1的小在最前面，其次是第3小，再次是第2小的，最后是第4小的。

变量解释

v21v21[i2][i1] = k，表示 nums[i2]和nums[x]组成12模式的数量是k，x取值范围[0,i1)
v32v32[i3][i2]=k，表示以num[i3]为3以nums[x]为2 组成的132模式的数量是k，x取[0,i2)

代码

class Solution {
public:
long long countQuadruplets(vector& nums) {
m_c = nums.size();
//v21[i2][i1] = k，表示 nums[i2]和nums[x]组成12模式的数量是k，x取值范围[0,i1)
vector<vector> v21(m_c,vector(m_c+1));
for (int i2 = 0; i2 < m_c; i2++)
{
for (int i1 = 0; i1 < i2; i1++)
{
v21[i2][i1 + 1] = v21[i2][i1] + (nums[i1] < nums[i2]);
}
}
vector<vector> v32(m_c, vector(m_c + 1));
for (int i3 = 0; i3 < m_c; i3++)
{
for (int i2 = i3 + 1; i2 < m_c; i2++)
{
v32[i3][i2 + 1] = v32[i3][i2];
if (nums[i3] > nums[i2])
{
v32[i3][i2 + 1] += v21[i2][i3];
}
}
}
long long llRet = 0;
for (int i3 = 0; i3 < m_c; i3++)
{
for (int i4 = i3 + 1; i4 < m_c; i4++)
{
if (nums[i3] < nums[i4])
{
llRet += v32[i3][i4];
}
}
}
return llRet;
}
int m_c;
};

测试用例

template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{
	if (v1.size() != v2.size())
	{
		assert(false);
		return;
	}
	for (int i = 0; i < v1.size(); i++)
	{
		assert(v1[i] == v2[i]);
	}
}

template<class T>
void Assert(const T& t1, const T& t2)
{
	assert(t1 == t2);
}

int main()
{
	Solution slu;
	vector<int> nums ;
	long long res;
	nums = { 1, 3, 2, 4, 5 };
	res = slu.countQuadruplets(nums);
	Assert(2LL, res);
	nums = { 1, 2,3,4 };
	res = slu.countQuadruplets(nums);
	Assert(0LL, res);
	nums = { 4,3,2,1 };
	res = slu.countQuadruplets(nums);
	Assert(0LL, res);
	nums = { 4,3,2,6,5,1 };
	res = slu.countQuadruplets(nums);
	Assert(0LL, res);
	nums = { 1,3,2,4 };
	res = slu.countQuadruplets(nums);
	Assert(1LL, res);
	nums = { 2,1,4,3,5 };
	res = slu.countQuadruplets(nums);
	Assert(2LL, res);
	nums.clear();
	for (int i = 0; i < 4000; i++)
	{
		nums.emplace_back(i + 1);
	}
	res = slu.countQuadruplets(nums);
	Assert(0LL, res);
	//CConsole::Out(res);
}

第二版

三步是如此相似，也许可以合并。第一步的循环似乎不同。我们把第一步的第一层循环换到第二层就更相似了。修改后的第一步：

	for (int i1 = 0; i1 < m_c ; i1++)		
		{
			for (int i2 = i1+1; i2 < m_c; i2++)
			{
				v21[i2][i1 + 1] = v21[i2][i1] + (nums[i1] < nums[i2]);
			}
		}

第三版

第一层 的循环变量改成i,第一层的循环变量改成j。

class Solution {
public:
	long long countQuadruplets(vector<int>& nums) {
		m_c = nums.size();
		//v21[i2][i1] = k，表示 nums[i2]和nums[x]组成12模式的数量是k，x取值范围[0,i1)
		vector<vector<int>> v21(m_c,vector<int>(m_c+1));
		for (int i = 0; i < m_c ; i++)		
		{
			for (int j = i+1; j < m_c; j++)
			{
				v21[j][i + 1] = v21[j][i] + (nums[i] < nums[j]);
			}
		}
		vector<vector<int>> v32(m_c, vector<int>(m_c + 1));
		for (int i = 0; i < m_c; i++)
		{
			for (int j = i + 1; j < m_c; j++)
			{
				v32[i][j + 1] = v32[i][j];
				if (nums[i] > nums[j])
				{
					v32[i][j + 1] += v21[j][i];
				}
			}
		}
		long long llRet = 0;
		for (int i = 0; i < m_c; i++)
		{
			for (int j = i + 1; j < m_c; j++)
			{
				if (nums[i] < nums[j])
				{
					llRet += v32[i][j];
				}
			}
		}
		return llRet;
	}
	int m_c;
};

第四版

三轮循环合并。

class Solution {
public:
	long long countQuadruplets(vector<int>& nums) {
		m_c = nums.size();
		//v21[i2][i1] = k，表示 nums[i2]和nums[x]组成12模式的数量是k，x取值范围[0,i1)
		vector<vector<int>> v21(m_c,vector<int>(m_c+1));
		vector<vector<int>> v32(m_c, vector<int>(m_c + 1));
		long long llRet = 0;
		for (int i = 0; i < m_c ; i++)		
		{
			for (int j = i+1; j < m_c; j++)
			{
				v21[j][i + 1] = v21[j][i] + (nums[i] < nums[j]);
				v32[i][j + 1] = v32[i][j];
				if (nums[i] > nums[j])
				{
					v32[i][j + 1] += v21[j][i];
				}
				if (nums[i] < nums[j])
				{
					llRet += v32[i][j];
				}
			}
		}
		return llRet;
	}
	int m_c;
};

第五版

v2 只用到三处, v21[j][i + 1] 和 v21[j][i]，可以简化成一维变量。
优化后，代码如下：

class Solution {
public:
	long long countQuadruplets(vector<int>& nums) {
		m_c = nums.size();
		//v21[i2][i1] = k，表示 nums[i2]和nums[x]组成12模式的数量是k，x取值范围[0,i1)
		vector<vector<int>> v32(m_c, vector<int>(m_c + 1));
		long long llRet = 0;
		vector<int> v21(m_c);
		for (int i = 0; i < m_c ; i++)		
		{			
			for (int j = i+1; j < m_c; j++)
			{		
				v32[i][j + 1] = v32[i][j];
				if (nums[i] > nums[j])
				{
					v32[i][j + 1] += v21[j];
				}
				if (nums[i] < nums[j])
				{
					llRet += v32[i][j];
				}
				v21[j] +=  (nums[i] < nums[j]);
			}
		}
		return llRet;
	}
	int m_c;
};

第六版

v32只用到v32[i][j + 1] v32[i][j]，我们可以简化成一个变量i32，i发生变化的时候赋初值0。

class Solution {
public:
	long long countQuadruplets(vector<int>& nums) {
		m_c = nums.size();
		//v21[i2][i1] = k，表示 nums[i2]和nums[x]组成12模式的数量是k，x取值范围[0,i1)
		long long llRet = 0;
		vector<int> v21(m_c);
		for (int i = 0; i < m_c ; i++)		
		{	
			int i32 = 0;
			for (int j = i+1; j < m_c; j++)
			{					
				if (nums[i] < nums[j])
				{
					llRet += i32;
				}
				if (nums[i] > nums[j])
				{
					i32 += v21[j];
				}
				v21[j] +=  (nums[i] < nums[j]);
			}
		}
		return llRet;
	}
	int m_c;
};

扩展阅读

视频课程

有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步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

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/202224.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

CSAPP bomb_lab：phase_5

CSAPP bomb_lab：phase_5

phase_5的汇编代码 0x0000000000401062 <0>: push %rbx0x0000000000401063 <1>: sub $0x20,%rsp0x0000000000401067 <5>: mov %rdi,%rbx0x000000000040106a <8>: mov %fs:0x28,%rax0x0000000000401073 <17>: mov …
阅读更多...
hql面试题之字符串使用split分割，并选择其中的一部分字段的问题

hql面试题之字符串使用split分割，并选择其中的一部分字段的问题

版本&#xff1a;20231109 1.题目&#xff1a; 有两张表,a表有id和abstringr两个字段&#xff0c;b表也有id和bstr两个字段&#xff0c;具体如下 A表&#xff1a; 1abc,bcd,cdf2123,456,789 B表: 1acddef2123456 在a表的abstring字段中用‘,’分割&#xff0c;并取出前两…
阅读更多...
sqli-labs靶场详解（less32-less37）

sqli-labs靶场详解（less32-less37）

宽字节注入 原理在下方 目录 less-32 less-33 less-34 less-35 less-36 less-37 less-32 正常页面 ?id1 下面有提示 获取到了Hint: The Query String you input is escaped as : 1\ ?id1 看来是把参数中的非法字符就加上了转义 从而在数据库中只能把单引号当成普通的字…
阅读更多...
Go 从编译到执行

Go 从编译到执行

一、Go运行编译简介 Go语言&#xff08;也称为Golang&#xff09;自从2009年由Google发布以来&#xff0c;已成为现代软件开发中不可或缺的一部分。设计者Rob Pike, Ken Thompson和Robert Griesemer致力于解决多核处理器、网络系统和大型代码库所引发的现实世界编程问题。我们…
阅读更多...
TA-Lib学习研究笔记——Overlap Studies（二）上

TA-Lib学习研究笔记——Overlap Studies（二）上

TA-Lib学习研究笔记——Overlap Studies&#xff08;二&#xff09; 1. Overlap Studies 指标 [BBANDS, DEMA, EMA, HT_TRENDLINE, KAMA, MA, MAMA, MAVP, MIDPOINT, MIDPRICE, SAR, SAREXT, SMA, T3, TEMA, TRIMA, WMA]2.数据准备 get_data函数参数&#xff08;代码&#x…
阅读更多...
msyql迁移到mongodb

msyql迁移到mongodb

关系型数据库迁移到mongodb的理由 高并发需求&#xff0c;关系型数据库不容易扩展 快速迭代 灵活的json模式 大数据量需求 应用迁移难度&#xff1a; 关系型到关系 oracle-》mysql oracle -》 postgresql 关系到文档- oracle -》 mongodb 需要考虑&#xff1a; 总体架构&#…
阅读更多...
阿里云Windows server2016 安装Docker

阿里云Windows server2016 安装Docker

阿里云Windows server2016 安装Docker 1 软件环境介绍2 下载更新2.1 windowsR 输入sconfig2.2 下载最新版的安装包&#xff0c;安装并重启2.3 下载并安装更新2.4 以管理员方式运行powershell2.5 将Tls修改成二级2.6 安装NuGet服务2.7 安装docker模块2.7 安装 docker包 32.8 查看…
阅读更多...
Ajax的使用方法

Ajax的使用方法

1,什么是Ajax&#xff1f; Ajax&#xff08;异步Javascript和XML&#xff09;&#xff0c;是指一种创建交互式网页应用的网页开发技术。 2&#xff0c;Ajax的作用 Ajax可以使网页实现异步更新----即在不更新整个页面的情况下实现对某一部分进行更新。 简单来说Ajax就是用于连接…
阅读更多...
顶级大厂Quora如何优化数据库性能？

顶级大厂Quora如何优化数据库性能？

Quora 的流量涉及大量阅读而非写入&#xff0c;一直致力于优化读和数据量而非写。 0 数据库负载的主要部分 读取数据量写入 1 优化读取 1.1 不同类型的读需要不同优化 ① 复杂查询&#xff0c;如连接、聚合等 在查询计数已成为问题的情况下&#xff0c;它们在另一个表中构…
阅读更多...
HT for Web (Hightopo) 使用心得（5）- 动画的实现

HT for Web (Hightopo) 使用心得（5）- 动画的实现

其实&#xff0c;在 HT for Web 中&#xff0c;有多种手段可以用来实现动画。我们这里仍然用直升机为例&#xff0c;只是更换了场景。增加了巡游过程。 使用 HT 开发的一个简单网页直升机巡逻动画&#xff08;Hightopo 使用心得&#xff08;5&#xff09;&#xff09; 这里主…
阅读更多...
纯js实现录屏并保存视频到本地的尝试

纯js实现录屏并保存视频到本地的尝试

前言&#xff1a;先了解下&#xff1a;navigator.mediaDevices&#xff0c;mediaDevices 是 Navigator 只读属性&#xff0c;返回一个 MediaDevices 对象&#xff0c;该对象可提供对相机和麦克风等媒体输入设备的连接访问&#xff0c;也包括屏幕共享。 const media navigator…
阅读更多...
【brew】Mac上安装vue3

【brew】Mac上安装vue3

先安装node。 这里我从其他博客找的方案&#xff0c;原始脚本下载太慢了。 cnpm的安装&#xff1a; 让npm更快一点。 npm install -g cnpm --registryhttps://registry.npm.taobao.org安装vue脚手架 2.0版本&#xff1a;sudo npm install -g vue-cli 3.0版本&#xff1a; sud…
阅读更多...
2023.11.26使用opencv调节图片亮度

2023.11.26使用opencv调节图片亮度

2023.11.26使用opencv调节图片亮度 测试一些opencv对图片的处理效果&#xff0c;方法比较简单&#xff0c;找出所有像素点&#xff0c;然后将RGB三色的亮度分别进行调节即可&#xff0c;同类可以进行像素级的处理。测试结果和项目代码如下&#xff1a; 使用OpenCV调节图拍亮…
阅读更多...
Unity引擎：创造无限可能的游戏开发平台

Unity引擎：创造无限可能的游戏开发平台

Unity引擎&#xff1a;创造无限可能的游戏开发平台 一、Unity引擎概述1.1 什么是Unity引擎&#xff1f;1.2 Unity引擎的特点和优势 二、Unity开发环境和工具2.1 Unity编辑器2.2 支持的平台2.3 脚本语言2.4 图形和音频工具 三、Unity游戏开发流程四、示例应用场景五、结论&#…
阅读更多...
java使用poi读写excel（处理上下标和科学计数法）

java使用poi读写excel（处理上下标和科学计数法）

Background 要读写如下图所示的excel&#xff0c;符号和单位中包含上下标&#xff0c;在读写时需要特殊处理&#xff1b;取值列中是科学计数法&#xff0c;读写时需要特殊处理&#xff1b;excel中包含多个sheet&#xff0c;读的时候把所有sheet的数据读出来&#xff0c;写的时候…
阅读更多...
分割掩模 VS 掩膜

分割掩模 VS 掩膜

掩膜 Mask分割掩模 Segmentation Mask总结示例 掩膜 Mask “掩膜” 是指一种用于 标识或遮蔽图像中特定区域 的 图像。 在图像处理中&#xff0c;掩膜通常是一个 二值图像&#xff0c;其中的 像素值为 0 或 1。binary Mask 叫做二元掩膜&#xff0c;如下图所示&#xff1a; 这…
阅读更多...
Airtest进阶使用篇！提高脚本稳定性 + 批量运行脚本！

Airtest进阶使用篇！提高脚本稳定性 + 批量运行脚本！

一、背景 今天彭于晏为大家分享Airtest进阶使用篇&#xff0c;主要包含两块的内容&#xff1a; 提高脚本稳定性批量运行脚本生成测试报告 二、提高脚本稳定性 1、添加全局配置: #全局设置 ST.FIND_TIMEOUT10 #设置隐式等待时长,默认识别图片时间是30秒&#xff0c;可改为…
阅读更多...
[黑皮系列] 计算机网络：自顶向下方法（第8版）

[黑皮系列] 计算机网络：自顶向下方法（第8版）

文章目录 《计算机网络&#xff1a;自顶向下方法&#xff08;第8版&#xff09;》简介作者目录前言配套公开课 《计算机网络&#xff1a;自顶向下方法&#xff08;第8版&#xff09;》 出版信息&#xff1a; 原作名: Computer Networking: A Top-Down Approach 作者: [美] Jame…
阅读更多...
运维知识点-SQLServer/mssql

运维知识点-SQLServer/mssql

SQLServer/mssql Microsoft structed query language常见注入提权 技术点&#xff1a;0x00 打点前提 0x01 上线CS0x02 提权0x03 转场msf0x04 抓取Hash0x05 清理痕迹 Microsoft structed query language 常见注入 基于联合查询注入 order by 判断列数&#xff08;对应数据类型…
阅读更多...
idea无法创建jdk8的springboot修复方案

idea无法创建jdk8的springboot修复方案

https://start.aliyun.com/
阅读更多...
最新文章

Copyright @ 2022~2023