精选50题之 20. 有效的括号

男娘i 2024-04-17 22:01 57阅读 0赞

### 腾讯精选练习（50 题）之 20. 有效的括号 ###

*   *  原题目链接
     *  题目分析
     *  解题思路
     *  代码实现
     *  写在最后

## [原题目链接][Link 1] ##

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

有效字符串需满足：  
左括号必须用相同类型的右括号闭合。  
左括号必须以正确的顺序闭合。  
注意空字符串可被认为是有效字符串。

> 示例 1:  
> 输入: “()”  
> 输出: true

> 示例 2:  
> 输入: “()\[\]\{\}”  
> 输出: true

> 示例 3:  
> 输入: “(\]”  
> 输出: false

> 示例 4:  
> 输入: “(\[)\]”  
> 输出: false

> 示例 5:  
> 输入: “\{\[\]\}”  
> 输出: true

## 题目分析 ##

这是一道使用堆栈的简单题…

## 解题思路 ##

创建堆栈，遇到左括号进栈，遇到右括号，栈顶判断一致，出栈；不一致，返回错误。  
遍历所有元素，若堆栈为空，返回正确；否则，返回错误。  
利用ASCII码简化判断条件。  
经过查表，发现"(“和”)“ASCII码值相差1，而”\[“与”\]"，"\{“与”\}"均相差2，所以实际上可以通过比较字符的ASCII码值的差值来判断是否为有效括号。

## 代码实现 ##

class Solution {
        
    public:
        bool isValid(string s) {
        
            stack<char> count;
            for(int i = 0;i < s.size(); i++)
            {
        
                if(count.empty() && (s[i]==')' || s[i] == '}' || s[i]==']'))
                    return false; //有多余右括号
                if(s[i] == ')' || s[i] == '}' || s[i] == ']')
                {
        
                    if(s[i] - count.top() == 1 || s[i] - count.top() == 2)
                        count.pop(); //满足ASCII码值相差1或2，栈顶(左括号)出栈
                    else
                        return false;
                }
                else
                    count.push(s[i]); //左括号进栈
            }
            return count.empty(); //返回计数栈是否为空
        }
    };

## 写在最后 ##

0ms官方范例如下

class CharStack {
        
        
    private:
        vector<char> data;
        
    public:
        void push(char x) {
        
            data.push_back(x);
        }
        
        void pop() {
        
            data.pop_back();
        }
        
        char top() {
        
            if(data.empty()) {
        
                return '-1';
            }
            return data.back();
        }
        
        bool isEmpty() {
        
            return data.empty();
        }   
    };
    
    class Solution {
        
    public:
        bool isValid(string s) {
        
            int c1, c2, i, len;            
            
            len = s.size();
            CharStack* obj = new CharStack();
            
            if(!len) {
        
                return true;
            }
            obj->push(s[0]);
            for(i = 1; i < len; i++) {
        
                c1 = obj->top();
                c2 = s[i];
                if ((c1 == '(' &&  c2 == ')') || (c1 == '[' &&  c2 == ']') || (c1 == '{' &&  c2 == '}')) {
        
                    obj->pop();
                } else {
        
                    obj->push(c2);
                }
            }
            if(!obj->isEmpty()) {
        
                return false;
            }
            return true;
        }
    };

[Link 1]: https://leetcode-cn.com/problems/valid-parentheses/