Решение: оценка скобок

LeetCode Solutions (161 серия деталей)

Это является частью серии объяснений решения LeetCode ( index ). Если вам понравилось это решение или нашли его полезным, Пожалуйста, нравится Этот пост и/или upvote Мое решение по сообщению на форумах LeetCode Анкет

Проблема LeetCode #856 (среда): оценка скобок

Описание:

( прыгнуть в : Идея решения Код : JavaScript | Python | Java | C++

Учитывая сбалансированную строку скобок S , вычислить оценку строки на основе следующего правила:

• () имеет счет 1
• Ab имеет счет A + b , где A и B сбалансированные столовые струны.
• (А) имеет счет 2 * A , где A это сбалансированная строка скобок.

Примеры:

Ограничения:

• S это сбалансированная строка скобок, содержащая только ( и ) .
• 2. длиной

Идея:

( прыгнуть к : Описание проблемы Код : JavaScript | Python | Java | C++

Каждый раз, когда мы видим проблему, которая описывает операцию удвоения и операцию по увеличению, мы должны, по крайней мере, подумать о потенциальном бинарном решении. В этом случае это действительно единственные две операции. Вложенные операции удвоения означает полномочия 2 В зависимости от глубины гнездования, и простая закрытая пара скобок – это +1 .

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

Рассмотрим следующее:

S = "(((()()())))"
  = "(((" 1 + 1 + 1 ")))"    // After replacing completed "()"s with 1s
  = (1 + 1 + 1) * 2^3        // Applying the power operations
  = 2^3 + 2^3 + 2^3          // Through the distributive property of multiplication

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

Это означает, что мы можем решить эту проблему в O (n) время и O (1) пространство Анкет

Реализация:

Для JavaScript S.Charat (i) быстрее при обработке строковой итерации, чем S [i] Анкет

Мы можем начать нашу итерацию в я Потому что мы знаем, что первый персонаж будет “(“ . Мы мог Начните с я В Но тогда нам придется начать с пвер или убедитесь, что уменьшить пвер Перед операцией питания вместо после.

Мы можем использовать Побитовая смена Для того, чтобы операция мощности более точно отражала бинарную природу решения.

Код JavaScript:

( прыгнуть к : Проблема Описание Идея решения

var scoreOfParentheses = function(S) {
    let len = S.length, pwr = 0, ans = 0
    for (let i = 1; i < len; i++)
        if (S.charAt(i) === "(") pwr++
        else if (S.charAt(i-1) === "(") ans += 1 << pwr--
        else pwr--  
    return ans
};

Код Python:

( прыгнуть к : Проблема Описание Идея решения

class Solution:
    def scoreOfParentheses(self, S: str) -> int:
        pwr, ans = 0, 0
        for i in range(1, len(S)):
            if S[i] == "(": pwr += 1
            elif S[i-1] == "(":
                ans += 1 << pwr
                pwr -= 1
            else: pwr -= 1
        return ans

Код Java:

( прыгнуть к : Проблема Описание Идея решения

class Solution {
    public int scoreOfParentheses(String S) {
        int len = S.length(), pwr = 0, ans = 0;
        for (int i = 1; i < len; i++)
            if (S.charAt(i) == '(') pwr++;
            else if (S.charAt(i-1) == '(') ans += 1 << pwr--;
            else pwr--;
        return ans;
    }
}

C ++ Код:

( прыгнуть к : Проблема Описание Идея решения

class Solution {
public:
    int scoreOfParentheses(string S) {
        int len = S.length(), pwr = 0, ans = 0;
        for (int i = 1; i < len; i++)
            if (S[i] == '(') pwr++;
            else if (S[i-1] == '(') ans += 1 << pwr--;
            else pwr--;
        return ans;
    }
};

LeetCode Solutions (161 серия деталей)

Оригинал: “https://dev.to/seanpgallivan/solution-score-of-parentheses-3gh0”