谷歌面试题
实现一个算法来判断一个字符串中的字符是否唯一(即没有重复).不能使用额外的数据结构。 (即只使用基本的数据结构)
解答
首先,你可以问面试官,构成字符串的字符集有多大?是ASCII字符,还是只是26个字母? 还是有更大的字符集,对于不同的情况,我们可能会有不同的解决方案。
如果我们假设字符集是ASCII字符,那么我们可以开一个大小为256的bool数组来表征每个字 符的出现。数组初始化为false,遍历一遍字符串中的字符,当bool数组对应位置的值为真, 表明该字符在之前已经出现过,即可得出该字符串中有重复字符。否则将该位置的bool数组 值置为true。代码如下:
1 2 3 4 5 6 7 8 9 10 11 12 13 | 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。相应代码如下:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | 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单元来表征字符出现,一个用位来表征。 完整代码如下:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 | #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),那就更好办了,用位运算只需要一个整型数即可。
1 2 3 4 5 6 7 8 9 10 11 12 | 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实现】
1 2 3 4 5 6 7 8 9 | publicstaticbooleanisUniqueChars(Stringstr){ intchecker=0; for(inti=0;i<th();++i){ intval=At(i)-‘a’; if((checker&(1<<val))>0)returnfalse; checker|=(1<<val); } returntrue; } |
1 2 3 4 5 6 7 8 9 | 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; } |
-
外企面试的五大忌讳
外企面试的五大忌讳1迟到失约守时守约在人们的日常生活中已成为起码的礼数,迟到、失约更是外企面试中的大忌。这不但会表现出求职者没有时间观念和责任感,更会让面试官觉得你对这份工作没有热忱,从而对你的第一印象大打折扣。面试官提醒求职者,去面试时最好提前10...
-
面试简历的自我评价(精选15篇)
日子在弹指一挥间就毫无声息的流逝,没想到也到了自己找工作的时间,需要为此写一份简历了哦。千万不能认为简历随便应付就可以喔,以下是小编帮大家整理的面试简历的自我评价,希望对大家有所帮助。面试简历的自我评价1本人虽然毕业于化工专业,但是一直喜欢英语,大学期...
-
【荐】面试自我评价
在平时的学习、工作或生活中,我们经常会被要求写一份自我评价,自我评价是个人对自己思想、愿望、行为和个性特点的判断和评价。那么你有了解过自我评价吗?以下是小编收集整理的面试自我评价,欢迎阅读,希望大家能够喜欢。面试自我评价1【财务面试自我评价范例一】具...
-
面试失败的行为
面试失败的行为1一、面试爽约,无致电说明许多求职者在接到面试通知电话以后口头答应了面试邀约,可是后来由于种种原因没有赴约,也没有主动给通知面试的公司说明情况。更有甚者在公司给爽约的求职者后再次电话询问情况的时候,求职者根本不愿再接听电话。这种不负责...