当前位置：首页 > article >正文

[代码随想录Day11打卡] 150. 逆波兰表达式求值 239. 滑动窗口最大值（有点难度） 347.前 K 个高频元素（有点难度）总结

article 2024/11/15 14:57:25

150. 逆波兰表达式求值

逆波兰表达式就是后缀表达式。我们日常接触到的1+2 * 3+4是中序表达式，中序表达式往往需要括号来指定执行操作的顺序。后序表达式1 2 + 3 4 + 就是顺序进行不需要括号。
按照输入的数据的类型可以分为数值和操作符。有效的算符为 ‘+’、‘-’、'’ 和 ‘/’ 。这些都是双目操作符。
比如以1 2 + 3 4 + 为例，遇到数字1 2我们没有操作，遇到操作符+我们需要将前面的数字进行加法操作得到3。遇到数字3 4 我们没有操作，遇到+，我们需要将前两个数字进行加法操作得到7。遇到操作符我们需要将前面获得的两个结果进行乘法操作。
遇到操作符操作的都是离操作符最近的两个元素或者说相邻的两个元素，先入后出使用栈。
两个操作：

遇到数字就将数字压入栈。
遇到操作符就连续弹出两个元素，并对其进行操作。先入后出，所以先弹出的元素num1，和后弹出的元素num2，两个的操作应该是num2 op num1。操作得到的结果压入到栈。
最后将栈中的数值弹出就好。
下面是C++,JAVA和Python的实现。

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]));//这个注意是使用stoll来将string类型变成long long 类型
        }
        int result = st.top();
        st.pop();
        return result;
    }
};

class Solution {
    public int evalRPN(String[] tokens) {
        Deque<Integer> stack = new LinkedList();//JAVA中定义栈的方法
        for(String s: tokens){
            if("+".equals(s)){
                stack.push(stack.pop()+stack.pop());
            }else if("-".equals(s) ){
                stack.push(-stack.pop()+stack.pop());
            }else if("*".equals(s)){
                stack.push(stack.pop()*stack.pop());
            }else if("/".equals(s)){
                int temp1 = stack.pop();
                int temp2 = stack.pop();
                stack.push(temp2/temp1);
            }else{
                stack.push(Integer.valueOf(s));//注意这个是将string变成int的
            }
        }
        int result = stack.pop();
        return result;
    }
}

from operator import add, sub, mul
def div(x, y):
    #使用整数除法的向零取整方式
    return int(x/y) if x*y >0 else -(abs(x)//abs(y))
class Solution(object):
    def evalRPN(self, tokens):
        """
        :type tokens: List[str]
        :rtype: int
        """
        stack = []
        op_map = {'+': add, '-': sub, '*': mul, '/': div}
        for token in tokens:
            if token in {'+','-','*','/'}:
                num1 = stack.pop()
                num2 = stack.pop()
                operator = op_map[token]
                stack.append(operator(num2, num1))
            else:
                stack.append(int(token))
        return stack.pop()

参考文章

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

239. 滑动窗口最大值（有点难度）

关键：定义单调队列。维护最大值的队列。
单调队列的功能：pop() push() getMaxValue() 三个函数好好定义。
定义一个队列，遍历列表，将列表中的值放到队列中。
滑动窗口两个操作：

旧元素出去pop。每次滑窗移动的时候判断一下要pop的值是不是队列中que.front()的最大值，如果是就pop，不是就不进行pop。
新元素进来push。如果当前值大于前面的值就将前面的值pop掉，这样队列的que.front()就是最大值。
得到最大值front。就是队列的que.front()。
定义完这个单调队列之后，进行操作。每次移动的时候就是pop(nums[i-k])，push(nums[i])，然后front()得到窗口中的最大值保存到结果列表中。

class Solution {
private:
    class MyQueue{
        public:
        deque<int> que;//使用deque实现队列
        void pop(int val){
            if(!que.empty() && val == que.front()){
                que.pop_front();
            }
        }
        void push(int val){
            while(!que.empty()&& val>que.back()){
                que.pop_back();
            }
            que.push_back(val);
        }
        int getMaxValue(){
            return que.front();
        }
    };
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        MyQueue que;
        vector<int> result;
        for(int i = 0; i<k; i++){
            que.push(nums[i]);//这个就是使用我们定义的单调队列
        }
        result.push_back(que.getMaxValue());//第一个窗口的最大值
        for(int i = k; i< nums.size(); i++){
            que.pop(nums[i-k]);
            que.push(nums[i]);
            result.push_back(que.getMaxValue());
        }
        return result;
    }
};

