巧妙使用栈结构,解决面试中的算法问题
2022/7/12 1:31:17
本文主要是介绍巧妙使用栈结构,解决面试中的算法问题,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
每天进步一点点,关注我们哦,每天分享测试技术文章
本文章出自【码同学软件测试】
码同学公众号:自动化软件测试,领取资料可加:magetest
码同学抖音号:小码哥聊软件测试
前提
现在测试工程师的面试,或多或少都会问到编程技术.在编程技术中,往往会挑选一个简单的算法题.很多同学一看到这,往往就不知如何是好了.后果轻则被压低薪水,重则失去这次面试机会。
其实面试中的算法,可以通过刷题来进行准备.下面分享下最近面试遇到的算法面试题。
今日知识点:栈(Stack)结构
栈(Stack)在计算机世界中有三种含义,今天我们要说的是数据结构中的"栈"
栈(stack)是有序的元素集合。栈最显著的特征是LIFO (Last In, First Out, 后进先出)。一个经典的场景就是-蜘蛛纸牌
最后抽到的牌反而可以最先匹配调.
和字符串\列表这样常见的数据类型不同.栈需要我们手动编码来实现.下边借用力扣中一道和栈相关题目来进行讲解
力扣题目地址:http://navo.top/MFNJbu
免费领取码同学软件测试课程笔记+超多学习资料+完整视频+面试题,可加微信:magetest
题目:有效的括号
给定一个只包括 '(',')','{','}','[',']' 的字符串,判断字符串是否有效。
有效字符串需满足:
左括号必须用相同类型的右括号闭合。所有括号必须成对 左括号必须以正确的顺序闭合。左括号出现的顺序,和右括号出现的顺序要匹配 注意空字符串可被认为是有效字符串。处理异常值
示例 1:
输入: "()"
输出: true
示例 2:
输入: "()[]{}"
输出: true
示例 3:
输入: "(]"
输出: false
分析题目:
题目中的括号,可以理解为一个栈的匹配规则.即:
'('匹配')',
'{'匹配'}'
'['匹配']'
并且,'后进先出'.最后出现的左边括号.需要先匹配对应的右边.
如果匹配失败,根据题目的'正确顺序闭合'要求,认为该串无效
如果,括号没有完全匹配.根据题目'所有括号必须成对'.也认为该串无效
只有当所有括号均匹配时,该串有效
class Solution: def isValid(self, s: str) -> bool: if not s: return False # 栈:后进先出,先进后出 # 最后出现的 左边括号(左边只入栈) 必须最先匹配适当的 右边括号(右边只出栈).否则即为失败 # 对于左括号,只考虑入栈 # 所谓入栈,这里可以用加入一个列表来表示(栈中只有左括号) # 对于右括号,只考虑出栈 # 出栈的时候,按照"先进后出".只考虑匹配最后一个入栈. # 如果不符合,则匹配失败.则:右括号和左括号不匹配(} # 如果符合,则执行"出栈"即删除栈中的匹配的"左括号" # # 如果没有入栈,先进行出栈.会报列表异常 # 如果循环结束,栈中仍有"左括号"则:缺少右括号( dict_1 = {')': '(', '}': '{', ']': '['} # 用于查找出栈对应关系 l = '(', '{', '[' # 用于判断入栈 r = ')', ']', '}' # 用于判断出栈 stack = [] # 新建栈 for i in s: # 遍历字符 if i in l: # 判断入栈 stack.append(i) # 入栈 elif i in r: # 判断出栈 try: # 处理空栈时,出栈导致的异常 if stack[-1] == dict_1[i]: # 判断符合出栈标准,即 目前右括号匹配最后入栈的左括号 stack.pop(-1) # 出栈:"先进后出"即从最后(-1开始出栈) else: return False # 右括号和左括号不匹配(} except: return False # 空栈异常,必定不匹配 例如)( if len(stack) == 0: return True # 唯一的成功情况 else: return False # 栈没有匹配完全
免费领取码同学软件测试课程笔记+超多学习资料+学习完整视频 ☞ 可加:magetest/关注码同学公众号:自动化软件测试
本文著作权归作者所有,任何形式的转载都请联系作者获得授权并注明出处。
这篇关于巧妙使用栈结构,解决面试中的算法问题的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-11-01后台管理开发学习:新手入门指南
- 2024-11-01后台管理系统开发学习:新手入门教程
- 2024-11-01后台开发学习:从入门到实践的简单教程
- 2024-11-01后台综合解决方案学习:从入门到初级实战教程
- 2024-11-01接口模块封装学习入门教程
- 2024-11-01请求动作封装学习:新手入门教程
- 2024-11-01登录鉴权入门:新手必读指南
- 2024-11-01动态面包屑入门:轻松掌握导航设计技巧
- 2024-11-01动态权限入门:新手必读指南
- 2024-11-01动态主题处理入门:新手必读指南