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

2021年4月3日18:00:33 发表评论 648 次浏览

本文概述

给定一个整数数组, 其中每个元素代表可以从该元素进行的最大步数。编写一个函数以返回到达数组末尾的最小跳转数(从第一个元素开始)。如果一个元素为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)解决方案。

实现

要使用的变量：

  1. maxReach变量maxReach始终存储数组中的最大可达索引。
  2. step：可变步长存储我们仍然可以执行的步数(并使用索引0的值进行初始化, 即初始步数)
  3. 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开始迭代, 上述值将更新如下：
      1. 首先, 我们测试是否已经到达数组的末尾, 在这种情况下, 我们只需要返回跳转变量即可。

        if (i == arr.length - 1)
    return jump;
      2. 接下来, 我们更新maxReach。这等于maxReach和i + arr [i]的最大值(我们从当前位置可以采取的步数)。
        maxReach = Math.max(maxReach, i+arr[i]);
      3. 我们用了一个步骤来获取当前索引, 因此必须减少步骤。
        step--;
      4. 如果没有更多的剩余步数(即, steps = 0, 那么我们必须使用了一个跳转。因此请增加跳转。)由于我们知道可以通过某种方式达到maxReach, 因此我们将步数再次初始化为从中达到maxReach的步数位置i。但是在重新初始化步骤之前, 我们还要检查某个步骤是变为零还是变为负值, 在这种情况下, 无法继续执行。
        if (step == 0) {
    jump++;
    if(i>=maxReach)
       return -1;
    step = maxReach - i;
}

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

// 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 end
  
class 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 array
   
   for 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#

// 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.
?>

输出如下：

3

复杂度分析：

  • 时间复杂度：O(n)。
    只需遍历数组。
  • 辅助空间：O(1)。
    不需要空间。

参考文献：栈溢出

谢谢奇兰杰夫·Ja那建议这种解决方案。

如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。

木子山

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: