如何有效地找到元素跳出数组所需的跳转次数？

Question

我正在尝试编写一种有效的算法，该算法将发现典当退出数组所需的跳跃数量。假设我们给我们一个数组，对于数组中的每个元素，如果数组[k] = n，那么数组[k]等于array [k + n];

例如，我们有此数组[2,3，-1,1,3]。

最初，典当在数组[0]，在第一次跳转时，它从阵列[0]移动到数组[2]，因为0 + array [0]等于2。在第二个跳转时，典当从[2]移动[1]是因为2 + a [2] = 1;在第三跳时，典当从[1]移至[4]，因为1 + a [1] = 4; 在第四跳时，典当跳出了阵列。该测试案例返回4。

如果典当无法跳出数组，我们将返回-1；

以下是我为此问题编写的算法，它适用于一些测试用例，但未能通过大型测试用例。如何使该算法更有效。

function jumpOut(A) { 
  let start = 0;
  let end = A.length - 1
  let pawn = 0;
  
  while (start < end){
    pawn= start + A[start]  
    start++;
  }
  
  if(pawn === end){
    return pawn
  }
  
  return -1;
} 

Answer 1

如果典当始终在给定数组中指定的量始终跳跃，则可以在线性时间内找到离开数组所需的移动次数。

在每次跳跃之前，您可以检查先前访问的当前位置。如果是，那意味着存在典当无法退出的循环-1。否则，继续跳跃并返回最终计数。

function getNumRequiredMoves(jumps) {
  // Remember the positions that have been visited
  let isVisited = Array(jumps.length).fill(false);
  // Position of the pawn
  let position = 0;
  // Final result
  let numMoves = 0;

  while (position >= 0 && position < jumps.length) {
    if (isVisited[position]) {
      // This position has been visited before
      return -1;
    }
    // Mark this position as visited
    isVisited[position] = true;
    // Jump
    position += jumps[position];
    // Increment the jump counter
    ++numMoves;
  }

  return numMoves;
}

现在在给定的时间，如果pawn可以在[1，跳跃[position]]之间跳跃，则可以使用动态编程有效地找到所需的动作数量。