一亩三分地论坛

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

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

[CareerCup] 【第三轮】8.3-8.9 CareerCup 9.2

[复制链接] |试试Instant~ |关注本帖
林微熙 发表于 2014-8-4 09:01:05 | 显示全部楼层 |阅读模式

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

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

x
本帖最后由 林微熙 于 2014-8-3 18:05 编辑

9.2 Imagine a robot sitting on the upper left comer of an X by Ygrid. The robot can only move in two directions: right and down. How many possible paths are there for the
robot to go from (0, 0) to (X, Y) ?
FOLLOW UP
Imagine certain spots are "off limits," such that the robot cannot step on them.
Design an algorithm to find a path for the robot from the top left to the bottom right.



回复解法可以按照以下格式来


【解题思路】
【时间复杂度】
【空间复杂度】
【gist link】
---------------OPTional,如果觉得test case比较好,欢迎写出来分享----------------------
【test case】

renli3000 发表于 2014-8-6 23:14:10 | 显示全部楼层
【解题思路】DP
【时间复杂度】O(XY)
【空间复杂度】O(XY)
【gist link】
https://gist.github.com/Noahsark/a83c3c51d173164df07c
回复 支持 反对

使用道具 举报

ivycheung1208 发表于 2014-8-7 11:33:17 | 显示全部楼层
【解题思路】
f(x,y) = f(x-1, y) + f(x, y-1)
special cases:
f(0,y) = 1;
f(x,0) = 1;
off-limits spots = 0;
【时间复杂度】
O(XY)
【空间复杂度】
O(XY)
【gist link】
https://gist.github.com/f815ad32ccaefe9f6ded

p.s. function of returning path to be implemented...
回复 支持 反对

使用道具 举报

圆梦梦剧场 发表于 2014-8-8 04:02:17 | 显示全部楼层
【解题思路】
paths[row][currCol] = paths[row - 1][currCol] + paths[row][prevCol];


【时间复杂度】
O(x*y)

【空间复杂度】
O(min(x,y))
Follow up: O(x*y)

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

回复 支持 反对

使用道具 举报

grassgigi 发表于 2014-8-16 14:11:11 | 显示全部楼层
【解题思路】
Totally X+Y Choose X paths
Follow up: Recursion with memorization

【时间复杂度】
O(X*Y)

【空间复杂度】
O(X*Y)

【gist link】
https://gist.github.com/chrislukkk/dd8e7697d5201f773c4c
回复 支持 反对

使用道具 举报

jetfish1900 发表于 2014-9-1 15:52:01 | 显示全部楼层
这道题想请教下各位。答案中的path,add(p)两次是什么意思了?为啥没有成功的情况下,还要再add?谢谢解答。
回复 支持 反对

使用道具 举报

jetfish1900 发表于 2014-9-1 15:54:18 | 显示全部楼层
楼主请问下,这道题的答案看了吗?里面的path,add(p)两次是什么原因了?
回复 支持 反对

使用道具 举报

movefast 发表于 2014-9-4 09:53:19 | 显示全部楼层
【解题思路】
res(x,y) = res(x-1, y) + res(x, y-1); maintain a dp result array and return the last result
【时间复杂度】
O(xy)
【空间复杂度】
O(xy)
【gist link】
https://gist.github.com/movefast/2bf80131abf19db89db1

Test case:
invalid input: null
edge case example: [[0]]
回复 支持 反对

使用道具 举报

movefast 发表于 2014-9-4 10:02:02 | 显示全部楼层
jetfish1900 发表于 2014-9-1 15:54
楼主请问下,这道题的答案看了吗?里面的path,add(p)两次是什么原因了?

啊,看了下CC的这道题答案,发现有点看错题了,我是按leetcode的那道题写的,不过道理是一样的。只是方法不一样,CC答案的方法是recursion,实际也就是dps,但他可没add两次哦,再看一下,没success的时候是remove,因为没success你就要try下一个candidate,所以要把不成功的point remove掉
回复 支持 反对

使用道具 举报

bitcpf 发表于 2014-9-16 23:43:22 | 显示全部楼层
【解题思路】recursion f(x,y) = f(x-1, y) + f(x, y-1), f(0,y) = 1, f(x,0) = 1, f(0,0)=0
off-limits spots = 0;
【时间复杂度】
O(XY)
【空间复杂度】
O(XY)
【gist link】
https://gist.github.com/bitcpf/3d46b096b96d6838f361
回复 支持 反对

使用道具 举报

swx1031 发表于 2014-11-14 13:43:55 | 显示全部楼层
lz,我看了cc的答案,不是很理解,他是怎么记录每条path的?想了好久也没想出来,他只是把点加进去了呀,输出来也不是一条完整的path吧。。何况要输出所有的path。。而且follow up 里的有些点off limits 了,这个又做和理解,是怎么是此案的呢?嗯,我基础比较差,正在努力补,有时候代码看不明吧,请多指教了~
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-6 23:05

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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