当前位置: 首页 > news >正文

LeetCode_20_简单_有效的括号

文章目录

  • 1. 题目
  • 2. 思路及代码实现(Python)
    • 2.1 栈


1. 题目

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

有效字符串需满足:

  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。
  3. 每个右括号都有一个对应的相同类型的左括号。

示例 1:

输入:s = "()"
输出:true

示例 2:

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

示例 3:

输入:s = "(]"
输出:false


提示

  • 1 < = s . l e n g t h < = 1 0 4 1 <= s.length <= 10^4 1<=s.length<=104
  • s 仅由括号 '()[]{}' 组成

2. 思路及代码实现(Python)

2.1 栈

判断括号的有效性可以使用「栈」这一数据结构来解决。

我们遍历给定的字符串 s。当我们遇到一个左括号时,我们会期望在后续的遍历中,有一个相同类型的右括号将其闭合。由于后遇到的左括号要先闭合,因此我们可以将这个左括号放入栈顶。

当我们遇到一个右括号时,我们需要将一个相同类型的左括号闭合。此时,我们可以取出栈顶的左括号并判断它们是否是相同类型的括号。如果不是相同的类型,或者栈中并没有左括号,那么字符串 s 无效,返回 False \text{False} False。为了快速判断括号的类型,我们可以使用哈希表存储每一种括号。哈希表的键为右括号,值为相同类型的左括号。

在遍历结束后,如果栈中没有左括号,说明我们将字符串 s 中的所有左括号闭合,返回 True \text{True} True,否则返回 False \text{False} False。注意到有效字符串(只包含括号)的长度一定为偶数,因此如果字符串的长度为奇数,我们可以直接返回 False \text{False} False,省去后续的遍历判断过程。

该算法时间复杂度为 O ( n ) O(n) O(n),其中 n n n 是字符串 s s s 的长度;算法空间复杂度为存储了的字符串长度大小与存储括号总类的哈希表大小之和。

class Solution:def isValid(self, s: str) -> bool:if len(s) % 2 == 1:return Falsepairs = {")": "(","]": "[","}": "{",}stack = list()for ch in s:if ch in pairs:if not stack or stack[-1] != pairs[ch]:return Falsestack.pop()else:stack.append(ch)return not stack

执行用时:44 ms
消耗内存:16.44 MB

题解来源:力扣官方题解

相关文章:

LeetCode_20_简单_有效的括号

文章目录 1. 题目2. 思路及代码实现&#xff08;Python&#xff09;2.1 栈 1. 题目 给定一个只包括 (&#xff0c;)&#xff0c;{&#xff0c;}&#xff0c;[&#xff0c;] 的字符串 s &#xff0c;判断字符串是否有效。 有效字符串需满足&#xff1a; 左括号必须用相同类型…...

gRPC 备查

简介 HTTP/2 HTTP/2 的三个概念 架构 使用流程 gRPC 的接口类型 1.单一RPC 2.服务器流式RPC 3.客户端式流式RPC 4.双向流式RPC...

MySQL 基础知识(十)之 MySQL 架构

目录 1 MySQL 架构说明 2 连接层 3 核心业务层 3.1 查询缓存 3.2 解析器 3.3 优化器 3.4 执行器 4 存储引擎层 5 参考文档 1 MySQL 架构说明 下图是 MySQL 5.7 及其之前版本的逻辑架构示意图 MySQL 架构大致可分为以下三层&#xff1a; 连接层&#xff1a;负责跟客户…...

[晓理紫]每日论文分享(有中文摘要,源码或项目地址)--大模型、扩散模型

