【代码随想录】算法训练营 第十一天 第五章 栈与队列 Part 2

20. 有效的括号

题目

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

有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。
3. 每个右括号都有一个对应的相同类型的左括号。

思路

用栈来匹配是最好的选择，将字符串的每个字符与栈顶元素匹配，如果栈为空或者不匹配，就将字符进栈，每次匹配成功就可以将栈顶元素弹出，如果字符串有效，那么栈里最后是不会有元素的。

代码

class Solution {
public:
    bool isValid(string s) {
        stack st;
        if (s.size() % 2)
            return false;
        for (int i = 0; i 

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

题目

思路

和上一题一样，只不过这题要注意最后留下的字服务器托管网符串是要输出的，所以我们一开始遍历原字符串时就要从最后一个遍历，这样塞进栈里的字符串顺序是反的，最后再把栈里的字符串输出到一个新定义的字符串即可，注意定义字符串的格式是 string str(length, ‘ ‘) 括号中前一个参数是字符串的长度，后一个是用什么字符填充这个字符串。

代码

class Solution {
public:
    string removeDuplicates(string s) {
        stack st;
        int len = 0;
        for (int i = s.size() - 1; i >= 0; i--) {
            if (st.empty()) {
                st.push(s[i]);
               服务器托管网 len++;
            }
            else if (s[i] == st.top()) {
                st.pop();
                len--;
            }
            else {
                st.push(s[i]);
                len++;
            }
        }
        string ss(len, ' ');
        int k = 0;
        while (len--) {
            ss[k] = st.top();
            st.pop();
            k++;
        }
        return ss;
    }
};

150. 逆波兰表达式求值

题目

给你一个字符串数组tokens，表示一个根据逆波兰表示法表示的算术表达式。

请你计算该表达式。返回一个表示表达式值的整数。

注意：

• 有效的算符为'+'、'-'、'*'和'/'。
• 每个操作数（运算对象）都可以是一个整数或者另一个表达式。
• 两个整数之间的除法总是向零截断。
• 表达式中不含除零运算。
• 输入是一个根据逆波兰表示法表示的算术表达式。
• 答案及所有中间计算结果可以用32 位整数表示。

思路

理解了逆波兰式的输入就很好办了，和上面两题异曲同工，而且这道题不会有需要特判的情况，所以只需要遇到符号就取栈顶元素计算即可，唯一要注意的是这里面的数据类型转换，把string类型变成int型用stoll。

代码

class Solution {
public:
    int evalRPN(vector& tokens) {
        stack st;
        for (int i = 0; i 

服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net

相关推荐: 《算法竞赛·快冲300题》每日一题：“彩虹数”
题目描述

题解

C++代码

Java代码

Python代码

《算法竞赛快冲300题》将于2024年出版，是《算法竞赛》的辅助练习册。 所有题目放在自建的OJ New Online Judge。 用C/C++、Java、Python三种语言给出代码，以中低档题为主，适合入门、进阶。 文章目录 题目描述 题解 C++代码 …