网站建设 部署与发布,杭州网站建设价格,好听的网络公司名称,西安到北京航班时刻表Leetcod面试经典150题刷题记录 —— 栈篇 1. 有效的括号2. 简化路径3. 最小栈4. 逆波兰表达式求值5. 基本计算器 1. 有效的括号 题目链接#xff1a;有效的括号 - leetcode 题目描述#xff1a; 给定一个只包括 ( #xff0c;)#xff0c;{#xff0c;}#xff0c;[… Leetcod面试经典150题刷题记录 —— 栈篇 1. 有效的括号2. 简化路径3. 最小栈4. 逆波兰表达式求值5. 基本计算器 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 False2. 简化路径 题目链接简化路径 - leetcode 题目描述 给你一个字符串 path 表示指向某一文件或目录的 Unix 风格 绝对路径 以 / 开头请你将其转化为更加简洁的规范路径。 在 Unix 风格的文件系统中一个点.表示当前目录本身此外两个点 .. 表示将目录切换到上一级指向父目录两者都可以是复杂相对路径的组成部分。任意多个连续的斜杠即//都被视为单个斜杠 / 。 对于此问题任何其他格式的点例如...均被视为文件/目录名称。 请注意返回的 规范路径 必须遵循下述格式 始终以斜杠 / 开头。 两个目录名之间必须只有一个斜杠 / 。 最后一个目录名如果存在不能 以 / 结尾。 此外路径仅包含从根目录到目标文件或目录的路径上的目录即不含 . 或 ..。 返回简化后得到的 规范路径 。 题目归纳 解题思路 (1) 解法 简化路径 - leetcode官方题解 class Solution:def simplifyPath(self, path: str) - str:# 使用栈结构# (1)将字符串path根据/分割成字符串数组pathspaths共包含以下元素# (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() 获取堆栈中的最小元素。 -231 val 231 - 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(452)-3)(68)” 输出23 题目归纳 解题思路 (1) 解法 基本计算器 - leetcode官方题解 class Solution:def calculate(self, s: str) - int:# 括号展开符号栈# 括号展开将表达式中所有的括号展开得到新表达式# 维护一个栈ops其栈顶元素记录了当前位置所处的每个括号所共同形成的符号# 如对于 12(3-(45))# (1)扫描到12时当前位置没有被任何括号所包含ops栈顶元素为初始值1# (2)扫描到12(3时当前位置被一个括号所包含该括号前面的符号为 号因此ops栈顶元素依然 1# (3)扫描到12(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
