代码随想录 -- 栈和队列

文章目录

栈实现队列
- 描述
- 题解
用队列实现栈
- 描述
- 题解
有效的括号
- 描述
- 题解
删除字符串中的所有相邻重复项
- 描述
- 题解
逆波兰表达式求值
- 描述
- 题解
滑动窗口最大值
- 描述
- 题解：暴力
- 题解：单调队列
前 K 个高频元素
- 描述
- 题解

栈实现队列

题目链接

描述

使用两个栈实现队列的下列操作：

push(x) – 将一个元素放入队列的尾部。
pop() – 从队列首部移除元素。
peek() – 返回队列首部的元素。
empty() – 返回队列是否为空。

示例:

MyQueue queue = new MyQueue();
queue.push(1);
queue.push(2);
queue.peek();  // 返回 1
queue.pop();   // 返回 1
queue.empty(); // 返回 false

说明:

你只能使用标准的栈操作 – 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
假设所有操作都是有效的（例如，一个空的队列不会调用 pop 或者 peek 操作）。

题解

使用两个栈来模拟队列：
一个栈为入队栈，一个栈为出队栈
出队栈的top为队头，入队栈的top为队尾（存在）
入队直接放入入队栈
出队先判断出队栈是否为空，不为空直接pop，为空先将入队栈的元素加入出队栈，然后再pop

class MyQueue {
private:
    stack<int>sIn;
    stack<int>sOut;
public:
    MyQueue()=default;

    void push(int x) {
        sIn.push(x);
    }
    void pushSOut(){
        if(sOut.empty()){
            //空
            while (!sIn.empty()){
                sOut.push(sIn.top());
                sIn.pop();
            }
        }
    }
    int pop() {
        pushSOut();
        int result = sOut.top();
        sOut.pop();
        return result;
    }

    int peek() {
        pushSOut();
        return sOut.top();
    }

    bool empty() {
        return sIn.empty()&&sOut.empty();
    }
};

用队列实现栈

题目链接

描述

使用两个队列实现栈的下列操作：

push(x) – 元素 x 入栈
pop() – 移除栈顶元素
top() – 获取栈顶元素
empty() – 返回栈是否为空
注意:

你只能使用队列的基本操作-- 也就是 push to back, peek/pop from front, size, 和 is empty 这些操作是合法的。
你所使用的语言也许不支持队列。你可以使用 list 或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。
你可以假设所有操作都是有效的（例如, 对一个空的栈不会调用 pop 或者 top 操作）。

题解

class MyStack {
private:
    queue<int> qIn;
    queue<int> qOut;
    int count=0;
public:
    MyStack() = default;

    void push(int x) {
        qIn.push(x);
        count++;
    }

    void handle(int num) {
        while (num) {
            qOut.push(qIn.front());
            qIn.pop();
            num--;
        }
    }

    void OutToIn() {
        while (!qOut.empty()) {
            qIn.push(qOut.front());
            qOut.pop();
        }
    }

    int pop() {
        handle(count - 1);
        count--;
        int res = qIn.front();
        qIn.pop();
        OutToIn();
        return res;
    }

    int top() {
        handle(count - 1);
        int res = qIn.front();
        handle(1);
        OutToIn();
        return res;
    }

    bool empty() {
        return qIn.empty();
    }
};

也可以不使用conut记录长度因为count就是qIn的长度

#include<iostream>
#include<queue>

using namespace std;

class MyStack {
private:
    queue<int> qIn;
    queue<int> qOut;
public:
    MyStack() = default;

    void push(int x) {
        qIn.push(x);
    }

    void handle(int num) {
        while (num) {
            qOut.push(qIn.front());
            qIn.pop();
            num--;
        }
    }

    void OutToIn() {
        while (!qOut.empty()) {
            qIn.push(qOut.front());
            qOut.pop();
        }
    }

    int pop() {
        handle(qIn.size()-1);
        int res = qIn.front();
        qIn.pop();
        OutToIn();
        return res;
    }

    int top() {
        return qIn.back();
    }

    bool empty() {
        return qIn.empty();
    }
};


int main() {
    /**
 * Your MyStack object will be instantiated and called as such:
 * MyStack* obj = new MyStack();
 * obj->push(x);
 * int param_2 = obj->pop();
 * int param_3 = obj->top();
 * bool param_4 = obj->empty();
 */
    return 0;
}

有效的括号

题目链接

描述

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

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
示例 1:

输入: “()”
输出: true
示例 2:

输入: “()[]{}”
输出: true
示例 3:

输入: “(]”
输出: false

题解

题倒是不难不过边界情况要考虑清楚处理清楚

class Solution {
public:
    bool isValid(string s) {
        stack<char>stk;
        for (const auto &item: s) {
            switch (item) {
                case '(':
                    stk.push(item);
                    break;
                case '{':
                    stk.push(item);
                    break;
                case '[':
                    stk.push(item);
                    break;
                case ')':
                case '}':
                case ']':
                    if(stk.empty())
                        return false;
                    char c = stk.top();
                    stk.pop();
                    if(!((item==')'&&c=='(')||(item=='}'&&c=='{')||(item==']'&&c=='[')))
                        return false;
            }
        }
        if (stk.empty())return true;
        return false;
    }
};

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

题目链接

描述

给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。

在 S 上反复执行重复项删除操作，直到无法继续删除。

在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。

示例：

