day10-数据结构力扣

150. 逆波兰表达式求值题目链接150. 逆波兰表达式求值 - 力扣LeetCode说实话我示例没看懂我不懂他那个计算顺序哪两个数字计算是怎么判断的思路什么是逆波兰表达式逆波兰表达式Reverse Polish Notation, RPN是一种数学表达式的书写方式也称为后缀表达式。其特点是将运算符置于操作数之后无需括号即可明确运算顺序。例如表达式3 4 等价于中缀表达式3 4。特点无括号优先级运算顺序由操作符的位置决定无需依赖括号。从左到右解析表达式按顺序读取遇到运算符时对前两个操作数进行计算。栈结构适用适合用栈数据结构高效处理运算过程。示例中缀表达式(5 3) * 2转换为逆波兰表达式为5 3 2 *。中缀表达式9 - (2 3)转换为逆波兰表达式为9 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: res1stack[-2]stack[-1] stack.pop() stack.pop() stack.append(res1) elif i-: res2stack[-2]-stack[-1] stack.pop() stack.pop() stack.append(res2) elif i/: res3stack[-2]//stack[-1] if res30: res31 stack.pop() stack.pop() stack.append(res3) elif i*: res4stack[-2]*stack[-1] stack.pop() stack.pop() stack.append(res4) else: stack.append(int(i)) print(stack) return stack[0]他这个除法这里我写不好到底是除/但是示例结果又没有小数点整除//?但是他6//-132-1?好像是向下取整所以我之前在这里加了判断但是如果刚好整除那这个处理就不对。if res30: res31关键修复说明除法用int(a / b)而不是a // ba / 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后面进行计算简化变量的使用239. 滑动窗口最大值题目链接239. 滑动窗口最大值 - 力扣LeetCode这几天做到的第一道力扣标注困难的题目有一种错觉是我感觉我能写先写一下试试看。我直接用列表切片的方法做但是提交38/52有些是超过了时间限制。不是他数据这么多怎么能怪我超时自己不知道把测试数据弄少一点class Solution: def maxSlidingWindow(self, nums: List[int], k: int) - List[int]: res[] for i in range(len(nums)-k1): windownums[i:ik] 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_list347.前 K 个高频元素题目链接347. 前 K 个高频元素 - 力扣LeetCode思路遍历统计 → 字典字典转列表 → 方便排序列表按次数降序排序切片取前 k 个数字写题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(keylambda x: x[1], reverseTrue) # 5. 切片直接取前k个数字一行搞定 result [item[0] for item in count_list[:k]] return result