代码随想录算法训练营第十一天|150. 逆波兰表达式求值|239. 滑动窗口最大值|347.前 K 个高频元素
150. 逆波兰表达式求值
根据 逆波兰表示法，求表达式的值。
有效的运算符包括 + , - , * , / 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。
说明：
整数除法只保留整数部分。 给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。
逆波兰表达式：是一种后缀表达式，所谓后缀就是指运算符写在后面。
平常使用的算式则是一种中缀表达式，如 ( 1 + 2 ) * ( 3 + 4 ) 。
该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * ) 。
逆波兰表达式主要有以下两个优点：
去掉括号后表达式无歧义，上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果。
适合用栈操作运算：遇到数字则入栈；遇到运算符则取出栈顶两个数字进行计算，并将结果压入栈中
class Solution:
def evalRPN(self, tokens: List[str]) -> int:
from operator import add,sub,mul
def div(x,y):
if x/y>0:
return int(x/y)
else:
return -int(-x/y)
admap={'+':add,'-':sub,'*':mul,'/':div}
stack=[]
for token in tokens:
if token not in {'+','-','*','/'}:
stack.append(int(token))
else:
op2=stack.pop()
op1=stack.pop()
stack.append(admap[token](op1,op2))
return stack.pop()
239. 滑动窗口最大值
给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回滑动窗口中的最大值。
进阶：
你能在线性时间复杂度内解决此题吗？
from typing import List
from collections import deque
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
dq=deque()
result=[]
for i,num in enumerate(nums):
#降序
#nums和dq都使用方括号取数
while dq and nums[dq[-1]]<=num:
dq.pop()
dq.append(i)
#处理队末小值
if dq[0]<=i-k:
dq.popleft()
#处理队头大值
if i>=k-1:
result.append(nums[dq[0]])
#需要等队列中有k个值
return result
在Python中， deque （发音为“deck”，是“double-ended queue”的缩写）是 collections 模块中提供的一种数据结构，它是一个双端队列。
deque 有以下特点和常见用法：
1. 高效的两端操作： deque 允许在队列的两端（头部和尾部）进行高效的添加和删除元素操作。在列表（ list ）中，在头部插入或删除元素的时间复杂度为O(n)，因为需要移动其他元素；而 deque 在两端操作的时间复杂度为O(1)。
2. 创建 deque 对象：
python
from collections import deque
# 创建一个空的deque
dq = deque()
# 创建一个包含初始元素的deque
dq = deque([1, 2, 3])
3. 添加元素：
- append(x) ：在 deque 的右侧（尾部）添加一个元素 x 。
- appendleft(x) ：在 deque 的左侧（头部）添加一个元素 x 。
python
dq = deque([1, 2, 3])
dq.append(4)
print(dq) # deque([1, 2, 3, 4])
dq.appendleft(0)
print(dq) # deque([0, 1, 2, 3, 4])
4. 删除元素：
- pop() ：移除并返回 deque 右侧（尾部）的元素。
- popleft() ：移除并返回 deque 左侧（头部）的元素。
python
dq = deque([0, 1, 2, 3, 4])
print(dq.pop()) # 4
print(dq) # deque([0, 1, 2, 3])
print(dq.popleft()) # 0
print(dq) # deque([1, 2, 3])
5. 限制长度：可以在创建 deque 时指定最大长度，当 deque 达到最大长度后，再添加元素时，会自动从另一端移除元素。
python
dq = deque(maxlen=3)
dq.append(1)
dq.append(2)
dq.append(3)
dq.append(4)
print(dq) # deque([2, 3, 4])
deque 在处理需要频繁在队列两端进行操作的场景中非常有用，比如广度优先搜索（BFS）算法中存储待访问的节点等。
347.前 K 个高频元素
给定一个非空的整数数组，返回其中出现频率前 k 高的元素。
示例 1:
输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]
示例 2:
输入: nums = [1], k = 1
输出: [1]
class Solution:
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
from collections import Counter
count=collections.Counter(nums)
#Counter是统计元素频数的函数
dct=count.most_common(k)
#k个，返回元组组成的列表
dct.sort(key=lambda x: x[1],reverse=True)
#lambda reverse
lst=[dc[0] for dc in dct[:k]]
return lst