1.leetcode-232. 用栈实现队列

1.题目描述

使用栈实现队列的下列操作：
push(x) – 将一个元素放入队列的尾部。
pop() – 从队列首部移除元素。
peek() – 返回队列首部的元素。
empty() – 返回队列是否为空。
2.方法及思路（双栈）
思路
将一个栈当作输入栈，用于压入 push传入的数据；另一个栈当作输出栈，用于 pop，peek 操作。
每次 pop或 peek 时，若输出栈为空则将输入栈的全部数据依次弹出并压入输出栈，这样输出栈从栈顶往栈底的顺序就是队列从队首往队尾的顺序。

3.代码实现

class MyQueue {
public:stack<int> instack,outstack;void in2out(){while(!instack.empty()){outstack.push(instack.top());instack.pop();}}MyQueue() {}void push(int x) {instack.push(x);}int pop() {if(outstack.empty()){in2out();}int r=outstack.top();outstack.pop();return r;}int peek() {if(outstack.empty()){in2out();}return outstack.top();}bool empty() {return instack.empty()&&outstack.empty();}
};

2.leetcode-225. 用队列实现栈

1.题目描述

请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。
实现 MyStack 类：
void push(int x) 将元素 x 压入栈顶。
int pop() 移除并返回栈顶元素。
int top() 返回栈顶元素。
boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

2.方法及思路（双队列）
为了满足栈的特性，即最后入栈的元素最先出栈，在使用队列实现栈时，应满足队列前端的元素是最后入栈的元素。可以使用两个队列实现栈的操作，其中 queue1 用于存储栈内的元，queue2 作为入栈操作的辅助队列。

用两个队列que1和que2实现队列的功能，que2其实完全就是一个备份的作用，把que1最后面的元素以外的元素都备份到que2，然后弹出最后面的元素，再把其他元素从que2导回que1。

3.代码实现

class MyStack {
public:queue<int> queue1;queue<int> queue2;MyStack() {}void push(int x) {queue2.push(x);while(!queue1.empty()){queue2.push(queue1.front());queue1.pop();}swap(queue1,queue2);}int pop() {int r=queue1.front();queue1.pop();return r;}int top() {return queue1.front();}bool empty() {return queue1.empty();}
};

3.leetcode-20. 有效的括号

1.题目描述

给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。

（1）代码1

1.首先遍历字符串
2.如果遇到左半边括号就入栈对应的右半边括号
3.如果遇到右半边括号就与栈顶元素比较，相同则弹出元素，否则直接返回false
（注意字符串长度，奇数的话可以直接返回false）

class Solution {
public:bool isValid(string s) {if (s.size() % 2 != 0) return false; // 如果s的长度为奇数，一定不符合要求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(']');// 第三种情况：遍历字符串匹配的过程中，栈已经为空了，没有匹配的字符了，说明右括号没有找到对应的左括号 return false// 第二种情况：遍历字符串匹配的过程中，发现栈里没有我们要匹配的字符。所以return falseelse if (st.empty() || st.top() != s[i]) return false;else st.pop(); // st.top() 与 s[i]相等，栈弹出元素}// 第一种情况：此时我们已经遍历完了字符串，但是栈不为空，说明有相应的左括号没有右括号来匹配，所以return false，否则就return truereturn st.empty();}
};

（2）代码2

我们遍历给定的字符串 s。当我们遇到一个左括号时，我们会期望在后续的遍历中，有一个相同类型的右括号将其闭合。由于后遇到的左括号要先闭合，因此我们可以将这个左括号放入栈顶。

当我们遇到一个右括号时，我们需要将一个相同类型的左括号闭合。此时，我们可以取出栈顶的左括号并判断它们是否是相同类型的括号。如果不是相同的类型，或者栈中并没有左括号，那么字符串 s 无效，返回 False。为了快速判断括号的类型，我们可以使用哈希表存储每一种括号。哈希表的键为右括号，值为相同类型的左括号。

在遍历结束后，如果栈中没有左括号，说明我们将字符串 s 中的所有左括号闭合，返回 True，否则返回 False。

class Solution {
public:bool isValid(string s) {int n=s.size();if(n%2==1){return false;}unordered_map<char,char> pairs={{'}','{'},{']','['},{')','('}};stack<char> skt;for(auto ch:s){if(pairs.count(ch)){if(skt.empty()||skt.top()!=pairs[ch]){return false;}skt.pop();}else {skt.push(ch);}}return skt.empty();}
};

4.leetcode-1047. 删除字符串中的所有相邻重复项

1.题目描述

给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。
在 S 上反复执行重复项删除操作，直到无法继续删除
在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。

2.方法及思路
充分理解题意后，我们可以发现，当字符串中同时有多组相邻重复项时，我们无论是先删除哪一个，都不会影响最终的结果。因此我们可以从左向右顺次处理该字符串。
而消除一对相邻重复项可能会导致新的相邻重复项出现，如从字符串 abba中删除 bb 会导致出现新的相邻重复项 aa 出现。因此我们需要保存当前还未被删除的字符。一种显而易见的数据结构呼之欲出：栈。我们只需要遍历该字符串，如果当前字符和栈顶字符相同，我们就贪心地将其消去，否则就将其入栈即可。

3.代码实现

class Solution {
public:string removeDuplicates(string s) {string stk;int n=s.size();for(int i=0;i<n;i++){if(stk.empty()){stk.push_back(s[i]);}else if(s[i]==stk.back()){stk.pop_back();continue;}else{stk.push_back(s[i]);}}return stk;}
};

5.leetcode-150. 逆波兰表达式求值

1.题目描述

给你一个字符串数组 tokens ，表示一个根据 逆波兰表示法 表示的算术表达式。
请你计算该表达式。返回一个表示表达式值的整数。
注意：
有效的算符为 ‘+’、‘-’、‘*’ 和 ‘/’ 。
每个操作数（运算对象）都可以是一个整数或者另一个表达式。
两个整数之间的除法总是 向零截断 。
表达式中不含除零运算。
输入是一个根据逆波兰表示法表示的算术表达式。
答案及所有中间计算结果可以用 32 位 整数表示。

2.方法及思路
逆波兰表达式：是一种后缀表达式，所谓后缀就是指运算符写在后面。

平常使用的算式则是一种中缀表达式，如 ( 1 + 2 ) * ( 3 + 4 ) 。

该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * ) 。

