Валидация скобочной последовательности (3 вида скобок)

Нельзя обойти стороной одну из самых мейнстримных задач на собеседованиях — валидация скобочной последовательности. Тот читатель, кто время от времени ходит по собесдованиям и имеет десяток-два продйенных алгоритмических секции, почти со стопроцентной вероятностью сталкивался с ней. Она настолько популярна, что давно перешла из разряда средне-сложных в разряд легких и, скорее всего, в известных компаниях, практикующих эту секцию, если и попадется вам, то в самом начале собеседования, как «разминочная».

Но, все же, разобрать ее просто необходимо. Эта задача имеет каноническое оптимальное решение через стек, которое от вас будет ждать любой интервьер (хотя, безусловно, это не единственно возможный подход).

Сложность: 🟢 Легкая

ℹ️ Описание

Дана строка, состоящий только из скобок «(», «)», «{», «}», «[» и «]». Напишите функцию, определяющую, является ли строка правильной скобочной последовательностью.

⚠️ Ограничения

🔹Длина строки от 1 до 10000 символов
🔹Строка состоит только из символов «(», «)», «{», «}», «[» и «]».


1️⃣ Пример

Входящие данные: "()"
Ответ: true
Объяснение: все открывающие скобки имеют соотвествующую закрывающую скобку, открывающие и закрывающие скобки расположены в правильном порядке, в строке нет закрывающих скобок без предварительно открывающей пары.

2️⃣ Пример

Входящие данные: "()[]{}"
Ответ: true
Объяснение: все открывающие скобки имеют соотвествующую закрывающую скобку, открывающие и закрывающие скобки расположены в правильном порядке, в строке нет закрывающих скобок без предварительно открывающей пары.

3️⃣ Пример

Входящие данные: "(]"
Ответ: false
Объяснение: открывающая и закрывающая скобки относятся к разным типам скобок


✅ Решение

Для решения задачи мы воспользуемся структурой данных стек (можно реализовать через обычный массив). Будем идти по строчке посимвольно.

🔘 Если символ — одна из открывающих скобок, кладем ее в стек.

🔘 Если символ — одна из закрывающих скобок, пытаемся извлечь верхний элемент из стека:
⏺ если в стеке нет эементов, значит последовательность невалидна и мы столкнулись с закрывающей скобкой для которой нет открывающей;
⏺ если верхний элемент — это открывающая скобка другого типа, значит последовательность невалидна и мы столкнулись с кейсом неверной пары (например "(]");
⏺ если верхний элемент — это открывающая скобка нужного типа, то просто идем дальше.

🔘 Если после итерации по всем симолам строки в стеке остались какие-либо элементы, значит последовательность невалидна (есть открывающие скобки, для которых нет открывающей пары). В противном случае — последовательность валидна.

Посмотреть реализацию

🅾️ Оценка сложности

По времени
Чтобы провалидировать строку, нам достаточно один раз проитерироваться по всем символам, то есть сложность равна O(n),
где n — длина строки.

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

#strings #stack #easy

Столкновение астероидов

Привет, друзья. Помните задачку на валидацию скобочной последовательности? Она считается очень легкой и на leetcode она в разряде easy задач. Я же никогда не считал, что ее по сложности можно сравнить с каким-нибудь слиянием отсортированных массивов. Львиная доля ее легкости заключается в мейнстримности этой задачи - едва ли не каждый знает каноническое решение через стек. А между тем, это далеко не единственная задача, которую можно оптимально решить через эту структуру данных. И, если попросить кандидата решить немного другую задачу с похожей идеей решения, то вполне можно вогнать человека в ступор :). Как всегда, дело в умении распознать класс задачи, а вот применить паттерн решения уже не составляет труда.

Поэтому, сегодня мы разберем задачу о столкновении астероидов.

P.S. Если быть честным, у меня ушло около 40 минут на реализацию и отладку решения через 2 индекса, прежде чем я догадался воспользоваться стеком. Решение через стек вышло сильно лаконичнее и быстрее в реализации 🙂

Сложность: 🟠 Средняя

ℹ️ Описание

Напишите функцию, которая будет рассчитывать результаты столкновения астероидов.

Входные данные: массив целых ненулевых чисел. Каждое число обозначает массу астероида, знак - направление движения.

Выходные данные: массив целых ненулевых чисел. Массив будет описывать множество астероидов, их массу и направление, после того, как все астероиды, которые могут столкнуться, столкнутся.

Все астероиды движутся с одинаковой скоростью. Таким образом, астероиды, летящие в одном направлении никогда не столкнутся друг с другом.

В отличие от реальной жизни, при столкновении масса и направление движение астероидов после никак не изменяются. Меньший из двух полностью уничтожается, больший продолжает лететь в прежнем направлении, не меняя массу.

