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

1 leetcode150. 逆波兰表达式求值

题目链接：150. 逆波兰表达式求值 - 力扣（LeetCode）

文章链接：代码随想录

视频链接：栈的最后表演！ | LeetCode：150. 逆波兰表达式求值哔哩哔哩bilibili

自己的思路：这是一道有思路，但是思路并不多的题目，就是我会觉得是先将数据进行添加，然后对于符号通过倒序的方法添加，但是不会写着道题目

1.1 视频后的思路

思路:

1. 就是首先将数字进行存储，如果遇到了符号就进行取后面两个进行计算，计算后的值又加入到这个栈中

2. 直到最后循环结束，就结束了这个过程

注意

1. python中的加减乘除等符号在使用计算的时候需要进行定义的

2. 加减乘可以调用内部函数，但是除法由于这道题需要保留整数部分，所以就需要进行函数调用

3. 在计算值的时候创建了一个字典，因为字典的值相当于函数本身，所以后面加括号，输入值就正确了

from operator import add,mul,sub
def div(x,y):
    return int(x/y) if x*y>0 else -int(abs(x)/abs(y))
class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        op_map = {'+':add,'-':sub,'*':mul,'/':div}
        stack = []
        for i in tokens:
            if i not in op_map.keys():
                stack.append(int(i))
            else:
                num2 = stack.pop()
                num1 = stack.pop()
                stack.append(op_map[i](num1,num2))
        return stack.pop()        

1.2 本题小结

1. 这道题主要注意点就是加减乘除计算的时候，是先倒数第二位减/除倒数第一位，这里如果弄错了会出现结果错误的现象

2. 这道题对于python而言，里面的加减乘除需要进行函数调用，这一点做的时候没有想到

2 leetcode239. 滑动窗口最大值

题目链接：239. 滑动窗口最大值 - 力扣（LeetCode）

文章链接：代码随想录

视频链接：单调队列正式登场！| LeetCode：239. 滑动窗口最大值哔哩哔哩bilibili

自己的思路：第一反应就是定义好长度，进行索引取值，找到这个地方的最大值，然后将其添加到列表中，对于简单的例子，走通了，但是里面很复杂的值的时候报错了

2.1 自己的思路

这个方法针对数据量小的时候完全可行，数据量大就会报错了

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        left = 0
        right = k
        l = list()
        while right<=len(nums):
            l.append(max(nums[left:right]))
            left +=1
            right +=1
        return l

2.2 看视频后的方法

思路：

1. 这道题首先想的是用队列的方法解决问题

2. 然后就考虑这个数值怎么存取，首先就是一直保持第一个数就是最大的数，所以如果有比他大的数，需要进行删除，即pop

3. 然后就是要看加进去的数的大小，如果没有，就一直保存队列的第一个数值，如果有比第一个大的数就需要进行删除

4. 然后不断保存就好了

from collections import deque
​
class Myqueue:
    def __init__(self):
        self.que = deque()
    
    def pop(self,value):
        if self.que and value == self.que[0]:
            self.que.popleft()
    
    def push(self,value):
        while self.que and value> self.que[-1]:
            self.que.pop()
        self.que.append(value)
​
    def front(self):
        return self.que[0]
​
class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        que = Myqueue()
        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

2.3 本题小结

1. 这道题，其实有点没明白，后面有时间的话，再做一遍这道题吧。但是怎么说呢，感觉做题目做到这里以后，我的代码思路有一定的提升

2. 队列的方法，还是不熟，有待继续去练习

3 leetcode347.前 K 个高频元素

题目链接：347. 前 K 个高频元素 - 力扣（LeetCode）

文章链接：代码随想录

视频链接：优先级队列正式登场！大顶堆、小顶堆该怎么用？| LeetCode：347.前 K 个高频元素哔哩哔哩bilibili

自己的思路：这道题，首先想的是利用哈希的方法，对数值做键，出现的次数做值，然后对值进行排序，最后返回前k个键

3.1 自己的方法

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        new_l = dict()
        for i in nums:
            if i not in new_l:
                new_l[i] =new_l.get(i,0)+1
            else:
                new_l[i] +=1
        sorted_new_l = sorted(new_l.items(),key = lambda x:x[1],reverse=True)
        return [key[0] for key in sorted_new_l[:k]]

3.2 视频后的方法

思路：

1. 其实和字典方法不同的在于，这里面排序是对前k个数据进行排序，不需要对整个队列进行排序

2. 第二个需要考虑的就是使用大顶堆还是小顶堆，大顶堆就是长度大于k的时候，就会弹出最大的数值；小顶堆就是长度大于k的时候弹出最小的数值，所以这道题使用的是小顶堆

3. 然后就对这个保存的小顶堆进行排序，因为使用小顶堆，所以数值是从小到大的顺序，所以排序的时候需要进行倒序，而且保存的是值、键

4. 在列表中进行返回的时候，就需要使用值从大到小排序，加入到列表中

import heapq
class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        new_l = dict()
        for i in nums:
            if i not in new_l:
                new_l[i] =new_l.get(i,0)+1
            else:
                new_l[i] +=1
        pri_que = []
        for key,freq in new_l.items():
            heapq.heappush(pri_que,(freq,key))
            if len(pri_que) >k:
                heapq.heappop(pri_que)
​
        result = [0]*k
        for i in range(k-1,-1,-1):
            result[i] = heapq.heappop(pri_que)[1]
        return result

3.3 本题小结

1. 这道题，思路上不难，但是有几个函数需要掌握，这个是属于这一块的重点

2. 函数掌握，import heapq这个是调用优先队列算法，默认就是最小堆，即小顶堆

3. heapq.heappush(heap, item)将 item 压入 heap 中，保持堆的性质。如果 heap 不是一个堆，此操作会将其转换为一个堆

4. heapq.heappop(heap) 弹出并返回 heap 中最小的元素，同时保持堆的性质

5. heapq.heappush(pri_que,(freq,key))这句话中，就是freq作为排序的数；key是附加给这个的

4 今日小结

1. 周三写吧，这个先空着，突然有事

2. 周三了，补起来，这几道题主要是关于栈和队列的，

3. 第一题的思路就是将数值放入栈中，然后如果遇到符号，就需要进行运算在运算过程中，注意的点就是python中的符号需要被定义，定义为不同的函数，然后如果遇到了进行调用，然后计算；这里面的计算名称一般都是内置函数，直接在后面加括号进行计算即可

4. 第二题的思路就是在队列中一直保持第一个值是最大值，然后对队列中的数据进行删除添加等操作

5. 第三题的自己的思路就是先构建字典，然后最后对字典的值进行排序得到答案；看视频后突然发现用队列也是一种方法，就是对需要的前k个数据进行排序，意义也是一样的