制約の下で配列の最後に到達するための最小ステップ

1 桁の数値を含む配列がある場合、最初のインデックスに立っていると仮定すると、最小限のステップ数を使用して配列の末尾に到達する必要があり、1 ステップで隣接するインデックスにジャンプしたり、同じ値を持つ位置にジャンプしたりできます。
言い換えると、インデックス i にある場合、arr[K] = arr[i] (arr[K] の値は arr[i] と同じ) となるように、1 ステップで arr[i-1]、arr[i+1]、または arr[K] に到達できます。

例:

Input : arr[] = {5 4 2 5 0} Output : 2 Explanation : Total 2 step required. We start from 5(0) in first step jump to next 5 and in second step we move to value 0 (End of arr[]). Input : arr[] = [0 1 2 3 4 5 6 7 5 4 3 6 0 1 2 3 4 5 7] Output : 5 Explanation : Total 5 step required. 0(0) -> 0(12) -> 6(11) -> 6(6) -> 7(7) -> (18) (inside parenthesis indices are shown)

この問題は次を使用して解決できます BFS 。与えられた配列を、すべての頂点が前後の配列要素への 2 つのエッジと、同じ値を持つ配列要素へのさらに多くのエッジを持つ重み付けされていないグラフとみなすことができます。ここで、3 番目のタイプのエッジを高速に処理するために、10 を維持します。ベクトルこれには、0 ～ 9 の数字が存在するすべてのインデックスが格納されます。上記の例では、0 に対応するベクトルは、指定された配列内で 0 が発生した [0 12] 2 つのインデックスを格納します。

同じインデックスに複数回アクセスしないように、別のブール配列が使用されます。 BFS を使用しており、BFS はレベルごとに進行するため、最適な最小ステップが保証されます。

ハッシュマップJava

実装：

C++

// C++ program to find minimum jumps to reach end // of array #include    using namespace std; // Method returns minimum step to reach end of array int getMinStepToReachEnd(int arr[] int N) {  // visit boolean array checks whether current index  // is previously visited  bool visit[N];  // distance array stores distance of current  // index from starting index  int distance[N];  // digit vector stores indices where a  // particular number resides  vector<int> digit[10];  // In starting all index are unvisited  memset(visit false sizeof(visit));  // storing indices of each number in digit vector  for (int i = 1; i < N; i++)  digit[arr[i]].push_back(i);  // for starting index distance will be zero  distance[0] = 0;  visit[0] = true;  // Creating a queue and inserting index 0.  queue<int> q;  q.push(0);  // loop until queue in not empty  while(!q.empty())  {  // Get an item from queue q.  int idx = q.front(); q.pop();  // If we reached to last index break from loop  if (idx == N-1)  break;  // Find value of dequeued index  int d = arr[idx];  // looping for all indices with value as d.  for (int i = 0; i<digit[d].size(); i++)  {  int nextidx = digit[d][i];  if (!visit[nextidx])  {  visit[nextidx] = true;  q.push(nextidx);  // update the distance of this nextidx  distance[nextidx] = distance[idx] + 1;  }  }  // clear all indices for digit d because all  // of them are processed  digit[d].clear();  // checking condition for previous index  if (idx-1 >= 0 && !visit[idx - 1])  {  visit[idx - 1] = true;  q.push(idx - 1);  distance[idx - 1] = distance[idx] + 1;  }  // checking condition for next index  if (idx + 1 < N && !visit[idx + 1])  {  visit[idx + 1] = true;  q.push(idx + 1);  distance[idx + 1] = distance[idx] + 1;  }  }  // N-1th position has the final result  return distance[N - 1]; } // driver code to test above methods int main() {  int arr[] = {0 1 2 3 4 5 6 7 5  4 3 6 0 1 2 3 4 5 7};  int N = sizeof(arr) / sizeof(int);  cout << getMinStepToReachEnd(arr N);  return 0; }

Java

