C++前缀和算法:生成数组原理、源码及测试用例

简介: C++前缀和算法:生成数组原理、源码及测试用例

本文涉及的基础知识点

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

动态规划,日后完成。

题目

给定三个整数 n、m 和 k 。考虑使用下图描述的算法找出正整数数组中最大的元素。

请你构建一个具有以下属性的数组 arr :

arr 中包含确切的 n 个整数。

1 <= arr[i] <= m 其中 (0 <= i < n) 。

将上面提到的算法应用于 arr 之后,search_cost 的值等于 k 。

返回在满足上述条件的情况下构建数组 arr 的 方法数量 ,由于答案可能会很大,所以 必须 对 10^9 + 7 取余。

示例 1:

输入:n = 2, m = 3, k = 1

输出:6

解释:可能的数组分别为 [1, 1], [2, 1], [2, 2], [3, 1], [3, 2] [3, 3]

示例 2:

输入:n = 5, m = 2, k = 3

输出:0

解释:没有数组可以满足上述条件

示例 3:

输入:n = 9, m = 1, k = 1

输出:1

解释:唯一可能的数组是 [1, 1, 1, 1, 1, 1, 1, 1, 1]

提示:

1 <= n <= 50

1 <= m <= 100

0 <= k <= n

暴力解法

分析

时间复杂度O(nmk*m)。第一层循环,枚举res[i],时间复杂度O(n)。第二层第三层循环状态,最大值和search_cost的值。第四层循环,当前值。

核心代码

emplate
class C1097Int
{
public:
C1097Int(long long llData = 0) :m_iData(llData% MOD)
{
}
C1097Int operator+(const C1097Int& o)const
{
return C1097Int(((long long)m_iData + o.m_iData) % MOD);
}
C1097Int& operator+=(const C1097Int& o)
{
m_iData = ((long long)m_iData + o.m_iData) % MOD;
return this;
}
C1097Int& operator-=(const C1097Int& o)
{
m_iData = (m_iData + MOD - o.m_iData) % MOD;
return this;
}
C1097Int operator-(const C1097Int& o)
{
return C1097Int((m_iData + MOD - o.m_iData) % MOD);
}
C1097Int operator(const C1097Int& o)const
{
return((long long)m_iData * o.m_iData) % MOD;
}
C1097Int& operator=(const C1097Int& o)
{
m_iData = ((long long)m_iData * o.m_iData) % MOD;
return *this;
}
bool operator<(const C1097Int& o)const
{
return m_iData < o.m_iData;
}
C1097Int pow(long long n)const
{
C1097Int iRet = 1, iCur = *this;
while (n)
{
if (n & 1)
{
iRet *= iCur;
}
iCur *= iCur;
n >>= 1;
}
return iRet;
}
C1097Int PowNegative1()const
{
return pow(MOD - 2);
}
int ToInt()const
{
return m_iData;
}
private:
int m_iData = 0;;
};
template
int operator+(int iData, const C1097Int& int1097)
{
int iRet = int1097.operator+(C1097Int(iData)).ToInt();
return iRet;
}
template
int& operator+=(int& iData, const C1097Int& int1097)
{
iData = int1097.operator+(C1097Int(iData)).ToInt();
return iData;
}
template
int operator*(int iData, const C1097Int& int1097)
{
int iRet = int1097.operator*(C1097Int<>(iData)).ToInt();
return iRet;
}
template
int& operator*=(int& iData, const C1097Int& int1097)
{
iData = int1097.operator*(C1097Int<>(iData)).ToInt();
return iData;
}
class Solution {
public:
int numOfArrays(int n, int m, int k) {
vector<vector<C1097Int<>>> pre(k + 1, vector<C1097Int<>>(m+1));//pre[k][j]表示res[0,i)的 最大值为j且search_cost 为k的数量
pre[0][0] = 1;
for (int i = 0; i < n; i++)
{
vector<vector<C1097Int<>>> dp(k + 1, vector<C1097Int<>>(m + 1));
for (int preMax = 0; preMax <= m; preMax++)
{
for (int preK = 0; preK <= k; preK++)
{
for (int cur = 1; cur <= m; cur++)
{
const int iNewK = (cur <= preMax) ? preK : preK + 1;
if (iNewK > k)
{
continue;
}
dp[iNewK][max(cur, preMax)] += pre[preK][preMax];
}
}
}
pre.swap(dp);
}
auto bi = std::accumulate(pre[k].begin(), pre[k].end(), C1097Int<>());
return bi.ToInt();
}
};

测试用例

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()
{
int res = Solution().numOfArrays(2,3,1);
Assert(6, res);
res = Solution().numOfArrays(20, 30, 5);
Assert(266034711, res);
res = Solution().numOfArrays(30, 20, 4);
Assert(835697098, res);
//CConsole::Out(res);
}

前缀和优化

分析

dp[curK][curMax]的来源有两种 ,见下表

