Baseball Game

FacilePile

+10

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

Écris une fonction nommée calPoints qui renvoie la somme des scores restant dans le registre après la dernière opération. La somme d’un registre vide est 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 dossier à 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" uniquement lorsqu’il en contient au moins un.
Chaque score de l’enregistrement ainsi que la somme finale tiennent dans un entier signé sur 32 bits.

Exemples

Entrée: operations = ["4", "-2", "D", "+", "C", "7"]
Sortie: 5
Explication: La liste s’agrandit jusqu’à [4, -2], "D" ajoute -4, "+" ajoute -2 + -4 = -6, "C" supprime ce -6, et 7 est ajouté en dernier. La liste [4, -2, -4, 7] donne une somme de 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] donne une somme de 21.

Pour aller plus loin

Comment ajouterais-tu une opération qui annule le dernier "C" et rétablit le score annulé, en O(1) ?

Indices

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

0 sur 3 ouverts

Solution

Chaque opération lit les scores les plus récents, et "C" peut les retirer un à la fois, de sorte que les scores plus anciens redeviennent les plus récents. C’est le principe du dernier entré, premier sorti : empile chaque nouveau score, dépile avec "C", et lis le ou les deux éléments au sommet pour "D" et "+".

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

Intuition

Conservez les scores dans une liste, le plus récent à la fin, afin que chaque opération ne touche qu’à la fin. Après un "C", l’avant-dernier score devient le plus récent, et un "D" ou un "+" ultérieur doit le lire ; le retrait le révèle. Dans le premier exemple, "C" retire -6 et laisse [4, -2, -4].

Quand les opérations sont terminées, la liste contient exactement les scores à prendre en compte : additionnez-les. Complexité : O(n) en temps et O(n) en espace.

Algorithme

Commence par 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 tous les éléments restants 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 cumulé

Intuition

Garde total égal à la somme de la pile : chaque empilement ajoute le nouveau score et chaque "C" soustrait le score qu’il dépile. La pile doit être conservée, car une annulation doit savoir quel score retirer. Dans le premier exemple, le total évolue ainsi : 4, 2, -2, -8 ; l’annulation retire -6, ce qui le ramène à -2, et 7 le porte à 5.

Il s’agit d’un seul parcours en temps O(n), et la réponse est prête après n’importe quel préfixe des opérations. L’espace utilisé est de O(n), puisque chaque opération peut être un nombre qui reste dans la pile.

Algorithme

Commencez avec une pile vide record et total = 0.
Pour "C", dépilez le score au 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.
Renvoyez 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

Ne conserver qu’un total courant et les deux derniers scores. Dans ["1", "2", "3", "C", "+"], "+" a besoin de 1 et de 2, et une fenêtre de deux scores a perdu le 1.
Ne pas soustraire un score annulé du total courant. Dans le deuxième exemple, cela laisse 18 au lieu de 0.
Décider qu’une entrée est un nombre en vérifiant si elle contient un chiffre. "-2" commence par un signe moins ; compare avec les trois symboles et analyse tout le reste avec le parseur d’entiers du langage.
Supposer que la réponse est positive. ["-3", "D"] donne une somme de -9.

Questions fréquentes3

Quelle est la complexité temporelle du jeu de baseball ?

Chaque opération effectue un travail constant au sommet de la pile ; ainsi, n opérations prennent un temps de O(n). La pile occupe un espace de O(n) lorsque la plupart des opérations ajoutent des scores.

Pourquoi une pile est-elle la structure de données appropriée pour un match de baseball ?

Chaque règle lit ou supprime les scores les plus récents, et une annulation révèle le score qui les précède. C’est le principe du dernier entré, premier sorti, que permet une pile avec des opérations d’ajout, de retrait et de consultation en O(1). Un tableau utilisé uniquement à son extrémité fonctionne comme une pile.

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

Pas en général. Une séquence de nombres suivie d’une séquence 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.

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

Test #1

Test #2

Test #3

Argument

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

Résultat attendu