C++前缀和算法的应用：优化了6版的1324模式

2023-11-30 08:04
文章标签 算法 c++ 模式 应用 优化 前缀 1324

本文主要是介绍C++前缀和算法的应用：优化了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

这篇关于C++前缀和算法的应用：优化了6版的1324模式的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/436258。

相关文章

Vue3 的 shallowRef 和 shallowReactive：优化性能

Vue3 的 shallowRef 和 shallowReactive：优化性能

大家对 Vue3 的 ref 和 reactive 都很熟悉，那么对 shallowRef 和 shallowReactive 是否了解呢？ 在编程和数据结构中，“shallow”（浅层）通常指对数据结构的最外层进行操作，而不递归地处理其内部或嵌套的数据。这种处理方式关注的是数据结构的第一层属性或元素，而忽略更深层次的嵌套内容。 1. 浅层与深层的对比 1.1 浅层（Shallow） 定义
阅读更多...
不懂推荐算法也能设计推荐系统

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例，告诉我们不懂推荐算法的产品，也能从产品侧出发， 设计出一款不错的推荐系统。 相信很多新手产品，看到算法二字，多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法（注：传统是指科班出身的产品都会接触过）。但对于推荐算法，多数产品对着网上搜到的资源，都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后，更是加大了理解的难度。 但，不了解推荐算法，就无法做推荐系
阅读更多...
中文分词jieba库的使用与实景应用（一）

中文分词jieba库的使用与实景应用（一）

知识星球：https://articles.zsxq.com/id_fxvgc803qmr2.html 目录 一.定义： 精确模式（默认模式）： 全模式： 搜索引擎模式： paddle 模式（基于深度学习的分词模式）： 二 自定义词典 三.文本解析   调整词出现的频率 四. 关键词提取 A. 基于TF-IDF算法的关键词提取 B. 基于TextRank算法的关键词提取
阅读更多...
水位雨量在线监测系统概述及应用介绍

水位雨量在线监测系统概述及应用介绍

在当今社会，随着科技的飞速发展，各种智能监测系统已成为保障公共安全、促进资源管理和环境保护的重要工具。其中，水位雨量在线监测系统作为自然灾害预警、水资源管理及水利工程运行的关键技术，其重要性不言而喻。 一、水位雨量在线监测系统的基本原理 水位雨量在线监测系统主要由数据采集单元、数据传输网络、数据处理中心及用户终端四大部分构成，形成了一个完整的闭环系统。 数据采集单元：这是系统的“眼睛”，
阅读更多...
HDFS—存储优化（纠删码）

HDFS—存储优化（纠删码）

纠删码原理 HDFS 默认情况下，一个文件有3个副本，这样提高了数据的可靠性，但也带来了2倍的冗余开销。 Hadoop3.x 引入了纠删码，采用计算的方式，可以节省约50％左右的存储空间。 此种方式节约了空间，但是会增加 cpu 的计算。 纠删码策略是给具体一个路径设置。所有往此路径下存储的文件，都会执行此策略。 默认只开启对 RS-6-3-1024k
阅读更多...
康拓展开（hash算法中会用到）

康拓展开（hash算法中会用到）

康拓展开是一个全排列到一个自然数的双射（也就是某个全排列与某个自然数一一对应） 公式： X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。（a[i]在不同应用中的含义不同）； 典型应用： 计算当前排列在所有由小到大全排列中的顺序，也就是说求当前排列是第
阅读更多...
【C++ Primer Plus习题】13.4

【C++ Primer Plus习题】13.4

大家好,这里是国中之林! ❥前些天发现了一个巨牛的人工智能学习网站，通俗易懂，风趣幽默，忍不住分享一下给大家。点击跳转到网站。有兴趣的可以点点进去看看← 问题: 解答: main.cpp #include <iostream>#include "port.h"int main() {Port p1;Port p2("Abc", "Bcc", 30);std::cout <<
阅读更多...
使用opencv优化图片（画面变清晰）

使用opencv优化图片（画面变清晰）

文章目录 需求影响照片清晰度的因素 实现降噪测试代码 锐化空间锐化Unsharp Masking频率域锐化对比测试 对比度增强常用算法对比测试 需求 对图像进行优化，使其看起来更清晰，同时保持尺寸不变，通常涉及到图像处理技术如锐化、降噪、对比度增强等 影响照片清晰度的因素 影响照片清晰度的因素有很多，主要可以从以下几个方面来分析 1. 拍摄设备 相机传感器：相机传
阅读更多...
csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

这是一道扩展欧几里得算法的简单应用题，这题是在湖南多校训练赛中队友ac的一道题，在比赛之后请教了队友，然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意：把题意转变下就变成了：求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点：求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个
阅读更多...
C++包装器

C++包装器

包装器 在 C++ 中，“包装器”通常指的是一种设计模式或编程技巧，用于封装其他代码或对象，使其更易于使用、管理或扩展。包装器的概念在编程中非常普遍，可以用于函数、类、库等多个方面。下面是几个常见的 “包装器” 类型： 1. 函数包装器 函数包装器用于封装一个或多个函数，使其接口更统一或更便于调用。例如，std::function 是一个通用的函数包装器，它可以存储任意可调用对象（函数、函数
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2