一、前记(2/3)

果然之前留校一个人住宿感觉非常舒服,现在集中住宿导致我和室友的作息时间不太一样。惹不起惹不起,还是溜回家了。今天这篇blog是我在家里面写的,不得不感慨家里的机械键盘真好用,看显示器是真滴舒服。(啊哈哈哈哈哈哈)

二、题目描述

三、解题思路

u1s1,这个题目我是真的没想出来,只有卑微地看了看网上的解题思路,才恍然大悟到:“原来Python也还是会有栈这种做法”。

其实我一开始主要是解决不了括号里面的逻辑问题,就是:“{()}”和“{)}(”这种的逻辑问题,我们都知道第一个是对的,而第二个是错的,但是我应该怎么用计算机的逻辑将这个判断出来呢?(莫法,确实Python没想到会使用到栈。但是现在这种方法我学会了!!!)

在正确的方法里面,运用到了栈这个知识点。栈的具体内容不必详说,后面我学习一下之后会另写一篇有关于数据结构的博客。(也可以是为了考研而复习)。只需要知道的是栈遵循的是“先进后出,后进先出”的原则。在这个时候,我们可以思考一下,如果形如:“{}()”或者“{()}”的正确形式,我们如何利用栈来判断,是否正确?如果左括号:"(,{,["作为入栈,右括号:“),},]”作为出栈的标志,那么对于正确的形式,执行一遍之后栈为空。那么对于错误的形式:“{)}(”,“}{)(”,执行一遍之后,栈不为空。所以依照这样的思路,我们可以写出如下代码:

#encoding:utf-8
class Solution:
    def isValid(self, s: str) -> bool:
        #奇数一定是错误的
        if len(s)%2!=0:
            return False
        #创建字典(dict)和栈(stack)
        com_dict,stack={"]":"[","}":"{",")":"("},[]
        #遍历字符串内容
        for i in range(len(s)):
            #如果是左括号则入栈
            if s[i]=="(" or s[i]=="{" or s[i]=="[":
                stack.append(s[i])
            #如果是右括号则出栈,在这里为避免指针错误,所以一定要i>0
            elif i >0 and stack[-1]==com_dict[s[i]]:
                stack.pop()
            else:
                return False
        #空字符串也是返回的正确
        if len(stack) == 0:
            return True

        return False

#as a checking
solution=Solution()
a="{}()[]"
c=solution.isValid(a)
print(c)

结果和运行详情如下图所示:

四、另类算法解

在题解上面看到鬼才这样写的

class Solution:
    def isValid(self, s: str) -> bool:
        s_new = s.replace('()','').replace('[]','').replace('{}','')
        while len(s_new) < len(s):
            s = s_new
            s_new = s.replace('()','').replace('[]','').replace('{}','')
        return not s_new

🤣鬼才还是鬼才就是运行时间和占用内存不理想

五、学到了什么?

1、学习到了Python3的栈思想,后续会根据栈等数据结构进行学习并及时做好记录。