题目1 150. 逆波兰表达式求值
给你一个字符串数组 tokens ，表示一个根据 逆波兰表示法 表示的算术表达式。
请你计算该表达式。返回一个表示表达式值的整数。
注意：
- 有效的算符为
'+'、'-'、'*'和'/'。 - 每个操作数（运算对象）都可以是一个整数或者另一个表达式。
- 两个整数之间的除法总是 向零截断 。
- 表达式中不含除零运算。
- 输入是一个根据逆波兰表示法表示的算术表达式。
- 答案及所有中间计算结果可以用 32 位 整数表示。
示例 1：
输入：tokens = ["2","1","+","3","*"]
输出：9
解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9
示例 2：
输入：tokens = ["4","13","5","/","+"]
输出：6
解释：该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6
示例 3：
输入：tokens = ["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 <= tokens.length <= 104tokens[i]是一个算符（"+"、"-"、"*"或"/"），或是在范围[-200, 200]内的一个整数
思路
用一个辅助栈用于存放每个数，当碰到计算符号时进行出栈两数计算，再将结果放回栈，直到tokens遍历结束。
代码
class Solution {
public:
int evalRPN(vector<string>& tokens) {
stack<int> numStack;
int lft, rht;
for(auto &str : tokens)
{
//进行出栈计算并入栈
#define OPERATIONS(STACK, OPERATOR, OPER) if(str.size() == 1 && str[0] == OPERATOR){\
rht = STACK.top();STACK.pop(); \
lft = STACK.top();STACK.pop(); \
lft = lft OPER rht; \
STACK.push(lft); \
continue;}
OPERATIONS(numStack, '+', +);
OPERATIONS(numStack, '-', -);
OPERATIONS(numStack, '*', *);
OPERATIONS(numStack, '/', /);
#undef OPERATIONS
rht = atoi(str.c_str());
numStack.push(rht);
}
return numStack.top();
}
};
题目2 239. 滑动窗口最大值*
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。
示例 1：
输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置 最大值
--------------- -----
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
示例 2：
输入：nums = [1], k = 1
输出：[1]
提示：
1 <= nums.length <= 105-104 <= nums[i] <= 1041 <= k <= nums.length
思路
使用自定义的两个push和pop接口来模拟优先级队列，保证队列中元素的顺序从高到低排序，通过这种方法，每次进行pop和push以及取出max存入vector对象来遍历每个数。
代码
class Solution {
public:
void pop(deque<int> &myQueue, int& value)
{
if(!myQueue.empty() && myQueue.front() == value)
{
myQueue.pop_front();
}
}
// @brief 维护优先级队列
void push(deque<int> &myQueue, int& value)
{
while(!myQueue.empty() && myQueue.back() < value)
{
myQueue.pop_back();
}
myQueue.push_back(value);
}
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
deque<int> myQueue;
vector<int> result;
result.reserve(nums.size() - k + 1);
int max = INT_MIN;
for(int i = 0; i < k; i++)
{
push(myQueue, nums[i]);
}
result.push_back(myQueue[0]);
for(int i = k; i < nums.size(); i++)
{
pop(myQueue, nums[i-k]);
push(myQueue, nums[i]);
result.push_back(myQueue[0]);
}
return result;
}
};
题目3 347. 前 K 个高频元素
给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
示例 1:
输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]
示例 2:
输入: nums = [1], k = 1
输出: [1]
提示：
1 <= nums.length <= 105k的取值范围是[1, 数组中不相同的元素的个数]- 题目数据保证答案唯一，换句话说，数组中前
k个高频元素的集合是唯一的
思路
队列
用deque来存储每个元素的值和出现次数，并保证deque对象的size<=k。这种方法效率不高，因为每次进行插入元素时要比较很多次。
代码
class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
deque<pair<int, int>> myQueue; // 用来存储频率最高的元素和频率
sort(nums.begin(), nums.end()); // 将 nums 排序，方便统计频率
int num = 1; // 当前元素的频率
for(int i = 1; i < nums.size(); i++) {
// 统计每个元素的出现次数
if (nums[i] == nums[i - 1]) {
num++;
} else {
// 把频率插入到队列中
insertIntoQueue(myQueue, nums[i - 1], num, k);
num = 1; // 重置 num，统计下一个元素
}
}
// 处理最后一个元素的频率
insertIntoQueue(myQueue, nums.back(), num, k);
// 提取结果
vector<int> result;
for(auto &iter : myQueue) {
result.push_back(iter.first);
}
return result;
}
// 插入到 deque 中并保持前 k 个高频元素
void insertIntoQueue(deque<pair<int, int>>& myQueue, int value, int freq, int k) {
if(myQueue.empty()) {
myQueue.push_back({value, freq});
} else {
// 如果队列的大小小于 k 或者当前元素频率大于队列最后一个元素的频率
if (myQueue.size() < k || myQueue.back().second < freq) {
// 如果队列已经满了，移除频率最低的元素
if (myQueue.size() == k) {
myQueue.pop_back();
}
// 将新元素按频率插入到正确位置
auto iter = myQueue.begin();
while (iter != myQueue.end() && iter->second > freq) {
iter++;
}
myQueue.insert(iter, {value, freq});
}
}
}
};
优先级队列*
忘了优先级队列的使用。。。2刷补上代码
标签：10,队列,nums,int,随想录,back,push,myQueue,day From： https://www.cnblogs.com/code4log/p/18405347