趋势科技C++ 2020年第二题
趋势科技C++笔试题记录。
第二题：给定硬币面值数组［1，5，10，20，50，100］以及每个硬币的数量(有限)，求能组成一个指定值m的所有组合，输出各种组合长度之和。
样例输入：
6 5 4 3 2 1
11
输出：
12
解析：[1,1,1,1,1,1,5] [1 5 5] [1 10],长度分别为7 3 2，则输出12
#include<bits/stdc++.h>
using namespace std;
vector<int> split(string str, string pattern) {
string::size_type pos;
vector<int> result;
str += pattern;//扩展字符串以方便操作
int size = str.size();
for (int i = 0; i<size; i++)
{
pos = str.find(pattern, i);//从位置i开始，返回第一个pattern子串索引
if (pos<size)
{
string s = str.substr(i, pos - i);
result.push_back(stoi(s));
i = pos + pattern.size() - 1;
}
}
return result;
}</int></int>
/* 寻找所有种类的组合 */
void find_seq(vector<int> value, set<list<int>> &myset, list<int> seq, int sum, int index)
{
if (sum <= 0 || index < 0)
return;
if (sum == value[index])
{
seq.reverse();
seq.push_back(value[index]);
myset.insert(seq);
seq.pop_back();
seq.reverse();
}
seq.push_back(value[index]); // 放入
find_seq(value, myset, seq, sum - value[index], index - 1);
seq.pop_back();
find_seq(value, myset, seq, sum, index - 1); // 不放入
}</int></int></int>
int process(std::string strTargetNum, std::string strValueSequences) {
//insert your code here:
int targetNum = std::stoi(strTargetNum);
vector<int> vec = split(strValueSequences, " ");
vector<int> mseq;
multimap<int, int> M;
M.insert(make_pair(1, vec[0]));
M.insert(make_pair(5, vec[1]));
M.insert(make_pair(10, vec[2]));
M.insert(make_pair(20, vec[3]));
M.insert(make_pair(50, vec[4]));
M.insert(make_pair(100, vec[5]));
for (auto it = M.begin(); it != M.end(); ++it) {
for (int i = 0; i < it->second; ++i) {
mseq.push_back(it->first);
}
}
list<int> temp;
set<list<int>> myset;
find_seq(mseq, myset, temp, targetNum, mseq.size() - 1);
int cout = 0;
for (auto it = myset.begin(); it != myset.end(); ++it) {
cout += it->size();
}
return cout;
}</int></int></int></int>
int main(int argc, const char * argv[]) {
std::string strValueSequences;
//std::cin >> strValueSequences;
//std::getline(std::cin, strValueSequences);
std::string strChargeNum;
std::cin >> strChargeNum;
//process
int lenSum = process(strChargeNum, strValueSequences);
std::cout << lenSum << std::endl;
return 0;
}
