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

本文主要是介绍代码随想录算法训练营第十天|20. 有效的括号，1047. 删除字符串中的所有相邻重复项，150. 逆波兰表达式求值，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

系列文章目录

代码随想录算法训练营第一天|数组理论基础，704. 二分查找，27. 移除元素
代码随想录算法训练营第二天|977.有序数组的平方 ，209.长度最小的子数组 ，59.螺旋矩阵II
代码随想录算法训练营第三天|链表理论基础，203.移除链表元素，707.设计链表，206.反转链表
代码随想录算法训练营第四天|24. 两两交换链表中的节点，19.删除链表的倒数第N个节点，面试题 02.07. 链表相交，142.环形链表II，总结
代码随想录算法训练营第五天|哈希表理论基础，242.有效的字母异位词，349. 两个数组的交集，202. 快乐数，1. 两数之和
代码随想录算法训练营第六天|454.四数相加II，383. 赎金信，15. 三数之和，18. 四数之和，总结
代码随想录算法训练营第七天|344.反转字符串，541. 反转字符串II，卡码网：54.替换数字，151.翻转字符串里的单词，卡码网：55.右旋转字符串
代码随想录算法训练营第八天|28. 实现 strStr()，459.重复的子字符串，字符串总结，双指针回顾
代码随想录算法训练营第九天|理论基础，232.用栈实现队列，225. 用队列实现栈

---

20. 有效的括号

题目链接： 20.有效的括号
题目内容： 给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 s ，判断字符串是否有效。有效字符串需满足：左括号必须用相同类型的右括号闭合；左括号必须以正确的顺序闭合；每个右括号都有一个对应的相同类型的左括号。
视频讲解：栈的拿手好戏！| LeetCode：20. 有效的括号

核心思想：遇到左括号就把对应的右括号放进栈里，遇到右括号就去栈里进行匹配，这样不仅可以保证左右括号的匹配，而且能保证顺序不出现问题。False的三种情况：左括号多了；左右括号类型不匹配；右括号多了。

class Solution:def isValid(self, s: str) -> bool:stack=[]for i in s:if i =='(':stack.append(')')elif i=='{':stack.append('}')elif i=='[':stack.append(']')elif not stack or stack[-1]!=i:return Falseelse:stack.pop()return True if not stack else False

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

题目链接： 1047.删除字符串中的所有相邻重复项
题目内容： 给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。在 S 上反复执行重复项删除操作，直到无法继续删除。在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。
视频讲解：栈的好戏还要继续！| LeetCode：1047. 删除字符串中的所有相邻重复项

核心思想：与上题类似，栈的目的就是存放遍历过的元素，当遍历当前的这个元素的时候，去栈里看一下是不是遍历过相同数值的相邻元素，然后再去做对应的消除操作。

class Solution:def removeDuplicates(self, s: str) -> str:stack=[]for i in s:if not stack or i != stack[-1]:stack.append(i)else:stack.pop()return "".join(stack)

也可以使用双指针的方法：慢指针用于产生结果，快指针用于遍历。当慢指针当前元素与前一个元素相同时，慢指针退回一格。

class Solution:def removeDuplicates(self, s: str) -> str:res = list(s)slow = fast = 0length = len(res)while fast < length:# 如果一样直接换，不一样会把后面的填在slow的位置res[slow] = res[fast]# 如果发现和前一个一样，就退一格指针if slow > 0 and res[slow] == res[slow - 1]:slow -= 1else:slow += 1fast += 1return ''.join(res[0: slow])

150. 逆波兰表达式求值

题目链接： 150.逆波兰表达式求值
题目内容： 给你一个字符串数组 tokens ，表示一个根据 逆波兰表示法 表示的算术表达式。请你计算该表达式。返回一个表示表达式值的整数。注意：有效的算符为 ‘+’、‘-’、‘*’ 和 ‘/’ ；每个操作数（运算对象）都可以是一个整数或者另一个表达式；两个整数之间的除法总是 向零截断 ；表达式中不含除零运算；输入是一个根据逆波兰表示法表示的算术表达式；答案及所有中间计算结果可以用 32 位 整数表示。
视频讲解：栈的最后表演！ | LeetCode：150. 逆波兰表达式求值

class Solution:def evalRPN(self, tokens: List[str]) -> int:stack=[]for i in tokens:if i in ['+','-','*','/']:num1=stack.pop()num2=stack.pop()#注意事项：第一个出栈的应该在运算符后边if i == '+':stack.append(int(num2+num1))elif i == '-':stack.append(int(num2-num1))elif i == '*':stack.append(int(num2*num1))else:stack.append(int(num2/num1))else:stack.append(int(i))return stack.pop()  

这篇关于代码随想录算法训练营第十天|20. 有效的括号，1047. 删除字符串中的所有相邻重复项，150. 逆波兰表达式求值的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---