Задача кодирования средней сложности для подготовки к собеседованию
Для заданной строки вернуть минимальное количество перестановок скобок, необходимых для создания сбалансированных скобок. Круглые скобки будут либо "("
, либо ")"
. Например:
solve(")(") = 2 Because we need to reverse ")" to "(" and "(" to ")". These are 2 reversals. solve("(((())") = 1 We need to reverse just one "(" parenthesis to make it balanced. solve("(((") = -1 Not possible to form balanced parenthesis. Return -1.
Объяснение решения
Первая часть
Чтобы сделать сбалансированную скобку, мы знаем, что нам нужны (
и )
. Наивным решением было бы подсчитать, сколько каждого из них у нас есть, и посмотреть, равно ли у нас их обоих. Если да, то это означает, что у нас есть сбалансированный набор. Однако это решение игнорирует порядок скобок. Для допустимой пары (
предшествует )
, поэтому нам нужен способ подсчета с порядком.
Таким образом, просто чтобы выяснить, сколько допустимых пар у нас есть, нам нужно будет считать каждый раз, когда мы видим (
, а затем искать соответствующее )
после. Например:
count ( = 0 for each char in the string if char is (: then update count if count > 0 and char is ) : then decrement count if count === 0, then we had all valid pairs
В приведенном выше псевдокоде мы используем count, чтобы проверить, есть ли у нас допустимые пары. Каждый раз, когда мы находим (
, мы увеличиваем наш счетчик, и каждый раз, когда мы находим соответствующий ему )
, мы уменьшаем счетчик. Мы гарантируем, что )
соответствует ранее найденному (
, подтверждая, что наш счет больше 0, и уменьшая этот счет, чтобы подтвердить, что пара учитывается сейчас.
В конце этого, если у нас останется счетчик, то мы знаем, что это открытые скобки без соответствующей закрывающей скобки.
Часть вторая
Наша проблема, однако, состоит в том, чтобы выяснить, как мы можем сделать сбалансированную скобку всего заданного массива. Итак, для этого нам нужно выяснить, сколько у нас несбалансированных скобок и как мы можем поменять местами определенные скобки, чтобы создать баланс. Теперь, когда мы можем проверить баланс, нам просто нужно использовать оставшиеся счетчики, чтобы помочь нам отслеживать необходимые развороты.
Напомним: чтобы найти каждую пару, мы отслеживаем openBracketCount
.
- Мы увеличиваем этот счетчик, когда находим открытую скобку.
- Мы уменьшаем значение после того, как нашли соответствующую закрывающую скобку.
- Примечание. Мы уменьшаем это значение только в том случае, если у нас есть
openBracketCount>0
, чтобы убедиться, что мы нашли действительную пару. Если мы не нашли ни одной открытой скобки к тому времени, когда увидели закрытую скобку, мы не нашли допустимую пару.
Solve for "(())" char = "(" // add count of open brackets openBracketCount = 1 char = "(" // add count of open brackets openBracketCount = 2 char = ")" // subtract count, we found a pair openBracketCount = 1 char = ")" // subtract count, we found a pair openBracketCount = 0 Result: We have balanced parenthesis
Итак, если мы видим закрывающую скобку:
- Проверяем, не нашли ли мы ранее соответствующую ей открытую скобку. Если да, мы уменьшаем наше
openBracketCount
, так как мы нашли действительную пару. В этот момент перейдите к следующему персонажу. - Если вышесказанное неверно, то мы знаем, что нам нужно обратить это
)
в(
, увеличив нашеcountReversals
. Поскольку мы перевернули его в открытую скобку, теперь нам также нужно увеличить нашуopenBracketCount
, так как теперь у нас есть дополнительная открытая скобка, которую нам нужно соединить. Таким образом, мы можем отслеживать, находим ли мы соответствующую закрывающую скобку для создания сбалансированной пары. Часть третья.
Solve for "())(((" char = "(" // add count of open brackets openBracketCount = 1 countReversals = 0 char = ")" // decrement count, we found a valid pair openBracketCount = 0 countReversals = 0 char = ")" // we need to reverse this to "(" since it can't make a pair otherwise openBracketCount = 1 countReversals = 1 char = "(" // add count of open bracket openBracketCount = 2 countReversals = 1 char = "(" // add count of open brackets openBracketCount = 3 countReversals = 1 char = "(" // add count of open brackets openBracketCount = 4 countReversals = 1
Часть третья
В конце нам нужно проверить наши openBracketCount
, чтобы увидеть, сколько лишних открытых скобок у нас осталось. Если у нас осталось нечетное количество открытых скобок, мы знаем, что не можем составить пары для всех из них, и поэтому должны вернуть -1.
openBracketCount%2 = 4%2 = 0
Для приведенных выше примеров, поскольку у нас осталось четное количество (
, мы можем преобразовать половину из них в )
, чтобы получить сбалансированные пары.
Если у нас осталось четное количество открытых скобок, нам нужно перевернуть половину открытых скобок, чтобы создать правильные пары. Итак, мы добавляем половину количества открытых скобок к нашему countReversals
.
countReversals += openBracketCount // 2
Продолжая приведенный выше пример, посмотрите, как мы получаем наш результат 3
:
countReversals = 1 countReversals += 4//2 = 2 countReversals = 3 // this is our result
Код с комментариями
Я рекомендую прокрутить вниз, чтобы прочитать объясненное решение, чтобы понять мой процесс мышления для закодированного решения ниже. Кроме того, я добавил комментарии, связывающие мое объяснение с каждой строкой кода ниже.
function solve(s){ // this will help track any open bracket that has not yet been paired let openBracketCount = 0 // this will track any times we need to reverse a bracket let countReversals = 0 // check each character in array for (let i=0; i<s.length; i++) { const curr = s[i] // if we found an open bracket, increment count if (curr === "(") { openBracketCount += 1 } // if we found a balanced pair, decrement from openBracketCount else if (openBracketCount > 0 && curr === ")") { openBracketCount -= 1 } // curr is ")" at this point // since we don't have a open bracket to pair this to // reverse the ")" to an "(" and increment the open bracket count else { countReversals += 1 openBracketCount += 1 } } // At this point, if we have open brackets left, we need to reverse // half of them to create balanced pairs of open and closed brackets // So we increment our countReversals to track these necessary reversals // We use Math.ceil to properly round to an integer countReversals += Math.ceil(openBracketCount/2) // check if we have an even number of open brackets, otherwise return -1 // because we can't make balanced pairs with an odd number return openBracketCount%2 === 0 ? countReversals : -1
Поскольку мой код написан на Javascript, вы заметите, что мы используем Math.ceil
, чтобы округлить число в большую сторону. Это связано с тем, что Javascript не поддерживает операцию //
и в противном случае возвращает десятичное число.
Это имеет временную сложность O (N), поскольку у нас есть один цикл, который выполняется для длины массива s. Это имеет. пространственная сложность O (1), поскольку мы храним только константы.
Надеюсь, это помогло! Пожалуйста, прокомментируйте ниже и поделитесь своими мыслями. :)
Подпишитесь на DDIntel Здесь.
Посетите наш сайт здесь: https://www.datadriveninvestor.com
Присоединяйтесь к нашей сети здесь: https://datadriveninvestor.com/collaborate