栈与队列
用栈实现队列
LeetCode.232
核心代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
| class MyQueue {
public:
MyQueue() {}
void push(int x) {
MyStackIn.push(x);
}
int pop() {
while(!MyStackIn.empty()){
MyStackOut.push(MyStackIn.top());
MyStackIn.pop();
}
int out = MyStackOut.top();
MyStackOut.pop();
while(!MyStackOut.empty()){
MyStackIn.push(MyStackOut.top());
MyStackOut.pop();
}
return out;
}
int peek() {
while(!MyStackIn.empty()){
MyStackOut.push(MyStackIn.top());
MyStackIn.pop();
}
int out = MyStackOut.top();
while(!MyStackOut.empty()){
MyStackIn.push(MyStackOut.top());
MyStackOut.pop();
}
return out;
}
bool empty() {
return MyStackIn.empty();
}
private:
stack<int> MyStackIn;
stack<int> MyStackOut;
};
|
用队列实现栈
LeetCode.225
核心代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| class MyStack {
public:
MyStack() {}
void push(int x) {
MyQueueIn.push(x);
}
int pop() {
while(MyQueueIn.size()!=1){
MyQueueOut.push(MyQueueIn.front());
MyQueueIn.pop();
}
int out = MyQueueIn.front();
MyQueueIn.pop();
while(!MyQueueOut.empty()){
MyQueueIn.push(MyQueueOut.front());
MyQueueOut.pop();
}
return out;
}
int top() {
return MyQueueIn.back();
}
bool empty() {
return MyQueueIn.empty();
}
private:
queue<int> MyQueueIn;
queue<int> MyQueueOut;
};
|
有效的括号（⭐）
LeetCode.20
核心代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| bool isValid(string s) {
if (s.size() % 2 != 0) return false;
stack<char> st;
for (int i = 0; i < s.size(); i++) {
if (s[i] == '(') st.push(')');
else if (s[i] == '{') st.push('}');
else if (s[i] == '[') st.push(']');
else if (st.empty() || st.top() != s[i]) return false;
else st.pop();
}
return st.empty();
}
|
删除字符串中的所有相邻重复项（⭐）
LeetCode.1047
可以把string当作一个栈来操作。
核心代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
|
string removeDuplicates(string s) {
stack<char> stack;
string res;
for(char c:s){
if(stack.empty()||stack.top()!=c){
stack.push(c);
}else{
stack.pop();
}
}
while(!stack.empty()){
res.push_back(stack.top());
stack.pop();
}
reverse(res.begin(), res.end());
return res;
}
string removeDuplicates(string s) {
string res;
for(char c:s){
if(res.empty()||res.back()!=c){
res.push_back(c);
}else{
res.pop_back();
}
}
return res;
}
|
逆波兰表达式求值
LeetCode.150
遇到数字压入栈中，遇到运算符从栈中取出两个元素进行运算；这里注意string到int的转换（⭐），可以使用 stoi() 函数；
核心代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
| int evalRPN(vector<string>& tokens) {
stack<int> numStack;
for(auto s:tokens){
if(s!="+"&&s!="-"&&s!="*"&&s!="/"){
if(s[0]=='-'){
int num=0;
for(int i=1;i<s.size();i++){
num+=(s[i]-'0')*pow(10, (s.size()-i-1));
}
numStack.push(-num);
}else{
int num=0;
for(int i=0;i<s.size();i++){
num+=(s[i]-'0')*pow(10, (s.size()-i-1));
}
numStack.push(num);
}
}else{
int b=numStack.top();
numStack.pop();
int a=numStack.top();
numStack.pop();
if(s=="+"){
numStack.push(a+b);
}else if(s=="-"){
numStack.push(a-b);
}else if(s=="*"){
numStack.push(a*b);
}else if(s=="/"){
numStack.push(a/b);
}
}
}
return numStack.top();
}
|
滑动窗口最大值（单调队列⭐⭐⭐）
LeetCode.239
需要使用单调队列解题，单调队列指队列中元素从大到小排列，队列头的元素最大，使用deque实现单调队列，使用单调队列时间复杂度为O(n)；
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
| class MyQueue{
public:
void pop(int& x){
if(!deque.empty()&&x==deque.front())
deque.pop_front();
}
void push(int& x){
if(deque.empty()||deque.back()>=x){
deque.push_back(x);
}else{
while(!deque.empty()&&deque.back()<x){
deque.pop_back();
}
deque.push_back(x);
}
}
int getMaxValue(){
return deque.front();
}
private:
deque<int> deque;
};
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
vector<int> res;
if(nums.size()<=k){
int maxValue=nums[0];
for(int i=0;i<k;i++){
maxValue=max(nums[i], maxValue);
}
res.push_back(maxValue);
return res;
}
MyQueue myQueue;
for(int i=0;i<nums.size();i++){
if(i<k){
while(i<k){
myQueue.push(nums[i]);
i++;
}
i--;
res.push_back(myQueue.getMaxValue());
}else{
myQueue.pop(nums[i-k]);
myQueue.push(nums[i]);
res.push_back(myQueue.getMaxValue());
}
}
return res;
}
|
前k个高频元素（⭐⭐⭐）
LeetCode.347
使用unordered_map记录元素出现次数，使用 大小为k的小顶堆 遍历map，小顶堆元素超过k就弹出最小元素（pop），最后剩下的小顶堆中的k个元素就是前k个高频元素。
大顶堆小顶堆在C++中使用 priority_queue 实现；
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| class myCompare{
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>>, myCompare> pri_que;
for(unordered_map<int, int>::iterator ite=map.begin();ite!=map.end();ite++){
pri_que.push(*ite);
if(pri_que.size()>k){
pri_que.pop();
}
}
vector<int> res(k);
for(int i=k-1;i>=0;i--){
res[i]=pri_que.top().first;
pri_que.pop();
}
return res;
}
|