谷歌面試題

欄目: 面試 / 發佈於: / 人氣:2.09W

實現一個算法來判斷一個字符串中的字符是否唯一(即沒有重複).不能使用額外的數據結構。 (即只使用基本的數據結構)

解答

首先，你可以問面試官，構成字符串的字符集有多大?是ASCII字符，還是隻是26個字母? 還是有更大的字符集，對於不同的情況，我們可能會有不同的解決方案。

如果我們假設字符集是ASCII字符，那麼我們可以開一個大小為256的bool數組來表徵每個字符的出現。數組初始化為false，遍歷一遍字符串中的字符，當bool數組對應位置的值為真，表明該字符在之前已經出現過，即可得出該字符串中有重複字符。否則將該位置的bool數組值置為true。代碼如下：

boolisUnique1(strings)

{

boola[256];

memset(a,0,sizeof(a));

intlen=th();

for(inti=0;i<len;++i)

{

intv=(int)s[i];

if(a[v])returnfalse;

a[v]=true;

}

returntrue;

}

該算法的時間複雜度為O(n)。我們還可以通過位運算來減少空間的使用量。用每一位表徵相應位置字符的出現。對於ASCII字符，我們需要256位，即一個長度為8的數組a即可。這裏的關鍵是要把字符對應的數字，映射到正確的位上去。比如字符’b’對應的代碼是98，那麼我們應該將數組中的哪一位置為1呢?用98除以32，得到對應數組a的下標： 3。98對32取模得到相應的位：2。相應代碼如下：

boolisUnique2(strings)

{

inta[8];

memset(a,0,sizeof(a));

intlen=th();

for(inti=0;i<len;++i)

{

intv=(int)s[i];

intidx=v/32,shift=v%32;

if(a[idx]&(1<<shift))returnfalse;

a[idx]|=(1<<shift);

}

returntrue;

}

兩個算法的本質其實是一樣的，只不過一個用bool單元來表徵字符出現，一個用位來表徵。完整代碼如下：

#include <iostream>

#include <cstring>

usingnamespacestd;

boolisUnique1(strings)

{

boola[256];

memset(a,0,sizeof(a));

intlen=th();

for(inti=0;i<len;++i)

{

intv=(int)s[i];

if(a[v])returnfalse;

a[v]=true;

}

returntrue;

}

boolisUnique2(strings)

{

inta[8];

memset(a,0,sizeof(a));

intlen=th();

for(inti=0;i<len;++i)

{

intv=(int)s[i];

intidx=v/32,shift=v%32;

if(a[idx]&(1<<shift))returnfalse;

a[idx]|=(1<<shift);

}

returntrue;

}

intmain()

{

strings1="i am hawstein.";

strings2="abcdefghijklmnopqrstuvwxyzABCD1234567890";

cout<<isUnique1(s1)<<" "<<isUnique1(s2)<<endl;

cout<<isUnique2(s1)<<" "<<isUnique2(s2)<<endl;

return0;

}

如果字符集只是a-z(或是A-Z)，那就更好辦了，用位運算只需要一個整型數即可。

boolisUnique3(strings)

{

intcheck=0;

intlen=th();

for(inti=0;i<len;++i)

{

intv=(int)(s[i]-'a');

if(check&(1<<v))returnfalse;

check|=(1<<v);

}

returntrue;

}

【JAVA實現】

publicstaticbooleanisUniqueChars(Stringstr){

intchecker=0;

for(inti=0;i<th();++i){

intval=At(i)-‘a’;

if((checker&(1<<val))>0)returnfalse;

checker|=(1<<val);

}

returntrue;

}

publicstaticbooleanisUniqueChars2(Stringstr){

boolean[]char_set=newboolean[256];

for(inti=0;i<th();i++){

intval=At(i);

if(char_set[val])returnfalse;

char_set[val]=true;

}

returntrue;

}

Tags：面試題谷歌