Pour plus de détails sur le problème, consultez cette sortie sur - https: //www.hackerrank .Com / Défis / Stacks égaux / Problème
Nous avons trois piles de cylindres où chaque cylindre a le même diamètre, mais ils peuvent varier en hauteur. Vous pouvez modifier la hauteur d'une pile en retirant et en supprimant son cylindre le plus haut de fois.
Nous devons trouver la hauteur maximale possible des piles de telle que toutes les piles sont exactement la même hauteur. Cela signifie que nous devons éliminer zéro ou plusieurs cylindres du haut de zéro ou plus des trois piles jusqu'à ce qu'ils soient tous de la même hauteur, puis imprimez la hauteur. Les déménagements doivent être effectués de manière à maximiser la hauteur.
J'ai implémenté les piles à l'aide de trois vecteurs et découvrit la somme des hauteurs de cylindres dans chacune des trois piles. Maintenant, j'ai mis en place la fonction POP () sur chaque pile à plusieurs reprises jusqu'à ce que l'une de l'une de la pile soit vide ou la somme des hauteurs de cylindres dans chaque pile devient égale.
// ma fonction qui renvoie la hauteur maximale : entrée d'échantillon: sortie attendue:
3 Réponses :
Le problème est que vous supprimez simplement le haut de la pile de chaque pile dans chaque itération.
Par exemple: Vous avez trois piles, tout en ayant la base d'un objet de 5 unités. Maintenant, un seul d'entre eux a également un objet de 1 unité de hauteur sur la base; Cela vous donnera des hauteurs de 5 (1x5), 5 (1x5) et 6 (1x5 + 1x1).
Dans votre algorithme, vous comparez d'abord les sommes. "Si (5 == 5 == 6) => Faux".
Ensuite, vous prenez l'objet sur chaque empilement. -> Première pile: 0 unités, deuxième pile: 0 unités, troisième pile 1 unité.
Vous voyez le problème?
Igor l'a mentionné, mais vous devez d'abord rechercher la plus grande pile et "Travailler".
J'ai trouvé deux choses qui doivent être réparées.
Pour le premier, je renverserais trois vecteurs donnés au début de la fonction. Bien que cela ne soit pas très efficace, mais cela est de minimiser les changements de votre code. Vous ne devez pas effacer le premier élément car il provoque des copies Pour la seconde, voici un contre-exemple: La solution doit être 2, mais elle retournera 0. < P> Nous pouvons donc changer la stratégie pour sauter la seule pile la plus longue à la fois. Donc, je changerais la boucle tandis que: Ces modifications rendraient le code un peu plus lentement, mais ne change pas la complexité de temps. Si vous ne souhaitez pas inverser les tableaux, vous pouvez penser à garder les indices de courant pour chaque vecteur plutôt que de les éclairer réellement. O (n) tandis que pop_back est o (1)
Voir que j'ai commis la même erreur précédemment, je sais que vous savez que corriger le code ci-dessus est la solution au problème ci-dessus.
int equalStacks(vector<int> h1, vector<int> h2, vector<int> h3) {
stack<int> stk1;
stack<int> stk2;
stack<int> stk3;
int sum1=0,sum2=0,sum3=0;
for(int i=h1.size()-1;i>=0;i--){
sum1=sum1+h1[i];
stk1.push(sum1);
}
for(int i=h2.size()-1;i>=0;i--){
sum2=sum2+h2[i];
stk2.push(sum2);
}
for(int i=h3.size()-1;i>=0;i--){
sum3=sum3+h3[i];
stk3.push(sum3);
}
while(1){
if(stk1.empty()||stk2.empty()||stk3.empty()){
return 0;
}
if(stk1.top()==stk2.top() && stk1.top()==stk3.top()){
return stk1.top();
}
else if(stk1.top()>=stk2.top()&&stk1.top()>=stk3.top()){
stk1.pop();
}
else if(stk2.top()>=stk1.top()&&stk2.top()>=stk3.top()){
stk2.pop();
}
else {
stk3.pop();
}
}
return 0;
À chaque étape, vous retirez simultanément trois cylindres, un de chaque pile. Au lieu de cela, vous devez les supprimer un par un, à chaque fois de la plus haute pile (ou du moins, d'un qui n'est pas le plus court).