06 力扣热题刷题记录之第20题有效的括号

系列文章目录

发现一篇一篇放在这里,编辑的时候很浪费时间,干脆把专栏的链接放在这里,如果需要,直接去专栏里面看即可,nice!

力扣刷题记录

文章目录


前言

每天进步一点点哟!

一、背景

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

有效字符串需满足: 左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/valid-parentheses

二、我的思路

这个还是比较简单的,之前做过数学表达式求解的,这个相比就是弟弟。

采用栈的数据结构,将所有的左括号入栈,当访问到右括号的时候,那么就和栈顶元素进行比较,如果匹配,那么栈顶元素出栈,再继续匹配下一个字符;如果不匹配,那么直接返回false.

代码如下:

class Solution {
public:
    bool isValid(string s) {
        stack <char>  bracket_match;
        for(char c:s)
        {
            if(c=='('||c=='['||c=='{')
            {
                bracket_match.push(c);
            }
            else
            {
                //右括号,但是栈是空的,必然false
                if (bracket_match.empty())
                    return false;
                else
                {
                    if(c==')'&&bracket_match.top()=='(') bracket_match.pop();
                    else if (c==']'&&bracket_match.top()=='[') bracket_match.pop();
                    else if (c=='}'&&bracket_match.top()=='{') bracket_match.pop();
                    else return false;
                }
            }
        }
        if(bracket_match.empty()) return true;
        return false;
    }
};

这个代码速度有点慢,4ms,有网友是0ms的,我也不晓得具体是怎么优化的。

二、官方的思路

官方给的答案思路比我多一个点,就是我是用if_else语句判断括号匹配与否,它是直接使用map数组。

代码如下:

class Solution {
public:
    bool isValid(string s) {
        int n = s.size();
        if (n % 2 == 1) {
            return false;
        }

        unordered_map<char, char> pairs = {
            {')', '('},
            {']', '['},
            {'}', '{'}
        };
        stack<char> stk;
        for (char ch: s) {
            if (pairs.count(ch)) {
                if (stk.empty() || stk.top() != pairs[ch]) {
                    return false;
                }
                stk.pop();
            }
            else {
                stk.push(ch);
            }
        }
        return stk.empty();
    }
};

作者:LeetCode-Solution
链接:https://leetcode-cn.com/problems/valid-parentheses/solution/you-xiao-de-gua-hao-by-leetcode-solution/
来源:力扣(LeetCode)

总结

这个基本上就是说方法是比较一致的,当然有人用C语言写这个,他是用的数组去存的,再是左右括号的ASCII码值相差1(具体多少忘记了),做减法可以判断括号是否匹配,也能达到目的。其实数组的话只需记录最后存进去的那个字符的下标即可,一样的道理。

喜欢就点个赞叭!!!

上一篇:虚拟化架构与Centos7系统部署


下一篇:php – 在多卷存档上扫描.rar文件内容条目