算法设计（到达终点的最小跳数|S2（O(n)解）） _数据结构

本文概述

C ++
C
Java
python
C#
的PHP

给定一个整数数组, 其中每个元素代表可以从该元素进行的最大步数。编写一个函数以返回到达数组末尾的最小跳转数(从第一个元素开始)。如果一个元素为0, 那么我们将无法遍历该元素。
例子：

Input:arr[] = {1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9} Output: 3 (1-> 3 -> 8 -> 9) Explanation: Jump from 1st element to 2nd element as there is only 1 step, now there are three options 5, 8 or 9. If 8 or 9 is chosen then the end node 9 can be reached. So 3 jumps are made.Input:arr[] = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1} Output: 10 Explanation: In every step a jump is needed so the count of jumps is 10.

在这篇文章中, 将讨论其O(n)解决方案。
实现
要使用的变量：

maxReach变量maxReach始终存储数组中的最大可达索引。
step：可变步长存储我们仍然可以执行的步数(并使用索引0的值进行初始化, 即初始步数)
jump：跳转存储达到该最大可到达位置所需的跳转量。

给定数组arr = 1、3、5、8、9、2、6、7、6、8、9

maxReach= arr [0]; // arr [0] = 1, 因此我们目前可以达到的最大索引为1。
步骤= arr [0]; // arr [0] = 1, 我们仍然可以执行的步数也为1。
跳= 1; //我们总是需要至少跳一次。
现在, 从索引1开始迭代, 上述值将更新如下：

C ++

// C++ program to count Minimum number // of jumps to reach end #include < bits/stdc++.h> using namespace std; int max( int x, int y) { return (x > y) ? x : y; }// Returns minimum number of jumps // to reach arr[n-1] from arr[0] int minJumps( int arr[], int n) {// The number of jumps needed to // reach the starting index is 0 if (n < = 1) return 0; // Return -1 if not possible to jump if (arr[0] == 0) return -1; // initialization // stores all time the maximal // reachable index in the array. int maxReach = arr[0]; // stores the number of steps // we can still take int step = arr[0]; // stores the number of jumps // necessary to reach that maximal // reachable position. int jump = 1; // Start traversing array int i = 1; for (i = 1; i < n; i++) { // Check if we have reached the end of the array if (i == n - 1) return jump; // updating maxReach maxReach = max(maxReach, i + arr[i]); // we use a step to get to the current index step--; // If no further steps left if (step == 0) { // we must have used a jump jump++; // Check if the current index/position or lesser index // is the maximum reach point from the previous indexes if (i > = maxReach) return -1; // re-initialize the steps to the amount // of steps to reach maxReach from position i. step = maxReach - i; } }return -1; }// Driver program to test above function int main() { int arr[] = { 1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9 }; int size = sizeof (arr) / sizeof ( int ); // Calling the minJumps function cout < < ( "Minimum number of jumps to reach end is %d " , minJumps(arr, size)); return 0; } // This code is contributed by // Shashank_Sharma

// C program to count Minimum number // of jumps to reach end #include < stdio.h> int max( int x, int y) { return (x > y) ? x : y; }// Returns minimum number of jumps // to reach arr[n-1] from arr[0] int minJumps( int arr[], int n) {// The number of jumps needed to // reach the starting index is 0 if (n < = 1) return 0; // Return -1 if not possible to jump if (arr[0] == 0) return -1; // initialization // stores all time the maximal // reachable index in the array. int maxReach = arr[0]; // stores the number of steps // we can still take int step = arr[0]; // stores the number of jumps // necessary to reach that maximal // reachable position. int jump = 1; // Start traversing array int i = 1; for (i = 1; i < n; i++) { // Check if we have reached the end of the array if (i == n - 1) return jump; // updating maxReach maxReach = max(maxReach, i + arr[i]); // we use a step to get to the current index step--; // If no further steps left if (step == 0) { // we must have used a jump jump++; // Check if the current index/position or lesser index // is the maximum reach point from the previous indexes if (i > = maxReach) return -1; // re-initialize the steps to the amount // of steps to reach maxReach from position i. step = maxReach - i; } } return -1; }// Driver program to test above function int main() { int arr[] = { 1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9 }; int size = sizeof (arr) / sizeof ( int ); // Calling the minJumps function printf ( "Minimum number of jumps to reach end is %d " , minJumps(arr, size)); return 0; } // This code is contributed by Abhishek Kumar Singh

Java

