查看: 2671| 回复: 19
跳转到指定楼层
上一主题 下一主题
收起左侧

[CareerCup] 【第三轮】7.7-7.13 CareerCup 4.2

全局:

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
4.2 Given a directed graph, design an algorithm to find out whether there is a route between two nodes.

回复解法可以按照以下格式来
【解题思路】
【时间复杂度】
【空间复杂度】
【gist link】
---------------Optional,如果觉得test case比较好,欢迎写出来分享----------------------
【test case】


Notice:
1、记得在程序注释中表明自己算法的时间、空间复杂度
2、代码难懂之处加注释
3、每道题目有对应的帖子,除了贴解法,欢迎讨论,集思广益
4、任何未尽之处,欢迎回报名帖提问,我会进一步作出修改。




上一篇:【第三轮】7.7-7.13 CareerCup 4.1
下一篇:【第三轮】7.7-7.13 CareerCup 4.3
全局:
【解题思路】1. 表示directed graph 参考了geeksforgeeks,每个顶点有他对应的adjacent list,addedge()用来添加directed edge
                  2. 找路径,最后就变成了在adjacent lists 里找,为了防止可能存在的circle,访问过的顶点需要标记
                  3. 具体查找采用bfs,用一个queue来添加当前正在查看的顶点,dequeue一个顶点要保证已经enqueue它的所有adjacent vertices
                     只要queue没空就循环找下去,直到发现返回true,不然就false

【时间复杂度】O(V+E)
【空间复杂度】O(V)
【gist link】: https://gist.github.com/xun-gong/7242a6c9205de1a3f43d
回复

使用道具 举报

推荐
donnice 2014-7-8 04:07:26 | 只看该作者
全局:
【解题思路】递归思想。当a和b链接后,设定a到b为1,b到a为-1,无路径的两点间距离设为0,以此类推。之后判断a和c是否有路径时,从a开始遍历全图,直到能遍历至c为止。显然,如果在半程中碰到-1或者全为0(即没有路),则返回false。遍历成功则为true
【时间复杂度】O(N^2)
【空间复杂度】O(N)
【gist link】
https://github.com/donnice/donnice/blob/master/Q4_2
【Test case】
我对照的是附件里的图。大家可以拿自己的有向图试一试

SSZ4(QG)_@XM`1(X`QEN13F.jpg (24.45 KB, 下载次数: 3)

SSZ4(QG)_@XM`1(X`QEN13F.jpg
回复

使用道具 举报

🔗
bitcpf 2014-7-9 23:53:41 | 只看该作者
全局:
【解题思路】BST, actually qiuckunion... do not use recursion, but recursion could be easier
【时间复杂度】O(N^2)
【空间复杂度】O(N)
【gist link】https://gist.github.com/bitcpf/629c20bb88618ac70df0
回复

使用道具 举报

🔗
林微熙 2014-7-10 07:20:11 | 只看该作者
全局:
【解题思路】BFS
【时间复杂度】o(n)
【空间复杂度】o(n)
【gist link】https://gist.github.com/hilda8519/ddf4f88a839401471697
回复

使用道具 举报

🔗
Neal 2014-7-10 09:14:58 | 只看该作者
全局:
【解题思路】BFS
【时间复杂度】o(n)
【空间复杂度】o(n)
【gist link】https://gist.github.com/nealhu/ff50192e189ae3f01e4f
回复

使用道具 举报

🔗
jason51122 2014-7-10 12:45:45 | 只看该作者
全局:
【解题思路】BFS
【时间复杂度】O(V+E)
【空间复杂度】O(V)
【gist link】https://gist.github.com/jason51122/57c2fa7f36cee4d0c307
回复

使用道具 举报

🔗
grassgigi 2014-7-10 12:56:15 | 只看该作者
全局:
【解题思路】
BFS

【时间复杂度】
O(V+E)

【空间复杂度】
O(V+E)

【gist link】
https://gist.github.com/chrislukkk/e37504aa6c3dc21b49fe
回复

使用道具 举报

🔗
chouclee 2014-7-11 20:22:32 | 只看该作者
全局:
【解题思路】
DFS
【时间复杂度】
O(V+E)
【空间复杂度】
O(V+E)
【gist link】
https://gist.github.com/chouclee/60c5d74e6fa206e656c7
回复

使用道具 举报

全局:
【解题思路】
BFS

【时间复杂度】
O(v+e)


【空间复杂度】
O(v)


【gist link】
https://gist.github.com/happyWinner/cd03c98bdf6ca5a5c4ec

回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表