现在的位置: 首页 > 综合 > 正文

12-5-9百度笔试后的总结

2018年01月10日 ⁄ 综合 ⁄ 共 398字 ⁄ 字号 评论关闭

1.给定一个单词a,如果通过交换单词中字母的顺序可以得到另外的单词b,那么定义b是a的兄弟单词。现在给定一个字典,用户输入一个单词,如何根据字典找出这个单词有多少个兄弟单词?

   这里有一种很原始的办法,变换所有的单词,得到所有的兄弟单词,然后依次在字典中寻找。可想而知这是很复杂的

基于上面的思想我们对字典进行优化。不妨将字典建成一个hash链表。使得字典中的兄弟单词有相同的key例如 hello 我们选取key为ehllo,这里的key

选取依据是单词中的字母从小到大排列。这样我们就用链表将所有兄弟单词都串在了一起。从而将字典构成了一个hash链表。

   开始遍历字典,将每个单词按照key,加入到对应的链表中。当需要取兄弟单词时,只需取这个单词的key,然后到相应的链表中取查找。

这样创建hash_map时间复杂度为O(n),查找单词的时间复杂度为O(1)


2关于字符串哈希函数


关于字符串如何转key

抱歉!评论已关闭.