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

这篇具有很好参考价值的文章主要介绍了C++前缀和算法的应用:统计上升四元组。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

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

本文涉及的基础知识点

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
解释:

  • 当 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 是一个排列。

容易理解

分析

第一层循环,枚举j,第二层循环枚举k。时间复杂度O(n*n)。在通过不通过之间,用vector<vector>就通过不了,用int**勉强可以通过。分两步:

第一步 求前缀和
第二步 枚举j和k

核心代码

class Solution {
public:
long long countQuadruplets(vector& nums) {
m_c = nums.size();
int** vSum = new int*[m_c + 1];//vSum[i][j]:nums[0,j)中小于等于i的个数
for (int i = 1; i <= m_c; i++)
{//计算小于i的个数
vSum[i] = new int[m_c+1];
vSum[i][0] = 0;
for (int j = 0 ; j < m_c; j++ )
{
vSum[i][j+1] = vSum[i][j] + (nums[j] <= i);
}
}
long long llRet = 0;
for (int j = 1; j < m_c; j++)
{
for (int k = j + 1; k+1 < m_c; k++)
{
if (nums[j] < nums[k])
{
continue;
}
//nums[i]范围:nums[0,j)中小于等于nums[k]的数量
const long long lessNumK = vSum[nums[k]][j];
//nums[k+1,m_c)中大于nums[j]
const long long moreNumJ = m_c - (k + 1) - (vSum[nums[j]][m_c]- vSum[nums[j]][k+1]);
llRet += lessNumK * moreNumJ;
}
}
return llRet;
}
int m_c;
};

测试用例

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]);
}
}

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

int main()
{
Solution slu;
vector 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);
}

性能稍强

分析

第一层循环,枚举l或k;第二层循环,枚举j。时间复杂度O(n*n),代码简洁得多,可以轻松通过。

变量解释

llRet 所有符合条件的四元祖
iLessLK nums[0,j)中小于nums[i]的数量
m_v132[j] nums[0,i)中符合i,j,k的数量

核心代码

class Solution {
public:
	long long countQuadruplets(vector<int>& nums) {
		m_c = nums.size();
		long long llRet = 0;
		vector<long long> m_v132(m_c);//132
		for (int lk = 0; lk < m_c; lk++)
		{
			int iLessLK = 0;
			for (int j = 0; j < lk; j++)
			{
				if (nums[j] < nums[lk])
				{
					iLessLK++;
					llRet += m_v132[j];
				}
				else
				{
					//iLessLK 表示[0,j)中小于nums[lk]的数,假定其索引为i,则nums[i] < nums[lk] ,nums[j] < nums[lk],故i j lk,符合前三个数i,j,k
					m_v132[j] += iLessLK;
				}
			}
		}
		return llRet;
	}
	int m_c;
};

2月旧代码

