前置知识

用到了stoi(),以及to_string()两个函数

• 头文件#include<cstring>
• stoi() 和 atoi()
  • stoi 的参数是 const string* 类型
  • atoi 的参数是 const char* 类型
• stoi() 会对转化后的数进行检查，判断是否会超出 int 范围，如果超出范围就会报错；
• atoi() 不会对转化后的数进行检查，超出上界，输出上界，超出下界，输出下界；
• to_string():将数字常量(int,double,long等)转换为字符串（string),返回转换好的字符串.

150.逆波兰表达式求值

几乎一次成功
虽然写得很丑陋

class Solution {
public:
  bool isOperator(string x) {
    return x == "+" || x == "-" || x == "*" || x == "/";
  };
  int evalRPN(vector<string> &tokens) {
    int a1 = 0;
    int a2 = 0;
    stack<string> st;
    for (int i = 0; i < tokens.size(); i++) {
      if (st.empty() || !isOperator(*(tokens.begin() + i))) {
        st.push(*(tokens.begin() + i));
      } else {
        a1 = stoi(st.top());
        st.pop();
        a2 = stoi(st.top());
        st.pop();

        if (*(tokens.begin() + i) == "+") {
          st.push(to_string(a2 + a1));
        }
        if (*(tokens.begin() + i) == "-") {
          st.push(to_string(a2 - a1));
        }
        if (*(tokens.begin() + i) == "*") {
          st.push(to_string(a2 * a1));
        }
        if (*(tokens.begin() + i) == "/") {
          st.push(to_string(a2 / a1));
        }
      }
    }
    return stoi(st.top());
  }
};

239.滑动窗口最大值

由于卡哥使用单调队列解决的,看视频的过程中了解到了大小顶堆,优先级队列这个概念,于是我尝试使用大小顶堆来解决,但是由于一开始没看清题目,所以以为窗口一直为3,不过思路应该没问题

其实思路就是用一个双端队列来维护,大顶堆用来比较.

class Solution {
public:
  vector<int> maxSlidingWindow(vector<int> &nums, int k) {
    priority_queue<int> big_heap;
    deque<int> que;
    vector<int> res;
    auto it = nums.begin();
    while (it + k - 1 != nums.end()) {
      if (que.size() != k) {
        for (int i = 0; i < k; i++) {
          que.push_front(*it);
          it++;
        }
        it -= k - 1;
      }
      for (int i = 0; i < k; i++) {
        big_heap.push(que.back());
        que.pop_back();
      }
      res.push_back(big_heap.top());
      for (int i = 0; i < k; i++) {
        big_heap.pop();
      }
    }

    return res;
  }
};

结果测试超时了一个...

优化了一下,还是不行

class Solution {
public:
  vector<int> maxSlidingWindow(vector<int> &nums, int k) {
    priority_queue<int> big_heap;
    deque<int> que;
    vector<int> res;
    auto it = nums.begin();
    while (it != nums.end()) {
      if (que.size() != k) {
        for (int i = 0; i < k; i++) {
          que.push_front(*it);
          it++;
        }
      } else {
        que.pop_back();
        que.push_front(*it);
        it++;
      }

      for (int i = 0; i < k; i++) {
        big_heap.push(*(que.begin()+ i));
      }
      res.push_back(big_heap.top());
      for (int i = 0; i < k; i++) {
        big_heap.pop();
      }
    }

    return res;
  }
};

还是老老实实用单调队列吧.
代码和网站上一样,就不贴了

347.前 K 个高频元素

关于优先级队列

声明

priority_queue< type, container, function>；

第一个参数不能省略,但是后两个可以.

• type: 保存的数据类型
• container: 实现优先队列的底层容器,必须是可随机访问的容器，例如vector,deque,而不能使用list;
• function: 元素之间比较的方式,其实就是一个comparator

在STL中，默认情况下（不加后面两个参数）是以vector为容器，以 operator< 为比较方式，所以在只使用第一个参数时，优先队列默认是一个最大堆，每次输出的堆顶元素是此时堆中的最大元素。

解题思路

利用小顶堆(底层为二叉树)能排序的特性(根节点最小),来维护前K个高频元素(插入元素与根节点做比较,如果比根节点大就pop).首先遍历元素的复杂度为n,二叉树插入操作复杂度为Logk(小顶堆只维护k个元素),所以时间复杂度为O(n*Logk).

注意

本题的优先级队列保存的数据类型是pair<int, int>,因为pair能保存一对数据,且可以排序,如果用map是不可排序的.