代码随想录第12天 | 栈与队列part02(有题目未解决)

题目：150. 逆波兰表达式求值

思路：

1.使用栈，存储数字，遇到运算符，则取出栈顶两个数进行运算，结果在存入栈中。

坑：

1. 加减乘除运算符没有别的技巧，就是if相等 然后 +-*/ ,switch 也可以
2. 栈使用long long型，int型会溢出
3. 使用 "+"不是单引号'+'，vector<string类型> 不是 vector<char类型>
4. 编译错误，num1未定义， 作用域问题， if后没加{}

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<long long  >stack;
        for(auto & str:tokens){//注意引用&
            if(str=="+"||str=="-"||str=="*"||str=="/") {//string类型是双引号""
                long long num1=stack.top();
                stack.pop();
                long long num2=stack.top();
                stack.pop();
                long long  sum=0;
                if(str=="+")  sum=num2+num1;
                if(str=="-")  sum=num2-num1;
                if(str=="*")  sum=num2*num1;
                if(str=="/")  sum=num2/num1;      
                stack.push(sum);
            }else{
                stack.push(stoll(str));//stoll()是string转long long 类型函数
            }
        } 
        return stack.top();
    }
};

补充：

字符串类型转换
1.[数字] 转换 “字符串”
【函数名】
to_string(数字类型)； //数字类型 int long float 等
2.“字符串” 转换 [数字]
【函数名】
stoi() 对应 int
stol() 对应 long
stoll() 对应 long long

题目：239. 滑动窗口最大值（二刷题）

思路：

1. 使用双端队列deque单调队列，将滑动窗口中的值存入队列，一直保持最大值在队首，新添加元素大于队首，则全部删除，反之添加在队首后

坑：

笑鼠，看错三次题。下次好好理解题目

补充：

单调队列：保持单调递减或递增的原则的队列
双向队列deque

1. 可以在队列的两端进行元素的插入和删除操作，deque是C++STL（标准模板库）中的一种容器，
2. 包含#include
3. 常用函数

push_back()//在队列的尾部插入元素。
emplace_front()//与push_front()的作用一样 
push_front()//在队列的头部插入元素。
emplace_back()//与push_back()的作用一样 
pop_back()//删除队列尾部的元素。
pop_front()//删除队列头部的元素。
back()//返回队列尾部元素的引用。
front()//返回队列头部元素的引用。
clear()//清空队列中的所有元素。
empty()//判断队列是否为空。
size()//返回队列中元素的个数。
begin()//返回头位置的迭代器
end()//返回尾+1位置的迭代器
rbegin()//返回逆头位置的迭代器 
rend()//返回逆尾-1位置的迭代器 
insert()//在指定位置插入元素 
erase()//在指定位置删除元素 

题目：347.前 K 个高频元素（二刷题）

思路：

坑：

补充：

今日总结