Baseball Game

+10

Você mantém a pontuação de um jogo incomum. Leia operations da esquerda para a direita; cada entrada altera um registro de pontuações. Um número inteiro como "7" ou "-2" adiciona essa pontuação. "+" adiciona a soma das duas pontuações mais recentes, "D" adiciona o dobro da pontuação mais recente, e "C" remove definitivamente a pontuação mais recente.

Escreva uma função chamada calPoints que retorne a soma das pontuações que restarem no registro após a última operação. Um registro vazio soma 0.

Função

calPoints(operations: string-array) → integer

operationsstring-array: as operações em ordem: inteiros como texto, ou "+", "D", "C"
Retornainteger: a soma das pontuações que ainda estão no registro ao final

Restrições

1 ≤ operations.length ≤ 5000
Cada entrada é "+", "D", "C" ou um número inteiro escrito em decimal com -3 × 10⁴ ≤ value ≤ 3 × 10⁴.
Todas as operações são válidas: "+" só aparece quando o registro contém pelo menos duas pontuações, "D" e "C" só quando contém pelo menos uma.
Cada pontuação no registro e a soma final cabem em um inteiro com sinal de 32 bits.

Exemplos

Entrada: operations = ["4", "-2", "D", "+", "C", "7"]
Saída: 5
Explicação: O registro cresce para [4, -2], "D" adiciona -4, "+" adiciona -2 + -4 = -6, "C" remove esse -6, e 7 é adicionado por último. A soma do registro [4, -2, -4, 7] é 5.

Entrada: operations = ["6", "D", "C", "C"]
Saída: 0
Explicação: "D" adiciona 12 depois do 6, então as duas entradas "C" removem 12 e 6. Não resta nada, então a resposta é 0.

Entrada: operations = ["1", "2", "+", "+", "D"]
Saída: 21
Explicação: As duas entradas "+" somam 1 + 2 = 3 e depois 2 + 3 = 5, e "D" adiciona 10. O registro [1, 2, 3, 5, 10] soma 21.

Para ir além

Como você adicionaria uma operação que desfaz o "C" mais recente, colocando a pontuação cancelada de volta, em tempo O(1)?

Dicas

Abra uma de cada vez. Cada uma revela um pouco mais.

0 de 3 abertas

Solução

Cada operação lê as pontuações mais recentes, e "C" pode removê-las uma de cada vez, fazendo com que as pontuações mais antigas voltem a ser as mais recentes. Isso é o último a entrar, primeiro a sair: empilhe cada nova pontuação, desempilhe ao encontrar "C" e leia a pontuação do topo ou as duas do topo para "D" e "+".

Monte o registro em uma pilha e some tudo no final

Intuição

Mantenha o registro como uma lista com a pontuação mais recente no final, para que cada operação mexa apenas no final. Depois de um "C", a segunda pontuação mais recente se torna a mais recente, e um "D" ou "+" posterior deve lê-la; remover o último elemento a expõe. No primeiro exemplo, "C" remove -6 e deixa [4, -2, -4].

Quando as operações acabarem, a lista conterá exatamente as pontuações que contam, então some-as: tempo O(n) e espaço O(n).

Algoritmo

Comece com uma pilha vazia record.
Para "+", empilhe a soma das duas entradas do topo. Para "D", empilhe o dobro da entrada do topo.
Para "C", remova a entrada do topo.
Caso contrário, a entrada é um número: converta o texto em um inteiro e empilhe-o.
Retorne a soma de tudo o que restou na pilha.

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)

Pilha com total acumulado

Intuição

Mantenha total igual à soma da pilha: cada inserção adiciona a nova pontuação e cada "C" subtrai a pontuação que remove. A pilha precisa ser mantida, pois um cancelamento precisa saber qual pontuação retirar. No primeiro exemplo, o total passa por 4, 2, -2, -8, o cancelamento retira -6, resultando em -2, e 7 o leva a 5.

Isso é uma única passagem em tempo O(n), e a resposta está pronta após qualquer prefixo das operações. O espaço é O(n), já que cada operação pode ser um número que permanece.

Algoritmo

Comece com uma pilha vazia record e total = 0.
Para "C", remova a pontuação do topo e subtraia-a de total.
Caso contrário, calcule a nova pontuação: a soma das duas do topo para "+", o dobro da pontuação do topo para "D" ou o próprio número inteiro.
Empilhe a nova pontuação e some-a a total.
Retorne 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

Armadilhas e casos extremos

Manter apenas um total acumulado e as duas últimas pontuações. Em ["1", "2", "3", "C", "+"], "+" precisa de 1 e 2, e uma janela de duas pontuações já perdeu o 1.
Não subtrair uma pontuação cancelada do total acumulado. No segundo exemplo, isso resulta em 18 em vez de 0.
Decidir que uma entrada é um número verificando se contém um dígito. "-2" começa com um sinal de menos; compare com os três símbolos e analise todo o restante com o analisador de inteiros da linguagem.
Presumir que a resposta é positiva. ["-3", "D"] soma -9.

Perguntas frequentes3

Qual é a complexidade de tempo de Baseball Game?

Cada operação realiza trabalho constante no topo da pilha, então n operações levam tempo O(n). A pilha ocupa espaço O(n) quando a maioria das operações adiciona pontuações.

Por que uma pilha é a estrutura de dados certa para o Baseball Game?

Cada regra lê ou remove as pontuações mais recentes, e um cancelamento revela a pontuação anterior. Isso é último a entrar, primeiro a sair, algo que uma pilha oferece com operações de inserir, remover e consultar o topo em O(1). Um array usado apenas em sua extremidade funciona como pilha.

É possível resolver o Baseball Game usando O(1) de espaço extra?

Não, em geral. Uma sequência de números seguida por uma sequência de entradas "C" cancela esses números na ordem inversa, então você precisa se lembrar de cada número até saber se ele será cancelado. Isso exige memória O(n) no pior caso.

def calPoints(operations):
    # Escreva o código aqui

Teste #1

Teste #2

Teste #3

Argumento

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

Saída Esperada