采访拼图:跳跃游戏

Question

跳跃游戏:给定一个数组,从第一个元素开始,通过跳跃到达最后一个元素.跳转长度最多可以是数组中当前位置的值.最佳结果是当您以最小跳跃次数达到目标时.

什么是找到最佳结果的算法？

一个例子:给定数组A = {2,3,1,1,4}到达结尾的可能方式(索引列表)是

1. 0,2,3,4(跳2到索引2,然后跳1到索引3然后1到索引4)
2. 0,1,4(跳转1到索引1,然后跳转到索引4)

由于第二种解决方案只有2次跳跃,因此是最佳结果.

Answer 1

概观

给定数组a和当前位置的索引i,重复以下操作直到到达最后一个元素.

考虑所有候选"跳转到元素" a[i+1]来a[a[i] + i].对于index处的每个这样的元素e,calculate v= a[e]+ e.如果其中一个元素是最后一个元素,则跳转到最后一个元素.否则,跳转到具有最大值的元素v.

更简单地说,触手可及的元素,寻找能让你在下一次跳跃中走得最远的元素.我们知道这个选择x是正确的,因为与y你可以跳转到的每个其他元素相比,可到达的元素是可以到达的元素y的子集x(除了来自向后跳转的元素,这显然是错误的选择).

该算法在O(n)中运行,因为每个元素只需要考虑一次(可以跳过被认为是第二次的元素).

例

考虑一系列值a,i指标,以及索引和值的总和v.

i ->  0   1   2   3   4   5   6   7   8   9  10  11  12
a -> [4, 11,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1]
v ->  4  12   3   4   5   6   7   8   9  10  11  12  13

从索引0开始,考虑接下来的4个元素.找到最大的那个v.该元素位于索引1处,因此跳转到1.现在考虑接下来的11个元素.目标是触手可及的,所以跳到目标.

演示

请参阅此处或此处的代码.

Answer 2

动态编程.

想象一下,您有一个数组B,其中B[i]显示了i在数组中达到索引所需的最小步数A.你的回答当然是B[n],因为A拥有n的元素和指数从1开始假设C[i]=j意味着你从索引j跃升至索引i(这是恢复后所采取的路径)

所以,算法如下:

set B[i] to infinity for all i
B[1] = 0;                    <-- zero steps to reach B[1]
for i = 1 to n-1             <-- Each step updates possible jumps from A[i]
    for j = 1 to A[i]        <-- Possible jump sizes are 1, 2, ..., A[i]
        if i+j > n           <-- Array boundary check
            break
        if B[i+j] > B[i]+1   <-- If this path to B[i+j] was shorter than previous
            B[i+j] = B[i]+1  <-- Keep the shortest path value
            C[i+j] = i       <-- Keep the path itself

所需的跳跃次数是B[n].需要采取的路径是:

1 -> C[1] -> C[C[1]] -> C[C[C[1]]] -> ... -> n

哪个可以通过简单的循环恢复.

该算法具有O(min(k,n)*n)时间复杂度和O(n)空间复杂度.n是元素的数量,A并且k是数组内的最大值.

注意

我保持这个答案,但是cheeken的贪婪算法是正确的,更有效率.

Answer 3

从数组构造有向图.例如:i-> j if | ij | <= x [i](基本上,如果你可以在一跳中从i移动到j,则i-> j作为图中的边缘).现在,找到从第一个节点到最后一个节点的最短路径.

FWIW,您可以使用Dijkstra的算法,以便找到最短的路线.复杂度为O(| E | + | V | log | V |).自| E | <n ^ 2,这变为O(n ^ 2).