本文涉及的基础知识点
C++算法:前缀和、前缀乘积、前缀异或的原理、源码及测试用例 包括课程视频
动态规划
本题其它解法
类似题解法
题目
给你一个长度为 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
解释:
第一版
分析
1324模式,第1的小在最前面,其次是第3小,再次是第2小的,最后是第4小的。
变量解释
代码
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;
};
测试用例
第二版
三步是如此相似,也许可以合并。第一步的循环似乎不同。我们把第一步的第一层循环换到第二层就更相似了。修改后的第一步: