【代码随想录训练营】【Day11】第五章|栈与队列|20. 有效的括号|1047. 删除字符串中的所有相邻重复项|150. 逆波兰表达式求值
20. 有效的括号
题目详细:LeetCode.20
由题可知,有效字符串需满足:
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 每个右括号都有一个对应的相同类型的左括号。
那么,我们可以利用栈后进先出
的特点:
- 当遍历到左括号时,将左括号字符依次进栈
- 当遍历到右括号时,将栈顶的左括号字符出栈
- 左括号如果与闭括号属于相同类型,则为有效括号,继续遍历下一个字符
- 左括号如果与闭括号属于不同类型,则为无效括号,栈内剩余的左括号也无法以正确的顺序闭合,返回false
- 如果栈为空,则说明不存在与之匹配的左括号,返回false
- 当遍历完输入的字符串后,注意需要判断栈是否为空,进而来判断字符串内的括号是否已完全匹配
Java解法(栈):
class Solution {public boolean isValid(String s) {Stack<Character> stack = new Stack<>();for(char a: s.toCharArray()){if(a == '(' || a == '{' || a == '['){stack.push(a);}else if(stack.isEmpty()){return false;}else{char b = stack.pop();// 在ASCII码中,左括号和右括号的差值 <= 2// 所以这里直接用 Math.abs(a-b) 来判断左右括号是否匹配if(Math.abs(a-b) > 2){return false;}}}return stack.isEmpty();}
}
1047. 删除字符串中的所有相邻重复项
题目详细:LeetCode.1047
这道题的实现方式不同,但解决思路是殊途同归的,都是利用栈后进先出的存储特点来解题:
- 字符串中的字符依zg次进栈,这样就保证了出栈的字符一定与下一个字符是相邻的
- 那么只需要比较栈顶元素和即将进栈的元素是否重复
- 如果重复,则弹出栈顶元素
- 如果不重复,则将遍历到字符进栈
- 最后只需要将栈内的字符重新组成字符串,即为无重复项的字符串。
Java解法(栈):
class Solution {public String removeDuplicates(String s) {Stack<Character> stack = new Stack<>();for(char a : s.toCharArray()){if(stack.isEmpty()){stack.push(a);}else{char b = stack.pop();if(a != b){stack.push(b);stack.push(a);}}}StringBuffer sb = new StringBuffer();while(!stack.isEmpty()){sb.insert(0, stack.pop());}return sb.toString();}
}
无独有偶,我们也可以用同样具备后进先出特点的双向队列来解决这道问题:
Java解法(双向队列):
class Solution {public String removeDuplicates(String s) {Deque<Character> deque = new LinkedList<>();for(char a : s.toCharArray()){if(deque.isEmpty()){deque.add(a);}else{char b = deque.pollLast();if(a != b){deque.add(b);deque.add(a);}}}StringBuffer sb = new StringBuffer();while(!deque.isEmpty()){sb.append(deque.poll());}return sb.toString();}
}
还有更为效率的方法,就是将字符串转为字符数组后,通过双指针,来模拟栈进栈和压栈时栈顶指针的移动,以及对重复字符的替换的过程,来解决这一问题:
Java解法(双指针/模拟栈):
class Solution {public String removeDuplicates(String s) {char[] ch = s.toCharArray();int top = 0;int next = 0;while(next < s.length()){ch[top] = ch[next];if(top > 0 && ch[top] == ch[top - 1]){top--;}else{top++;}next++;}return new String(ch,0,top);}
}
150. 逆波兰表达式求值
题目详细:LeetCode.150
波兰表达式,其实就是将表达式用二叉树的形式表示后,中序遍历二叉树得到的序列;而逆波兰表达式,就是后序遍历二叉树得到的序列。
观察逆波兰表达式的数组,可以发现:
- 利用栈先进后出的特点,能够保证两个数值计算的前后顺序
- 当遇到一个算术符号时,则在栈中弹出最近的两个数
- 将这两个数,按照算术符号进行相应的术式计算出结果
- 然后将计算结果再次压入栈中,保证后续数值计算的前后顺序
- 直到表达式遍历完,栈中仅剩的计算结果即为最终结果
Java解法(双指针/模拟栈):
class Solution {public int evalRPN(String[] tokens) {Deque<Integer> deque = new LinkedList<>();for(String t: tokens){if(t.equals("+") || t.equals("-") || t.equals("*") || t.equals("/")){int a = 0, b = 0, c = 0;a = deque.pollLast();b = deque.pollLast();switch(t){case "+":c = b + a;break;case "-":c = b - a;break;case "*":c = b * a;break;case "/":c = b / a;break;}deque.add(c);}else{deque.add(Integer.parseInt(t));}}return deque.poll();}
}
相关文章:
【代码随想录训练营】【Day11】第五章|栈与队列|20. 有效的括号|1047. 删除字符串中的所有相邻重复项|150. 逆波兰表达式求值
20. 有效的括号 题目详细:LeetCode.20 由题可知,有效字符串需满足: 左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。每个右括号都有一个对应的相同类型的左括号。 那么,我们可以利用栈后进先出的特点&#x…...

基于云原生分布式存储ceph实现k8s数据持久化
文章目录1、初始化集群1.1 集群机器配置1.2 配置主机名1.3 配置hosts文件1.4、配置互信1.5、关闭防火墙1.6、关闭selinux1.7、配置Ceph安装源1.8、配置时间同步1.9、安装基础软件包2、安装ceph集群2.1 安装ceph-deploy2.2 创建monitor节点2.3 安装ceph-monitor2.4 部署osd服务2…...
SpringMVC获取请求参数
SpringMVC获取请求参数 通过ServletAPI获取 将HttpServletRequest作为控制器方法的形参,此时HttpServletRequest类型的参数表示封装了当前请求的报文对象。 RequestMapping("/testServletAPI") // request表示当前请求 public String testServletAPI(H…...
详解浏览器从输入URL到页面展示的过程
用户发出 URL 请求到页面开始解析的这个过程,就叫做导航。 1. 用户输入 当用户在地址栏中输入一个查询关键字时,地址栏会判断输入的关键字是搜索内容,还是请求的 URL。 当用户输入关键字并键入回车之后,这意味着当前页面即将要…...

【吉先生的Java全栈之路】
吉士先生Java全栈学习路线🧡第一阶段Java基础: 在第一阶段:我们要认真听讲,因为基础很重要!基础很重要!基础很重要!!! 重要的事情说三遍。在这里我们先学JavaSE路线;学完之后我们要去学第一个可视化组件编程《GUI》;然后写个《贪吃蛇》游戏耍…...

第二章 Opencv图像处理基本操作
目录1.读取图像1-1.imread()方法2.显示图像2-1.imshow()方法2-2.waitKey()方法2-3.destroyAllWindows()方法2-4.小总结3.保存图像3-1.imwrite()方法4.查看图像属性4-1.常见的三个图像属性1.读取图像 要对一幅图像进行处理,第一件事就是要读取这幅图像。 1-1.imread(…...

字节一面:在浏览器地址栏输入一个 URL 后回车,背后发生了什么?
近段时间,有小伙伴面试字节,说遇到一个面试题: 在浏览器地址栏输入一个 URL 后回车,背后发生了什么? 这里尼恩给大家做一下系统化、体系化的梳理,使得大家可以充分展示一下大家雄厚的 “技术肌肉”…...

推荐3dMax三维设计十大插件
3dMax是一款功能非常强大的三维设计软件,但无论它的功能多么强大,也不可能包含所有三维方面的功能,这时候,第三方插件可以很好的弥补和增强3dMax的基本功能,下面就给大家介绍十款非常不错的3dMax插件。 森林包…...

Arduino IDE 2.0.6中 ESP32开发环境搭建笔记
Arduino IDE 2.0.6中 ESP32开发环境搭建 Arduino IDE2.0 已上线一段时间,以后ESP32的学习转至新的IDE中 ,需对开发环境进行。 Arduino IDE2.0与1.0有很大差异。原来环境搭建方法已完全不同。下文主要记录环…...

商品秒杀接口压测及优化
目录一、生成测试用户二、jmeter压测三、秒杀接口优化1、优化第一步:解决超卖2、优化第二步:Redis重复抢购3、优化第三步:Redis预减库存①商品初始化②预减库存一、生成测试用户 将UserUtils工具类导入到zmall-user模块中,运行生…...
NFC 项目前期准备工作
同学,别退出呀,我可是全网最牛逼的 WIFI/BT/GPS/NFC分析博主,我写了上百篇文章,请点击下面了解本专栏,进入本博主主页看看再走呗,一定不会让你后悔的,记得一定要去看主页置顶文章哦。 了解项目信息,FAE联系方式,驱动源码等驱动合入内核配置DTS驱动设备节点验证Push nf…...

(C语言)数据的存储
问:1. 数据类型有哪五大类?2. 数据类型的作用是什么与什么?3. 整型又可以具体分为哪五个?为什么字符char也归属于整型?4. 浮点型又可以具体分为哪两类?5. 构造类型就是什么?具体分为哪四类&…...

C语言深度剖析之文件操作
💗 💗 博客:小怡同学 💗 💗 个人简介:编程小萌新 💗 💗 如果博客对大家有用的话,请点赞关注加关注 🌞 什么是文件 磁盘上的文件是文件。 但是在程序设计中,我们一般谈的文…...

RNN神经网络初探
目录1. 神经网络与未来智能2. 回顾数据维度和神经网络1. 神经网络与未来智能 2. 回顾数据维度和神经网络 循环神经网络,主要用来处理时序的数据,它对每个词的顺序是有要求的。 循环神经网络如何保存记忆功能? 当前样本只有 3 个特征&#x…...
【flinkx】【hdfs】【ing】Cannot obtain block length for LocatedBlock
一. 任务描述 使用flinkx去跑HDFS到HIVE的任务时,出现如下报错: CannotObtainBlockLengthException com.dtstack.flinkx.throwable.FlinkxRuntimeException: cant get file size from hdfs, file hdfs://xxx/.data/540240453caeb6fe4b3f118410a05315_2…...

【Day6】合并两个排序链表与合并k个已排序的链表,java代码实现
前言: 大家好,我是良辰丫🚀🚀🚀,今天与大家一起做两道牛客网的链表题,好久写关于链表题的博客了,这两道题可以帮大家巩固一下链表知识,我把两道题的链接放到下面…...
Swagger PHP
PHP使用Swagger生成好看的API文档不是不可能,而是非常简单。首先本人使用Laravel框架,所以在Laravel上安装swagger-php。一、安装swagger - phpcomposer require zircote/swagger-phpswagger-php提供了命令行工具,所以可以全局安装࿰…...
谷粒商城-品牌管理-JSR303数据校验
后端在处理前端传过来的数据时,尽管前端表单已经加了校验逻辑,但是作为严谨考虑,在后端对接口传输的数据做校验也必不可少。 开启校验: 实体类上增加校验注解,接口参数前增加Valid 开启校验 package com.xxh.product.…...

Java零基础教程——数组
目录数组静态初始化数组数组的访问数组的动态初始化元素默认值规则:数组的遍历数组遍历-求和冒泡排序数组的逆序交换数组 数组就是用来存储一批同种类型数据的容器。 20, 10, 80, 60, 90 int[] arr {20, 10, 80, 60, 90}; //位置 0 1 2 3 4数组的…...

AirServer在哪下载?如何免费使用教程
苹果手机投屏到电脑mac是怎么弄?你知道多少?相信大家对苹果手机投屏到电脑mac能在电脑上操作不是很了解,下面就让coco玛奇朵带大家一起了解一下教程。AIrServer是一款ios投屏到mac的专用软件,可将iOS上的音频,视频&…...

关于nvm与node.js
1 安装nvm 安装过程中手动修改 nvm的安装路径, 以及修改 通过nvm安装node后正在使用的node的存放目录【这句话可能难以理解,但接着往下看你就了然了】 2 修改nvm中settings.txt文件配置 nvm安装成功后,通常在该文件中会出现以下配置&…...

【机器视觉】单目测距——运动结构恢复
ps:图是随便找的,为了凑个封面 前言 在前面对光流法进行进一步改进,希望将2D光流推广至3D场景流时,发现2D转3D过程中存在尺度歧义问题,需要补全摄像头拍摄图像中缺失的深度信息,否则解空间不收敛…...
工程地质软件市场:发展现状、趋势与策略建议
一、引言 在工程建设领域,准确把握地质条件是确保项目顺利推进和安全运营的关键。工程地质软件作为处理、分析、模拟和展示工程地质数据的重要工具,正发挥着日益重要的作用。它凭借强大的数据处理能力、三维建模功能、空间分析工具和可视化展示手段&…...
postgresql|数据库|只读用户的创建和删除(备忘)
CREATE USER read_only WITH PASSWORD 密码 -- 连接到xxx数据库 \c xxx -- 授予对xxx数据库的只读权限 GRANT CONNECT ON DATABASE xxx TO read_only; GRANT USAGE ON SCHEMA public TO read_only; GRANT SELECT ON ALL TABLES IN SCHEMA public TO read_only; GRANT EXECUTE O…...

ardupilot 开发环境eclipse 中import 缺少C++
目录 文章目录 目录摘要1.修复过程摘要 本节主要解决ardupilot 开发环境eclipse 中import 缺少C++,无法导入ardupilot代码,会引起查看不方便的问题。如下图所示 1.修复过程 0.安装ubuntu 软件中自带的eclipse 1.打开eclipse—Help—install new software 2.在 Work with中…...

IT供电系统绝缘监测及故障定位解决方案
随着新能源的快速发展,光伏电站、储能系统及充电设备已广泛应用于现代能源网络。在光伏领域,IT供电系统凭借其持续供电性好、安全性高等优势成为光伏首选,但在长期运行中,例如老化、潮湿、隐裂、机械损伤等问题会影响光伏板绝缘层…...

ArcGIS Pro制作水平横向图例+多级标注
今天介绍下载ArcGIS Pro中如何设置水平横向图例。 之前我们介绍了ArcGIS的横向图例制作:ArcGIS横向、多列图例、顺序重排、符号居中、批量更改图例符号等等(ArcGIS出图图例8大技巧),那这次我们看看ArcGIS Pro如何更加快捷的操作。…...
【无标题】路径问题的革命性重构:基于二维拓扑收缩色动力学模型的零点隧穿理论
路径问题的革命性重构:基于二维拓扑收缩色动力学模型的零点隧穿理论 一、传统路径模型的根本缺陷 在经典正方形路径问题中(图1): mermaid graph LR A((A)) --- B((B)) B --- C((C)) C --- D((D)) D --- A A -.- C[无直接路径] B -…...

Ubuntu系统复制(U盘-电脑硬盘)
所需环境 电脑自带硬盘:1块 (1T) U盘1:Ubuntu系统引导盘(用于“U盘2”复制到“电脑自带硬盘”) U盘2:Ubuntu系统盘(1T,用于被复制) !!!建议“电脑…...

五子棋测试用例
一.项目背景 1.1 项目简介 传统棋类文化的推广 五子棋是一种古老的棋类游戏,有着深厚的文化底蕴。通过将五子棋制作成网页游戏,可以让更多的人了解和接触到这一传统棋类文化。无论是国内还是国外的玩家,都可以通过网页五子棋感受到东方棋类…...