小米软件开发 0.86+1.0，第一题最后还是超时
第一题，小米之家购物，属于完全最小找零问题，贴上超时代码：
#include <iostream>
#include <vector>
#include <numeric>
#include <limits>
#include <limits.h>
#include <algorithm>
using namespace std;
/*请完成下面这个函数，实现题目要求的功能
当然，你也可以不按照下面这个模板来作答，完全按照自己的想法来 ^-^
******************************开始写代码******************************/
void dfs(vector<int>::iterator coin, vector<int>::iterator end, int count, int amount, int& res)
{
if (amount == 0)
{
res = min(res, count);
return;
}
if (coin == end) { return; }
int max = amount / *coin;
while (max >= 0 && count + max < res)
{
dfs(coin + 1, end, count + max, amount - max * (*coin), res);
max--;
}
}
int solution(vector<int>& coins, int amount)
{
vector<int>::iterator it = coins.begin();
for (; it != coins.end();) {
if (*it == 0)
it = coins.erase(it);
else
++it;
}
if (coins.size() == 0) {
return -1;
}
if (amount <= 0)
return -1;
sort(coins.rbegin(), coins.rend());
int res = INT_MAX;
dfs(coins.begin(), coins.end(), 0, amount, res);
return res == INT_MAX? -1 : res;
}
/******************************结束写代码******************************/
int main() {
int res;
int _prices_size = 0;
cin >> _prices_size;
cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');
vector< int> _prices;
int _prices_item;
for ( int _prices_i = 0; _prices_i < _prices_size; _prices_i++) {
cin >> _prices_item;
cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');
_prices.push_back(_prices_item);
}
int _budget;
cin >> _budget;
cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');
res = solution(_prices, _budget);
cout << res << endl;
return 0;
} 第二题，打印二叉树：
#include <iostream>
#include <vector>
#include <numeric>
#include <limits>
#include <stack>
using namespace std;
typedef struct node{
int data;
struct node *lchild;
struct node *rchild;
}BTNode;
void Postorder(BTNode *root,string &str)
{
if(root==NULL)
return;
Postorder(root->lchild,str);
str+=root->data;
Postorder(root->rchild,str);
}
void create2(BTNode *&root,char *str){
root=NULL;
BTNode *p;
int i=0,k=0;
stack<BTNode*> s;
char ch=str[i];
while(ch!='\0'){
switch(ch){
case '(':{
s.push(p);
k=1;
break;
}
case ',':{
k=2;
break;
}
case ')':{
s.pop();
break;
}
default:{
p=(BTNode*)malloc(sizeof(BTNode));
p->lchild=p->rchild=NULL;
p->data=ch;
if(root==NULL)
root=p;
else{
if(k==1){
s.top()->lchild=p;
}else if(k==2)
s.top()->rchild=p;
}
break;
}
}
ch=str[++i];
}
}
/*请完成下面这个函数，实现题目要求的功能
当然，你也可以不按照下面这个模板来作答，完全按照自己的想法来 ^-^
******************************开始写代码******************************/
string solution(string input) {
BTNode *root;
string str="";
create2(root, const_cast<char*>(input.data()));
Postorder(root,str);
return str;
}
/******************************结束写代码******************************/
int main() {
string res;
string _input;
getline(cin, _input);
res = solution(_input);
cout << res << endl;
return 0;
} 