卡哥算法打卡
1.用栈实现队列思路
只用一个栈很明显就是不行的，需要两个栈。stack1和stack2。push操作比较简单，跟之前没有区别。但是pop就不同了，如果发现stack2是空的时候需要把stack1中所有的元素pop出来放到stack2里面，那么stack2中的元素pop出来就是队列的排序。但是只有stack2为空的时候才能够把stack1中的元素拿过来，原因就是如果不为空的情况也拿出来，就会压住上面的元素，导致顺序错误
class MyQueue {
Stack stack1;
Stack stack2;
public MyQueue() {
stack1=new Stack<>();
stack2=new Stack<>();
}
public void push(int x) {
stack1.push(x);
}
public int pop() {
dumpStack();
return stack2.pop();
}
public int peek() {
dumpStack();
return stack2.peek();
}
public boolean empty() {
return stack1.isEmpty()&&stack2.isEmpty();
}
public void dumpStack(){
if(stack2.isEmpty()){
while(!stack1.isEmpty()){
stack2.push(stack1.pop());
}
}
}
}
2.用队列实现栈
思路
也是用两个队列来进行实现。方法就是每次push先把元素放到a，这个时候a队列是空的，b队列保存了之前的队列数据。然后再把b的数据全部push进a。然后就是交换a和b队列。其实就是相当于后面进来的元素先放入a，也就是变成了先进来的元素，然后就是把b里面真正最早进来的元素放进a。再交换a和b。最后b先出来的肯定就是后面加进来的那个元素，因为它是先进a（后来交换给了b）的。而b的元素也遵循这样的规则加入。那么也就是模仿栈，后进先出。
class MyStack {
private Queue a;
private Queue b;
public MyStack() {
a=new linkedList<>();
b=new linkedList<>();
}
public void push(int x) {
a.offer(x);
//b队列全部交给a
while(!b.isEmpty()){
a.offer(b.poll());
}
//交换队列，保证a是空的，为了让后进元素，变成在队列中的先进元素
Queue temp=a;
a=b;
b=temp;
}
public int pop() {
return b.poll();
}
public int top() {
return b.peek();
}
public boolean empty() {
return a.isEmpty()&&b.isEmpty();
}
}
3.有效括号
思路
利用栈来进行匹配。其实这些括号，只要是嵌套的那种，很明显都有一种特点就是后进先出，也就是越里面的左括号离匹配的右括号越近，也就符合了栈的存储原则。但是这里需要思考清楚三个错误的判断
- 左括号太多，右括号匹配不来
- 匹配成功，但是匹配的括号不正确
- 右括号太多匹配不过来
在代码里面的栈，每次只要有左括号，那么就压栈一个有括号，也就是说后面遍历到右括号的时候，栈弹出来的一定要是对应的右括号。这样才算匹配成功。下面有三种情况
- 左括号太多，那么就会不断压栈右括号进去，遍历完后发现，栈不为空，也就是左括号匹配不完
- 弹出栈的右括号和实际的右括号并不匹配，也就是左括号和右括号存在但是类型不匹配
- 还有一种就是右括号太多，会导致压栈的右括号并不多，还没遍历完字符串就已经栈空了
class Solution {
public boolean isValid(String s) {
Deque deque=new linkedList<>();
for(int i=0;i
4.删除字符串中所有相邻的重复项
思路
其实重复项就相当于是左括号和右括号的匹配。每次进栈的时候只需要判断栈顶是不是与外面进来的新字符相同，就知道是否匹配。如果匹配那么就弹出来。本质上就是利用栈的后进先出，匹配问题其实也符合这个原则。左括号进去早，那么匹配也早。同样相同字符出现早也是匹配早。
class Solution {
public String removeDuplicates(String s) {
ArrayDeque deque=new ArrayDeque<>();
for(int i=0;i
5.逆波兰表达式求值
思路
逆波兰表达式的规则就是遇到符号之后，弹出来那个是加数或者是减数，第二个弹出来的才是被加数或者是被减数。需要厘清这个关系。然后这个地方为什么需要用到栈？原因就是与上面的题目项目，左括号匹配右括号，相同的值匹配相邻重复项，然后再到逆波兰表达式，其实思路都是相似，逆波兰表达式计算只不过就是符号作为右括号，然后数字就是所谓的左括号，不管怎么变，只要符合这样的规则匹配，就能够尝试使用栈。
拓展
①需要判断是不是符号，不是符号就压栈，是符号那么就需要判断是什么符号然后进行计算
②减和除需要拿出第二个被除数或者是被减数之后才能计算，而不是第一个出来减去第二个。这样是不符合规则的。
class Solution {
public int evalRPN(String[] tokens) {
Deque stack=new linkedList<>();
for(String token:tokens){
char ch=token.charAt(0);
if(!isOpe(token)){
stack.addFirst(stoi(token));
}else if(ch=='+'){
stack.push(stack.pop()+stack.pop());
}else if(ch=='-'){
stack.push(-stack.pop()+stack.pop());
}else if(ch=='*'){
stack.push(stack.pop()*stack.pop());
}else{
int num1=stack.pop();
int num2=stack.pop();
stack.push(num2/num1);
}
}
return stack.pop();
}
private boolean isOpe(String s){
return s.length()==1&&s.charAt(0)<'0'||s.charAt(0)>'9';
}
private int stoi(String s){
return Integer.valueOf(s);
}
}
6.最大滑动窗口
思路
第一种办法就是直接暴力，时间复杂度是n*k。第二种方法就是通过单调队列来进行处理。什么是单调队列，比如单调递增或者递减。这里采用的是单调递减，也就是最大的数值一直会放到队首。每次遍历到最大的数值才把它弹出去，或者如果遇到更大的数值进入队列，那么就要把前面的数值全部弹出去，加入新的数值，这样才能够维持单调队列。我们不需要维护窗口里面的数值，只需要维护每个窗口上最大的那个元素就可以了。它的原理实际上就是窗口罩住的k个元素，排好序，通过加入队列的时候先检验新加入的元素是不是大于前面进入的元素，如果是那么就把前面的先弹出来再加入新的元素。如果是出队列，那么就要看看当前遍历到的元素是不是与队列的出口元素相同，如果是那么就出队列。本质就是无论k个元素的窗口怎么移动，除非加入更大的元素，否则都是原来窗口的元素最大，所以只需要等到遍历最大的元素再让他出队列就可以了，而且也能够按照顺序加入到结果集上面去。
拓展
①注意有空的nums和nums的长度是1的情况直接返回nums即可。
总结：单调队列可以解决窗口最大的问题，无论窗口怎么移动，只要不进来比原来窗口大的，或者窗口尾巴没有遍历到最大元素，那么窗口最大的仍然就是之前的最大元素，所以并不需要维护窗口的大小。单调队列的出需要判断窗口尾巴是不是与队列出口元素相同，入队的时候需要判断元素是不是比队尾更大，如果是那么就要让队尾元素弹出。
class Solution {
class MyQueue{
Deque deque=new linkedList<>();
public void poll(int val){
if(!deque.isEmpty()&&val==deque.peek()){
deque.poll();
}
}
public void add(int val){
while(!deque.isEmpty()&&deque.getLast()
7.前k个高频元素
思路
①第一个就是要解决如果统计，可以使用map
②第二个就是怎么排序->优先队列（原理是大顶堆和小顶堆）
③第三个就是用大顶堆还是小顶堆？使用的是小顶堆，为了保留前k个高频元素。（倒序）
整体思路其实就是map先统计频率，然后通过把它变成entryset，接着就是遍历，并且加入到优先队，优先队列的排序方式是小的频率在前面。如果加入到优先队列的元素大于k，那么就poll出来（最小的那个元素）。最后就只剩下k个从小到大的高频元素，只需要倒序遍历放入结果数组即可.
总结：这道题的解决方案就是优先队列，优先队列可以解决排序问题。时间复杂度是n*logn。
class Solution {
public int[] topKFrequent(int[] nums, int k) {
Map map=new HashMap();
for(int num:nums){
map.put(num,map.getOrDefault(num,0)+1);
}
int[] res=new int[k];
Set> entries=map.entrySet();
PriorityQueue> queue=new PriorityQueue<>((o1,o2)->o1.getValue()-o2.getValue());
for(Map.Entry entry:entries){
queue.offer(entry);
if(queue.size()>k){
queue.poll();
}
}
for(int i=k-1;i>=0;i--){
res[i]=queue.poll().getKey();
}
return res;
}
}
