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

变量 varablie 声明- Rust 变量 let mut 声明与 C/C++ 变量声明对比分析

一、变量声明设计&#xff1a;let 与 mut 的哲学解析 Rust 采用 let 声明变量并通过 mut 显式标记可变性&#xff0c;这种设计体现了语言的核心哲学。以下是深度解析&#xff1a; 1.1 设计理念剖析 安全优先原则&#xff1a;默认不可变强制开发者明确声明意图 let x 5; …...

C++_核心编程_多态案例二-制作饮品

#include <iostream> #include <string> using namespace std;/*制作饮品的大致流程为&#xff1a;煮水 - 冲泡 - 倒入杯中 - 加入辅料 利用多态技术实现本案例&#xff0c;提供抽象制作饮品基类&#xff0c;提供子类制作咖啡和茶叶*//*基类*/ class AbstractDr…...

C++:std::is_convertible

C++标志库中提供is_convertible,可以测试一种类型是否可以转换为另一只类型: template <class From, class To> struct is_convertible; 使用举例: #include <iostream> #include <string>using namespace std;struct A { }; struct B : A { };int main…...

React hook之useRef

React useRef 详解 useRef 是 React 提供的一个 Hook&#xff0c;用于在函数组件中创建可变的引用对象。它在 React 开发中有多种重要用途&#xff0c;下面我将全面详细地介绍它的特性和用法。 基本概念 1. 创建 ref const refContainer useRef(initialValue);initialValu…...

FFmpeg 低延迟同屏方案

引言 在实时互动需求激增的当下&#xff0c;无论是在线教育中的师生同屏演示、远程办公的屏幕共享协作&#xff0c;还是游戏直播的画面实时传输&#xff0c;低延迟同屏已成为保障用户体验的核心指标。FFmpeg 作为一款功能强大的多媒体框架&#xff0c;凭借其灵活的编解码、数据…...

YSYX学习记录(八)

C语言&#xff0c;练习0&#xff1a; 先创建一个文件夹&#xff0c;我用的是物理机&#xff1a; 安装build-essential 练习1&#xff1a; 我注释掉了 #include <stdio.h> 出现下面错误 在你的文本编辑器中打开ex1文件&#xff0c;随机修改或删除一部分&#xff0c;之后…...

linux arm系统烧录

1、打开瑞芯微程序 2、按住linux arm 的 recover按键 插入电源 3、当瑞芯微检测到有设备 4、松开recover按键 5、选择升级固件 6、点击固件选择本地刷机的linux arm 镜像 7、点击升级 &#xff08;忘了有没有这步了 估计有&#xff09; 刷机程序 和 镜像 就不提供了。要刷的时…...

Linux云原生安全:零信任架构与机密计算

Linux云原生安全&#xff1a;零信任架构与机密计算 构建坚不可摧的云原生防御体系 引言&#xff1a;云原生安全的范式革命 随着云原生技术的普及&#xff0c;安全边界正在从传统的网络边界向工作负载内部转移。Gartner预测&#xff0c;到2025年&#xff0c;零信任架构将成为超…...

BCS 2025|百度副总裁陈洋:智能体在安全领域的应用实践

6月5日&#xff0c;2025全球数字经济大会数字安全主论坛暨北京网络安全大会在国家会议中心隆重开幕。百度副总裁陈洋受邀出席&#xff0c;并作《智能体在安全领域的应用实践》主题演讲&#xff0c;分享了在智能体在安全领域的突破性实践。他指出&#xff0c;百度通过将安全能力…...

实现弹窗随键盘上移居中

实现弹窗随键盘上移的核心思路 在Android中&#xff0c;可以通过监听键盘的显示和隐藏事件&#xff0c;动态调整弹窗的位置。关键点在于获取键盘高度&#xff0c;并计算剩余屏幕空间以重新定位弹窗。 // 在Activity或Fragment中设置键盘监听 val rootView findViewById<V…...