Day11:栈与队列part02:20. 有效的括号、1047.删除字符串中所有相邻重复项、150. 逆波兰表达式求值

本文主要是介绍Day11:栈与队列part02:20. 有效的括号、1047.删除字符串中所有相邻重复项、150. 逆波兰表达式求值,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

https://blog.csdn.net/weixin_43303286/article/details/131869968?spm=1001.2014.3001.5501

  1. 有效的括号

遇见左括号对应的右括号进栈,遇到右括号看栈顶,不相同就返回false

class Solution {public boolean isValid(String s) {Stack<Character> stack = new Stack<>();for(char ch : s.toCharArray()){if(ch == '{') {stack.push('}');}else if(ch == '('){stack.push(')');}else if(ch == '['){stack.push(']');}else{if(!stack.empty()){if(stack.peek() != ch){return false;}else{stack.pop();}}else{return false;}}}return stack.empty();}}

1047.删除字符串中所有相邻重复项

就是消消乐思想,栈的拿手好戏,可以直接声明stack,也可以用字符串当作栈:

在Java中,Deque(双端队列)通常被用作栈的实现,而不是Stack类,主要有以下几个原因:

Stack类是Java早期版本中的遗留类,它继承自Vector类,而Vector类的所有方法都是同步的,这意味着它在多线程环境下的性能较差。

Deque接口提供了更丰富和一致的接口。例如,Deque提供了addFirst、addLast、removeFirst、removeLast等方法,这使得它既可以作为栈(先进后出)使用,也可以作为队列(先进先出)使用。

Deque接口的实现类,如ArrayDeque,通常比Stack类具有更好的性能。

class Solution {public String removeDuplicates(String s) {Stack<Character> sb = new Stack<>();StringBuilder sb1 = new StringBuilder();for (int i = 0; i < s.length(); i++) {if(sb.isEmpty() || sb.peek()!= s.charAt(i)){sb.push(s.charAt(i));}else{sb.pop();}}while(!sb.empty()){sb1.append(sb.pop());}return sb1.reverse().toString();}
}
  • 翻转字符串:StringBuilder的reverse()
  • 使用Deque的代码:
