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

算法训练营第十一天 | 20. 有效的括号、 1047. 删除字符串中的所有相邻重复项、150. 逆波兰表达式求值

目录:

  1.  力扣  20. 有效的括号
  2. 力扣  1047. 删除字符串中的所有相邻重复项
  3. 力扣  150. 逆波兰表达式求值

问题一、 20. 有效的括号

题目链接:20. 有效的括号 - 力扣(LeetCode)
思路分析:

      很多朋友刚开始接触这一类题的时候 , 可能会没有思路

       1、使用栈来解决。

       2、遍历字符串,遇到左括号(  " { " 、" [ "、" ( " ),我们将右括号压入栈中。

       3、当我们遇到右括号时,则和栈顶元素进行匹配,如果不相等则说明没有有效的括号。如果         相等,则匹配成功,将其出栈。

       4、循环结束之后,如果栈为空,则说明括号是有效的。

文章讲解/视频讲解(代码随想录):  代码随想录

问题解答:

bool isValid(string s) {stack< char >st;   //定义一个栈//要括号都匹配,说明传入的字符串一定是偶数if( s.length() %2!=0)  return false;for(int i = 0 ;i < s.length() ; i++){if( s[i]=='('){st.push( ')' );continue;}else if( s[i] == '{'){st.push( '}' );continue;}else if( s[i]== '['){st.push( ']' );continue;}//开始匹配else if( st.empty()!=true && s[i]==st.top()){st.pop();continue;} else {return false;}}if(st.empty()){return true;}return false;
}

问题二、1047. 删除字符串中的所有相邻重复项

题目链接:1047. 删除字符串中的所有相邻重复项 - 力扣(LeetCode)
思路分析:

  1. 利用栈的特性 ,用来记录字符串中已经遍历的数据
  2. for 循环遍历字符串 , 如果我们的当前字符和栈顶元素相同,则出栈,不同则将其压入栈
  3. 最后我们需要元素就是栈中的元素,但是我们需要注意的是 , 栈中元素和我们想要的顺序是相反的。
  4. 提示我们使用字符串来模拟栈的操作

文章讲解/视频讲解 (代码随想录) :  代码随想录

问题解答:

tring removeDuplicates(string s) {string ret;    //用来记录我们遍历过的数据(用字符串来模拟栈的结构)for(int i=0 ; i<s.length() ; i++ ){//每遍历一个元素都要和栈中的元素进行比较if(ret.empty() || ret.back()!=s[i]){    //不相等的情况ret.push_back(s[i]);}else {ret.erase(ret.end()-1);}}return ret;
}

问题三、150. 逆波兰表达式求值

问题链接:150. 逆波兰表达式求值 - 力扣(LeetCode)
思路分析:

  1. 还是利用栈的特性( 可以记录当前元素的前一个数据 )。
  2. 遍历字符串,将整数依次放入栈中,如果遇到有效运算符,这从栈中取出两个数据进行计算

  3. 将计算的结果再次放入栈中。

  4. 最后栈中剩余的元素,就是我们表达式的值。

  5. 这里我们想要主要的是 ,从栈中取出的两个元素  ,在进行运算的时候,是后一个元素放在前面,比如取出的数据是  a,b   。操作时应该是 b-a  |   b*a。

  6. 补充:  C++ 中  std::stoi(string to integer)将字符串转换为整数类型。

文章 | 视频讲解(代码随想录):代码随想录


问题解答:

我这里给出的过程比较冗余,大家可以改进优化一下.

class Solution {
public:void getAB(int &a,int &b){a=st.top();st.pop();b=st.top();st.pop();
}
int evalRPN(vector<string>& tokens) {//2. 遍历字符串,将整数依次放入栈中,如果遇到有效运算符,这从栈中取出两个数据进行计算//3. 将计算的结果再次放入栈中 int a=0 , b=0, temp=0;for(int i=0 ; i < tokens.size() ; i++){if( tokens[i]=="*" ){getAB(a,b);temp = a*b;st.push(temp);continue;}else if( tokens[i]=="/" ){getAB(a,b);temp=b/a;st.push(temp);continue;}else if( tokens[i]=="+" ){getAB(a,b);temp=a+b;st.push(temp);continue;}else if( tokens[i]=="-" ){getAB(a,b);temp=b-a;st.push(temp);continue;}else{st.push(std::stoi(tokens[i]) );}}return st.top();
}
private://1. 定义一个栈stack< int >st;
};

