阿里C++编程题，AC ，40%
第一道插入空格切割单词那个，其实就是叫你尽可能的切分最大的单词。
所以思路就是，
1.先求字典里最大单词的长度。
2.然后按照这个长度，从前面开始切割
3.切割后查字典，若不存在，则去掉最后一个字符。
4.继续查找，重复3 ~ 4步骤必定能找到最大的单次
5.若去掉完这个切割后的字符还没找到，那么就代表字典里面没有，直接跳出，输出n/a
代码如下：（没有优化，直接贴，有点乱）
void mincut(const string& str, const set<string>& dict)
{
vector<string> vec;
string src = str;
bool bS = true; //是否切割成功
int max_len = (*dict.begin()).size(); //求字典最大单词长度
for (auto it = dict.begin();it != dict.end();it++)
{
if ((*it).size() > max_len)
max_len = (*it).size();
}
while (!src.empty()) //切割字符串
{
int cur = 0;
string s = src.substr(0, max_len); //每次都切割这么长的串
bool bExits = dict.find(s) != dict.end() ? true : false; //查找
if (bExits) //如果正好切割到一个最大单词
{
vec.push_back(s);
}
else //否则去掉最后一个字符继续查
{
while (!s.empty() && bExits == false)
{
cur++;
s = src.substr(0, max_len - cur);
bExits = dict.find(s) != dict.end() ? true : false;
if (bExits)
{
vec.push_back(s);
}
}
}
if (s.empty())
{
bS = false;
break;
}
if (max_len - cur <= src.size())
src = src.substr(max_len - cur, src.size());
else
break;
}
if (bS)
{
for (int i = 0; i < vec.size(); i++)
{
cout << vec[i];
if (i != vec.size() - 1)
cout << ' ';
}
cout << endl;
}
else
cout << "n/a" << endl;
}
第二道题没时间仔细研究，大概看了下题目，不管37二十一，直接写了。
大概想法是，求的那个东西，好像结构体里面那个就是了。我是直接加起来，然后直接输出，就40%了。。。狗屎运。
代码：
double calculateExpectation(const vector<Point>& points, const int total, const int min)
{
typedef pair<int, double> PAIR;
map<int, PAIR> m;
for (int i = 0; i < points.size(); i++)
{
m[points[i].value] = make_pair(m[points[i].value].first + points[i].num, m[points[i].value].second + points[i].ratio);
}
double res = 0;
for (auto it = m.begin(); it != m.end(); it++)
{
if (it->second.second > res)
res = it->second.second;
}
return res;
}
欢迎讨论~
