有效的括号(字节面试题 最优解)

news/2024/12/15 12:28:01/

题目来源

20. 有效的括号 - 力扣(LeetCode)


题目描述

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

有效字符串需满足:

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

示例 1:

输入:s = "()"

输出:true

示例 2:

输入:s = "()[]{}"

输出:true

示例 3:

输入:s = "(]"

输出:false

示例 4:

输入:s = "([])"

输出:true

提示:

  • 1 <= s.length <= 104
  • s 仅由括号 '()[]{}' 组成

题目限制

要求最优解 

不能暴力


思路分析

这题可以用栈这种数据结构来解决,以下是思路提示:

首先,遍历给定的字符串。

当遇到左括号(也就是 '('、'{'、'[' 这几种)的时候,把它们依次压入栈中。因为后续要靠它们来匹配对应的右括号嘛。

而一旦遇到右括号(')'、'}'、'[' )时,就去检查栈顶元素。如果栈为空,那说明没有可以匹配的左括号了,直接返回 false ;要是栈不为空,就看看栈顶的左括号和当前遇到的右括号是不是同一类型的(比如栈顶是 '(',当前是 ')' ,这就是同一类型能匹配上的情况),如果是同一类型,那就把栈顶元素弹出,表示这个括号对匹配上了;要是类型不同,那就不符合要求,直接返回 false 。

最后,当整个字符串都遍历完了,如果栈为空,那就说明所有括号都匹配上了,字符串是有效的,返回 true,要是栈里还有元素,那就意味着有左括号没匹配到右括号,返回 false 。

利用栈来处理的好处在于它能很好地按照顺序来记录和匹配括号,符合括号匹配的先后顺序规则,时间复杂度相对比较优哦。大家可以顺着这个思路再详细去思考具体的实现啦。


具体代码

class Solution {
public:bool isValid(string s) {stack <char> a;for(auto i:s){if(i=='('||i=='{'||i=='[')a.push(i);else {if(a.empty())return false;else{char top=a.top();if((top=='('&&i==')')||(top=='{'&&i=='}')||(top=='['&&i==']'))a.pop();else{return false;}}}}return a.empty();}
};

在上述代码中,我们使用了std::stack(栈)这个容器来辅助我们解决问题。首先,我们遍历输入的字符串 s。当遇到左括号('(''{''[')时,我们将其压入栈 a 中。而当遇到右括号时,我们首先检查栈是否为空,如果为空,那就意味着没有对应的左括号来匹配这个右括号,所以直接返回 false。如果栈不为空,我们获取栈顶元素 top,然后检查栈顶的左括号和当前的右括号是否是匹配的类型(例如 '(' 和 ')' 匹配、'[' 和 ']' 匹配、'{' 和 '}' 匹配),如果是匹配的,我们就将栈顶元素弹出,表示这一对括号已经成功匹配;如果不匹配,那么就说明字符串中的括号不是有效的,直接返回 false。当整个字符串都遍历完后,如果栈为空,那就说明所有的括号都找到了对应的匹配括号,字符串是有效的,返回 true;否则返回 false

这种利用栈来解决括号匹配问题的方法,充分利用了栈的后进先出(LIFO)特性,能够高效且准确地判断字符串中括号的有效性。通过这个问题,我们不仅加深了对栈数据结构的理解,也提升了我们解决实际编程问题的能力。

 


注意事项

解题思路在编程学习中占据着举足轻重的地位。就拿本题来说,关键在于确定运用何种算法予以攻克。多数人起初往往只会盲目地尝试各种括号匹配方式,然而这毫无成效。若无法洞悉解题的核心思路,个人的编程能力将永远停滞不前。刷题的意义绝非仅仅局限于用代码实现某个题目,更为关键的是要深刻领悟其背后的解题思路,而这其中的核心要素便是算法。它宛如一盏明灯,能够穿透问题的重重迷雾,引导我们找到高效且准确的解决方案,从而在编程的学习之路上实现真正的成长与突破。


http://www.ppmy.cn/news/1555289.html

相关文章

Qt之网络监测

在Qt中&#xff0c;网络监测通常涉及到检测网络连接状态、网络延迟、带宽使用情况等。Qt提供了一些类和模块来帮助开发者实现这些功能。以下是一些常用的方法和类&#xff1a; 1. 检测网络连接状态 QtNetwork模块中的QNetworkConfigurationManager类可以用来检测设备的网络连…

ConfyUI(sd-webui)-aki-v4.9.1升级安装Torch 2.5.1-CUDA12.4【含安装包】

总结&#xff1a; 原地升级操作三步走【要有一个能正常运行的aki-v4.9.1&#xff0c;先压缩备份它】&#xff1a; 一、在绘世-高级选项-安装PyTorch时&#xff0c;找到接近并且低于N卡CUDA驱动版本的版本&#xff0c;显示安装成功&#xff1b; 二、重启绘世-高级选项-原生组件…

将PDF流使用 canvas 绘制然后转为图片展示在页面上(二)

将PDF流转为图片展示在页面上 使用 pdfjs-dist 库来渲染 PDF 页面到 canvas 上&#xff0c;然后将 canvas 转为图片 安装 pdfjs-dist 依赖 npm install pdfjs-dist 或者 yarn add pdfjs-dist创建一个组件来处理 PDF 流的加载和渲染 该组件中是一个包含 PDF 文件的 ArrayBuffer…

OGG FOR MYSQL同步DDL

以下实验测试OGG FOR mysql 同步DDL&#xff0c; OGG 21.3 MYSQL 8.0.27 --创建测试数据 create table oggddl_20241201 (oid int primary key ,oname varchar(10)); create table oggddl_20241202 (oid int primary key ,oname varchar(10)); create table oggddl_20241203…

php仿199万年历程序源码的实现方法和成品黄历站展示

以下是一个简单的方案&#xff0c;包含了前端设计思路、后端逻辑和黄历计算的基本实现。 设计方案 1. 项目架构 核心文件: Calendar.php: 封装黄历计算逻辑。index.php: 入口文件&#xff0c;处理用户输入并调用黄历类。 2. 黄历类设计 (Calendar.php) 属性: date: 存储用户…

ubuntu 用 ss-tproxy的最终网络结构

1、包含了AD广告域名筛选 2、Ss-tproxy 国内国外地址分类 3、chinadns-ng解析 4、透明网关 更多细节看之前博客 ubuntu 用ss-TPROXY实现透明代理&#xff0c;基于TPROXY的透明TCP/UDP代理,在 Linux 2.6.28 后进入官方内核。ubuntu 用 ss-tproxy的内置 DNS 前挂上 AdGuardHome…

杨振宁大学物理视频中黄色的字,c#写程序去掉(原版改进,二)

我发现&#xff0c;黄色消去比较稳定。 而色带矩形&#xff0c;经常变化&#xff0c;不稳定。 所以我们能不能先保证稳定的消去黄色&#xff1f;可以。 我们原来的代码黄色和色带矩形混在一起了&#xff0c;我们拆分开&#xff1a; 而且我们知道图像高度480&#xff0c;黄色…

Java 动态设置 JVM 参数的方法

Java虚拟机&#xff08;JVM&#xff09;在运行Java应用时&#xff0c;其性能调优和资源管理至关重要。虽然许多JVM参数在启动时通过命令行设置&#xff0c;但在应用运行期间动态调整某些参数也是可行的。通过动态设置JVM参数&#xff0c;开发者可以更有效地管理资源使用和优化性…