Google关于字符串的经典算法

2017-06-19 10:38 阅读 721 次 评论 0 条

Google的算法题大多短小而精悍,逻辑性与技巧性非常强。关于字符串的笔试面试题层出不穷,既然备受青睐必当重视练之。今天所分析的两道算法题都是借助哈希表来实现的,消耗小空间提高时间效率。

第一次只出现一次的字符

我们需要一个数据容器来存放每个字符出现的次数,即将每个字符都映射成一个数字,我们第一个想到的就是哈希表。可以定义哈希表的键值(key)为字符值(value)是字符出现的次数

字符是一个长度为8的数据类型,因此总共需要256种可能,我们可以定义一个长度为256的数组,每个字符依据其ASCll码值作为数组的下标对应数组的一个数字,而数组中存储每个字符出现的次数。

第一次扫描时,更新字符出现的次数的时间复杂度为O(n),第二次扫描时,时间复杂度也是0(n),即总的时间复杂度为0(n)。因为我们创建了一个包含256个字符的数组,大小为常数,所以空间复杂度为O(1)

删除字符串中所有重复的字符

本题依据接触哈希表的思想,我们将下标看做ASCll码对应的字母在字符中是否已经出现,初始时给定所有元素均为false,开始扫描时,若为true,说明已经出现过,直接跳过,若为false,则置为true。如果字符串长度为n,则时间复杂度为O(n)

上述第三步比较繁琐,这里我解释一下:我们在上面定义了fast与slow两个字符指针均指向了str字符串,若str有重复字符串,则fast必然先遍历完,若str无重复,slow与fast一起遍历完。所以置为true之后,我们需要更新slow的首字符为fast,覆盖slow中重复的字符,然后一起向后遍历。

版权声明:本文著作权归原作者所有,欢迎分享本文,谢谢支持!
转载请注明:Google关于字符串的经典算法 | 术与道的分享
分类:编程素养 标签:, ,
1024do.com导航_术与道导航平台

发表评论


表情