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

算法训练第十一天

backend 2025/6/23 18:58:05

150. 逆波兰表达式求值

代码：

class Solution(object):def evalRPN(self, tokens):""":type tokens: List[str]:rtype: int"""stack = []for i in tokens:if i=='+':b = int(stack.pop())a = int(stack.pop())stack.append(a+b)elif i=='-':b = int(stack.pop())a = int(stack.pop())stack.append(a-b)elif i=='*':b = int(stack.pop())a = int(stack.pop())stack.append(a*b)elif i == '/':b = int(stack.pop())a = int(stack.pop())if a * b < 0:res = abs(a)//abs(b)stack.append(-res)else:stack.append(a // b)else:stack.append(int(i))return int(stack[0])

239. 滑动窗口最大值

代码：

class Queue:def __init__(self):self.arr = []def add(self,x):while len(self.arr)>0 and self.arr[len(self.arr)-1]<x:self.arr.pop()self.arr.append(x)def delete(self, x):if self.arr[0] == x:self.arr.pop(0)def get_max(self):return self.arr[0]class Solution(object):def maxSlidingWindow(self, nums, k):""":type nums: List[int]:type k: int:rtype: List[int]"""ans = []queue = Queue()i = 0j = 0while j< len(nums):queue.add(nums[j])if j-i>=k:queue.delete(nums[i])i+=1if j-i+1>=k:ans.append(queue.get_max())j+=1return ans

347.前 K 个高频元素

代码：

class Solution(object):def topKFrequent(self, nums, k):""":type nums: List[int]:type k: int:rtype: List[int]"""nums.sort()di = {}for i in nums:if di.get(i):di[i]+=1else:di[i]=1di_items = di.items()res = sorted(di_items, key=lambda x: x[1], reverse=True)ans = []for i in res:ans.append(i[0])if len(ans)==k:return ans