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

【代码随想录训练营】【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. 有效的括号 题目详细&#xff1a;LeetCode.20 由题可知&#xff0c;有效字符串需满足&#xff1a; 左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。每个右括号都有一个对应的相同类型的左括号。 那么&#xff0c;我们可以利用栈后进先出的特点&#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作为控制器方法的形参&#xff0c;此时HttpServletRequest类型的参数表示封装了当前请求的报文对象。 RequestMapping("/testServletAPI") // request表示当前请求 public String testServletAPI(H…...

详解浏览器从输入URL到页面展示的过程

用户发出 URL 请求到页面开始解析的这个过程&#xff0c;就叫做导航。 1. 用户输入 当用户在地址栏中输入一个查询关键字时&#xff0c;地址栏会判断输入的关键字是搜索内容&#xff0c;还是请求的 URL。 当用户输入关键字并键入回车之后&#xff0c;这意味着当前页面即将要…...

【吉先生的Java全栈之路】

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

第二章 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.读取图像 要对一幅图像进行处理&#xff0c;第一件事就是要读取这幅图像。 1-1.imread(…...

字节一面:在浏览器地址栏输入一个 URL 后回车,背后发生了什么?

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

推荐3dMax三维设计十大插件

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

Arduino IDE 2.0.6中 ESP32开发环境搭建笔记

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

商品秒杀接口压测及优化

目录一、生成测试用户二、jmeter压测三、秒杀接口优化1、优化第一步&#xff1a;解决超卖2、优化第二步&#xff1a;Redis重复抢购3、优化第三步&#xff1a;Redis预减库存①商品初始化②预减库存一、生成测试用户 将UserUtils工具类导入到zmall-user模块中&#xff0c;运行生…...

NFC 项目前期准备工作

同学,别退出呀,我可是全网最牛逼的 WIFI/BT/GPS/NFC分析博主,我写了上百篇文章,请点击下面了解本专栏,进入本博主主页看看再走呗,一定不会让你后悔的,记得一定要去看主页置顶文章哦。 了解项目信息,FAE联系方式,驱动源码等驱动合入内核配置DTS驱动设备节点验证Push nf…...

(C语言)数据的存储

问&#xff1a;1. 数据类型有哪五大类&#xff1f;2. 数据类型的作用是什么与什么&#xff1f;3. 整型又可以具体分为哪五个&#xff1f;为什么字符char也归属于整型&#xff1f;4. 浮点型又可以具体分为哪两类&#xff1f;5. 构造类型就是什么&#xff1f;具体分为哪四类&…...

C语言深度剖析之文件操作

&#x1f497; &#x1f497; 博客:小怡同学 &#x1f497; &#x1f497; 个人简介:编程小萌新 &#x1f497; &#x1f497; 如果博客对大家有用的话&#xff0c;请点赞关注加关注 &#x1f31e; 什么是文件 磁盘上的文件是文件。 但是在程序设计中&#xff0c;我们一般谈的文…...

RNN神经网络初探

目录1. 神经网络与未来智能2. 回顾数据维度和神经网络1. 神经网络与未来智能 2. 回顾数据维度和神经网络 循环神经网络&#xff0c;主要用来处理时序的数据&#xff0c;它对每个词的顺序是有要求的。 循环神经网络如何保存记忆功能&#xff1f; 当前样本只有 3 个特征&#x…...

【flinkx】【hdfs】【ing】Cannot obtain block length for LocatedBlock

一. 任务描述 使用flinkx去跑HDFS到HIVE的任务时&#xff0c;出现如下报错&#xff1a; CannotObtainBlockLengthException com.dtstack.flinkx.throwable.FlinkxRuntimeException: cant get file size from hdfs, file hdfs://xxx/.data/540240453caeb6fe4b3f118410a05315_2…...

【Day6】合并两个排序链表与合并k个已排序的链表,java代码实现

前言&#xff1a; 大家好&#xff0c;我是良辰丫&#x1f680;&#x1f680;&#x1f680;&#xff0c;今天与大家一起做两道牛客网的链表题&#xff0c;好久写关于链表题的博客了&#xff0c;这两道题可以帮大家巩固一下链表知识&#xff0c;我把两道题的链接放到下面&#xf…...

Swagger PHP

PHP使用Swagger生成好看的API文档不是不可能&#xff0c;而是非常简单。首先本人使用Laravel框架&#xff0c;所以在Laravel上安装swagger-php。一、安装swagger - phpcomposer require zircote/swagger-phpswagger-php提供了命令行工具&#xff0c;所以可以全局安装&#xff0…...

谷粒商城-品牌管理-JSR303数据校验

