当前位置: 首页 > news >正文

[LeetCode]day33 150.逆波兰式求表达值 + 239.滑动窗口最大值

逆波兰式求表达值

题目链接

题目描述

给你一个字符串数组 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

提示:

1 <= tokens.length <= 104
tokens[i] 是一个算符(“+”、“-”、“*” 或 “/”),或是在范围 [-200, 200] 内的一个整数

题解

请添加图片描述

代码书写
class Solution {
public:int evalRPN(vector<string>& tokens) {stack<int>s;for(int i=0;i<tokens.size();i++){if(tokens[i]=="+"||tokens[i]=="-"||tokens[i]=="*"||tokens[i]=="/"){int num1,num2;num2 = s.top();s.pop();num1 = s.top();s.pop();if(tokens[i]=="+") s.push(num1+num2);else if(tokens[i]=="-") s.push(num1-num2);else if(tokens[i]=="*") s.push(num1*num2);else if(tokens[i]=="/") s.push(num1/num2);}else{//注意把字符串转换成数组s.push(stol(tokens[i]));}}int re = s.top();return re;}
};

239.滑动窗口最大值

题目链接

题目描述

给你一个整数数组 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]

提示:

1 <= nums.length <= 10^5
-104 <= nums[i] <= 10^4
1 <= k <= nums.length

解题

解法一:暴力解法

请添加图片描述

class Solution {
public:vector<int> maxSlidingWindow(vector<int>& nums, int k) {vector<int>re;for(int i=0;i<=nums.size()-k;i++){auto begin = nums.begin()+i;auto end = nums.begin()+i+k;auto max = max_element(begin,end);re.push_back(*max);}return re;}
};

喜提超时
在这里插入图片描述
尝试用条件进行剪枝,省去一些不必要的判断,比如最大值还没有被移出滑动窗口并且新加进来的元素小于最大值时就没有必要调用寻找最大值的函数

class Solution {
public:int findMaxIndex(vector<int>&nums,int begin,int end){int max = nums[begin];int re=begin;for(int i = begin;i<end;i++){if(nums[i]>max){max = nums[i];re = i;}}return re;}vector<int> maxSlidingWindow(vector<int>& nums, int k) {vector<int>re;if (nums.empty() || k <= 0) return re;int index= findMaxIndex(nums,0,k);int max= nums[index];for(int i=0;i<=nums.size()-k;i++){if((i>0 && index==i-1)||nums[i+k-1]>nums[index]){index = findMaxIndex(nums,i,i+k);}re.push_back(nums[index]);}return re;}
};

在这里插入图片描述
稍微好了一些 这次过到47个用例

解法二.单调队列

我们使用一个队列,在这个队列中,只存放可能成为最大值的数字。
为了避免排序算法带来的时间复杂度,我们不排序,怎么获得当前窗口中最大的数字呢?
我们希望队列的第一个元素就是当前窗口中最大的数字,这样就能直接弹出来。
所以队列中一定呈现非增的特征

所以在进行push()时,如果发现队列末尾的元素比即将入队的元素小,就要把该元素pop出去;

注意这个队列实现的底层是deque,则元素可以从两头出
在进行pop()操作时,可能会出现要弹出滑动窗口的那个元素在更大的元素push进来时,就被弹出了,就不用真的进行pop()。需要真的进行pop()的情况为滑动窗口弹出的元素恰好为原来的最大元素且新加入滑动窗口的元素没有原来的大
如:请添加图片描述

举个栗子:
请添加图片描述

class MyQueue{public:deque<int>q;void push(int value){while(!q.empty()&&value>q.back()){q.pop_back();}q.push_back(value);}void pop(int value){if(!q.empty()&&value==q.front()){q.pop_front();}}int getMax(){return q.front();}
};
class Solution {
public:vector<int> maxSlidingWindow(vector<int>& nums, int k) {vector<int>re;MyQueue q;for(int i =0;i<k;i++){q.push(nums[i]);}re.push_back(q.getMax());for(int i=k;i<nums.size();i++){q.push(nums[i]);q.pop(nums[i-k]);re.push_back(q.getMax());}return re;}
};

相关文章:

[LeetCode]day33 150.逆波兰式求表达值 + 239.滑动窗口最大值

逆波兰式求表达值 题目链接 题目描述 给你一个字符串数组 tokens &#xff0c;表示一个根据 逆波兰表示法 表示的算术表达式。 请你计算该表达式。返回一个表示表达式值的整数。 注意&#xff1a; 有效的算符为 ‘’、‘-’、‘*’ 和 ‘/’ 。 每个操作数&#xff08;运…...

【银河麒麟高级服务器操作系统实际案例分享】数据库资源重启现象分析及处理全过程

更多银河麒麟操作系统产品及技术讨论&#xff0c;欢迎加入银河麒麟操作系统官方论坛 https://forum.kylinos.cn 了解更多银河麒麟操作系统全新产品&#xff0c;请点击访问 麒麟软件产品专区&#xff1a;https://product.kylinos.cn 开发者专区&#xff1a;https://developer…...

C#中泛型的协变和逆变

协变&#xff1a; 在泛型接口中&#xff0c;使用out关键字可以声明协变。这意味着接口的泛型参数只能作为返回类型出现&#xff0c;而不能作为方法的参数类型。 示例&#xff1a;泛型接口中的协变 假设我们有一个基类Animal和一个派生类Dog&#xff1a; csharp复制 public…...

【JavaScript】《JavaScript高级程序设计 (第4版) 》笔记-附录B-严格模式

附录B、严格模式 严格模式 ECMAScript 5 首次引入严格模式的概念。严格模式用于选择以更严格的条件检查 JavaScript 代码错误&#xff0c;可以应用到全局&#xff0c;也可以应用到函数内部。严格模式的好处是可以提早发现错误&#xff0c;因此可以捕获某些 ECMAScript 问题导致…...

跨平台 C++ 程序崩溃调试与 Dump 文件分析

前言 C 程序在运行时可能会由于 空指针访问、数组越界、非法内存访问、栈溢出 等原因崩溃。为了分析崩溃原因&#xff0c;我们通常会生成 Dump 文件&#xff08;Windows 的 .dmp&#xff0c;Linux 的 core&#xff0c;macOS 的 .crash&#xff09;&#xff0c;然后用调试工具分…...

缺陷VS质量:为何软件缺陷是质量属性的致命对立面?

为何说缺陷是质量的对立面&#xff1f; 核心逻辑&#xff1a;软件质量的定义是“满足用户需求的程度”&#xff0c;而缺陷会直接破坏这种满足关系。 对立性&#xff1a;缺陷的存在意味着软件偏离了预期行为&#xff08;如功能错误、性能不足、安全性漏洞等&#xff09;&#…...

伍[5],伺服电机,电流环,速度环,位置环

电流环、速度环和位置环是电机控制系统中常见的三个闭环控制环节,通常采用嵌套结构(内环→外环:电流环→速度环→位置环),各自负责不同层级的控制目标。以下是它们的详细说明及相互关系: 1. 电流环(最内环) 作用:控制电机的电流,间接控制输出转矩(τ=Kt⋅Iτ=Kt​⋅…...

RuntimeError: CUDA error: device-side assert triggered

RuntimeError: CUDA error: device-side assert triggered 欢迎来到英杰社区&#xff0c;这里是博主英杰https://bbs.csdn.net/topics/617804998 原因&#xff1a; cuda运行可能是异步的&#xff08;asynchronously&#xff09;&#xff0c;因此报错信息中提示的位置可能不准确…...

清华大学Deepseek第六版AIGC发展研究3.0(共186页,附PDF下载)

人工智能生成内容&#xff08;AIGC&#xff09;正以前所未有的速度改变我们的生活。 2024年底&#xff0c;清华大学新闻与传播学院与人工智能学院联合发布了《AIGC发展研究3.0版》&#xff0c;这份报告系统梳理了AIGC技术的突破性进展、应用场景及社会影响&#xff0c;并展望了…...

SpringBoot生成唯一ID的方式

1.为什么要生成唯一ID&#xff1f; 数据唯一性&#xff1a;每个记录都需要有一个独一无二的标识符来确保数据的唯一性。这可以避免重复的数据行&#xff0c;并有助于准确地查询、更新或删除特定的记录。 数据完整性&#xff1a;通过使用唯一ID&#xff0c;可以保证数据库中的数…...

通俗易懂的分类算法之K近邻详解

通俗易懂的分类算法之K近邻详解 用最通俗的语言和例子&#xff0c;来彻底理解 K近邻&#xff08;K-Nearest Neighbors&#xff0c;简称 KNN&#xff09; 这个分类算法。不用担心复杂的数学公式&#xff0c;我会用生活中的例子来解释&#xff0c;保证你一听就懂&#xff01; 1.…...

CSDN markdown 操作指令等

CSDN markdown 操作指令等 页内跳转 [内容](#1) <div id"1"> </div>...

【linux】文件与目录命令 - uniq

文章目录 1. 基本用法2. 常用参数3. 用法举例4. 注意事项 uniq 命令用于过滤文本文件中相邻的重复行&#xff0c;并支持统计重复次数或仅保留唯一行。它通常与 sort 命令配合使用&#xff0c;因为 uniq 只识别相邻的重复行。 1. 基本用法 语法&#xff1a; uniq [选项] [输入…...

零信任沙箱:为网络安全筑牢“隔离墙”

在数字化浪潮汹涌澎湃的今天&#xff0c;网络安全如同一艘船在波涛汹涌的大海中航行&#xff0c;面临着重重挑战。数据泄露、恶意软件攻击、网络钓鱼等安全威胁层出不穷&#xff0c;让企业和个人用户防不胜防。而零信任沙箱&#xff0c;就像是一座坚固的“隔离墙”&#xff0c;…...

【金融量化】Ptrade中交易环境支持的业务类型

1. 普通股票买卖 • 特点&#xff1a; 普通股票买卖是最基础的交易形式&#xff0c;投资者通过买入和卖出上市公司的股票来获取收益。 ◦ 流动性高&#xff1a;股票市场交易活跃&#xff0c;买卖方便。 ◦ 收益来源多样&#xff1a;包括股价上涨的资本利得和公司分红。 ◦ 风险…...

【Java---数据结构】链表 LinkedList

1. 链表的概念 链表用于存储一系列元素&#xff0c;由一系列节点组成&#xff0c;每个节点包含两部分&#xff1a;数据域和指针域。 数据域&#xff1a;用于存储数据元素 指针域&#xff1a;用于指向下一个节点的地址&#xff0c;通过指针将各个节点连接在一起&#xff0c;形…...

紧跟 Web3 热潮,RuleOS 如何成为行业新宠?

Web3 热潮正以汹涌之势席卷全球。从金融领域的创新应用到供应链管理的变革&#xff0c;从社交媒体的去中心化尝试到游戏产业的全新玩法探索&#xff0c;Web3 凭借其去中心化、安全性和用户赋权等特性&#xff0c;为各个行业带来了前所未有的机遇。在这股热潮中&#xff0c;Rule…...

CC++的内存管理

目录 1、C/C内存划分 C语言的动态内存管理 malloc calloc realloc free C的动态内存管理 new和delete operator new函数和operator delete函数 new和delete的原理 new T[N]原理 delete[]的原理 1、C/C内存划分 1、栈&#xff1a;存有非静态局部变量、函数参数、返回…...

Spark核心之02:RDD、算子分类、常用算子

spark内存计算框架 一、目标 深入理解RDD弹性分布式数据集底层原理掌握RDD弹性分布式数据集的常用算子操作 二、要点 ⭐️1. RDD是什么 RDD&#xff08;Resilient Distributed Dataset&#xff09;叫做**弹性分布式数据集&#xff0c;是Spark中最基本的数据抽象&#xff0c…...

【Resis实战分析】Redis问题导致页面timeout知识点分析

事故现象&#xff1a;前端页面返回timeout 事故回溯总结一句话&#xff1a; &#xff08;1&#xff09;因为大KEY调用量&#xff0c;随着白天自然流量趋势增长而增长&#xff0c;最终在业务高峰最高点期占满带宽使用100%。 &#xfeff; &#xfeff; &#xff08;2&#x…...

剑指offer20_链表中环的入口节点

链表中环的入口节点 给定一个链表&#xff0c;若其中包含环&#xff0c;则输出环的入口节点。 若其中不包含环&#xff0c;则输出null。 数据范围 节点 val 值取值范围 [ 1 , 1000 ] [1,1000] [1,1000]。 节点 val 值各不相同。 链表长度 [ 0 , 500 ] [0,500] [0,500]。 …...

1.3 VSCode安装与环境配置

进入网址Visual Studio Code - Code Editing. Redefined下载.deb文件&#xff0c;然后打开终端&#xff0c;进入下载文件夹&#xff0c;键入命令 sudo dpkg -i code_1.100.3-1748872405_amd64.deb 在终端键入命令code即启动vscode 需要安装插件列表 1.Chinese简化 2.ros …...

Cloudflare 从 Nginx 到 Pingora:性能、效率与安全的全面升级

在互联网的快速发展中&#xff0c;高性能、高效率和高安全性的网络服务成为了各大互联网基础设施提供商的核心追求。Cloudflare 作为全球领先的互联网安全和基础设施公司&#xff0c;近期做出了一个重大技术决策&#xff1a;弃用长期使用的 Nginx&#xff0c;转而采用其内部开发…...

【git】把本地更改提交远程新分支feature_g

创建并切换新分支 git checkout -b feature_g 添加并提交更改 git add . git commit -m “实现图片上传功能” 推送到远程 git push -u origin feature_g...

PL0语法,分析器实现!

简介 PL/0 是一种简单的编程语言,通常用于教学编译原理。它的语法结构清晰,功能包括常量定义、变量声明、过程(子程序)定义以及基本的控制结构(如条件语句和循环语句)。 PL/0 语法规范 PL/0 是一种教学用的小型编程语言,由 Niklaus Wirth 设计,用于展示编译原理的核…...

工业自动化时代的精准装配革新:迁移科技3D视觉系统如何重塑机器人定位装配

AI3D视觉的工业赋能者 迁移科技成立于2017年&#xff0c;作为行业领先的3D工业相机及视觉系统供应商&#xff0c;累计完成数亿元融资。其核心技术覆盖硬件设计、算法优化及软件集成&#xff0c;通过稳定、易用、高回报的AI3D视觉系统&#xff0c;为汽车、新能源、金属制造等行…...

(转)什么是DockerCompose?它有什么作用?

一、什么是DockerCompose? DockerCompose可以基于Compose文件帮我们快速的部署分布式应用&#xff0c;而无需手动一个个创建和运行容器。 Compose文件是一个文本文件&#xff0c;通过指令定义集群中的每个容器如何运行。 DockerCompose就是把DockerFile转换成指令去运行。 …...

Web 架构之 CDN 加速原理与落地实践

文章目录 一、思维导图二、正文内容&#xff08;一&#xff09;CDN 基础概念1. 定义2. 组成部分 &#xff08;二&#xff09;CDN 加速原理1. 请求路由2. 内容缓存3. 内容更新 &#xff08;三&#xff09;CDN 落地实践1. 选择 CDN 服务商2. 配置 CDN3. 集成到 Web 架构 &#xf…...

LeetCode - 199. 二叉树的右视图

题目 199. 二叉树的右视图 - 力扣&#xff08;LeetCode&#xff09; 思路 右视图是指从树的右侧看&#xff0c;对于每一层&#xff0c;只能看到该层最右边的节点。实现思路是&#xff1a; 使用深度优先搜索(DFS)按照"根-右-左"的顺序遍历树记录每个节点的深度对于…...

Fabric V2.5 通用溯源系统——增加图片上传与下载功能

fabric-trace项目在发布一年后,部署量已突破1000次,为支持更多场景,现新增支持图片信息上链,本文对图片上传、下载功能代码进行梳理,包含智能合约、后端、前端部分。 一、智能合约修改 为了增加图片信息上链溯源,需要对底层数据结构进行修改,在此对智能合约中的农产品数…...