码随想录算法训练营Day11 | LeetCode150. 逆波兰表达式求值,239. 滑动窗口最大值, 347.前 K 个高频元素

server/2025/1/11 4:45:39/

LeetCode150. 逆波兰表达式求值

题目链接/文章讲解/视频讲解:https://programmercarl.com/0150.%E9%80%86%E6%B3%A2%E5%85%B0%E8%A1%A8%E8%BE%BE%E5%BC%8F%E6%B1%82%E5%80%BC.html

后缀表达式无需写括号,而中缀表达式需要有括号

栈适用于相邻字符的消除操作

python">class Solution:def evalRPN(self, tokens: List[str]) -> int:# 题目中有个要求:两个整数之间的除法总是 向零截断。向零截断指进行除法运算时,不论结果是正是负,都直接丢掉小数部分,保留整数部分# 但python中的地板除//是取离除法的结果最接近但小于该结果的整数部分# 所以我们要对此题中的除法进行新的定义from operator import add, sub, muldiv = lambda x, y: x // y if x * y > 0 else -(abs(x) // abs(y))opt_fun = {'+' : add, '-' : sub, '*' : mul, '/' : div}# 用列表模拟栈stack = []for i in range(len(tokens)):# 遇到算符则弹出栈顶的两个数字元素,进行相应的算符运算if tokens[i] in opt_fun:num1 = stack.pop()num2 = stack.pop()stack.append( opt_fun[ tokens[i] ]( num2 , num1 )  )# 若遇到数字则压入栈else:stack.append( int(tokens[i]) )ans = stack.pop()return ans

时间复杂度: O(n)
空间复杂度: O(n)

239. 滑动窗口最大值

本题算比较有难度的,需要自己去构造单调队列

题目链接/文章讲解/视频讲解:https://programmercarl.com/0239.%E6%BB%91%E5%8A%A8%E7%AA%97%E5%8F%A3%E6%9C%80%E5%A4%A7%E5%80%BC.html

python">from collections import deque
from typing import Listclass Myqueue:'''实现单调队列'''def __init__(self):self.que = deque()   # 用deque对象模拟单调队列,用list对象会超时def pop(self, val:int) -> None:'''理论上来说滑动窗口每移动一格,需要从单调队列pop一个元素,再push一个元素进入单调队列。但由于单调队列的对头是当前 滑动窗口中值最大的元素,所以只有当滑动窗口即将pop的元素等于队头元素时才确确实实需要对单调队列执行pop操作当滑动窗口即将pop的元素小于队头元素时,说明该元素之前由于小于滑动窗口中最大值而已被pop掉,无需再执行pop操作'''if self.que and val == self.que[0]:self.que.popleft()def push(self, val:int) -> None:'''将即将压入单调队列的元素与队尾元素比大小,若大于队尾元素值,则弹出队尾元素反复进行上述操作,直到即将压入的的元素小于队尾元素'''while self.que and val > self.que[-1]:self.que.pop()self.que.append(val)def getMax(self) -> int:return self.que[0]class Solution:def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:que = Myqueue()result = []# 先将前k个元素按照单调队列的规则压入队列for i in range(k):que.push(nums[i])tempMax = que.getMax()result.append(tempMax)# 滑动窗口开始移动for i in range( len(nums) - k ):que.pop( nums[i] )que.push( nums[i+k])tempMax = que.getMax()result.append(tempMax)return result

时间复杂度: O(n)
空间复杂度: O(k)

347.前 K 个高频元素

大/小顶堆的应用,也即优先级队列

题目链接/文章讲解/视频讲解:https://programmercarl.com/0347.%E5%89%8DK%E4%B8%AA%E9%AB%98%E9%A2%91%E5%85%83%E7%B4%A0.html

python">import heapqclass Solution:def topKFrequent(self, nums: List[int], k: int) -> List[int]:my_map = {}# 用哈希表存储nums数组,键为nums中的元素值,key为对应键在nums中出现的次数for i in range(len(nums)):my_map[nums[i]] = my_map.get( nums[i], 0 ) + 1    # my_map.get(nums[i],0)指从字典my_map中找出键为nums[i]的value值,若不存在该键,则返回默认值0# 注:不可用my_map[nums[i]] = my_map[nums[i]] + 1, 因为当my_map中没有mums[i]元素时,无法执行my_map[nums[i]] + 1操作# 列表用于存储小顶堆# heapq用于实现逻辑上对堆的各种操作least_heap = [] # 为什么用小顶堆而不是大顶堆?# 若用大顶堆,每次往堆中加入新元素并排序后,堆顶元素将是最大的,此时若堆大小大于k,需从堆中推出多余元素,即推出堆顶元素,这样最终在堆中留下来的k个元素将是最小的k个元素,和我们想要的恰恰相反for value, freq in my_map.items():# heappush(least_heap, (freq, value))用于将元组(freq, value)插入到堆least_heap中(默认为小顶堆)# 小顶堆的逻辑是堆顶是最小值,按照元组的第一个元素freq进行排序,若freq相等,则根据元组的第二个元素value进行排序heapq.heappush( least_heap, (freq, value) )if len(least_heap) > k:# heappop()的逻辑是弹出并返回堆顶元素。弹出后,堆结构将自动调整,将最后一个元素移到堆顶,并对其进行下沉操作,确保堆的特性得以恢复heapq.heappop(least_heap)#按照出现次数从小到大放入result列表中result = [0] * kfor i in range(k-1, -1, -1):result[i] = heapq.heappop(least_heap)[1]return result

