括号

发表于 | 分类于 ， ， |

三道括号题目

20.有效的括号

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

有效字符串需满足：

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
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 '{';
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
func isValid(s string) bool {
    st := []rune{} // 用切片模拟栈
    for _, ch := range s {
        if ch == '(' || ch == '[' || ch == '{' { // 如果是左括号进栈
            st = append(st, ch)
        } else {
            if len(st) > 0 && fun(ch) == st[len(st)-1] {
                st = st[:len(st)-1] // 出栈
            } else {
                // 和最近的左括号不匹配
                return false
            }
        }
    }
    // 是否所有的左括号都被匹配了
    return len(st) == 0
}

func fun(c rune) rune {
    if c == ')' {
        return '('
    }
    if c == ']' {
        return '['
    }
    return '{'
}

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
func minAddToMakeValid(s string) int {
    // 核心思路是以左括号为基准，通过维护对右括号的需求数need,
    // 来计算最小的插入次数
    res := 0  // 记录需要插入的最少次数
    need := 0 // 需要多少个右括号来与左括号匹配
    for _, ch := range s {
        if ch == '(' {
            // 对右括号的需求+1
            need++
        }
        if ch == ')' {
            // 对右括号的需求-1
            need--
            if need == -1 {
                need = 0
                // 需要插入一个左括号
                res++
            }
        }
    }
    return res + need
}

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

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

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

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
func minInsertions(s string) int {
    // 核心思路是以左括号为基准，通过维护对右括号的需求数need,
    // 来计算最小的插入次数
    res := 0  // 记录需要插入的最少次数
    need := 0 // 记录右括号的需求量
    for _, ch := range s {
        if ch == '(' {
            // 一个左括号对应两个右括号
            need += 2
            // 当对右括号的需求量为奇数时，需要插入一个右括号
            if need%2 == 1 {
                // 插入一个右括号
                res++
                // 对右括号的需求量-1
                need--
            }
        }
        if ch == ')' {
            need--
            // 说明有括号太多了
            if need == -1 {
                // 插入一个左括号
                res++
                // 同时，对右括号的需求变为1
                need = 1
            }
        }
    }
    return res + need
}

678.有效的括号字符串

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

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

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

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

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

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

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

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

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
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();
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
func checkValidString(s string) bool {
    n := len(s)
    st1 := []int{} // 用切片模拟栈，存储左括号的下标
    st2 := []int{} // 用切片模拟栈，存储星号的下标
    for i := 0; i < n; i++ {
        if s[i] == '(' {
            st1 = append(st1, i)
        } else if s[i] == '*' {
            st2 = append(st2, i)
        } else {
            if len(st1) > 0 {
                st1 = st1[:len(st1)-1] // 出栈
            } else if len(st2) > 0 {
                st2 = st2[:len(st2)-1] // 出栈
            } else {
                return false
            }
        }
    }

    for len(st1) > 0 && len(st2) > 0 {
        index1 := st1[len(st1)-1]
        st1 = st1[:len(st1)-1]
        index2 := st2[len(st2)-1]
        st2 = st2[:len(st2)-1]
        if index1 > index2 {
            return false
        }
    }
    return len(st1) == 0
}

32.最长有效括号

1
2
3
4
5
6
7
8
//思路：
//栈
//始终保持栈底元素为当前已经遍历过的元素中「最后一个没有被匹配的右括号的下标」
//对于遇到的每个‘(’ ，我们将它的下标放入栈中
//对于遇到的每个‘)’ ，我们先弹出栈顶元素表示匹配了当前右括号：
    //如果栈为空，说明当前的右括号为没有被匹配的右括号，
    //我们将其下标放入栈中来更新我们之前提到的「最后一个没有被匹配的右括号的下标」
    //如果栈不为空，当前右括号的下标减去栈顶元素即为「以该右括号为结尾的最长有效括号的长度」
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func longestValidParentheses(s string) int {
    st := []int{} // 用切片模拟栈
    res := 0
    st = append(st, -1)
    
    for i := 0; i < len(s); i++ {
        if s[i] == '(' { // 遇到左括号
            st = append(st, i)
        } else { // 遇到右括号
            st = st[:len(st)-1] // 出栈
            if len(st) == 0 {   // 当前右括号为没有被匹配的括号
                st = append(st, i) // 更新栈底元素
            } else {
                if i-st[len(st)-1] > res {
                    res = i - st[len(st)-1]
                }
            }
        }
    }
    return res
}

22.括号生成

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

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

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

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
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();
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
func generateParenthesis(n int) []string {
    if n == 0 {
        return []string{}
    }
    res := []string{}
    temp := ""
    // 可用的左括号和右括号数量初始为 n
    var dfs func(left, right int)
    dfs = func(left, right int) { // 可用的左括号为left个，可用的右括号为right个
        // 不合法，结束
        if left < 0 || right < 0 {
            return
        }
        // 若剩下的左括号多，不合法
        if right < left {
            return
        }

        // 当所有括号都恰好用完时，得到一个合法的组合
        if left == 0 && right == 0 {
            res = append(res, temp)
            return
        }
        // 尝试添加一个左括号
        temp += "("
        dfs(left-1, right)
        temp = temp[:len(temp)-1]

        // 尝试添加一个右括号
        temp += ")"
        dfs(left, right-1)
        temp = temp[:len(temp)-1]
    }
    dfs(n, n)
    return res
}
-------------本文结束 感谢阅读-------------
0%