问1道array hop的题 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

问1道array hop的题

问1道array hop的题# JobHunting - 待字闺中

j*n2012-05-15 07:05

1 楼

没想明白，这个是DP还是什么？
Start with an array A of positive numbers. Start at index 0. From index i,
you can move to index i+x for any x <= A[i]. The goal is to find the minimum
number of moves needed to get to the end of the array.
更新，面试时候的题目说这个array 只是非负，会有0的情况，跳那就卡死了。
请指教....

p*22012-05-15 07:05

2 楼

minimum
伪greedy

【在 j*****n 的大作中提到】

: 没想明白，这个是DP还是什么？
: Start with an array A of positive numbers. Start at index 0. From index i,
: you can move to index i+x for any x <= A[i]. The goal is to find the minimum
: number of moves needed to get to the end of the array.
: 更新，面试时候的题目说这个array 只是非负，会有0的情况，跳那就卡死了。
: 请指教....

q*y2012-05-15 07:05

3 楼

LeetCode Jump Game II. 从右向左，搞个array S[]记录每一位的最少步数。当前最少
等于min{S[i+1],...S[i+A[i]]}+1。最坏情况O(n^2)。虽然过了online judge。
求更好解法。

p*22012-05-15 07:05

4 楼

这题的正解是O（n）

【在 q***y 的大作中提到】

: LeetCode Jump Game II. 从右向左，搞个array S[]记录每一位的最少步数。当前最少
: 等于min{S[i+1],...S[i+A[i]]}+1。最坏情况O(n^2)。虽然过了online judge。
: 求更好解法。

q*y2012-05-15 07:05

5 楼

所以求解啊

j*n2012-05-15 07:05

6 楼

http://stackoverflow.com/questions/7353813/fastest-algorithm-to
这上面给了个 O(n)，没看懂....

j*e2012-05-15 07:05

7 楼

这个题的trick就是每一步只选i+A[i]最大的位置。
A[0]确定了第一步可以到位置0~A[0],然后从中选出i+A[i]最大的i。
第二步就可以到A[0]+1~i+A[i]，然后从这些位置再选

【在 q***y 的大作中提到】

z*i2012-05-15 07:05

8 楼

注意到如果A[j]能到A[n-1]，那么对任意iA[i]+i>=j，则A[i]=2。例子：输
入数组1 3 4 1 1 1 6。A[4]需要3步道A[6]，A[3]需要4步，A[2]仅需要1步。考虑A[2]
的时候，A[1]+1=4〉2，那么A[1]仅需要两步则可到A[6]。更普遍的情况如下：
A[0] A[3] A[9] A[14] A[22] A[n-1]
5步 4步 3步 2步 1步
我们可假设在A[22]前没有任何元素可仅用1步就到A[n-1]，A[14]前没有任何元素可仅
用2步就到A[n-1]，等等。但是，在A[22]和A[14]间可有元素需2步（3步等等）才能到A
[n-1]。
现在，可以考虑保存从n-1倒溯的时候记录（最小的步数，下标）。在前面的例子中，
先记录（1，22）。当到溯还未到A[14]的时候，记录有（1，22），（2，19），（3，
16）。那么当到溯至A[14]的时候，发现A[14]仅用2步可到A[n-1]，因为A[14]+14〉22
。所以保留（1，22）和（2，14）。
简单的分析，可见时间复杂度是O(nlongn)。感觉复杂度可能为O(n)。

minimum

【在 j*****n 的大作中提到】