查看匯總:2015軟件水平考試程序員精選題匯總
第一個(gè)只出現(xiàn)一次的字符
題目:在一個(gè)字符串中找到第一個(gè)只出現(xiàn)一次的字符。如輸入abaccdeff,則輸出b。
分析:這道題是2006年google的一道筆試題。
看到這道題時(shí),最直觀的想法是從頭開始掃描這個(gè)字符串中的每個(gè)字符。當(dāng)訪問到某字符時(shí)拿這個(gè)字符和后面的每個(gè)字符相比較,如果在后面沒有發(fā)現(xiàn)重復(fù)的字符,則該字符就是只出現(xiàn)一次的字符。如果字符串有n個(gè)字符,每個(gè)字符可能與后面的O(n)個(gè)字符相比較,因此這種思路時(shí)間復(fù)雜度是O(n2)。我們試著去找一個(gè)更快的方法。
由于題目與字符出現(xiàn)的次數(shù)相關(guān),我們是不是可以統(tǒng)計(jì)每個(gè)字符在該字符串中出現(xiàn)的次數(shù)?要達(dá)到這個(gè)目的,我們需要一個(gè)數(shù)據(jù)容器來存放每個(gè)字符的出現(xiàn)次數(shù)。在這個(gè)數(shù)據(jù)容器中可以根據(jù)字符來查找它出現(xiàn)的次數(shù),也就是說這個(gè)容器的作用是把一個(gè)字符映射成一個(gè)數(shù)字。在常用的數(shù)據(jù)容器中,哈希表正是這個(gè)用途。
哈希表是一種比較復(fù)雜的數(shù)據(jù)結(jié)構(gòu)。由于比較復(fù)雜,STL中沒有實(shí)現(xiàn)哈希表,因此需要我們自己實(shí)現(xiàn)一個(gè)。但由于本題的特殊性,我們只需要一個(gè)非常簡單的哈希表就能滿足要求。由于字符(char)是一個(gè)長度為8的數(shù)據(jù)類型,因此總共有可能256 種可能。于是我們創(chuàng)建一個(gè)長度為256的數(shù)組,每個(gè)字母根據(jù)其ASCII碼值作為數(shù)組的下標(biāo)對應(yīng)數(shù)組的對應(yīng)項(xiàng),而數(shù)組中存儲的是每個(gè)字符對應(yīng)的次數(shù)。這樣我們就創(chuàng)建了一個(gè)大小為256,以字符ASCII碼為鍵值的哈希表。
我們第一遍掃描這個(gè)數(shù)組時(shí),每碰到一個(gè)字符,在哈希表中找到對應(yīng)的項(xiàng)并把出現(xiàn)的次數(shù)增加一次。這樣在進(jìn)行第二次掃描時(shí),就能直接從哈希表中得到每個(gè)字符出現(xiàn)的次數(shù)了。
參考代碼如下:
///////////////////////////////////////////////////////////////////////
// Find the first char which appears only once in a string
// Input: pString - the string
// Output: the first not repeating char if the string has, otherwise 0
///////////////////////////////////////////////////////////////////////
char FirstNotRepeatingChar(char* pString)
{
// invalid input
if(!pString)
return 0;
// get a hash table, and initialize it
constinttableSize =256;
unsignedinthashTable[tableSize];
for(unsignedinti = 0; ihashTable[i] = 0;
// get the how many times each char appears in the string
char* pHashKey = pString;
while(*(pHashKey) != '\0')
hashTable[*(pHashKey++)] ++;
// find the first char which appears only once in a string
pHashKey = pString;
while(*pHashKey != '\0')
{
if(hashTable[*pHashKey] == 1)
return *pHashKey;
pHashKey++;
}
// if the string is empty
// or every char in the string appears at least twice
return 0;
}
相關(guān)推薦:
北京 | 天津 | 上海 | 江蘇 | 山東 |
安徽 | 浙江 | 江西 | 福建 | 深圳 |
廣東 | 河北 | 湖南 | 廣西 | 河南 |
海南 | 湖北 | 四川 | 重慶 | 云南 |
貴州 | 西藏 | 新疆 | 陜西 | 山西 |
寧夏 | 甘肅 | 青海 | 遼寧 | 吉林 |
黑龍江 | 內(nèi)蒙古 |