20. 有效的括号 无序map、栈 2021/11/21

给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 s ，判断字符串是否有效。
有效字符串需满足：左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。
示例：
输入：s = “()[]{}”
输出：true
输入：s = “([)]”
输出：false

使用unordered_map无序关联容器。利用栈先进后出的性质，遍历字符串，如为([{则压入栈，否则为)]}，看栈顶元素是否为其对应值，如是则弹出栈顶元素，最后遍历完如栈空则视为有效。

class Solution {
public:
    bool isValid(string s) {
        stack<char> stk;
        if(s.size() % 2) return false; //如果字符串长度都不是偶数，直接判断无效
        unordered_map<char, char> m = { {')', '('}, {']', '['}, {'}', '{'} };  //使用不排序map存放括号字符对
        for(int ch:s){ //遍历s
            if(m.count(ch)){ //如果找到了键值
                if(stk.empty() || stk.top()!= m[ch]){ //判断栈顶是否为其value，如果不是或栈为空
                    return false; //字符串无效
                }
                stk.pop(); //反之则为其value，栈顶元素弹出
            }
            else{
                stk.push(ch); //为([{，压入栈
            }
        }
        return stk.empty(); //如果遍历完发现栈为空，视为有效
    }
};

---

92. 反转链表 II 反转链表（栈、递归） 2021/11/21

给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。
示例：
输入：head = [1,2,3,4,5], left = 2, right = 4
输出：[1,4,3,2,5]

方法一：先找到待反转的结点，再使用栈依次将待反转的结点压入栈，最后拼接即可。（注意断裂时的链表结点记得保存）

class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int left, int right) {
        if(!head || !head->next) return head; //如果表长为0或1直接返回
        ListNode* dummy = new ListNode(0, head); //哑结点
        stack<ListNode*> stk; //栈用于存放待反转的结点
        ListNode* cur = dummy; //辅助指针，用于移动到待反转结点的前一个结点
        for(int i = 1; i < left; i++){
            cur = cur->next; //移动left-1次，最后cur停留在待反转结点的前一个结点
        }
        ListNode* p = cur; //辅助指针，用于将各待反转结点压入栈
        for(int j = 0; j <= right - left; j++){
            stk.push(p->next); //将要翻转的结点压入栈，最后p指向待反转结点的最后一个结点
            p = p->next;
        }
        ListNode* latter = p->next; //latter辅助结点指向反转结点后面的结点
        while(!stk.empty()){
            cur->next = stk.top();
            cur = cur->next;
            stk.pop();
        }
        cur->next = latter; //拼接链表
        ListNode* newhead = dummy->next;
        delete dummy;
        return newhead;
    }
};

方法二：在链表反转时用递归（待补充）。

---

剑指 Offer II 036.后缀表达式 栈 2023/3/3

根据 逆波兰表示法，求该后缀表达式的计算结果。
有效的算符包括 +、-、、/ 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。
示例：
输入：tokens = [“2”,“1”,“+”,“3”,""]
输出：9
解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9

逆波兰表达式⇒栈。遇到运算符后取出栈顶元素进行运算。

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> stk;
        for (string s: tokens) {
            if (s == "+" || s == "-" || s == "*" || s == "/") {
                int op2 = stk.top();
                stk.pop();
                int op1 = stk.top();
                stk.pop();
                if (s == "+") stk.push(op1 + op2);
                else if (s == "-") stk.push(op1 - op2);
                else if (s == "*") stk.push(op1 * op2);
                else if (s == "/") stk.push(op1 / op2);
            }
            else stk.push(atoi(s.c_str()));
        }
        return stk.top();
    }
};

---

剑指 Offer II 037. 小行星碰撞 栈 2023/3/3

给定一个整数数组 asteroids，表示在同一行的小行星。
对于数组中的每一个元素，其绝对值表示小行星的大小，正负表示小行星的移动方向（正表示向右移动，负表示向左移动）。每一颗小行星以相同的速度移动。
找出碰撞后剩下的所有小行星。碰撞规则：两个行星相互碰撞，较小的行星会爆炸。如果两颗行星大小相同，则两颗行星都会爆炸。两颗移动方向相同的行星，永远不会发生碰撞。
示例：
输入：asteroids = [5,10,-5]
输出：[5,10]
解释：10 和 -5 碰撞后只剩下 10 。 5 和 10 永远不会发生碰撞。

非常难的模拟栈问题。
使用栈模拟小行星碰撞，从左往右遍历小行星数组，当我们遍历到小行星$aster$时，使用变量$alive$记录小行星$aster$是否还存在（即未爆炸）。

当小行星$aster$存在且$aster<0$，栈顶元素非空且大于0时，说明两个小行星相互向对方移动：如果栈顶元素大于等于$aster$，则小行星$aster$发生爆炸，将$alive$置为$false$；如果栈顶元素小于等于$-aster$，则栈顶元素表示的小行星发生爆炸，执行出栈操作。重复以上判断直到不满足条件，如果最后$alive$为真，说明小行星$aster$不会爆炸，则将 $aster$入栈。

class Solution {
public:
    vector<int> asteroidCollision(vector<int>& asteroids) {
        vector<int> st;
        for (auto aster : asteroids) {
            bool alive = true;
            while (alive && aster < 0 && !st.empty() && st.back() > 0) {
                alive = (aster + st.back() < 0); // aster 是否存在
                if (aster + st.back() <= 0) {  // 栈顶小行星爆炸
                    st.pop_back();
                }
            }
            if (alive) {
                st.push_back(aster);
            }
        }
        return st;
    }
};

---