// Java program to find minimum jumps  // to reach end of array import java.util.*; class GFG { // Method returns minimum step  // to reach end of array static int getMinStepToReachEnd(int arr[]   int N) {  // visit boolean array checks whether   // current index is previously visited  boolean []visit = new boolean[N];  // distance array stores distance of   // current index from starting index  int []distance = new int[N];  // digit vector stores indices where a  // particular number resides  Vector<Integer> []digit = new Vector[10];  for(int i = 0; i < 10; i++)  digit[i] = new Vector<>();  // In starting all index are unvisited  for(int i = 0; i < N; i++)  visit[i] = false;  // storing indices of each number  // in digit vector  for (int i = 1; i < N; i++)  digit[arr[i]].add(i);  // for starting index distance will be zero  distance[0] = 0;  visit[0] = true;  // Creating a queue and inserting index 0.  Queue<Integer> q = new LinkedList<>();  q.add(0);  // loop until queue in not empty  while(!q.isEmpty())  {  // Get an item from queue q.  int idx = q.peek();   q.remove();  // If we reached to last   // index break from loop  if (idx == N - 1)  break;  // Find value of dequeued index  int d = arr[idx];  // looping for all indices with value as d.  for (int i = 0; i < digit[d].size(); i++)  {  int nextidx = digit[d].get(i);  if (!visit[nextidx])  {  visit[nextidx] = true;  q.add(nextidx);  // update the distance of this nextidx  distance[nextidx] = distance[idx] + 1;  }  }  // clear all indices for digit d   // because all of them are processed  digit[d].clear();  // checking condition for previous index  if (idx - 1 >= 0 && !visit[idx - 1])  {  visit[idx - 1] = true;  q.add(idx - 1);  distance[idx - 1] = distance[idx] + 1;  }  // checking condition for next index  if (idx + 1 < N && !visit[idx + 1])  {  visit[idx + 1] = true;  q.add(idx + 1);  distance[idx + 1] = distance[idx] + 1;  }  }  // N-1th position has the final result  return distance[N - 1]; } // Driver Code public static void main(String []args) {  int arr[] = {0 1 2 3 4 5 6 7 5  4 3 6 0 1 2 3 4 5 7};  int N = arr.length;  System.out.println(getMinStepToReachEnd(arr N)); } } // This code is contributed by 29AjayKumar

Python3

# Python 3 program to find minimum jumps to reach end# of array # Method returns minimum step to reach end of array def getMinStepToReachEnd(arrN): # visit boolean array checks whether current index # is previously visited visit = [False for i in range(N)] # distance array stores distance of current # index from starting index distance = [0 for i in range(N)] # digit vector stores indices where a # particular number resides digit = [[0 for i in range(N)] for j in range(10)] # storing indices of each number in digit vector for i in range(1N): digit[arr[i]].append(i) # for starting index distance will be zero distance[0] = 0 visit[0] = True # Creating a queue and inserting index 0. q = [] q.append(0) # loop until queue in not empty while(len(q)> 0): # Get an item from queue q. idx = q[0] q.remove(q[0]) # If we reached to last index break from loop if (idx == N-1): break # Find value of dequeued index d = arr[idx] # looping for all indices with value as d. for i in range(len(digit[d])): nextidx = digit[d][i] if (visit[nextidx] == False): visit[nextidx] = True q.append(nextidx) # update the distance of this nextidx distance[nextidx] = distance[idx] + 1 # clear all indices for digit d because all # of them are processed # checking condition for previous index if (idx-1 >= 0 and visit[idx - 1] == False): visit[idx - 1] = True q.append(idx - 1) distance[idx - 1] = distance[idx] + 1 # checking condition for next index if (idx + 1 < N and visit[idx + 1] == False): visit[idx + 1] = True q.append(idx + 1) distance[idx + 1] = distance[idx] + 1 # N-1th position has the final result return distance[N - 1] # driver code to test above methods if __name__ == '__main__': arr = [0 1 2 3 4 5 6 7 5 4 3 6 0 1 2 3 4 5 7] N = len(arr) print(getMinStepToReachEnd(arr N)) # This code is contributed by # Surendra_Gangwar