class Solution {
public:
long long countQuadruplets(vector& nums) {
m_c = nums.size();
//vLeft[i][m] 表示nums[i]及之前的元素,小于等于m+1的个数
int vLeft[4000][4000] = { 0 };
{
for (int i = 0; i < m_c; i++)
{
if (i > 0)
{
memcpy(vLeft[i], vLeft[i - 1], sizeof(vLeft[0]));
}
for (int j = nums[i] - 1; j < m_c; j++)
{
vLeft[i][j] ++;
}
}
}
long long llRet = 0;
for (int j = 1; j + 1 < m_c; j++)
{
for (int k = j + 1; k + 1 < m_c; k++)
{
if (nums[j] <= nums[k])
{
continue;
}
const int iLeft = vLeft[j - 1][nums[k] - 1];
const int iRight = nums[j] - vLeft[k][nums[j] - 1];
llRet += vLeft[j - 1][nums[k] - 1] * (nums.size() - k - 1 - iRight);
}
}
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

C++前缀和算法的应用:统计上升四元组,数据结构与算法,# 算法题,算法,c++,数据结构,前缀和,四元组,力扣,leetcode文章来源地址https://www.toymoban.com/news/detail-739206.html

到了这里,关于C++前缀和算法的应用:统计上升四元组的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • C++前缀和算法的应用:石头游戏 VIII 原理源码测试用例

    C++算法:前缀和、前缀乘积、前缀异或的原理、源码及测试用例 包括课程视频 Alice 和 Bob 玩一个游戏,两人轮流操作, Alice 先手 。 总共有 n 个石子排成一行。轮到某个玩家的回合时,如果石子的数目 大于 1 ,他将执行以下操作: 选择一个整数 x 1 ,并且 移除 最左边的 x

    2024年02月08日
    浏览(39)
  • 大厂面试题-网络四元组

    四元组,简单理解就是在TCP协议中,去确定一个客户端连接的组成要素,它包括源 IP 地 址、目标IP地址、源端口号、目标端口号。 正常情况下 ,我们对于网络通信的认识可能是这样(如图)。 服务端通过Server   Sock e t 建立一个对指定端口号的监听,比如8080。客户端通过目 标

    2024年02月06日
    浏览(36)
  • C++前缀和算法的应用:DI序列的有效排列的原理、源码及测试用例

    C++算法:前缀和、前缀乘积、前缀异或的原理、源码及测试用例 包括课程视频 给定一个长度为 n 的字符串 s ,其中 s[i] 是: “D” 意味着减少,或者 “I” 意味着增加 有效排列 是对有 n + 1 个在 [0, n] 范围内的整数的一个排列 perm ,使得对所有的 i: 如果 s[i] == ‘D’,那么

    2024年02月08日
    浏览(55)
  • 【每日算法 && 数据结构(C++)】—— 01 | 平方值去重统计(解题思路STL法,双指针法、流程图、代码片段)

    “Success is not final, failure is not fatal: It is the courage to continue that counts.” - Winston Churchill (成功并非终点,失败并非致命:真正重要的是继续前行的勇气 - 温斯顿·丘吉尔) 给你一个整数数组,数组中的数可以是正数、负数、零,请实现一个函数,返回这个数组中所有数的平方

    2024年02月12日
    浏览(51)
  • 蓝桥杯统计子矩阵前缀和C++(附图文超详细讲解)(保姆级)

    给定一个 N × M 的矩阵 A,请你统计有多少个子矩阵 (最小 1 × 1,最大 N × M) 满足子矩阵中所有数的和不超过给定的整数 K?  第一行包含三个整数 N, M 和 K.  之后 N 行每行包含 M 个整数,代表矩阵 A. 一个整数代表答案。 满足条件的子矩阵一共有 19,包含: 大小为 1 × 1 的有

    2023年04月08日
    浏览(36)
  • 【数据结构与算法】前缀和+哈希表算法

    关于前缀和和哈希这两个概念大家都不陌生,在之前的文章中也有过介绍:前缀和与差分算法详解 而哈希表最经典的一题莫过于 两数之和 题目链接 题目描述: 给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target 的那 两个 整数,并返回它

    2024年02月01日
    浏览(110)
  • 《数据结构、算法与应用C++语言描述》-列车车厢重排问题

    完整可编译运行代码见:Github::Data-Structures-Algorithms-and-Applications/_10Train_carriages_rearrangement/ 一列货运列车有 n 节车厢,每节车厢要停靠在不同的车站。假设 n个车站从 1 到n 编号,而且货运列车按照从n到1的顺序经过车站。车厢的编号与它们要停靠的车站编号相同。为了便于从

    2024年04月10日
    浏览(61)
  • 【尚硅谷】数据结构和算法——前缀、中缀、后缀表达式规则

    跟着B站的尚硅谷学习数据结构与算法,语言为java,目前是第七个代码内容——前缀、中缀、后缀表达式 课程传送门:尚硅谷——前缀、中缀、后缀表达式 1)前缀表达式又称波兰式, 前缀表达式 的运算符位于操作符之前。 2)举例说明:(3+4)*5-6 对应的前缀表达式就是 - *

    2024年02月03日
    浏览(56)
  • 【数据结构与算法】【12】前缀表达式、中缀表达式、后缀表达式

    什么是前缀表达式、中缀表达式、后缀表达式 前缀表达式、中缀表达式、后缀表达式,是通过树来存储和计算表达式的三种不同方式 以如下公式为例 ( a + ( b − c ) ) ∗ d ( a+(b-c) )*d ( a + ( b − c ) ) ∗ d 通过树来存储该公式,可以表示为 那么问题就来了,树只是一种抽象的数据

    2024年02月08日
    浏览(44)
  • C++数据结构与算法详解:链表、栈、队列、树、二叉树和图结构的实现与应用

    链表是一种常见的数据结构由一系列节点按顺序连接而成,一般每个节点包含一个数据元素和一个指向下一个节点的引用。 链表有多种类型: 单向链表:每个节点只有一个指向下一个节点的引用 双向链表:每个节点有一个指向前一个节点和一个指向后一个节点的引用 循环链

    2024年02月04日
    浏览(47)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包