前言

从今天起，不定期更新C++的STL库以及算法练习的笔记
分享给大家也是督促自己不断努力学习算法
学习算法之前，要想高效简洁的写好代码，还需要熟练掌握STL库的一些方法和数据结构
参考书籍：
《算法竞赛入门经典》（第2版）刘汝佳著
《挑战程序设计竞赛》巫泽俊主译
我的笔记和题目将以上两本书中内容精华进行整合，练习题目会依据书后习题从oj，poj等平台选取

一、题目描述

输入一些单词，找出所有满足如下条件的单词：该单词不能通过字母重排，得到输入文本中的另外一个单词。在判断是否满足条件时，字母不分大小写，但在输出时应保留输入中的大小写，按字典序进行排列（所有大写字母在所有小写字母的前面）
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
注：文末附有原版英文题目

二、思路分析与代码书写

1.映射map

map就是从键（key）到值（value）的映射。在离散数学中我们学习过单射（x满y可以不满一对一）、满射（x满y满允许多对一）以及一一映射（二者的结合），这里我们是一一映射。
如用map<string,int>week_name来表示“星期名字到星期编号”的映射，然后用week_name["Monday"]=1来赋值。（参考刘汝佳老师的讲解）
实际应用中，map更多的用在不同类型一对一的计数或者二叉搜索树。
如果对map的使用不熟练，或者第一次接触，可以看这一篇文章：
C++STL映射map用法

2.题目思路分析

因为只要字母重排与另一个单词一致即可算重复了，则我们可以使用map构造单词字母序列与出现次数的映射。map<string,int> cnt
之后可以通过cnt[这个单词的字母序列]++来对每个序列计数
最终我们需要输出的就是计数结果为1的那些字母序列对应的原单词

除了映射，因为题目中没有给出输入单词的数量（也没有允许用户自己决定），故我们还需要一个不定长数组vector来对输入的单词进行存储。想到这里，自然会想到输出的单词数量也是未知的，因此再用一个vector专门保存输出的答案。

由此我们意识到，需要专门定义一个函数，对每一个输入的单词进行“标准化”。将单词先全部转化为小写字母，再对所有字母进行排序，得到字母序列。

最后我们根据映射的结果，找到对应的原单词并输出即可。

3.完整代码书写

该代码参考刘汝佳老师书上的代码，自己根据思路独立完成，可能细节上与老师略有不同。

首先是头文件，一个都不能少。（实际写代码过程中可能是边写边添加的）

#include<iostream>
#include<algorithm>
#include<map>
#include<string>
#include<cctype>
#include<vector>

其中cctype提供tolower()函数
algorithm提供sort()函数

采用自顶向上的写法，先写主函数。
先搭好框架：

int main()
{
	string s;//每次接一个单词进入程序
	while(cin>>s){
		
		words.push_back(s);
		
		if()cnt[字母序列]=0;//如果首次出现该单词（的字母序列），初始化
		cnt[字母序列]++;//该单词（的字母序列）次数+1 
	} 
	
	vector<string> ans;//存储所有答案单词
	for(int i=0;i<words.size();i++){
		
	} 
	sort(ans.begin(),ans.end());//按字典序对所有答案进行排序
	for(int i=0;i<ans.size();i++)cout<<ans[i]<<endl; 
	return 0;
}

再完善细节：

int main()
{
	string s;//每次接一个单词进入程序
	while(cin>>s){
		if(s[0]=='#')break;//所有单词输入完毕，退出输入的循环 
		words.push_back(s);
		string r=repr(s);//对单词进行标准化
		if(!cnt.count(r))cnt[r]=0;//如果首次出现该单词（的字母序列），初始化
		cnt[r]++;//该单词（的字母序列）次数+1 
	} 
	
	vector<string> ans;//存储所有答案单词
	for(int i=0;i<words.size();i++){
		if(cnt[repr(words[i])]==1){//该单词（的字母序列）只出现了一次 
			ans.push_back(words[i]);//则该单词为答案 
		}
	} 
	sort(ans.begin(),ans.end());//按字典序对所有答案进行排序
	for(int i=0;i<ans.size();i++)cout<<ans[i]<<endl; 
	return 0;
}

最后实现标准化一个单词的函数：

string repr(const string& s)
{
	string newWord=s;
	for(int i=0;i<newWord.length();i++){
		newWord[i]=tolower(newWord[i]);
	}
	sort(newWord.begin(),newWord.end());//注意string类型排序方式
	return newWord; 
}