本題為《劍指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 程序員人生 版權所有
