b*s
2 楼
array hooper
给一个array,每个元素都是大于等于0的数字,每个数字代表可以向右跳的最大步数。
从第一个元素出发,要跳出数组。跟leetcode的jump gameII差不多,区别在于
1. 这里要求跳出数组,leetcode是要求跳到最后一个元素
2. 如果能跳出数组,给出其中一组最少步数的跳法,如不能跳出,输出failure。
leetcode是只要求给出答案能不能跳到最后
examples:
input: 1, 1 output: 0, 1, out
input: 2, 1, 3, 1, 1 output: 0, 2, out
input: 5, 6, 0, 4, 2, 4, 1, 0, 0, 4 output: 0, 5, 9, out
input: 1, 2, 1, 0, 2 output: failure
我的代码是
def hopper(a):
a.append(0)
path = []
cur = 0
maxCenter = 0
maxRange = 0
for i, n in enumerate(a):
if i > cur:
if i > maxRange:
print "failure"
return
else:
path.append(maxCenter)
cur = maxRange
if i + n > maxRange:
maxCenter = i
maxRange = max(maxRange, i + n)
path.append('out')
print ', '.join(map(str, path))
return
两天后被拒了,求大牛指出我的代码错哪了
给一个array,每个元素都是大于等于0的数字,每个数字代表可以向右跳的最大步数。
从第一个元素出发,要跳出数组。跟leetcode的jump gameII差不多,区别在于
1. 这里要求跳出数组,leetcode是要求跳到最后一个元素
2. 如果能跳出数组,给出其中一组最少步数的跳法,如不能跳出,输出failure。
leetcode是只要求给出答案能不能跳到最后
examples:
input: 1, 1 output: 0, 1, out
input: 2, 1, 3, 1, 1 output: 0, 2, out
input: 5, 6, 0, 4, 2, 4, 1, 0, 0, 4 output: 0, 5, 9, out
input: 1, 2, 1, 0, 2 output: failure
我的代码是
def hopper(a):
a.append(0)
path = []
cur = 0
maxCenter = 0
maxRange = 0
for i, n in enumerate(a):
if i > cur:
if i > maxRange:
print "failure"
return
else:
path.append(maxCenter)
cur = maxRange
if i + n > maxRange:
maxCenter = i
maxRange = max(maxRange, i + n)
path.append('out')
print ', '.join(map(str, path))
return
两天后被拒了,求大牛指出我的代码错哪了
h*a
3 楼
是这样吗?如果是的话,那是不是拍的raw照片都一样,jpg机内加工不同?
u*o
5 楼
面的是whitepage吗? 做过一模一样的coding challenge的题。。。用的是greedy的解
,也被据了。。不知是不是DP更好?
,也被据了。。不知是不是DP更好?
h*1
10 楼
google, baidu
z*e
19 楼
现在看到这种题第一感觉就是dp……
c*2
20 楼
我前天也做了这道题...
然后昨天起来回想自己的思路, 发现了一个bug, 硬着头皮给HR发邮件说明了bug,昨晚
看到这个帖子后感觉他们不会理我了, 结果今天收到邮件说想多聊聊...
然后昨天起来回想自己的思路, 发现了一个bug, 硬着头皮给HR发邮件说明了bug,昨晚
看到这个帖子后感觉他们不会理我了, 结果今天收到邮件说想多聊聊...
w*t
21 楼
greedy for sure does not work.
eg. step 0 -- 1, 3
step 1 -- 100
step 3 -- 1
first to 1 is better than to 3
this is a dp with memorization. should be space o(n), time o(n2), the best I
can come up.
【在 c*******2 的大作中提到】![](/moin_static193/solenoid/img/up.png)
: 我前天也做了这道题...
: 然后昨天起来回想自己的思路, 发现了一个bug, 硬着头皮给HR发邮件说明了bug,昨晚
: 看到这个帖子后感觉他们不会理我了, 结果今天收到邮件说想多聊聊...
eg. step 0 -- 1, 3
step 1 -- 100
step 3 -- 1
first to 1 is better than to 3
this is a dp with memorization. should be space o(n), time o(n2), the best I
can come up.
【在 c*******2 的大作中提到】
![](/moin_static193/solenoid/img/up.png)
: 我前天也做了这道题...
: 然后昨天起来回想自己的思路, 发现了一个bug, 硬着头皮给HR发邮件说明了bug,昨晚
: 看到这个帖子后感觉他们不会理我了, 结果今天收到邮件说想多聊聊...
l*n
22 楼
你理解的greedy有问题,不是每次直接跑最远。
http://stackoverflow.com/questions/9041853/interview-puzzle-jum
I
【在 w**t 的大作中提到】![](/moin_static193/solenoid/img/up.png)
: greedy for sure does not work.
: eg. step 0 -- 1, 3
: step 1 -- 100
: step 3 -- 1
: first to 1 is better than to 3
: this is a dp with memorization. should be space o(n), time o(n2), the best I
: can come up.
http://stackoverflow.com/questions/9041853/interview-puzzle-jum
I
【在 w**t 的大作中提到】
![](/moin_static193/solenoid/img/up.png)
: greedy for sure does not work.
: eg. step 0 -- 1, 3
: step 1 -- 100
: step 3 -- 1
: first to 1 is better than to 3
: this is a dp with memorization. should be space o(n), time o(n2), the best I
: can come up.
b*s
27 楼
我不太懂他那个test的意思
用3 100 1 1 1 1 1 0 作input的话我写的那个greedy出来结果是0, 1, out
【在 l**********o 的大作中提到】![](/moin_static193/solenoid/img/up.png)
: 不仔细看帖就吃亏呀!我也做了这家,在大家之后。交了之后发现bug。。。。
: 这题能O(n) 时间?不可能吧。。。
: bfs 或者 dp 都有解,我用了dp, 完了之后才想到bfs, bfs应该更有效率。
: 我不太熟Python, wzxt 给的例子你test一下试试看。
: array 是 3 100 1 1 1 1 1 0 或者你试试这个 case
:
: ★ 发自iPhone App: ChineseWeb 7.8
用3 100 1 1 1 1 1 0 作input的话我写的那个greedy出来结果是0, 1, out
【在 l**********o 的大作中提到】
![](/moin_static193/solenoid/img/up.png)
: 不仔细看帖就吃亏呀!我也做了这家,在大家之后。交了之后发现bug。。。。
: 这题能O(n) 时间?不可能吧。。。
: bfs 或者 dp 都有解,我用了dp, 完了之后才想到bfs, bfs应该更有效率。
: 我不太熟Python, wzxt 给的例子你test一下试试看。
: array 是 3 100 1 1 1 1 1 0 或者你试试这个 case
:
: ★ 发自iPhone App: ChineseWeb 7.8
C*w
28 楼
greedy不对吧,这题正解是dp啊,O(N)时间解决不了的吧
p*o
32 楼
I think your condition for "failure" is wrong:
if i > cur:
if i > maxRange:
print "failure"
return
e.g., the case that it stops right at the end (i.e., case maxRange == n-1, n
is the size of input array a):
[2,3,1,1,0], which you should output "failure".
the right condition for success should be "maxRange > n-1", strictly greater
. (i.e., "<=" for failure)
based on your code, you can decide fail or success after the loop is
finished, e.g., if (maxRange > len(a)-1) out; else fail
【在 b*********s 的大作中提到】![](/moin_static193/solenoid/img/up.png)
: array hooper
: 给一个array,每个元素都是大于等于0的数字,每个数字代表可以向右跳的最大步数。
: 从第一个元素出发,要跳出数组。跟leetcode的jump gameII差不多,区别在于
: 1. 这里要求跳出数组,leetcode是要求跳到最后一个元素
: 2. 如果能跳出数组,给出其中一组最少步数的跳法,如不能跳出,输出failure。
: leetcode是只要求给出答案能不能跳到最后
: examples:
: input: 1, 1 output: 0, 1, out
: input: 2, 1, 3, 1, 1 output: 0, 2, out
: input: 5, 6, 0, 4, 2, 4, 1, 0, 0, 4 output: 0, 5, 9, out
if i > cur:
if i > maxRange:
print "failure"
return
e.g., the case that it stops right at the end (i.e., case maxRange == n-1, n
is the size of input array a):
[2,3,1,1,0], which you should output "failure".
the right condition for success should be "maxRange > n-1", strictly greater
. (i.e., "<=" for failure)
based on your code, you can decide fail or success after the loop is
finished, e.g., if (maxRange > len(a)-1) out; else fail
【在 b*********s 的大作中提到】
![](/moin_static193/solenoid/img/up.png)
: array hooper
: 给一个array,每个元素都是大于等于0的数字,每个数字代表可以向右跳的最大步数。
: 从第一个元素出发,要跳出数组。跟leetcode的jump gameII差不多,区别在于
: 1. 这里要求跳出数组,leetcode是要求跳到最后一个元素
: 2. 如果能跳出数组,给出其中一组最少步数的跳法,如不能跳出,输出failure。
: leetcode是只要求给出答案能不能跳到最后
: examples:
: input: 1, 1 output: 0, 1, out
: input: 2, 1, 3, 1, 1 output: 0, 2, out
: input: 5, 6, 0, 4, 2, 4, 1, 0, 0, 4 output: 0, 5, 9, out
b*s
33 楼
n
greater
输入是2, 3, 1, 1, 0的时候我的程序没有错,结果是failure
我在最开始的时候往数组最后面加了个0
【在 p****o 的大作中提到】
![](/moin_static193/solenoid/img/up.png)
: I think your condition for "failure" is wrong:
: if i > cur:
: if i > maxRange:
: print "failure"
: return
: e.g., the case that it stops right at the end (i.e., case maxRange == n-1, n
: is the size of input array a):
: [2,3,1,1,0], which you should output "failure".
: the right condition for success should be "maxRange > n-1", strictly greater
: . (i.e., "<=" for failure)
p*o
34 楼
ok, I only had a glimpse on a.append(0), and quickly skip it... :-), have
not written python for quite some time.
then I think it is correct. but personally, I feel it is tricky to append "0
" at the end of input, and also the input has to change. Another
controversial case is the empty input, you will output "out".
Well, maybe the reviewer did not see that "append", or did not think too
much. or there is still something wrong we have not checked out.
Your code is not far from not modifying input, as follows.
def hopper(a):
path = []
cur = 0
maxCenter = 0
maxRange = 0
for i, n in enumerate(a):
if i > cur:
path.append(maxCenter)
cur = maxRange
if i + n > maxRange:
maxCenter = i
maxRange = i + n
if (maxRange <= len(a)):
print "failure"
return
path.append('out')
print ', '.join(map(str, path))
return
【在 b*********s 的大作中提到】![](/moin_static193/solenoid/img/up.png)
:
: n
: greater
: 输入是2, 3, 1, 1, 0的时候我的程序没有错,结果是failure
: 我在最开始的时候往数组最后面加了个0
not written python for quite some time.
then I think it is correct. but personally, I feel it is tricky to append "0
" at the end of input, and also the input has to change. Another
controversial case is the empty input, you will output "out".
Well, maybe the reviewer did not see that "append", or did not think too
much. or there is still something wrong we have not checked out.
Your code is not far from not modifying input, as follows.
def hopper(a):
path = []
cur = 0
maxCenter = 0
maxRange = 0
for i, n in enumerate(a):
if i > cur:
path.append(maxCenter)
cur = maxRange
if i + n > maxRange:
maxCenter = i
maxRange = i + n
if (maxRange <= len(a)):
print "failure"
return
path.append('out')
print ', '.join(map(str, path))
return
【在 b*********s 的大作中提到】
![](/moin_static193/solenoid/img/up.png)
:
: n
: greater
: 输入是2, 3, 1, 1, 0的时候我的程序没有错,结果是failure
: 我在最开始的时候往数组最后面加了个0
b*s
35 楼
"0
You're right. Thanks!
【在 p****o 的大作中提到】
![](/moin_static193/solenoid/img/up.png)
: ok, I only had a glimpse on a.append(0), and quickly skip it... :-), have
: not written python for quite some time.
: then I think it is correct. but personally, I feel it is tricky to append "0
: " at the end of input, and also the input has to change. Another
: controversial case is the empty input, you will output "out".
: Well, maybe the reviewer did not see that "append", or did not think too
: much. or there is still something wrong we have not checked out.
: Your code is not far from not modifying input, as follows.
: def hopper(a):
: path = []
w*e
36 楼
这道题目就是leetcode的jump game II,没有任何区别
【在 b*********s 的大作中提到】![](/moin_static193/solenoid/img/up.png)
: array hooper
: 给一个array,每个元素都是大于等于0的数字,每个数字代表可以向右跳的最大步数。
: 从第一个元素出发,要跳出数组。跟leetcode的jump gameII差不多,区别在于
: 1. 这里要求跳出数组,leetcode是要求跳到最后一个元素
: 2. 如果能跳出数组,给出其中一组最少步数的跳法,如不能跳出,输出failure。
: leetcode是只要求给出答案能不能跳到最后
: examples:
: input: 1, 1 output: 0, 1, out
: input: 2, 1, 3, 1, 1 output: 0, 2, out
: input: 5, 6, 0, 4, 2, 4, 1, 0, 0, 4 output: 0, 5, 9, out
【在 b*********s 的大作中提到】
![](/moin_static193/solenoid/img/up.png)
: array hooper
: 给一个array,每个元素都是大于等于0的数字,每个数字代表可以向右跳的最大步数。
: 从第一个元素出发,要跳出数组。跟leetcode的jump gameII差不多,区别在于
: 1. 这里要求跳出数组,leetcode是要求跳到最后一个元素
: 2. 如果能跳出数组,给出其中一组最少步数的跳法,如不能跳出,输出failure。
: leetcode是只要求给出答案能不能跳到最后
: examples:
: input: 1, 1 output: 0, 1, out
: input: 2, 1, 3, 1, 1 output: 0, 2, out
: input: 5, 6, 0, 4, 2, 4, 1, 0, 0, 4 output: 0, 5, 9, out
z*n
37 楼
lz这个贪心算法不对,给个例子(下标从0开始)。大家验证一下
2 3 100 1 1 1
自己推算,lz的程序会输出 0 1 2 out
【在 b*********s 的大作中提到】![](/moin_static193/solenoid/img/up.png)
: array hooper
: 给一个array,每个元素都是大于等于0的数字,每个数字代表可以向右跳的最大步数。
: 从第一个元素出发,要跳出数组。跟leetcode的jump gameII差不多,区别在于
: 1. 这里要求跳出数组,leetcode是要求跳到最后一个元素
: 2. 如果能跳出数组,给出其中一组最少步数的跳法,如不能跳出,输出failure。
: leetcode是只要求给出答案能不能跳到最后
: examples:
: input: 1, 1 output: 0, 1, out
: input: 2, 1, 3, 1, 1 output: 0, 2, out
: input: 5, 6, 0, 4, 2, 4, 1, 0, 0, 4 output: 0, 5, 9, out
2 3 100 1 1 1
自己推算,lz的程序会输出 0 1 2 out
【在 b*********s 的大作中提到】
![](/moin_static193/solenoid/img/up.png)
: array hooper
: 给一个array,每个元素都是大于等于0的数字,每个数字代表可以向右跳的最大步数。
: 从第一个元素出发,要跳出数组。跟leetcode的jump gameII差不多,区别在于
: 1. 这里要求跳出数组,leetcode是要求跳到最后一个元素
: 2. 如果能跳出数组,给出其中一组最少步数的跳法,如不能跳出,输出failure。
: leetcode是只要求给出答案能不能跳到最后
: examples:
: input: 1, 1 output: 0, 1, out
: input: 2, 1, 3, 1, 1 output: 0, 2, out
: input: 5, 6, 0, 4, 2, 4, 1, 0, 0, 4 output: 0, 5, 9, out
相关阅读
d7000 vs d5200升级大吗?bh google wallet与discover CB能叠加吗?Pro-10好像有货无市bh家的6d w/ EF 24-105mm f/4L 1850算deal 吗数码摄像机有啥推荐的么?富士的色彩真棒Sigma要出X3 FF?amazon BF没发威是不是要等到圣诞大招了?【FS】 Panasonic 35-100 f/2.8, Canon EF100 f/2.0索尼革命残副机的致命弱点ebuckscanon t5, nikon d3300 and Sony a60003星 28寸4k显示器,ebay daily,阿朵喇嘛nikon d7000 vs sony a6000FE1635 试镜Rockwall 灯塔Wow! D810 $2300[FS] Sony A7系列电池手柄给推荐几个500px flickr上拍人物的吧[6D] 70-200 f/4L IS 还是 24-105 f/4L IS?