跳转至

Day9 | Part2

约 109 个字 37 行代码 预计阅读时间 1 分钟

20.有效的括号

括号匹配栈的经典问题

Tips

在匹配左括号时 对应的右括号先入栈，此时只需要比较当前元素和栈顶相等否

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
bool isValid(string s) {
    stack<int> 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;
        else st.pop();
    }
    return st.empty();
}

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

利用栈完美解决 → 参考动图

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
string removeDuplicates(string s) {
    stack<char> st;
    for (auto i : s) {
        if (!st.empty() && i == st.top()) st.pop();
        else st.push(i);
    }
    s = "";
    while(!st.empty()) s += st.top(); st.pop();
    reverse(s.begin(), s.end());
    return s;
}

150.逆波兰表达式求值

逆波兰表达式：是一种后缀表达式，即二叉树的后序遍历 → 动图参考

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
int evalRPN(vector<string>& tokens) {
    stack<int> st;
    for (auto s : tokens) {
        if (s == "+" || s == "-" || s == "*" || s == "/") {
            auto x2 = st.top(); st.pop();
            auto x1 = st.top(); st.pop();
            if (s == "+") st.push(x1 + x2);
            if (s == "-") st.push(x1 - x2);
            if (s == "*") st.push(x1 * x2);
            if (s == "/") st.push(x1 / x2);
        }
        else st.push(stoi(s)); // a string into an integer
    }
    return st.top();
}

颜色主题调整

快来和我聊天~

可以的话请给我赞和 star喔~    =>  GitHub stars

评论