c++ - 模拟数组/向量中的棋子跳跃

Question

假设我们有一个大小为 N 的向量
A。Pawn 从 A[0] 开始并跳转到 A[0] 指向的索引：A[0] 的值告诉它必须如何移动，即：如果索引为 6。

A[6]=1 -> move 1 to the right, to A[7]

A[6]=-2 -> move 2 to the left, to A[4]

如果 pawn 到达最后一个索引并且是 positive，则 pawn 超出范围示例：

A  0 | 1 | 1 | 3 | 4 | 5
   2  -1   4   1   4   2

每个元素包含的最大值为 1 000 000 且 N < 1 000 000。函数应返回 4。

任务：编写一个函数int arrayJmp ( const vector<int> &A )，如果 pawn 永远不会离开表，则返回 -1；如果它会跳出数组，则返回移动次数。最坏情况的复杂度应该是 O(n)。你可以在下面找到我的答案。这是正确的吗？

Answer 1

#include <algorithm>

void myfunction (int &i) {  // function:
  i=1000001;
}

int arrayJmp ( const vector<int> &A ) {
    int N=A.size();

  vector<int> indexes;
  for_each (indexes.begin(), indexes.end(), myfunction);
  int index=0;

  while(std::find(indexes.begin(), indexes.end(), index) == indexes.end()){
    indexes.push_back(index);

    index+=A[index];
    if (index==(N-1)&&A[index]>0) return indexes.size()+1;
  }

  return -1;
}

Answer 2

您是否可以互换使用“表”、“数组”和“向量”？

请求很简单：

if ((i = array[  index ]) < 0 || i >= sizeof(array)) ;//out of bounds

otherwise i is within bounds

Answer 3

#include <iostream>
#include <vector>

int jump_array(const std::vector<int>& vector)
{
    int index = 0;
    int old_index = 0;
    int size = vector.size();
    int count = 0;
    do
    {
        old_index = index;
        index += vector[index];
        if(count >= size)
        {
            return -1;
        }
        else
        {
            count++;
        }
    }
    while(index < size);

    return vector[old_index];
}

int main()
{
    std::vector<int> vector;
    vector.push_back(2);
    vector.push_back(-1);
    vector.push_back(4);
    vector.push_back(1);
    vector.push_back(4);
    vector.push_back(2);

    std::cout << jump_array(vector);
}