Решаю задачу с собеседования в Тинькофф: valid parentheses

preview_player
Показать описание

Консультации:

Рекомендации по теме
Комментарии
Автор

Увидел видео, прошел решать. Часа 4 сидел ифы писал. На следующий день вспомнил про стек и решил за десять минут😂

Balck
Автор

int l = 0;
while(l != str.Length)
{
l = str.Length;
str = str.Replace("{}", "")
.Replace("[]", "")
.Replace("()", "");
}

return str.Length == 0;

Если на входе идут ещё значения (например цифры или пробелы), кроме скобочек, то нужно взять только всё скобочки и вкинуть их в строку.

Работает всегда и довольно быстро. Код на C#

rememberme
Автор

Здравствуйте, хотелось бы увидеть задачи по бинарным деревьям

Daedalic_Artist
Автор

Думаю на скале задачу можно решить проще.

Нам нужна пустая очередь где мы будем хранить входы
Далее нужна мапа с возможными кейсами

def isSeqCorrect(l: List[String], map: Map[String, String], queue: Queue[String]): Boolean = {
l match {
case ::(head, next) => {
val analoq = map.get(head)
analoq match {
case Some(value) =>
if (queue.contains(value)) {
val newQueue = queue.dequeue._2
isSeqCorrect(next, map, newQueue)
} else {
val newQueue = queue.enqueue(value)
isSeqCorrect(next, map, newQueue)
}
case None => false
}
}
case Nil => true
}
}

println(isSeqCorrect(List("(", "{", "[", "]", "}", ")"), Map("(" -> ")", ")" -> ")", "[" -> "]", "]" -> "]", "{" -> "}", "}" -> "}"), Queue.empty[String]))

cavidxalilov
Автор

Спасибо за Ваш труд!
Возник вопрос: Что если скобки будет идти в такой последовательности ((( )) - как в обычной строке. Т.е. подряд может стоять несколько открывающихся и необходимо определить, все ли они закрываются...

Чикибряк-сы
Автор

А если бы скобочек было 10 типов, то в условии 10 "или" писал бы? Есть более лаконичное решение этой задачи.

MrROnic
Автор

Меня удивило время рантайм. Низкоуровневый быстрый c++ справился за 5ms, а у меня жирная неповоротливая java за 1ms, правда она памяти сожрала 45Mb.

Balck
Автор

"{[]}" - мне предложил такой вариант - видимо не математика, не стэк с этим не справятся

nabels
Автор

4:56, вредное решение какое-то получилось))

vladimirtaburkin