Baseball Game

Q: Comment distinguer un nombre d’une opération dans Baseball Game ?

Comparez d’abord l’entrée aux trois symboles "+" , "D" et "C" , et traitez tout autre élément comme un entier. La conversion avec le parseur du langage prend en charge un signe moins en tête, donc "-30000" devient -30000 .

FacilePile

+10

Tu tiens le score d’un jeu inhabituel. La liste operations est lue de gauche à droite, et chaque entrée modifie un relevé des scores. Un entier tel que "7" ou "-2" ajoute ce score au relevé. "+" ajoute un score égal à la somme des deux derniers scores, "D" ajoute un score égal au double du dernier score, et "C" supprime définitivement le dernier score du relevé.

Écris une fonction nommée calPoints qui renvoie la somme des scores restants sur le relevé après la dernière opération. Un relevé vide a une somme de 0.

Fonction

calPoints(operations: string-array) → integer

operationsstring-array: les opérations dans l'ordre : des entiers sous forme de texte, ou "+", "D", "C"
Renvoieinteger: la somme des scores encore inscrits au registre à la fin

Contraintes

1 ≤ operations.length ≤ 5000
Chaque entrée est "+", "D", "C", ou un entier écrit en décimal tel que -3 × 10⁴ ≤ value ≤ 3 × 10⁴.
Chaque opération est valide : "+" n’apparaît que lorsque l’enregistrement contient au moins deux scores, "D" et "C" seulement lorsqu’il en contient au moins un.
Chaque score de l'enregistrement ainsi que la somme finale tiennent dans un entier signé de 32 bits.

Exemples

Entrée: operations = ["4", "-2", "D", "+", "C", "7"]
Sortie: 5
Explication: Le relevé s’agrandit pour atteindre [4, -2], "D" ajoute -4, "+" ajoute -2 + -4 = -6, "C" supprime ce -6, et 7 est ajouté en dernier. La somme du relevé [4, -2, -4, 7] est égale à 5.

Entrée: operations = ["6", "D", "C", "C"]
Sortie: 0
Explication: "D" ajoute 12 après le 6, puis les deux entrées "C" suppriment 12 et 6. Il ne reste rien, donc la réponse est 0.

Entrée: operations = ["1", "2", "+", "+", "D"]
Sortie: 21
Explication: Les deux entrées "+" additionnent 1 + 2 = 3, puis 2 + 3 = 5, et "D" ajoute 10. L’enregistrement [1, 2, 3, 5, 10] totalise 21.

+13 tests cachés à la soumission

Pour aller plus loin

Peux-tu renvoyer la somme sans additionner l'enregistrement à la fin, afin que chaque opération, y compris une annulation, prenne un temps O(1) ?

Indices

Ouvrez-les un par un. Chacun en dévoile un peu plus.

0 sur 3 ouverts

Solution

Chaque opération examine les scores les plus récents, et "C" peut retirer les scores un à un, de sorte que les scores précédant un score annulé redeviennent les plus récents. Ce modèle « dernier entré, premier sorti » correspond exactement à une pile. Empile chaque nouveau score, dépile lors de "C", et consulte la ou les deux entrées au sommet pour "D" et "+".

Construisez l’enregistrement sur une pile, additionnez-le à la fin

Intuition

Garde les scores dans une liste où le score le plus récent se trouve à la fin. Chaque opération ne touche alors qu’à la fin de la liste : un entier est ajouté, "D" ajoute le double de la dernière valeur, "+" ajoute la somme des deux dernières valeurs et "C" retire la dernière valeur.

Pourquoi une pile suffit : après un "C", le score qui était l’avant-dernier devient le plus récent, et c’est celui que le "D" ou le "+" suivant doit lire. Le retirer de la liste te donne cela gratuitement. Dans le premier exemple, "C" retire -6 et laisse [4, -2, -4], donc tout "+" ultérieur additionnerait à nouveau -2 + -4.

Quand il n’y a plus d’opérations, la liste contient exactement les scores à prendre en compte. Additionne-les. Chaque opération prend O(1) et la somme finale prend O(n) : l’ensemble s’exécute donc en O(n) avec un espace de O(n) pour la pile.

Algorithme

Commence avec une pile vide record.
Pour "+", empile la somme des deux éléments au sommet. Pour "D", empile le double de l'élément au sommet.
Pour "C", dépile l'élément au sommet.
Sinon, l'élément est un nombre : convertis le texte en entier et empile-le.
Renvoie la somme de tout ce qui reste dans la pile.

