Бесплатный 5-дневный мини-курс: https://backtobackswe.com
Попробуйте нашу полную платформу: https://backtobackswe.com/pricing
📹 Интуитивно понятные видеообъяснения
🏃 Запускайте код по мере обучения
💾 Сохраняйте прогресс
❓Новые, ранее не рассматривавшиеся вопросы
🔎 Получить все решения
Вопрос: Дан массив с последовательностью, представляющей выражение RPN. Вычислите выражение в обратной польской нотации.
Это одна из классических задач. Это классический пример того, когда поведение LIFO благоприятно для решения определенных задач.
Чтобы получить выражение RPN, нам по определению нужны 2 вещи:
Одна цифра или последовательность цифр.
Оно имеет вид ["A", "B", "o"], где A и B — целые числа, а o — оператор (+, -, * или /).
Примеры:
[ "3", "4", "+", "2", "*", "1", "+" ]
то же самое, что и ( ( 3 + 4 ) * 2 ) + 1
что, в свою очередь, то же самое, что и ( 3 + 4 ) * 2 + 1 из-за порядка операций.
Пример 2:
[ "1", "1", "+", "2", "2", "*", "+" ]
Подход
Это классическая задача на стек, давайте просто решим её.
Две ключевые операции:
Когда мы видим цифру, мы помещаем её в стек.
Когда мы видим операцию, мы выполняем 2 извлечения, применяем операцию к двум значениям (первый извлечённый элемент помещается слева от знака, второй — справа от знака), а затем помещаем результат обратно в стек, чтобы мы могли работать с ним дальше.
Если это корректное выражение RPN, то у нас не должно возникнуть проблем с несовпадениями и нулевыми указателями. Всегда уточняйте у своего интервьюера, что это корректная строка RPN.
Сложности
n — длина выражения RPN
Время: O(n)
Мы обработаем все n операторов/операндов в выражении. Каждый из них потребует либо вставки/выталкивания O(1), либо арифметических вычислений O(1).
Арифметические операции занимают O(1).
Вставки и выталкивания O(1).
Пространство: O(d)
Пусть d — общее количество операндов (чисел).
Пусть b — количество операторов (+, -, *, /).
Если у нас d цифр и b операторов, где d + b = n, мы точно не будем использовать O(d + b) памяти (операторы не помещаются в стек).
В худшем случае у нас есть только числа, за которыми следуют операторы. И у нас будет стек высотой d цифр. Поэтому мы можем привязаться к этому.
++++++++++++++++++++++++++++++++++++++++++++++++++++
HackerRank: / @hackerrankofficial
Тушар Рой: / tusharroy2525
GeeksForGeeks: / @geeksforgeeksvideos
Джарвис Джонсон: / vsympathyv
Успех в технологиях: / @successintech
++++++++++++++++++++++++++++++++++++++++++++++++++++
Этот вопрос — номер 9.2 в разделе «Элементы собеседований по программированию». Аднан Азиз, Цун-Сиен Ли и Амит Пракаш.
Информация по комментариям в разработке