逆波兰表达式主要有以下两个优点：

去掉括号后表达式无歧义，上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果。

适合用栈操作运算：遇到数字则入栈；遇到运算符则取出栈顶两个数字进行计算，并将结果压入栈中。
3.代码实现

class Solution {
public:int evalRPN(vector<string>& tokens) {stack<long long> st; for (int i = 0; i < tokens.size(); i++) {if (tokens[i] == "+" || tokens[i] == "-" || tokens[i] == "*" || tokens[i] == "/") {long long num1 = st.top();st.pop();long long num2 = st.top();st.pop();if (tokens[i]=="+") st.push(num2 + num1);if (tokens[i]=="-") st.push(num2 - num1);if (tokens[i]=="*") st.push(num2 * num1);if (tokens[i]=="/") st.push(num2 / num1);} else {st.push(stoll(tokens[i]));}}int result = st.top();st.pop(); // 把栈里最后一个元素弹出（其实不弹出也没事）return result;}
};

6.leetcode-239. 滑动窗口最大值

1.题目描述

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

2.方法及思路（双端队列）
1.队列的第一个元素保存最大值元素的下标

2.当前元素与队列从尾部开始的元素比较，如果队尾小则出队，直到空或者找到比他大的
（这样既可以保证第一个元素总是最大的）

3.还要保证队首元素的下标是在滑动窗口的范围内（当前值-k）
如果不在此范围内就从队首开始弹出元素

4.什么时候开始向数组中插入最大值呢？
从第k个元素的下标开始插入

3.代码实现

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

4.对于一开始的插入代码优化
可以先遍历到k个时就直接插入
后面的for循环中就可以加入每次的插入操作

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

7.leetcode-347. 前 K 个高频元素

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

2.思路
这道题目主要涉及到如下三块内容：

1.要统计元素出现频率
2.对频率排序
3.找出前K个高频元素

首先统计元素出现的频率，这一类的问题可以使用map来进行统计。

然后是对频率进行排序，这里我们可以使用一种 容器适配器就是优先级队列。

什么是优先级队列呢？

其实就是一个披着队列外衣的堆，因为优先级队列对外接口只是从队头取元素，从队尾添加元素，再无其他取元素的方式，看起来就是一个队列。

而且优先级队列内部元素是自动依照元素的权值排列。那么它是如何有序排列的呢？

缺省情况下priority_queue利用max-heap（大顶堆）完成对元素的排序，这个大顶堆是以vector为表现形式的complete binary tree（完全二叉树）。

什么是堆呢？

堆是一棵完全二叉树，树中每个结点的值都不小于（或不大于）其左右孩子的值。 如果父亲结点是大于等于左右孩子就是大顶堆，小于等于左右孩子就是小顶堆。

所以大家经常说的大顶堆（堆头是最大元素），小顶堆（堆头是最小元素），如果懒得自己实现的话，就直接用priority_queue（优先级队列）就可以了，底层实现都是一样的，从小到大排就是小顶堆，从大到小排就是大顶堆。

本题我们就要使用优先级队列来对部分频率进行排序。

3.代码实现

优先级的处理

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

例如我们在写快排的cmp函数的时候，return left>right 就是从大到小，return left<right 就是从小到大。
优先级队列的定义正好反过来了，可能和优先级队列的源码实现有关，我估计是底层实现上优先队列队首指向后面，队尾指向最前面

元素入map容器

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;

用迭代器入队
是按照second元素，也就是出现的次数排序

for (unordered_map<int, int>::iterator it = map.begin(); it != map.end(); it++) {pri_que.push(*it);if (pri_que.size() > k) { pri_que.pop();}}

4.完整代码

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 (unordered_map<int, int>::iterator it = map.begin(); it != map.end(); it++) {pri_que.push(*it);if (pri_que.size() > k) { pri_que.pop();}}vector<int> result(k);for (int i = k - 1; i >= 0; i--) {result[i] = pri_que.top().first;pri_que.pop();}return result;}
};