您现在的位置是:首页 >技术交流 >【代码随想录】刷题Day11网站首页技术交流

【代码随想录】刷题Day11

哈里沃克 2023-07-09 16:00:03
简介【代码随想录】刷题Day11

1.栈解决括号判断问题

20. 有效的括号

1.由于最先的左类括号是最后被判断的,所以我们使用的是栈来判断

2.如果碰到左类括号,那就直接入栈

3.如果碰到右类括号,如果栈中是空的,那么说明没有括号和它对应,直接返回false

4.如果碰到右类括号和stack的栈顶对应,说明栈顶可以出栈

5.如果不对应,也是无效的括号,返回false

6.最后循环走完的说明是成功的,返回true

class Solution {
public:
    bool isValid(string s) {
        stack<char> st;
        for(auto e:s)
        {
            if(e=='('||e=='['||e=='{')
                st.push(e);
            else
            {
                if(st.empty()==1)
                    return false;
                if(e==')'&&st.top()=='('||e==']'&&st.top()=='['||e=='}'&&st.top()=='{')                   
                    st.pop();
                else
                    return false;
            }
        }
        return st.empty();
    }
};

2.栈删除相同临近的字符

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

1.由于我们要删除临近的字符,使用栈很合适,只要检查栈顶和要插入的是否一样。

2.进入循环将s中的值插入栈中:如果栈为空,或者栈顶元素和要插入元素不相同,说明此时元素可以被插入;此外的都是需要把栈顶元素删除

3.循环结束,需要把栈的元素全部交给字符串,但是元素出栈得到结果是倒着的,所以我们还要将得到的字符串reverse一下

class Solution {
public:
    string removeDuplicates(string s) {
        stack<char> st;
        for(auto e:s)
        {
            if(st.empty()||e!=st.top())
                st.push(e);
            else
                st.pop();
        }
        string ret;
        while(!st.empty())
        {
            ret += st.top();
            st.pop();
        }
        reverse(ret.begin(),ret.end());
        return ret;
    }
};

3.逆波兰表达法求值

150. 逆波兰表达式求值

1.遇到数就入栈

2.遇到符号就出栈两个值,进行运算,注意前后,先出栈的是右边的数。运算得到的结果要返回栈中,以便进入下一轮计算

3.最后留在栈中的唯一一个数,就是我们要返回的结果

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> s;
        for(int i=0;i<tokens.size();i++)
        {
            if(tokens[i]=="+"||tokens[i]=="-"||tokens[i]=="*"||tokens[i]=="/")
            {
                int second = s.top();
                s.pop();
                int first = s.top();
                s.pop();
                if(tokens[i]=="+"){s.push(first+second);}
                if(tokens[i]=="-"){s.push(first-second);}
                if(tokens[i]=="*"){s.push(first*second);}
                if(tokens[i]=="/"){s.push(first/second);}
            }
            else
                s.push(stoi(tokens[i]));
        }
        return s.top();
    }
};

风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。