当前位置: 首页 > 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;测评在…...

Day131 | 灵神 | 回溯算法 | 子集型 子集

Day131 | 灵神 | 回溯算法 | 子集型 子集 78.子集 78. 子集 - 力扣&#xff08;LeetCode&#xff09; 思路&#xff1a; 笔者写过很多次这道题了&#xff0c;不想写题解了&#xff0c;大家看灵神讲解吧 回溯算法套路①子集型回溯【基础算法精讲 14】_哔哩哔哩_bilibili 完…...

IT供电系统绝缘监测及故障定位解决方案

随着新能源的快速发展&#xff0c;光伏电站、储能系统及充电设备已广泛应用于现代能源网络。在光伏领域&#xff0c;IT供电系统凭借其持续供电性好、安全性高等优势成为光伏首选&#xff0c;但在长期运行中&#xff0c;例如老化、潮湿、隐裂、机械损伤等问题会影响光伏板绝缘层…...

均衡后的SNRSINR

本文主要摘自参考文献中的前两篇&#xff0c;相关文献中经常会出现MIMO检测后的SINR不过一直没有找到相关数学推到过程&#xff0c;其中文献[1]中给出了相关原理在此仅做记录。 1. 系统模型 复信道模型 n t n_t nt​ 根发送天线&#xff0c; n r n_r nr​ 根接收天线的 MIMO 系…...

10-Oracle 23 ai Vector Search 概述和参数

一、Oracle AI Vector Search 概述 企业和个人都在尝试各种AI&#xff0c;使用客户端或是内部自己搭建集成大模型的终端&#xff0c;加速与大型语言模型&#xff08;LLM&#xff09;的结合&#xff0c;同时使用检索增强生成&#xff08;Retrieval Augmented Generation &#…...

[ACTF2020 新生赛]Include 1(php://filter伪协议)

题目 做法 启动靶机&#xff0c;点进去 点进去 查看URL&#xff0c;有 ?fileflag.php说明存在文件包含&#xff0c;原理是php://filter 协议 当它与包含函数结合时&#xff0c;php://filter流会被当作php文件执行。 用php://filter加编码&#xff0c;能让PHP把文件内容…...

深入理解Optional:处理空指针异常

1. 使用Optional处理可能为空的集合 在Java开发中&#xff0c;集合判空是一个常见但容易出错的场景。传统方式虽然可行&#xff0c;但存在一些潜在问题&#xff1a; // 传统判空方式 if (!CollectionUtils.isEmpty(userInfoList)) {for (UserInfo userInfo : userInfoList) {…...

uniapp 小程序 学习(一)

利用Hbuilder 创建项目 运行到内置浏览器看效果 下载微信小程序 安装到Hbuilder 下载地址 &#xff1a;开发者工具默认安装 设置服务端口号 在Hbuilder中设置微信小程序 配置 找到运行设置&#xff0c;将微信开发者工具放入到Hbuilder中&#xff0c; 打开后出现 如下 bug 解…...

Python 训练营打卡 Day 47

注意力热力图可视化 在day 46代码的基础上&#xff0c;对比不同卷积层热力图可视化的结果 import torch import torch.nn as nn import torch.optim as optim from torchvision import datasets, transforms from torch.utils.data import DataLoader import matplotlib.pypl…...

ubuntu系统文件误删(/lib/x86_64-linux-gnu/libc.so.6)修复方案 [成功解决]

报错信息&#xff1a;libc.so.6: cannot open shared object file: No such file or directory&#xff1a; #ls, ln, sudo...命令都不能用 error while loading shared libraries: libc.so.6: cannot open shared object file: No such file or directory重启后报错信息&…...

网络安全问题及对策研究

摘 要 网络安全问题一直是近年来社会乃至全世界十分关注的重要性问题&#xff0c;网络关乎着我们的生活&#xff0c;政治&#xff0c;经济等多个方面&#xff0c;致力解决网络安全问题以及给出行之有效的安全策略是网络安全领域的一大目标。 本论文简述了课题的开发背景&…...