查看原文
其他

【边学边敲边记】LeetCode008:有效的括号

老表的第一个一百万 简说Python 2019-05-25

一、写在前面

LeetCode 第七题 最接近的三数之和 传输门:LeetCode007 : 最接近的三数之和
今天给大家分享的是LeetCode 数组与字符串 第八题:有效的括号,为面试而生,期待你的加入。

二、今日题目

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

有效字符串需满足:
1.左括号必须用相同类型的右括号闭合。

2.左括号必须以正确的顺序闭合。


注意空字符串可被认为是有效字符串。
示例:

输入: "()"
输出: true

示例 2:

输入: "()[]{}"
输出: true

示例 3:

输入: "(]"
输出: false

示例 4:

输入: "([)]"
输出: false

示例 5:

输入: "{[]}"
输出: true

三、 分析

在《算法面试40讲》里有讲到这个题目,当时听老师讲的时候我想到我大二学《数据结构》时的一个题目:求一个表达式的值(比如:5*(3+2) ),当时用c语言做这个题花了两节课,计算表达式这个题比较麻烦的主要是运算优先级的判断,相比之下,只用判断括号是否有效(即匹配),就太小case了~思路分析如下:

我的思路

四、解题

  • 我的方法:

# 我的方法
class Solution:
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        reg_dict = {')':'(','}':'{',']':'['}
        # 括号匹配集
        temp_list = []
        # 临时存储栈
        for i in range(len(s)):
           if s[0] in reg_dict:
                return False
           if s[i] not in reg_dict: # 左括号,入栈
              temp_list.append(s[i])
           else:  # 右括号,取出栈顶,匹配
              if temp_list == []: # 有右括号无左括号可匹配
                 return False
              if not temp_list[-1] == reg_dict[s[i]]: # 左右括号不匹配
                 return False     
              temp_list.pop()  # 匹配成功出栈
        if temp_list != []:
            return False
        return True

  • 提交结果

100%秀不秀

测试数据:76组
运行时间:20ms
击败人百分比:100%

五、疑惑

值得一说的是,我最开始区分字符是左括号还是有括号用的是列表,然后运行结果在76.53%,也是做第一题两数之和的经验,然后选择了直接用字典,果然速度快多了,飙升到100%,这块,大家以后也可以多注意,一个小细节,改变你的命运,这也是老表的第一个100%,今天好好纪念一下。

六、结语

好的,最后再说两句,刷LeetCode已经一个多月了,虽然只刷了8题,但我觉得,我还是用心了的,同时也学到了很多东西。

现在带着读者刷LeetCode的公众号很多,我不敢说我是最厉害的,我只能说我能做到最用心,在题目分析、解题思路、最优解寻找中,而不是仅仅发一个能解出题目的代码,代码是死的,人是活的,思想是活的,我会继续坚持,一周最少两题。

另外,刷第一题就说了,坚持一个月后会建一个LeetCode算法刷题交流群,群其实找就建了,只是最开始为了方便管理和学习交流,只拉了几个研究生学长学姐,现在一个多月了,效果还不错,所以现在算法学习交流群面向所有读者开放,加我微信:zs820553471,备注:LeetCode 即可。

坚持 and 努力 : 终有所获。


END

维权路上

我今天,摊上了件大事!

进学习交流群

不失联,扫码加老表微信学习交流

温馨提示

欢迎大家转载,转发,留言,点赞支持老表

文末广告点一下也是对老表莫大的支持。

做知识的传播者,随手转发。


更多精彩推荐,请关注我们

你的支持是我原创的最大动力

    您可能也对以下帖子感兴趣

    文章有问题?点此查看未经处理的缓存