一亩三分地论坛

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

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

发一个whitepages的OA,Dragon Game类似leet code jump game2

[复制链接] |试试Instant~ |关注本帖
Crius康 发表于 2015-12-30 12:11:25 | 显示全部楼层 |阅读模式

() @ - -  |

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

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

x
给一个数组,每一个数表示下一次能走的最大步长,求一条走出这个数组的最短路径,例如:
[5,6,0,4,2,4,1,0,0,4],返回[0,5,9]
用dfs 和slide window都能做出,可是我有两个testcase过不了然后直接悲剧了
740919074 发表于 2015-12-30 13:04:42 | 显示全部楼层
dfs超时,用贪心就好了
回复 支持 反对

使用道具 举报

cucucucu123 发表于 2016-1-16 07:54:09 | 显示全部楼层
740919074 发表于 2015-12-30 13:04. visit 1point3acres.com for more.
dfs超时,用贪心就好了

贪心是O(N^2) 的吗
回复 支持 反对

使用道具 举报

wangshuokevin 发表于 2016-1-23 03:53:41 | 显示全部楼层
楼主的code还有吗》学习一下
回复 支持 反对

使用道具 举报

cucucucu123 发表于 2016-1-23 06:09:19 | 显示全部楼层
wangshuokevin 发表于 2016-1-23 03:53
楼主的code还有吗》学习一下

我写了一下,用leetcode原题的方法基础上加一个数组做dp就好了。
稍微解释一下,这个dp数组的含义是,每一个位置的prev index。
然后复杂度应该还是O(n)的样子
回复 支持 反对

使用道具 举报

aiweiwei 发表于 2016-2-8 04:00:04 | 显示全部楼层
请问楼主用什么语言写的
.鐣欏璁哄潧-涓浜-涓夊垎鍦
然后有后续吗。。
回复 支持 反对

使用道具 举报

joseph1992 发表于 2016-2-8 08:47:14 | 显示全部楼层
这个我觉得用greedy O(n)就能做出来, 可网上的solution全是dp 和 naive, 时间是O(n^2),看不懂为什么不提greedy. 1point 3acres 璁哄潧

回复 支持 反对

使用道具 举报

nevermor 发表于 2016-2-8 09:14:01 | 显示全部楼层
joseph1992 发表于 2016-2-8 08:47
这个我觉得用greedy O(n)就能做出来, 可网上的solution全是dp 和 naive, 时间是O(n^2),看不懂为什么不提gre ...
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
求解贪心怎么做
回复 支持 反对

使用道具 举报

joseph1992 发表于 2016-2-8 13:26:15 | 显示全部楼层
一顿操作还是剩一个test case没过,心好累. 第16个测试永远过不去. code 就不发了怕误导别人. 我说一下想法吧: 就是在初始点能到达的范围内找能到达最远element的element, 找到后再根据这element的范围找下一个类似的点, 这些element组一起就是minimum path. 我查了2小时都查不出那个test case为什么不过,就提前交了. 能发一下全都通过的code吗, 好像知道第16个是干嘛的
回复 支持 反对

使用道具 举报

aiweiwei 发表于 2016-2-8 15:00:30 | 显示全部楼层
joseph1992 发表于 2016-2-8 13:26. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
一顿操作还是剩一个test case没过,心好累. 第16个测试永远过不去. code 就不发了怕误导别人. 我说一下想法 ...

谢谢面经,已经很不错了。 请问你有后续吗?
回复 支持 反对

使用道具 举报

guaitt 发表于 2016-2-9 01:32:18 | 显示全部楼层
aiweiwei 发表于 2016-2-8 15:00
谢谢面经,已经很不错了。 请问你有后续吗?

我12月做完oa,之后hr问我对哪些组感兴趣,回复后一个月没消息,发邮件询问后直接被拒,醉了
回复 支持 反对

使用道具 举报

gotta0625 发表于 2016-2-9 02:59:36 | 显示全部楼层
正准备做OA 大神们请问返回的也要是一个数组吗 还是一个list 求解答
回复 支持 反对

使用道具 举报

antonioybw 发表于 2016-2-9 06:35:00 | 显示全部楼层
joseph1992 发表于 2016-2-8 13:26
一顿操作还是剩一个test case没过,心好累. 第16个测试永远过不去. code 就不发了怕误导别人. 我说一下想法 ...

你描述的这个是不是有点没有讲完或者讲清楚?   因为每次都找最远的点的话,可能到后面是跳不到最后一个数的呀。 网上的solution有greedy的但是要稍微处理下,不是只找最远的那个点这么简单吧
回复 支持 反对

使用道具 举报

sunnywrq 发表于 2016-3-16 00:30:36 | 显示全部楼层
joseph1992 发表于 2016-2-8 13:26
一顿操作还是剩一个test case没过,心好累. 第16个测试永远过不去. code 就不发了怕误导别人. 我说一下想法 ...
.1point3acres缃
能不能求代码。。正在做OA。。。。。心里虚。。。。。求助攻啊啊啊啊

补充内容 (2016-3-16 00:31):
137025147@qq.com 求助攻!!!!

补充内容 (2016-3-16 00:31):
. visit 1point3acres.com for more.137025147@qq.com 求助攻!!!
回复 支持 反对

使用道具 举报

linlin1990 发表于 2016-4-14 07:25:53 | 显示全部楼层
求问你们是面intern还是fulltime呢
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-11 14:28

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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