5.3有效的括号(LC20-E)

2023-11-05 19:36
文章标签 括号 有效 5.3 lc20

本文主要是介绍5.3有效的括号(LC20-E),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

算法:

题目中:左括号必须以正确的顺序闭合。意思是,最后出现的左括号(对应着栈中的最后一个元素),应该先找到对应的闭合符号(右括号)

比如:s="( [ ) ]"就是False,因为"("比"["先出现,对应地,"( [ "中最后的元素应该最先找到闭合符"]",而 闭合符(就是右括号)先出现的是")",这个时候就能判断False了

括号匹配是使用栈解决的经典问题。

由于栈结构的特殊性,非常适合做对称匹配类的题目。

首先要弄清楚,字符串里的括号不匹配有几种情况。

1.第一种情况:字符串里左方向的括号多余了 ,所以不匹配。

2.第二种情况:括号没有多余,但是 括号的类型没有匹配上。

3.第三种情况:字符串里右方向的括号多余了,所以不匹配。

怎么用栈来解决该问题?

举个例子:s="(","[","}",")"

遍历字符串中的符号,发现左括号时,往栈中push其对应的右符号;发现右括号时,往栈中pop与其一样的右括号

当遍历到"(",push“)”  //stack=")"

当遍历到"[",push"]"  //stack="]" , ")"

当遍历到"}",push“}”  //stack=“}”, "]" , ")"

当遍历到")", pop ")"  //stack=“}”, "]" 

发现stack非空,说明括号无效。

总的代码思路如下(遍历s中的符号item):

1.如果 `item` 是一个开放符号(‘(’, ‘[’, ‘{’),则将相应的闭合符号压入栈中。

2.如果 `item` 是一个闭合符号(‘)’, ‘]’, ‘}’),则检查栈是否为空,或者栈顶元素(最后一个元素)与 `item` 不相等。

  • 栈为空:说明没有右括号了,肯定不对了
  • 栈顶元素(最后一个元素)与 `item` 不相等:说明最近的需要的闭合符号不对(和示例一样)
  • 如果以上任一条件为真,则意味着闭合符号不平衡,函数返回 `False`

3.如果 `item` 是一个闭合符号,并且它与栈顶元素匹配,那么从栈中弹出顶部元素,表示开放符号和闭合符号是平衡匹配的。

4.在遍历完 `s` 中的所有字符后,如果栈为空,则表示所有的开放符号都已经匹配并弹出,函数返回 `True`。否则,如果栈不为空,则表示存在未匹配的开放符号,函数返回 `False`

调试过程:

class Solution:def isValid(self, s: str) -> bool:stack = []for item in s:#如果s的长度为奇数,必然不符合,可以做个简单判断剪枝,节省时间if len(s)%2 != 0:return Falseelif item == "(":stack.append(")")elif item == "[":stack.append("]")elif item == "{":stack.append("}")#如果输入的不是以上三种左括号,那只能是右括号了#如果是右括号,正确的s对应的stack中应该存在该右括号了(刚刚append了)#如果此时stack为空,或者栈顶非距离最近的左括号的闭合符号,那就Falseelif not stack or item != stack[-1]:#注意:应该先判非空再判item != stack[-1],因为若stack为空,stack[-1]不存在,判断时就会报错return Falseelse:stack.pop()return True if stack == None else False

原因:最后返回语句写得不对。栈为空应该用“stack == []”或者“len(stack)==0”表示。

在Python中,`None` 表示一个空对象,而 `[]` 表示一个空列表。在这段代码中,我们使用一个列表来模拟栈的数据结构。当栈为空时,我们希望栈对象 `stack` 的值是一个空列表 `[]`

当使用 `stack == None` 进行判断时,它会检查栈对象 `stack` 是否是 `None`,而不是一个空列表。因此,如果栈为空,但是栈对象 `stack` 的值是 `None`,那么判断结果就会是错误的。

正确代码:

class Solution:def isValid(self, s: str) -> bool:stack = []for item in s:#如果s的长度为奇数,必然不符合,可以做个简单判断剪枝,节省时间if len(s)%2 != 0:return Falseelif item == "(":stack.append(")")elif item == "[":stack.append("]")elif item == "{":stack.append("}")#如果输入的不是以上三种左括号,那只能是右括号了#如果是右括号,正确的s对应的stack中应该存在该右括号了(刚刚append了)#如果此时stack为空,或者栈顶非距离最近的左括号的闭合符号,那就Falseelif not stack or item != stack[-1]:#注意:应该先判非空再判item != stack[-1],因为若stack为空,stack[-1]不存在,判断时就会报错return Falseelse:stack.pop()return True if stack == [] else False

时间空间复杂度:

  • 时间复杂度: O(n)
  • 空间复杂度: O(n)

