给定一个只包含一位数的数组，假设我们站在第一个索引处，我们需要使用最少的步骤数到达数组的末尾，在一个步骤中，我们可以跳转到相邻的索引或跳转到具有相同值的位置。 换句话说，如果我们在索引i，那么在一个步骤中，你可以达到，arr[i-1]或arr[i+1]或arr[K]，这样arr[K]=arr[i]（arr[K]的值与arr[i]相同） 例如：
null
Input : arr[] = {5, 4, 2, 5, 0}Output : 2Explanation : 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 : 5Explanation : Total 5 step required.0(0) -> 0(12) -> 6(11) -> 6(6) -> 7(7) ->(18) (inside parenthesis indices are shown)
这个问题可以通过使用 BFS 我们可以将给定的数组看作是未加权的图，其中每个顶点具有两个边到下一个数组和前一个数组元素，并且更多的边具有相同值的数组元素。现在，为了快速处理第三类边，我们保留了10条 载体 存储0到9位的所有索引。在上面的示例中，对应于0的向量将存储[0,12]，其中在给定数组中出现了0。 使用另一个布尔数组，这样我们就不会多次访问同一个索引。由于我们使用BFS，BFS逐级进行，因此保证了最佳最小步数。
C++
// C++ program to find minimum jumps to reach end // of array #include <bits/stdc++.h> 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(arr,N): # 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 ( 1 ,N): 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#
// 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(arr,N) { // 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> |
输出：
5
本文由 乌特卡什·特里维迪 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用 写极客。组织 或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
