LeetCode刷题Day11（补卡）

20. 有效的括号

题目链接：leetcode 20. 有效的括号
文章讲解：代码随想录
视频讲解：哔哩哔哩视频

这题考察的是栈的使用 ，遍历字符串，如果是左括号存入栈中，如果是右括号则对比栈的头部是否为与之匹配的左括号，如果不是则返回false，最后若栈为空则正好匹配返回true，详细代码如下：

class Solution {
public:
    bool isValid(string s) {
        //首先判断字符串是不是奇数，奇数一定返回false 
        if( s.size() % 2 != 0 ) return false; 
        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( ')' ) ; 
            else if( st.empty() || st.top() != s[i] )  return false ;  //说明右括号没有与所括号匹配，返回false
            else st.pop()  ;    //不满足上面所有的条件，说明当前括号正好和最上端括号匹配
        }
        return st.empty() ;     //最后栈为空说明正好全部匹配
    }
};

1047. 删除字符串中的所有相邻重复项

题目链接：leetcode 1047. 删除字符串中的所有相邻重复项
文章讲解：代码随想录
视频讲解：哔哩哔哩视频

这题的思路也比较简单，也是利用栈的特点存储元素，遍历字符串，假如遍历到的元素与栈中的头部相同则进行出栈，遍历下一个元素，具体代码如下：

class Solution {
public:
    string removeDuplicates(string s) {
        stack<char> st ; 
        for( int i = 0 ; i < s.size() ; i++ )
        {
            if( st.empty() || st.top()!= s[i] )     
                st.push( s[i] ) ; 
            else st.pop()  ;    
        }
        string result = "" ; 
        while( !st.empty() ){
            result += st.top() ;    //此时获得的result的顺序是与结果相反的
            st.pop()  ;
        }
        reverse( result.begin() , result.end() ) ; 
        return result ;
    }
};

150. 逆波兰表达式求值

题目链接：leetcode 150. 逆波兰表达式求值
文章讲解：代码随想录
视频讲解：哔哩哔哩视频

这题主要就是需要知道逆波兰表达式是什么，掌握规律则使用栈很方便。即如果是数字就直接入栈，假如是运算符则取出栈内的两个元素num1和num2，其中num1是栈顶元素，num2为其下一个元素进行运算，例如：num2/num1等，具体代码如下：

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<long long> st ; 
        for( int i = 0 ; i < tokens.size() ; i++) 
        {
            if( tokens[i] == "+" || tokens[i] == "/" || tokens[i] == "*" || tokens[i] == "-" )
            {
                long long num1 = st.top() ; 
                st.pop() ; 
                long long num2 = st.top() ; 
                st.pop() ; 
                if(tokens[i] == "+")  st.push( num2 + num1) ;
                if(tokens[i] == "-")  st.push( num2 - num1) ;
                if(tokens[i] == "*")  st.push( num2 * num1) ;
                if(tokens[i] == "/")  st.push( num2 / num1) ;
            }else{
                st.push( stoll(tokens[i]) ) ; 
            }
        }
        int result = st.top() ; 
        return result ; 
    }
};