这篇关于5.3有效的括号(LC20-E)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/352033

相关文章

Kali Linux安装实现教程(亲测有效)

《KaliLinux安装实现教程(亲测有效)》:本文主要介绍KaliLinux安装实现教程(亲测有效),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、下载二、安装总结一、下载1、点http://www.chinasem.cn击链接 Get Kali | Kal

一文教你PyCharm如何有效地添加源与库

《一文教你PyCharm如何有效地添加源与库》在使用PyCharm进行Python开发的时候,很多时候我们需要添加库或者设置源,下面我们就来和大家详细介绍一下如何在PyCharm中添加源和库吧... 在使用PyCharm进行python开发的时候,很多时候我们需要添加库或者设置源。这些操作可以帮助我们更方便

OpenManus本地部署实战亲测有效完全免费(最新推荐)

《OpenManus本地部署实战亲测有效完全免费(最新推荐)》文章介绍了如何在本地部署OpenManus大语言模型,包括环境搭建、LLM编程接口配置和测试步骤,本文给大家讲解的非常详细,感兴趣的朋友一... 目录1.概况2.环境搭建2.1安装miniconda或者anaconda2.2 LLM编程接口配置2

Linux虚拟机不显示IP地址的解决方法(亲测有效)

《Linux虚拟机不显示IP地址的解决方法(亲测有效)》本文主要介绍了通过VMware新装的Linux系统没有IP地址的解决方法,主要步骤包括:关闭虚拟机、打开VM虚拟网络编辑器、还原VMnet8或修... 目录前言步骤0.问题情况1.关闭虚拟机2.China编程打开VM虚拟网络编辑器3.1 方法一:点击还原VM

C++使用栈实现括号匹配的代码详解

《C++使用栈实现括号匹配的代码详解》在编程中,括号匹配是一个常见问题,尤其是在处理数学表达式、编译器解析等任务时,栈是一种非常适合处理此类问题的数据结构,能够精确地管理括号的匹配问题,本文将通过C+... 目录引言问题描述代码讲解代码解析栈的状态表示测试总结引言在编程中,括号匹配是一个常见问题,尤其是在

查询SQL Server数据库服务器IP地址的多种有效方法

《查询SQLServer数据库服务器IP地址的多种有效方法》作为数据库管理员或开发人员,了解如何查询SQLServer数据库服务器的IP地址是一项重要技能,本文将介绍几种简单而有效的方法,帮助你轻松... 目录使用T-SQL查询方法1:使用系统函数方法2:使用系统视图使用SQL Server Configu

浅谈主机加固,六种有效的主机加固方法

在数字化时代,数据的价值不言而喻,但随之而来的安全威胁也日益严峻。从勒索病毒到内部泄露,企业的数据安全面临着前所未有的挑战。为了应对这些挑战,一种全新的主机加固解决方案应运而生。 MCK主机加固解决方案,采用先进的安全容器中间件技术,构建起一套内核级的纵深立体防护体系。这一体系突破了传统安全防护的局限,即使在管理员权限被恶意利用的情况下,也能确保服务器的安全稳定运行。 普适主机加固措施:

损坏SD数据恢复的8种有效方法

SD卡被用于许多不同的产品来存储重要数据,如图片和重要的商业文件。如果您的SD卡坏了,您需要SD数据恢复来获取您的信息。通过从损坏的SD卡中取回数据,您可以确保重要文件不会永远丢失,这对于工作或个人原因是非常重要的。 有许多东西会损坏SD卡,因此有必要从中恢复数据。处理不当,如打碎或沾湿,会使卡无法使用。文件系统中的错误或错误倾倒都可能导致损坏。另一个需要好的SD卡恢复软件的常见问题是意外删除文

win7系统中C盘空间缩水的有效处理方法

一、深度剖析和完美解决   1、 休眠文件 hiberfil.sys :   该文件在C盘根目录为隐藏的系统文件,隐藏的这个hiberfil.sys文件大小正好和自己的物理内存是一致的,当你让电脑进入休眠状态时,Windows 7在关闭系统前将所有的内存内容写入Hiberfil.sys文件。   而后,当你重新打开电脑,操作系统使用Hiberfil.sys把所有信息放回内存,电脑

括号匹配问题(nyoj2)

括号配对问题 时间限制: 3000 ms  |  内存限制: 65535 KB 难度: 3 描述 现在,有一行括号序列,请你检查这行括号是否配对。 输入 第一行输入一个数N(0<N<=100),表示有N组测试数据。后面的N行输入多组输入数据,每组输入数据都是一个字符串S(S的长度小于10000,且S不是空串),测试数据组数少于5组。数据保证S中只含有"[","]","(",")"