题目简介
20: 有效的括号 https://leetcode.cn/problems/valid-parentheses/description/
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。
1047: 删除字符串中的所有相邻重复项 https://leetcode.cn/problems/remove-all-adjacent-duplicates-in-string/description/
给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。
在 S 上反复执行重复项删除操作，直到无法继续删除。
在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。
150: 逆波兰表达式求值 https://leetcode.cn/problems/evaluate-reverse-polish-notation/
给你一个字符串数组 tokens ，表示一个根据 逆波兰表示法 表示的算术表达式。
请你计算该表达式。返回一个表示表达式值的整数。
注意：
- 有效的算符为
'+'、'-'、'*'和'/'。 - 每个操作数（运算对象）都可以是一个整数或者另一个表达式。
- 两个整数之间的除法总是 向零截断 。
- 表达式中不含除零运算。
- 输入是一个根据逆波兰表示法表示的算术表达式。
- 答案及所有中间计算结果可以用 32 位 整数表示。
初见思路
今日全部AC思路如下。 这样的栈的使用暂且还很简单，150题有很多的变式， 但核心都不变。 150有一个头痛的点是除法的取整有可能会有问题，Python中的int()的直接转型是向0取整，注意可以活用，不一定要round()或者ceil().
class Solution:
def isValid(self, s: str) -> bool:
if len(s) % 2 == 1:
return False
pairs = {')':'(',']':'[','}':'{'}
stack = list()
for ch in s:
if ch in pairs:
if not stack or pairs[ch] != stack[-1]:
return False
stack.pop()
else:
stack.append(ch)
return not stack
1047
class Solution:
def removeDuplicates(self, s: str) -> str:
if len(s) < 2:
return s
stack = list()
for i,ch in enumerate(s):
if i > 0 and stack and ch == stack[-1]:
stack.pop()
continue
stack.append(ch)
return ''.join(stack)
150
from collections import deque
class Solution:
def evalRPN(self, tokens: List[str]) -> int:
if len(tokens) == 0 and tokens[0].isnumeric():
return int(tokens[0])
digits = deque()
for ch in tokens:
if ch.isdigit() or (ch.startswith('-') and ch[1:].isdigit()):
print(ch)
digits.append(int(ch))
else:
if len(digits) > 1:
d2,d1 = digits.pop(),digits.pop()
result = 0
if ch == '+':
result = d1 + d2
elif ch == '-':
result = d1 - d2
elif ch == '*':
result = d1 * d2
elif ch == '/':
result = int(d1 / d2)
digits.append(result)
return digits[0]
复盘思路
https://programmercarl.com/0020.%E6%9C%89%E6%95%88%E7%9A%84%E6%8B%AC%E5%8F%B7.html
重点难点
见复盘思路
今日收获
- 栈的基本特点和操作。
