劍指offer_面試題55_字元流中第一個不重複的字元 *

劍指offer_面試題55_字元流中第一個不重複的字元 *

題目:請實現一個函式用來找出字元流中第一個只出現一次的字元。

例如,當從字元流中只讀出前兩個字元“go”時,第一個只出現一次的字元是“g”。當從該字元流中讀出前六個字元“google”時,第一個只出現一次的字元時“l”。

ps. 本題,我在阿里二面的時候,被問到了,需要注意。

第一種解法:

一種很笨的解法,時間效率低下,但確是我的第一反應。需要記下以便反思。

1、首先用一個指標指向第一個出現的字元,然後用第二指標,指向出現的第二個字元,並讓第二指標向後移動,當出現和第一個指標相同的字元時,將這兩個字元置為 “ * ”

2、一輪遍歷後,第二個指標向後移動一位,再次用第二個指標遍歷,方式和步驟一 一樣,這樣經過 n 輪遍歷。所有重複的字元都變成了 “ * ”

3、然後重新遍歷,當出現第一個不是 “ * ”的字元時,就找到了第一個只出現一次的字元

如上步驟所說,這種方法效率十分低下,需要更加高效的方法。

第二種解法:

對這個題目思考,可以發現,出現的字元 和 它的出現的次數 是一種對應關係,自然聯想到 雜湊表key-value 這種對應,或者應用
關聯容器 map,可以很方便的解決這個問題。

map 容器中,它的一個元素 就是一組(key,value)對應的資料。建議 先去 瞭解一下 雜湊表 和 map 的相關概念和原理。

以下是第二種解法的程式碼:

#include <iostream>
#include <map>
#include <string>
#include <cstdlib>      /*exit()的標頭檔案*/
//#include <exception>
using namespace std;
char First_appearing_once(string str)
{
if(str.empty())
{
//throw new exception;
cout << "字串為空" << endl;
exit(1);   /*異常退出*/
}
map<char,int> word_count;
/**unsigned int i;這裡要用無符號整型,因為size()產生的是無符號整型;直接用int,會產生警告*/
string::size_type i;                       /**size_type 就是容器中定義的無符號整型*/
char target_ch;
for(i = 0; i < str.size(); i  )
{
word_count[str[i]];
}
for(i = 0; i < str.size(); i  )
{
if(1 == word_count[str[i]])
{
target_ch = str[i];
break;
}
}
return target_ch;
}
int main()
{
//string str("abbacde");
//string str("google");
//string str;
string str("abbacde cdgoogle ");
char x;
x = First_appearing_once(str);
cout << x << endl;
return 0;
}

結果如下:

PS:疑問:在上述程式碼中,當字串為空時,如何丟擲異常,並退出程式?

可以看到在程式碼中我註釋掉的部分 “ throw new exception; ” 這樣寫有點問題,就是在程式會退出時,會出現 “例如程式崩潰時” 出現的彈框。

這個問題我沒有解決,只能用 exit(1)代替了。

我在 丟擲異常 這一塊 不是很熟練,如果有 哪位 大神 會,麻煩解答一下,謝謝。

/*點滴積累,我的一小步O(∩_∩)O~*/