解决括号问题

解决括号问题

01 有效的括号

给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。

示例 1：
输入：s = "()"
输出：true
示例 2：
输入：s = "()[]{}"
输出：true
示例 3：
输入：s = "(]"
输出：false
示例 4：
输入：s = "([)]"
输出：false
示例 5：
输入：s = "{[]}"
输出：true
提示：
1 <= s.length <= 104
s 仅由括号 '()[]{}' 组成
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/valid-parentheses
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

使用栈数据结构。遇到左括号就将其入栈，遇到右括号就去栈中寻找最近的左括号，看是否匹配。

char reverseOf(char c) {
    if (c == '}')
        return '{';
    if (c == ']')
        return '[';
    return '('
}
bool isValid(string str) {
    stack<char> st;
    for (char c : str) {
        if (c == '(' || c == '{' || c == '[') {
            st.push(c);
        } else {
            if (!left.empty() && reverseof(c) == st.top())
                st.pop();
            else
                return false;
        }
    }
    return st.empty();
}

// 或者
 bool isValid(string s) {
     stack<char> st;
     for (char ch : s) {
         if (ch == '(')
             st.push(')');
         else if (ch == '{')
             st.push('}');
         else if (ch == '[')
             st.push(']');
         else {
             if (!st.empty() && st.top() == ch)
                 st.pop();
             else 
                 return false;
         }
     }
     return st.empty();
 }

02 使括号有效的最少添加

给定一个由 ‘(‘ 和 ‘)’ 括号组成的字符串 S，我们需要添加最少的括号（ ‘(‘ 或是 ‘)’，可以在任何位置），以使得到的括号字符串有效。

从形式上讲，只有满足下面几点之一，括号字符串才是有效的：

它是一个空字符串，或者
它可以被写成 AB （A 与 B 连接）, 其中 A 和 B 都是有效字符串，或者
它可以被写作 (A)，其中 A 是有效字符串。
给定一个括号字符串，返回为使结果字符串有效而必须添加的最少括号数。

示例 1：

输入："())"
输出：1
示例 2：

输入："((("
输出：3
示例 3：

输入："()"
输出：0
示例 4：

输入："()))(("
输出：4


提示：

S.length <= 1000
S 只包含 '(' 和 ')' 字符。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-add-to-make-parentheses-valid
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

可以使用上题思想，如果遇到的是 )，并且和栈顶元素不相同，那么就需要添加一个左括号。当字符串遍历完后，返回 st.size() + res 即可。其中 st.size() 是需要添加右括号的个数。

int minAddToMakeValid(string s) {
    if (s.empty())
        return 0;
    stack<int> st;
    int res = 0;
    for (char ch : s) {
        if (ch == '(')
            st.push(')');
           else {
            if (!st.empty() && st.top() == ch)
                st.pop();
            else 
                res++;
        }
    }
    return st.size() + res;
}

也可以不入栈。

int minAddToMakeValid(string s) {
    // 记录左括号需求数
    int res = 0;
    // 记录右括号需求数
    int need = 0;
    for (char ch : s) {
        if (ch == '(')
            need++;
        else {
            need--;
            if (need == -1){
                need = 0;
                res++;
            }
        }
    }
    return res + need;
}

03 平衡括号字符串的最小插入次数

给你一个括号字符串 s ，它只包含字符 ‘(‘ 和 ‘)’ 。一个括号字符串被称为平衡的当它满足：

任何左括号 ‘(‘ 必须对应两个连续的右括号 ‘))’ 。
左括号 ‘(‘ 必须在对应的连续两个右括号 ‘))’ 之前。
比方说 “())”， “())(())))” 和 “(())())))” 都是平衡的， “)()”， “()))” 和 “(()))” 都是不平衡的。

你可以在任意位置插入字符 ‘(‘ 和 ‘)’ 使字符串平衡。

请你返回让 s 平衡的最少插入次数。

示例 1：

输入：s = "(()))"
输出：1
解释：第二个左括号有与之匹配的两个右括号，但是第一个左括号只有一个右括号。我们需要在字符串结尾额外增加一个 ')' 使字符串变成平衡字符串 "(())))" 。
示例 2：

输入：s = "())"
输出：0
解释：字符串已经平衡了。
示例 3：

输入：s = "))())("
输出：3
解释：添加 '(' 去匹配最开头的 '))' ，然后添加 '))' 去匹配最后一个 '(' 。
示例 4：

输入：s = "(((((("
输出：12
解释：添加 12 个 ')' 得到平衡字符串。
示例 5：

输入：s = ")))))))"
输出：5
解释：在字符串开头添加 4 个 '(' 并在结尾添加 1 个 ')' ，字符串变成平衡字符串 "(((())))))))" 。


提示：

1 <= s.length <= 10^5
s 只包含 '(' 和 ')' 。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-insertions-to-balance-a-parentheses-string
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

int minInsertions(string s) {
    int res = 0;
    int need = 0;
    for (char ch : s) {
        if (ch == '(') {
            // 一个左括号需要两个右括号匹配
            need += 2;
            if (need % 2 == 1) {
                // 如果右括号不是偶数，说明右括号多了一个，需要一个右括号匹配
                res++;
                // 对右括号需求减 1
                need--;
            }
        } else {
            need--;
            // 右括号太多了
            if (need == -1) {
                // j
                res++;
                need = 1;
            }
        }
    }
    return res + need;
}

算法笔记

1.2.2 括号题目

解决括号问题

01 有效的括号

02 使括号有效的最少添加

03 平衡括号字符串的最小插入次数