代码随想录打卡第十二天补
第五章 栈和队列 part2
150. 逆波兰表达式求值
本题不难，但第一次做的话，会很难想到，所以先看视频，了解思路再去做题
题目链接/文章讲解/视频讲解：https://programmercarl.com/0150.%E9%80%86%E6%B3%A2%E5%85%B0%E8%A1%A8%E8%BE%BE%E5%BC%8F%E6%B1%82%E5%80%BC.html
这个题目的话，首先想到的就是使用栈的解法，需要一遇到运算符进行取出顶上两个元素的操作，然后再将运算结果放入栈中。思路比较简单
问题：
数据结构栈的使用：Deque还是什么
怎么判断是数字还是运算符
看了代码随想录的之后，发现可以直接进行比较运算符，使用equals，然后使用if else结构就可以直接的获取非运算符的数字了，其次主义题目中其实说明了除法中 的取整
然后在写的时候发现，取出来的是数字，只要存进去的时候转换为数字，取出来肯定是数字，然后就是，字符相等的比较的时候，单双引号的问题，单引号是字符，双引号是字符串。但是为什么在取出来的时候不用字符那，因为是字符串数组，不是字符数组
class Solution {
public int evalRPN(String[] tokens) {
Deque<Integer> stack = new LinkedList<>();
for (String eachstr : tokens){
if(eachstr.equals("+")){
stack.push(stack.pop() + stack.pop());
} else if(eachstr.equals("-")) {
int s1 = stack.pop();
int s2 = stack.pop();
stack.push( s2 - s1);
} else if (eachstr.equals("*")) {
stack.push( stack.pop() * stack.pop());
} else if (eachstr.equals("/")) {
int s1 = stack.pop();
int s2 = stack.pop();
stack.push( s2 / s1);
} else {
stack.push(Integer.valueOf(eachstr));
}
}
return stack.pop();
}
}
239. 滑动窗口最大值 （有点难度，可能代码写不出来，但一刷至少需要理解思路）
之前讲的都是栈的应用，这次该是队列的应用了。
本题算比较有难度的，需要自己去构造单调队列，建议先看视频来理解。
题目链接/文章讲解/视频讲解：https://programmercarl.com/0239.%E6%BB%91%E5%8A%A8%E7%AA%97%E5%8F%A3%E6%9C%80%E5%A4%A7%E5%80%BC.html
思路：读完题目，觉得，我每次智能看到窗口里面的数字，然后我只需要每次移动之后，找到窗口的最大值并存入一个数组就可以。然后窗口的数据结构的实现用什么那，然后这道题目的难点应该在于每次如何找到窗口的最大值。如果吗每次都需要遍历就很复杂。
看完代码随想录：单调队列，首先理解单调队列的思想，就是维护一个队首为最大值的队列，注意仅仅针对这道题目来说，然后就是，队列里面需要存储的是这个窗口的数据，每次在添加元素的时候，需要判断这个元素是否比队列末尾的元素大，打的话就替换掉，同时也要注意队首的元素是否存在于这个窗口中，也就是需要判断窗口移动的时候是否移出去的数据是队头元素。
回顾一下双端队列的new方法和添加删除元素的方法：
今日收获：在写代码模拟过程的时候，其实放在最普通最中间的情况去看待问题，从大方向去把握代码的各部分内容，再从细节把握每部分的具体操作
先写一个队列存储的下标的版本
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
ArrayDeque<Integer> deque = new ArrayDeque<>();
int[] res = new int[nums.length - k + 1];
int idx=0;
for (int i = 0; i < nums.length; i++){
//先看队头元素是否需要移除,i指代需要加入队列的元素的下标，注意这里需要使用while
while(!deque.isEmpty() && deque.peekFirst() <= i-k){
//注意这里需要指明是队头
deque.pollFirst();
}
//加入队尾元素
while(!deque.isEmpty() && nums[deque.peekLast()] <nums[i] ){
deque.removeLast();
}
//添加元素的话需要在循环外面
deque.addLast(i);
if (i+1 >= k){
res[idx] = nums[deque.peekFirst()];
idx++;
}
}
return res;
}
}
347.前 K 个高频元素 （有点难度，可能代码写不出来，一刷至少需要理解思路）
大/小顶堆的应用， 在C++中就是优先级队列
本题是 大数据中取前k值 的经典思路，了解想法之后，不算难。
题目链接/文章讲解/视频讲解：https://programmercarl.com/0347.%E5%89%8DK%E4%B8%AA%E9%AB%98%E9%A2%91%E5%85%83%E7%B4%A0.html
这里我们就先理解下思路，直接看代码随想录的
/*Comparator接口说明:
* 返回负数，形参中第一个参数排在前面；返回正数，形参中第二个参数排在前面
* 对于队列：排在前面意味着往队头靠
* 对于堆（使用PriorityQueue实现）：从队头到队尾按从小到大排就是最小堆（小顶堆），
* 从队头到队尾按从大到小排就是最大堆（大顶堆）--->队头元素相当于堆的根节点
* */
class Solution {
//解法1：基于大顶堆实现
public int[] topKFrequent1(int[] nums, int k) {
Map<Integer,Integer> map = new HashMap<>(); //key为数组元素值,val为对应出现次数
for (int num : nums) {
map.put(num, map.getOrDefault(num,0) + 1);
}
//在优先队列中存储二元组(num, cnt),cnt表示元素值num在数组中的出现次数
//出现次数按从队头到队尾的顺序是从大到小排,出现次数最多的在队头(相当于大顶堆)
PriorityQueue<int[]> pq = new PriorityQueue<>((pair1, pair2) -> pair2[1] - pair1[1]);
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {//大顶堆需要对所有元素进行排序
pq.add(new int[]{entry.getKey(), entry.getValue()});
}
int[] ans = new int[k];
for (int i = 0; i < k; i++) { //依次从队头弹出k个,就是出现频率前k高的元素
ans[i] = pq.poll()[0];
}
return ans;
}
//解法2：基于小顶堆实现
public int[] topKFrequent2(int[] nums, int k) {
Map<Integer,Integer> map = new HashMap<>(); //key为数组元素值,val为对应出现次数
for (int num : nums) {
map.put(num, map.getOrDefault(num, 0) + 1);
}
//在优先队列中存储二元组(num, cnt),cnt表示元素值num在数组中的出现次数
//出现次数按从队头到队尾的顺序是从小到大排,出现次数最低的在队头(相当于小顶堆)
PriorityQueue<int[]> pq = new PriorityQueue<>((pair1, pair2) -> pair1[1] - pair2[1]);
for (Map.Entry<Integer, Integer> entry : map.entrySet()) { //小顶堆只需要维持k个元素有序
if (pq.size() < k) { //小顶堆元素个数小于k个时直接加
pq.add(new int[]{entry.getKey(), entry.getValue()});
} else {
if (entry.getValue() > pq.peek()[1]) { //当前元素出现次数大于小顶堆的根结点(这k个元素中出现次数最少的那个)
pq.poll(); //弹出队头(小顶堆的根结点),即把堆里出现次数最少的那个删除,留下的就是出现次数多的了
pq.add(new int[]{entry.getKey(), entry.getValue()});
}
}
}
int[] ans = new int[k];
for (int i = k - 1; i >= 0; i--) { //依次弹出小顶堆,先弹出的是堆的根,出现次数少,后面弹出的出现次数多
ans[i] = pq.poll()[0];
}
return ans;
}
}
总结
栈与队列做一个总结吧，加油
https://programmercarl.com/%E6%A0%88%E4%B8%8E%E9%98%9F%E5%88%97%E6%80%BB%E7%BB%93.html
