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

150. 逆波兰表达式求值 - 力扣（LeetCode）

给你一个字符串数组 tokens ，表示一个根据 逆波兰表示法 表示的算术表达式。

请你计算该表达式。返回一个表示表达式值的整数。

注意：

  • 有效的算符为 '+'、'-'、'*' 和 '/' 。

  • 每个操作数（运算对象）都可以是一个整数或者另一个表达式。

  • 两个整数之间的除法总是 向零截断 。

  • 表达式中不含除零运算。

  • 输入是一个根据逆波兰表示法表示的算术表达式。

  • 答案及所有中间计算结果可以用 32 位 整数表示。

思路：因为是二刷所以看到就想到用栈来做，每次遇到有效运算符则将栈中的两个数字弹出进行数值的运算，运算后的结果重新压入栈中。

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

stoll的用法

对c++的函数还不够熟练，因此在这里做些笔记。

作用：将字符串转化成 long long 整数

stoll的申明如下：

long long stoll(const std::string& str, std::size_t* idx = 0, int base = 10);

可以看出stoll的返回值的类型为long long ，其参数有三个str、idx、base。

  • str：所需转换的字符串

  • idx：此参数指定指向size_t类型的对象的指针，该对象的值由函数设置为数值后str中下一个字符的位置。此参数也可以是空指针，在这种情况下，将不使用该参数。

  • base：此参数指定“数字基数”，以确定用于解释字符的数字系统。如果基数为0，则它使用的基数由序列中的格式确定。默认基数为10。、

    • base = 0：自动检测数值进制后进行转换

    • base = 16：指定十六进制进行转换

    • base = 10：指定十进制进行转换（默认）

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

239. 滑动窗口最大值 - 力扣（LeetCode）

给你一个整数数组 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

思路：使用单调队列，单调队列指的是队列的形态是单调的，要么单调递增，要么单调递减，此题中使用的是单调递减的队列，因为C++中没有对应的容器，因此需要自己手动设计一个，其代码如下：

class MyQueue{
    public:
        deque<int>que;
        void pop(int value){
            if(!que.empty() && value == que.front()){
                que.pop_front();
            }
        }
        void push(int value){
            //因为是单调队列因此队列从后往前走若发现比push进来的数值小则将该值弹出，因为可能不止弹出一个数值因此使用while
            while(!que.empty() && value > que.back()){
                que.pop_back();
            }
            que.push_back(value);
        }
        int front(){
            return que.front();
        }
    };

pop：判断一下队列的首位元素是否是我们要pop的元素，若不是则说明已经因为单调递减的原因被pop了（针对本题而言特意这样写的）

push：因为单调递减的原因，在每个数值push进队列时候需要从后往前 查找是否push进队列的值比队列末位的值要大，若是大则要将末尾的值pop出后继续比对；若是小则直接将数值插入队列的末尾即可。（单调队列的push都得这么写，通用）

front：直接输出队列的首位元素即为最大值。

得到上述队列后可以轻松的解答这题，代码如下：

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){
            //因为是单调队列因此队列从后往前走若发现比push进来的数值小则将该值弹出，因为可能不止弹出一个数值因此使用while
            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;
        int left = 0;
        vector<int> res;
        // 将前k个元素放入que中
        for(int i = 0; i<k;i++){
            que.push(nums[i]);
        }
        //初始数据push到res中
        res.push_back(que.front());
        for(int right = k; right < nums.size();right++){
            que.pop(nums[left]);
            left++;
            que.push(nums[right]);
            res.push_back(que.front());
        }
        return res;
    }
};

题目： 347.前 K 个高频元素（重点题）

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

示例 1:

  • 输入: nums = [1,1,1,2,2,3], k = 2

  • 输出: [1,2]

示例 2:

  • 输入: nums = [1], k = 1

  • 输出: [1]

提示：

  • 你可以假设给定的 k 总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。

  • 你的算法的时间复杂度必须优于 O(n \log n) , n 是数组的大小。

  • 题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的。

  • 你可以按任意顺序返回答案。

思路一

思路：有一个非常常见的想法，只要出现频率直接用map，后根据map的value来进行一个排序，确实本题可以这样做但也存在缺陷，实现代码如下：

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int,int> nums_map;
        for(int i = 0; i<nums.size();i++){
            nums_map[nums[i]] ++;
        }
        vector<pair<int, int>> elements(nums_map.begin(), nums_map.end());
​
        sort(elements.begin(), elements.end(), 
            [](const auto& a, const auto& b) {
                return a.second > b.second;
            });
        
        //选取elements中的排序最高的即可
        vector<int> result;
        for (int i = 0; i < k && i < elements.size(); ++i) {
            result.push_back(elements[i].first);
        }
        
        return result;
    }
};

注意：std::sort 不能直接用于 std::map，因为 map 的迭代器不支持随机访问。

缺点：

  1. 改用 vector 存储并排序（适用于数据量较小的情况）。

  2. 使用小（大）顶堆（适用于大数据量，时间复杂度更优 O(n log k)）。

接下来要使用堆因此在此处介绍一下STL优先队列

STL堆/优先队列（priority_queue）（学习ing）

优先级队列需要包含头文件<queue>，优先级队列的定义如下：

priority_queue<typename, container, functional>

  • typename是数据的类型；

  • container是容器类型，可以是vector,queue等用数组实现的容器，不能是list，默认可以用vector；

  • functional是比较的方式，默认是大顶堆（就是元素值越大，优先级越高）；如果使用C++基本数据类型，可以直接使用自带的less和greater这两个仿函数（默认使用的是less，就是构造大顶堆，元素小于当前节点时下沉）。使用自定义的数据类型的时候，可以重写比较函数，也可以进行运算符重载（less重载小于“<”运算符，构造大顶堆；greater重载大于“>”运算符，构造小顶堆）。

