Dada una array de enteros donde cada elemento representa el número máximo de pasos que se pueden realizar desde ese elemento. Escriba una función para devolver el número mínimo de saltos para llegar al final de la array (a partir del primer elemento). Si un elemento es 0, entonces no podemos movernos a través de ese elemento. Si no podemos llegar al final, devuelve -1.
Ejemplos:
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.
En esta publicación, se discutirá su solución O(n).
En el Conjunto -1 , se discute la solución O(n 2 ).
Implementación: Variables a utilizar:
- maxReach La variable maxReach almacena en todo momento el índice máximo alcanzable en el arreglo.
- jump almacena la cantidad de saltos necesarios para alcanzar la posición máxima alcanzable. También indica el salto actual que estamos haciendo en el arreglo .
- paso La variable paso almacena el número de pasos que todavía podemos dar en el salto actual ‘salto’ (y se inicializa con el valor en el índice 0, es decir, el número inicial de pasos)
Array dada arr = 1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9
- maxReach = arr[0]; // arr[0] = 1, por lo que el índice máximo que podemos alcanzar en este momento es 1.
step = arr[0]; // arr[0] = 1, la cantidad de pasos que aún podemos dar también es 1.
jump = 1; // actualmente estamos dando nuestro primer salto.
Ahora, comenzando la iteración desde el índice 1, los valores anteriores se actualizan de la siguiente manera:
- Primero, probamos si hemos llegado al final de la array, en ese caso, solo necesitamos devolver la variable de salto.
if (i == arr.length - 1)
return jump;
- A continuación, actualizamos el maxReach. Esto es igual al máximo de maxReach e i+arr[i](la cantidad de pasos que podemos dar desde la posición actual).
maxReach = Math.max(maxReach, i+arr[i]);
- Utilizamos un paso para llegar al índice actual, por lo que los pasos deben reducirse.
step--;
- Si no quedan más pasos (es decir, pasos = 0, entonces debemos haber usado un salto. Por lo tanto, aumente el salto. Como sabemos que es posible alcanzar el alcance máximo de alguna manera, inicializamos nuevamente los pasos al número de pasos para alcanzar el alcance máximo desde posición i. Pero antes de reiniciar el paso, también verificamos si un paso se está volviendo cero o negativo. En este caso, no es posible llegar más lejos.
if (step == 0) {
jump++;
if(i>=maxReach)
return -1;
step = maxReach - i;
}
Implementación:
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));
}
}
Python3
# 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.
?>
Javascript
<script>
// Javascript program to count Minimum number
// 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.
let maxReach = arr[0];
// stores the number of steps
// we can still take
let step = arr[0];
// stores the number of jumps
// necessary to reach that maximal
// reachable position.
let jump = 1;
// Start traversing array
let 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 =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 program to test above function
var arr = [ 1, 3, 5, 8, 9, 2, 6, 7, 6, 8,9 ];
let size = arr.length;
// Calling the minJumps function
document.write("Minimum number of jumps to reach end is "+
minJumps(arr, size));
// This code is contributed by
// Potta Lokesh
</script>
Producción
3
Análisis de Complejidad:
- Complejidad de tiempo: O (n), solo se necesita un recorrido de la array.
- Espacio Auxiliar: O(1), No se requiere espacio.
Este artículo es una contribución de Sahil Chhabra y Gaurav Miglani. Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks. Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Otro enfoque:
- Para resolver saltos mínimos para llegar al final de la array,
- Para cada índice de salto, consideramos la necesidad de evaluar los valores de paso correspondientes en el índice y, al usar el valor del índice, se divide la array en subpartes y se descubre el índice máximo de pasos cubiertos.
- El siguiente código y explicación le dará una idea clara:
- En cada subarreglo, descubra el índice de distancia máxima recorrida como la primera parte del arreglo y el segundo arreglo
Array de entrada: {1, 3, 5, 9, 6, 2, 6, 7, 6, 8, 9} -> la posición del índice comienza con 0
Pasos :
El paso inicial es considerar el primer índice e incrementar el salto.
Saltar = 1
1, { 3, 5, 9, 6, 2, 6, 7, 6, 8, 9} -> 1 se considera como primer salto
próximo paso
Desde el paso inicial, solo hay un paso para avanzar, así que
Saltar = 2
1,3, { 5, 9, 6,2, 6, 7, 6, 8, 9} -> 1 se considera como primer salto
próximo paso
Ahora tenemos la flexibilidad de elegir cualquiera de {5,9,6} porque el último paso dice que podemos avanzar hasta 3 pasos
Considérelo como un subarreglo, evalúe la distancia máxima que cubre con cada posición de índice
Como {5,9,6} las posiciones del índice son {2,3,4}
por lo que el total de pasos adicionales que podemos cubrir:
{7,12,10} -> podemos suponer que {7,12} y {10} son 2 subarreglos donde la parte izquierda de los arreglos dice la distancia máxima cubierta con 2 pasos y el lado derecho dice que los pasos máximos cubren con el resto valores
próximo paso:
Teniendo en cuenta la distancia máxima cubierta en la primera array, iteramos los siguientes elementos restantes
1,3,9 {6,2, 6, 7, 6, 8, 9}
Desde el paso anterior ya visitamos el 4º índice, continuamos con el siguiente 5º índice como se explicó anteriormente
{6,2, 6, 7, 6, 8, 9} posiciones de índice {4,5,6,7,8,9,10}
{10,7,12,14,14,17,19}
El paso máximo cubre aquí es 19 cuyo índice correspondiente es 10
C++
// C++ program to illustrate Minimum
// number of jumps to reach end
#include <iostream>
using namespace std;
// 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;
// Stores the number of jumps
// necessary to reach that maximal
// reachable position.
int jump = 1;
// Stores the subarray last index
int subArrEndIndex = arr[0];
int i = 1;
// Maximum steps covers in
// first half of sub array
int subArrFistHalfMaxSteps = 0;
// Maximum steps covers
// in second half of sub array
int subArrSecondHalfMaxSteps = 0;
// Start traversing array
for (i = 1; i < n;) {
subArrEndIndex = i + subArrEndIndex;
// Check if we have reached
// the end of the array
if (subArrEndIndex >= n)
return jump;
int firstHalfMaxStepIndex = 0;
// Iterate the sub array
// and find out the maxsteps
// cover index
for (; i < subArrEndIndex; i++) {
int stepsCanCover = arr[i] + i;
if (subArrFistHalfMaxSteps < stepsCanCover) {
subArrFistHalfMaxSteps = stepsCanCover;
subArrSecondHalfMaxSteps = 0;
firstHalfMaxStepIndex = i;
}
else if (subArrSecondHalfMaxSteps
< stepsCanCover) {
subArrSecondHalfMaxSteps = stepsCanCover;
}
}
if (i > subArrFistHalfMaxSteps)
return -1;
jump++;
// Next subarray end index
// and so far calculated sub
// array max step cover value
subArrEndIndex = arr[firstHalfMaxStepIndex];
subArrFistHalfMaxSteps = subArrSecondHalfMaxSteps;
}
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;
}
Java
// Java program to illustrate Minimum
// number of jumps to reach end
import java.io.*;
class GFG {
// Returns minimum number of jumps
// to reach arr[n-1] from arr[0]
static 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;
// Stores the number of jumps
// necessary to reach that maximal
// reachable position.
int jump = 1;
// Stores the subarray last index
int subArrEndIndex = arr[0];
int i = 1;
// Maximum steps covers in
// first half of sub array
int subArrFistHalfMaxSteps = 0;
// Maximum steps covers
// in second half of sub array
int subArrSecondHalfMaxSteps = 0;
// Start traversing array
for (i = 1; i < n;) {
subArrEndIndex = i + subArrEndIndex;
// Check if we have reached
// the end of the array
if (subArrEndIndex >= n)
return jump;
int firstHalfMaxStepIndex = 0;
// Iterate the sub array
// and find out the maxsteps
// cover index
for (; i < subArrEndIndex; i++) {
int stepsCanCover = arr[i] + i;
if (subArrFistHalfMaxSteps
< stepsCanCover) {
subArrFistHalfMaxSteps = stepsCanCover;
subArrSecondHalfMaxSteps = 0;
firstHalfMaxStepIndex = i;
}
else if (subArrSecondHalfMaxSteps
< stepsCanCover) {
subArrSecondHalfMaxSteps
= stepsCanCover;
}
}
if (i > subArrFistHalfMaxSteps)
return -1;
jump++;
// Next subarray end index
// and so far calculated sub
// array max step cover value
subArrEndIndex = arr[firstHalfMaxStepIndex];
subArrFistHalfMaxSteps
= subArrSecondHalfMaxSteps;
}
return -1;
}
// Driver program to test above function
public static void main(String[] args)
{
int arr[] = { 1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9 };
int size = arr.length;
// Calling the minJumps function
System.out.println(
"Minimum number of jumps to reach end is "
+ minJumps(arr, size));
}
}
Python3
# Python program to illustrate 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
# Stores the number of jumps
# necessary to reach that maximal
# reachable position.
jump = 1
# Stores the subarray last index
subArrEndIndex = arr[0]
i = 1
# Maximum steps covers in
# first half of sub array
subArrFistHalfMaxSteps = 0
# Maximum steps covers
# in second half of sub array
subArrSecondHalfMaxSteps = 0
# Start traversing array
for i in range(1, n):
subArrEndIndex = i + subArrEndIndex
# Check if we have reached
# the end of the array
if (subArrEndIndex >= n):
return jump
firstHalfMaxStepIndex = 0
# Iterate the sub array
# and find out the maxsteps
# cover index
j = i
for j in range(i, subArrEndIndex):
stepsCanCover = arr[j] + j
if (subArrFistHalfMaxSteps < stepsCanCover):
subArrFistHalfMaxSteps = stepsCanCover
subArrSecondHalfMaxSteps = 0
firstHalfMaxStepIndex = j
elif(subArrSecondHalfMaxSteps < stepsCanCover):
subArrSecondHalfMaxSteps = stepsCanCover
i = j
if (i > subArrFistHalfMaxSteps):
return -1
jump += 1
# Next subarray end index
# and so far calculated sub
# array max step cover value
subArrEndIndex = arr[firstHalfMaxStepIndex]
subArrFistHalfMaxSteps = subArrSecondHalfMaxSteps
return -1
# Driver program to test above function
if __name__ == '__main__':
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 ", minJumps(arr, size))
C#
// C# program to illustrate Minimum
// number of jumps to reach end
using System;
public class GFG {
// Returns minimum number of jumps
// to reach arr[n-1] from arr[0]
static 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;
// Stores the number of jumps
// necessary to reach that maximal
// reachable position.
int jump = 1;
// Stores the subarray last index
int subArrEndIndex = arr[0];
int i = 1;
// Maximum steps covers in
// first half of sub array
int subArrFistHalfMaxSteps = 0;
// Maximum steps covers
// in second half of sub array
int subArrSecondHalfMaxSteps = 0;
// Start traversing array
for (i = 1; i < n;) {
subArrEndIndex = i + subArrEndIndex;
// Check if we have reached
// the end of the array
if (subArrEndIndex >= n)
return jump;
int firstHalfMaxStepIndex = 0;
// Iterate the sub array
// and find out the maxsteps
// cover index
for (; i < subArrEndIndex; i++) {
int stepsCanCover = arr[i] + i;
if (subArrFistHalfMaxSteps
< stepsCanCover) {
subArrFistHalfMaxSteps = stepsCanCover;
subArrSecondHalfMaxSteps = 0;
firstHalfMaxStepIndex = i;
}
else if (subArrSecondHalfMaxSteps
< stepsCanCover) {
subArrSecondHalfMaxSteps
= stepsCanCover;
}
}
if (i > subArrFistHalfMaxSteps)
return -1;
jump++;
// Next subarray end index
// and so far calculated sub
// array max step cover value
subArrEndIndex = arr[firstHalfMaxStepIndex];
subArrFistHalfMaxSteps
= subArrSecondHalfMaxSteps;
}
return -1;
}
// Driver code
static public void Main()
{
int[] arr = { 1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9 };
int size = arr.Length;
// Calling the minJumps function
Console.WriteLine(
"Minimum number of jumps to reach end is "
+ minJumps(arr, size));
}
}
Javascript
<script>
// Javascript program to count Minimum number
// 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;
// Stores the number of jumps
// necessary to reach that maximal
// reachable position.
let jump = 1;
// Stores the subarray last index
let subArrEndIndex = arr[0];
let i = 1;
// Maximum steps covers in
// first half of sub array
let subArrFistHalfMaxSteps = 0;
// Maximum steps covers
// in second half of sub array
let subArrSecondHalfMaxSteps = 0;
// Start traversing array
for (i = 1; i < n;) {
subArrEndIndex = i + subArrEndIndex;
// Check if we have reached
// the end of the array
if (subArrEndIndex >= n)
return jump;
let firstHalfMaxStepIndex = 0;
// Iterate the sub array
// and find out the maxsteps
// cover index
for (; i < subArrEndIndex; i++) {
let stepsCanCover = arr[i] + i;
if (subArrFistHalfMaxSteps < stepsCanCover) {
subArrFistHalfMaxSteps = stepsCanCover;
subArrSecondHalfMaxSteps = 0;
firstHalfMaxStepIndex = i;
}
else if (subArrSecondHalfMaxSteps
< stepsCanCover) {
subArrSecondHalfMaxSteps = stepsCanCover;
}
}
if (i > subArrFistHalfMaxSteps)
return -1;
jump++;
// Next subarray end index
// and so far calculated sub
// array max step cover value
subArrEndIndex = arr[firstHalfMaxStepIndex];
subArrFistHalfMaxSteps = subArrSecondHalfMaxSteps;
}
return -1;
}
// Driver program to test above function
var arr =[1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9 ];
let size = arr.length;
// Calling the minJumps function
document.write ("Minimum number of jumps to reach end is "+
minJumps(arr, size));
</script>
Producción
3
Complejidad temporal: O(n),Espacio auxiliar: O(1).
Solo se requiere un recorrido de una array. No se ha utilizado una array adicional, por lo que se utiliza un espacio constante.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA