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

2023-12-29 03:20

本文主要是介绍Leetcod面试经典150题刷题记录 —— 栈篇,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

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

-231 <= val <= 231 - 1
poptopgetMin 操作总是在 非空栈 上调用
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

这篇关于Leetcod面试经典150题刷题记录 —— 栈篇的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/548190

相关文章

字节面试 | 如何测试RocketMQ、RocketMQ?

字节面试:RocketMQ是怎么测试的呢? 答: 首先保证消息的消费正确、设计逆向用例,在验证消息内容为空等情况时的消费正确性; 推送大批量MQ,通过Admin控制台查看MQ消费的情况,是否出现消费假死、TPS是否正常等等问题。(上述都是临场发挥,但是RocketMQ真正的测试点,还真的需要探讨) 01 先了解RocketMQ 作为测试也是要简单了解RocketMQ。简单来说,就是一个分

秋招最新大模型算法面试,熬夜都要肝完它

💥大家在面试大模型LLM这个板块的时候,不知道面试完会不会复盘、总结,做笔记的习惯,这份大模型算法岗面试八股笔记也帮助不少人拿到过offer ✨对于面试大模型算法工程师会有一定的帮助,都附有完整答案,熬夜也要看完,祝大家一臂之力 这份《大模型算法工程师面试题》已经上传CSDN,还有完整版的大模型 AI 学习资料,朋友们如果需要可以微信扫描下方CSDN官方认证二维码免费领取【保证100%免费

Node.js学习记录(二)

目录 一、express 1、初识express 2、安装express 3、创建并启动web服务器 4、监听 GET&POST 请求、响应内容给客户端 5、获取URL中携带的查询参数 6、获取URL中动态参数 7、静态资源托管 二、工具nodemon 三、express路由 1、express中路由 2、路由的匹配 3、路由模块化 4、路由模块添加前缀 四、中间件

记录每次更新到仓库 —— Git 学习笔记 10

记录每次更新到仓库 文章目录 文件的状态三个区域检查当前文件状态跟踪新文件取消跟踪(un-tracking)文件重新跟踪(re-tracking)文件暂存已修改文件忽略某些文件查看已暂存和未暂存的修改提交更新跳过暂存区删除文件移动文件参考资料 咱们接着很多天以前的 取得Git仓库 这篇文章继续说。 文件的状态 不管是通过哪种方法,现在我们已经有了一个仓库,并从这个仓

java面试常见问题之Hibernate总结

1  Hibernate的检索方式 Ø  导航对象图检索(根据已经加载的对象,导航到其他对象。) Ø  OID检索(按照对象的OID来检索对象。) Ø  HQL检索(使用面向对象的HQL查询语言。) Ø  QBC检索(使用QBC(Qurey By Criteria)API来检索对象。 QBC/QBE离线/在线) Ø  本地SQL检索(使用本地数据库的SQL查询语句。) 包括Hibern

HotSpot虚拟机的经典垃圾收集器

读《深入理解Java虚拟机》第三版笔记。 关系 Serial、ParNew、Parallel Scavenge、Parallel Old、Serial Old(MSC)、Concurrent Mark Sweep (CMS)、Garbage First(G1)收集器。 如图: 1、Serial 和 Serial Old 收集器 2、ParNew 收集器 3、Parallel Sc

学习记录:js算法(二十八):删除排序链表中的重复元素、删除排序链表中的重复元素II

文章目录 删除排序链表中的重复元素我的思路解法一:循环解法二:递归 网上思路 删除排序链表中的重复元素 II我的思路网上思路 总结 删除排序链表中的重复元素 给定一个已排序的链表的头 head , 删除所有重复的元素,使每个元素只出现一次 。返回 已排序的链表 。 图一 图二 示例 1:(图一)输入:head = [1,1,2]输出:[1,2]示例 2:(图

STL经典案例(四)——实验室预约综合管理系统(项目涉及知识点很全面,内容有点多,耐心看完会有收获的!)

项目干货满满,内容有点过多,看起来可能会有点卡。系统提示读完超过俩小时,建议分多篇发布,我觉得分篇就不完整了,失去了这个项目的灵魂 一、需求分析 高校实验室预约管理系统包括三种不同身份:管理员、实验室教师、学生 管理员:给学生和实验室教师创建账号并分发 实验室教师:审核学生的预约申请 学生:申请使用实验室 高校实验室包括:超景深实验室(可容纳10人)、大数据实验室(可容纳20人)、物联网实验

贝壳面试:什么是回表?什么是索引下推?

尼恩说在前面 在40岁老架构师 尼恩的读者交流群(50+)中,最近有小伙伴拿到了一线互联网企业如得物、阿里、滴滴、极兔、有赞、希音、百度、网易、美团的面试资格,遇到很多很重要的面试题: 1.谈谈你对MySQL 索引下推 的认识? 2.在MySQL中,索引下推 是如何实现的?请简述其工作原理。 3、说说什么是 回表,什么是 索引下推 ? 最近有小伙伴在面试 贝壳、soul,又遇到了相关的

perl的学习记录——仿真regression

1 记录的背景 之前只知道有这个强大语言的存在,但一直侥幸自己应该不会用到它,所以一直没有开始学习。然而人生这么长,怎就确定自己不会用到呢? 这次要搭建一个可以自动跑完所有case并且打印每个case的pass信息到指定的文件中。从而减轻手动跑仿真,手动查看log信息的重复无效低质量的操作。下面简单记录下自己的思路并贴出自己的代码,方便自己以后使用和修正。 2 思路整理 作为一个IC d