自定义比较函数的5种方式

可以使用现成的 less<T>来定义大顶堆 greater<T>来定义小顶堆

从文档出可以看到，传入的可以是 函数指针或者 函数对象（类对操作符()进行了重载，）

参考链接：函数指针和函数对象 参考链接：decltype

方式一：struct重载运算符()（传入函数对象 ）
struct cmp{
   bool operator()(vector<int>&a,vector<int>&b){
       return a[0]>b[0]; 
   }
};
priority_queue<vector<int>,vector<vector<int>>,cmp> q;//小顶堆
方式二：class重载运算符()（传入函数对象 ）
class cmp{   
public:
    bool operator()(vector<int>&a,vector<int>&b){
        return a[0]>b[0]; 
    }
};
priority_queue<vector<int>,vector<vector<int>>,cmp> q;//小顶堆

注意：要写在public中

方法三：定义函数（传入函数指针 ）
bool cmp(vector<int>&a,vector<int>&b){
	return a[0]>b[0];
}
priority_queue<vector<int>,vector<vector<int>>,decltype(&cmp)> q(cmp);//小顶堆

需要通过decltype()关键字从而推导指针的类型decltype(&cmp)

注意：如果作为类成员函数，一定要声明static

static bool cmp(vector<int>&a,vector<int>&b){
	return a[0]>b[0];
}
方法四：lambda表达式（传入函数指针 ）
auto cmp=[](vector<int>&a,vector<int>&b)->bool{
            return a[0]>b[0];
        };

priority_queue<vector<int>,vector<vector<int>>,decltype(cmp)> q(cmp);//小顶堆
方式五：function包装lambda表达式（传入函数指针）

要加入头文件#include<functional>

function<bool(vector<int>&,vector<int>&)> cmp=[](vector<int>&a,vector<int>&b)->bool{
            return a[0]>b[0];
        };
priority_queue<vector<int>,vector<vector<int>>,decltype(cmp)> q(cmp);//小顶堆

通过重写仿函数来支持自定义数据类型

仿函数是通过重载“()”运算符来模拟函数操作的类。

先自定义一个类Data，将id作为该类的关键字，进行比较，重写仿函数。

//自定义数据类型，Data类
class Data
{
public:
	Data(int i, int d) :id(i), data(d) {}
	~Data() {}
	int getId() { return id; }
	int getData() { return data; }
private:
	int id;
	int data;
};
//重写仿函数，完成less的功能，也可以用class定义类，此时需要将运算符重载函数设为public
//结构体struct中默认是访问类型是public
struct cmp    
{
	bool operator() ( Data &a, Data &b) {
		return a.getId() < b.getId();
	}
};
 
int main(void){
    priority_queue<Data, vector<Data>, cmp > priQueMaxFirst;//该优先级队列维护一个大顶堆，因此最大的元素最先出队
    ...//一系列操作
    ...
    return 0;
}

通过运算符重载来支持自定义比较函数

运算符重载的话，由于是重载双目运算符，因此需要使用友元函数，我们在类内声明友元函数，在类外实现友元函数，如下：

//自定义数据类型，Data类
class Data
{
public:
	Data(int i, int d) :id(i), data(d) {}
	~Data() {}
	int getId() { return id; }
	int getData() { return data; }
	friend bool operator < (const Data &a, const Data &b);//运算符重载，友元函数可以访问类的私有成员
private:
	int id;
	int data;
};
//重载“<”运算符，仿函数less中需要使用
bool operator < (const Data &a, const Data &b) {
	return a.id < b.id;
}
 
int main(void){
    priority_queue<Data, vector<Data>, less<Data> > priQueMaxFirst;//该优先级队列维护一个大顶堆，因此最大的元素最先出队
    ...//一系列操作
    ...
    return 0;
}

优先队列的方法

  1. push()：向优先队列中插入元素，插入的元素的优先级由其权值决定。

  2. pop()：从优先队列中弹出最小的元素，将其从队列中删除。

  3. top()：获取队列中最小的元素，不会将其从队列中删除。

  4. empty()：判断队列是否为空，为空返回true，不为空返回false。

  5. size()：获取队列中元素的个数。

复杂度：

push

pop

top

empty

O(logn)

O(logn)

O(1)

O(1)

引用

  1. C++——优先级队列（priority_queue）_c++优先队列-CSDN博客）很好的博客，对初学cpp的人非常友好。

  2. c++优先队列priority_queue（自定义比较函数）_c++优先队列自定义比较-CSDN博客付费内容，大致和我摘的差不多，但做过一定的修改

思路二

思路：使用优先级队列，通过map记录了频率后通过小顶堆来实现，小顶堆顶部的元素永远是当前堆中频率出现最少的，因此当遍历map中所有的值后保留在堆中的即为频率最高的元素。其中堆需要维持的大小即为所需要保留的前k高个元素的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> nums_map;
        for(int i = 0; i<nums.size();i++){
            nums_map[nums[i]] ++;
        }
        priority_queue<pair<int,int>,vector<pair<int,int>>,mycomparison> pri_que;
​
        for(auto it = nums_map.begin();it != nums_map.end(); it++){
            pri_que.push(*it);
            if (pri_que.size() > k) { // 如果堆的大小大于了K，则队列弹出，保证堆的大小一直为k
                pri_que.pop();
            }
        }
        
        vector<int> result(k);
        //先弹出的频率较低，后弹出的频率较高
        for (int i = k - 1; i >= 0 ; i--) {
            result[i] = pri_que.top().first;
            pri_que.pop();
        }
        
        return result;
    }
};