巧妙使用栈结构，解决面试中的算法问题

每天进步一点点，关注我们哦，每天分享测试技术文章

码同学抖音 ：小码哥聊软件测试

前提

现在测试工程师的面试,或多或少都会问到编程技术.在编程技术中,往往会挑选一个简单的算法题.很多同学一看到这,往往就不知如何是好了.后果轻则被压低薪水,重则失去这次面试机会。

其实面试中的算法,可以通过刷题来进行准备.下面分享下最近面试遇到的算法面试题。

今日知识点：栈(Stack)结构

栈(Stack)在计算机世界中有三种含义,今天我们要说的是数据结构中的”栈”

栈(stack)是有序的元素集合。栈最显著的特征是LIFO (Last In, First Out, 后进先出)。一个经典的场景就是-蜘蛛纸牌

最后抽到的牌反而可以最先匹配调.

和字符串列表这样常见的数据类型不同.栈需要我们手动编码来实现.下边借用力扣中一道和栈相关题目来进行讲解

力扣题目地址:http://navo.top/MFNJbu

免费领取 码同学软件测试 课程笔记+超多学习资料+完整视频+最新面试题，可以转发文章 + 私信「码同学666」获取资料哦

题目:有效的括

给定一个只包括 ‘(‘，’)’，'{‘，’}’，'[‘，’]’ 的字符串，判断字符串是否有效。

有效字符串需满足：

左括 必须用相同类型的右括 闭合。所有括 必须成对 左括 必须以正确的顺序闭合。左括 出现的顺序,和右括 出现的顺序要匹配 注意空字符串可被认为是有效字符串。处理异常值

示例 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  # 栈没有匹配完全