题解 Ananagrams(UVa156)紫书P113map的应用

紫书P113；map的应用；UVa146 Ananagrams；

Vjudge题目链接请点击此处

题目大意：

输入一些单词（输入包含若干行，每行不超过80个字符，由一些单词组成。单词由不超过20个大小写字母组成），找出所有满足如下条件的单词：该单词不能通过字母重排，得到输入文本的另外一个单词。在判断是否满足条件时，字母不分大小写，但在输出时应保留输入的大小写，按字典序排列。

Sample Input
ladder came tape soon leader acme RIDE lone Dreis peat
ScAlE orb eye Rides dealer NotE derail LaCeS drIed
noel dire Disk mace Rob dries

Sample Output
Disk
NotE
derail
drIed
eye
ladder
soon

题目分析（思路依据紫书）：

题目要求找出 “不重复” 的单词，那么如何判断 “重复” 是本题的重点；
题目中给的 “重复” 的含义是指：具有相同数量的相同字母构成的两个单词，对字母顺序没有要求。

数据结构选择：由于map具有值对应键的特性，可以方便的帮我们统计出每种单词出现的次数，便于去重，我们可以选择建立一个map来存放不同单词出现的次数。

算法设计：map的合理使用可以帮我们简化代码，但我们仍需要一种可以高效利用map的方法来实现对目标的选择；既然题目要求的 “重复” 没有规定字母顺序，那我们可以把单词中字母的顺序统一化处理来方便比较：将字母全部转化为小写并按照字典序排序；

void change(string& now)
{
    
	 for(int i=0;i<now.length();i++)
	 	 now[i]=tolower(now[i]);
	 sort(now.begin(),now.end());
	 return ;
}

之后依据统一化后的单词进行比较；

模块设计：定义与预处理–输入与初始化–模拟判断–输出–return 0;

代码：

#include<map>
#include<iostream>
#include<string>
#include<cctype>
#include<vector>
#include<algorithm>
using namespace std;

vector<string> txt;
map<string,int> words;
vector<string> answer;
string s;

//txt存读入的全部单词,words存初始化后的单词与其出现次数,answer存只出现过一次的单词

void change(string& now);

int main()
{
    
	 while(cin>>s)
	 {
    
	 	 if(s=="#") break; //遇到#结束读入
	 	 txt.push_back(s);
	 	 string now(s);
	 	 change(now);      //初始化
	 	 words[now]++;     //统计次数
	 }
	 for(int i=0;i<txt.size();i++)
	 {
    
	 	 string now(txt[i]);
	 	 change(now);
	 	 if(words[now]==1) answer.push_back(txt[i]);
	 }
	 sort(answer.begin(),answer.end());   //输出要求按照字典序排序
	 for(int i=0;i<answer.size();i++) cout<<answer[i]<<endl;
	 return 0;
}

void change(string& now)
{
    
	 for(int i=0;i<now.length();i++)
	 	 now[i]=tolower(now[i]);
	 sort(now.begin(),now.end());
	 return ;
}

要点与细节总结：

1. 灵活利用map中键与值的对应关系，根据场景合理选择；
2. sort使用的两种情况<1. sort(a,a+n) <2. sort(m.begin(),m.end());

更新于2020.6.24