力扣日记 cpp 150 239 347 71
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 (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; while (!s.empty()) { res = s.top() + res; s.pop(); } if (res == "") return "/"; return res; } };
