问题 A: 变位词
时间限制: 2 Sec 内存限制: 10 MB
提交: 322 解决: 59
提交 状态 算法问答
题目描述
请大家在做oj题之前，仔细阅读关于抄袭的说明http://www.bigoh.net/JudgeOnline/.
变位词是指由相同的字母组成的单词，如eat、tea是变位词。本次问题给出一串单词，你需要找到所有的变位词。
输入
输入由两行组成：第一行是所有单词的总数，第二行是由空格分隔的单词列表。两行末尾都有空格。
注：为防歧义，输入的单词都是小写
输出
这次需要大家先输出一个字符串，它是“我已阅读关于抄袭的说明”的汉语拼音.输出此行的提交我们将认为已经完全阅读并了解了“关于抄袭的说明”公告.
第二行是变位词组的个数，后面是所有的变位词。每个输出的变位词占一行。一组变位词只需要输出一个字典序最小的代表即可，如eat、tea中eat字典序小于tea，所以输出eat。变位词与变位词也按照字典序从小到大排列，如eat和el中eat字典序小于el所以eat在el前面。
输出的每一行最后都没有空格。
样例输入9 | 样例输出wo yi yue du guan yu chao xi de shuo ming |
提示
使用代价为O(nlgn)的方法。
代码
复杂度要达到nlogn，读入输入字符串是n复杂度，就是说插入部分为logn的复杂度，肯定就是使用树结构，c++中map使用平衡二叉树实现，可以直接使用。
int main()
{
int len = ;
cin >> len;
/*
第一个string代表sort(temp.begin(), temp.end())，这是为了把变位词聚集在一起
第二个string代表一个变位词集合中最小的元素
第三个int代表出现次数
*/
map<string, pair<string,int>> m;
int result = ;
string temp;
for (int i = ; i < len; i++) {
cin >> temp;
string orgin = temp;
sort(temp.begin(), temp.end());
m[temp].second++;
if (m[temp].second == )
m[temp].first = orgin;
else if (m[temp].second >= ) {
if (orgin < m[temp].first)
m[temp].first = orgin;
if(m[temp].second == )
result++;
}
} cout << "wo yi yue du guan yu chao xi de shuo ming" << endl;
cout << result << endl;
vector<string> v;
v.reserve(result);
for (auto k = m.begin(); k!=m.end() ; k++) {
if ((*k).second.second >= )
v.emplace_back((*k).second.first);
}
//m是使用string内部字符排序后的值作为索引，还要排个序
sort(v.begin(), v.end());
for (auto q = v.begin(); q != v.end(); q++)
cout << *q << endl; return ;
}
问题 B: 三数之和
时间限制: 1 Sec 内存限制: 2 MB
提交: 113 解决: 56
提交 状态 算法问答
题目描述
一个没有重复元素的整数数组，给定某个整数，找到所有triple之和等于该整数的个数，其中triple是数组中的不同的3个数。
输入
数组长度，以及要求的三数之和；
没有重复元素的数组。
输出
已阅读抄袭的说明；
所有triple的个数。
样例输入6 3 | 样例输出wo yi yue du guan yu chao xi de shuo ming |
提示
代码
题目没有重复元素，简便了一些，先排序，然后确定一个元素的位置，剩下两个元素采用两边逼近的方式来求。可以见Leetcode15，3 sum问题，比这个稍微复杂一点，思路完全相同
int main()
{
int len = ;
int sum = ;
cin >> len;
cin >> sum;
vector<int> v;
v.reserve(len);
int temp;
for (int i = ; i < len; i++) {
cin >> temp;
v.emplace_back(temp);
}
sort(v.begin(), v.end());
int times = ;
for (int i = ; i < len - ; i++) {
int pos2 = i + ;
int pos3 = len - ;
while (pos2 < pos3) {
if (v[i] + v[pos2] + v[pos3] < sum) {
pos2++;
}else if(v[i] + v[pos2] + v[pos3] > sum){
pos3--;
}else {
times++;
pos2++;
}
}
}
cout << "wo yi yue du guan yu chao xi de shuo ming" << endl;
cout << times << endl; return ;
}