算法面试-最近的括号

前提:

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

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

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

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

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

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

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

力扣题目地址:https://leetcode-cn.com/problems/valid-parentheses/

题目:有效的括号

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

有效字符串需满足：

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

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