Baseball Game

Q: Как отличить число от операции в Baseball Game?

Сначала сравни запись с тремя символами "+" , "D" и "C" , а всё остальное считай целым числом. Преобразование с помощью парсера языка обрабатывает знак минус в начале, поэтому "-30000" становится -30000 .

ЛегкоСтек

+10

Ты ведёшь счёт в необычной игре. Список operations читается слева направо, и каждая запись изменяет список очков. Целое число, например "7" или "-2", добавляет это очко в список. "+" добавляет очко, равное сумме двух последних очков, "D" добавляет очко, равное удвоенному последнему очку, а "C" навсегда удаляет последнее очко из списка.

Напиши функцию с именем calPoints, которая возвращает сумму очков, оставшихся в списке после последней операции. Сумма пустого списка равна 0.

Функция

calPoints(operations: string-array) → integer

operationsstring-array: операции по порядку: целые числа в виде текста или "+", "D", "C"
Возвращаетinteger: сумма результатов, оставшихся в записи к концу

Ограничения

1 ≤ operations.length ≤ 5000
Каждая запись — это "+", "D", "C" или целое число, записанное в десятичной системе счисления, где -3 × 10⁴ ≤ value ≤ 3 × 10⁴.
Каждая операция допустима: "+" появляется только тогда, когда запись содержит как минимум две оценки, а "D" и "C" — только тогда, когда она содержит как минимум одну.
Каждый результат в записи и итоговая сумма помещаются в 32-разрядное целое число со знаком.

Примеры

Ввод: operations = ["4", "-2", "D", "+", "C", "7"]
Вывод: 5
Пояснение: Запись увеличивается до [4, -2], "D" добавляет -4, "+" добавляет -2 + -4 = -6, "C" удаляет это значение -6, а 7 добавляется последним. Сумма записи [4, -2, -4, 7] равна 5.

Ввод: operations = ["6", "D", "C", "C"]
Вывод: 0
Пояснение: "D" добавляет 12 после 6, затем две записи "C" удаляют 12 и 6. Ничего не остаётся, поэтому ответ — 0.

Ввод: operations = ["1", "2", "+", "+", "D"]
Вывод: 21
Пояснение: Две записи "+" складывают 1 + 2 = 3, а затем 2 + 3 = 5, а "D" добавляет 10. Сумма записи [1, 2, 3, 5, 10] равна 21.

+13 скрытых тестов при отправке

Дополнительный вопрос

Можешь возвращать сумму, не прибавляя запись в конце, чтобы каждая операция, включая отмену, занимала O(1) времени?

Подсказки

Открывайте по одной. Каждая подсказывает чуть больше.

Открыто 0 из 3

Решение

Каждая операция обращается к последним результатам, а "C" может убирать результаты по одному, поэтому результаты перед отменённым снова становятся последними. Этот принцип «последним пришёл — первым ушёл» — это и есть стек. Добавляй каждый новый результат в стек, извлекай верхний элемент при "C" и считывай одну или две верхние записи для "D" и "+".

Формируйте результат в стеке, а в конце подсчитайте сумму

Идея

Храни записи в виде списка, где самая новая оценка находится в конце. Тогда каждая операция затрагивает только конец списка: целое число добавляется в конец, "D" добавляет в конец удвоенное последнее значение, "+" добавляет в конец сумму двух последних значений, а "C" удаляет последнее значение.

Почему достаточно стека: после "C" вторая по новизне оценка становится самой новой, и именно её должна прочитать следующая операция "D" или "+". Удаление последнего значения даёт это бесплатно. В первом примере "C" удаляет -6 и оставляет [4, -2, -4], поэтому любая последующая операция "+" снова сложит -2 + -4.

Когда операции закончатся, в списке останутся ровно те оценки, которые учитываются. Сложи их. Каждая операция выполняется за O(1), а итоговая сумма — за O(n), поэтому вся последовательность занимает O(n) времени и O(n) памяти для стека.

Алгоритм

