算法大挑战

一、前记（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的栈思想，后续会根据栈等数据结构进行学习并及时做好记录。