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

C++前缀和算法:生成数组原理、源码及测试用例,# 算法题,c++,算法,开发语言,动态规划,前缀和,测试用例,生成数组文章来源地址https://www.toymoban.com/news/detail-739108.html

到了这里,关于C++前缀和算法:生成数组原理、源码及测试用例的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 【算法】激光炸弹(二维数组前缀和)

    地图上有 N 个目标,用整数 Xi,Yi 表示目标在地图上的位置,每个目标都有一个价值 Wi。 注意 :不同目标可能在同一位置。 现在有一种新型的激光炸弹,可以摧毁一个包含 R×R 个位置的正方形内的所有目标。 激光炸弹的投放是通过卫星定位的,但其有一个缺点,就是其爆

    2024年01月25日
    浏览(40)
  • [Daimayuan] 三段式(C++,数组前缀和)

    有一个长度为 n n n 的序列,现在我们想把它切割成三段(每一段都是连续的),使得每一段的元素总和都相同,请问有多少种不同的切割方法 输入描述 第一行给出一个数 n n n ,( 1 ≤ n ≤ 1 0 5 1≤n≤10^5 1 ≤ n ≤ 1 0 5 ) 第二行给出序列 a 1 a_1 a 1 ​ , a 2 a_2 a 2 ​ , a 3 a_3 a 3 ​

    2024年02月05日
    浏览(34)
  • 自动生成测试用例_接口测试用例自动生成工具

    写用例之前,我们应该熟悉API的详细信息。建议使用抓包工具Charles或AnyProxy进行抓包。 我们先来了解一下另一个项目har2case 他的工作原理就是将当前主流的抓包工具和浏览器都支持将抓取得到的数据包导出为标准通用的 HAR 格式(HTTP Archive),然后 HttpRunner 将 HAR 格式的数据

    2024年02月05日
    浏览(61)
  • 【easytestapi,文档即测试,自动生成测试用例】

    个人编写的一个开源测试工具,GitHub - easytestapi/easytestapi: 生产力!!! 目前主要用户接口功能自动化测试,其核心思想是文档即测试。 文档是接口文档。通过我定义的标准化的接口文档,可生成测试用例,也可直接执行测试。 目前没有可视化,独立一人编写。希望有兴趣的

    2023年04月08日
    浏览(50)
  • 模型生成自动化测试用例

    自动产生的测试用例本就应该由程序自动执行,这其实也就是NModel推荐的模式。先回过头来看看文章中制作的模型,模型里面将登录、注销、用户名以及密码等要素都抽象出来了,而NModel是以这些抽象出来的动作(登录、注销)和状态(用户名、密码)为依据,产生测试用例

    2024年02月09日
    浏览(49)
  • LeetCode算法心得——和可被 K 整除的子数组(前缀和+HashMap)

    大家好,我是晴天学长,同余定理的应用,需要的小伙伴可以关注支持一下哦!后续会继续更新的。 1) .和可被 K 整除的子数组 题目描述 给定一个整数数组 A,返回其中元素之和可被 K 整除的(连续、非空)子数组的数目。 示例: 输入:A = [4,5,0,-2,-3,1], K = 5 输出:7 解释:

    2024年02月07日
    浏览(40)
  • Python实现自动生成测试用例

    目录 1、概要... 3 2、正交表法简介... 3 2.1、什么是正交表法... 3 2.2、正交表法优点... 3 2.3、正交表法的缺点... 4 2.4、为什么选择正交表法... 4 3、Python实现... 4 3.1、实现自动化排列组合... 4 3.2、解决元素互斥... 5 3.3、解决流程终止... 6 4、case_generate工具使用方法... 6 4.1、使用流

    2024年02月05日
    浏览(64)
  • idea生成springboot单元测试用例

    1、找到需要生成单元测试的类型,右键Go To - Test  2、选择JUnit4 和勾选需要测试的方法  3、查看自动生成的文件 4、添加测试代码 注意:@RunWith(SpringRunner.class)            @SpringBootTest 这两行让项目跑起来后运行测试用例,必须加上 方法二:通过继承applicationTest,

    2024年02月13日
    浏览(34)
  • 算法——前缀和之除自身以外数组的乘积、和为K的子数组、和可被K整除的子数组、连续数组、矩阵区域和

    这几道题对于我们前面讲过的一维、二维前缀和进行了运用,包含了面对特殊情况的反操作 目录 4.除自身以外数组的乘积 4.1解析 4.2题解 5.和为K的子数组 5.1解析 5.2题解 6.和可被K整除的子数组 6.1解析 6.2题解 7.连续数组 7.1题解 7.2题解 8.矩阵区域和 8.1解析 8.2题解 4.除自身以外

    2024年04月14日
    浏览(43)
  • 使用testMe自动生成单元测试用例

    公司对于系统单元测试覆盖率有要求,需要达到50%或80%以上才可以,但是对于之前的老项目或者是前期赶进度未添加单元测试用例的项目来说,手动添加单元测试耗时又费力,这时候我们就需要一款能够提高效率的一款插件来帮助我们提高单元测试覆盖率,经过对比temstMe、

    2024年02月07日
    浏览(62)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包