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

LeetCode20:有效的括号

原题地址:. - 力扣(LeetCode)

题目描述

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

有效字符串需满足:

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

示例 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:有效的括号

原题地址&#xff1a;. - 力扣&#xff08;LeetCode&#xff09; 题目描述 给定一个只包括 (&#xff0c;)&#xff0c;{&#xff0c;}&#xff0c;[&#xff0c;] 的字符串 s &#xff0c;判断字符串是否有效。 有效字符串需满足&#xff1a; 左括号必须用相同类型的右括号闭合…...

简单介绍Class文件、Dex文件以及ELF文件

Class文件 Class文件是Java源代码文件经Java编译器编译后得到的Java字节码文件。对比Linux、Windows上的可执行文件而言&#xff0c;Class文件可以看作是Java虚拟机的可执行文件。 Dex文件 Dex文件是Android平台上与传统Class文件对应的Java字节码文件。Dex文件的核心内容与Cl…...

Vivo开奖了,劝退价。。

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

鸿蒙打包hvigorw clean报错No npmrc file is matched in the current user folder解决

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

无人机救援系统基本组成

无人机救援系统基本组成 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&#xff1a;git简介git入门教程2&#xff1a;git发展历史git入门教程3&#xff1a;安装配置git入门教程4&#xff1a;git工作流程git入门教程5&#xff1a;git仓库操作git入门教程6&#xff1a;git基本版本控制git入门教程7&#xff1a;git与远程仓库的交互git入门…...

AMBA:AHB_Slave_Mux的解析与HREADY、HREADYOUT

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

初始Linux (2) : 权限

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

在Mac下安装时间序列软件Hector

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

JVM1.8内存模型

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

windows C#-类型系统(上)

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

【酷狗音乐】逆向登录参数分析

mid、uuid参数 从cookie里面取值kg_mid&#xff0c;没有就生成 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第三次实验

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

基于LORA的一主多从监测系统_4G模块上巴法云

临时添加一个更新&#xff0c;更换云平台为巴法云&#xff0c;事情的起因是因为阿里云这个老六&#xff0c;早上睡了一觉起来发短信告诉我云平台给我停了&#xff0c;得交钱&#xff0c;好嘛&#xff0c;不过也没办法现在这基本都收费&#xff0c;当然还有onenet可以用&#xf…...

pip使用

pip全称pip install package,是python第三方包sitepackage管理的工具&#xff0c;安装&#xff0c;卸载第三方包。安装python时可以选择安装pip&#xff0c;或自己安装pip 查看pip是否安装&#xff1a;pip --version 安装pip &#xff1a;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()从键盘获取一个字符串&#xff0c;判断这个字符串在列表中是否存在(函数体不能使用in)&#xff0c;返回结果为True或False def exists_in_list(input_string, str_list):# 遍历列表中的每个元素for item in str_list:if item input_string: # 如果当前元素等于输…...

【YApi】接口管理平台

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

QNAP威联通NAS忘记密码怎么办?

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

eNSP-Cloud(实现本地电脑与eNSP内设备之间通信)

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

idea大量爆红问题解决

问题描述 在学习和工作中&#xff0c;idea是程序员不可缺少的一个工具&#xff0c;但是突然在有些时候就会出现大量爆红的问题&#xff0c;发现无法跳转&#xff0c;无论是关机重启或者是替换root都无法解决 就是如上所展示的问题&#xff0c;但是程序依然可以启动。 问题解决…...

React Native 开发环境搭建(全平台详解)

React Native 开发环境搭建&#xff08;全平台详解&#xff09; 在开始使用 React Native 开发移动应用之前&#xff0c;正确设置开发环境是至关重要的一步。本文将为你提供一份全面的指南&#xff0c;涵盖 macOS 和 Windows 平台的配置步骤&#xff0c;如何在 Android 和 iOS…...

Vue3 + Element Plus + TypeScript中el-transfer穿梭框组件使用详解及示例

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

渗透实战PortSwigger靶场-XSS Lab 14:大多数标签和属性被阻止

<script>标签被拦截 我们需要把全部可用的 tag 和 event 进行暴力破解 XSS cheat sheet&#xff1a; https://portswigger.net/web-security/cross-site-scripting/cheat-sheet 通过爆破发现body可以用 再把全部 events 放进去爆破 这些 event 全部可用 <body onres…...

从深圳崛起的“机器之眼”:赴港乐动机器人的万亿赛道赶考路

进入2025年以来&#xff0c;尽管围绕人形机器人、具身智能等机器人赛道的质疑声不断&#xff0c;但全球市场热度依然高涨&#xff0c;入局者持续增加。 以国内市场为例&#xff0c;天眼查专业版数据显示&#xff0c;截至5月底&#xff0c;我国现存在业、存续状态的机器人相关企…...

为什么需要建设工程项目管理?工程项目管理有哪些亮点功能?

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

HTML 列表、表格、表单

1 列表标签 作用&#xff1a;布局内容排列整齐的区域 列表分类&#xff1a;无序列表、有序列表、定义列表。 例如&#xff1a; 1.1 无序列表 标签&#xff1a;ul 嵌套 li&#xff0c;ul是无序列表&#xff0c;li是列表条目。 注意事项&#xff1a; ul 标签里面只能包裹 li…...

Golang dig框架与GraphQL的完美结合

将 Go 的 Dig 依赖注入框架与 GraphQL 结合使用&#xff0c;可以显著提升应用程序的可维护性、可测试性以及灵活性。 Dig 是一个强大的依赖注入容器&#xff0c;能够帮助开发者更好地管理复杂的依赖关系&#xff0c;而 GraphQL 则是一种用于 API 的查询语言&#xff0c;能够提…...

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&#xff0c;SRS管理页面端口是8080&#xff0c;可…...