4.电话号码

• 【问题描述】
• 【输入形式】
• 【输出形式】
• 【样例输入】
• 【样例输出】
• 题解
• • 思路
  • 代码

【问题描述】

Vasya有几本电话簿，记录了他的朋友们的电话号码，每一个朋友都可以有一或几个电话号码。

Vasya决定整理关于朋友电话号码的信息。给定n个字符串，来自于Vasya的电话簿中的条目。每一条都以朋友的姓名开头，然后跟着当前条目中的电话号码个数，然后是本人的电话号码。有可能几个相同的电话被记录在同一个记录中。

Vasya还认为，如果电话号码a是电话号码b的后缀（也就是说，号码b以a结尾），这两个号码被当作同一个电话号码，那么a被认为是无城市代码，它不应该被考虑。

输出整理后Vasya朋友的电话号码信息。有可能两个不同的人有相同的号码。如果一个人有两个电话号码x和y，x是y的后缀（即y以x结尾），则不输出x。

如果Vasya的电话簿中的某些朋友记录了几次，那么只需要记录一次。

【输入形式】

输入第一行一个整数n(1<=n<=20)，Vasya的电话簿上的条目数。

以下n行后面是描述中的格式记录。 朋友的姓名中不包含空字符，长度不超过10位，由小写英文字母组成。电话号码个数在1 ~ 10之间。每个电话号码的长度范围在1~10之间，可以包含前导0。

【输出形式】

输出Vasya的朋友的电话号码的有序信息。首先输出电话簿中的朋友数目m。

接下来的m行，包含以格式“姓名 电话号码个数 电话号码1 … 电话号码k"的条目，号码间以空格分隔。每个记录包含当前朋友的所有电话号码。

每个条目输出按照姓名字母序进行排序，电话号码按照从小到大的顺序排列（注意电话号码比较规则：“1”<“01”、“12”<“012”，依此类推）

【样例输入】

4
ivan 3 123 123 456
ivan 2 456 456
ivan 8 789 3 23 6 56 9 89 2
dasha 2 23 789

【样例输出】

2
dasha 2 23 789 
ivan 4 2 123 456 789

题解

思路

• 1.map+set存下名字和对面的号码，set使用结构体，set是自动排序的，所以号码的排序我们在这里解决了，而且set本身是去重的，不会有重复的号码出现。
• 2.遍历map拿出所有的set进行去重，set去重是两层循环，后者和前者是同一个set，前者的每一项和后者的每一项进行比较看前者的这一项是否需要去掉
• 3.去重之后我们转存vector进行最后一步字典序，(这里不转存直接输出也是通过5个样例)，其实用不用vector对这个题好像是一样的
• 4.最后按照题目要求输出就可以了
• 注意：删除后，i–，这样才能保证i的位置没动
• 这个题样例过了一半，原因没找到，我觉得思路应该没问题吧！

代码

#include<iostream>
#include<map>
#include<set>
#include<vector>
#include<algorithm>
using namespace std;
/******************set结构体*************************/
struct phonenum{
	int len;
	string num;
	/**************set或者优先队列这些使用结构体要写排序规则*********************/
	/**************顺便进行了电话号码的比较*********************/
	bool operator < (const phonenum &a) const{
		if(len!=a.len) return len<a.len;
		else return num<a.num;
	}
};
/******************vector结构体**********************/
struct node{
	string name;
	set<phonenum> nums;
};
/******************vector排序规则********************/
bool cmp(node a,node b){
	return a.name<b.name;
}
int main(){
	map<string,set<phonenum> > m;
	vector<node> res;
	int n;
	cin>>n;
	while(n--){	
		int cnt;
		string name;
		cin>>name>>cnt;//输入名字和号码个数 
		for(int i=0;i<cnt;i++){
			phonenum temp;//temp结构体准备输入号码： 
			cin>>temp.num;//输入号码 
			temp.len=temp.num.size();//用于后面去重的判断       
			m[name].insert(temp); 
		}
	} 
	/******************遍历map，拿出所有没去重的号码**************************/
	for(map<string,set<phonenum> >::iterator it=m.begin();it!=m.end();it++){
		set<phonenum> temp=it->second;//temp<set> 拿出set准备去重
		for(set<phonenum>::iterator i=temp.begin();i!=temp.end();){
			bool flag=false;//控制是否删除该项
			string temp_num=i->num;//当前号码 
			int temp_len=i->len; //当前号码长度
			for(set<phonenum>::iterator j=temp.begin();j!=temp.end();j++){	
				if(i==j) continue;
				/***********************第二层循环拿出比较的号码信息*********************/
				string temp_num2=j->num;
				int temp_len2=j->len;
				if(temp_len>temp_len2) continue;  //号码长的肯定不会被删除掉 
				/*******拿出比较的号码比较长，那么切割后缀比较，如果相同flag=true********/
				else if(temp_num2.substr(temp_len2-temp_len,temp_len)==temp_num){
					flag=true;
					break; 
				}
			} 
			if(flag){
				temp.erase(i);
				i--;
			}
			i++;
		}
		/***************去重完毕后，重新赋给map*******************************/
		it->second=temp; 
	} 
	cout<<m.size()<<endl;//输出总的个数 
	for(map<string,set<phonenum> >::iterator it=m.begin();it!=m.end();it++){
		node temp;
		temp.name=it->first;
		temp.nums=it->second;
		res.push_back(temp);//转存vector进行姓名字典序排序 
		/*set<phonenum> temp=it->second;
		cout<<it->first<<" "<<temp.size()<<" ";//输出当前name和对应的去重后的号码数 
		for(set<phonenum>::iterator i=temp.begin();i!=temp.end();i++){
			cout<<i->num<<" ";//输出set中所有的去重后的号码 
		}
		cout<<endl;*/
	}
	sort(res.begin(),res.end(),cmp);//姓名字典序排序 
	for(int i=0;i<res.size();i++){
		set<phonenum> temp=res[i].nums;
		cout<<res[i].name<<" "<<temp.size()<<" ";//输出当前name和对应的去重后的号码数 
		for(set<phonenum>::iterator i=temp.begin();i!=temp.end();i++){
			cout<<i->num<<" ";//输出set中所有的去重后的号码 
		}
		cout<<endl;
	}
	return 0;
}