// C# program to find minimum jumps  // to reach end of array  using System; using System.Collections.Generic; class GFG { // Method returns minimum step  // to reach end of array static int getMinStepToReachEnd(int []arr   int N) {  // visit boolean array checks whether   // current index is previously visited  bool []visit = new bool[N];  // distance array stores distance of   // current index from starting index  int []distance = new int[N];  // digit vector stores indices where a  // particular number resides  List<int> []digit = new List<int>[10];  for(int i = 0; i < 10; i++)  digit[i] = new List<int>();  // In starting all index are unvisited  for(int i = 0; i < N; i++)  visit[i] = false;  // storing indices of each number  // in digit vector  for (int i = 1; i < N; i++)  digit[arr[i]].Add(i);  // for starting index distance will be zero  distance[0] = 0;  visit[0] = true;  // Creating a queue and inserting index 0.  Queue<int> q = new Queue<int>();  q.Enqueue(0);  // loop until queue in not empty  while(q.Count != 0)  {  // Get an item from queue q.  int idx = q.Peek();   q.Dequeue();  // If we reached to last   // index break from loop  if (idx == N - 1)  break;  // Find value of dequeued index  int d = arr[idx];  // looping for all indices with value as d.  for (int i = 0; i < digit[d].Count; i++)  {  int nextidx = digit[d][i];  if (!visit[nextidx])  {  visit[nextidx] = true;  q.Enqueue(nextidx);  // update the distance of this nextidx  distance[nextidx] = distance[idx] + 1;  }  }  // clear all indices for digit d   // because all of them are processed  digit[d].Clear();  // checking condition for previous index  if (idx - 1 >= 0 && !visit[idx - 1])  {  visit[idx - 1] = true;  q.Enqueue(idx - 1);  distance[idx - 1] = distance[idx] + 1;  }  // checking condition for next index  if (idx + 1 < N && !visit[idx + 1])  {  visit[idx + 1] = true;  q.Enqueue(idx + 1);  distance[idx + 1] = distance[idx] + 1;  }  }  // N-1th position has the final result  return distance[N - 1]; } // Driver Code public static void Main(String []args) {  int []arr = {0 1 2 3 4 5 6 7 5  4 3 6 0 1 2 3 4 5 7};  int N = arr.Length;  Console.WriteLine(getMinStepToReachEnd(arr N)); } } // This code is contributed by PrinciRaj1992

JavaScript

<script> // Javascript program to find minimum jumps  // to reach end of array // Method returns minimum step  // to reach end of array function getMinStepToReachEnd(arrN) {  // visit boolean array checks whether   // current index is previously visited  let visit = new Array(N);    // distance array stores distance of   // current index from starting index  let distance = new Array(N);    // digit vector stores indices where a  // particular number resides  let digit = new Array(10);  for(let i = 0; i < 10; i++)  digit[i] = [];    // In starting all index are unvisited  for(let i = 0; i < N; i++)  visit[i] = false;    // storing indices of each number  // in digit vector  for (let i = 1; i < N; i++)  digit[arr[i]].push(i);    // for starting index distance will be zero  distance[0] = 0;  visit[0] = true;    // Creating a queue and inserting index 0.  let q = [];  q.push(0);    // loop until queue in not empty  while(q.length!=0)  {  // Get an item from queue q.  let idx = q.shift();       // If we reached to last   // index break from loop  if (idx == N - 1)  break;    // Find value of dequeued index  let d = arr[idx];    // looping for all indices with value as d.  for (let i = 0; i < digit[d].length; i++)  {  let nextidx = digit[d][i];  if (!visit[nextidx])  {  visit[nextidx] = true;  q.push(nextidx);    // update the distance of this nextidx  distance[nextidx] = distance[idx] + 1;  }  }    // clear all indices for digit d   // because all of them are processed  digit[d]=[];    // checking condition for previous index  if (idx - 1 >= 0 && !visit[idx - 1])  {  visit[idx - 1] = true;  q.push(idx - 1);  distance[idx - 1] = distance[idx] + 1;  }    // checking condition for next index  if (idx + 1 < N && !visit[idx + 1])  {  visit[idx + 1] = true;  q.push(idx + 1);  distance[idx + 1] = distance[idx] + 1;  }  }    // N-1th position has the final result  return distance[N - 1]; } // Driver Code let arr=[0 1 2 3 4 5 6 7 5  4 3 6 0 1 2 3 4 5 7]; let N = arr.length; document.write(getMinStepToReachEnd(arr N));  // This code is contributed by rag2127 </script>

出力

時間計算量: O(N) ここで、N は配列内の要素の数です。

空間の複雑さ: O(N) ここで、N は配列内の要素の数です。サイズ N の距離および訪問配列と、配列のインデックスを格納するサイズ N のキューを使用しています。

文字列値