面试谜题：跳跃游戏

Question

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

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

示例：给定数组 A = {2,3,1,1,4} 到达末尾（索引列表）的可能方式为

1. 0,2,3,4 > （跳转 2 到索引 2，然后跳转 1 到索引 3，然后跳转 1 到索引 4）
2. 0,1,4 （跳转 1 到索引 1，然后跳转 3 到索引 4）

由于第二个解决方案有只有 2 次跳跃最佳结果。

Answer 1

概述

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

考虑 a[i+1] 到 a[a[i] + i] 中的所有候选“跳转元素”。对于索引 e 处的每个此类元素，计算 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] 显示到达数组 A 中的索引 i 所需的最小步数。你的答案当然是在 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 是数组内的最大值。

请注意，

我保留了这个答案，但奇琴的贪婪算法是正确的并且更有效。

Answer 3

从数组构造一个有向图。例如： i->j if |ij|<=x[i] （基本上，如果您可以一跳从 i 移动到 j，则 i->j 作为图中的边）。现在，找到从第一个节点到最后一个节点的最短路径。

FWIW，您可以使用 Dijkstra 算法来找到最短路线。复杂度为 O( | E | + | V | log | V | )。自从 |电子| < n^2，这变成了 O(n^2)。

Answer 4

我们可以计算远索引以跳跃最大值，并且在两者之间如果任何索引值大于远索引值，我们将更新远索引值。

简单的 O(n) 时间复杂度解决方案

public boolean canJump(int[] nums) {
    int far = 0;
    for(int i = 0; i<nums.length; i++){
        if(i <= far){
            far = Math.max(far, i+nums[i]);
        }
        else{
            return false;
        }
    }
    return true;
}

Answer 5

从左（结束）开始......遍历直到数字与索引相同，使用这些数字中的最大值。例如，如果列表是

   list:  2738|4|6927
   index: 0123|4|5678

一旦您从该数字开始重复上述步骤，直到您到达最右边。

273846927
000001234

如果您找不到与索引匹配的内容，请使用索引最远且值大于索引的数字。在本例中为 7。（因为索引很快就会大于数字，所以您可能只计算 9 个索引）

Answer 6

基本思想：

通过查找所有可以最后跳转到目标元素的数组元素（所有 i 使得 A[i ] >= 目标 - i)。

将每个这样的 i 视为新目标并找到到达它的路径（递归地）。

选择找到的最小长度路径，附加目标，返回。

python 中的简单示例：

ls1 = [2,3,1,1,4]
ls2 = [4,11,1,1,1,1,1,1,1,1,1,1,1]

# finds the shortest path in ls to the target index tgti
def find_path(ls,tgti):

    # if the target is the first element in the array, return it's index.
    if tgti<= 0:
        return [0]

    # for each 0 <= i < tgti, if it it possible to reach
    # tgti from i (ls[i] <= >= tgti-i) then find the path to i

    sub_paths = [find_path(ls,i) for i in range(tgti-1,-1,-1) if ls[i] >= tgti-i]

    # find the minimum length path in sub_paths

    min_res = sub_paths[0]
    for p in sub_paths:
        if len(p) < len(min_res):
            min_res = p

    # add current target to the chosen path
    min_res.append(tgti)
    return min_res

print  find_path(ls1,len(ls1)-1)
print  find_path(ls2,len(ls2)-1)

>>>[0, 1, 4]
>>>[0, 1, 12]