代码随想录算法训练营第十一天|150. 逆波兰表达式求值 、239. 滑动窗口最大值、347.前 K 个高频元素

本文主要是介绍代码随想录算法训练营第十一天|150. 逆波兰表达式求值 、239. 滑动窗口最大值、347.前 K 个高频元素，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Leetcode150. 逆波兰表达式求值

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

C++：

class Solution {
public:int evalRPN(vector<string>& tokens) {stack<long long> st; for (int i = 0; i < tokens.size(); i++) {if (tokens[i] == "+" || tokens[i] == "-" || tokens[i] == "*" || tokens[i] == "/") {long long num1 = st.top();st.pop();long long num2 = st.top();st.pop();if (tokens[i] == "+") st.push(num2 + num1);if (tokens[i] == "-") st.push(num2 - num1);if (tokens[i] == "*") st.push(num2 * num1);if (tokens[i] == "/") st.push(num2 / num1);} else {st.push(stoll(tokens[i]));}}int result = st.top();st.pop();return result;}
};

Python：

operator模块：模块提供了一套与Python的内置运算符对应的高效率函数

（1）内置封装函数：mul、add、sub

（2）格式举例：mul(x, y) == x * y

from operator import add, sub, muldef div(x, y):# 使用整数除法的向零取整方式return int(x / y) if x * y > 0 else -(abs(x) // abs(y))class Solution(object):op_map = {'+': add, '-': sub, '*': mul, '/': div}def evalRPN(self, tokens: List[str]) -> int:stack = []for token in tokens:if token not in {'+', '-', '*', '/'}:stack.append(int(token))else:op2 = stack.pop()op1 = stack.pop()stack.append(self.op_map[token](op1, op2))  # 第一个出来的在运算符后面return stack.pop()

Leetcode239. 滑动窗口最大值

题目链接：239. 滑动窗口最大值

C++：（单调队列）

单调队列：将队列元素通过最大值顶出比他小的值的方式实现单调队列排序

class Solution {
private:class MyQueue { //单调队列（从大到小）public:deque<int> que;void pop(int value) {if (!que.empty() && value == que.front()) {que.pop_front();}}void push(int value) {while (!que.empty() && value > que.back()) {que.pop_back();}que.push_back(value);}int front() {return que.front();}};
public:vector<int> maxSlidingWindow(vector<int>& nums, int k) {MyQueue que;vector<int> result;for (int i = 0; i < k; i++) { // 先将前k的元素放进队列que.push(nums[i]);}result.push_back(que.front()); // result 记录前k的元素的最大值for (int i = k; i < nums.size(); i++) {que.pop(nums[i - k]); // 滑动窗口移除最前面元素que.push(nums[i]); // 滑动窗口前加入最后面的元素result.push_back(que.front()); // 记录对应的最大值}return result;}
};

Python：

from collections import dequeclass MyQueue: #单调队列（从大到小def __init__(self):self.queue = deque()def pop(self, value):if self.queue and value == self.queue[0]:self.queue.popleft()def push(self, value):while self.queue and value > self.queue[-1]:self.queue.pop()self.queue.append(value)def front(self):return self.queue[0]class Solution:def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:que = MyQueue()result = []for i in range(k): #先将前k的元素放进队列que.push(nums[i])result.append(que.front()) #result 记录前k的元素的最大值for i in range(k, len(nums)):que.pop(nums[i - k]) #滑动窗口移除最前面元素que.push(nums[i]) #滑动窗口前加入最后面的元素result.append(que.front()) #记录对应的最大值return result

Leetcode347.前 K 个高频元素

题目链接：347. 前 K 个高频元素

C++：（太难了，代码半天才看懂）

数据结构priority_que（顶堆：二叉树实现）

（1）要包含头文件#include<queue>

（2）定义：priority_que<数据类型, 容器类型, 仿函数>，当需要用自定义的数据类型时才需要传入这三个参数，否则默认为大顶堆。（仿函数：就是使一个类的使用看上去像一个函数。其实现就是类中实现一个operator()，这个类就有了类似函数的行为，就是一个仿函数类)

（3）含义：如果仿函数（比较方式）返回为真，则进行之后的push操作

（4）大顶堆：堆顶元素最大；小顶堆：堆顶元素最小

（5）方法：pop从堆顶弹出，push向堆底压入

C++：

class Solution {
public:// 小顶堆class mycomparison {public:bool operator()(const pair<int, int>& lhs, const pair<int, int>& rhs) {return lhs.second > rhs.second;}};vector<int> topKFrequent(vector<int>& nums, int k) {// 要统计元素出现频率unordered_map<int, int> map; // map<nums[i],对应出现的次数>for (int i = 0; i < nums.size(); i++) {map[nums[i]]++;}// 对频率排序// 定义一个小顶堆，大小为kpriority_queue<pair<int, int>, vector<pair<int, int>>, mycomparison> pri_que;// 用固定大小为k的小顶堆，扫面所有频率的数值for (unordered_map<int, int>::iterator it = map.begin(); it != map.end(); it++) {pri_que.push(*it);if (pri_que.size() > k) { // 如果堆的大小大于了K，则队列弹出，保证堆的大小一直为kpri_que.pop();}}// 找出前K个高频元素，因为小顶堆先弹出的是最小的，所以倒序来输出到数组vector<int> result(k);for (int i = k - 1; i >= 0; i--) {result[i] = pri_que.top().first;pri_que.pop();}return result;}
};

这篇关于代码随想录算法训练营第十一天|150. 逆波兰表达式求值 、239. 滑动窗口最大值、347.前 K 个高频元素的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---