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 永远不会发生碰撞。

非常难的模拟栈问题。
使用栈模拟小行星碰撞,从左往右遍历小行星数组,当我们遍历到小行星 a s t e r aster aster时,使用变量 a l i v e alive alive记录小行星 a s t e r aster aster是否还存在(即未爆炸)。

当小行星 a s t e r aster aster存在且 a s t e r < 0 aster<0 aster<0,栈顶元素非空且大于0时,说明两个小行星相互向对方移动:如果栈顶元素大于等于 a s t e r aster aster,则小行星 a s t e r aster aster发生爆炸,将 a l i v e alive alive置为 f a l s e false false;如果栈顶元素小于等于 − a s t e r -aster aster,则栈顶元素表示的小行星发生爆炸,执行出栈操作。重复以上判断直到不满足条件,如果最后 a l i v e alive alive为真,说明小行星 a s t e r aster aster不会爆炸,则将 a s t e r 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;
    }
};

Logo

权威|前沿|技术|干货|国内首个API全生命周期开发者社区

更多推荐