def calPoints(operations):
    record = []  # the scores that still count, newest last
    for op in operations:
        if op == "+":
            record.append(record[-1] + record[-2])
        elif op == "D":
            record.append(2 * record[-1])
        elif op == "C":
            record.pop()
        else:
            record.append(int(op))
    return sum(record)

Pile avec un total cumulatif

Intuition

La boucle finale sur la pile représente un travail supplémentaire que tu peux éviter. Garde une variable total qui correspond toujours à la somme de la pile. Chaque ajout incrémente total du nouveau score, et chaque "C" soustrait le score retiré de la pile.

La pile reste nécessaire. Une annulation doit savoir quel score retirer du total, et "+" et "D" doivent connaître les derniers scores après les annulations. Dans le premier exemple, le total passe par 4, 2, -2, -8, puis l’annulation retire le -6 pour obtenir -2, et le 7 final le porte à 5.

La complexité temporelle est de O(n) avec un seul parcours, et la réponse est disponible après chaque préfixe des opérations, ce qui est important lorsque les scores arrivent en direct. L’espace utilisé est de O(n) : les n opérations pourraient toutes être des nombres qui restent dans le registre.

Algorithme

Commencez avec une pile vide record et total = 0.
Pour "C", dépilez le score du sommet et soustrayez-le de total.
Sinon, calculez le nouveau score : la somme des deux scores au sommet pour "+", le double du score au sommet pour "D", ou l'entier lui-même.
Empilez le nouveau score et ajoutez-le à total.
Retournez total.

def calPoints(operations):
    record = []  # the scores that still count, newest last
    total = 0    # always the sum of record
    for op in operations:
        if op == "C":
            total -= record.pop()  # the cancelled score leaves the total too
            continue
        if op == "+":
            score = record[-1] + record[-2]
        elif op == "D":
            score = 2 * record[-1]
        else:
            score = int(op)
        record.append(score)
        total += score
    return total

Pièges et cas limites

Les règles sont simples, donc la plupart des bugs viennent d’une mauvaise lecture du score ou de l’analyse du texte.

Ne conserver qu’un total cumulé et les deux derniers scores. Après un "C", il faut le score qui précède ces deux scores ; ainsi, une annulation suivie de "+" lit des valeurs périmées. Conservez toute la pile.
Oublier que les scores annulés sont retirés du total. Avec un total cumulé, "C" doit soustraire le score dépilé, et non l’ignorer.
Analyser les scores négatifs manuellement et perdre le signe. Utilisez le parseur d’entiers du langage, qui lit "-2" comme -2.
Vérifier si une entrée est un nombre en cherchant un chiffre. "-5" commence par un signe moins ; vérifiez les trois symboles et traitez tout le reste comme un nombre.
Supposer que la réponse est positive. Les scores négatifs et les annulations peuvent donner une somme négative, ou 0 si tous les scores ont été annulés.

Questions fréquentes4

Quelle est la complexité temporelle du jeu de baseball ?

Chaque opération effectue une quantité constante de travail au sommet de la pile, donc traiter n opérations prend un temps de O(n). Additionner les éléments de la pile à la fin prend au maximum un autre temps de O(n), et un total courant permet même d’éviter cela. La pile utilise un espace de O(n) lorsque la plupart des opérations ajoutent des scores.

Pourquoi une pile est-elle la structure de données adaptée au jeu de baseball ?

Chaque règle lit ou supprime les scores les plus récents, et une annulation révèle le score précédent. C’est un ordre dernier entré, premier sorti, que fournit une pile avec des opérations d’empilement, de dépilement et de consultation en O(1). Un tableau ou une liste ordinaire utilisé uniquement à son extrémité sert de pile dans tous les langages.

Peut-on résoudre Baseball Game avec un espace supplémentaire en O(1) ?

Pas en général. Une série de nombres suivie d’une série d’entrées "C" les annule dans l’ordre inverse, donc tu dois mémoriser chaque nombre jusqu’à savoir s’il sera annulé. Cela nécessite une mémoire de O(n) dans le pire des cas. Un total cumulatif évite le passage final, pas la pile.

Comment distinguer un nombre d’une opération dans Baseball Game ?

Comparez d’abord l’entrée aux trois symboles "+", "D" et "C", et traitez tout autre élément comme un entier. La conversion avec le parseur du langage prend en charge un signe moins en tête, donc "-30000" devient -30000.

Python

def calPoints(operations):
    # Écrivez le code ici

Cas de test

Cas 1

Cas 2

Cas 3

Entrée

operations = ["4", "-2", "D", "+", "C", "7"]

Attendu