Comment trouver le nombre minimum de sauts pour atteindre la fin du tableau en O(n) fois

Le temps de la complexité de la solution proposée sur le site est linéaire car vous ne itérer sur le tableau une fois. L'algorithme évite l'intérieur itération de ma proposition de solution à l'aide de quelques astuces judicieuses.

La variable maxReach des magasins de tous les temps au maximum accessible position dans le tableau. jump magasins de la quantité de sauts nécessaires pour atteindre cette position. step magasins de la quantité de mesures que nous pouvons prendre encore (et est initialisé avec le nombre de mesures à la première position de tableau)

Cours de l'itération, les valeurs ci-dessus sont mis à jour comme suit:

Nous avons d'abord tester si nous avons atteint la fin du tableau, dans lequel cas, on a juste besoin de retourner la jump variable.

Ensuite, nous mettre à jour l'maximale accessible position. C'est égal à la valeur maximale de maxReach et i+A[i] (le nombre de mesures que nous pouvons prendre à partir de la position actuelle).

Nous avons utilisé une étape pour obtenir à l'index actuel, de sorte steps doit être diminué.

Si aucune des étapes restantes (c'est à dire steps=0, nous devons alors avoir utilisé un saut. Par conséquent, l'augmentation jump. Puisque nous savons qu'il est possible en quelque sorte à atteindre maxReach, nous initialisons les étapes de la quantité de mesures pour les atteindre maxReach de la position i.

public class Solution {
    public int jump(int[] A) {
        if (A.length <= 1)
            return 0;
        int maxReach = A[0];
        int step = A[0];
        int jump = 1;
        for (int i = 1; i < A.length; i++) {
           if (i == A.length - 1)
                return jump;
            if (i + A[i] > maxReach)
                maxReach = i + A[i];
            step--;
            if (step == 0) {
                jump++;
                step = maxReach - i;
            } 
        }
        return jump;
    }
}

Exemple:

int A[] = {1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9}
int maxReach = A[0];     //A[0]=1, so the maximum index we can reach at the moment is 1.
int step = A[0];         //A[0] = 1, the amount of steps we can still take is also 1.
int jump = 1;            //we will always need to take at least one jump.
/*************************************
* First iteration (i=1)
************************************/
if (i + A[i] > maxReach) //1+3 > 1, we can reach further now!
maxReach = 1 + A[i]  //maxReach = 4, we now know that index 4 is the largest index we can reach.
step--                   //we used a step to get to this index position, so we decrease it
if (step == 0) {
++jump;              //we ran out of steps, this means that we have made a jump
//this is indeed the case, we ran out of the 1 step we started from. jump is now equal to 2.
//but we can continue with the 3 steps received at array position 2.
steps = maxReach-i   //we know that by some combination of 2 jumps, we can reach  position 4.
//therefore in the current situation, we can minimaly take 3
//more steps to reach position 4 => step = 3
}
/*************************************
* Second iteration (i=2)
************************************/
if (i + A[i] > maxReach) //2+5 > 4, we can reach further now!
maxReach = 1 + A[i]  //maxReach = 7, we now know that index 7 is the largest index we can reach.
step--                   //we used a step so now step = 2
if (step==0){
//step 
}
/*************************************
* Second iteration (i=3)
************************************/
if (i + A[i] > maxReach) //3+8 > 7, we can reach further now!
maxReach = 1 + A[i]  //maxReach = 11, we now know that index 11 is the largest index we can reach.
step--                   //we used a step so now step = 1
if (step==0){
//step 
}
/*************************************
* Third iteration (i=4)
************************************/
if (i + A[i] > maxReach) //4+9 > 11, we can reach further now!
maxReach = 1 + A[i]  //maxReach = 13, we now know that index 13 is the largest index we can reach.
step--                   //we used a step so now step = 0
if (step == 0) {
++jump;              //we ran out of steps, this means that we have made a jump.
//jump is now equal to 3.
steps = maxReach-i   //there exists a combination of jumps to reach index 13, so
//we still have a budget of 9 steps
}
/************************************
* remaining iterations
***********************************
//nothing much changes now untill we reach the end of the array.

Mon sous-optimale de l'algorithme qui fonctionne en O(nk) temps avec n le nombre d'éléments dans le tableau et k le plus grand élément du tableau et utilise une boucle interne sur array[i]. Cette boucle est évitée par l'algorithme ci-dessous.

Code

public static int minimum_steps(int[] array) {
int[] min_to_end = new int[array.length];
for (int i = array.length - 2; i >= 0; --i) {
if (array[i] <= 0)
min_to_end[i] = Integer.MAX_VALUE;
else {
int minimum = Integer.MAX_VALUE;
for (int k = 1; k <= array[i]; ++k) {
if (i + k < array.length)
minimum = Math.min(min_to_end[i+k], minimum);
else
break;
}
min_to_end[i] = minimum + 1;
}
}
return min_to_end[0];
} 

OriginalL'auteur Niels Billen

Voici un autre linéaire de la solution. Le code est plus long que celui suggéré dans le leet lien de code, mais je pense que c'est plus facile à comprendre. Elle est basée sur deux observations: le nombre d'étapes requises pour atteindre les i + 1 position n'est jamais moins que le nombre d'étapes requises pour atteindre les i de la position et de chaque élément de chaque élément affecte sa valeur + 1 pour i + 1 ... i + a[i] segment.

public class Solution {
public int jump(int[] a) {
int n = a.length;
//count[i] is the number of "open" segments with value i
int[] count = new int[n];
//the number of steps to reach the i-th position
int[] dp = new int[n];
Arrays.fill(dp, n);
//toDelete[i] is the list of values of segments 
//that close in the i-th position
ArrayList<Integer>[] toDelete = new ArrayList[n];
for (int i = 0; i < n; i++)
toDelete[i] = new ArrayList<>();
//Initially, the value is 0(for the first element).
toDelete[0].add(0);
int min = 0;
count[0]++;
for (int i = 0; i < n; i++) {
//Finds the new minimum. It uses the fact that it cannot decrease. 
while (min < n && count[min] == 0)
min++;
//If min == n, then there is no path. So we can stop.
if (min == n)
break;
dp[i] = min;
if (dp[i] + 1 < n) {
//Creates a new segment from i + 1 to i + a[i] with dp[i] + 1 value
count[dp[i] + 1]++;
if (i + a[i] < n)
toDelete[i + a[i]].add(dp[i] + 1);
}
//Processes closing segments in this position.
for (int deleted : toDelete[i])
count[deleted]--;
}
return dp[n - 1];
}
}

Analyse de la complexité:

1. Le nombre total d'éléments dans toDelete listes est O(n). C'est le cas, parce qu'à chaque position i au plus un élément est ajouté. C'est pourquoi le traitement de tous les éléments de tous les toDelete listes nécessite du temps linéaire.

2. La min valeur ne peut qu'augmenter. C'est pourquoi l'intérieur while boucle, au plus n itérations au total.

3. L'extérieur for boucle rend évidemment n itérations. Ainsi, la complexité du temps est linéaire.

OriginalL'auteur kraskevich

Simple code python pour le nombre Minimum de sauts pour atteindre la fin de problème.

ar=[1, 3, 6, 3, 2, 3, 6, 8, 9, 5]
minJumpIdx=0
res=[0]*len(ar)
i=1
while(i<len(ar) and i>minJumpIdx):
if minJumpIdx+ar[minJumpIdx]>=i:
res[i]=res[minJumpIdx]+1
i+=1
else:
minJumpIdx+=1
if res[-1]==0:
print(-1)
else:
print(res[-1])

OriginalL'auteur Vishwanath Hiremath