150. 逆波兰表达式求值 - 力扣（LeetCode）
题目要求：
1 、整数除法只保留整数部分；
2、该表达式总会得出有效数值且部存在除数为0的情况；
3、逆波兰表达式：是一种后缀表达式，所谓后缀就是指运算符写在后面。
from typing import List
from operator import add, sub, mul, floordiv, truediv
# 整数除法只保留整数部分；
def div(x, y):
return int(x / y) if x * y > 0 else -(abs(x) // abs(y))
class Solution:
# 摆出可能存在的计算方式，进行后续选择；
op_map = {'+': add, '-': sub, '*': mul, '/': div}
def evalRPN(self, tokens: List[str]) -> int:
stack = []
for i in tokens:
if i not in {'+', '-', '*', '/'}:
stack.append(int(i))
else:
# 先弹出栈顶元素，原始op2，再是op1；
op2 = stack.pop()
op1 = stack.pop()
stack.append(self.op_map[i](op1, op2))
return stack.pop()
if __name__ == '__main__':
tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
res = Solution().evalRPN(tokens)
print(res)不理解：为什么要自己写div函数，不是采用库函数？
解答：operator库中除法有两个函数，分别为truediv函数和floordiv函数，但是两者都不塌太符合；
原因：1、truediv函数，相除之后是小数；
2、floordiv函数，相除之后向下取整（例如，-0.545取为-1，可以我们来说要取整数部分，取为0）
239. 滑动窗口最大值 - 力扣（LeetCode）
自编思路：使用for循环搭配[num:num+k]进行滑窗，并使用max函数进行取出最大值，代码如下：
from typing import List
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
res = []
for i in range(len(nums)-k+1):
a = nums[i:i+k]
tmp = max(nums[i:i+k])
res.append(tmp)
return res
if __name__ == '__main__':
nums = [1, 3, -1, -3, 5, 3, 6, 7]
k = 3
res = Solution().maxSlidingWindow(nums, k)
print(res)结果，运行发现超出时间限制；看代码随想录发现，需要使用单调队列，直接使用list会超时；
使用单调队列方法代码如下：（该题困难，未完全理解，后续补充）
from typing import List
from collections import deque
class MyQueue:
def __init__(self):
self.queue = deque()
# 队列添加新的数值，当新的数值大于入口的之，就将队列后端的数值弹出，知道push的数值小于等于队列入口的数值为止；
# 这样就保持这个一个从大到小的队列；
def push(self, value):
while self.queue and value > self.queue[-1]:
self.queue.pop()
self.queue.append(value)
# 先判断当前队列是否为空，每次弹出时，比较当前弹出的数值是否等于队列出口元素值，相等则弹出；
def pop(self, value):
if self.queue and value == self.queue[0]:
self.queue.popleft()
# 查询当前最大值；
def front(self):
return self.queue[0]
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
que = MyQueue()
res = []
for i in range(k):
que.push(nums[i])
res.append(que.front())
for i in range(k, len(nums)):
que.pop(nums[i-k])
que.push(nums[i])
res.append(que.front())
return res
if __name__ == '__main__':
nums = [1, 3, -1, -3, 5, 3, 6, 7]
k = 3
res = Solution().maxSlidingWindow(nums, k)
print(res)347. 前 K 个高频元素 - 力扣（LeetCode）
根据题目要求，返回其中出现频率前K高的元素，第一反应就是通过字典计数，然后通过计数的值进行排序，返回第K高的元素的value;
1、使用字典的方式进行解题:
from typing import List
from collections import defaultdict
class Solution:
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
# 使用字典的方式计数
count_dict = defaultdict(int)
for i in nums:
count_dict[i] += 1
# 由于使用得到的计数值进行排序，得到第K高的值，则需要对字典的key和value进行对调；
index_dict = defaultdict(list)
for key in count_dict:
index_dict[count_dict[key]].append(key)
# 对调整好的字典的key值进行排序
key = list(index_dict.keys())
key = sorted(key)
res = []
count = 0
# 获取前K个
# 根据count != k进行筛出前K个值
while key and count != k:
# 经过排序后是升序，故最大值在最末尾，需要使用key[-1]进行取出
res += index_dict[key[-1]]
count += len(index_dict[key[-1]])
key.pop()
return res[0:k]
if __name__ == '__main__':
nums = [1, 1, 1, 2, 2, 3]
k = 2
res = Solution().topKFrequent(nums, k)
print(res) 2、使用本单元栈或队列的方法进行解题：
思路：
1、统计元素出现的频率进行计数；
2、对元素出现的计数进行排序；
3、找出前K个元素
针对思路2，对频率计数排序的问题，可以使用一种容器适配器就是优先级队列，其实就是一个披着队列外衣的堆（因为优先级队列对外接口只是从对头取元素，从队尾添加元素，再无其他元素的方式，看起来就是一个队列）；
什么是堆：
堆是一棵完全二叉树，树中每个节点的值都不小于（或者不大于）其左右孩子的值；如果父亲节点是大于等于左右孩子就是大顶堆，小于等于左右孩子就是小顶堆。所以，大顶堆（堆头是最大元素），小顶堆（堆头是最小元素）。可以使用priority_queue（优先级队列）进行实现；
本次我们使用小顶堆进行实现；为什么不用大顶堆呢？因为在每次移动更新大顶堆的时候，每次弹出都把最大的元素弹出去了，那么怎么保留下来前K个高频元素呢？所以要统计最大前k个元素，只有小顶堆每次将最小的元素弹出，最后小顶堆里积累的才是前k个最大元素。
代码如下所示：（理解方法和做法，但是代码未完全理解，总是觉得有些奇怪，但是debug又能够理解其中值的变化）；
from typing import List
# 引入堆
import heapq
class Solution:
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
# 使用map进行元素计数
map_ = {}
for i in range(len(nums)):
map_[nums[i]] = map_.get(nums[i], 0) + 1
# 对元素计数进行排序
# 定义一个小顶堆
pri_que = []
# 用固定大小为K的小顶堆，遍历所有的计数值
for key, count in map_.items():
heapq.heappush(pri_que, (count, key))
# 若堆的大小大于K，则队列弹出，保证堆的大小一直为K；
if len(pri_que) > k:
heapq.heappop(pri_que)
# 找出计数前K高的元素，因为小顶堆最先弹出的是最小值，所以要倒序输出；
res = [0] * k
for i in range(k-1, -1, -1):
res[i] = heapq.heappop(pri_que)[1]
return res
if __name__ == '__main__':
nums = [1, 1, 1, 2, 2, 3]
k = 2
res = Solution().topKFrequent(nums, k)
print(res)栈与队列总结
1、 要掌握栈与队列的基本操作；
2、栈内的数据在内存中不一定是连续分布的（栈是容器适配器，底层容器使用不同的容器）；deque在内存中的数据分布也是不连续的（缺省情况下，默认底层容器是deque）；
3、递归的实现是栈：每一次递归调用都会把函数的局部变量、参数值和返回地址等压入调用栈中，然后递归返回的时候，从栈顶弹出上一次递归的各项参数，所以这就是递归为什么可以返回上一层位置的原因；
标签：第十一天,__,nums,int,res,self,随想录,key,求值 From： https://blog.csdn.net/weixin_49494409/article/details/143941672