2013百度校招笔试真题以及解析(二)

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/sinat_35512245/article/details/54426746

1、一个单词单词字母交换,可得另一个单词,如army->mary,成为兄弟单词。提供一个单词,在字典中找到它的兄弟。描述数据结构和查询过程。


思路1:使用hash_map和链表

(1)首先定义一个key,使得兄弟单词有相同的key,不是兄弟的单词有不同的key。例如,将单词按字母从小到大重新排序后作为其key,比如bad的key为abd,good的key为dgoo。 (2)使用链表将所有兄弟单词串在一起,hash_map的key为单词的key,value为链表的起始地址。 (3)开始时,先遍历字典,将每个单词都按照key加入到对应的链表当中。 (4)当需要找兄弟单词时,只需求取这个单词的key,然后到hash_map中找到对应的链表即可。

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

引用:原文链接

思路2:同样使用hash_map和链表

(1)将每一个字母对应一个质数,然后让对应的质数相乘,将得到的值进行hash,这样兄弟单词的值就是一样的了,并且不同单词的质数相乘积肯定不同。

注解: 根据数学定理:任何一个大于1的自然数N,都可以唯一分解成有限个质数的乘积 N=(P_1^a1)*(P_2^a2)……(P_n^an) , 这里P_1小于P_2小于…小于P_n是质数,且唯一。 例如 a=2 b=3 c=5 d=7 e=11… f(abcd)=2*3*5*7=210 然后字典里找乘积210的位数相同的一定是这5个字母组合的单词就是兄弟单词 (2)使用链表将所有兄弟单词串在一起,hash_map的key为单词的质数相乘积,value为链表的起始地址。 (3)对于用户输入的单词进行计算,然后查找hash,将链表遍历输出就得到所有兄弟单词。

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

引用:原文链接


2、一个url指向的页面里面有另一个url,最终有一个url指向之前出现过的url或空,这两种情形都定义为null。这样构成一个单链表。给两条这样单链表,判断里面是否存在同样的url。url以亿级计,资源不足以hash。


本题可以抽象为有环和无环情况下的链表交叉问题:

情况一:两条单链表均无环   最简单的一种情况,由于两条链表如果交叉,他们的尾节点必然相等(Y字归并),所以只需要判断他们的尾节点是否相等即可。

情况二:两条单链表均有环   这种情况只需要拆开一条环路(注意需要保存被设置成null的节点),然后判断另一个单链表是否仍然存在环路,如果存在,说明无交叉,反之,则有交叉的情况。

情况三:两条单链表,一条有环路,一条无环路   这种情况显然他们是不可能有交叉的。


附:如何判断一条单链表是否存在环路,以及找出环路的入口

快慢指针:在表头设置两个指针fast与slow,fast指针与slow指针同时向前移动,但是fast每次移动2个节点,slow每次移动1个节点,若fast指向null或者fast==slow时停止,这时如果fast指向null,则说明没有环路,若fast==slow则说明有环路。

找环路入口:当fast==slow时,将fast重新指向表头。slow原地不动。然后fast和slow在同时以每次一个节点的速度向前移动,当他们再次重合时,就是环路入口。证明如下:

1.证明fast和slow肯定会重合 在slow和fast第一次相遇的时候,假定slow走了n步骤,环路的入口是在p步的时候经过的,那么有slow走的路径: p+c = n; c为p1和p2相交点,距离环路入口的距离;fast走的路径: p+c+k*L = 2*n; L为环路的周长,k是整数。显然,如果从p+c点开始,p1再走n步骤的话,还可以回到p+c这个点同时p2从头开始走的话,经过n步,也会达到p+c这点。

2.fast和slow在p+c点会重合,显然他们从环的入口点就开始重合。

转自http://iam42.iteye.com/blog/1680444

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏PHP在线

关于PHP浮点数精度损失问题

$f = 0.57; echo intval($f * 100); //56 结果可能有点出乎你的意外,PHP遵循IEEE 754双精度: 浮点数, 以64位...

30450
来自专栏技术总结

算法(2)

25090
来自专栏WD学习记录

数据结构与算法2016-05-31

数据元素是数据的基本单位,在计算机程序中通常被作为一个整体进行考虑和处理。一个数据元素可由若干个数据项组成。数据项是不可分割的、含有独立意义的最小数据单位,数据...

11720
来自专栏开源优测

[快学Python3]二分查找[策略优化版本]

概述 在上文《二分查找》中,我们了解了二分查找基本实现原理和具体的实现算法。 但大家有没有发现,如果目标查找值,如果在查找序列中存在多个,则查找返回的索引值,会...

21360
来自专栏desperate633

LintCode 恢复旋转排序数组题目分析代码

说明 什么是旋转数组? 比如,原始数组为[1,2,3,4], 则其旋转数组可以是[1,2,3,4], [2,3,4,1], [3,4,1,2], [4,1,...

9320
来自专栏开源优测

[快学Python3]二分查找[策略优化版本]

概述 在上文《二分查找》中,我们了解了二分查找基本实现原理和具体的实现算法。 但大家有没有发现,如果目标查找值,如果在查找序列中存在多个,则查找返回的索引值,会...

33250
来自专栏ACM算法日常

POJ1258:Agri-Net-最小生成树

Farmer John has been elected mayor of his town! One of his campaign promises was...

10820
来自专栏人工智能头条

70个NumPy练习:在Python下一举搞定机器学习矩阵运算

38120
来自专栏数据结构与算法

洛谷T21776 子序列

题目描述 你有一个长度为 nn 的数列 ,这个数列由 0,10,1 组成,进行 mm 个的操作: 1~l~r1 l r :把数列区间 [l, r][l,r] ...

43280
来自专栏大神带我来搬砖

如何编写更优雅的代码——java中用break语句模拟goto来中止代码块的执行

根据https://docs.oracle.com/javase/specs/jls/se7/html/jls-14.html, java的break语句不仅可...

28090

扫码关注云+社区

领取腾讯云代金券