【算法day10】栈与队列:拓展与应用
题目引用
- 逆波兰表达式求值
- 滑动窗口最大值
- 前k个高频元素
1.逆波兰表达式求值
给你一个字符串数组 tokens ,表示一个根据 逆波兰表示法 表示的算术表达式。
请你计算该表达式。返回一个表示表达式值的整数。
注意:
有效的算符为 ‘+’、‘-’、‘*’ 和 ‘/’ 。
每个操作数(运算对象)都可以是一个整数或者另一个表达式。
两个整数之间的除法总是 向零截断 。
表达式中不含除零运算。
输入是一个根据逆波兰表示法表示的算术表达式。
答案及所有中间计算结果可以用 32 位 整数表示。
示例 1:
输入:tokens = [“2”,“1”,“+”,“3”,“*”]
输出:9
解释:该算式转化为常见的中缀算术表达式为:((2 + 1) * 3) = 9
示例 2:
输入:tokens = [“4”,“13”,“5”,“/”,“+”]
输出:6
解释:该算式转化为常见的中缀算术表达式为:(4 + (13 / 5)) = 6
示例 3:
输入:tokens = [“10”,“6”,“9”,“3”,“+”,“-11”,““,”/“,””,“17”,“+”,“5”,“+”]
输出:22
解释:该算式转化为常见的中缀算术表达式为:
((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22
这道题目就很简单,我们只需要定义一个栈st
,然后遍历一遍数组,不是符号的话就入栈,遇到符号的话就从栈中取出两个元素进行加减乘除运算,再压入栈中。最后返回栈中元素。
来看代码:
int evalRPN(vector<string>& tokens) {stack<long long> st; for (int i = 0; i < tokens.size(); i++) {if (tokens[i] == "+" || tokens[i] == "-" || tokens[i] == "*" || tokens[i] == "/") {long long num1 = st.top();st.pop();long long num2 = st.top();st.pop();if (tokens[i] == "+") st.push(num2 + num1);if (tokens[i] == "-") st.push(num2 - num1);if (tokens[i] == "*") st.push(num2 * num1);if (tokens[i] == "/") st.push(num2 / num1);} else {st.push(stoll(tokens[i]));}}int result = st.top();st.pop(); // 把栈里最后一个元素弹出(其实不弹出也没事)return result;}
这里需要注意栈中元素进行运算时可能会溢出,所以使用long long
来定义中间值。
2.滑动窗口最大值
给你一个整数数组 nums,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。
示例 1:
输入:nums = [1,3,-1,-3,5,3,6,7], k = 3
输出:[3,3,5,5,6,7]
解释:
滑动窗口的位置 最大值
[1 3 -1] -3 5 3 6 7 | 3
1 [3 -1 -3] 5 3 6 7 | 3
1 3 [-1 -3 5] 3 6 7 | 5
1 3 -1 [-3 5 3] 6 7 | 5
1 3 -1 -3 [5 3 6] 7 | 6
1 3 -1 -3 5 [3 6 7] | 7
示例 2:
输入:nums = [1], k = 1
输出:[1]
这道题比较难实现,如果是第一次刷题的话遇到这种题目就可以直接跳过了。
我们来看题目,题目要求我们找到每次滑动窗口滑动时的最大值,那么我们就可以想一下,可不可以创建一个自动找到最大值或者说第二大的数据结构呢,可能很多人会想到优先级队列。优先级队列是一种思路,可是我们再仔细想想,我们一开始就要入一些元素进来,而只有优先级队列的top()
是我们需要的,其他的我们都可以丢弃,那这就造成了空间的浪费,而且随着滑动窗口向后移动,遇到比原来top()
小,比其他值大的数时就可能产生混乱,无法判断这个值什么时候该弹出,或者早该弹出却因为其他值比它大而没有弹出导致后续的结果出现问题。
所以我们需要一种方便我们进行弹入弹出又能便于维护的数据结构,是什么呢?没有~
但是我们可以造一个,而底层我们就用deque
这种便于头插头删尾插尾删的数据结构。当我们滑动窗口向前滑动时,我们要把即将进入的值与已经在队列中的值一一比对,只要比即将要插入的值小,那么就直接pop_back()
,直到找到比自己大的数或者队列清空。同时队列头部与将要滑出窗口的值进行比较,如果等于就大胆pop_front()
,然后再将尾插头删后的队列的front()
插入结果数组中,如此循环,就得到了每一轮的最大值。
这样说大概大家还是云里雾里,那么来看代码吧:
class Myqueue{private:deque<int> que;public:void push(int x){while(!que.empty()&&x>que.back()) que.pop_back();que.push_back(x);}void pop(int x){if(!que.empty()&&x==que.front()) que.pop_front();}int front(){return que.front();}};vector<int> maxSlidingWindow(vector<int>& nums, int k) {Myqueue que;vector<int> result;for (int i = 0; i < k; i++) { // 先将前k的元素放进队列que.push(nums[i]);}result.push_back(que.front()); // result 记录前k的元素的最大值for (int i = k; i < nums.size(); i++) {que.pop(nums[i - k]); // 滑动窗口移除最前面元素que.push(nums[i]); // 滑动窗口前加入最后面的元素result.push_back(que.front()); // 记录对应的最大值}return result;}
3.前k个高频元素
给你一个整数数组 nums 和一个整数 k ,请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
示例 1:
输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]
示例 2:
输入: nums = [1], k = 1
输出: [1]
这题相较于上一题来说就稍微简单一点了,我们直接说思路吧,他要找前k
频率的元素,那么我们就要先使用unordered_map
将每个元素出现的频率统计一下,然后再用小根堆来记录,为什么是小根堆,因为是前k
高频率,使用小根堆的话,当堆中元素大于k
个时就可以直接将出现频率最小的弹出堆中,便于维护更新。
最后将堆中元素倒序输出即可
struct compare{bool operator()(const pair<int,int> lhs,const pair<int,int> rhs){return lhs.second>rhs.second;}};vector<int> topKFrequent(vector<int>& nums, int k) {unordered_map<int,int> map;for(int i=0;i<nums.size();i++){map[nums[i]]++;}priority_queue<pair<int,int>,vector<pair<int,int>>,compare> que;for(unordered_map<int,int>::iterator it=map.begin();it!=map.end();it++){que.push(*it);if(que.size()>k){que.pop();}}vector<int> res(k);for(int i=k-1;i>=0;i--){res[i]=que.top().first;que.pop(); }return res;}
总结
今天的题目普遍比较难,大家下去一定要自己敲一下感受感受。
相关文章:
【算法day10】栈与队列:拓展与应用
题目引用 逆波兰表达式求值滑动窗口最大值前k个高频元素 1.逆波兰表达式求值 给你一个字符串数组 tokens ,表示一个根据 逆波兰表示法 表示的算术表达式。 请你计算该表达式。返回一个表示表达式值的整数。 注意: 有效的算符为 ‘’、‘-’、‘*’ 和…...
爆肝Android JNI - 延展Android蓝牙JNI学习
零. 前言 由于Bluedroid的介绍文档有限,以及对Android的一些基本的知识需要了(Android 四大组件/AIDL/Framework/Binder机制/JNI/HIDL等),加上需要掌握的语言包括Java/C/C++等,加上网络上其实没有一个完整的介绍Bluedroid系列的文档,所以不管是蓝牙初学者还是蓝牙从业人员…...
总篇:Python3+Request+Pytest+Allure+Jenkins接口自动化框架设计思路
1、技术选型 Python3 Python 是一种广泛使用的高级编程语言,具有简洁、易读、易维护的特点。 Python 拥有丰富的第三方库,可以方便地进行接口测试的开发。 Request Request 是一个强大的 HTTP 库,用于发送 HTTP 请求和处理响应。 Request 支持多种 HTTP 方法,如 GET、P…...
Java的Map介绍以及常见方法和三种遍历方式
Java的Map介绍以及常见方法和三种遍历方式 1 Java 中的 Map 介绍 在 Java 中,Map 是一个接口,它提供了一种存储键值对(key-value pairs)的方式。每个键(key)都关联着一个值(value)…...
C/C++基础知识复习(39)
1) 什么是封装性?C中如何实现封装? 封装性(Encapsulation)是面向对象编程中的一个重要概念,它指的是将对象的状态(数据)和行为(方法)绑定在一起,并且通过访问…...

自建服务器,数据安全有保障
在远程桌面工具的选择上,向日葵和TeamViewer功能强大,但都存在收费昂贵、依赖第三方服务器、数据隐私难以完全掌控等问题。相比之下,RustDesk 凭借开源免费、自建服务的特性脱颖而出!用户可以在自己的服务器上部署RustDesk服务端&…...

CCF-GESP 编程能力认证 C++ 七级 2024年9月份判断题详细解析
链接:CCF-GESP 编程能力认证 C 七级 2024年9月份选择题详细解析-CSDN博客 目录 第 1 题 第 2 题 第 3 题 第 4 题 第 5 题 第 6 题 第 7 题 第 8 题 第 9 题 第 10 题 第 1 题 表达式 a << 1 的结果为 a(错误) 【a是字符常…...

使用Vue3+Echarts实现加载中国地图,点击省份地图下钻(完整教程)
一. 前言 在众多 ECharts 图表类型中,开发者始终绕不开的有各种各样的地图开发,关于地图开发,可能比其他图表相对繁琐一些,其实说简单也简单,说复杂也复杂,其中不乏有层级地图、3D 地图等,感觉…...

NUMA-非统一内存访问架构
NUMA(Non-Uniform Memory Access) 是一种计算机内存架构,主要用于多处理器系统。NUMA架构中的每个处理器都连接到自己的本地内存,并且可以访问其他处理器的内存,但访问其他处理器的内存速度较慢。 内核通过调度优化进…...

初识交换机和路由器
目录 初识交换机和路由器交换机路由器主要区别工作流程如果是交换机:如果是路由器 初识交换机和路由器 左为路由器,右为交换机 交换机 交换机的前身是集线器,集线器是物理层的设备,有很多接口,当一台计算机A想发消息…...
SQL面试题——滴滴SQL面试题 取出累计值与1000差值最小的记录
滴滴SQL面试题 取出累计值与1000差值最小的记录 今天的题目来自滴滴出行 已知有表cost_detail包含id和money两列,id为自增,请累加计算money值,并求出累加值与1000差值最小的记录。 +-----+--------+ | id | money | +-----+--------+ | 1 | 200 | | 2 | 300 …...

openEuler 22.03 使用cephadm安装部署ceph集群
目录 目的步骤规格步骤ceph部署前准备工作安装部署ceph集群ceph集群添加node与osdceph集群一些操作组件服务操作集群进程操作 目的 使用ceph官网的cephadm无法正常安装,会报错ERROR: Distro openeuler version 22.03 not supported 在openEuler上实现以cephadm安装部…...

C++哈希(一)
1.底层结构 顺序结构以及平衡中,元素关键码与其存储位置之间没有相对应的关系,因此在查找一个元素时,要经过关键码的多次比较。顺序查找的时间复杂度为O(N)。 理想的搜索方法:可以不经过比较,依次直接从表中直接搜索…...

阿拉丁论文助手:一键点亮学术之路
在学术研究的海洋中,每一位学者都渴望拥有一盏能够照亮前行道路的神灯。阿拉丁论文助手,正是这样一盏神奇的灯,它以其先进的人工智能技术和丰富的学术资源,为学者们的学术写作提供了全方位的支持。 一、阿拉丁论文助手简介 阿拉丁…...

视频码率到底是什么?详细说明
视频码率(Video Bitrate)是指在单位时间内(通常是每秒)传输或处理的视频数据量,用比特(bit)表示。它通常用来衡量视频文件的压缩程度和质量,码率越高,视频质量越好&#…...

嵌入式学习(17)-stm32F407串口使用注意事项
一、概述 配置串口时串口的接收一直不好使,对比例程发现了问题: 在网上也找了一些资料供参考“STM32F4的串口RX引脚不能被设置为输入是因为串口的接收(RX)功能是由硬件电路实现的,无法通过软件配置来控制。串口接收功…...
汽车48V电气系统
汽车48V电气系统 汽车48V电气系统汽车48V电气系统设计汽车48V电气系统测试汽车48V系统是48V供电和12V供电共存的么?48V供电系统是如何与12V供电系统共存的?48V电气系统测试的难点有哪些?在汽车48V电气系统通信测试中,如何向12V的控制器和48V的控制器供电?汽车48V电气系统通…...

【人工智能基础05】决策树模型习题
文章目录 1. 归一化对决策树的影响2. 选择决策树模型3. 决策树计算4. 基尼系数的优势5. 在叶子上使用线性模型的优缺点 1. 归一化对决策树的影响 题目:对于一些机器学习模型(例如,神经网络),对特征进行归一化(normaliz…...

rockit 学习、开发笔记(六)(VENC)
前言 上节我们讲到了VDEC解码模块,那当然少不了VENC编码模块了,一般有编解码的需求都是为了压缩视频的大小,方便减少传输所占用的带宽。 概述 VENC 模块,即视频编码模块。本模块支持多路实时编码,且每路编码独立&am…...
spring技术点
引入对象 Autowired 和 Resource的区别 Autowired 和 Resource的区别 valid 参数校验 jarkata进行SpringMVC校验 常规当前进行校验的配置操作,参考文档如下进行操作。 SpringMVC校验注解不生效 List类型参数校验 由于list类型默认不能进行标注校验实现&#x…...

Linux 文件类型,目录与路径,文件与目录管理
文件类型 后面的字符表示文件类型标志 普通文件:-(纯文本文件,二进制文件,数据格式文件) 如文本文件、图片、程序文件等。 目录文件:d(directory) 用来存放其他文件或子目录。 设备…...

shell脚本--常见案例
1、自动备份文件或目录 2、批量重命名文件 3、查找并删除指定名称的文件: 4、批量删除文件 5、查找并替换文件内容 6、批量创建文件 7、创建文件夹并移动文件 8、在文件夹中查找文件...
PHP和Node.js哪个更爽?
先说结论,rust完胜。 php:laravel,swoole,webman,最开始在苏宁的时候写了几年php,当时觉得php真的是世界上最好的语言,因为当初活在舒适圈里,不愿意跳出来,就好比当初活在…...
java 实现excel文件转pdf | 无水印 | 无限制
文章目录 目录 文章目录 前言 1.项目远程仓库配置 2.pom文件引入相关依赖 3.代码破解 二、Excel转PDF 1.代码实现 2.Aspose.License.xml 授权文件 总结 前言 java处理excel转pdf一直没找到什么好用的免费jar包工具,自己手写的难度,恐怕高级程序员花费一年的事件,也…...
连锁超市冷库节能解决方案:如何实现超市降本增效
在连锁超市冷库运营中,高能耗、设备损耗快、人工管理低效等问题长期困扰企业。御控冷库节能解决方案通过智能控制化霜、按需化霜、实时监控、故障诊断、自动预警、远程控制开关六大核心技术,实现年省电费15%-60%,且不改动原有装备、安装快捷、…...

CentOS下的分布式内存计算Spark环境部署
一、Spark 核心架构与应用场景 1.1 分布式计算引擎的核心优势 Spark 是基于内存的分布式计算框架,相比 MapReduce 具有以下核心优势: 内存计算:数据可常驻内存,迭代计算性能提升 10-100 倍(文档段落:3-79…...

dedecms 织梦自定义表单留言增加ajax验证码功能
增加ajax功能模块,用户不点击提交按钮,只要输入框失去焦点,就会提前提示验证码是否正确。 一,模板上增加验证码 <input name"vdcode"id"vdcode" placeholder"请输入验证码" type"text&quo…...

【CSS position 属性】static、relative、fixed、absolute 、sticky详细介绍,多层嵌套定位示例
文章目录 ★ position 的五种类型及基本用法 ★ 一、position 属性概述 二、position 的五种类型详解(初学者版) 1. static(默认值) 2. relative(相对定位) 3. absolute(绝对定位) 4. fixed(固定定位) 5. sticky(粘性定位) 三、定位元素的层级关系(z-i…...
工程地质软件市场:发展现状、趋势与策略建议
一、引言 在工程建设领域,准确把握地质条件是确保项目顺利推进和安全运营的关键。工程地质软件作为处理、分析、模拟和展示工程地质数据的重要工具,正发挥着日益重要的作用。它凭借强大的数据处理能力、三维建模功能、空间分析工具和可视化展示手段&…...
Nginx server_name 配置说明
Nginx 是一个高性能的反向代理和负载均衡服务器,其核心配置之一是 server 块中的 server_name 指令。server_name 决定了 Nginx 如何根据客户端请求的 Host 头匹配对应的虚拟主机(Virtual Host)。 1. 简介 Nginx 使用 server_name 指令来确定…...