总结:

栈的应用场景

合适做一些类似于爱消除的操作,因为栈帮助我们记录了 遍历数组当前元素时候,前一个元素是什么。

相关文章:

算法训练营第十一天 | 20. 有效的括号、 1047. 删除字符串中的所有相邻重复项、150. 逆波兰表达式求值

目录&#xff1a; 力扣 20. 有效的括号力扣 1047. 删除字符串中的所有相邻重复项力扣 150. 逆波兰表达式求值 问题一、 20. 有效的括号 题目链接&#xff1a;20. 有效的括号 - 力扣&#xff08;LeetCode&#xff09; 思路分析&#xff1a; 很多朋友刚开始接触这一类题的时候…...

Python unittest单元测试框架 TestSuite测试套件

TestSuite 测试套件简介 对一个功能的验证往往是需要很多多测试用例&#xff0c;可以把测试用例集合在一起执行&#xff0c;这就产生了测试套件TestSuite 的概念&#xff0c;它是用来组装单个测试用例&#xff0c;规定用例的执行的顺序&#xff0c;而且TestSuite也可以嵌套Tes…...

FSB逮捕为乌克兰网络部队工作的俄罗斯黑客

导语 近日&#xff0c;俄罗斯联邦安全局&#xff08;FSB&#xff09;逮捕了两名涉嫌协助乌克兰网络部队对俄罗斯重要基础设施目标进行网络攻击的个人。这起事件引起了广泛关注&#xff0c;涉及到了网络安全和国际关系等多个领域。本文将为您详细介绍这一事件的背景和最新进展。…...

【PC电脑windows-学习样例tusb_serial_device-ESP32的USB模拟串口程序+VScode建立工程+usb组件添加+-基础样例学习】

【PC电脑windows-学习样例tusb_serial_device-ESP32的USB模拟串口程序-基础样例学习】 1、概述2、实验环境3-1、 物品说明3-2、所遇问题&#xff1a;ESP32 cannot open source file "tinyusb.h"或者“tinyusb.h:No such file or directory ....”3-3、解决问题&#…...

LeetCode75——Day26

文章目录 一、题目二、题解 一、题目 394. Decode String Given an encoded string, return its decoded string. The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times. Note that k is guar…...

面试算法53:二叉搜索树的下一个节点

题目 给定一棵二叉搜索树和它的一个节点p&#xff0c;请找出按中序遍历的顺序该节点p的下一个节点。假设二叉搜索树中节点的值都是唯一的。例如&#xff0c;在图8.9的二叉搜索树中&#xff0c;节点8的下一个节点是节点9&#xff0c;节点11的下一个节点是null。 分析&#xf…...

2023SHCTF web方向wp

1.ezphp 看一眼&#xff0c;你大爷&#xff0c;啥玩意都给我过滤完了。 还好下面有preg_replace()/e&#xff0c;会把replacement当作php语句执行 传参pattern.*&#xff0c; .*表示任意字符&#xff0c;code{${phpinfo()}} &#xff0c;为什么这样写&#xff0c;因为,print_…...

从物理磁盘到数据库 —— 存储IO链路访问图

原图来自&#xff1a;数据库IO链路访问图 – OracleBlog 由于很复杂&#xff0c;为了加深理解自己重新画了一次&#xff0c;另外参考其他文档补充了各部分的插图和介绍。 一、 存储服务器 1. 物理磁盘 外层的壳子称为硬盘笼 cage 2. chunklet Chunklet 是一个虚拟概念而不是实…...

基于java+springboot+vue在线选课系统

项目介绍 本系统结合计算机系统的结构、概念、模型、原理、方法&#xff0c;在计算机各种优势的情况下&#xff0c;采用JAVA语言&#xff0c;结合SpringBoot框架与Vue框架以及MYSQL数据库设计并实现的。员工管理系统主要包括个人中心、课程管理、专业管理、院系信息管理、学生…...

GO学习之 同步操作sync包

