الحد الأدنى من الخطوات للوصول إلى نهاية المصفوفة تحت القيود
نظرًا لمصفوفة تحتوي على أرقام مكونة من رقم واحد فقط بافتراض أننا نقف عند الفهرس الأول، نحتاج للوصول إلى نهاية المصفوفة باستخدام الحد الأدنى لعدد الخطوات حيث يمكننا في خطوة واحدة الانتقال إلى المؤشرات المجاورة أو يمكننا الانتقال إلى موضع بنفس القيمة.
بمعنى آخر، إذا كنا في الفهرس i، ففي خطوة واحدة يمكنك الوصول إلى arr[i-1] أو arr[i+1] أو arr[K] بحيث يكون arr[K] = arr[i] (قيمة arr[K] هي نفسها arr[i])
أمثلة:
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) يمكن حل هذه المشكلة باستخدام بفس . يمكننا اعتبار المصفوفة المحددة بمثابة رسم بياني غير مرجح حيث يكون لكل قمة حافتان لعناصر المصفوفة التالية والسابقة والمزيد من الحواف لعناصر المصفوفة بنفس القيم. الآن للمعالجة السريعة للنوع الثالث من الحواف نحتفظ بـ 10 ناقلات التي تخزن جميع المؤشرات التي توجد فيها الأرقام من 0 إلى 9. في المثال أعلاه، سيخزن المتجه المطابق لـ 0 [0 12] مؤشرين حيث حدث 0 في المصفوفة المحددة.
يتم استخدام مصفوفة منطقية أخرى حتى لا نزور نفس الفهرس أكثر من مرة. نظرًا لأننا نستخدم مستوى عائدات BFS وBFS حسب المستوى، يتم ضمان الحد الأدنى من الخطوات المثالية.
تطبيق:
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 ( 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
تعقيد الوقت: O(N) حيث N هو عدد العناصر في المصفوفة
تعقيد الفضاء: O(N) حيث N هو عدد العناصر في المصفوفة نحن نستخدم مسافة وزيارة مصفوفة بالحجم N وقائمة انتظار بالحجم N لتخزين مؤشرات المصفوفة.
إنشاء اختبار
