Day 10 逆波兰表达式求值，滑动窗口的最大值，前k个高频词

逆波兰表达式求值

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

#include<iostream>
using namespace std;
#include<stack>
string s;
int main()
{
	string s;
	cin >> s;
	stack<int>u;
	for (int i = 0; i < s.size(); i++)
	{
		if (s[i] == '+' || s[i] == '-' || s[i] == '*' || s[i] == '/')
		{
			int num1 = u.top();
			u.pop();
			int num2 = u.top();
			u.pop();
			if (s[i] == '+')
			{
				u.push(num1 + num2);
			}
			if (s[i] == '-')
			{
				u.push(num2 - num1);

			}
			if (s[i] == '*')
			{
				u.push(num1 * num2);
			}
			if (s[i] == '/')
			{
				u.push(num2 / num1);
			}
	    }
		else
		{
			u.push(s[i]-'0');
		}
	}
	int result = u.top();
	cout << result;
}

滑动窗口的最大值

#include<iostream>
#include<vector>
using namespace std;
#include<deque>
vector<int>v;
class mydeque
{
public:
	mydeque(){}
	
	deque<int>u;
	void pop(int x)
	{
		if (!u.empty() && x == u.front())
		{
			u.pop_front();
		}
	}
	void push(int x)
	{
		while (!u.empty() && x > u.back())
		{
			u.pop_back();
		}
		u.push_back(x);
	}
	void getmax()
	{
		v.push_back(u.front());
	}

};
int main()
{
	
	int k;
	cin >> k;
	int n;
	cin >> n;
	vector<int>z;

	while (n--)
	{
		int num;
		cin >> num;
		z.push_back(num);
	}
	mydeque w;
	for (int i = 0; i < k; i++)
	{
		w.push(z[i]);
		
	}
	w.getmax();
	for (int i = k; i < z.size();i++)
	{
		w.pop(z[i - k]);
		w.push(z[i]);
	
		w.getmax();
	}
	for (int i = 0; i < v.size(); i++)
	{
		cout << v[i] << " ";
	}
}

前k个高频词

大顶堆推的是大，小顶堆推的是小 

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]]++;
        }

        // 对频率排序
        // 定义一个小顶堆，大小为k
        priority_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，则队列弹出，保证堆的大小一直为k
                pri_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;

    }
};