时间复杂度:O(Nlogk),其中 N 为数组的长度。我们首先遍历原数组,并使用哈希表记录出现次数,每个元素需要 O(1) 的时间,共需 O(N) 的时间。随后,我们遍历「出现次数数组」,由于堆的大小至多为 k,因此每次堆操作需要 O(logk) 的时间,共需 O(Nlogk) 的时间。二者之和为 O(Nlogk)。

空间复杂度:O(N)。哈希表的大小为 O(N),而堆的大小为 O(k),共计为 O(N)。

总结

灵魂四问:

  1. C++中stack,queue 是容器么?
  2. 我们使用的stack,queue是属于那个版本的STL?
  3. 我们使用的STL中stack,queue是如何实现的?
  4. stack,queue 提供迭代器来遍历空间么

http://www.ppmy.cn/server/157375.html

相关文章

【数据结构】 树的遍历:先序、中序、后序和层序

在数据结构中,树(Tree)作为一种基础的非线性结构,广泛应用于多种场景。树的遍历是树操作中的重要组成部分,它决定了我们如何访问树中的每一个节点。树的遍历方法有多种,每种方法适用于不同的场景&#xff0…

【EI,Scopus检索 | 往届均已检索见刊】第四届智能系统、通信与计算机网络国际学术会议(ISCCN 2025)

重要信息: 大会官网:更多详情【论文投稿】 截稿时间:以官网信息为准 大会时间:2025年2月21-23日 接受/拒稿通知:投稿后3-5个工作日内 收录检索:EI,Scopus 出版信息: 本会议所有…

cursor试用出现:Too many free trial accounts used on this machine 的解决方法

文章精选推荐 1 JetBrains Ai assistant 编程工具让你的工作效率翻倍 2 Extra Icons:JetBrains IDE的图标增强神器 3 IDEA插件推荐-SequenceDiagram,自动生成时序图 4 BashSupport Pro 这个ides插件主要是用来干嘛的 ? 5 IDEA必装的插件&…

2025新年源码免费送

2025很开门很开门的源码免费传递。不需要馒头就能获取4套大开门源码。 听泉偷宝,又进来偷我源码啦👊👊👊。欢迎偷源码 🔥🔥🔥 获取免费源码以及更多源码,可以私信联系我 我们常常…

Github 2025-01-08 C开源项目日报 Top10

根据Github Trendings的统计,今日(2025-01-08统计)共有10个项目上榜。根据开发语言中项目的数量,汇总情况如下: 开发语言项目数量C项目10Shell项目1Redis - 内存数据库和数据结构服务器 创建周期:5411 天开发语言:C协议类型:BSD 3-Clause “New” or “Revised” License…

腾讯云大数据智能管家:AI驱动管理效能飞升

点击蓝字⬆ 关注我们 本文共计1241 预计阅读时长4分钟 在大数据时代,海量数据的产生给企业带来了新的机遇,也带来了复杂的管理挑战。如何高效利用数据资源、降低运维成本、提升系统性能成为每个企业的共同难题。腾讯云推出的大数据智能管家,以…

阿里巴巴新零售模式下的创新实践:结合开源AI智能名片2+1链动模式S2B2C商城小程序的应用探索

摘要:在数字经济浪潮的推动下,新零售作为传统零售与现代信息技术深度融合的产物,正逐步改变着零售行业的面貌。阿里巴巴作为新零售战略的倡导者和实践者,通过整合线上线下资源,利用大数据、云计算等先进技术&#xff0…

HTML 音频(Audio)

HTML 音频(Audio) HTML5 引入了新的音频标签 <audio>,使得在网页上嵌入音频文件变得更加简单。在此之前,播放音频通常需要依赖于第三方插件,如 Flash。但随着 HTML5 的普及,浏览器原生支持音频播放,极大地提升了用户体验和网页性能。 基本用法 要使用 HTML5 的音…