[劍指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++标準庫中沒有哈希表，自定義哈希表的代碼量較大，不适合在面試時書寫。

是以懇請熱心的高手能夠解答我的疑惑，不勝感激！