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

相关文章

C#数据结构之字符串(string)详解

《C#数据结构之字符串(string)详解》:本文主要介绍C#数据结构之字符串(string),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录转义字符序列字符串的创建字符串的声明null字符串与空字符串重复单字符字符串的构造字符串的属性和常用方法属性常用方法总结摘

macOS无效Launchpad图标轻松删除的4 种实用方法

《macOS无效Launchpad图标轻松删除的4种实用方法》mac中不在appstore上下载的应用经常在删除后它的图标还残留在launchpad中,并且长按图标也不会出现删除符号,下面解决这个问... 在 MACOS 上,Launchpad(也就是「启动台」)是一个便捷的 App 启动工具。但有时候,应

Java实现时间与字符串互相转换详解

《Java实现时间与字符串互相转换详解》这篇文章主要为大家详细介绍了Java中实现时间与字符串互相转换的相关方法,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录一、日期格式化为字符串(一)使用预定义格式(二)自定义格式二、字符串解析为日期(一)解析ISO格式字符串(二)解析自定义

Mysql删除几亿条数据表中的部分数据的方法实现

《Mysql删除几亿条数据表中的部分数据的方法实现》在MySQL中删除一个大表中的数据时,需要特别注意操作的性能和对系统的影响,本文主要介绍了Mysql删除几亿条数据表中的部分数据的方法实现,具有一定... 目录1、需求2、方案1. 使用 DELETE 语句分批删除2. 使用 INPLACE ALTER T

Python实现将MySQL中所有表的数据都导出为CSV文件并压缩

《Python实现将MySQL中所有表的数据都导出为CSV文件并压缩》这篇文章主要为大家详细介绍了如何使用Python将MySQL数据库中所有表的数据都导出为CSV文件到一个目录,并压缩为zip文件到... python将mysql数据库中所有表的数据都导出为CSV文件到一个目录,并压缩为zip文件到另一个

利用Go语言开发文件操作工具轻松处理所有文件

《利用Go语言开发文件操作工具轻松处理所有文件》在后端开发中,文件操作是一个非常常见但又容易出错的场景,本文小编要向大家介绍一个强大的Go语言文件操作工具库,它能帮你轻松处理各种文件操作场景... 目录为什么需要这个工具?核心功能详解1. 文件/目录存javascript在性检查2. 批量创建目录3. 文件

python中字符串拼接的几种方法及优缺点对比详解

《python中字符串拼接的几种方法及优缺点对比详解》在Python中,字符串拼接是常见的操作,Python提供了多种方法来拼接字符串,每种方法有其优缺点和适用场景,以下是几种常见的字符串拼接方法,需... 目录1. 使用 + 运算符示例:优缺点:2. 使用&nbsjsp;join() 方法示例:优缺点:3

SpringBoot @Scheduled Cron表达式使用方式

《SpringBoot@ScheduledCron表达式使用方式》:本文主要介绍SpringBoot@ScheduledCron表达式使用方式,具有很好的参考价值,希望对大家有所帮助,如有... 目录Cron 表达式详解1. 表达式格式‌2. 特殊字符解析3. 常用示例‌4. 重点规则5. 动态与复杂场景‌

java字符串数字补齐位数详解

《java字符串数字补齐位数详解》:本文主要介绍java字符串数字补齐位数,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Java字符串数字补齐位数一、使用String.format()方法二、Apache Commons Lang库方法三、Java 11+的St

C++从序列容器中删除元素的四种方法

《C++从序列容器中删除元素的四种方法》删除元素的方法在序列容器和关联容器之间是非常不同的,在序列容器中,vector和string是最常用的,但这里也会介绍deque和list以供全面了解,尽管在一... 目录一、简介二、移除给定位置的元素三、移除与某个值相等的元素3.1、序列容器vector、deque