c++ - 配列/ベクトルでのポーンジャンプのシミュレーション

Question

サイズNのベクトルAがあると仮定します。
ポーンは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]

ポーンが最後のインデックスに到達し、それが正の場合、ポーンはスコープ外の例になります。

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

各要素に含まれる最大値は1000000で、N <1000000です。関数は4を返す必要があります。

タスク：int arrayJmp ( const vector<int> &A )ポーンがテーブルから出ない場合は-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);
}