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

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

本文章出自【码同学软件测试】

码同学公众号：自动化软件测试

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

  前提

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

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

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

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

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

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

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

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

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

  题目:有效的括号

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

有效字符串需满足：

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

示例 1:

输入: "()"

输出: true

示例 2:

输入: "()[]{}"

输出: true

示例 3:

输入: "(]"

输出: false

分析题目:

题目中的括号,可以理解为一个栈的匹配规则.即:

'('匹配')',

'{'匹配'}'

'['匹配']'

并且,'后进先出'.最后出现的左边括号.需要先匹配对应的右边.

如果匹配失败,根据题目的'正确顺序闭合'要求,认为该串无效

如果,括号没有完全匹配.根据题目'所有括号必须成对'.也认为该串无效

只有当所有括号均匹配时,该串有效

classSolution:

    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:  # 处理空栈时,出栈导致的异常

                    ifstack[-1] == dict_1[i]:  # 判断符合出栈标准,即 目前右括号匹配最后入栈的左括号 

                        stack.pop(-1)  # 出栈:"先进后出"即从最后(-1开始出栈)

                    else:

                        return False  # 右括号和左括号不匹配(}

                except:

                    return False  # 空栈异常,必定不匹配 例如)(

        if len(stack) == 0:

            return True  # 唯一的成功情况

        else:

            return False  # 栈没有匹配完全

免费领取码同学软件测试课程笔记+超多学习资料+学习完整视频，可以关注我们公众号哦：自动化软件测试

本文著作权归作者所有，任何形式的转载都请联系作者获得授权并注明出处。