⚠️ Ограничения

- Количество астероидов (длина входного массива) находится в диапазоне от 2 до 10000
- Масса астероида лежит в диапазоне от 1 до 1000 (знак влияет только на направление движения)
- Астероидов с нулевой массой не существует

1️⃣Пример

Входящие данные

[]int{5,10,-5}

Ответ

[]int{5,10}

Пояснение

Первые два астероида движутся вправо, последний - влево. В результате, второй и третий астероид должны столкнуться. Второй астероид имеет большую массу, поэтому он полностью уничтожит третий.

2️⃣ Пример

Входящие данные

[]int{8,-8}

Ответ

[]int{}

Пояснение

Астероиды движутся навстречу друг другу и имеют одинаковую массу. В результате оба астероида будут уничтожены.


3️⃣ Пример

Входящие данные

[]int{10,2,-5}

Ответ

[]int{10}

Пояснение

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


✅ Решение

Посмотреть подробное объяснение решения

#stack #medium

Дневная температура

Всем привет!
Продолжаем закреплять знание структуры данных «стек» и умение определять этот паттерн. Мы уже разбирали самую мейнстримную задачу на валидацию скобочной последовательности. На прошлой неделе мы моделировали столкновение астероидов. Сегодня будем считать количество дней до ближайшего более теплого дня 🙂

Сложность: 🟠 Средняя

ℹ️ Описание

Напишите функцию, которая будет рассчитывать количество дней между текущим и днем с большей температурой.

Входные данные: Массив целых неотрицательных чисел. Каждое число в массиве, это температура в соответствующий день.

Выходные данные: Массив целых неотрицательных чисел. Каждое число в массиве, это количество дней от i'го дня до дня с большей температурой.

⚠️ Ограничения

- Количество дней (длина входного массива) находится в диапазоне от 1 до 100000
- Температура для каждого дня находится в диапазоне от 30 до 100

1️⃣Пример

Входящие данные

[73, 74, 75, 71, 69, 72, 76, 73]

Ответ

[1, 1, 4, 2, 1, 1, 0, 0]

2️⃣ Пример

Входящие данные

[30, 40, 50, 60]

Ответ

[1, 1, 1, 0]

3️⃣ Пример

Входящие данные

[0, 60, 90]

Ответ

[1, 1, 0]

✅ Решение

Посмотреть подробное объяснение решения

#stack #medium

Самая длинная подстрока, являющаяся валидной скобочной последовательностью

Всем привет!
Сегодня продолжаем одновременно 2 начинания: решать сложные задачи и решать задачи на валидные скобочные последовательности 🙂

Как я уже говорил ранее, классическая задача на валидацию скобочной последовательности считается легкой только из-за их мейнстримности: это чуть ли не первая задача, которую решают на алгоритмах, когда проходят стек. А как часто она попадается на интервью, страшно представить.

Но, на самом деле, эта задача не из простых и, стоит хоть немного отойти от классической формулировки, и из легкой она превращается в сложную. Так и в сегодняшней вариации — даже несмотря на то, что оптимальное решение использует все тот же самый стек (да и алгоритм в итоге очень несложный), догадался я до него не с первого раза.

Сложность: 🤬 Сложная

ℹ️ Описание

Напишите функцию для поиска самой длинной подстроки, являющейся правильной скобочной последовательностью.

⚠️ Ограничения

— Длина каждой строки от 0 до 30 000 символов
— Строка состоит из символов '(' и ')'

1️⃣ Пример
Входные данные

s := "(()"

Ответ

2

Самая длинная правильная скобочная последовательность — ().

2️⃣ Пример
Входные данные

s := ")()())"

Ответ

4

Самая длинная правильная скобочная последовательность - ()().

3️⃣ Пример
Входные данные

s := ""

Ответ

0

✅ Решение

Можно попробовать пойти с помощью брутфорса — взять всю строку (как самую длинную возможную подстроку) и проверить её на валидность. После уменьшить длину подстроки на единицу и проверить на валидность 2 возможные подстроки длиной n-1. Потом ещё на единицу и проверить три возможные подстроки длиной n-2. И так далее, пока не наткнёмся на первую валидную подстроку. Но такое решение будет слишком долгим — на LeetCode вы даже не сможете пройти все тест-кейсы из-за таймаута.

Чтобы найти более оптимальное решение, можно переформулировать задачу: самая длинная подстрока с валидной скобочной последовательностью — это максимальное расстояние между двумя невалидными подстроками. Осталось придумать, как с помощью стека мы можем вырезать все валидные подстроки из оригинальной строки, и задача будет решена 🙂

Посмотреть реализацию и объяснения в блоге.

#stack #hard