150. 逆波兰表达式求值

LeetCode题目

注意事项

• 不要搞错栈内元素和操作符的使用顺序

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> collect;
        for (int i = 0; i < tokens.size(); i++) {
            if (tokens[i] == "+") {
                int x1 = collect.top();
                collect.pop();
                int x2 = collect.top();
                collect.pop();
                collect.push(x1 + x2);
            } else if (tokens[i] == "-") {
                int x1 = collect.top();
                collect.pop();
                int x2 = collect.top();
                collect.pop();
                collect.push(x2 - x1);
            } else if (tokens[i] == "*") {
                int x1 = collect.top();
                collect.pop();
                int x2 = collect.top();
                collect.pop();
                collect.push(x1 * x2);
            } else if (tokens[i] == "/") {
                int x1 = collect.top();
                collect.pop();
                int x2 = collect.top();
                collect.pop();
                collect.push(x2 / x1);
            } else
                collect.push(stoi(tokens[i]));
        }
        return collect.top();
    }
};

239. 滑动窗口最大值

LeetCode题目

注意事项

• 考虑操作的原因：即并不需要考虑两个极大值中间的数（可以省略不看）

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int m = -1;
        vector<int> result; 
        deque<int> collect;
        for (int i = 0; i < k; i++) {
            while(!collect.empty() && nums[i] > collect.back())
                collect.pop_back();
            collect.push_back(nums[i]);
        }
        result.push_back(collect.front());
        for (int i = k; i < nums.size(); i++) {
            if (nums[i-k] == collect.front()) 
                collect.pop_front();
            while(!collect.empty() && nums[i] > collect.back())
                collect.pop_back();
            collect.push_back(nums[i]);
            result.push_back(collect.front());
        }
        return result;
    }
};

347.前 K 个高频元素

LeetCode题目

注意事项

• 考虑一个新的概念：优先级队列

priority_queue<pair<int, int>, vector<pair<int, int>>, mycomparison> pri_que;

• 构造方式：小顶堆，构建最大的树

class mycomparison {
    public:
        bool operator()(const pair<int, int>& lhs, const pair<int, int>& rhs) {
            return lhs.second 》 rhs.second;
        }
    };

• 构造方式：大顶堆，构建最小的树

class mycomparison {
    public:
        bool operator()(const pair<int, int>& lhs, const pair<int, int>& rhs) {
            return lhs.second < rhs.second;
        }
    };

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;
        for (int i = 0; i < nums.size(); i++)
            map[nums[i]]++;

        priority_queue<pair<int, int>, vector<pair<int, int>>, mycomparison>
            pri_que;
        for (auto it = map.begin(); it != map.end(); it++) {
            pri_que.push({it->first, it->second});
            if (pri_que.size() > k)
                pri_que.pop();
        }
        vector<int> result;
        while (!pri_que.empty()) {

            result.push_back(pri_que.top().first);
            pri_que.pop();
        }
        return result;
    }
};