代码随想录第十天——LeetCode 150. 逆波兰表达式求值、239. 滑动窗口最大值、347.前 K 个高频元素

150. 逆波兰表达式求值

力扣题目链接(opens new window)

根据 逆波兰表示法,求表达式的值。

有效的运算符包括 + ,  - ,  * ,  / 。每个运算对象可以是整数,也可以是另一个逆波兰表达式。

说明:

整数除法只保留整数部分。 给定逆波兰表达式总是有效的。换句话说,表达式总会得出有效数值且不存在除数为 0 的情况。

示例 1:

  • 输入: ["2", "1", "+", "3", " * "]
  • 输出: 9
  • 解释: 该算式转化为常见的中缀算术表达式为:((2 + 1) * 3) = 9

逆波兰表达式:是一种后缀表达式,所谓后缀就是指运算符写在后面。

平常使用的算式则是一种中缀表达式,如 ( 1 + 2 ) * ( 3 + 4 ) 。

该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * ) 。

逆波兰表达式主要有以下两个优点:

  • 去掉括号后表达式无歧义,上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果。

  • 适合用栈操作运算:遇到数字则入栈;遇到运算符则取出栈顶两个数字进行计算,并将结果压入栈中。

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:op_map = {'+': add, '-': sub, '*': mul, '/': div}def evalRPN(self, tokens: List[str]) -> int:# tokens = list(tokens)stack = []for i in tokens:if i not in {'+', '-', '*', '/'}:stack.append(int(i))else:op2 = stack.pop()op1 = stack.pop()  # 这里是难点,"4","13","5","/","+"当到/的时候,第一个pop取出的是5,第二个pop取出的是13stack.append(self.op_map[i](op1, op2))return stack.pop()

239. 滑动窗口最大值

力扣题目链接(opens new window)

给定一个数组 nums,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回滑动窗口中的最大值。

from collections import dequeclass MyQUeue:def __init__(self):self.queue = deque()def push(self, value):while self.queue and value > self.queue[-1]:self.queue.pop()self.queue.append(value)def pop(self, value):if self.queue and value == self.queue[0]:self.queue.popleft()  # 把最大的元素pop掉,开始添加新元素了def front(self):return self.queue[0]class Solution:def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:que = MyQUeue()result = []for i in range(k):que.push(nums[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

思路:

1)push:如果push的元素比前元素大,直接把前面元素删掉,

2)pop:当要pop的值等于que的第一个(最大值)的时候说明这个值要真的被pop掉了,和他本身大小无关,只是滑窗滑到下一个了。

3)front:对于queue序列来说,第一个值queue[0],一直是最大值

347.前 K 个高频元素

力扣题目链接(opens new window)

给定一个非空的整数数组,返回其中出现频率前 k 高的元素。

示例 1:

  • 输入: nums = [1,1,1,2,2,3], k = 2
  • 输出: [1,2]

示例 2:

  • 输入: nums = [1], k = 1
  • 输出: [1]
class Solution:def topKFrequent(self, nums: List[int], k: int) -> List[int]:map_ = {}for i in range(len(nums)):map_[nums[i]] = map_.get(nums[i], 0)+1pri_que = []  # 小顶堆for key, freq in map_.items():heapq.heappush(pri_que, (freq, key))if len(pri_que) > k:heapq.heappop(pri_que)result = [0] * kfor i in range(k-1, -1, -1):result[i] = heapq.heappop(pri_que)[1]return result
  • for key, freq in map_.items():

    • 这个循环遍历字典 map_ 的所有键值对。
    • key 是字典中的键(通常表示某个元素)。
    • freq 是字典中对应键的值(表示该元素的频率)。
  • heapq.heappush(pri_que, (freq, key))

    • 使用 heapq.heappush 函数将元素 (freq, key) 推入优先队列 pri_que 中。
    • 这里使用的是一个小顶堆(默认情况下 heapq 实现的是小顶堆),堆中的每个元素是一个元组 (freq, key),其中 freq 是元素的频率,key 是元素的值。
    • 小顶堆的特性是堆顶元素总是最小的,因此当我们插入 (freq, key) 时,堆会自动调整顺序,使频率最小的元素保持在堆顶。
  • if len(pri_que) > k:

    • 检查堆 pri_que 的大小是否超过了 k
    • 如果堆中元素数量超过了 k,说明堆中已经有超过 k 个元素。
  • heapq.heappop(pri_que)

    • 如果堆的大小超过了 k,使用 heapq.heappop 将堆顶元素弹出。
    • 由于这是一个小顶堆,堆顶的元素是堆中频率最小的元素,所以弹出操作会移除当前频率最小的那个元素。
    • 通过这种方式,堆的大小始终保持在 k,并且堆中只保留频率最高的 k 个元素。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/412447.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

