leetcode算法每天一题 020: 有效的括号(c++ stack＜＞ queue＜＞的简单使用 )

题目描述

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

有效字符串需满足：

    左括号必须用相同类型的右括号闭合。
    左括号必须以正确的顺序闭合。
    每个右括号都有一个对应的相同类型的左括号。
1
2
3
4
5
6
7

class Solution {
public:
    bool isValid(string s) {

    }
};
1
2
3
4
5
6

C++ 栈（stack）使用简述

C++ 语言中 queue 的常见用法详解

解（正经解法）

class Solution {
public:
    bool isValid(string s) {
        stack<char> mystack;
        char now;
        char instack;
        int n = s.length();
         
        for(int i=n;i>0;i--){
                now = s[i-1];
                if(!mystack.empty()){//如果栈非空
                   instack =  mystack.top();//读取一个元素
                }else{
                    instack = NULL;//else 是对应这个用例 "[[[]"
                }
                if( now =='(' && instack ==')'){mystack.pop();}
                else if( now =='{' && instack =='}'){mystack.pop();}
                else if( now =='[' && instack ==']'){mystack.pop();}
                else{mystack.push(now);}
        }
        return mystack.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

其他解法

class Solution:
    def isValid(self, s):
        while '{}' in s or '()' in s or '[]' in s:
            s = s.replace('{}', '')
            s = s.replace('[]', '')
            s = s.replace('()', '')
        return s == ''

1
2
3
4
5
6
7
8

class Solution {
    public boolean isValid(String s) {
        int length = s.length() / 2;
		for (int i = 0; i < length; i++) {
			s = s.replace("()", "").replace("{}", "").replace("[]", "");
		}

		return s.length() == 0;
    }
}
1
2
3
4
5
6
7
8
9
10

class Solution {
public:
    bool isValid(string s) {
        if (s.size() % 2 != 0) return false; // 如果s的长度为奇数，一定不符合要求
        stack<char> st;
        for (int i = 0; i < s.size(); i++) {
            if (s[i] == '(') st.push(')');
            else if (s[i] == '{') st.push('}');
            else if (s[i] == '[') st.push(']');
            // 第三种情况：遍历字符串匹配的过程中，栈已经为空了，没有匹配的字符了，说明右括号没有找到对应的左括号 return false
            // 第二种情况：遍历字符串匹配的过程中，发现栈里没有我们要匹配的字符。所以return false
            else if (st.empty() || st.top() != s[i]) return false;
            else st.pop(); // st.top() 与 s[i]相等，栈弹出元素
        }
        // 第一种情况：此时我们已经遍历完了字符串，但是栈不为空，说明有相应的左括号没有右括号来匹配，所以return false，否则就return true
        return st.empty();
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18