Leetcod面试经典150题刷题记录 —— 栈篇

1. 有效的括号

题目链接：有效的括号 - leetcode
题目描述：
给定一个只包括 ( ，)，{，}，[，] 的字符串 s ，判断字符串是否有效。有效字符串需满足：
(1)左括号必须用相同类型的右括号闭合。
(2)左括号必须以正确的顺序闭合。
(3)每个右括号都有一个对应的相同类型的左括号。
题目归纳：
经典面试题，一定要掌握

解题思路：
(1) 解法： 有效的括号 - leetcode官方题解

class Solution:def isValid(self, s: str) -> bool:dic = {")":"(", "]":"[", "}":"{"}# (1)左括号入栈，遇到右括号就出栈s_len = len(s)stack = list()for i in range(s_len):ch = s[i]if ch in dic and len(stack) > 0 and dic[ch] == stack[-1]: # (2)右括号，且匹配正确stack.pop(-1)else: # (3)左括号需入栈stack.append(ch)# (4)最后栈空即是有效括号的字符串if len(stack) == 0:return Truereturn False

2. 简化路径

题目链接：简化路径 - leetcode
题目描述：
给你一个字符串 path ，表示指向某一文件或目录的 Unix 风格 绝对路径 （以 '/' 开头），请你将其转化为更加简洁的规范路径。
在 Unix 风格的文件系统中，一个点（.）表示当前目录本身；此外，两个点 （..） 表示将目录切换到上一级（指向父目录）；两者都可以是复杂相对路径的组成部分。任意多个连续的斜杠（即，'//'）都被视为单个斜杠 '/' 。 对于此问题，任何其他格式的点（例如，'...'）均被视为文件/目录名称。
请注意，返回的 规范路径 必须遵循下述格式：
始终以斜杠 '/' 开头。
两个目录名之间必须只有一个斜杠 '/' 。
最后一个目录名（如果存在）不能 以 '/' 结尾。
此外，路径仅包含从根目录到目标文件或目录的路径上的目录（即，不含 '.' 或 '..'）。
返回简化后得到的 规范路径 。
题目归纳：

解题思路：
(1) 解法： 简化路径 - leetcode官方题解

class Solution:def simplifyPath(self, path: str) -> str:# 使用栈结构# (1)将字符串path根据/分割成字符串数组paths，paths共包含以下元素#    (a)空字符串。分割多个连续的///时出现。无需处理#    (b). 无需处理#    (c)..#    (d)dir_namepaths = path.split('/')print(paths)# (2)建栈stack = list()for i in range(len(paths)):path = paths[i]if path == "..": # 遇到.. ，栈顶元素出栈if stack:    # 允许/../../../../这种反复cd到根目录的情况，相当于在stack空的时候丢弃了..stack.pop()elif path == ".":continueelif path != "": # 遇到dir_name ，元素入栈            stack.append(path)# (3)最后用/，从栈底到栈顶依次连接栈内元素，并在最前面加上/表示根目录，即为规范路径return "/" + "/".join(stack)

3. 最小栈

题目链接：最小栈 - leetcode
题目描述：
设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
实现 MinStack 类:
MinStack() 初始化堆栈对象。
void push(int val) 将元素val推入堆栈。
void pop() 删除堆栈顶部的元素。
int top() 获取堆栈顶部的元素。
int getMin() 获取堆栈中的最小元素。

-2³¹ <= val <= 2³¹ - 1
pop、top 和 getMin 操作总是在 非空栈 上调用
push, pop, top, getMin最多被调用 3 * 104 次

题目归纳：
首先，只靠一个单独的普通的栈，无法做到这点，即便做到也需要O(n)的时间，所以一定会需要额外空间，这确定了本题的方向与思路，即开辟额外的空间去记录信息作为辅助

解题思路：
(1) 解法： 最小栈 - leetcode官方题解

