day10-数据结构力扣

150. 逆波兰表达式求值

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

说实话，我示例没看懂，我不懂他那个计算顺序，哪两个数字计算是怎么判断的

思路

什么是逆波兰表达式？

逆波兰表达式（Reverse Polish Notation, RPN）是一种数学表达式的书写方式，也称为后缀表达式。其特点是将运算符置于操作数之后，无需括号即可明确运算顺序。例如，表达式3 4 +等价于中缀表达式3 + 4。

特点

• 无括号优先级：运算顺序由操作符的位置决定，无需依赖括号。

• 从左到右解析：表达式按顺序读取，遇到运算符时对前两个操作数进行计算。

• 栈结构适用：适合用栈数据结构高效处理运算过程。

示例

• 中缀表达式(5 + 3) * 2转换为逆波兰表达式为5 3 + 2 *。
• 中缀表达式9 - (2 + 3)转换为逆波兰表达式为9 2 3 + -。

计算步骤

1. 初始化空栈：用于存储操作数。

2. 遍历表达式：逐个读取表达式中的元素。

   • 遇到操作数时压入栈。

   • 遇到运算符时，弹出栈顶两个操作数进行计算，并将结果压回栈中。

3. 返回结果：最终栈中剩余的唯一元素即为计算结果。

示例计算5 3 + 2 *：

• 压入5和3，遇到+时计算5 + 3 = 8，压入8。

• 压入2，遇到*时计算8 * 2 = 16。结果为16。

有点理解了：

就是从左到右，先把数放到栈里，遇到计算符号，

把计算符号的前两个数字用这个符号计算

得到结果再放入栈中，循环这个过程，直到算完。

写题

错误

通过了18/22个测试用例

class Solution: def evalRPN(self, tokens: List[str]) -> int: stack=[] for i in tokens: if i=='+': res1=stack[-2]+stack[-1] stack.pop() stack.pop() stack.append(res1) elif i=='-': res2=stack[-2]-stack[-1] stack.pop() stack.pop() stack.append(res2) elif i=='/': res3=stack[-2]//stack[-1] if res3<0: res3+=1 stack.pop() stack.pop() stack.append(res3) elif i=='*': res4=stack[-2]*stack[-1] stack.pop() stack.pop() stack.append(res4) else: stack.append(int(i)) print(stack) return stack[0]

他这个除法这里我写不好，到底是除/但是示例结果又没有小数点

整除//?但是他6//-132=-1?好像是向下取整，所以我之前在这里加了判断，但是如果刚好整除，那这个处理就不对。

if res3<0: res3+=1

关键修复说明

• 除法用int(a / b)而不是a // b

  • a / b得到浮点数

  • int()强制向零取整，完全符合题目要求

提交

class Solution: def evalRPN(self, tokens: List[str]) -> int: stack = [] for i in tokens: if i == '+': # 弹出两个数：后弹出的是左操作数 b = stack.pop() a = stack.pop() stack.append(a + b) elif i == '-': b = stack.pop() a = stack.pop() stack.append(a - b) elif i == '*': b = stack.pop() a = stack.pop() stack.append(a * b) elif i == '/': b = stack.pop() a = stack.pop() # 核心修复：向零取整 stack.append(int(a / b)) else: # 数字直接入栈 stack.append(int(i)) return stack[0]

对于冗余的代码进行了优化，在弹出元素的同时，取出元素。

在append后面进行计算，简化变量的使用

class Solution: def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]: res=[] for i in range(len(nums)-k+1): window=nums[i:i+k] res.append(max(window)) return res

思路

是之前切片再求最大值的时间复杂度太高，用单调队列进行优化

维护单调的队列，加入一个元素，如果前面元素没有加入的元素大，把前面的元素弹出。

这样第一个就是队列里面最大的元素，我们可以直接得到最大的值

写题

from collections import deque from typing import List class Solution: def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]: max_list = [] # 结果：每个窗口最大值 q = deque() # 单调递减队列，队头=当前最大值 for i in range(len(nums)): # 新元素入队，删掉前面比它小的 while q and nums[i] > q[-1]: q.pop() q.append(nums[i]) # 窗口左边移出的如果是队头，也要删掉 if i >= k and nums[i - k] == q[0]: q.popleft() # 窗口形成后，记录队头 if i >= k - 1: max_list.append(q[0]) return max_list

from typing import List class Solution: def topKFrequent(self, nums: List[int], k: int) -> List[int]: # 1. 创建字典：key=数字，value=出现次数 count_dict = {} # 2. 遍历数组，统计每个数字出现几次 for num in nums: if num in count_dict: # 已经存在，次数+1 count_dict[num] += 1 else: # 第一次出现，次数=1 count_dict[num] = 1 # 3. 把字典转成列表：[[数字, 次数], [数字, 次数]...] count_list = [] for key, value in count_dict.items(): count_list.append([key, value]) # 4. 简化排序：按次数从大到小排 count_list.sort(key=lambda x: x[1], reverse=True) # 5. 切片直接取前k个数字（一行搞定） result = [item[0] for item in count_list[:k]] return result