class MyQueue{
    Deque<Integer> deque = new LinkedList<>();
    void poll(int val){
        if(!deque.isEmpty() && val == deque.peek()){
            deque.poll();
        }
    }
    void add(int val){//这个是while
        while(!deque.isEmpty() && val>deque.getLast()){
            deque.removeLast();
        }
        deque.add(val);
    }
    int peek(){
        return deque.peek();
    }
}
class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums.length == 1) {
            return nums;
        }
        MyQueue myque = new MyQueue();
        int len = nums.length - k +1;
        int[] res = new int[len];
        int count = 0;
        for(int i = 0; i < k; i++){
            myque.add(nums[i]);
        }
        res[count++] = myque.peek();
        for(int i =k ; i < nums.length; i++){
            myque.poll(nums[i-k]);
            myque.add(nums[i]);
            res[count++] = myque.peek();
        }
        return res;
    }
}

class MyQue:
    def __init__(self):
        self.queue = deque()
    def pop(self, value):
        if self.queue and value == self.queue[0]:
            self.queue.popleft()
    def push(self, value):
        while self.queue and value> self.queue[-1]:
            self.queue.pop()
        self.queue.append(value)
    def front(self):
        return self.queue[0]
class Solution(object):
    def maxSlidingWindow(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """
        que = MyQue()
        result = []
        for i in range(k):
            que.push(nums[i])
        result.append(que.front())
        for i in range(k, len(nums)):
            que.pop(nums[i-k])
            que.push(nums[i])
            result.append(que.front())
        return result

参考文章

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

347.前 K 个高频元素（有点难度）

关键：定义最小堆。维护K个值的顺序。
需要保存元素及其对应的频率，所以使用map。因为只需要找到前k个高频元素所以我们只需要维护频率最高的K个元素的顺序就好。
小顶堆，pop的时候堆顶弹出的是堆中最小的元素。我们就使用小顶堆遍历列表，然后保持小顶堆的长度为K就好。
对我来说不同语言的小顶堆定义是很困难的。
前面获得每个元素及其对应的频率就是哈希表。定义好了小顶堆就只需要push，当小顶堆的size大于K pop就可以。我看JAVA中也有使用大顶堆的（没仔细看，可能把所有元素和频率都放到大顶堆中，然后弹出K个元素）。

class Solution {
public:
    //小顶堆
    class mycomparison{
        public:
        bool operator()(const pair<int, int>& lhs, const pair<int, int>& rhs){
            return lhs.second > rhs.second;
        }//函数重载
    };//是不是所有class最后都要有分号
    vector<int> topKFrequent(vector<int>& nums, int k) {
        //要统计元素出现的频率
        unordered_map<int,int> map;//map<nums[i],对应出现的次数>
        for(int i = 0; i < nums.size(); i++){
            map[nums[i]]++;//次数加一
        }
        //遍历一遍得到相应的频率之后，对频率进行排序
        //定义一个小顶堆，大小为k
        priority_queue<pair<int, int>,vector<pair<int, int>>, mycomparison> pri_que;

        //用固定大小为k的小顶堆，扫描是哟有频率的数值，只维持前k个
        for(unordered_map<int, int>::iterator it = map.begin(); it !=map.end(); it++){
            pri_que.push(*it);
            if(pri_que.size() > k){//堆大小大于k就弹出，维持堆的大小为k
            pri_que.pop();
            }
        }
        //找出k个高频元素，小顶堆先弹出最小的，倒叙输出到数组
        vector<int> result(k);
        for(int i = k-1; i>=0;i--){
            result[i] = pri_que.top().first;
            pri_que.pop();
        }
        return result;
    }
};

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();//key为数组元素值，val为对应出现的次数
        for (int num : nums){//统计每个元素出现的次数
            map.put(num, map.getOrDefault(num, 0)+1);//如果对应的值存在就是使用索引得到的值，否则就是初始化为0
        }
        PriorityQueue<int[]> pq = new PriorityQueue<>((pair1, pair2)->pair1[1]-pair2[1]);//如果pair1[1]-pair2[1]小于0则pair1放到pair2的前面否则就是pair1放到pair2的后面
        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]){//当前出现的频率大于小顶堆的顶点就弹出然后push
                    pq.poll();
                    pq.add(new int[]{ entry.getKey(), entry.getValue()});

                }
            }
        }
        int[] ans = new int[k];//按照顺序输出前k个高频词
        for (int i = k -1 ; i >= 0; i--){//一次弹出小顶堆，但是逆序添加到result中
            ans[i] = pq.poll()[0];
        }
        return ans;
    }
}

import heapq
class Solution(object):
    def topKFrequent(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """
        map_ = {}#记录元素及对应的出现的次数
        for i in range(len(nums)):
            map_[nums[i]] = map_.get(nums[i], 0)+1
        #对频率进行排序，看看python怎么定义小顶堆的
        pri_que = []

        #用固定大小的小顶堆遍历所有频率的数值
        for key, freq in map_.items():#遍历整个map
            heapq.heappush(pri_que,(freq, key))#这个是做什么的呢，这个是不是实现小顶堆的
            if len(pri_que) > k:#维护小顶堆内的数据只有k个
                heapq.heappop(pri_que)
        #找出前K个元素。倒序输出
        result = [0]*k
        for i in range(k-1, -1, -1):
            result[i] = heapq.heappop(pri_que)[1]
        return result