输入：“abbaca”
输出：“ca”
解释：例如，在 “abbaca” 中，我们可以删除 “bb” 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 “aaca”，其中又只有 “aa” 可以执行重复项删除操作，所以最后的字符串为 “ca”。
提示：

1 <= S.length <= 20000
S 仅由小写英文字母组成。

题解

class Solution {
public:
    string removeDuplicates(string s) {
        stack<char>stk;
        for (const auto &item: s) {
            if(stk.empty())stk.push(item);
            else{
                char last = stk.top();
                if (last == item)stk.pop();
                else stk.push(item);
            }
        }
        string result;
        while (!stk.empty()){
            result+=stk.top();
            stk.pop();
        }
        reverse(result.begin(),result.end());
        return result;
    }
};

逆波兰表达式求值

题目链接

描述

根据逆波兰表示法，求表达式的值。

有效的运算符包括 + , - , * , / 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。

说明：

整数除法只保留整数部分。给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。

示例 1：

输入: [“2”, “1”, “+”, “3”, " * "]
输出: 9
解释: 该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9
示例 2：

输入: [“4”, “13”, “5”, “/”, “+”]
输出: 6
解释: 该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6
示例 3：

输入: [“10”, “6”, “9”, “3”, “+”, “-11”, " * ", “/”, " * ", “17”, “+”, “5”, “+”]

输出: 22

解释:该算式转化为常见的中缀算术表达式为：

((10 * (6 / ((9 + 3) * -11))) + 17) + 5       
= ((10 * (6 / (12 * -11))) + 17) + 5       
= ((10 * (6 / -132)) + 17) + 5     
= ((10 * 0) + 17) + 5     
= (0 + 17) + 5    
= 17 + 5    
= 22

逆波兰表达式：是一种后缀表达式，所谓后缀就是指运算符写在后面。

平常使用的算式则是一种中缀表达式，如 ( 1 + 2 ) * ( 3 + 4 ) 。

该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * ) 。

逆波兰表达式主要有以下两个优点：

去掉括号后表达式无歧义，上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果。

适合用栈操作运算：遇到数字则入栈；遇到运算符则取出栈顶两个数字进行计算，并将结果压入栈中。

题解

class Solution {
public:
    int evalRPN(vector<string> &tokens) {
        stack<long long> numbers;
        string flags = "+-*/";
        int len = tokens.size();
        for (int i = 0; i < len; ++i) {
            if (flags.find(tokens[i])==string::npos)
                numbers.push(stoll(tokens[i]));
            else {
                long long num1 = numbers.top();//右操作数
                numbers.pop();
                long long num2 = numbers.top();//左操作数
                numbers.pop();
                if (tokens[i] == "+")numbers.push(num2 + num1);
                else if (tokens[i] == "-")numbers.push(num2 - num1);
                else if (tokens[i] == "*")numbers.push(num2 * num1);
                else if (tokens[i] == "/")numbers.push(num2 / num1);
            }
        }
       
        return numbers.top();
    }
};

滑动窗口最大值

题目链接

描述

给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回滑动窗口中的最大值。

进阶：

你能在线性时间复杂度内解决此题吗？

在这里插入图片描述

题解：暴力

力扣超出时间限制，行不通，时间复杂度为O(k*n)

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int>v;
        for (int i = 0; i <= nums.size()-k; ++i) {
                int max = -10000;
            for (int j = i; j < i+k; ++j) {
                if (nums[j]>max)max=nums[j];
            }
            v.push_back(max);
        }
        return v;
    }
};

题解：单调队列

有难度的题目

class Solution {
private:
    class MyQueue{
    private:
        deque<int>dq;
    public:
        // 删除滑动窗口第一个元素 （滑动窗口后移）
        // 每次弹出的时候，比较当前要弹出的数值是否等于队列出口元素的数值，如果相等则弹出。
        // 同时pop之前判断队列当前是否为空。
        void pop(int value){
            if(!dq.empty()&&value==dq.front())
                dq.pop_front();
        }
        // 如果push的数值大于入口元素的数值，那么就将队列后端的数值弹出，直到push的数值小于等于队列入口元素的数值为止。
        // 这样就保持了队列里的数值是单调从大到小的了。
        void push(int value){
            while(!dq.empty()&&value>dq.back())
                dq.pop_back();
            dq.push_back(value);
        }
        // 查询当前队列里的最大值 直接返回队列前端也就是front就可以了。
        int front(){
            return dq.front();
        }
    };
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        MyQueue mq;
        vector<int>result;
        for (int i = 0; i < k; ++i)
            mq.push(nums[i]);
        result.push_back(mq.front());
        for (int i = k; i < nums.size(); ++i) {
            mq.pop(nums[i-k]);
            mq.push(nums[i]);
            result.push_back(mq.front());
        }
        return result;
    }
};

前 K 个高频元素

题目链接

描述

给定一个非空的整数数组，返回其中出现频率前 k 高的元素。

示例 1:

输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]
示例 2:

输入: nums = [1], k = 1
输出: [1]
提示：

你可以假设给定的 k 总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。
题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的。
你可以按任意顺序返回答案。

题解

优先队列+map

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        map<int,int>mp;
        for(int num:nums){
            if (mp.find(num)!=mp.end()){
                mp[num]++;
            }else{
                mp.insert(make_pair(num,1));
            }
        }
        priority_queue<pair<int,int>>pq;
        for(auto & it : mp) {
            pq.emplace(it.second, it.first);
        }
        
        vector<int>v;
        while (k--){
            v.push_back(pq.top().second);
            pq.pop();
        }
        return v;
    }
};