【算法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…...

地震勘探——干扰波识别、井中地震时距曲线特点
目录 干扰波识别反射波地震勘探的干扰波 井中地震时距曲线特点 干扰波识别 有效波:可以用来解决所提出的地质任务的波;干扰波:所有妨碍辨认、追踪有效波的其他波。 地震勘探中,有效波和干扰波是相对的。例如,在反射波…...
测试markdown--肇兴
day1: 1、去程:7:04 --11:32高铁 高铁右转上售票大厅2楼,穿过候车厅下一楼,上大巴车 ¥10/人 **2、到达:**12点多到达寨子,买门票,美团/抖音:¥78人 3、中饭&a…...
python爬虫:Newspaper3k 的详细使用(好用的新闻网站文章抓取和解析的Python库)
更多内容请见: 爬虫和逆向教程-专栏介绍和目录 文章目录 一、Newspaper3k 概述1.1 Newspaper3k 介绍1.2 主要功能1.3 典型应用场景1.4 安装二、基本用法2.2 提取单篇文章的内容2.2 处理多篇文档三、高级选项3.1 自定义配置3.2 分析文章情感四、实战案例4.1 构建新闻摘要聚合器…...

《基于Apache Flink的流处理》笔记
思维导图 1-3 章 4-7章 8-11 章 参考资料 源码: https://github.com/streaming-with-flink 博客 https://flink.apache.org/bloghttps://www.ververica.com/blog 聚会及会议 https://flink-forward.orghttps://www.meetup.com/topics/apache-flink https://n…...
关于 WASM:1. WASM 基础原理
一、WASM 简介 1.1 WebAssembly 是什么? WebAssembly(WASM) 是一种能在现代浏览器中高效运行的二进制指令格式,它不是传统的编程语言,而是一种 低级字节码格式,可由高级语言(如 C、C、Rust&am…...
全面解析各类VPN技术:GRE、IPsec、L2TP、SSL与MPLS VPN对比
目录 引言 VPN技术概述 GRE VPN 3.1 GRE封装结构 3.2 GRE的应用场景 GRE over IPsec 4.1 GRE over IPsec封装结构 4.2 为什么使用GRE over IPsec? IPsec VPN 5.1 IPsec传输模式(Transport Mode) 5.2 IPsec隧道模式(Tunne…...

用机器学习破解新能源领域的“弃风”难题
音乐发烧友深有体会,玩音乐的本质就是玩电网。火电声音偏暖,水电偏冷,风电偏空旷。至于太阳能发的电,则略显朦胧和单薄。 不知你是否有感觉,近两年家里的音响声音越来越冷,听起来越来越单薄? —…...

人机融合智能 | “人智交互”跨学科新领域
本文系统地提出基于“以人为中心AI(HCAI)”理念的人-人工智能交互(人智交互)这一跨学科新领域及框架,定义人智交互领域的理念、基本理论和关键问题、方法、开发流程和参与团队等,阐述提出人智交互新领域的意义。然后,提出人智交互研究的三种新范式取向以及它们的意义。最后,总结…...

AI+无人机如何守护濒危物种?YOLOv8实现95%精准识别
【导读】 野生动物监测在理解和保护生态系统中发挥着至关重要的作用。然而,传统的野生动物观察方法往往耗时耗力、成本高昂且范围有限。无人机的出现为野生动物监测提供了有前景的替代方案,能够实现大范围覆盖并远程采集数据。尽管具备这些优势…...
苹果AI眼镜:从“工具”到“社交姿态”的范式革命——重新定义AI交互入口的未来机会
在2025年的AI硬件浪潮中,苹果AI眼镜(Apple Glasses)正在引发一场关于“人机交互形态”的深度思考。它并非简单地替代AirPods或Apple Watch,而是开辟了一个全新的、日常可接受的AI入口。其核心价值不在于功能的堆叠,而在于如何通过形态设计打破社交壁垒,成为用户“全天佩戴…...