后端在处理前端传过来的数据时&#xff0c;尽管前端表单已经加了校验逻辑&#xff0c;但是作为严谨考虑&#xff0c;在后端对接口传输的数据做校验也必不可少。 开启校验&#xff1a; 实体类上增加校验注解&#xff0c;接口参数前增加Valid 开启校验 package com.xxh.product.…...

Java零基础教程——数组

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

AirServer在哪下载?如何免费使用教程

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

C++_核心编程_多态案例二-制作饮品

#include <iostream> #include <string> using namespace std;/*制作饮品的大致流程为&#xff1a;煮水 - 冲泡 - 倒入杯中 - 加入辅料 利用多态技术实现本案例&#xff0c;提供抽象制作饮品基类&#xff0c;提供子类制作咖啡和茶叶*//*基类*/ class AbstractDr…...

【Web 进阶篇】优雅的接口设计:统一响应、全局异常处理与参数校验

系列回顾&#xff1a; 在上一篇中&#xff0c;我们成功地为应用集成了数据库&#xff0c;并使用 Spring Data JPA 实现了基本的 CRUD API。我们的应用现在能“记忆”数据了&#xff01;但是&#xff0c;如果你仔细审视那些 API&#xff0c;会发现它们还很“粗糙”&#xff1a;有…...

ios苹果系统,js 滑动屏幕、锚定无效

现象&#xff1a;window.addEventListener监听touch无效&#xff0c;划不动屏幕&#xff0c;但是代码逻辑都有执行到。 scrollIntoView也无效。 原因&#xff1a;这是因为 iOS 的触摸事件处理机制和 touch-action: none 的设置有关。ios有太多得交互动作&#xff0c;从而会影响…...

GC1808高性能24位立体声音频ADC芯片解析

1. 芯片概述 GC1808是一款24位立体声音频模数转换器&#xff08;ADC&#xff09;&#xff0c;支持8kHz~96kHz采样率&#xff0c;集成Δ-Σ调制器、数字抗混叠滤波器和高通滤波器&#xff0c;适用于高保真音频采集场景。 2. 核心特性 高精度&#xff1a;24位分辨率&#xff0c…...

USB Over IP专用硬件的5个特点

USB over IP技术通过将USB协议数据封装在标准TCP/IP网络数据包中&#xff0c;从根本上改变了USB连接。这允许客户端通过局域网或广域网远程访问和控制物理连接到服务器的USB设备&#xff08;如专用硬件设备&#xff09;&#xff0c;从而消除了直接物理连接的需要。USB over IP的…...

Git 3天2K星标:Datawhale 的 Happy-LLM 项目介绍(附教程)

引言 在人工智能飞速发展的今天&#xff0c;大语言模型&#xff08;Large Language Models, LLMs&#xff09;已成为技术领域的焦点。从智能写作到代码生成&#xff0c;LLM 的应用场景不断扩展&#xff0c;深刻改变了我们的工作和生活方式。然而&#xff0c;理解这些模型的内部…...

Elastic 获得 AWS 教育 ISV 合作伙伴资质,进一步增强教育解决方案产品组合

作者&#xff1a;来自 Elastic Udayasimha Theepireddy (Uday), Brian Bergholm, Marianna Jonsdottir 通过搜索 AI 和云创新推动教育领域的数字化转型。 我们非常高兴地宣布&#xff0c;Elastic 已获得 AWS 教育 ISV 合作伙伴资质。这一重要认证表明&#xff0c;Elastic 作为 …...

React从基础入门到高级实战:React 实战项目 - 项目五:微前端与模块化架构

React 实战项目&#xff1a;微前端与模块化架构 欢迎来到 React 开发教程专栏 的第 30 篇&#xff01;在前 29 篇文章中&#xff0c;我们从 React 的基础概念逐步深入到高级技巧&#xff0c;涵盖了组件设计、状态管理、路由配置、性能优化和企业级应用等核心内容。这一次&…...

数据库正常,但后端收不到数据原因及解决

从代码和日志来看&#xff0c;后端SQL查询确实返回了数据&#xff0c;但最终user对象却为null。这表明查询结果没有正确映射到User对象上。 在前后端分离&#xff0c;并且ai辅助开发的时候&#xff0c;很容易出现前后端变量名不一致情况&#xff0c;还不报错&#xff0c;只是单…...

Python环境安装与虚拟环境配置详解

本文档旨在为Python开发者提供一站式的环境安装与虚拟环境配置指南&#xff0c;适用于Windows、macOS和Linux系统。无论你是初学者还是有经验的开发者&#xff0c;都能在此找到适合自己的环境搭建方法和常见问题的解决方案。 快速开始 一分钟快速安装与虚拟环境配置 # macOS/…...