Baseball Game

Q: Como distinguir um número de uma operação em Baseball Game?

Compare a entrada primeiro com os três símbolos "+" , "D" e "C" , e trate qualquer outra coisa como um inteiro. A conversão com o analisador da linguagem lida com um sinal de menos no início, então "-30000" se torna -30000 .

FácilPilha

+10

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

Escreva uma função chamada calPoints que retorna a soma das pontuações restantes no registro após a última operação. Um registro vazio tem 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 ainda registradas 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" somente 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 entra por último. O registro [4, -2, -4, 7] soma 5.

Entrada: operations = ["6", "D", "C", "C"]
Saída: 0
Explicação: "D" adiciona 12 após o 6, então as duas entradas "C" removem 12 e 6. Não sobra 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.

+13 testes ocultos ao enviar

Para ir além

Você consegue retornar a soma sem somar o registro no final, de modo que cada operação, inclusive um cancelamento, leve O(1) tempo?

Dicas

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

0 de 3 abertas

Solução

Cada operação considera as pontuações mais recentes, e "C" pode remover pontuações uma de cada vez, fazendo com que as pontuações anteriores à cancelada voltem a ser as mais recentes. Esse padrão de último a entrar, primeiro a sair é exatamente uma pilha. Empilhe cada nova pontuação, desempilhe ao encontrar "C" e leia a entrada do topo ou as duas entradas do topo para "D" e "+".

Monte o registro em uma pilha e some tudo no final

Intuição

Mantenha o registro como uma lista em que a pontuação mais recente fica no final. Assim, cada operação mexe apenas no final da lista: um número inteiro é adicionado, "D" adiciona o dobro do último elemento, "+" adiciona a soma dos dois últimos elementos e "C" remove o último elemento.

Por que uma pilha é suficiente: depois de um "C", a pontuação que era a penúltima passa a ser a mais recente, e é essa que uma operação "D" ou "+" seguinte precisa ler. Remover o último elemento resolve isso automaticamente. No primeiro exemplo, "C" remove -6 e deixa [4, -2, -4], então qualquer "+" posterior somaria -2 + -4 novamente.

Quando as operações acabam, a lista contém exatamente as pontuações válidas. Some-as. Cada operação é O(1) e a soma final é O(n), então a execução toda leva tempo O(n) e usa espaço O(n) para a pilha.

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 um total acumulado

Intuição

O loop final pela pilha é trabalho extra que você pode evitar. Mantenha uma variável total que seja sempre igual à soma da pilha. Cada inserção adiciona a nova pontuação a total, e cada "C" subtrai a pontuação que remove.

A pilha ainda é necessária. Um cancelamento precisa saber qual pontuação retirar do total, e "+" e "D" precisam saber as pontuações mais recentes após quaisquer cancelamentos. No primeiro exemplo, o total passa por 4, 2, -2, -8; então, o cancelamento retira o -6, resultando em -2, e o 7 final o leva a 5.

O tempo é O(n) com uma única passagem, e a resposta fica pronta após qualquer prefixo das operações, o que importa quando as pontuações chegam em tempo real. O espaço é O(n): todas as n operações podem ser números que permanecem no registro.

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 pontuações do topo para "+", o dobro da pontuação do topo para "D" ou o próprio 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

As regras são curtas, então a maioria dos erros vem de ler a pontuação errada ou de interpretar o texto incorretamente.

Manter apenas um total acumulado e as duas últimas pontuações. Depois de um "C", você precisa da pontuação anterior a essas duas, então um cancelamento seguido de "+" lê valores desatualizados. Mantenha a pilha inteira.
Esquecer que as pontuações canceladas são removidas do total. Com um total acumulado, "C" deve subtrair a pontuação removida, não ignorá-la.
Interpretar pontuações negativas manualmente e perder o sinal. Use o analisador de inteiros da linguagem, que lê "-2" como -2.
Verificar se há um dígito para decidir se uma entrada é um número. "-5" começa com um sinal de menos; verifique os três símbolos e trate todo o resto como um número.
Supor que a resposta é positiva. Pontuações negativas e cancelamentos podem resultar em uma soma negativa, ou em 0 quando todas as pontuações foram canceladas.

Perguntas frequentes4

Qual é a complexidade de tempo do jogo de beisebol?

Cada operação realiza uma quantidade constante de trabalho no topo da pilha, então processar n operações leva O(n) de tempo. Somar os valores da pilha no final leva, no máximo, mais O(n), e um total acumulado elimina até mesmo isso. A pilha usa O(n) de espaço quando a maioria das operações adiciona pontuações.

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

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

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

Não em geral. Uma sequência de números seguida por uma sequência de entradas "C" as cancela 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. Um total acumulado elimina a passagem final, não a pilha.

Como distinguir um número de uma operação em Baseball Game?

Compare a entrada primeiro com os três símbolos "+", "D" e "C", e trate qualquer outra coisa como um inteiro. A conversão com o analisador da linguagem lida com um sinal de menos no início, então "-30000" se torna -30000.

Python

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

Casos de teste

Caso 1

Caso 2

Caso 3

Entrada

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

Esperado