# 首先，只靠一个单独的普通的栈，无法做到这点，即便做到也需要O(n)的时间
# 所以一定会需要额外空间，这确定了本题的方向与思路，即开辟额外的空间去记录信息作为辅助
# 空间复杂度：存储 信息的开销。
# 时间复杂度：计算 信息的开销。
# 由于存储设备RAM相对比较低廉，主要考虑的都是空间换时间# 一边往正常的stack压元素，一边往min_stack压当前的最小值
# 当一个元素入栈时，取当前辅助栈栈顶存储的min_value，与当前元素比较得出min_value，将这个min_value插入辅助栈中；class MinStack:def __init__(self):self.stack = []self.min_stack = [math.inf] # 若取到math.inf说明栈空def push(self, val: int) -> None:self.stack.append(val)self.min_stack.append(min(self.min_stack[-1], val))def pop(self) -> None:self.stack.pop(-1)self.min_stack.pop(-1)def top(self) -> int:return self.stack[-1]def getMin(self) -> int:return self.min_stack[-1]# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(val)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()

4. 逆波兰表达式求值

题目链接：逆波兰表达式求值 - leetcode
题目描述：
给你一个字符串数组 tokens ，表示一个根据 逆波兰表示法 表示的算术表达式。
请你计算该表达式。返回一个表示表达式值的整数。
注意：
有效的算符为 '+'、'-'、'*' 和 '/' 。
每个操作数（运算对象）都可以是一个整数或者另一个表达式。
两个整数之间的除法总是 向零截断 。
表达式中不含除零运算。
输入是一个根据逆波兰表示法表示的算术表达式。
答案及所有中间计算结果可以用 32 位 整数表示。

题目归纳：
向零取整：正数向下取整，负数向上取整。

解题思路：
(1) 解法： 逆波兰表达式求值 - leetcode官方题解
(2) 解法： 逆波兰表达式求值 - 负雪明烛民间题解

class Solution:def evalRPN(self, tokens: List[str]) -> int:stack = []for token in tokens:if token == "+":    num2 = stack.pop(-1)num1 = stack.pop(-1)stack.append(num1 + num2)elif token == "-":num2 = stack.pop(-1)num1 = stack.pop(-1)stack.append(num1 - num2)elif token == "*":num2 = stack.pop(-1)num1 = stack.pop(-1)stack.append(num1 * num2)elif token == "/":num2 = stack.pop(-1)num1 = stack.pop(-1)stack.append(int(num1 / num2)) # 向0取整else: # numberstack.append(int(token))return stack[0]

5. 基本计算器

题目链接：基本计算器 - leetcode
题目描述：
给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。注意:不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() 。

示例：
输入：s = “(1+(4+5+2)-3)+(6+8)”
输出：23

题目归纳：

解题思路：
(1) 解法： 基本计算器 - leetcode官方题解

class Solution:def calculate(self, s: str) -> int:# 括号展开+符号栈# 括号展开：将表达式中所有的括号展开，得到新表达式# 维护一个栈ops，其栈顶元素记录了当前位置所处的每个括号所共同形成的符号# 如：对于 1+2+(3-(4+5))# (1)扫描到1+2时，当前位置没有被任何括号所包含，ops栈顶元素为初始值+1# (2)扫描到1+2+(3时，当前位置被一个括号所包含，该括号前面的符号为 + 号，因此ops栈顶元素依然 +1；# (3)扫描到1+2+(3-(4时，当前位置被两个括号所包含，分别对应着 + 号和 − 号，由于 + 号和 − 号合并的结果为 − 号，因此栈顶元素变为 −1。# 由于只有加减，所以不需要考虑乘除对优先级的影响s = s.replace(" ","") # 去除空格ops = []ops.append(1) # +号sign = 1ret = 0n = len(s)i = 0while i < n:if s[i] == "+":sign = ops[-1] # top()i += 1elif s[i] == "-":sign = -ops[-1]i += 1elif s[i] == "(": ops.append(sign)i += 1elif s[i] == ")":ops.pop(-1)i += 1else: # 遇到了number的最高位，如"123"，但还需要把"123"变成真正的数值123num = 0while i < n and ord("0") <= ord(s[i]) and ord(s[i]) <= ord("9"):num = num*10 + ord(s[i]) - ord("0")i += 1ret += sign * numreturn ret