Baseball Game

+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.

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

Как добавить операцию, которая отменяет последнее "C", восстанавливая отменённый результат, за время O(1)?

Подсказки

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

Открыто 0 из 3

Решение

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

Собирай запись в стеке, а в конце сложи значения

Идея

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

Когда операции заканчиваются, в списке остаются ровно те оценки, которые учитываются, поэтому сложите их: время 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 равным сумме в стеке: каждое добавление помещает в сумму новый балл, а каждое "C" вычитает балл, который оно извлекает. Стек должен оставаться, потому что при отмене нужно знать, какой балл убрать. В первом примере сумма меняется так: 4, 2, -2, -8; при отмене из неё снова вычитается -6, получается -2, а 7 доводит сумму до 5.

Это один проход за время O(n), и ответ готов после любого префикса операций. Требуется O(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

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

Хранение только текущей суммы и двух последних результатов. В ["1", "2", "3", "C", "+"] для "+" нужны 1 и 2, а при хранении только двух результатов 1 уже не осталось.
Не вычитать отменённый результат из текущей суммы. Во втором примере в результате остаётся 18 вместо 0.
Определять, что запись является числом, по наличию в ней цифры. "-2" начинается со знака минус; сравнивайте запись с тремя символами, а всё остальное разбирайте с помощью целочисленного парсера языка.
Предполагать, что ответ положительный. Сумма ["-3", "D"] равна -9.

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

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

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

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

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

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

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

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

Тест #1

Тест #2

Тест #3

Аргумент

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

Ожидаемый вывод