Задача кодирования средней сложности для подготовки к собеседованию

Для заданной строки вернуть минимальное количество перестановок скобок, необходимых для создания сбалансированных скобок. Круглые скобки будут либо "(", либо ")". Например:

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