一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 882|回复: 19
收起左侧

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

[复制链接] |试试Instant~ |关注本帖
wrj5518 发表于 2014-7-6 20:51:56 | 显示全部楼层 |阅读模式

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

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、任何未尽之处,欢迎回报名帖提问,我会进一步作出修改。



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
回复 支持 反对

使用道具 举报

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
回复 支持 反对

使用道具 举报

头像被屏蔽
serolins 发表于 2014-7-11 07:00:03 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复 支持 反对

使用道具 举报

chouclee 发表于 2014-7-11 20:22:32 | 显示全部楼层
【解题思路】
DFS
【时间复杂度】
O(V+E)
【空间复杂度】
O(V+E)
【gist link】
https://gist.github.com/chouclee/60c5d74e6fa206e656c7
回复 支持 反对

使用道具 举报

圆梦梦剧场 发表于 2014-7-11 22:34:55 | 显示全部楼层
【解题思路】
BFS

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


【空间复杂度】
O(v)


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

回复 支持 反对

使用道具 举报

ivycheung1208 发表于 2014-7-12 05:17:40 | 显示全部楼层
【解题思路】
用DFS递归遍历直到访问到目标节点或无连通路径……
研究了半天肿么表示graph真是弱爆了=。=最后终于在GeeksforGeeks上找到些不错的栗子 喵
【时间复杂度】
V(O+E)
【空间复杂度】
V(O+E)
【gist link】
https://gist.github.com/fe02d53a80a5684422da
回复 支持 反对

使用道具 举报

兰橘清檬 发表于 2014-7-13 06:36:28 | 显示全部楼层
【解题思路】
BFS , DFS
【时间复杂度】
O(n)
【空间复杂度】
O(n)
【gist link】
https://gist.github.com/JoyceeLee/fa095f6e3b3f82d4c83e

ps : 比较 DFS & BFS
回复 支持 反对

使用道具 举报

wilbert 发表于 2014-7-14 05:25:51 | 显示全部楼层

【解题思路】
BFS
【时间复杂度】
O(V+E)
【空间复杂度】
O(V)
【gist link】
https://gist.github.com/iwilbert/fef11bcadca3b1acfa9e
回复 支持 反对

使用道具 举报

jyh橘子 发表于 2014-7-15 13:09:50 | 显示全部楼层
【解题思路】 BFS
【时间复杂度】 O(V+E)
【空间复杂度】 O(V)
【gist link】 https://gist.github.com/jyhjuzi/11fb399098dafe34a3b4
回复 支持 反对

使用道具 举报

renli3000 发表于 2014-7-18 03:23:29 | 显示全部楼层
本帖最后由 renli3000 于 2014-7-18 03:48 编辑

【解题思路】 DFS和BFS都写了一遍, 用hashtable做访问记录
【时间复杂度】 O(N)
【空间复杂度】 O(N)
【gist link】
https://gist.github.com/Noahsark/5b95a325a0b86e58ba0d
回复 支持 反对

使用道具 举报

renli3000 发表于 2014-7-18 03:29:25 | 显示全部楼层
jyh橘子 发表于 2014-7-15 13:09
【解题思路】 BFS
【时间复杂度】 O(V+E)
【空间复杂度】 O(V)

首先 object永远不要用 “==” 比较,最安全的做法是用Object.equal()
其次 不要写类似于“(current.nexts != null && current.nexts.size() != 0)”的表达,即时你知道current.next已经initialize了,NPE的隐患总会有的
回复 支持 反对

使用道具 举报

jyh橘子 发表于 2014-7-18 04:24:18 | 显示全部楼层
renli3000 发表于 2014-7-18 03:29
首先 object永远不要用 “==” 比较,最安全的做法是用Object.equal()
其次 不要写类似于“(current.nex ...

灰常感谢!  
第一条有道理,我以后多注意。但是第二条我不太懂,如果&&应该是前一个成立了才会判断后一个的吧,应该不会有NPE了吧?  希望你给解释一下,谢谢哈~
回复 支持 反对

使用道具 举报

renli3000 发表于 2014-7-18 04:46:24 | 显示全部楼层
jyh橘子 发表于 2014-7-18 04:24
灰常感谢!  
第一条有道理,我以后多注意。但是第二条我不太懂,如果&&应该是前一个成立了才会判断后一 ...

举个例子 计算if(a && b) 时
java会先算 c = a & b 然后是 if(c)
所以b的NPE 是在计算c的时候抛出的
回复 支持 反对

使用道具 举报

jyh橘子 发表于 2014-7-18 05:17:25 | 显示全部楼层
renli3000 发表于 2014-7-18 04:46
举个例子 计算if(a && b) 时
java会先算 c = a & b 然后是 if(c)
所以b的NPE 是在计算c的时候抛出的

Got it !    非常感谢哈,我基础不好,各种不扎实!
回复 支持 反对

使用道具 举报

tonygxxx1212 发表于 2014-7-19 22:12:34 | 显示全部楼层
【解题思路】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
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-8 01:49

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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