// Java program to count Minimum number // of jumps to reach endclass Test { static int minJumps( int arr[]) { if (arr.length < = 1 ) return 0 ; // Return -1 if not possible to jump if (arr[ 0 ] == 0 ) return - 1 ; // initialization int maxReach = arr[ 0 ]; int step = arr[ 0 ]; int jump = 1 ; // Start traversing array for ( int i = 1 ; i < arr.length; i++) { // Check if we have reached // the end of the array if (i == arr.length - 1 ) return jump; // updating maxReach maxReach = Math.max(maxReach, i + arr[i]); // we use a step to get to the current index step--; // If no further steps left if (step == 0 ) { // we must have used a jump jump++; // Check if the current // index/position or lesser index // is the maximum reach point // from the previous indexes if (i > = maxReach) return - 1 ; // re-initialize the steps to the amount // of steps to reach maxReach from position i. step = maxReach - i; } }return - 1 ; }// Driver method to test the above function public static void main(String[] args) { int arr[] = new int [] { 1 , 3 , 5 , 8 , 9 , 2 , 6 , 7 , 6 , 8 , 9 }; // calling minJumps method System.out.println(minJumps(arr)); } }

python

# python program to count Minimum number # of jumps to reach end# Returns minimum number of jumps to reach arr[n-1] from arr[0] def minJumps(arr, n): # The number of jumps needed to reach the starting index is 0 if (n < = 1 ): return 0# Return -1 if not possible to jump if (arr[ 0 ] = = 0 ): return - 1# initialization # stores all time the maximal reachable index in the array maxReach = arr[ 0 ] # stores the amount of steps we can still take step = arr[ 0 ] # stores the amount of jumps necessary to reach that maximal reachable position jump = 1 # Start traversing arrayfor i in range ( 1 , n): # Check if we have reached the end of the array if (i = = n - 1 ): return jump# updating maxReach maxReach = max (maxReach, i + arr[i])# we use a step to get to the current index step - = 1 ; # If no further steps left if (step = = 0 ): # we must have used a jump jump + = 1# Check if the current index / position or lesser index # is the maximum reach point from the previous indexes if (i > = maxReach): return - 1# re-initialize the steps to the amount # of steps to reach maxReach from position i. step = maxReach - i; return - 1# Driver program to test above function arr = [ 1 , 3 , 5 , 8 , 9 , 2 , 6 , 7 , 6 , 8 , 9 ] size = len (arr)# Calling the minJumps function print ( "Minimum number of jumps to reach end is % d " % minJumps(arr, size))# This code is contributed by Aditi Sharma

// C# program to count Minimum // number of jumps to reach end using System; class GFG { static int minJumps( int [] arr) { if (arr.Length < = 1) return 0; // Return -1 if not // possible to jump if (arr[0] == 0) return -1; // initialization int maxReach = arr[0]; int step = arr[0]; int jump = 1; // Start traversing array for ( int i = 1; i < arr.Length; i++) { // Check if we have reached // the end of the array if (i == arr.Length - 1) return jump; // updating maxReach maxReach = Math.Max(maxReach, i + arr[i]); // we use a step to get // to the current index step--; // If no further steps left if (step == 0) { // we must have used a jump jump++; // Check if the current index/position // or lesser index is the maximum reach // point from the previous indexes if (i > = maxReach) return -1; // re-initialize the steps to // the amount of steps to reach // maxReach from position i. step = maxReach - i; } }return -1; }// Driver Code public static void Main() { int [] arr = new int [] { 1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9 }; // calling minJumps method Console.Write(minJumps(arr)); } }// This code is contributed // by nitin mittal

的PHP

< ?php // PHP program to count Minimum number // of jumps to reach end// Returns minimum number of jumps to reach arr[n-1] from arr[0] function minJumps(& $arr , $n ) {// The number of jumps needed to reach the starting index is 0 if ( $n < = 1) return 0; // Return -1 if not possible to jump if ( $arr [0] == 0) return -1; // initialization // stores all time the maximal reachable index in the array. $maxReach = $arr [0]; // stores the number of steps we can still take $step = $arr [0]; //stores the number of jumps necessary to reach that //maximal reachable position. $jump =1; // Start traversing array $i =1; for ( $i = 1; $i < $n ; $i ++) { // Check if we have reached the end of the array if ( $i == $n -1) return $jump ; // updating maxReach $maxReach = max( $maxReach , $i + $arr [ $i ]); // we use a step to get to the current index $step --; // If no further steps left if ( $step == 0) { // we must have used a jump $jump ++; // Check if the current index/position or lesser index // is the maximum reach point from the previous indexes if ( $i > = $maxReach ) return -1; // re-initialize the steps to the amount // of steps to reach maxReach from position i. $step = $maxReach - $i ; } }return -1; }// Driver program to test above function$arr = array (1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9); $size = sizeof( $arr )/sizeof( $arr [0]); // Calling the minJumps function echo "Minimum number of jumps to reach end is " . minJumps( $arr , $size ); return 0; // This code is contribute by Ita_c. ?>

【算法设计（到达终点的最小跳数|S2（O(n)解））】输出如下：