Начни с пустого стека record.
Для "+" добавь в стек сумму двух верхних элементов. Для "D" добавь в стек удвоенное значение верхнего элемента.
Для "C" извлеки верхний элемент из стека.
В противном случае запись является числом: преобразуй текст в целое число и добавь его в стек.
Верни сумму всех оставшихся элементов в стеке.

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)

Стек с накапливаемой суммой

Идея

Последний цикл по стеку — это лишняя работа, которой можно избежать. Храни переменную total, которая всегда равна сумме элементов стека. Каждое добавление помещает новый счёт в total, а каждое "C" вычитает счёт, который оно удаляет.

Стек всё ещё нужен. При отмене нужно знать, какой счёт вычесть из общей суммы, а "+" и "D" должны знать последние счета после всех отмен. В первом примере сумма меняется так: 4, 2, -2, -8, затем отмена убирает -6, и получается -2, а последнее значение 7 доводит сумму до 5.

Время работы — O(n) за один проход, и ответ готов после любого префикса операций, что важно, когда значения счёта поступают в реальном времени. Затраты памяти — O(n): все n операций могут оказаться числами, которые останутся в записи.

Алгоритм

Начни с пустого стека record и total = 0.
Для "C" извлеки верхнюю оценку и вычти её из total.
Иначе вычисли новую оценку: сумму двух верхних для "+", удвоенное значение верхней для "D" или само целое число.
Добавь новую оценку в стек и прибавь её к total.
Верни 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

Ловушки и крайние случаи

Правила короткие, поэтому большинство ошибок возникает из-за того, что вы читаете не ту сумму или неправильно разбираете текст.

Сохранять только текущую сумму и две последние оценки. После "C" вам нужна оценка, которая была до этих двух, поэтому после отмены следующая операция "+" использует устаревшие значения. Сохраняйте весь стек.
Забывать, что отменённые оценки влияют на сумму. При подсчёте текущей суммы "C" должна вычесть извлечённую оценку, а не игнорировать её.
Разбирать отрицательные оценки вручную и терять знак. Используйте целочисленный парсер языка, который считывает "-2" как -2.
Проверять, является ли первый символ цифрой, чтобы определить, что запись — это число. "-5" начинается со знака минус; проверяйте три символа, а всё остальное считайте числом.
Предполагать, что ответ положительный. Отрицательные оценки и отмены могут привести к отрицательной сумме или к 0, если были отменены все оценки.

Частые вопросы4

Какова временная сложность игры в бейсбол?

Каждая операция выполняет постоянный объём работы с вершиной стека, поэтому обработка n операций занимает время O(n). Суммирование значений в стеке в конце занимает ещё не более O(n), а текущая сумма позволяет избежать даже этого. Стек использует O(n) памяти, когда большинство операций добавляют очки.

Почему стек — подходящая структура данных для игры в бейсбол?

Каждое правило считывает или удаляет самые последние результаты, а отмена показывает результат, который был до них. Это порядок «последним пришёл — первым вышел», который обеспечивает стек с операциями добавления, удаления и просмотра вершины за O(1). Обычный массив или список, используемый только с конца, подходит на роль стека в любом языке.

Можно ли решить задачу Baseball Game, используя O(1) дополнительной памяти?

Не в общем случае. Последовательность чисел, за которой следует последовательность записей "C", отменяет их в обратном порядке, поэтому нужно запоминать каждое число, пока не станет известно, будет ли оно отменено. В худшем случае для этого требуется O(n) памяти. Накопительный итог избавляет от заключительного прохода, но не от стека.

Как отличить число от операции в Baseball Game?

Сначала сравни запись с тремя символами "+", "D" и "C", а всё остальное считай целым числом. Преобразование с помощью парсера языка обрабатывает знак минус в начале, поэтому "-30000" становится -30000.

Python

def calPoints(operations):
    # Напишите код здесь

Тестовые случаи

Случай 1

Случай 2

Случай 3

Ввод

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

Ожидается