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

Question

我正在尝试编写一个高效的算法来计算一个 pawn 退出数组所需的跳跃次数。假设我们有一个数组，对于数组中的每个元素，如果 array[k] = n 那么 array[k] 等于 array[k + n];

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

最初棋子位于数组[0]，第一次跳跃时它从数组[0]移动到数组[2]，因为0 + 数组[0]等于2。第二次跳跃时，棋子移动从 A[2] 到 A[1] 因为 2 + A[2] = 1；在第三次跳跃时，棋子从 A[1] 移动到 A[4]，因为 1 + A[1] = 4；在第四次跳跃中，棋子跳出了阵列。对于此测试用例，它 returns 4。

如果棋子跳不出阵我们return -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

如果 pawn 总是准确地跳跃给定数组中指定的数量，则可以在线性时间内找到离开数组所需的移动次数。

在每次跳跃之前，可以检查pawn当前位置之前是否被访问过。如果是，则意味着存在一个 pawn 无法退出的循环，因此 return -1。否则继续跳跃，return 最终计数。

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;
}

现在在给定时间，如果棋子可以在 [1, jumps[position]] 之间的任意位置跳跃，您可以使用动态编程来有效地找到所需的移动次数。

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

How do I find efficiently, the number of jumps it will take for an element to jump out of an array?

javascript

arrays

arr