class Solution {public String removeDuplicates(String S) {//ArrayDeque会比LinkedList在除了删除元素这一点外会快一点//参考:https://stackoverflow.com/questions/6163166/why-is-arraydeque-better-than-linkedlistArrayDeque<Character> deque = new ArrayDeque<>();char ch;for (int i = 0; i < S.length(); i++) {ch = S.charAt(i);if (deque.isEmpty() || deque.peek() != ch) {deque.push(ch);} else {deque.pop();}}String str = "";//剩余的元素即为不重复的元素while (!deque.isEmpty()) {str = deque.pop() + str;}return str;}
}
  • 直接用字符串当栈:
class Solution {public String removeDuplicates(String s) {// 将 res 当做栈// 也可以用 StringBuilder 来修改字符串,速度更快// StringBuilder res = new StringBuilder();StringBuffer res = new StringBuffer();// top为 res 的长度int top = -1;for (int i = 0; i < s.length(); i++) {char c = s.charAt(i);// 当 top > 0,即栈中有字符时,当前字符如果和栈中字符相等,弹出栈顶字符,同时 top--if (top >= 0 && res.charAt(top) == c) {res.deleteCharAt(top);top--;// 否则,将该字符 入栈,同时top++} else {res.append(c);top++;}}return res.toString();}
}

150. 逆波兰表达式求值

注意-和/有顺序要求。

class Solution {public int evalRPN(String[] tokens) {Deque<Integer> nums = new ArrayDeque<>();//用来存数字for(String s: tokens){if(Objects.equals(s, "+")){nums.push(nums.pop() + nums.pop());}else if(Objects.equals(s, "-")){int a = nums.pop();int b = nums.pop();nums.push(b - a);}else if(Objects.equals(s, "*")){nums.push(nums.pop() * nums.pop());}else if(Objects.equals(s, "/")){int a = nums.pop();int b = nums.pop();nums.push(b / a);}else{nums.push(Integer.parseInt(s));}}return nums.peek();}
  • Integer.parseInt(s)字符串转数字

这篇关于Day11:栈与队列part02:20. 有效的括号、1047.删除字符串中所有相邻重复项、150. 逆波兰表达式求值的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/817396

相关文章

Java中字符串转时间与时间转字符串的操作详解

《Java中字符串转时间与时间转字符串的操作详解》Java的java.time包提供了强大的日期和时间处理功能,通过DateTimeFormatter可以轻松地在日期时间对象和字符串之间进行转换,下面... 目录一、字符串转时间(一)使用预定义格式(二)自定义格式二、时间转字符串(一)使用预定义格式(二)自

MySQL重复数据处理的七种高效方法

《MySQL重复数据处理的七种高效方法》你是不是也曾遇到过这样的烦恼:明明系统测试时一切正常,上线后却频频出现重复数据,大批量导数据时,总有那么几条不听话的记录导致整个事务莫名回滚,今天,我就跟大家分... 目录1. 重复数据插入问题分析1.1 问题本质1.2 常见场景图2. 基础解决方案:使用异常捕获3.

Java的栈与队列实现代码解析

《Java的栈与队列实现代码解析》栈是常见的线性数据结构,栈的特点是以先进后出的形式,后进先出,先进后出,分为栈底和栈顶,栈应用于内存的分配,表达式求值,存储临时的数据和方法的调用等,本文给大家介绍J... 目录栈的概念(Stack)栈的实现代码队列(Queue)模拟实现队列(双链表实现)循环队列(循环数组

redis过期key的删除策略介绍

《redis过期key的删除策略介绍》:本文主要介绍redis过期key的删除策略,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录第一种策略:被动删除第二种策略:定期删除第三种策略:强制删除关于big key的清理UNLINK命令FLUSHALL/FLUSHDB命

Java中的Lambda表达式及其应用小结

《Java中的Lambda表达式及其应用小结》Java中的Lambda表达式是一项极具创新性的特性,它使得Java代码更加简洁和高效,尤其是在集合操作和并行处理方面,:本文主要介绍Java中的La... 目录前言1. 什么是Lambda表达式?2. Lambda表达式的基本语法例子1:最简单的Lambda表

Redis消息队列实现异步秒杀功能

《Redis消息队列实现异步秒杀功能》在高并发场景下,为了提高秒杀业务的性能,可将部分工作交给Redis处理,并通过异步方式执行,Redis提供了多种数据结构来实现消息队列,总结三种,本文详细介绍Re... 目录1 Redis消息队列1.1 List 结构1.2 Pub/Sub 模式1.3 Stream 结

Spring Boot 集成 Quartz并使用Cron 表达式实现定时任务

《SpringBoot集成Quartz并使用Cron表达式实现定时任务》本篇文章介绍了如何在SpringBoot中集成Quartz进行定时任务调度,并通过Cron表达式控制任务... 目录前言1. 添加 Quartz 依赖2. 创建 Quartz 任务3. 配置 Quartz 任务调度4. 启动 Sprin

Java字符串操作技巧之语法、示例与应用场景分析

《Java字符串操作技巧之语法、示例与应用场景分析》在Java算法题和日常开发中,字符串处理是必备的核心技能,本文全面梳理Java中字符串的常用操作语法,结合代码示例、应用场景和避坑指南,可快速掌握字... 目录引言1. 基础操作1.1 创建字符串1.2 获取长度1.3 访问字符2. 字符串处理2.1 子字

一文详解如何在Python中从字符串中提取部分内容

《一文详解如何在Python中从字符串中提取部分内容》:本文主要介绍如何在Python中从字符串中提取部分内容的相关资料,包括使用正则表达式、Pyparsing库、AST(抽象语法树)、字符串操作... 目录前言解决方案方法一:使用正则表达式方法二:使用 Pyparsing方法三:使用 AST方法四:使用字

Java字符串处理全解析(String、StringBuilder与StringBuffer)

《Java字符串处理全解析(String、StringBuilder与StringBuffer)》:本文主要介绍Java字符串处理全解析(String、StringBuilder与StringBu... 目录Java字符串处理全解析:String、StringBuilder与StringBuffer一、St