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

<a href="#%e5%89%91%e6%8c%87offer-%e7%ac%ac5%e7%ab%a0%e8%af%be%e5%90%8e%e9%a2%98%e8%af%a6%e8%a7%a3">剑指offer 第5章课后题详解</a>

<a href="#%e7%9b%ae%e5%bd%95">目录</a>

<a href="#%e5%88%a0%e9%99%a4%e6%8c%87%e5%ae%9a%e5%ad%97%e7%ac%a6">删除指定字符</a>

<a href="#%e5%88%86%e6%9e%90">分析</a>

<a href="#%e8%a7%a3%e6%b3%95">解法</a>

<a href="#%e4%bc%98%e5%8c%96">优化</a>

<a href="#%e5%88%a0%e9%99%a4%e9%87%8d%e5%a4%8d%e5%85%83%e7%b4%a0">删除重复元素</a>

<a href="#%e5%88%86%e6%9e%90-1">分析</a>

<a href="#%e8%a7%a3%e6%b3%95-1">解法</a>

<a href="#%e5%88%a4%e6%96%ad%e5%8f%98%e4%bd%8d%e8%af%8d">判断变位词</a>

<a href="#%e5%88%86%e6%9e%90-2">分析</a>

<a href="#%e8%a7%a3%e6%b3%95-2">解法</a>

<a href="#%e6%b1%82%e5%8a%a9">求助</a>

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

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

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

使用临时字符串会增加空间开销，可能使空间复杂度上升o（n）,删除s1中字符的时候可以使用两个一前一后的迭代器，前面的迭代器寻找后面第一个没在s2中出现的字符，然后复制到前一个迭代器所指的位置，再将两个迭代器依次后移一步，如此循环直到后面的迭代器抵达s1末尾。最后再将两个迭代器之间的元素删除，这样删除操作就全在字符串尾部进行了，时间复杂度依旧为o（n）。删除s1中字符的代码可以用下面的代码替换。

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

本题与上题大体类似，遍历一个字符串，如果遇到没出现过的字符便存入临时字符串中，并将对应的标志位设为true（表示出现过），遇到出现过的则直接跳过。

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

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

《剑指offer》“面试题35：第一个只出现一次的字符”一节中的“本题拓展”

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

关于本题，个人考虑了两个思路：

第一：照瓢画葫芦，与原题采用完全一样的解法，只是将ascii码换为中文unicode编码，由于汉字的unicode编码位数较多，范围为0x3000到0x9fff，虽然也可以将空间效率解释为o（1），但这个常量很大，至少需要用2的15次方级的空间，空间开销太大，感觉不太合理。

第二：使用哈希表，这个方法用java可行，但是c++标准库中没有哈希表，自定义哈希表的代码量较大，不适合在面试时书写。

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