阿里笔试C++软件开发
选择题太坑，一路懵逼过来，很多JAVA题，编程题一道AC，第二道40%；
第一道代码： 中间变量有点多，为了解题速度，看看思路就行
#include<iostream>
#include<string>
#include<vector>
#include<set>
#include<algorithm>
using namespace std;
void mincut(const string& str, int start,const set<string>& dict,vector<string> output,vector<string> &result)
{
if(start == str.length())
{
if(result.empty() || (!output.empty()&& result.size()>output.size()))//收敛条件
{
result.clear();
result = output;
}
return;
}
for(int i=start;i<str.size();i++)
{
string tmp = str.substr(start,i-start+1);
if(find(dict.begin(),dict.end(),tmp) !=dict.end())
{
output.push_back(tmp);
mincut(str,i+1,dict,output,result); //深搜寻找
output.pop_back();
}
}
}
int main(int argc, const char * argv[])
{
string strS;
string dictStr;
int nDict;
set<string> dict;
cin>>strS;
cin>>nDict;
for (int i = 0; i < nDict; i++)
{
cin>>dictStr;
dict.insert(dictStr);
}
vector<string> output;
vector<string> result;
mincut(strS,0, dict,output,result);
if(!result.empty()) //输出结果
{
auto it=result.begin();
for(;it!=prev(result.end());it++)
cout<<*it<<" ";
cout<<*it<<endl;
}
else
cout<<"n/a"<<endl;
return 0;
}
华为成长空间 479人发布