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

前言

打卡代码随想录算法训练营第49期第十一天 φ(゜▽゜*)♪

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

今日题目

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

LeetCode 150 逆波兰表达式求值

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

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

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

如果能读懂题目并且学过之前用栈解题，那这道题会十分简单，这里卡哥也用一个GIF直接将题讲清楚了，我也就不过多赘述。

public class Solution {
    public int EvalRPN(string[] tokens) {
        Stack<int> st = new Stack<int>();
        for(int i = 0; i < tokens.Length; i++)
        {
            //判断如果是+ - * /就取出两个值进行计算
            if(tokens[i] == "+")
            {
                int num1 = st.Pop();
                int num2 = st.Pop();
                st.Push(num1 + num2);
            }
            else if(tokens[i] == "-")
            {
                int num1 = st.Pop();
                int num2 = st.Pop();
                st.Push(num2 - num1);
            }
            else if(tokens[i] == "*")
            {
                int num1 = st.Pop();
                int num2 = st.Pop();
                st.Push(num1 * num2);
            }
            else if(tokens[i] == "/")
            {
                int num1 = st.Pop();
                int num2 = st.Pop();
                st.Push(num2 / num1);
            }
            //如果不是 则直接压入该值
            else
                st.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 个高频元素

本题最简单的思路就是统计频率，在对频率进行排序，返回前K个，但是时间复杂度就会偏高，而这里使用堆的概念，使用小顶堆，这样如果超过了K个数量，每次弹出的就是堆中频率最小的数。

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]]++;
            else
                dic.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;
    }
}

今天的题相对要难一些，需要重复的学习和练习，明天见~~~