preMax < curMax k加1 pre[curK-1][0,curMax) 之和,前缀和。
preMax >= curMax k不变 cur取[1,curMax]都是pre[curK][curMax],故pre[curK][curMax]*curMax。

代码

class Solution {
public:
int numOfArrays(int n, int m, int k) {
vector<vector<C1097Int<>>> pre(k + 1, vector<C1097Int<>>(m+1));//pre[k][j]表示res[0,i)的 最大值为j且search_cost 为k的数量
pre[0][0] = 1;
for (int i = 0; i < n; i++)
{
vector<vector<C1097Int<>>> dp(k + 1, vector<C1097Int<>>(m + 1));
for (int curK = 1; curK <= k; curK++)
{
C1097Int<> bi = 0;
for (int curMax = 1; curMax <= m; curMax++)
{
//preMax < curMax
bi += pre[curK-1][curMax - 1];
dp[curK][curMax] = bi;
//
dp[curK][curMax] += pre[curK][curMax] * (curMax);
}
}
pre.swap(dp);
}
auto bi = std::accumulate(pre[k].begin(), pre[k].end(), C1097Int<>());
return bi.ToInt();
}
};

扩展阅读

视频课程

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


相关文章
|
16天前
|
存储 人工智能 算法
C 408—《数据结构》算法题基础篇—数组(通俗易懂)
408考研——《数据结构》算法题基础篇之数组。(408算法题的入门)
58 23
|
26天前
|
JavaScript NoSQL Java
基于SpringBoot+Vue实现的大学生体质测试管理系统设计与实现(系统源码+文档+数据库+部署)
面向大学生毕业选题、开题、任务书、程序设计开发、论文辅导提供一站式服务。主要服务:程序设计开发、代码修改、成品部署、支持定制、论文辅导,助力毕设!
38 2
|
1月前
|
机器学习/深度学习 算法 PyTorch
深度强化学习中SAC算法:数学原理、网络架构及其PyTorch实现
软演员-评论家算法(Soft Actor-Critic, SAC)是深度强化学习领域的重要进展,基于最大熵框架优化策略,在探索与利用之间实现动态平衡。SAC通过双Q网络设计和自适应温度参数,提升了训练稳定性和样本效率。本文详细解析了SAC的数学原理、网络架构及PyTorch实现,涵盖演员网络的动作采样与对数概率计算、评论家网络的Q值估计及其损失函数,并介绍了完整的SAC智能体实现流程。SAC在连续动作空间中表现出色,具有高样本效率和稳定的训练过程,适合实际应用场景。
216 7
深度强化学习中SAC算法:数学原理、网络架构及其PyTorch实现
|
2月前
|
算法 Java 数据库
理解CAS算法原理
CAS(Compare and Swap,比较并交换)是一种无锁算法,用于实现多线程环境下的原子操作。它通过比较内存中的值与预期值是否相同来决定是否进行更新。JDK 5引入了基于CAS的乐观锁机制,替代了传统的synchronized独占锁,提升了并发性能。然而,CAS存在ABA问题、循环时间长开销大和只能保证单个共享变量原子性等缺点。为解决这些问题,可以使用版本号机制、合并多个变量或引入pause指令优化CPU执行效率。CAS广泛应用于JDK的原子类中,如AtomicInteger.incrementAndGet(),利用底层Unsafe库实现高效的无锁自增操作。
理解CAS算法原理
|
2月前
|
存储 人工智能 缓存
【AI系统】布局转换原理与算法
数据布局转换技术通过优化内存中数据的排布,提升程序执行效率,特别是对于缓存性能的影响显著。本文介绍了数据在内存中的排布方式,包括内存对齐、大小端存储等概念,并详细探讨了张量数据在内存中的排布,如行优先与列优先排布,以及在深度学习中常见的NCHW与NHWC两种数据布局方式。这些布局方式的选择直接影响到程序的性能,尤其是在GPU和CPU上的表现。此外,还讨论了连续与非连续张量的概念及其对性能的影响。
99 3
|
3月前
|
机器学习/深度学习 人工智能 算法
探索人工智能中的强化学习:原理、算法及应用
探索人工智能中的强化学习:原理、算法及应用
|
3月前
|
机器学习/深度学习 人工智能 算法
探索人工智能中的强化学习:原理、算法与应用
探索人工智能中的强化学习:原理、算法与应用
|
3月前
|
存储 算法 网络协议
OSPF的SPF算法介绍:原理、实现与应用
OSPF的SPF算法介绍:原理、实现与应用
130 3
|
3月前
|
缓存 算法 网络协议
OSPF的路由计算算法:原理与应用
OSPF的路由计算算法:原理与应用
106 4
|
3月前
|
算法 容器
令牌桶算法原理及实现,图文详解
本文介绍令牌桶算法,一种常用的限流策略,通过恒定速率放入令牌,控制高并发场景下的流量,确保系统稳定运行。关注【mikechen的互联网架构】,10年+BAT架构经验倾囊相授。
令牌桶算法原理及实现,图文详解