括号

三道括号题目

20.有效的括号

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

有效字符串需满足：

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

class Solution {
public:
    bool isValid(string s) {
        stack<char> st;
        for(int i=0;i<s.size();i++){
            if(s[i]=='(' || s[i]=='[' || s[i]=='{'){ //如果是左括号进栈
                st.push(s[i]);
            }
            else{
                if(!st.empty() && fun(s[i])==st.top()){
                    st.pop();
                }
                else{
                    //和最近的左括号不匹配
                    return false;
                }
            }
        }
        //是否所有的左括号都被匹配了
        return st.empty();
    }
    char fun(char c){
        if(c==')') return '(';
        if(c==']') return '[';
        return '{';
    }
};

921.使括号有效的最少添加

给你输入一个字符串s，你可以在其中的任意位置插入左括号(或者右括号)，请问至少需要几次插入才能使得s变成一个合法的括号串？

思路：以左括号为基准，通过维护对右括号的需求数need，来计算最小的插入次数

class Solution {
public:
    int minAddToMakeValid(string s) {
        //核心思路是以左括号为基准，通过维护对右括号的需求数need,
        //来计算最小的插入次数
        int res=0;    //记录需要插入的最少次数
        int need=0;   //需要多少个右括号来与左括号匹配
        for(int i=0;i<s.size();i++){
            if(s[i]=='('){
                //对右括号的需求+1
                need++; 
            }
            if(s[i]==')'){
                //对右括号的需求-1
                need--;
                if(need==-1){
                    need=0;
                    //需要插入一个左括号
                    res++;
                }
            }
        }
        return res + need;
    }
};

1541.平衡括号字符串的最少插入次数

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

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

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

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

相比前一个，这次1个左括号需要匹配两个2个右括号

class Solution {
public:
    int minInsertions(string s) {
        //核心思路是以左括号为基准，通过维护对右括号的需求数need,
        //来计算最小的插入次数
        int res=0;    //记录需要插入的最少次数
        int need=0;   //记录右括号的需求量
        for(int i=0;i<s.size();i++){
            if(s[i]=='('){
                //一个左括号对应两个右括号
                need += 2;
                //当对右括号的需求量为奇数时，需要插入一个右括号
                if(need%2==1){
                    //插入一个右括号
                    res++;
                    //对右括号的需求量-1
                    need--;
                }
            }
            if(s[i]==')'){
                need--;
                //说明有括号太多了
                if(need==-1){
                    //插入一个左括号
                    res++;
                    //同时，对右括号的需求变为1
                    need=1;
                }
            }
        }
        return res + need;
    }
};

678.有效的括号字符串

给定一个只包含三种字符的字符串：（ ，） 和 *，写一个函数来检验这个字符串是否为有效字符串。有效字符串具有如下规则：

1、任何左括号 ( 必须有相应的右括号 )。

2、任何右括号 ) 必须有相应的左括号 ( 。

3、左括号 ( 必须在对应的右括号之前 )。

4、*可以被视为单个右括号 ) ，或单个左括号 ( ，或一个空字符串。

5、一个空字符串也被视为有效字符串。

思路：双栈，一个栈存储左括号，一个栈存储星号。从左到右遍历字符串，进行如下操作：

如果遇到左括号，将当前下标进左括号栈

如果遇到星号，将当前下标进星号栈

如果遇到右括号，优先和左括号匹配，没有左括号再和星号匹配。

遍历结束之后，两个栈可能还有元素，将星号看成右括号和左括号进行匹配，而且每个左括号必须要在与其匹配的星号之前。通过之前存入的下标进行判断即可。

class Solution {
public:
    bool checkValidString(string s) {
        int n=s.size();
        stack<int> st1;
        stack<int> st2;
        for(int i=0;i<n;i++){
            if(s[i]=='('){
                st1.push(i);
            }else if(s[i]=='*'){
                st2.push(i);
            }else{
                if(!st1.empty()){
                    st1.pop();
                }else if(!st2.empty()){
                    st2.pop();
                }else{
                    return false;
                }
            }
        }

        while(!st1.empty() && !st2.empty()){
            int index1=st1.top();
            st1.pop();
            int index2=st2.top();
            st2.pop();
            if(index1 > index2){
                return false;
            }
        }
        return st1.empty();
    }
};

32.最长有效括号

//思路：
//栈
//始终保持栈底元素为当前已经遍历过的元素中「最后一个没有被匹配的右括号的下标」
//对于遇到的每个‘(’ ，我们将它的下标放入栈中
//对于遇到的每个‘)’ ，我们先弹出栈顶元素表示匹配了当前右括号：
    //如果栈为空，说明当前的右括号为没有被匹配的右括号，
    //我们将其下标放入栈中来更新我们之前提到的「最后一个没有被匹配的右括号的下标」
    //如果栈不为空，当前右括号的下标减去栈顶元素即为「以该右括号为结尾的最长有效括号的长度」

class Solution {
public:
    int longestValidParentheses(string s) {   
        stack<int> st;
        int res=0;
        st.push(-1);
        
        for(int i=0;i<s.size();i++){
            if(s[i]=='('){ //遇到左括号
                st.push(i);
            }else{ //遇到右括号
                st.pop();
                if(st.empty()){  //当前右括号为没有被匹配的括号
                    st.push(i);  //更新栈底元素
                }else{
                    res = max(res, i-st.top());
                }
            }
        }
        return res;
    }
};

22.括号生成

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且有效的括号组合。

有关括号问题，只要记住以下性质，思路就很容易想出来：

1、一个“合法”括号组合的左括号数量一定等于右括号数量

2、对于一个“合法”的括号字符串组合s，必然对于任何0<=i<s.size()都有：子串s[0…i]中左括号的数量都大于或等于右括号的数量。（因为是从左到右算的）

思路：算法输入一个整数n，让你计算n对括号能组成几种合法的括号组合，可以改写程如下问题：

现在有2n个位置，每个位置可以放置字符(或者)，组成的所有括号组合中，有多少个是合法的？

class Solution {
public:
    vector<string> res;
    string temp;
    vector<string> generateParenthesis(int n) {
        if(n==0) return {};
        //可用的左括号和右括号数量初始为 n
        dfs(n, n);
        return res;
    }
    void dfs(int left, int right){ //可用的左括号为left个，可用的右括号为right个
        //不合法，结束
        if(left<0 || right<0) return;
        //若剩下的左括号多，不合法
        if(right<left) return;

        //当所有括号都恰好用完时，得到一个合法的组合
        if(left==0 && right==0){
            res.push_back(temp);
            return;
        }
        //尝试添加一个左括号
        temp.push_back('(');
        dfs(left-1, right);
        temp.pop_back();

        //尝试添加一个右括号
        temp.push_back(')');
        dfs(left, right-1);
        temp.pop_back();
    }
};