7-15 新浪微博热门话题
分数 30
作者 DS课程组
单位 浙江大学
新浪微博可以在发言中嵌入“话题”,即将发言中的话题文字写在一对“#”之间,就可以生成话题链接,点击链接可以看到有多少人在跟自己讨论相同或者相似的话题。新浪微博还会随时更新热门话题列表,并将最热门的话题放在醒目的位置推荐大家关注。
本题目要求实现一个简化的热门话题推荐功能,从大量英文(因为中文分词处理比较麻烦)微博中解析出话题,找出被最多条微博提到的话题。
输入格式:
输入说明:输入首先给出一个正整数N(≤10
5
),随后N行,每行给出一条英文微博,其长度不超过140个字符。任何包含在一对最近的#中的内容均被认为是一个话题,输入保证#成对出现。
输出格式:
第一行输出被最多条微博提到的话题,第二行输出其被提到的微博条数。如果这样的话题不唯一,则输出按字母序最小的话题,并在第三行输出And k more ...,其中k是另外几条热门话题的条数。输入保证至少存在一条话题。
注意:两条话题被认为是相同的,如果在去掉所有非英文字母和数字的符号、并忽略大小写区别后,它们是相同的字符串;同时它们有完全相同的分词。输出时除首字母大写外,只保留小写英文字母和数字,并用一个空格分隔原文中的单词。
输入样例:
4
This is a #test of topic#.
Another #Test of topic.#
This is a #Hot# #Hot# topic
Another #hot!# #Hot# topic
输出样例:
Hot
2
And 1 more ...
using namespace std;
int main()
{
int n;
map<string,int>m;
map<string,int>q;
vector<int>vec;
string s;
cin>>n;
getchar();
for(int i=0; i<n; i++)
{
m.clear();
getline(cin,s);
vec.clear();
for(int j=0; s[j]; j++)
{
if(s[j]=='#')vec.push_back(j);
}
while(vec.size())
{
int x=vec.front();
vec.erase(vec.begin());
int y=vec.front();
vec.erase(vec.begin());
string s1=s.substr(x+1,y-x-1);
string s2;
for(int j=0; j<s1.size(); j++)
{
if(s1[j]>='A'&&s1[j]<='Z')s1[j]=tolower(s1[j]);
else if((s1[j]>='a'&&s1[j]<='z')||(s1[j]>='0'&&s1[j]<='9'))s1[j]=s1[j];
else s1[j]=' ';
}
if(s1[0]==' ')for(int k=1; k<s1.size(); k++) s2.push_back(s1[k]);
else if(s1[(s1.size()-1)]==' ')for(int k=0; k<s1.size()-1; k++)s2.push_back(s1[k]);
else s2=s1;
s2[0]=toupper(s2[0]);
if(m[s2]==0)
{
q[s2]++;
m[s2]=1;
}
}
}
int cnt=0,tt=0;
string top;
map<string,int >::iterator it;
for(it=q.begin(); it!=q.end(); it++)
{
string ss=it->first;
int val=it->second;
if(val>tt)
{
tt=val;
cnt=0;
top=ss;
}
else if(val==tt)cnt++;
}
cout<<top<<endl<<tt<<endl;
if(cnt)
cout<<"And "<<cnt<<" more ..."<<endl;
return 0;
}
AI 代码解读