专属领域论文订阅 VX关注{晓理紫},每日更新论文,如感兴趣,请转发给有需要的同学,谢谢支持 如果你感觉对你有所帮助,请关注我,每日准时为你推送最新论文。 为了答谢各位网友的支持,从今日起免费为300名读者提供订阅主题论文服务,只需VX关注公号并回复{邮箱+论文主题}(如…...

Delphi v11 安卓权限申请

问题 Delphi 10.4 的安卓权限申请代码&#xff0c;在 Delphi 11 下面编译无法通过。 原因 原因是里面有几个变量类型的定义有所不同。 procedure TDmBLE.RequestPermissionsResult(Sender: TObject; const APermissions: TArray<string>; const AGrantResults: TAr…...

频谱仿真平台HTZ Communications为私有5G建设铺平道路

韩国的国家监管机构韩国通信委员会&#xff08;KCA&#xff09;计划在德思特频谱仿真平台HTZ Communications的支持下加快扩大无线电接入范围&#xff0c;提升全国电信服务的质量和效率。 韩国通信委员会&#xff08;KCA&#xff09;在韩国的监管环境中扮演着至关重要的角色&am…...

【高效开发工具系列】PyCharm使用

&#x1f49d;&#x1f49d;&#x1f49d;欢迎来到我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐:kwan 的首页,持续学…...

进程终止与进程等待

fork 函数 fork 函数是 Linux 中一个非常重要的函数&#xff0c;它的作用是从已存在的进程中创建一个新进程。这个新进程就是当前进程的子进程。 fork() 函数使用方法&#xff1a;它在头文件 #include <unistd.h> 中&#xff0c;函数原型为 pid_t fork(void); 用一个…...

MySQL 基础知识(六)之数据查询(二)

目录 6 数值型函数 7 字符串函数 8 流程控制函数 9 聚合函数 10 分组查询 (group by) 11 分组过滤 (having) 12 限定查询 (limit) 13 多表查询 13.1 连接条件关键词 (on、using) 13.2 连接算法 13.3 交叉连接 (cross join) 13.4 内连接 (inner join) 13.5 外连接 …...

蓝桥杯嵌入式STM32G431RBT6知识点(主观题部分)

目录 1 前置准备 1.1 Keil 1.1.1 编译器版本及微库 1.1.2 添加官方提供的LCD及I2C文件 1.2 CubeMX 1.2.1 时钟树 1.2.2 其他 1.2.3 明确CubeMX路径&#xff0c;放置芯片包 2 GPIO 2.1 实验1&#xff1a;LED1-LED8循环亮灭 ​编辑 2.2 实验2&#xff1a…...

ELAdmin 部署

后端部署 按需修改 application-prod.yml 例如验证码方式、登录状态到期时间等等。 修改完成后打好 Jar 包 执行完成后会生成最终可执行的 jar。JPA版本是 2.6&#xff0c;MyBatis 版本是 1.1。 启动命令 nohup java -jar eladmin-system-2.6.jar --spring.profiles.active…...

计算机功能简介:EC, NVMe, SCSI/ISCSI与块存储接口 RBD,NUMA

一 EC是指Embedded Controller 主要应用于移动计算机系统和嵌入式计算机系统中&#xff0c;为此类计算机提供系统管理功能。EC的主要功能是控制计算机主板上电时序、管理电池充电和放电&#xff0c;提供键盘矩阵接口、智能风扇接口、串口、GPIO、PS/2等常规IO功能&#xff0c;…...

linux上安装bluesky的步骤

1、设备上安装的操作系统如下&#xff1a; orangepiorangepi5b:~$ lsb_release -a No LSB modules are available. Distributor ID: Ubuntu Description: Ubuntu 22.04.2 LTS Release: 22.04 Codename: jammy 2、在用户家目录下创建一个目录miniconda3目录&a…...

视频监控需求八问:视频智能分析/视频汇聚平台EasyCVR有何特性?

最近TSINGSEE青犀视频在与业内伙伴进行项目合作的过程中&#xff0c;针对安防监控可视化视频管理系统EasyCVR视频融合平台在电信运营商项目中的应用&#xff0c;进行了多方面的项目需求沟通。今天我们就该项目沟通为案例&#xff0c;来具体了解一下用户关心度较高的关于视频智能…...

django rest framework 学习笔记2

注意&#xff1a;该文章部分摘抄之百度&#xff0c;仅当做学习笔记供小白使用&#xff0c;若侵权请联系删除&#xff01; 显示关联表的数据&#xff0c;本示例会显示所有的关联的数据信息 from rest_framework import serializers from .models import Student class StudentM…...

第四篇【传奇开心果系列】Python文本和语音相互转换库技术点案例示例:pyttsx3自动化脚本经典案例

传奇开心果短博文系列 系列短博文目录Python文本和语音相互转换库技术点案例示例系列 短博文目录前言一、雏形示例代码二、扩展思路介绍三、批量处理文本示例代码四、自定义语音设置示例代码五、结合其他库和API示例代码六、语音交互系统示例代码七、多语言支持示例代码八、添加…...

model.train()和model.eval()两种模式的原理

1. model.train() 在使用 pytorch 构建神经网络的时候&#xff0c;训练过程中会在程序上方添加一句model.train()&#xff0c;作用是 启用 batch normalization 和 dropout 。 如果模型中有BN层&#xff08;Batch Normalization&#xff09;和 Dropout &#xff0c;需要在 训练…...

docker的底层原理六: 联合文件系统(UnionFS)

Docker的底层存储原理基于联合文件系统&#xff08;UnionFS&#xff09;。 联合文件系统&#xff08;UnionFS&#xff09;是一种特殊的文件系统&#xff0c;它允许独立地叠加多个目录层&#xff0c;呈现给用户的是这些目录层的联合视图。这种结构使得在Docker中&#xff0c;不…...

【动态规划专栏】专题一:斐波那契数列模型--------1.第N个泰波那契数

本专栏内容为&#xff1a;算法学习专栏&#xff0c;分为优选算法专栏&#xff0c;贪心算法专栏&#xff0c;动态规划专栏以及递归&#xff0c;搜索与回溯算法专栏四部分。 通过本专栏的深入学习&#xff0c;你可以了解并掌握算法。 &#x1f493;博主csdn个人主页&#xff1a;小…...

自养号测评低成本高效率推广,安全可控

测评的作用在于让用户更真实、清晰、快捷地了解产品以及产品的使用方法和体验。通过买家对产品的测评&#xff0c;也可以帮助厂商和卖家优化产品缺陷&#xff0c;提高用户的使用体验。这进而帮助他们获得更好的销量&#xff0c;并更深入地了解市场需求。因此&#xff0c;测评在…...

深度学习在微纳光子学中的应用

深度学习在微纳光子学中的主要应用方向 深度学习与微纳光子学的结合主要集中在以下几个方向&#xff1a; 逆向设计 通过神经网络快速预测微纳结构的光学响应&#xff0c;替代传统耗时的数值模拟方法。例如设计超表面、光子晶体等结构。 特征提取与优化 从复杂的光学数据中自…...

挑战杯推荐项目

“人工智能”创意赛 - 智能艺术创作助手&#xff1a;借助大模型技术&#xff0c;开发能根据用户输入的主题、风格等要求&#xff0c;生成绘画、音乐、文学作品等多种形式艺术创作灵感或初稿的应用&#xff0c;帮助艺术家和创意爱好者激发创意、提高创作效率。 ​ - 个性化梦境…...

HTML 语义化

目录 HTML 语义化HTML5 新特性HTML 语义化的好处语义化标签的使用场景最佳实践 HTML 语义化 HTML5 新特性 标准答案&#xff1a; 语义化标签&#xff1a; <header>&#xff1a;页头<nav>&#xff1a;导航<main>&#xff1a;主要内容<article>&#x…...

2025年能源电力系统与流体力学国际会议 (EPSFD 2025)

2025年能源电力系统与流体力学国际会议&#xff08;EPSFD 2025&#xff09;将于本年度在美丽的杭州盛大召开。作为全球能源、电力系统以及流体力学领域的顶级盛会&#xff0c;EPSFD 2025旨在为来自世界各地的科学家、工程师和研究人员提供一个展示最新研究成果、分享实践经验及…...

【快手拥抱开源】通过快手团队开源的 KwaiCoder-AutoThink-preview 解锁大语言模型的潜力

引言&#xff1a; 在人工智能快速发展的浪潮中&#xff0c;快手Kwaipilot团队推出的 KwaiCoder-AutoThink-preview 具有里程碑意义——这是首个公开的AutoThink大语言模型&#xff08;LLM&#xff09;。该模型代表着该领域的重大突破&#xff0c;通过独特方式融合思考与非思考…...

高危文件识别的常用算法:原理、应用与企业场景

高危文件识别的常用算法&#xff1a;原理、应用与企业场景 高危文件识别旨在检测可能导致安全威胁的文件&#xff0c;如包含恶意代码、敏感数据或欺诈内容的文档&#xff0c;在企业协同办公环境中&#xff08;如Teams、Google Workspace&#xff09;尤为重要。结合大模型技术&…...

【单片机期末】单片机系统设计

主要内容&#xff1a;系统状态机&#xff0c;系统时基&#xff0c;系统需求分析&#xff0c;系统构建&#xff0c;系统状态流图 一、题目要求 二、绘制系统状态流图 题目&#xff1a;根据上述描述绘制系统状态流图&#xff0c;注明状态转移条件及方向。 三、利用定时器产生时…...

【JavaSE】绘图与事件入门学习笔记

-Java绘图坐标体系 坐标体系-介绍 坐标原点位于左上角&#xff0c;以像素为单位。 在Java坐标系中,第一个是x坐标,表示当前位置为水平方向&#xff0c;距离坐标原点x个像素;第二个是y坐标&#xff0c;表示当前位置为垂直方向&#xff0c;距离坐标原点y个像素。 坐标体系-像素 …...

Spring AI与Spring Modulith核心技术解析

Spring AI核心架构解析 Spring AI&#xff08;https://spring.io/projects/spring-ai&#xff09;作为Spring生态中的AI集成框架&#xff0c;其核心设计理念是通过模块化架构降低AI应用的开发复杂度。与Python生态中的LangChain/LlamaIndex等工具类似&#xff0c;但特别为多语…...

算法笔记2

1.字符串拼接最好用StringBuilder&#xff0c;不用String 2.创建List<>类型的数组并创建内存 List arr[] new ArrayList[26]; Arrays.setAll(arr, i -> new ArrayList<>()); 3.去掉首尾空格...