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

大话软工笔记—需求分析概述

需求分析&#xff0c;就是要对需求调研收集到的资料信息逐个地进行拆分、研究&#xff0c;从大量的不确定“需求”中确定出哪些需求最终要转换为确定的“功能需求”。 需求分析的作用非常重要&#xff0c;后续设计的依据主要来自于需求分析的成果&#xff0c;包括: 项目的目的…...

Zustand 状态管理库:极简而强大的解决方案

Zustand 是一个轻量级、快速和可扩展的状态管理库&#xff0c;特别适合 React 应用。它以简洁的 API 和高效的性能解决了 Redux 等状态管理方案中的繁琐问题。 核心优势对比 基本使用指南 1. 创建 Store // store.js import create from zustandconst useStore create((set)…...

黑马Mybatis

Mybatis 表现层&#xff1a;页面展示 业务层&#xff1a;逻辑处理 持久层&#xff1a;持久数据化保存 在这里插入图片描述 Mybatis快速入门 ![在这里插入图片描述](https://i-blog.csdnimg.cn/direct/6501c2109c4442118ceb6014725e48e4.png //logback.xml <?xml ver…...

Python实现prophet 理论及参数优化

文章目录 Prophet理论及模型参数介绍Python代码完整实现prophet 添加外部数据进行模型优化 之前初步学习prophet的时候&#xff0c;写过一篇简单实现&#xff0c;后期随着对该模型的深入研究&#xff0c;本次记录涉及到prophet 的公式以及参数调优&#xff0c;从公式可以更直观…...

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

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

基于SpringBoot在线拍卖系统的设计和实现

摘 要 随着社会的发展&#xff0c;社会的各行各业都在利用信息化时代的优势。计算机的优势和普及使得各种信息系统的开发成为必需。 在线拍卖系统&#xff0c;主要的模块包括管理员&#xff1b;首页、个人中心、用户管理、商品类型管理、拍卖商品管理、历史竞拍管理、竞拍订单…...

破解路内监管盲区:免布线低位视频桩重塑停车管理新标准

城市路内停车管理常因行道树遮挡、高位设备盲区等问题&#xff0c;导致车牌识别率低、逃费率高&#xff0c;传统模式在复杂路段束手无策。免布线低位视频桩凭借超低视角部署与智能算法&#xff0c;正成为破局关键。该设备安装于车位侧方0.5-0.7米高度&#xff0c;直接规避树枝遮…...

Pydantic + Function Calling的结合

1、Pydantic Pydantic 是一个 Python 库&#xff0c;用于数据验证和设置管理&#xff0c;通过 Python 类型注解强制执行数据类型。它广泛用于 API 开发&#xff08;如 FastAPI&#xff09;、配置管理和数据解析&#xff0c;核心功能包括&#xff1a; 数据验证&#xff1a;通过…...

Qt的学习(一)

1.什么是Qt Qt特指用来进行桌面应用开发&#xff08;电脑上写的程序&#xff09;涉及到的一套技术Qt无法开发网页前端&#xff0c;也不能开发移动应用。 客户端开发的重要任务&#xff1a;编写和用户交互的界面。一般来说和用户交互的界面&#xff0c;有两种典型风格&…...

统计学(第8版)——统计抽样学习笔记(考试用)

一、统计抽样的核心内容与问题 研究内容 从总体中科学抽取样本的方法利用样本数据推断总体特征&#xff08;均值、比率、总量&#xff09;控制抽样误差与非抽样误差 解决的核心问题 在成本约束下&#xff0c;用少量样本准确推断总体特征量化估计结果的可靠性&#xff08;置…...