7-15 新浪微博热门话题（30 分）

本文主要是介绍7-15 新浪微博热门话题（30 分），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目：

新浪微博可以在发言中嵌入“话题”，即将发言中的话题文字写在一对“#”之间，就可以生成话题链接，点击链接可以看到有多少人在跟自己讨论相同或者相似的话题。新浪微博还会随时更新热门话题列表，并将最热门的话题放在醒目的位置推荐大家关注。

本题目要求实现一个简化的热门话题推荐功能，从大量英文（因为中文分词处理比较麻烦）微博中解析出话题，找出被最多条微博提到的话题。

输入格式：

输入说明：输入首先给出一个正整数

第一行输出被最多条微博提到的话题，第二行输出其被提到的微博条数。如果这样的话题不唯一，则输出按字母序最小的话题，并在第三行输出 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 ...

思路：

首先处理两个‘#’之间的字符串，是字母，数字的保留，字母、数字之间的其他符号统统用一个空格代替。另外开头和结尾的空格去掉。之后判断就可以了。

感谢该博客提供了卡我一中午的样例：https://blog.csdn.net/henuni/article/details/75907043

样例输入：

4
This is a #test of 1 topic#.
Another #Test of (1)topic.#
This is a #Hot# topic
This is a test of 1 topic

样例输出：

Test of 1 topic
2

卡掉一中午的代码：（因为没有考虑最后一个字符为‘#’的情况）

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 2147493647;
const int maxn = 1e5+10;
typedef pair<string,int> pir;
vector<pir> v;
map<string,int> mp;string makeString(string str){string temp = "",res = "";for(int i = 0; i<str.length(); i++){if(i==0 && str[i]==' ')continue;if(i==str.length()-1 && str[i]==' ')continue;temp+=str[i];}return temp;
}void init() {int n;string str;v.push_back(pir("@",1000));cin>>n;getchar();for(int kk = 0; kk<n; kk++) {getline(cin,str);string tmp = "";set<string> s;set<string>::iterator it;for(int i = 0; i<str.length(); i++) {if(str[i]=='#') {i++;while(str[i]!='#' && i<str.length()) {if(isupper(str[i])) {tmp += tolower(str[i]);i++;} else if(islower(str[i])) {tmp += str[i];i++;}else if(str[i]>='0'&&str[i]<='9'){tmp += str[i];i++;}else if(str[i]==' ') {//aaa#aa@@@@bb#while(i+1<str.length() && str[i+1]==' ')i++;tmp += str[i];//str[i];i++;}elsei++;}if(i>=str.length())break;else if(str[i]=='#') {tmp = makeString(tmp);//cout<<tmp<<endl;if(tmp!="")s.insert(tmp);tmp = "";}}}for(it=s.begin(); it!=s.end(); it++) {if(mp[*it]==0) {v.push_back(pir(*it,1));mp[*it] = v.size()-1;} else {int in = mp[*it];v[in].second++;}}s.clear();}
}bool cmd(pir a, pir b){if(a.second == b.second)return a.first<b.first;return a.second > b.second;
}int main() {init();sort(v.begin()+1,v.end(),cmd);int index = 0;for(int i = 2; i<v.size(); i++){if(v[i].second == v[1].second)index++;}string ans = v[1].first;ans[0] = ans[0]-'a'+'A';cout<<ans<<endl;cout<<v[1].second<<endl;if(index>0)cout<<"And "<<index<<" more ..."<<endl;return 0;
}

View Code

完全通过的代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 2147493647;
const int maxn = 1e5+10;
typedef pair<string,int> pir;
vector<pir> v;
map<string,int> mp;string makeString(string str){string temp = "",res = "";for(int i = 0; i<str.length(); i++){if(i==0 && str[i]==' ')continue;if(i==str.length()-1 && str[i]==' ')continue;temp+=str[i];}return temp;
}bool judge(char ch){if(isupper(ch) || islower(ch) || (ch>='0'&&ch<='9') || ch=='#')return false;return true;
}void init() {int n;string str;v.push_back(pir("@",1000));cin>>n;getchar();for(int kk = 0; kk<n; kk++) {getline(cin,str);string tmp = "";set<string> s;set<string>::iterator it;for(int i = 0; i<str.length(); i++) {if(str[i]=='#') {i++;while(str[i]!='#' && i<str.length()) {if(isupper(str[i])) {tmp += tolower(str[i]);i++;} else if(islower(str[i])) {tmp += str[i];i++;}else if(str[i]>='0'&&str[i]<='9'){tmp += str[i];i++;}else {while(i+1<str.length() && judge(str[i+1]))i++;tmp += ' ';//str[i];i++;}}if(i>=str.length())break;else if(str[i]=='#') {tmp = makeString(tmp);//cout<<tmp<<endl;
                    s.insert(tmp);tmp = "";}}}for(it=s.begin(); it!=s.end(); it++) {if(mp[*it]==0) {v.push_back(pir(*it,1));mp[*it] = v.size()-1;} else {int in = mp[*it];v[in].second++;}}s.clear();}
}bool cmd(pir a, pir b){if(a.second == b.second)return a.first<b.first;return a.second > b.second;
}int main() {init();sort(v.begin()+1,v.end(),cmd);int index = 0;for(int i = 2; i<v.size(); i++){if(v[i].second == v[1].second)index++;}string ans = v[1].first;ans[0] = ans[0]-'a'+'A';cout<<ans<<endl;cout<<v[1].second<<endl;if(index>0)cout<<"And "<<index<<" more ..."<<endl;return 0;
}