GO系列 1、GO学习之Hello World 2、GO学习之入门语法 3、GO学习之切片操作 4、GO学习之 Map 操作 5、GO学习之 结构体 操作 6、GO学习之 通道(Channel) 7、GO学习之 多线程(goroutine) 8、GO学习之 函数(Function) 9、GO学习之 接口(Interface) 10、GO学习之 网络通信(Net/Htt…...

NUUO网络摄像头(NVR)RCE漏洞复现

简介 NUUO Network Video Recorder&#xff08;NVR&#xff09;是中国台湾NUUO公司的一款网络视频记录器。 NUUO NVR视频存储管理设备的__debugging_center_utils___.php文件存在未授权远程命令执行漏洞&#xff0c;攻击者可在没有任何权限的情况下通过log参数执行任意命令。…...

一款快速获取目标网站关键信息的工具

1.摘要 今天要介绍的这款工具是一个快速收集网站信息的开源脚本, 采用Python语言编写, 该工具可以快速收集网站的页面标题、网站上次更新日期、DNS信息、子域、防火墙名称、网站使用的技术栈、证书等信息, 默认支持对验证码和JavaScript内容执行绕过操作。 2.工具安装使用 使…...

将GC编程语言引入WebAssembly的新方法

本文讨论了一种名为 WasmGC 的新方法&#xff0c;用于将垃圾收集编程语言有效地引入 WebAssembly。 WasmGC 定义了新的 GC 类型&#xff0c;例如结构和数组&#xff0c;与之前编译为线性内存的方法 (WasmMVP) 相比&#xff0c;它们可以实现更好的优化&#xff1a; 在编译时和…...

微信小程序UI自动化测试实践:Minium+PageObject

小程序架构上分为渲染层和逻辑层&#xff0c;尽管各平台的运行环境十分相似&#xff0c;但是还是有些许的区别&#xff08;如下图&#xff09;&#xff0c;比如说JavaScript 语法和 API 支持不一致&#xff0c;WXSS 渲染表现也有不同&#xff0c;所以不论是手工测试&#xff0c…...

Java零基础入门-输入与输出

哈喽&#xff0c;各位小伙伴们&#xff0c;你们好呀&#xff0c;我是喵手。 今天我要给大家分享一些自己日常学习到的一些知识点&#xff0c;并以文字的形式跟大家一起交流&#xff0c;互相学习&#xff0c;一个人虽可以走的更快&#xff0c;但一群人可以走的更远。 我是一名后…...

iOS报错命名空间“std”中的“unary_function”

刚刚将我的 Xcode 升级到 15.0&#xff0c;突然它开始在 RCT_Folly 中出现以下错误 No template named unary_function in namespace std; did you mean __unary_function?我尝试删除缓存数据和派生数据并清理构建。也尝试删除 pod 和 node_modules。但没有任何帮助。 于是我…...

Flink SQL 窗口聚合详解

1.滚动窗⼝&#xff08;TUMBLE&#xff09; **滚动窗⼝定义&#xff1a;**滚动窗⼝将每个元素指定给指定窗⼝⼤⼩的窗⼝&#xff0c;滚动窗⼝具有固定⼤⼩&#xff0c;且不重叠。 例如&#xff0c;指定⼀个⼤⼩为 5 分钟的滚动窗⼝&#xff0c;Flink 将每隔 5 分钟开启⼀个新…...

中间件redis的使用

Java中的中间件配置体现在springboot的yml配置文件中。Springboot框架支持微服务和中间件和restful api远程服务的调用。中间件是Java web系统的中间层的服务系统的调用接口。Springboot的自动装配和约定大于配置机制初始化springcontext的容器空间和注册组件。使用容器管理服务…...

Why delete[] array when deepcopying with “=“?

代码负责释放对象之前已经分配的资源&#xff0c;比如堆上的内存。在执行深拷贝之前&#xff0c;你需要确保对象不再引用之前的资源&#xff0c;以避免内存泄漏。通过删除先前的资源&#xff0c;你可以确保在进行深拷贝之前&#xff0c;已经释放了之前的资源&#xff0c;从而避…...

curl(六)DNS解析、认证、代理

一 DNS解析 ① ip协议 使用ipv4 [-4] 还是ipv6 [-6] ② --resolve 场景&#xff1a; 在不修改系统配置文件 /etc/hosts 的情况下将单个请求临时固定到 ip 地址 1、使用 * 作为通配符,这样请求中调用的所有 Host 都 会转到你指定的 ip curl https://www.wzj.com --resolv…...

第19节 Node.js Express 框架

Express 是一个为Node.js设计的web开发框架&#xff0c;它基于nodejs平台。 Express 简介 Express是一个简洁而灵活的node.js Web应用框架, 提供了一系列强大特性帮助你创建各种Web应用&#xff0c;和丰富的HTTP工具。 使用Express可以快速地搭建一个完整功能的网站。 Expre…...

《Qt C++ 与 OpenCV:解锁视频播放程序设计的奥秘》

引言:探索视频播放程序设计之旅 在当今数字化时代,多媒体应用已渗透到我们生活的方方面面,从日常的视频娱乐到专业的视频监控、视频会议系统,视频播放程序作为多媒体应用的核心组成部分,扮演着至关重要的角色。无论是在个人电脑、移动设备还是智能电视等平台上,用户都期望…...

3.3.1_1 检错编码(奇偶校验码)

从这节课开始&#xff0c;我们会探讨数据链路层的差错控制功能&#xff0c;差错控制功能的主要目标是要发现并且解决一个帧内部的位错误&#xff0c;我们需要使用特殊的编码技术去发现帧内部的位错误&#xff0c;当我们发现位错误之后&#xff0c;通常来说有两种解决方案。第一…...

iPhone密码忘记了办?iPhoneUnlocker,iPhone解锁工具Aiseesoft iPhone Unlocker 高级注册版​分享

平时用 iPhone 的时候&#xff0c;难免会碰到解锁的麻烦事。比如密码忘了、人脸识别 / 指纹识别突然不灵&#xff0c;或者买了二手 iPhone 却被原来的 iCloud 账号锁住&#xff0c;这时候就需要靠谱的解锁工具来帮忙了。Aiseesoft iPhone Unlocker 就是专门解决这些问题的软件&…...

抖音增长新引擎:品融电商,一站式全案代运营领跑者

抖音增长新引擎&#xff1a;品融电商&#xff0c;一站式全案代运营领跑者 在抖音这个日活超7亿的流量汪洋中&#xff0c;品牌如何破浪前行&#xff1f;自建团队成本高、效果难控&#xff1b;碎片化运营又难成合力——这正是许多企业面临的增长困局。品融电商以「抖音全案代运营…...

ElasticSearch搜索引擎之倒排索引及其底层算法

文章目录 一、搜索引擎1、什么是搜索引擎?2、搜索引擎的分类3、常用的搜索引擎4、搜索引擎的特点二、倒排索引1、简介2、为什么倒排索引不用B+树1.创建时间长,文件大。2.其次,树深,IO次数可怕。3.索引可能会失效。4.精准度差。三. 倒排索引四、算法1、Term Index的算法2、 …...

土地利用/土地覆盖遥感解译与基于CLUE模型未来变化情景预测;从基础到高级,涵盖ArcGIS数据处理、ENVI遥感解译与CLUE模型情景模拟等

&#x1f50d; 土地利用/土地覆盖数据是生态、环境和气象等诸多领域模型的关键输入参数。通过遥感影像解译技术&#xff0c;可以精准获取历史或当前任何一个区域的土地利用/土地覆盖情况。这些数据不仅能够用于评估区域生态环境的变化趋势&#xff0c;还能有效评价重大生态工程…...

(一)单例模式

一、前言 单例模式属于六大创建型模式,即在软件设计过程中,主要关注创建对象的结果,并不关心创建对象的过程及细节。创建型设计模式将类对象的实例化过程进行抽象化接口设计,从而隐藏了类对象的实例是如何被创建的,封装了软件系统使用的具体对象类型。 六大创建型模式包括…...

群晖NAS如何在虚拟机创建飞牛NAS

套件中心下载安装Virtual Machine Manager 创建虚拟机 配置虚拟机 飞牛官网下载 https://iso.liveupdate.fnnas.com/x86_64/trim/fnos-0.9.2-863.iso 群晖NAS如何在虚拟机创建飞牛NAS - 个人信息分享...

嵌入式常见 CPU 架构

架构类型架构厂商芯片厂商典型芯片特点与应用场景PICRISC (8/16 位)MicrochipMicrochipPIC16F877A、PIC18F4550简化指令集&#xff0c;单周期执行&#xff1b;低功耗、CIP 独立外设&#xff1b;用于家电、小电机控制、安防面板等嵌入式场景8051CISC (8 位)Intel&#xff08;原始…...