夜深了,赶紧根据软件系统建模建设一个房屋租赁服务系统,坐上收租大佬宝座,走上人生巅峰

目录 案例 【题目】 【问题 1】(12 分) 【问题 2】(5 分) 【问题 3】(8 分) 【答案】 【问题 1】答案 【问题 2】答案 【问题 3】答案 相关推荐 案例 阅读以下关于软件系统建模的叙述,在答题纸上回答问题 1 至问题 3。 【题目】 某公司欲建设一个房屋租赁服务…

如何在你vs code和ide编译器使用AI

vs code举例。先看效果图 2个步骤轻松拥有 1、注册豆包AI账号:点击注册 2、在vs code中安装: 第一种方法:快速安装 第二种方法:手动安装, 第1步:安装 Visual Studio Code 后,左侧导航栏上点击扩展。 第2步…

【C/C++】C语言中的内存分布

在C语言中,内存分布主要可以分为以下几个区域: 栈(Stack):由编译器自动分配和释放,存放函数的参数值、局部变量的值等。 堆(Heap):一般由程序员分配和释放,若…

SpringBoot异常处理原理分析

springboot默认机制 错误处理的自动配置都在ErrorMvcAutoConfiguration中,两大核心机制: SpringBoot 会自适应处理错误,响应页面或JSON数据 SpringMVC的错误处理机制依然保留,MVC处理不了,才会交给boot进行处理 发生…

K 个一组翻转链表

题目 给你一个链表,每 k 个节点一组进行翻转,请你返回翻转后的链表。 k 是一个正整数,它的值小于或等于链表的长度。 如果节点总数不是 k 的整数倍,那么请将最后剩余的节点保持原有顺序。 进阶: 你可以设计一个只…

2024年【A特种设备相关管理(A4电梯)】考试报名及A特种设备相关管理(A4电梯)考试资料

题库来源:安全生产模拟考试一点通公众号小程序 A特种设备相关管理(A4电梯)考试报名是安全生产模拟考试一点通总题库中生成的一套A特种设备相关管理(A4电梯)考试资料,安全生产模拟考试一点通上A特种设备相关…

AI模型:追求全能还是专精?

近日,OpenAI预计在秋季推出代号为“草莓”的新AI。从专注于数学问题到处理主观营销策略,"草莓"模型展现出惊人的多样性。而这种全能型 AI 是否代表了未来趋势?相比专攻于某一领域的专业型AI产品,全能型AI产品是否一定具…

全免费的数据恢复工具推荐!这几个不容错过!

不小心的数据丢失总会带来许多困扰,不过这些困扰也能通过一些全免费的数据恢复工具解决。接下来,就来给大家介绍几款好用的数据恢复工具! 第一款:福昕数据恢复 直达链接:www.pdf365.cn/foxit-restore/ 福昕数据恢复…

苹果秋季发布会前瞻:iPhone 16领衔新品盛宴

苹果定档9月9日,揭开新品神秘面纱 苹果公司近日正式宣布,将于9月9日在加州库比蒂诺的Apple Park,史蒂夫乔布斯剧院举办年度秋季新品发布会,主题为“It’s Glowtime”,预示着Siri界面将迎来一场华丽变身。此次发布会较原…

