代码随想录算法训练营第11天 | 20. 有效的括号、1047. 删除字符串中的所有相邻重复项、150. 逆波兰表达式求值

发布于 2022-11-25  170 次阅读


20. 有效的括号 - 力扣(LeetCode)

思路:本题使用栈先进后出的特性来解决问题。当遇到左边的符号时推入栈,遇到右边的符号时先判断栈是不是空的,如果此时栈是空的,直接return false,如果此时栈不是空的,继续判断栈顶的元素是否与现在遇到的元素相匹配,如果匹配则弹出,不匹配直接return false,等全部都走完以后还要判断栈是否为空,只有栈为空才能return true,否则return false,因为可能会出现只输入左半边符号的情况

  • 标准答案中出现了以下技巧:
    1. 可以先判断字符长度是不是奇数,如果是奇数肯定不匹配。
    2. 让右括号先入栈,就只需要比较当前元素和栈顶相不相等就可以了,比左括号先入栈代码实现要简单很多。

我的AC代码

//时间复杂度O(n),空间复杂度O(n)
class Solution {
public:
    bool isValid(string s) {
        stack<char> st;
        for(auto a : s) {
            if(a == '(' || a == '{' || a == '[') {
                st.push(a);
            }
            else {
                char tmp;
                if(!st.empty()) {
                    tmp = st.top();
                }
                else {
                    return false;
                }
                if((tmp == '(' && a == ')') || (tmp == '[' && a == ']') ||  (tmp == '{' && a == '}') ) {
                    st.pop();
                }
                else {
                    return false;
                }
            }
        }
        if(st.empty()) {
            return true;
        }
        else {
            return false;
        }
    }
};

标准答案

//时间复杂度O(n),空间复杂度O(n)
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();
    }
};

1047. 删除字符串中的所有相邻重复项 - 力扣(LeetCode)

思路:遍历字符串,先把字符串的第一个值存入栈。遍历过程中如果遇到栈顶与遍历到的字符相等,则执行出栈操作,否则就入栈,最后栈中存的就是答案。

  • 注意:最后从栈中输出的答案是反着的,需要反转字符串,刚开始我想用ans = string(1, st.top()) + ans结果一直超时,后来发现就是因为这个函数太慢了,千万不要用这个函数
  • 推荐使用标准答案中利用字符串模拟栈的方法,该方法时间复杂度和空间复杂度都大大降低

我的AC代码

//时间复杂度O(n),空间复杂度O(n)
class Solution {
public:
    string removeDuplicates(string s) {
        int scnt = s.size();
        if(scnt == 1) {
            return s;
        }
        stack<int> st;
        string ans = "";
        for(int i = 0;i < scnt; ++i) {
            if(i == 0) {
                st.push(s[i]);
            }
            else {
                if(!st.empty()) {
                    if(st.top() == s[i]) {
                        st.pop();
                    }
                    else {
                        st.push(s[i]);
                    }
                }
                else {
                    st.push(s[i]);
                }
            }
        }
        while(!st.empty()) {
            ans += st.top();
            st.pop();
        }
        reverse(ans.begin(), ans.end());
        return ans;
    }
};

标准答案

用栈实现

//时间复杂度O(n),空间复杂度O(1)
class Solution {
public:
    string removeDuplicates(string S) {
        stack<char> st;
        for (char s : S) {
            if (st.empty() || s != st.top()) {
                st.push(s);
            } else {
                st.pop(); // s 与 st.top()相等的情况
            }
        }
        string result = "";
        while (!st.empty()) { // 将栈中元素放到result字符串汇总
            result += st.top();
            st.pop();
        }
        reverse (result.begin(), result.end()); // 此时字符串需要反转一下
        return result;

    }
};

用字符串模拟栈实现

class Solution {
public:
    string removeDuplicates(string S) {
        string result;
        for(char s : S) {
            if(result.empty() || result.back() != s) {
                result.push_back(s);
            }
            else {
                result.pop_back();
            }
        }
        return result;
    }
};

150. 逆波兰表达式求值 - 力扣(LeetCode)

思路:用栈来解决该题,遇到数字则入栈,遇到运算符则取出栈顶两个数字进行计算,并将结果压入栈中。

  • 注意:
    1. 两个出栈数字的运算顺序是 后出栈的数字 +-*/ 先出栈的数字
    2. 为防止溢出,应该使用long long 来作为数据类型

我的AC代码

//时间复杂度O(n),空间复杂度O(n)
class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<long long> st;
        for(auto a : tokens) {
            long long tmp1;
            long long tmp2;
            if(a == "+") {
                tmp1 = st.top();
                st.pop();
                tmp2 = st.top();
                st.pop();
                st.push(tmp1 + tmp2);
            }
            else if(a == "-") {
                tmp1 = st.top();
                st.pop();
                tmp2 = st.top();
                st.pop();
                st.push(tmp2 - tmp1);
            }
            else if(a == "*") {
                tmp1 = st.top();
                st.pop();
                tmp2 = st.top();
                st.pop();
                st.push(tmp2 * tmp1);
            }
            else if(a == "/") {
                tmp1 = st.top();
                st.pop();
                tmp2 = st.top();
                st.pop();
                st.push(tmp2 / tmp1);
            }
            else if(stoi(a) >= -200 && stoi(a) <= 200) {
                st.push(stoi(a));
            }
        }
        return st.top();
    }
};

标准答案

//时间复杂度O(n),空间复杂度O(n)
class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        // 力扣修改了后台测试数据,需要用longlong
        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();
        st.pop(); // 把栈里最后一个元素弹出(其实不弹出也没事)
        return result;
    }
};

心有猛虎,细嗅蔷薇