本题为《剑指Offer》“面试题35：第1个只出现1次的字符”1节中的“相干题目”。
定义1个函数，输入两个字符串，从第1个字符串中删除在第2个字符串中出现过的所有字符。
字符是1个长度为8的数据类型，共256种可能。创建1个长度为256的bool型数组，数组下标为字符对应的ASCII码值，分别记录字符是不是在第2个字符串中出现过。由于直接调用erase函数删除元素效力较低，且在遍用时改变容器可能会造成严重毛病，所以创建1个临时字符串将不会被删除的字符保存下来，再赋值给第1个字符串。
auto DeleteAppearanceChar(string &s1, const string &s2) -> void{
//如果s1或s2为空，则直接返回
if(!s1.size() || !s2.size()){
return;
}
//创建临时字符串
string tempString;
//创建bool数组
const int tableSize = 256;
bool hashTable[tableSize];
//将所有bool值初始化为false
for(unsigned int i = 0; i < tableSize; ++i){
hashTable[i] = false;
}
//遍历s2，如果字符出现，则将数组对应位置标志为true
auto begin = s2.begin();
while(begin != s2.end()){
hashTable[*(begin ++)] = true;
}
//遍历s1，如果字符没在s2中出现过就加入到tempString中
begin = s1.begin();
while(begin != s1.end()){
if(!hashTable[*begin]){
tempString.push_back(*begin);
}
begin++;
}
//用临时字符串的值替换s1原本的内容
s1.assign(tempString);
}使用临时字符串会增加空间开消，可能使空间复杂度上升O（n）,删除s1中字符的时候可使用两个1前1后的迭代器，前面的迭代器寻觅后面第1个没在s2中出现的字符，然后复制到前1个迭代器所指的位置，再将两个迭代器顺次后移1步，如此循环直到后面的迭代器抵达s1末尾。最后再将两个迭代器之间的元素删除，这样删除操作就全在字符串尾部进行了，时间复杂度照旧为O（n）。删除s1中字符的代码可以用下面的代码替换。
//使用1前1后两个迭代器
begin = s1.begin();
auto behind = s1.begin();
//任意迭代器抵达字符串尾部后停止
while(begin != s1.end() && behind != s1.end()){
//如果字符没在s2中出现，则进行复制操作
if(!hashTable[*begin]){
*(behind++) = *(begin++);
continue;
}
//迭代器begin向后直到寻觅到下1个没在s2中出现的字符或抵达字符串尾部为止
while(begin++ != s1.end() && hashTable[*begin]);
if(begin == s1.end()){
break;
}
//找到以后进行复制操作，此行代码可省略
*(behind++) = *(begin++);
}
//删除s1末尾的字符
s1.erase(behind, begin);
本题为《剑指Offer》“面试题35：第1个只出现1次的字符”1节中的“相干题目”。
定义1个函数，删除字符串中所有重复出现的字符。
本题与上题大体类似，遍历1个字符串，如果遇到没出现过的字符便存入临时字符串中，并将对应的标志位设为true（表示出现过），遇到出现过的则直接跳过。
auto DeleteRepeatChar(string &s) -> void{
if(!s.size()){
return;
}
string tempString;
const int tableSize = 256;
bool hashTable[tableSize];
for(unsigned int i = 0; i < tableSize; ++i){
hashTable[i] = false;
}
auto begin = s.begin();
while(begin != s.end()){
if(!hashTable[*begin]){
tempString.push_back(*begin);
//遇到没出现过的字符，将数组对应位置标志为true
hashTable[*(begin)] = true;
}
begin++;
}
s.assign(tempString);
}本题为《剑指Offer》“面试题35：第1个只出现1次的字符”1节中的“相干题目”。
在英语中，如果两个单词中出现的字母相同，并且每一个字母出现的次数也相同，那末这两个单词互为变位词。
与前面两题类似，用1个int型数组来统计其中1个单词中所有字符出现的次数，再遍历另外一个单词，每遇到1个字符，便将数组对应位置的值减1，如果最后数组全部元素都未0，则说明是变位词，需要注意的是无效输入的处理。
//定义1个全局变量监控输入毛病
bool invaildInput = false;
auto IsAnagram(const string &s1, const string &s2) -> bool{
//如果最少有1个单词为空，则报输入毛病，并返回false。这里认定两个单词都为空也返回false（由于空字符串不是单词），这些边界条件可以跟面试官沟通如何判定，同时可以沟通的是完全相同的单词是不是算做换位词
if(!s1.size() || !s2.size()){
invaildInput = true;
return false;
}
//检查是不是有非字母之外的非法输入，如果有则报输入毛病，并返回false
auto begin = s2.begin();
while(begin != s2.end()){
if (!((*begin >= 'a' && *begin <= 'z') || (*begin >= 'A' && *begin <= 'Z'))){
invaildInput = true;
return false;
}
begin++;
}
begin = s1.begin();
while(begin != s1.end()){
if (!((*begin >= 'a' && *begin <= 'z') || (*begin >= 'A' && *begin <= 'Z'))){
invaildInput = true;
return false;
}
begin++;
}
const int tableSize = 256;
int hashTable[tableSize];
for(unsigned int i = 0; i < tableSize; ++i){
hashTable[i] = 0;
}
begin = s2.begin();
while(begin != s2.end()){
hashTable[*(begin ++)] ++;
}
begin = s1.begin();
while(begin != s1.end()){
//将遇到的每一个字符在数组对应位置的值⑴，如果出现负值则直接返回false
if(--hashTable[*begin]< 0 ){
return false;
}
begin++;
}
//遍历数字，检查是不是有不为0的值
for(unsigned int i = 0; i < tableSize; ++i){
if(hashTable[i] != 0){
return false;
}
}
return true;
}《剑指Offer》“面试题35：第1个只出现1次的字符”1节中的“本题拓展”
在字符串中找出第1个只出现1次的字符，斟酌汉字的情况。
关于本题，个人斟酌了两个思路：
第1：照瓢画葫芦，与原题采取完全1样的解法，只是将ASCII码换为中文Unicode编码，由于汉字的Unicode编码位数较多，范围为0x3000到0x9FFF，虽然也能够将空间效力解释为O（1），但这个常量很大，最少需要用2的15次方级的空间，空间开消太大，感觉不太公道。
第2：使用哈希表，这个方法用java可行，但是C++标准库中没有哈希表，自定义哈希表的代码量较大，不合适在面试时书写。
所以恳请热情的高手能够解答我的疑惑，不胜感激！
上一篇 java- Java IO
程序员人生，我编程，我富裕，记住wfuyu网，php教程，php学习，php手册，CMS模版制作
声明：本站大部分内容是作者原创，少部分收集于互联网供大家一起学习，原版权很多不明，如有侵权请联系本站，谢谢！
粤ICP备14040726号-1 2015-2020 程序员人生 版权所有
