LeetCode20:有效的括号
原题地址:. - 力扣(LeetCode)
题目描述
给定一个只包括
'('
,')'
,'{'
,'}'
,'['
,']'
的字符串s
,判断字符串是否有效。有效字符串需满足:
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 每个右括号都有一个对应的相同类型的左括号。
示例 1:
输入:s = "()"
输出:true
示例 2:
输入:s = "()[]{}"
输出:true
示例 3:
输入:s = "(]"
输出:false
示例 4:
输入:s = "([])"
输出:true
提示:
1 <= s.length <= 104
s
仅由括号'()[]{}'
组成
解题思路
- 输入检查:首先检查输入字符串是否为空或长度为零。如果是,则返回
true
,表示有效。- 长度检查:如果字符串的长度小于等于 1 或者是奇数,直接返回
false
,因为无法匹配成对的括号。- 使用栈:创建一个栈来存放左括号。遍历字符串中的每个字符:
- 如果当前字符是左括号
(
、[
或{
,将其压入栈中。- 如果当前字符是右括号
)
、]
或}
,则检查栈是否为空:
- 如果为空,说明没有左括号可以匹配,返回
false
。- 如果不为空,弹出栈顶元素并检查它是否与当前右括号匹配。如果不匹配,返回
false
。- 结束检查:遍历完成后,如果栈为空,说明所有的左括号都有对应的右括号,返回
true
;否则返回false
。
源码实现
class Solution {public boolean isValid(String s) {// 检查输入是否为空或长度为零if (s == null || s.length() == 0) {return true; // 空字符串被认为是有效的}// 检查长度是否小于等于1或为奇数if (s.length() <= 1 || s.length() % 2 != 0) {return false; // 不能成对匹配}// 创建一个栈来存放左括号Stack<Character> stack = new Stack<Character>();// 遍历字符串中的每个字符for (char c : s.toCharArray()) {// 如果是左括号,压入栈中if (c == '(' || c == '[' || c == '{') {stack.push(c);continue;}// 如果是右括号,检查栈是否为空if (stack.isEmpty()) {return false; // 没有对应的左括号}// 检查栈顶元素是否匹配if (c == ')' && stack.pop() != '(') {return false; // 不匹配} else if (c == ']' && stack.pop() != '[') {return false; // 不匹配} else if (c == '}' && stack.pop() != '{') {return false; // 不匹配}}// 如果栈为空,所有括号都匹配,返回true;否则返回falsereturn stack.isEmpty();}
}
复杂度分析
- 时间复杂度:O(n),其中 n 是字符串的长度。我们只需遍历字符串一次,栈的入栈和出栈操作的时间复杂度为 O(1)。
- 空间复杂度:O(n),在最坏的情况下,栈中可能会存放所有的左括号(例如字符串为 "((("),因此需要 O(n) 的空间。
相关文章:
LeetCode20:有效的括号
原题地址:. - 力扣(LeetCode) 题目描述 给定一个只包括 (,),{,},[,] 的字符串 s ,判断字符串是否有效。 有效字符串需满足: 左括号必须用相同类型的右括号闭合…...
简单介绍Class文件、Dex文件以及ELF文件
Class文件 Class文件是Java源代码文件经Java编译器编译后得到的Java字节码文件。对比Linux、Windows上的可执行文件而言,Class文件可以看作是Java虚拟机的可执行文件。 Dex文件 Dex文件是Android平台上与传统Class文件对应的Java字节码文件。Dex文件的核心内容与Cl…...

Vivo开奖了,劝退价。。
vivo 也开奖了,不过有小伙伴反馈是个劝退价,甚至不如隔壁的 oppo,要说这两家也是渊源颇深,一家是绿厂,一家是蓝厂,高管也都是早期步步高出来的。 给大家盘一下开奖的信息,方便大家横向做个对比&…...

鸿蒙打包hvigorw clean报错No npmrc file is matched in the current user folder解决
问题 在执行hvigorw clean等命令时,报错如下: Error: The hvigor depends on the npmrc file. No npmrc file is matched in the current user folder. Configure the npmrc file first解决方案 在用户当前目录下新建.npmrc文件,并配置如下…...

无人机救援系统基本组成
无人机救援系统基本组成 1. 源由2. 组成2.1 无人机载具2.1.1 多旋翼2.1.2 垂起固定翼2.1.3 智能避障2.1.4 物资投递 2.2 智能吊舱2.2.1 云台2.2.2 高清摄像2.2.3 红外热成像2.2.4 激光测距2.2.5 目标跟踪 2.3 通讯链路2.3.1 超长距离通信2.3.2 长距离通信2.3.3 中等距离通信 2.…...
git入门教程
git入门教程1:git简介git入门教程2:git发展历史git入门教程3:安装配置git入门教程4:git工作流程git入门教程5:git仓库操作git入门教程6:git基本版本控制git入门教程7:git与远程仓库的交互git入门…...

AMBA:AHB_Slave_Mux的解析与HREADY、HREADYOUT
相关阅读 AMBAhttps://blog.csdn.net/weixin_45791458/category_12800219.html?spm1001.2014.3001.5482 简介 从1999年的AMBA2发布以来,AHB协议中就存在数据选择器,如图1所示的AHB2协议的总线互连。 图1 AHB2的总线互连 这幅图画得比较粗糙࿰…...

初始Linux (2) : 权限
1. su [用户名]及权限概念 Linux中有两种用户:普通用户、超级用户 超级用户可以再 linux 系统下做任何事情,不受限制;而普通用户只能做有限的事情。 可以使用指令:su -快速进入root账户,但需要输入相关密码。 超级用…...

在Mac下安装时间序列软件Hector
1.软件介绍 Hector 是一款开源软件,专用于 GNSS 时间序列数据的处理与分析,广泛应用于地球科学研究。它帮助研究人员从 GNSS 数据中提取长期趋势、周期性成分,并建模噪声特性,用于地壳形变、地震影响和气候变化等方面的研究。Hec…...

JVM1.8内存模型
一、内存模型概览 本文介绍的是JDK1.8的内存模型。1.8同1.7相比,最大的差别就是元空间取代了永久代。元空间的本质和永久代类似,都是堆JVM规范中方法区的实现。不过元空间与永久代之间最大的区别在于:元空间并不存在虚拟机中,而是…...

windows C#-类型系统(上)
C# 是一种强类型语言。 每个变量和常量都有一个类型,每个求值的表达式也是如此。 每个方法声明都为每个输入参数和返回值指定名称、类型和种类(值、引用或输出)。 .NET 类库定义了内置数值类型和表示各种构造的复杂类型。 其中包括文件系统、网络连接、对象的集合和…...

【酷狗音乐】逆向登录参数分析
mid、uuid参数 从cookie里面取值kg_mid,没有就生成 dfid也是从cookie里面取的kg_dfid 清空cookie dfid "-"也是可以的 md5加密了一个随机uuid import uuid import hashlibuuid1 str(uuid.uuid4())def md5_encrypt(text):return hashlib.md5(text.enco…...
Jenkins面试整理-Jenkins Pipeline 是什么?
Jenkins Pipeline 是一种将 Jenkins 中的持续集成和持续交付(CI/CD)流程定义为代码的方式。Pipeline 提供了一种灵活、可维护的方式,通过脚本来描述构建、测试、部署等流程。Jenkins Pipeline 使用 Groovy 作为脚本语言,并可以通过 Jenkinsfile 来定义和管理流水线。 Jenki…...

RHCE第三次实验
要求 (1)学生信息网站只有song和tian两人可以访问,其他用户不能访问。 (2)访问缴费网站实现数据加密基于https访问。 架设一台NFS服务器,并按照以下要求配置 1、开放/nfs/shared目录,供所…...

基于LORA的一主多从监测系统_4G模块上巴法云
临时添加一个更新,更换云平台为巴法云,事情的起因是因为阿里云这个老六,早上睡了一觉起来发短信告诉我云平台给我停了,得交钱,好嘛,不过也没办法现在这基本都收费,当然还有onenet可以用…...

pip使用
pip全称pip install package,是python第三方包sitepackage管理的工具,安装,卸载第三方包。安装python时可以选择安装pip,或自己安装pip 查看pip是否安装:pip --version 安装pip :pip python -m pip install --upgrade…...
Django ORM详解:外键使用(外键逻辑关联)与查询优化
Django数据库迁移 # 创建迁移 python manage.py makemigrations your_app_name # 应用迁移 python manage.py migrate # 查看迁移状态 python manage.py showmigrations # 回滚迁移 python manage.py migrate your_app_name 0001 # 修改表后,删除迁移记录和表删除迁移记录后重…...
【Python】实战:使用input()从键盘获取一个字符串,判断这个字符串在列表中是否存在(函数体不能使用in),返回结果为True或False
使用input()从键盘获取一个字符串,判断这个字符串在列表中是否存在(函数体不能使用in),返回结果为True或False def exists_in_list(input_string, str_list):# 遍历列表中的每个元素for item in str_list:if item input_string: # 如果当前元素等于输…...

【YApi】接口管理平台
一、简介 YApi 是一个用于前后端开发团队协作的 API 管理平台,帮助团队更加高效地进行 API 接口的设计、测试、文档管理和版本控制等工作。 YApi 主要功能: API 设计和管理:提供 API 设计和文档生成工具,使开发者能够轻松创建、…...

QNAP威联通NAS忘记密码怎么办?
创作立场:原创不易,拒绝搬运~ hello 大家好,我是你们的老伙伴,稳重的大王~ 如题:在使用QNAP 威联通NAS期间,如果忘记密码,怎么去找回密码呢? 每台QNAP 威联通NAS,在机器…...

eNSP-Cloud(实现本地电脑与eNSP内设备之间通信)
说明: 想象一下,你正在用eNSP搭建一个虚拟的网络世界,里面有虚拟的路由器、交换机、电脑(PC)等等。这些设备都在你的电脑里面“运行”,它们之间可以互相通信,就像一个封闭的小王国。 但是&#…...

idea大量爆红问题解决
问题描述 在学习和工作中,idea是程序员不可缺少的一个工具,但是突然在有些时候就会出现大量爆红的问题,发现无法跳转,无论是关机重启或者是替换root都无法解决 就是如上所展示的问题,但是程序依然可以启动。 问题解决…...
React Native 开发环境搭建(全平台详解)
React Native 开发环境搭建(全平台详解) 在开始使用 React Native 开发移动应用之前,正确设置开发环境是至关重要的一步。本文将为你提供一份全面的指南,涵盖 macOS 和 Windows 平台的配置步骤,如何在 Android 和 iOS…...

Vue3 + Element Plus + TypeScript中el-transfer穿梭框组件使用详解及示例
使用详解 Element Plus 的 el-transfer 组件是一个强大的穿梭框组件,常用于在两个集合之间进行数据转移,如权限分配、数据选择等场景。下面我将详细介绍其用法并提供一个完整示例。 核心特性与用法 基本属性 v-model:绑定右侧列表的值&…...

渗透实战PortSwigger靶场-XSS Lab 14:大多数标签和属性被阻止
<script>标签被拦截 我们需要把全部可用的 tag 和 event 进行暴力破解 XSS cheat sheet: https://portswigger.net/web-security/cross-site-scripting/cheat-sheet 通过爆破发现body可以用 再把全部 events 放进去爆破 这些 event 全部可用 <body onres…...

从深圳崛起的“机器之眼”:赴港乐动机器人的万亿赛道赶考路
进入2025年以来,尽管围绕人形机器人、具身智能等机器人赛道的质疑声不断,但全球市场热度依然高涨,入局者持续增加。 以国内市场为例,天眼查专业版数据显示,截至5月底,我国现存在业、存续状态的机器人相关企…...

为什么需要建设工程项目管理?工程项目管理有哪些亮点功能?
在建筑行业,项目管理的重要性不言而喻。随着工程规模的扩大、技术复杂度的提升,传统的管理模式已经难以满足现代工程的需求。过去,许多企业依赖手工记录、口头沟通和分散的信息管理,导致效率低下、成本失控、风险频发。例如&#…...

HTML 列表、表格、表单
1 列表标签 作用:布局内容排列整齐的区域 列表分类:无序列表、有序列表、定义列表。 例如: 1.1 无序列表 标签:ul 嵌套 li,ul是无序列表,li是列表条目。 注意事项: ul 标签里面只能包裹 li…...
Golang dig框架与GraphQL的完美结合
将 Go 的 Dig 依赖注入框架与 GraphQL 结合使用,可以显著提升应用程序的可维护性、可测试性以及灵活性。 Dig 是一个强大的依赖注入容器,能够帮助开发者更好地管理复杂的依赖关系,而 GraphQL 则是一种用于 API 的查询语言,能够提…...

srs linux
下载编译运行 git clone https:///ossrs/srs.git ./configure --h265on make 编译完成后即可启动SRS # 启动 ./objs/srs -c conf/srs.conf # 查看日志 tail -n 30 -f ./objs/srs.log 开放端口 默认RTMP接收推流端口是1935,SRS管理页面端口是8080,可…...