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

这篇具有很好参考价值的文章主要介绍了【动态规划】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小的。

变量解释

v21 v21[i2][i1] = k,表示 nums[i2]和nums[x]组成12模式的数量是k,x取值范围[0,i1)
v32 v32[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

【动态规划】LeetCode2552:优化了6版的1324模式,# 算法题,c++,算法,前缀和,1324模式,4元组,合并循环,LeetCode文章来源地址https://www.toymoban.com/news/detail-752026.html

到了这里,关于【动态规划】LeetCode2552:优化了6版的1324模式的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 了解动态规划算法:原理、实现和优化指南

    动态规划(Dynamic Programming,简称 DP)是一种通过将原问题拆分成子问题并分别求解这些子问题来解决复杂问题的算法思想。 它通常用于求解优化问题,它的核心思想是将原问题分解成一系列的子问题,通过找到子问题之间的递推关系,可以避免重复计算,从而大幅提高计算

    2024年02月11日
    浏览(38)
  • 【算法|动态规划No.6】leetcode63. 不同路径Ⅱ

    个人主页:平行线也会相交 欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 平行线也会相交 原创 收录于专栏【手撕算法系列专栏】【LeetCode】 🍔本专栏旨在提高自己算法能力的同时,记录一下自己的学习过程,希望对大家有所帮助 🍓希望我们一起努力、成长,共同进步。

    2024年02月16日
    浏览(49)
  • 【算法|动态规划No.17】leetcode64. 最小路径和

    个人主页:兜里有颗棉花糖 欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 兜里有颗棉花糖 原创 收录于专栏【手撕算法系列专栏】【LeetCode】 🍔本专栏旨在提高自己算法能力的同时,记录一下自己的学习过程,希望对大家有所帮助 🍓希望我们一起努力、成长,共同进步。

    2024年02月07日
    浏览(49)
  • 【算法|动态规划系列No.5】leetcode62. 不同路径

    个人主页:平行线也会相交 欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 平行线也会相交 原创 收录于专栏【手撕算法系列专栏】【LeetCode】 🍔本专栏旨在提高自己算法能力的同时,记录一下自己的学习过程,希望对大家有所帮助 🍓希望我们一起努力、成长,共同进步。

    2024年02月12日
    浏览(43)
  • 【算法|动态规划No.12】leetcode152. 乘积最大子数组

    个人主页:兜里有颗棉花糖 欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 兜里有颗棉花糖 原创 收录于专栏【手撕算法系列专栏】【LeetCode】 🍔本专栏旨在提高自己算法能力的同时,记录一下自己的学习过程,希望对大家有所帮助 🍓希望我们一起努力、成长,共同进步。

    2024年02月08日
    浏览(45)
  • 【算法|动态规划No.7】leetcode300. 最长递增子序列

    个人主页:兜里有颗棉花糖 欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 兜里有颗棉花糖 原创 收录于专栏【手撕算法系列专栏】【LeetCode】 🍔本专栏旨在提高自己算法能力的同时,记录一下自己的学习过程,希望对大家有所帮助 🍓希望我们一起努力、成长,共同进步。

    2024年02月07日
    浏览(46)
  • 【算法|动态规划No.15】leetcode1035. 不相交的线

    个人主页:兜里有颗棉花糖 欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 兜里有颗棉花糖 原创 收录于专栏【手撕算法系列专栏】【LeetCode】 🍔本专栏旨在提高自己算法能力的同时,记录一下自己的学习过程,希望对大家有所帮助 🍓希望我们一起努力、成长,共同进步。

    2024年02月06日
    浏览(44)
  • LeetCode算法题解(动态规划)|LeetCoed62. 不同路径、LeetCode63. 不同路径 II

    题目链接:62. 不同路径 题目描述: 一个机器人位于一个  m x n   网格的左上角 (起始点在下图中标记为 “Start” )。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )。 问总共有多少条不同的路径? 示例 1: 示例 2:

    2024年02月05日
    浏览(53)
  • 【算法|动态规划No30】leetcode5. 最长回文子串

    个人主页:兜里有颗棉花糖 欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 兜里有颗棉花糖 原创 收录于专栏【手撕算法系列专栏】【LeetCode】 🍔本专栏旨在提高自己算法能力的同时,记录一下自己的学习过程,希望对大家有所帮助 🍓希望我们一起努力、成长,共同进步。

    2024年02月08日
    浏览(41)
  • 【手撕算法|动态规划系列No.4】leetcode91. 解码方法

    个人主页:平行线也会相交 欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 平行线也会相交 原创 收录于专栏【手撕算法系列专栏】【LeetCode】 🍔本专栏旨在提高自己算法能力的同时,记录一下自己的学习过程,希望对大家有所帮助 🍓希望我们一起努力、成长,共同进步。

    2024年02月12日
    浏览(41)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包