一分钟学会万用表

目录: 1、电池的安装 1)指针万用表 2)数字万用表 3)高精度表 2、表笔的分类 3、表笔安装 5、常用测量方法 1)二极管测量 2)电阻与通断测量 3)电压测量 4)电流测量 …

[C++]AVL树插入和删除操作的实现

AVL树又称为高度平衡的二叉搜索树,是1962年由两位俄罗斯数学家G.M.Adel’son-Vel’skii和E.M.Landis提出的。ALV树提高了二叉搜索树树的搜索效率。为此,就必须每向二叉搜索树插人一个新结点时调整树的结构,使得二叉搜索树保持平衡,从而尽可能降低树的高度,减少树的平均搜索长度…

数分基础(03-3)客户特征分析-Tableau

文章目录 客户特征分析 - Tableau1. 说明2. 思路与步骤3. 数据准备和导入3.1 用EXCEL初步检查和处理数据3.1.1 打开3.1.2 初步检查(1)缺失值(2)格式化日期字段(3)其他字段数据类型(4&#xff09…

桥梁在线监测解决方案:科技赋能,守护桥梁安全

在现代社会,桥梁作为连接城市与乡村、跨越河流与峡谷的重要交通设施,其安全性和稳定性直接关系到人民生命财产的安全以及经济社会的正常运转。然而,桥梁在长期使用过程中,会受到自然环境、车辆荷载、材料老化等多种因素的影响&…

8.26-docker创建容器+打包镜像+docker文件的学习

一、回顾 创建容器:docker run -it --name a1 centos:latest /bin/bash 查看容器:docker ps(查看正在up的容器) docker ps -a(查看所有的容器) 切回宿主机:ctrl p q 启动容器:docke…

KEIL Stm32 bin文件生成的两种方法以及报错的处理

Keil里生成bin文件的方法有两种,记录如下,以免忘记~ 首先,在Keil主页面,点击如下按钮,打开Options for Target ‘target 1’对话框,并选择User标签页。 其次,通过在 User标签页 设置 “After B…

react-native框架下,集成字体并应用全局

一、存放字体文件 将自定义字体文件(例如 .ttf 或 .otf 文件)放入项目的 assets/fonts 目录中。如果没有这个目录,可以手动创建。 二、配置字体 在项目根目录下建一个文件:react-native.config.js,文件内容如下&…

等保测评的五大误区与应对策略

等保测评(信息安全等级保护测评)作为确保信息系统安全的重要环节,常常伴随着一些常见的误区,这些误区可能导致组织在实施等保工作时偏离正确方向,增加合规风险。以下是等保测评中的五大常见误区及其应对策略。 一、误区…

zookeeper服务搭建

zookeeper服务搭建 前言1. 前置准备2. 下载和解压Zookeeper3. 配置环境变量4. 编辑Zookeeper配置文件5. 配置Zookeeper节点ID6. 配置好的Zookeeper分发到其他节点7. 启动Zookeeper集群参考博客 前言 Zookeeper是一个开源的分布式协调服务,主要用于解决分布式应用中的…

Leetcode面试经典150题-82.删除排序链表中的重复元素II前序-83.删除排序链表中的重复元素

解法都在代码里,不懂就留言或者私信,比第一题稍微难点 题目比较简单,真实面试中82和83都出现过,83偏多,先有个基础,马上分析82 /*** Definition for singly-linked list.* public class ListNode {* …

视频智能分析厨帽检测算法,厨帽检测算法全套源码、样本和模型展示

厨帽检测算法是一种基于人工智能和计算机视觉技术的系统,旨在自动检测厨师是否佩戴了符合规范的厨帽。该算法通过分析视频流或图像数据,实时识别厨帽的佩戴情况,从而帮助餐饮企业确保员工的着装符合卫生标准。这一技术广泛应用于餐馆、厨房、…