Comment trouver le nombre minimum de sauts pour atteindre la fin du tableau en O(n) fois
Question
Donné un tableau d'entiers dont chaque élément représente le nombre maximum d'étapes qui peuvent être faites avant à partir de cet élément.
Écrire une fonction pour renvoyer le nombre minimum de sauts pour atteindre le
fin du tableau (en commençant par le premier élément). Si un élément est
0, alors ne peut pas se déplacer par le biais de cet élément.Exemple
D'entrée: arr[] = {1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9}
Sortie: 3 (1-> 3 -> 8 ->9)
Trouvé plusieurs façons de L'approche par Programmation dynamique à d'autres linéaire approches. Je ne suis pas en mesure de comprendre la démarche qui est dit linéaire dans le temps. ICI est le lien où une approche linéaire est proposé.
Je ne suis pas en mesure de le comprendre. Ce que j'ai pu comprendre, c'est que l'auteur suggère de faire une approche gourmande et voir si nous arrivons à la fin .. si pas alors de revenir en arrière ?
OriginalL'auteur Walt | 2015-01-09
Vous devez vous connecter pour publier un commentaire.
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
eti+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'augmentationjump
. Puisque nous savons qu'il est possible en quelque sorte à atteindremaxReach
, nous initialisons les étapes de la quantité de mesures pour les atteindremaxReach
de la positioni
.Exemple:
Mon sous-optimale de l'algorithme qui fonctionne en
O(nk)
temps avecn
le nombre d'éléments dans le tableau etk
le plus grand élément du tableau et utilise une boucle interne surarray[i]
. Cette boucle est évitée par l'algorithme ci-dessous.Code
Je ne pense pas que ce soit le temps linéaire. Besoin d'une solution linéaire dans le temps.
Appologies, il n'est en effet pas dans le temps linéaire. J'ai édité mon post...
Allez les. Merci beaucoup de prendre le temps de répondre. Aucune raison de s'excuser :). Laissez-moi savoir si vous avez des idées sur le temps linéaire de la solution. Le leet le code du lien que j'ai partagé prétend avoir le temps linéaire de la solution. C'est juste que je ne suis pas en mesure de le comprendre. Pouvez vous s'il vous plaît jeter un oeil
la fonction
jump
ne manque jamais (exemple:A[] = {0,1}
etA[]={1,3,1,0,0,0,0,1}
, doit échouer, selon la question de la description). ne devriez-vous pas ajouter une condition au début de la boucle:if (steps == 0) return INT_MAX;
, et un retour à la fin de la fonction (si vous ne doit jamais y arriver):return INT_MAX;
?, thnx!OriginalL'auteur Niels Billen
Ans de retard à la fête , mais c'est un autre O(n), solution qui fait sens pour moi.
OriginalL'auteur Vasilescu Andrei
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 lesi
de la position et de chaque élément de chaque élément affecte sa valeur + 1 pouri + 1 ... i + a[i]
segment.Analyse de la complexité:
Le nombre total d'éléments dans
toDelete
listes estO(n)
. C'est le cas, parce qu'à chaque positioni
au plus un élément est ajouté. C'est pourquoi le traitement de tous les éléments de tous lestoDelete
listes nécessite du temps linéaire.La
min
valeur ne peut qu'augmenter. C'est pourquoi l'intérieurwhile
boucle, au plusn
itérations au total.L'extérieur
for
boucle rend évidemmentn
itérations. Ainsi, la complexité du temps est linéaire.Sur le nombre d'étapes: il signifie que
dp[i] <= dp[i + 1]
pour tousi
.Merci beaucoup @ILoveCoding pour l'ajout de l'analyse de la complexité. Mais je ne suis pas en mesure de comprendre l'algorithme encore. 🙁 Si vous pouvez certains commentaires. Ou comment est-il exactement de travail
Pour un instant, rappelons naïf solution: pour chaque i, itérer pour j = i + 1 ... i + a[i]: dp[j] = min(dp[j], dp[i] + 1). Cela crée donc un segment [i + 1, i + a[i]] avec dp[i] + 1 la valeur. Au lieu d'itération de cette façon, nous pouvons maintenir un ensemble de "l'ouvrir" segments et de leurs valeurs(ouvert signifie que k + 1 <= i <= k + a[k]).
OriginalL'auteur kraskevich
Ici est l'intuition fondamentale concernant le problème de l'approche gourmande et le repos sont les exigences du code.
Tableau donné en Entrée: une[] = {1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9}.
Maintenant nous commençons à partir du 1er élément que j'ai.e i=0 et a[i] = 1. Donc, voir ce que nous pouvons prendre à plus d'un saut de taille 1, alors, puisque nous n'avons pas d'autre choix si nous réaliser cette étape.
Actuellement, nous sommes à i=1 et a[i]=3. Nous pouvons faire un saut de taille 3, mais au lieu de nous considérer toutes les sauts qu'on peut faire à partir de l'emplacement actuel et d'atteindre la distance maximale qui est à l'intérieur de limites(de la matrice). Alors, quels sont nos choix? nous pouvons faire un saut de l'étape 1, ou 2 ou 3 étapes. Pour que nous puissions étudier partir de l'emplacement actuel pour chaque taille de sauts et de choisir celui qui peut prendre un maximum de plus dans le tableau.
Une fois que nous avons décidé, que l'on nous en tenir à, nous prenons le saut de la taille et de la mise à jour de notre nombre de sauts effectués jusqu'à présent et aussi où l'on peut atteindre au maximum et le nombre d'étapes que nous avons à décider dès maintenant de notre prochain déménagement. Et c'est tout. C'est de cette façon enfin, nous sélectionnons la meilleure option linéairement de la traversée de la matrice.
C'est donc l'idée de base de l'algo, vous pourriez être à la recherche pour, ensuite, le code pour l'algorithme de travailler. Cheers!
Espère que quelqu'un le temps de voyage et trouve l'intuition utile !! 🙂 😛
"Des années de retard à la partie" @Vasilescu Andrei - bien dit. Parfois, il me semble que nous sommes des voyageurs du temps.
OriginalL'auteur Sid Ray
Simple code python pour le nombre Minimum de sauts pour atteindre la fin de problème.
OriginalL'auteur Vishwanath Hiremath