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

11

Мне дали следующую проблему во время интервью:

Дает строку, которая содержит некоторую смесь символов (без скобок или фигурных скобок - только символы) с другими буквенно-цифровыми символами, идентифицирует все символы без соответствующих имен.

Например, в строке ") (ab))" индексы 0 и 5 содержат символы, которые не имеют соответствующего имени.

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

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

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

Может кто-нибудь уточнить решение, которое она предложила?

temporary_user_name
источник
1
Возможно, нам сначала понадобятся некоторые разъяснения от вас. Являются ли первые или вторые в «(()» несбалансированными, последние или вторые по длине в (()) считаются несбалансированными? Или этого достаточно, чтобы идентифицировать любой набор паренов с наименьшим количеством кардиналов, чтобы их удаление оставало сбалансированными оставшиеся парены? Или что-то другое? Или эта часть интервью такова, что ответ может просто выдвинуть какую-либо обоснованную спецификацию?
Джон Л.
Я бы сказал, что это не имеет значения, до вас. Удалите любой набор, который оставляет остаток сбалансированным.
temporary_user_name
5
Тогда удалите их всех; P
Veedrac
@Veedrac, конечно (как вы знаете), постер забыл слово «минимальный» в «Удалить любой минимальный набор…».
LSpice
Я не «забыл об этом» сам по себе, а скорее упустил его, потому что он не показался мне важной спецификацией, поскольку есть только один набор, который можно удалить, чтобы сделать его сбалансированным, помимо «всех», который конечно побеждает цель упражнения.
временное_имя_пользователя

Ответы:

17

Так как это происходит из опыта программирования, а не из теоретического упражнения в области компьютерных наук, я предполагаю, что для сохранения индекса в строке требуется память . В теоретической информатике это будет означать использование модели RAM; с машинами Тьюринга вы не можете этого сделать, и вам понадобится память для хранения индекса в строке длиной .O(1)Θ(log(n))n

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

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

Итак , что же содержит этот стек? Она никогда не будет содержать ()(открывающую скобку с последующей закрывающей скобкой), так как всякий раз , когда )появляются вы попы (вместо толкая ). Таким образом , стек всегда в форме )…)(…(- связка закрытия скобки следует связка открытия скобок.

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

Если вы обрабатываете строку слева направо, используя эти два счетчика, то в конце вы получите количество несовпадающих закрывающих скобок и количество несовпадающих открывающих скобок.

Если вы хотите сообщить о позиции несовпадающих скобок в конце, вам нужно запомнить положение каждой скобки. Это потребует памяти в худшем случае. Но вам не нужно ждать до конца, чтобы произвести вывод. Как только вы обнаружите несоответствующую закрывающую скобку, вы узнаете, что она не соответствует, поэтому выведите ее сейчас. И тогда вы не собираетесь использовать количество несовпадающих закрывающих скобок для чего-либо, поэтому просто держите счетчик несоответствующих открывающих скобок.Θ(n)

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

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

Упражнение 1: запишите это в формальной записи (математика, псевдокод или ваш любимый язык программирования).

Упражнение 2: убедите себя в том, что это тот же алгоритм, что и в Apass.Jack , только что объясненный по-другому.

Жиль "ТАК - прекрати быть злым"
источник
О, очень хорошо, Жиль, очень хорошо объяснил. Теперь я прекрасно понимаю. Прошло довольно много лет с тех пор, как я получил от вас ответ на один из моих вопросов.
temporary_user_name
«Если вы хотите сообщить о позиции несовпадающих скобок в конце, вам нужно запомнить положение каждой скобки». Не совсем. Линейное время не означает , что один проход. Вы можете сделать второй проход, чтобы найти скобки в несоответствующей стороне и отметить их.
мычат Duck
Для последнего шага вам не нужно запускать его в обратном порядке, вы можете просто пометить последний N "(" как несоответствие.
Mooing Duck
1
@ MooingDuck Это не работает. Например (().
orlp
Хотя мне действительно нравится этот ответ, меня что-то беспокоит. Это что-то: «Мне как-то нужно запомнить положение. И я думаю, что у меня есть проблема с этим: как вы« выводите текущий индекс », не потребляя память (или довольно специфический контекст, в котором ваши выходные данные потребляются таким образом, что порядок ваших выходных данных не имеет значения)
Эдуард
8

Поскольку мы можем просто игнорировать все буквенно-цифровые символы, мы будем предполагать, что строка теперь содержит только круглые скобки. Как и в вопросе, есть только один вид скобок, "()".

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

Вот алгоритм. В двух словах, он сначала вычисляет поворотный момент. Затем он выводит дополнительную закрывающую скобку, сканируя строку от начала вправо до точки поворота. Симметрично выводит лишнюю открывающую скобку, сканируя от конца влево до точки поворота.


Позвольте strбыть строкой как массив символов, чей размер равен .n

Инициализировать turning_point=0, maximum_count=0, count=0. Для каждого iиз них 0необходимо n-1сделать следующее.

  1. Если str[i] = ')'добавить 1 к count; в противном случае вычтите 1.
  2. Если count > maximum_count, установите turning_point=iи maximum_count=count.

Теперь turning_pointуказатель поворота.

Сброс maximum_count=0, count=0. Для каждого iиз них 0необходимо turning_pointсделать следующее.

  1. Если str[i] = ')'добавить 1 к count; в противном случае вычтите 1.
  2. Если count > maximum_countустановить maximum_count = count. Выведите iкак индекс несбалансированной закрывающей скобки.

Сброс maximum_count=0, count=0. Для каждого iиз n-1к turning_point+1вниз сделайте следующее.

  1. Если str[j] = '('добавить 1 к count; в противном случае вычтите 1.
  2. Если count > maximum_countустановить maximum_count = count. Выведите iкак индекс несбалансированной открывающей скобки.

Понятно, что алгоритм выполняется за времени и вспомогательной памяти и выходной памяти, где - количество несбалансированных скобок.O(n)O(1)O(u)u


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

Вот код на Python .

Просто нажмите «запустить», чтобы увидеть несколько результатов теста.


Упражнение 1. Покажите, что вышеприведенный алгоритм выведет набор скобок с наименьшим количеством элементов, чтобы оставшиеся скобки были сбалансированы.

Задача 1. Можем ли мы обобщить алгоритм на случай, когда строка содержит два вида скобок, таких как "() []"? Мы должны определить, как распознать и обработать новую ситуацию, случай чередования, "([)]".

Джон Л.
источник
Lol, упражнение 1 и задача 1, мило. Логика алгоритма, который вы описали, на удивление трудно представить. Я должен был бы закодировать это завтра, чтобы получить это.
временное_имя_пользователя
Похоже, я пропустил довольно очевидное, но самое важное объяснение. Логика, на самом деле, очень проста. Сначала мы выводим каждую дополнительную открывающую скобку. Как только мы прошли поворотный момент, мы выводим каждую дополнительную закрывающую скобку. Готово.
Джон Л.
Нахождение несбалансированных открывающих скобок неверно. Т.е. если ваш arr равен "())", p равен 2 и p + 1 выходит за пределы границы arr. Просто идея - чтобы найти несбалансированные открывающие скобки, вы можете обратить arr и использовать часть алгоритма, чтобы найти несбалансированные закрывающие скобки (конечно, с обратно адаптированными индексами).
OzrenTkalcecKrznaric
@OzrenTkalcecKrznaric Именно потому, что выходит за пределы границы, в "())" нет несбалансированных открывающих скобок. p+1
Джон Л.
Мне понадобилось немного, чтобы понять это, но мне это нравится, это довольно умно ... и работает, по крайней мере, для каждого случая, о котором я думал
dquijada