C++前缀和算法的应用：从栈中取出 K 个硬币的最大面值和原理源码测试用例

本文涉及的基础知识点

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

题目

一张桌子上总共有 n 个硬币栈。每个栈有正整数个带面值的硬币。
每一次操作中，你可以从任意一个栈的顶部取出 1 个硬币，从栈中移除它，并放入你的钱包里。
给你一个列表 piles ，其中 piles[i] 是一个整数数组，分别表示第 i 个栈里从顶到底的硬币面值。同时给你一个正整数 k ，请你返回在恰好进行 k 次操作的前提下，你钱包里硬币面值之和最大为多少。
示例 1：
输入：piles = [[1,100,3],[7,8,9]], k = 2
输出：101
解释：
上图展示了几种选择 k 个硬币的不同方法。
我们可以得到的最大面值为 101 。
示例 2：
输入：piles = [[100],[100],[100],[100],[100],[100],[1,1,1,1,1,1,700]], k = 7
输出：706
解释：
如果我们所有硬币都从最后一个栈中取，可以得到最大面值和。
**参数范围##
n == piles.length
1 1 1

分析

时间复杂度

三层循环，第一层循环，枚举各栈；第二层循环，枚举已经取走的硬币数；第三层循环，枚举本栈取走的硬币。令m=sum(piles[i].length)，第一层和第三层循环的总复杂度是O(m)。第二次循环的复杂度是O(k)，故复杂度为O(km)。

变量解释


pre	pre[i]的值是选取i枚硬币的最大值
i	之前的栈总共选取了i枚硬币
j	本次选取了j枚硬币

代码

核心代码

class Solution {
public:
int maxValueOfCoins(vector& piles, int k) {
vector pre = { 0 };//pre[i]的值是选取i枚硬币的最大值
for (const auto& v : piles )
{
const int iNum = min((int)v.size() + (int)pre.size(),k+1);
vector dp(iNum);
for (int i = 0; i {
//当前栈选取j枚硬币
int iSum = 0;
for (int j = 0; j {
const int iNewNum = i + j;
if (iNewNum > k)
{
continue;
}
dp[iNewNum] = max(dp[iNewNum], pre[i]+iSum);
if (j {
iSum += v[j];
}
}
}
pre.swap(dp);
}
return pre.back();
}
};

测试用例

template
void Assert(const vector& v1, const vector& v2)
{
if (v1.size() != v2.size())
{
assert(false);
ret服务器托管网urn;
}
for (int i = 0; i {
assert(v1[i] == v2[i]);
}
}

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

int main()
{
Solution slu;
vector piles;
int k = 0;
int res;

piles = { {1,100,3},{7,8,9} };
k = 2;
res = slu.maxValueOfCoins(piles, k);
Assert(101, res);

piles = { {100},{100},{100},{100},{100},{100},{1,1,1,1,1,1,700} };
k = 7;
res = slu.maxValueOfCoins(piles, k);
Assert(101, res);
	

//CConsole::Out(res);

}

2023年2月旧服务器托管网代码

class Solution {
public:
int maxValueOfCoins(vector& piles, int k) {
vector pre(1);
for (const auto& v : piles)
{
const int iSize = min(k + 1,int( pre.size()+ v.size()));
vector dp = pre;
dp.resize(iSize);
int iTotal = 0;
for (int i = 0; i {
iTotal += v[i];
for (int j = 0; j {
const int iNewIndex = j + i + 1;
if (iNewIndex > k)
{
break;
}
dp[iNewIndex] = max(dp[iNewIndex], pre[j] + iTotal);
}
}
pre.swap(dp);
}
return pre[k];
}

};

扩展阅读

视频课程

有效学习：明确的目标及时的反馈拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快

速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者操作系统：win10 开发环境：

VS2022 C++17

服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net

相关推荐: 【RocketMQ】DLedger模式下的选主流程分析

RocketMQ 4.5版本之前，可以采用主从架构进行集群部署，但是如果master节点挂掉，不能自动在集群中选举出新的Master节点，需要人工介入，在4.5版本之后提供了DLedger模式，使用Raft算法，如果Master节点出现故障，可以自动选举出新的…