Выбор ответа Junior Стек и монотонный стек спрашивают часто обновлено
Правильные скобки
Вопрос
Проверить, что строка из ()[]{} сбалансирована. Какая структура данных нужна?
Попробуйте сами
Выберите вариант, и откроется разбор.
Показать ответ и разбор
Коротко
Правильный ответ: Стек: открывающие кладём, закрывающую сверяем с вершиной. Последняя открытая скобка закрывается первой: это LIFO, стек.
Варианты ответа
- Очередь: скобки сверяются в порядке поступления
- Счётчик открытых скобок, который не уходит в минус
- Стек: открывающие кладём, закрывающую сверяем с вершинойправильный ответ
- Set скобок: проверить, что каждой открывающей есть пара
Разбор
Последняя открытая скобка закрывается первой: это LIFO, стек. В конце стек должен быть пуст. O(n) времени и памяти.
- Очередь FIFO не отражает вложенность.
- Один счётчик не видит порядок типов:
([)]пройдёт проверку счётчиком, но неверна. - Set не хранит порядок и повторы.
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.