C++ LeetCode 算法题解析：逆波兰表达式与滑动窗口

150 逆波兰表达式求值

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

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

注意：

• 有效的算符为 '+'、'-'、'*' 和 '/'。
• 每个操作数（运算对象）都可以是一个整数或者另一个表达式。
• 两个整数之间的除法总是 向零截断。
• 表达式中不含除零运算。
• 输入是一个根据逆波兰表示法表示的算术表达式。
• 答案及所有中间计算结果可以用 32 位 整数表示。

后缀表达式求值是前后中里面最简单的。

class Solution {
public:
    stack<int> data;
    int evalRPN(vector<string>& tokens) {
        int ans;
        int source1, source2;
        for (string str : tokens) {
            if (str == "+" || str == "-" || str == "*" || str == "/") {
                source1 = data.top(); data.pop();
                source2 = data.top(); data.pop();
                if(str == "+") data.push(source1 + source2);
                if(str == "-") data.push(source2 - source1);
                if(str == "*") data.push(source1 * source2);
                if(str == "/") data.push(source2 / source1);
            } else {
                data.push(stoi(str));
            }
        }
        return data.top();
    }
};

239 滑动窗口最大值

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回 滑动窗口中的最大值。

给出最大堆版本的和优先队列版本的，本质上都是堆。优先队列表征出了一个单调递减队列，会动态维护队列中元素。具体方法为：如果元素入队后队列符合单调递减，则入队；如果元素入队后不符合单调递减，则队尾不断出队，直到符合条件后停止淘汰队尾，然后元素入队。因为需要的是 top1 不是 topk，所以使用优先级队列更好。

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int length = nums.size();
        priority_queue<pair<int, int>> maxheap;
        for (int i = 0; i < k; i++) {
            maxheap.push({nums[i], i});
        }
        int left = 0, right = k;
        vector<int> res;
        res.emplace_back(maxheap.top().first);
        while (right < length) {
            left++;
            if (right != length) maxheap.push({nums[right], right});
            right++;
            while (!maxheap.empty() && maxheap.top().second < left) {
                maxheap.pop();
            }
            res.emplace_back(maxheap.top().first);
        }
        return res;
    }
};

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

347 前 K 个高频元素

给你一个整数数组 nums 和一个整数 k，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

需要注意，在 pair 里面，频率是 first，元素是 second。这样的话可以顺水推舟 greater 缺省按照字典序排序。否则需要自行制定比较方法。

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        vector<int> res;
        unordered_map<int, int> m;
        using Node = pair<int, int>; // frequency, element.
        priority_queue<Node, vector<Node>, greater<Node>> q;
        for (int num : nums) {
            m[num] += 1;
        }
        for (auto it = m.begin(); it != m.end(); it++) {
            q.push({it->second, it->first});
            if (q.size() > k) q.pop();
        }
        while (!q.empty()) {
            res.emplace_back(q.top().second);
            q.pop();
        }
        return res;
    }
};

71 简化路径

给你一个字符串 path，表示指向某一文件或目录的 Unix 风格 绝对路径（以 '/' 开头），请你将其转化为 更加简洁的规范路径。

在 Unix 风格的文件系统中规则如下：

• 一个点 '.' 表示当前目录本身。
• 此外，两个点 '..' 表示将目录切换到上一级（指向父目录）。
• 任意多个连续的斜杠（即，'//' 或 '///'）都被视为单个斜杠 '/'。
• 任何其他格式的点（例如，'...' 或 '....'）均被视为有效的文件/目录名称。

返回的 简化路径 必须遵循下述格式：

• 始终以斜杠 '/' 开头。
• 两个目录名之间必须只有一个斜杠 '/'。
• 最后一个目录名（如果存在）不能 以 '/' 结尾。
• 此外，路径仅包含从根目录到目标文件或目录的路径上的目录（即，不含 '.' 或 '..'）。

返回简化后得到的 规范路径。

可以使用 size_t 类型存储位置和判断 string::npos，更优雅，此处未使用。需要注意 erase 和 length 之间的动态关系。

class Solution {
public:
    string simplifyPath(string path) {
        int length = path.size();
        if (length > 0 && path[length - 1] == '/') path.erase(length - 1, 1);
        for (int i = 0; i < path.size(); i++) {
            if (i > 0 && path[i] == '/' && path[i - 1] == '/') {
                path.erase(i - 1, 1);
                i--;
            }
        }
        stack<string> s;
        int start = 0, end = 0;
        int newlength = path.size();
        for (int i = 0; i < newlength; i++) {
            if (path[i] == '/') start = i;
            if (i == newlength - 1 || path[i + 1] == '/') end = i;
            if (start < end) {
                string sub = path.substr(start, end - start + 1);
                if (sub == "/.") { // nop.
                } else if (sub == "/..") {
                    if (!s.empty()) {
                        s.pop();
                    }
                } else {
                    s.push(sub);
                }
            }
        }
        string res;
        while (!s.empty()) {
            res = s.top() + res;
            s.pop();
        }
        if (res == "") return "/";
        return res;
    }
};