232. 用栈实现队列
class MyQueue {
public:
MyQueue() {
}
void push(int x) {
++ _s;
st1.push(x);
}
int pop() {
if (_s) --_s;
while(!st1.empty())
{
st2.push(st1.top());
st1.pop();
}
int ret = st2.top();
st2.pop();
while(!st2.empty())
{
st1.push(st2.top());
st2.pop();
}
return ret;
}
int peek() {
while(!st1.empty())
{
st2.push(st1.top());
st1.pop();
}
int ret = st2.top();
while(!st2.empty())
{
st1.push(st2.top());
st2.pop();
}
return ret;
}
bool empty() {
return !_s;
}
private:
stack<int> st1,st2;
size_t _s = 0;
int _front = 0; // 4 - end -> (in) [3,2,1] (out) - front ->
};
/**
* Your MyQueue object will be instantiated and called as such:
* MyQueue* obj = new MyQueue();
* obj->push(x);
* int param_2 = obj->pop();
* int param_3 = obj->peek();
* bool param_4 = obj->empty();
*/225. 用队列实现栈
class MyStack {
public:
MyStack() {
}
void push(int x) {
que.emplace(x);
}
int pop() {
if(!que.size()) return -1;
int val = que.back();
if (que.size() == 1) que.pop();
queue<int> tque;
while (que.size() > 1)
{
tque.emplace(que.front());
que.pop();
}
que = tque;
return val;
}
int top() {
return que.back();
}
bool empty() {
return !que.size();
}
private:
queue<int> que;
};
/**
* Your MyStack object will be instantiated and called as such:
* MyStack* obj = new MyStack();
* obj->push(x);
* int param_2 = obj->pop();
* int param_3 = obj->top();
* bool param_4 = obj->empty();
*/20. 有效的括号
class Solution {
public:
// 注意这个用例 "(])" -- else res.push(c);
bool isValid(string s) {
stack<char> res;
for (char c: s)
{
if(!res.empty())
switch(c)
{
case ')': if(res.top() == '(') res.pop(); else res.push(c); break;
case ']': if(res.top() == '[') res.pop(); else res.push(c); break;
case '}': if(res.top() == '{') res.pop(); else res.push(c); break;
default : res.push(c); break;
}
else res.push(c);
}
return res.empty();
}
};1047. 删除字符串中的所有相邻重复项
1047. 删除字符串中的所有相邻重复项 - 力扣（LeetCode）
class Solution {
public:
string removeDuplicates(string s) {
if(s.size() == 1) return s;
string res;
for (char c : s)
if (!res.empty() && res.back() == c) res.pop_back();
else res += c;
return res;
}
};150. 逆波兰表达式求值
class Solution {
public:
int evalRPN(vector<string>& tokens) {
stack<int> res;
auto f = [&](const string &str){
int a = res.top();
res.pop();
int b = res.top();
res.pop();
if (str == "+") res.push(b + a);
else if (str == "-") res.push(b - a);
else if (str == "*") res.push(b * a);
else if (str == "/") res.push(b / a);
};
for (const string & str : tokens)
if (str == "+" || str == "-" || str == "*" || str == "/") f(str);
else res.push(stoi(str));
return res.top();
}
};239. 滑动窗口最大值
#include <algorithm>
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
if (k == 1) return nums;
int len = nums.size();
vector<int> res;
priority_queue<pair<int/*val*/,int/*rank*/>> priorQue;
for(int i = 0; i < k; ++ i)
priorQue.emplace(nums[i],i);
res.emplace_back(priorQue.top().first);
for(int i = k; i < len; ++ i)
{
priorQue.emplace(nums[i],i);
while (priorQue.top().second < i - k + 1)
priorQue.pop();
res.emplace_back(priorQue.top().first);
}
return res;
}
};347. 前 K 个高频元素
class Solution {
public:
class HeaplittleThenComp{
public:
bool operator()(const pair<int/*val*/,int/*cnt*/> &lRef, const pair<int/*val*/,int/*cnt*/> &rRef){
return lRef.second > rRef.second;
}
};
vector<int> topKFrequent(vector<int>& nums, int k) {
unordered_map<int/*val*/,int/*cnt*/> unorderMap;
for(int t: nums)
unorderMap[t]++;
priority_queue<pair<int/*val*/,int/*cnt*/>,
vector<pair<int/*val*/,int/*cnt*/>>,
HeaplittleThenComp> priorQue;
unordered_map<int,int>::iterator it = unorderMap.begin();
for(;it != unorderMap.end(); ++ it)
{
priorQue.emplace(*it);
if(priorQue.size() > k)
priorQue.pop();
}
vector<int> res(k);
for(int i = k - 1; i >= 0; i --){
res[i] = priorQue.top().first;
priorQue.pop();
}
return res;
}
};