当前位置：范文城>职场范本>面试>

谷歌面试题

面试阅读(2.16W)

实现一个算法来判断一个字符串中的字符是否唯一(即没有重复).不能使用额外的数据结构。 (即只使用基本的数据结构)

解答

首先，你可以问面试官，构成字符串的字符集有多大?是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;

}

标签：面试题谷歌

图文推荐