[剑指Offer] 第5章课后题详解

目录

删除指定字符

本题为《剑指Offer》“面试题35：第一个只出现一次的字符”一节中的“相关题目”。

定义一个函数，输入两个字符串，从第一个字符串中删除在第二个字符串中出现过的所有字符。

分析

字符是一个长度为8的数据类型，共256种可能。创建一个长度为256的bool型数组，数组下标为字符对应的ASCII码值，分别记录字符是否在第二个字符串中出现过。由于直接调用erase函数删除元素效率较低，且在遍历时改变容器可能会造成严重错误，所以创建一个临时字符串将不会被删除的字符保存下来，再赋值给第一个字符串。

解法

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中字符的时候可以使用两个一前一后的迭代器，前面的迭代器寻找后面第一个没在s2中出现的字符，然后复制到前一个迭代器所指的位置，再将两个迭代器依次后移一步，如此循环直到后面的迭代器抵达s1末尾。最后再将两个迭代器之间的元素删除，这样删除操作就全在字符串尾部进行了，时间复杂度依旧为O（n）。删除s1中字符的代码可以用下面的代码替换。

    //使用一前一后两个迭代器
    begin = s1.begin();
    auto behind = s1.begin();
    //任意迭代器抵达字符串尾部后停止
    while(begin != s1.end() && behind != s1.end()){
        //如果字符没在s2中出现，则进行复制操作
        if(!hashTable[*begin]){
            *(behind++) = *(begin++);
            continue;
        }
        //迭代器begin向后直到寻找到下一个没在s2中出现的字符或者抵达字符串尾部为止
        while(begin++ != s1.end() && hashTable[*begin]);
        if(begin == s1.end()){
            break;
        }
        //找到之后进行复制操作，此行代码可省略
        *(behind++) = *(begin++);
    }
    //删除s1末尾的字符
    s1.erase(behind, begin);

删除重复元素

本题为《剑指Offer》“面试题35：第一个只出现一次的字符”一节中的“相关题目”。

定义一个函数，删除字符串中所有重复出现的字符。

分析

本题与上题大体类似，遍历一个字符串，如果遇到没出现过的字符便存入临时字符串中，并将对应的标志位设为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：第一个只出现一次的字符”一节中的“相关题目”。

在英语中，如果两个单词中出现的字母相同，并且每个字母出现的次数也相同，那么这两个单词互为变位词。

分析

与前面两题类似，用一个int型数组来统计其中一个单词中所有字符出现的次数，再遍历另一个单词，每遇到一个字符，便将数组对应位置的值减1，如果最后数组全部元素都未0，则说明是变位词，需要注意的是无效输入的处理。

解法

//定义一个全局变量监控输入错误
bool invaildInput = false;

auto IsAnagram(const string &s1, const string &s2) -> bool{

    //如果至少有一个单词为空，则报输入错误，并返回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()){
        //将遇到的每个字符在数组对应位置的值-1，如果出现负值则直接返回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：第一个只出现一次的字符”一节中的“本题拓展”

在字符串中找出第一个只出现一次的字符，考虑汉字的情况。

关于本题，个人考虑了两个思路：
第一：照瓢画葫芦，与原题采用完全一样的解法，只是将ASCII码换为中文Unicode编码，由于汉字的Unicode编码位数较多，范围为0x3000到0x9FFF，虽然也可以将空间效率解释为O（1），但这个常量很大，至少需要用2的15次方级的空间，空间开销太大，感觉不太合理。
第二：使用哈希表，这个方法用java可行，但是C++标准库中没有哈希表，自定义哈希表的代码量较大，不适合在面试时书写。

所以恳请热心的高手能够解答我的疑惑，不胜感激！