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

Java 语言特性(面试系列1)

一、面向对象编程 1. 封装&#xff08;Encapsulation&#xff09; 定义&#xff1a;将数据&#xff08;属性&#xff09;和操作数据的方法绑定在一起&#xff0c;通过访问控制符&#xff08;private、protected、public&#xff09;隐藏内部实现细节。示例&#xff1a; public …...

日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする

日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする 1、前言(1)情况说明(2)工程师的信仰2、知识点(1) にする1,接续:名词+にする2,接续:疑问词+にする3,(A)は(B)にする。(2)復習:(1)复习句子(2)ために & ように(3)そう(4)にする3、…...

在鸿蒙HarmonyOS 5中实现抖音风格的点赞功能

下面我将详细介绍如何使用HarmonyOS SDK在HarmonyOS 5中实现类似抖音的点赞功能&#xff0c;包括动画效果、数据同步和交互优化。 1. 基础点赞功能实现 1.1 创建数据模型 // VideoModel.ets export class VideoModel {id: string "";title: string ""…...

抖音增长新引擎:品融电商,一站式全案代运营领跑者

抖音增长新引擎&#xff1a;品融电商&#xff0c;一站式全案代运营领跑者 在抖音这个日活超7亿的流量汪洋中&#xff0c;品牌如何破浪前行&#xff1f;自建团队成本高、效果难控&#xff1b;碎片化运营又难成合力——这正是许多企业面临的增长困局。品融电商以「抖音全案代运营…...

spring:实例工厂方法获取bean

spring处理使用静态工厂方法获取bean实例&#xff0c;也可以通过实例工厂方法获取bean实例。 实例工厂方法步骤如下&#xff1a; 定义实例工厂类&#xff08;Java代码&#xff09;&#xff0c;定义实例工厂&#xff08;xml&#xff09;&#xff0c;定义调用实例工厂&#xff…...

数据链路层的主要功能是什么

数据链路层&#xff08;OSI模型第2层&#xff09;的核心功能是在相邻网络节点&#xff08;如交换机、主机&#xff09;间提供可靠的数据帧传输服务&#xff0c;主要职责包括&#xff1a; &#x1f511; 核心功能详解&#xff1a; 帧封装与解封装 封装&#xff1a; 将网络层下发…...

云原生安全实战:API网关Kong的鉴权与限流详解

&#x1f525;「炎码工坊」技术弹药已装填&#xff01; 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 一、基础概念 1. API网关&#xff08;API Gateway&#xff09; API网关是微服务架构中的核心组件&#xff0c;负责统一管理所有API的流量入口。它像一座…...

【MATLAB代码】基于最大相关熵准则(MCC)的三维鲁棒卡尔曼滤波算法(MCC-KF),附源代码|订阅专栏后可直接查看

文章所述的代码实现了基于最大相关熵准则(MCC)的三维鲁棒卡尔曼滤波算法(MCC-KF),针对传感器观测数据中存在的脉冲型异常噪声问题,通过非线性加权机制提升滤波器的抗干扰能力。代码通过对比传统KF与MCC-KF在含异常值场景下的表现,验证了后者在状态估计鲁棒性方面的显著优…...

Vite中定义@软链接

在webpack中可以直接通过符号表示src路径&#xff0c;但是vite中默认不可以。 如何实现&#xff1a; vite中提供了resolve.alias&#xff1a;通过别名在指向一个具体的路径 在vite.config.js中 import { join } from pathexport default defineConfig({plugins: [vue()],//…...

从面试角度回答Android中ContentProvider启动原理

Android中ContentProvider原理的面试角度解析&#xff0c;分为​​已启动​​和​​未启动​​两种场景&#xff1a; 一、ContentProvider已启动的情况 1. ​​核心流程​​ ​​触发条件​​&#xff1a;当其他组件&#xff08;如Activity、Service&#xff09;通过ContentR…...