leetcode 20 有效的括号

简介: leetcode 20 有效的括号

有效括号


5df4e1effa8c4b2c982971629806f287.png

遇到左括号压栈左括号

class Solution {
public:
    bool checkout( char &a , char &b ) //检查括号是否匹配
    {
        if (a == '(' && b == ')') return 1;
        else if (a == '[' && b == ']') return 1;
        else if (a == '{' && b == '}') return 1;
        else return 0;
    }
    bool isValid(string s) {
        stack<char> stack_s;
        stack_s.push(1);//防止空栈时top函数报错,提前压栈
        stack_s.push(s[0]);
        for (int i = 1; i < s.size(); i++)
        {
            if (checkout(stack_s.top(), s[i]) == 0) //不匹配压栈
            {
                stack_s.push(s[i]);
            }
            else//匹配弹栈
            {
                stack_s.pop();
            }
        }
        stack_s.pop();//弹出之前压的1
        return stack_s.empty();
    }
};

#遇到左括号压栈右括号

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();
    }
};

二刷

class Solution {
public:
    bool isValid(string s) {
        if(s.size()%2 == 1) return false;
        stack<char> s1;
        for(int i=0 ; i<s.size() ;i++)
        {
            if(s[i] == '('||s[i] == '['||s[i] == '{')
                s1.push(s[i]);
            else 
            {
                if(s1.empty() == 1) return false;
                if(s[i] == ')' && s1.top() == '('
                    || s[i] == ']' && s1.top() == '['
                    || s[i] == '}' && s1.top() == '{') s1.pop();
                else return false;
            }
        }
        if(s1.empty() == 1)
            return true;
        else return false;
    }
};

高频题

class Solution {
public:
    bool isValid(string s) {
        stack<char> my_stack;
        for(int i=0 ; i<s.size() ;i++)
        {
            if(s[i] == '(') my_stack.push(')');
            else  if(s[i] == '{') my_stack.push('}');
            else  if(s[i] == '[') my_stack.push(']');
            else  if( my_stack.size() > 0 && my_stack.top() == s[i] ) my_stack.pop();
            else  return false;
        }
        if(my_stack.size() > 0) return false;
        return true;
    }
};
相关文章
|
1月前
|
存储 C语言 索引
环形链表、环形链表 II、有效的括号​​​​​​​【LeetCode刷题日志】
环形链表、环形链表 II、有效的括号​​​​​​​【LeetCode刷题日志】
|
1月前
leetcode-301:删除无效的括号
leetcode-301:删除无效的括号
24 0
|
3天前
|
算法
【经典LeetCode算法题目专栏分类】【第11期】递归问题:字母大小写全排列、括号生成
【经典LeetCode算法题目专栏分类】【第11期】递归问题:字母大小写全排列、括号生成
|
3天前
|
算法
【经典LeetCode算法题目专栏分类】【第9期】深度优先搜索DFS与并查集:括号生成、岛屿问题、扫雷游戏
【经典LeetCode算法题目专栏分类】【第9期】深度优先搜索DFS与并查集:括号生成、岛屿问题、扫雷游戏
|
7天前
|
SQL 算法 数据可视化
LeetCode 题目 32:最长有效括号【python】
LeetCode 题目 32:最长有效括号【python】
|
7天前
|
存储 SQL 算法
LeetCode第22题:生成括号【22/1000 python 递归|动态规划】
LeetCode第22题:生成括号【22/1000 python 递归|动态规划】
|
7天前
|
SQL 算法 数据挖掘
探索有效括号 力扣第20题:从栈到递归的多角度解法 【含图解 python】
探索有效括号 力扣第20题:从栈到递归的多角度解法 【含图解 python】
|
11天前
|
算法 Java C语言
【经典算法】LeetCode 20:有效的括号(Java/C/Python3实现含注释说明,Easy)
【经典算法】LeetCode 20:有效的括号(Java/C/Python3实现含注释说明,Easy)
12 1
LeetCode | 20. 有效的括号
LeetCode | 20. 有效的括号
|
20天前
|
索引
【力扣刷题】数组实现栈、后缀表达式(逆波兰表达式)求值、中缀表达式转换为后缀表达式(无括号&&有括号)
【力扣刷题】数组实现栈、后缀表达式(逆波兰表达式)求值、中缀表达式转换为后缀表达式(无括号&&有括号)
20 0