[代码随想录11]栈和队列的应用,逆波兰表达式求值 、滑动窗口最大值、前 K 个高频元素
前言
这几个题目都是栈和队列的高频面试题目,主要是考察思路和coding能力,在前面几道题目的基础上进行延伸的。同时还有优先级队列和双端队列的用法
题目链接
150. 逆波兰表达式求值 - 力扣(LeetCode)
239. 滑动窗口最大值 - 力扣(LeetCode)
一、逆波兰表达式求值
说点白话:我们好奇计算器是怎么处理运算的不?我们会在编译原理这门课程中学到,逆波兰表达式,俗称后缀表达式,具体来说就是,计算机并不知道计算逻辑的优先级(括号的优先级),但是他能找到一个括号最先匹配的,这样我们就会花了很大的时间去遍历查询括号,还有运算符的优先级问题,我们都需要考虑,有什么方法可以跳过这些呢?就是后缀表达式,我们让符号去匹配他的计算数值,同时利用栈来对符号的优先级进行排序,这样两个问题都能得到解决,足以可见逆波兰表达式(后缀表达式的腻害之处)。
tips:注意除法运算和减法的顺序第一次写错了,哈哈哈
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 nums1=st.top();st.pop();long long nums2=st.top();st.pop();if(tokens[i]=="+")st.push(nums1+nums2);if(tokens[i]=="-")st.push(nums2-nums1);if(tokens[i]=="*")st.push(nums1*nums2);if(tokens[i]=="/")st.push(nums2/nums1);}else{st.push(stoll(tokens[i]));}}return st.top();}
};
二、滑动窗口求最大值
思路:借助deque双端队列去实现这个题目比较简单一点,同时保持队列是递减的就行。
vector<int> maxSlidingWindow(vector<int>& nums, int k) {if(nums.size() == 0 || k == 0) return {};deque<int> deque;vector<int> res(nums.size() - k + 1);for(int j = 0, i = 1 - k; j < nums.size(); i++, j++) {// 删除 deque 中对应的 nums[i-1]if(i > 0 && deque.front() == nums[i - 1])deque.pop_front();// 保持 deque 递减while(!deque.empty() && deque.back() < nums[j])deque.pop_back();deque.push_back(nums[j]);if(i >= 0)res[i] = deque.front();}return res;}
三、前K个高频元素的值
使用优先级队列,哈希表统计数据,压入数据,然后遍历出数据。
unordered_map<int, int> hmap;priority_queue<pair<int,int>> pq;vector<int> res;for (int i : nums)hmap[i]++; //使用哈希表统计个数for (auto iter : hmap)pq.emplace(iter.second,iter.first); //压入优先级队列for (int i = 0; i < k; i++) //遍历k次找到前k个最大次数对应的值{ res.push_back(pq.top().second);pq.pop();}return res;相关文章:
[代码随想录11]栈和队列的应用,逆波兰表达式求值 、滑动窗口最大值、前 K 个高频元素
前言 这几个题目都是栈和队列的高频面试题目,主要是考察思路和coding能力,在前面几道题目的基础上进行延伸的。同时还有优先级队列和双端队列的用法 题目链接 150. 逆波兰表达式求值 - 力扣(LeetCode) 239. 滑动窗口最大值 - 力…...
认证插件介绍
本文档是针对 UOS 登录器插件给出开发指南,目的是为了让开发人员了解如何在 UOS 登录器上增加一种自定义认证方式,对插件接口做了详细说明以及实战练习。 文章目录 一、认证插件可以做什么?二、认证流程三、术语说明四、安全性五、可靠性六、…...
ASP.NET Core8.0学习笔记(二十四)——EF Core级联插入与删除
一、EF Core导航关系操作——级联插入 1.级联插入:在含有导航属性的实体(主体实体)中可以对实体进行级联插入。即在创建主体实体时直接把依赖实体进行赋值,此时只需要执行一次插入操作即可将主体实体与依赖实体同时入库。同时&am…...
Docker打包SpringBoot项目
一、项目打成jar包 在进行docker打包之前,先确定一下,项目能够正常的打成JAR包,并且启动之后能够正常的访问。这一步看似是可有可无,但是能避免后期的一些无厘头问题。 二、Dockerfile 项目打包成功之后,需要编写Doc…...
【Linux】WSL:Win运行Linux
WSL2(Windows Subsystem for Linux 2) 是 Microsoft 开发的技术,可在 Windows 系统上运行完整的 Linux 发行版环境。以下是详细的配置教程。 安装与配置 启用 WSL 功能 打开“开始”菜单,搜索 PowerShell,以 管理员身…...
js循环导出多个word表格文档
文章目录 js循环导出多个word表格文档一、文档模板编辑二、安装依赖三、创建导出工具类exportWord.js四、调用五、效果图js循环导出多个word表格文档 结果案例: 一、文档模板编辑 二、安装依赖 // 实现word下载的主要依赖 npm install docxtemplater pizzip --save// 文件操…...
Spring Boot 日志 配置 SLF4J 和 Logback
前言 在开发 Java 应用时,日志记录是不可或缺的一部分。日志可以记录应用的运行状态、错误信息和调试信息,帮助开发者快速定位和解决问题。Spring Boot 项目默认集成了 SLF4J 和 Logback,使得日志配置变得简单而灵活。本文将详细介绍如何在 …...
企业级包管理器:专栏概述 (1)
在当今的前端开发领域,包管理器已经成为了每一位开发者不可或缺的工具。它们就像一个个神奇的工具箱,里面装满了各种各样的工具(即软件包),帮助我们快速搭建项目、实现功能,极大地提高了开发效率。接下来&a…...
【动手学电机驱动】STM32-MBD(1)安装 STM32 硬件支持包
STM32-MBD(1)安装 STM32 硬件支持包 【动手学电机驱动】STM32-MBD(1)安装 STM32 硬件支持包 1. 必须的软硬件条件2. 嵌入式硬件支持包2.1 Embedded Coder2.2 嵌入式硬件支持包2.3 Embedded Coder Support Package for STMicroelec…...
书后习题答案:《Python程序设计基础(第2版)》,电子工业出版社,2020.01
【持续更新】 第3章 from math import *x1 float(input("请输入x1: ")) # print(x1) x2 float(input("请输入x2: ")) y1 float(input("请输入y1: ")) y2 float(input("请输入y2: "))dis sqrt(pow(x1 - x2, 2) pow(y1 - y2, 2))…...
Qt之第三方库QXlsx使用(三)
Qt开发 系列文章 - QXlsx(三) 目录 前言 一、Qt开源库 二、QXlsx 1.QXlsx介绍 2.QXlsx下载 3.QXlsx移植 4.修改项目文件.pro 三、使用技巧 1.添加头文件 2.写入数据 3.读出数据 总结 前言 Qt第三方控件库是指非Qt官方提供的、用于扩展Qt应用…...
Python通过global实现多文件共享全局参数,方法
Python通过global实现多文件共享全局参数 global关键字,全局变量 基础用法 这种用法,不能在其他的py文件中使用, x 6 def func():global x #定义外部的xx 10 func() print (x) #输出10共享参数 新建glo.py文件(全局变量文件)…...
DevOps工程技术价值流:项目构建工具的选择与实践
在快速迭代的软件工程领域,项目构建工具扮演着举足轻重的角色。它们不仅自动化了构建、测试、打包和部署等关键环节,还显著提升了开发效率和质量。本文将深入探讨后端常用的Maven和Gradle,以及前端不可或缺的NPM,并重点对比Maven与…...
【数据库】复习
数据库期中复习——概念填空_在修改数据结构时,为了保证数据库的数据独立性-CSDN博客 选择题 关系数据理论-数据库习题_数据库关系理论考题-CSDN博客 关系、关系模式、关系模型区别和联系 关系:元组的集合,一张表 关系模式:关系的描述 R(…...
CorsConfig前后端数据跨域连接,IDEA右侧Maven窗口消失
前后端数据跨域连接(分页查询并显示) 一、后端添加分页查询 分页查询核心就是:每页需要显示多少条记录(pageSize),当前查看第几页(pageNum);MySQL提供了分页函数limit m,n select * from table limit (pageNum-1)*pageSize, pa…...
Python微博动态爬虫
本文是刘金路的《语言数据获取与分析基础》第十章的扩展,详细解释了如何利用Python进行微博爬虫,爬虫内容包括微博指定帖子的一级评论、评论时间、用户名、id、地区、点赞数。 整个过程十分明了,就是用户利用代码模拟Ajax请求,发…...
【设计模式】单例模式 在java中的应用
文章目录 引言什么是单例模式单例模式的应用场景单例模式的优缺点优点缺点 单例模式的基本实现饿汉式单例模式懒汉式单例模式双重检查锁定静态内部类枚举单例 单例模式的线程安全问题多线程环境下的单例模式线程安全的实现方式1. **懒汉式单例模式(线程不安全&#…...
burp suite 8
声明! 学习视频来自B站up主 **泷羽sec** 有兴趣的师傅可以关注一下,如涉及侵权马上删除文章,笔记只是方便各位师傅的学习和探讨,文章所提到的网站以及内容,只做学习交流,其他均与本人以及泷羽sec团队无关&a…...
为什么在Java中super与this不能共存于子类构造器中,其中this起什么作用
在 Java 中,super 和 this 是两个关键字,它们在子类的构造器中有特定的用途和限制。 super 关键字: super 用于从父类(超类)访问成员(属性和方法)或者调用父类的构造方法。 在子类的构造器中&…...
Hypothesis:高效的 Python 测试工具
简介:Hypothesis 是一个强大的 Python 测试库,旨在自动生成各种测试案例,以帮助开发者发现潜在的边界问题和隐藏的错误。通过对输入数据进行智能化的探索,Hypothesis 能够为测试提供更全面的覆盖,避免遗漏一些极端或不…...
基于FPGA的PID算法学习———实现PID比例控制算法
基于FPGA的PID算法学习 前言一、PID算法分析二、PID仿真分析1. PID代码2.PI代码3.P代码4.顶层5.测试文件6.仿真波形 总结 前言 学习内容:参考网站: PID算法控制 PID即:Proportional(比例)、Integral(积分&…...
Java - Mysql数据类型对应
Mysql数据类型java数据类型备注整型INT/INTEGERint / java.lang.Integer–BIGINTlong/java.lang.Long–––浮点型FLOATfloat/java.lang.FloatDOUBLEdouble/java.lang.Double–DECIMAL/NUMERICjava.math.BigDecimal字符串型CHARjava.lang.String固定长度字符串VARCHARjava.lang…...
Nuxt.js 中的路由配置详解
Nuxt.js 通过其内置的路由系统简化了应用的路由配置,使得开发者可以轻松地管理页面导航和 URL 结构。路由配置主要涉及页面组件的组织、动态路由的设置以及路由元信息的配置。 自动路由生成 Nuxt.js 会根据 pages 目录下的文件结构自动生成路由配置。每个文件都会对…...
【论文笔记】若干矿井粉尘检测算法概述
总的来说,传统机器学习、传统机器学习与深度学习的结合、LSTM等算法所需要的数据集来源于矿井传感器测量的粉尘浓度,通过建立回归模型来预测未来矿井的粉尘浓度。传统机器学习算法性能易受数据中极端值的影响。YOLO等计算机视觉算法所需要的数据集来源于…...
python爬虫:Newspaper3k 的详细使用(好用的新闻网站文章抓取和解析的Python库)
更多内容请见: 爬虫和逆向教程-专栏介绍和目录 文章目录 一、Newspaper3k 概述1.1 Newspaper3k 介绍1.2 主要功能1.3 典型应用场景1.4 安装二、基本用法2.2 提取单篇文章的内容2.2 处理多篇文档三、高级选项3.1 自定义配置3.2 分析文章情感四、实战案例4.1 构建新闻摘要聚合器…...
微服务商城-商品微服务
数据表 CREATE TABLE product (id bigint(20) UNSIGNED NOT NULL AUTO_INCREMENT COMMENT 商品id,cateid smallint(6) UNSIGNED NOT NULL DEFAULT 0 COMMENT 类别Id,name varchar(100) NOT NULL DEFAULT COMMENT 商品名称,subtitle varchar(200) NOT NULL DEFAULT COMMENT 商…...
JavaScript基础-API 和 Web API
在学习JavaScript的过程中,理解API(应用程序接口)和Web API的概念及其应用是非常重要的。这些工具极大地扩展了JavaScript的功能,使得开发者能够创建出功能丰富、交互性强的Web应用程序。本文将深入探讨JavaScript中的API与Web AP…...
三分算法与DeepSeek辅助证明是单峰函数
前置 单峰函数有唯一的最大值,最大值左侧的数值严格单调递增,最大值右侧的数值严格单调递减。 单谷函数有唯一的最小值,最小值左侧的数值严格单调递减,最小值右侧的数值严格单调递增。 三分的本质 三分和二分一样都是通过不断缩…...
Linux系统部署KES
1、安装准备 1.版本说明V008R006C009B0014 V008:是version产品的大版本。 R006:是release产品特性版本。 C009:是通用版 B0014:是build开发过程中的构建版本2.硬件要求 #安全版和企业版 内存:1GB 以上 硬盘…...
如何应对敏捷转型中的团队阻力
应对敏捷转型中的团队阻力需要明确沟通敏捷转型目的、提升团队参与感、提供充分的培训与支持、逐步推进敏捷实践、建立清晰的奖励和反馈机制。其中,明确沟通敏捷转型目的尤为关键,团队成员只有清晰理解转型背后的原因和利益,才能降低对变化的…...
