代码随想录第55期训练营第十一天|LeetCode150.逆波兰表达式求值、239.滑动窗口最大值、347.前K个高频元素

前言

这是我参加的第二次训练营！！！爽！这次我将更加细致的写清每一道难题，不仅是提升自己，也希望我自己的写的文章对读者有一定的帮助！

打卡代码随想录算法训练营第55期第十一天（づ￣3￣）づ╭❤～

首先十分推荐学算法的同学可以先了解一下代码随想录，可以在B站卡哥B站账号、代码随想录官方网站代码随想录了解，卡哥清晰易懂的算法教学让我直接果断关注，也十分有缘和第55期的训练营大家庭一起进步。

今日题目

在学习今日的题目前先看：栈与队列的内部实现机制

LeetCode 150 逆波兰表达式求值

题目链接：150 逆波兰表达式求值

文章讲解：逆波兰表达式求值

视频讲解：卡哥讲解 —— 逆波兰表达式求值

本题依旧是使用了栈的特色，理解起来还行就是遇到数存起来，遇到符号取出计算，主要注意减和除的顺序问题，以及想明白最后结果的存储位置。

public class Solution {public int EvalRPN(string[] tokens) {Stack<int> st = new Stack<int>();for(int i = 0; i < tokens.Length; i++){//如果是符号则取出两个值来计算//注意这里令第一个取出的数为num2 第二个数为num1//且所有的计算都是num1 ... num2if(tokens[i] == "+"){int num2 = st.Pop();int num1 = st.Pop();st.Push(num1 + num2);}else if(tokens[i] == "-"){int num2 = st.Pop();int num1 = st.Pop();st.Push(num1 - num2);}else if(tokens[i] == "*"){int num2 = st.Pop();int num1 = st.Pop();st.Push(num1 * num2);}else if(tokens[i] == "/"){int num2 = st.Pop();int num1 = st.Pop();st.Push(num1 / num2);}elsest.Push(int.Parse(tokens[i]));}//最后结果就是栈中的唯一的值return st.Pop();}
}

LeetCode 239 滑动窗口最大值

题目链接：239 滑动窗口最大值

文章讲解：滑动窗口最大值

视频讲解：卡哥讲解 —— 滑动窗口最大值

滑动窗口的最大值也算是一道相对来说难一点的题，主要理解如何维持滑动窗口，为什么要维持滑动窗口，其实原因很简单，因为我们只需要取得滑动窗口的最大值，我们只需要让每个窗口的最大值放在首位即可，方面明了，后面的内容也可以依次排序。最后是选用什么样的容器来模拟滑动窗口，以及实现的细节。

public class Solution {public int[] MaxSlidingWindow(int[] nums, int k) {List<int> res = new List<int>();MyQueue queue = new MyQueue();for(int i = 0; i < k; i++)//先装够滑动窗口的数量queue.Enqueue(nums[i]);res.Add(queue.Max());//添加第一个值for(int i = k; i < nums.Length; i++){//之后反复添加删除求值即可queue.Dequeue(nums[i - k]);queue.Enqueue(nums[i]);res.Add(queue.Max());}return res.ToArray();} 
}
public class MyQueue
{//使用一个容器来模拟整个队列，需要维持容器第一个值为最大值//这里使用链表public LinkedList<int> queue = new LinkedList<int>();//填入数据方法public void Enqueue(int num){//如果比整个容器最后一个数据要大，就替换这个数据while(queue.Count > 0 && num > queue.Last.Value)queue.RemoveLast();queue.AddLast(num);}public void Dequeue(int num){//如果要移除的数是最大值，则才用移除if(num == queue.First.Value)queue.RemoveFirst();}public int Max(){//最大值就是第一个值return queue.First.Value;}
}

LeetCode 347 前K个高频元素

题目链接：347 前K个高频元素

文章讲解：前 K 个高频元素

视频讲解：卡哥讲解 —— 前 K 个高频元素

本题主要利用优先级队列的属性来做题，优先级队列主要就是求得一组数据最大的几个和最小的几个，利用大小顶堆的原理来封装。如果了解优先级队列，则这个题很好做，如果不了解，那就从这道题开始了解吧！C#中的优先级队列是PriorityQueue<内容,优先级>

public class Solution {public int[] TopKFrequent(int[] nums, int k) {//统计每个元素的频率Dictionary<int,int> dic = new Dictionary<int,int>();for(int i = 0; i < nums.Length; i++){if(dic.ContainsKey(nums[i]))dic[nums[i]]++;elsedic.Add(nums[i] , 1);}//设置优先级队列，求得前k个高频元素PriorityQueue<int , int> pq = new PriorityQueue<int , int>();foreach(var num in dic){pq.Enqueue(num.Key , num.Value);if(pq.Count > k)pq.Dequeue();}//将结果填入数组int[] res = new int[k];for(int i = k - 1; i >= 0; i--)res[i] = pq.Dequeue();return res;}
}