在补在补了
打卡Day13
- 1.150. 逆波兰表达式求值
- 2.239. 滑动窗口最大值
- 3.347. 前 K 个高频元素
- 总结
1.150. 逆波兰表达式求值
题目链接:逆波兰表达式求值
文档讲解: 代码随想录
class Solution(object):
def evalRPN(self, tokens):
"""
:type tokens: List[str]
:rtype: int
"""
stack = []
for i in tokens:
if i not in {'+', '-', '*', '/'}:
stack.append(i)
else:
num1 = int(stack.pop())
num2 = int(stack.pop())
if i == '+':
stack.append(num1 + num2)
elif i == '-':
stack.append(num2 - num1)
elif i == '*':
stack.append(num2 * num1)
else:
stack.append(num2 // num1 if num1 * num2 > 0 else - (abs(num2) // abs(num1)))
return int(stack.pop())
两个注意点:
(1)弹出的元素要进行类型转换,因为存储的是字符,要转成整型
(2)进行整除操作的时候,要考虑到负数的情况;要用绝对值整除,再取负
可以调用内置函数
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):
op_map = {'+': add, '-': sub, '*': mul, '/': div}
def evalRPN(self, tokens: List[str]) -> int:
stack = []
for token in tokens:
if token not in {'+', '-', '*', '/'}:
stack.append(int(token))
else:
op2 = stack.pop()
op1 = stack.pop()
stack.append(self.op_map[token](op1, op2)) # 第一个出来的在运算符后面
return stack.pop()
2.239. 滑动窗口最大值
题目链接:滑动窗口最大值
文档讲解: 代码随想录
思路:暴力求解过程中,遍历一遍的复杂度为O(n × m)。大顶堆(优先级队列)会改变队列元素的顺序,会导致弹出元素的时候出现问题。使用的单调队列只维护有可能成为窗口最大值的元素,同时保持队列里的元素数值是由大到小的,与优先级队列最大的区别是不改变队列中元素的顺序。
class MyQueue:
#单调队列
def __init__(self):
self.queue = deque() #直接使用list会超时
#检查要弹出的元素是否为队列出口元素的数值
def pop(self, value):
if self.queue and value == self.queue[0]:
self.queue.popleft()
#如果push的数值大于入口元素,就将队列后端的数值弹出,直到push的数值小于入口元素值
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 = MyQueue()
result = []
#先放前k个元素
for i in nums[:k]:
que.push(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
3.347. 前 K 个高频元素
题目链接:前 K 个高频元素
文档讲解: 代码随想录
暴力解法
class Solution(object):
def topKFrequent(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: List[int]
"""
#统计出现频率
time_dict = defaultdict(int)
for i in nums:
time_dict[i] += 1
#定义字典,key为出现次数,value是对应的数字
index_dict = defaultdict(list)
for key in time_dict:
#新字典将相同频率的数字放在同一个列表中
index_dict[time_dict[key]].append(key)
#升序
key = list(index_dict.keys())
key.sort()
res = []
count = 0
#获取前k项
# +=: 将右侧的可迭代对象中的元素追加到左侧的列表中
while key and count != k:
res += index_dict[key[-1]]
count += len(index_dict[key[-1]])
#移除列表最后一个元素
key.pop()
return res[:k]
import heapq
class Solution(object):
def topKFrequent(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: List[int]
"""
#定义字典统计频率
mapping = {}
for i in range(len(nums)):
mapping[nums[i]] = mapping.get(nums[i], 0) + 1
#定义一个大小为k的小顶堆,对频率进行排序
pri_que = []
for key, freq in mapping.items():
heapq.heappush(pri_que, (freq, key))
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
总结
在python中,栈的元素在内存中并不是连续分布的,其通常通过列表来实现,列表中的元素并不一定是连续分布的,是个动态数组,元素存储在堆内存中,并不要求连续的内存块。