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

括号匹配问题:栈的巧妙应用与代码优化【栈、优化、哈希表】

当解决算法问题时,灵活使用数据结构是至关重要的。在这个问题中,我们需要判断一个只包含括号的字符串是否有效,即括号是否能够正确匹配和闭合。使用这一数据结构可以很好地解决这个问题。

题目链接:有效的括号

解题思路:为什么使用栈?

括号匹配问题需要判断输入的字符串中的括号是否正确闭合,而且要求括号的顺序也必须正确。这种情况下,我们可以使用堆栈来处理。

堆栈是一种后进先出(LIFO)的数据结构,非常适合用来解决括号匹配问题。

当我们遇到左括号时,将其压入堆栈中,而遇到右括号时,我们可以弹出堆栈顶部的元素并比较是否匹配。

原始代码

首先,让我们来看一下最初的解答代码:

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

优化的代码

为了简化逻辑并提高代码的可读性,我们可以使用哈希表来存储括号的对应关系,并结合栈的基本操作进行改进:

class Solution {
public:bool isValid(string s) {stack<char> st;unordered_map<char, char> mapping = {{')', '('},{']', '['},{'}', '{'}};for (char c : s) {if (c == '(' || c == '[' || c == '{') {st.push(c);} else {if (st.empty() || st.top() != mapping[c]) {return false;}st.pop();}}return st.empty();}
};

栈的基础操作的使用技巧

在解决这个问题时,我们充分利用了栈的基础操作:

  1. push:将左括号入栈。
  2. pop:遇到右括号时,出栈并与当前右括号比较是否匹配。
  3. top:检查栈顶元素是否与当前右括号匹配。

这些操作使得我们能够高效地检查括号是否匹配。

总结与反思

括号匹配问题是一个典型的使用堆栈解决的问题。通过将左括号压入堆栈,然后在遇到相应的右括号时进行出栈匹配,我们可以有效地判断括号是否正确闭合。

原始代码虽然已经完成了任务,但存在着冗长的 if-else 语句,不够优雅。通过使用哈希表存储括号对应关系,我们能够用更简洁的代码完成同样的功能,提高代码的可读性和维护性。

括号匹配问题只是栈在算法中的一个小应用,栈还有许多其他强大的用途,如逆波兰表达式求值深度优先搜索等。掌握栈的基本操作和灵活应用,对于提升算法和数据结构的理解能力非常有帮助。

相关文章:

括号匹配问题:栈的巧妙应用与代码优化【栈、优化、哈希表】

当解决算法问题时&#xff0c;灵活使用数据结构是至关重要的。在这个问题中&#xff0c;我们需要判断一个只包含括号的字符串是否有效&#xff0c;即括号是否能够正确匹配和闭合。使用栈这一数据结构可以很好地解决这个问题。 题目链接&#xff1a;有效的括号 解题思路&#xf…...

vue项目正确使用样式deep穿透

经常开发前端的程序员应该都知道前端一般都是组件化开发&#xff0c;为了避免样式污染通常会使用scoped添加属性选择器&#xff0c;此时如果我们想在父组件中修改子组件的样式便成了难题。其实&#xff0c;我们可以通过以下几种方式修改子组件样式&#xff0c; 组件样式穿透 …...

Jenkins持续集成-快速上手

Jenkins持续集成-快速上手 注&#xff1a;Jenkins一般不单独使用&#xff0c;而是需要依赖代码仓库&#xff0c;构建工具等。 搭配组合&#xff1a;GitGitee&#xff08;GitHub、GitLab&#xff09;MavenJenkins 前置准备 常见安装方式&#xff1a; war包Docker容器实例&…...

查看linux 所有运行的应用和端口命令

要查看 Linux 中所有运行的应用程序及其对应的端口&#xff0c;可以使用以下命令&#xff1a; 1. 使用 netstat 命令&#xff08;已被弃用&#xff0c;建议使用 ss 命令&#xff09;&#xff1a; netstat -tuln 这会显示当前系统上所有打开的网络连接和监听的端口。其中&#…...

Maven安装与配置,Eclipse配置Maven【图文并茂的保姆级教程】

&#x1f973;&#x1f973;Welcome Huihuis Code World ! !&#x1f973;&#x1f973; 接下来看看由辉辉所写的关于Maven的相关操作吧 目录 &#x1f973;&#x1f973;Welcome Huihuis Code World ! !&#x1f973;&#x1f973; 一.Maven是什么&#xff1f; 二.Maven的下…...

利用XLL文件投递Qbot银行木马的钓鱼活动分析

1概述 近期&#xff0c;安天CERT发现了一起利用恶意Microsoft Excel加载项&#xff08;XLL&#xff09;文件投递Qbot银行木马的恶意活动。攻击者通过发送垃圾邮件来诱导用户打开附件中的XLL文件&#xff0c;一旦用户安装并激活Microsoft Excel加载项&#xff0c;恶意代码将被执…...

2023CNSS——WEB题解(持续更新)

[Baby] SignIn 进来看到 按钮点击不了&#xff0c;想到去修改代码&#xff0c;要“检查“&#xff0c;但这里的右键和F12都不可用 还好还有其他方法 检查的各种方法 选用一种后进入检查页面 删掉这里的disabled即可 点击后得到flag [Baby] Backdoor 进入&#xff0c…...

Unity之ShaderGraph 节点介绍 数学节点

数学 高级Absolute&#xff08;绝对值&#xff09;Exponential&#xff08;幂&#xff09;Length&#xff08;长度&#xff09;Log&#xff08;对数&#xff09;Modulo&#xff08;余数&#xff09;Negate&#xff08;相反数&#xff09;Normalize&#xff08;标准化矢量&…...

springboot mongo 使用

nosql对我来说&#xff0c;就是用它的变动列&#xff0c;如果列是固定的&#xff0c;我为什么不用mysql这种关系型数据库呢&#xff1f; 所以&#xff0c;现在网上搜出来的大部分&#xff0c;用实体类去接的做法&#xff0c;并不适合我的需求。 所以&#xff0c;整理记录一下…...

如何使用appuploader制作apple证书​

转载&#xff1a;如何使用appuploader制作apple证书​ 如何使用appuploader制作apple证书​ 一.证书管理​ 点击首页的证书管理 二.新建证书​ 点击“添加”&#xff0c;新建一个证书文件 免费账号制作证书只有7天有效期&#xff0c;没有推送消息功能&#xff0c;推送证书…...

Promise详细版

promise基础原理到难点分析 常见的Promise的方法解读 扩展async和await深入分析 逐步分析Promise底层逻辑代码 一、Promise基础 1.什么是promise 为了解决回调地狱&#xff1a; //2.设置点击事件btn.onclick function() {//3.创建ajax实例化对象let xhr new XMLHttpRe…...

v-for循环生成的盒子只改变当前选中的盒子的样式

1.给盒子添加动态属性:class"[index isActive?active-box:choose-box]" <div v-for"(item,index) in zyList" :key"item.sid" :class"[index isActive?active-box:choose-box]" click"getKmList(item,index)"…...

Spring Data JPA源码

导读: 什么是Spring Data JPA? 要解释这个问题,我们先将Spring Data JPA拆成两个部分&#xff0c;即Sping Data和JPA。 从这两个部分来解释。 Spring Data是什么? 摘自: https://spring.io/projects/spring-data Spring Data’s mission is to provide a familiar and cons…...

如何防止CSRF攻击

背景 随着互联网的高速发展&#xff0c;信息安全问题已经成为企业最为关注的焦点之一&#xff0c;而前端又是引发企业安全问题的高危据点。在移动互联网时代&#xff0c;前端人员除了传统的 XSS、CSRF 等安全问题之外&#xff0c;又时常遭遇网络劫持、非法调用 Hybrid API 等新…...

linuxARM裸机学习笔记(7)----RTC实时时钟实验

基础概念&#xff1a; I.MX6U 内部也有个RTC 模块&#xff0c;但是不叫作“ RTC ”&#xff0c;而是叫做“ SNVS ”。 SNVS 直译过来就是安全的非易性存储&#xff0c; SNVS 里面主要是一些低功耗的外设&#xff0c;包括一个 安全的实时计数器 (RTC) 、一个单调计数器 (mo…...

NSS [UUCTF 2022 新生赛]ez_upload

NSS [UUCTF 2022 新生赛]ez_upload 考点&#xff1a;Apache解析漏洞 开题就是标准的上传框 起手式就是传入一个php文件&#xff0c;非常正常的有过滤。 .txt、.user.ini、.txxx都被过滤了&#xff0c;应该是白名单或者黑名单加MIME过滤&#xff0c;只允许.jpg、.png。 猜测二…...

【操作系统】操作系统知识点总结(秋招篇)

文章目录 前言操作系统主要做了哪些工作&#xff1f;进程 线程 协程之间的区别进程的组成部分介绍一下进程的PCB讲一下进程的五态 以及它们的状态转移用户态和内核态是什么&#xff1f;进程在用户态和内核态之间是如何切换的讲一下进程之间的通信方式讲一下进程调度的三个层次介…...

篇十九:迭代器模式:遍历集合

篇十九&#xff1a;"迭代器模式&#xff1a;遍历集合" 开始本篇文章之前先推荐一个好用的学习工具&#xff0c;AIRIght&#xff0c;借助于AI助手工具&#xff0c;学习事半功倍。欢迎访问&#xff1a;http://airight.fun/。 另外有2本不错的关于设计模式的资料&…...

浅谈JVM中的即时编译器(Just-In-Time compiler, JIT)

Java虚拟机&#xff08;JVM&#xff09;中的即时编译器&#xff08;Just-In-Time compiler, JIT&#xff09;是一个非常重要的组件&#xff0c;它负责将字节码转换为本地机器代码。在不使用JIT的情况下&#xff0c;JVM通过解释字节码来执行程序&#xff0c;这意味着它会为每个字…...

Android 13 Launcher——长按图标弹窗内容修改以及小组件等隐藏起来

目录 一.背景 二.实现思路 三.布局文件修改 四.隐藏代码中原先的view 一.背景 由于定制化开发需要将原先的长按图标原生弹窗界面隐藏,然后显示自定义的弹窗界面,如下就是我们来实现自定义的弹窗界面...

vscode里如何用git

打开vs终端执行如下&#xff1a; 1 初始化 Git 仓库&#xff08;如果尚未初始化&#xff09; git init 2 添加文件到 Git 仓库 git add . 3 使用 git commit 命令来提交你的更改。确保在提交时加上一个有用的消息。 git commit -m "备注信息" 4 …...

日语AI面试高效通关秘籍:专业解读与青柚面试智能助攻

在如今就业市场竞争日益激烈的背景下&#xff0c;越来越多的求职者将目光投向了日本及中日双语岗位。但是&#xff0c;一场日语面试往往让许多人感到步履维艰。你是否也曾因为面试官抛出的“刁钻问题”而心生畏惧&#xff1f;面对生疏的日语交流环境&#xff0c;即便提前恶补了…...

装饰模式(Decorator Pattern)重构java邮件发奖系统实战

前言 现在我们有个如下的需求&#xff0c;设计一个邮件发奖的小系统&#xff0c; 需求 1.数据验证 → 2. 敏感信息加密 → 3. 日志记录 → 4. 实际发送邮件 装饰器模式&#xff08;Decorator Pattern&#xff09;允许向一个现有的对象添加新的功能&#xff0c;同时又不改变其…...

阿里云ACP云计算备考笔记 (5)——弹性伸缩

目录 第一章 概述 第二章 弹性伸缩简介 1、弹性伸缩 2、垂直伸缩 3、优势 4、应用场景 ① 无规律的业务量波动 ② 有规律的业务量波动 ③ 无明显业务量波动 ④ 混合型业务 ⑤ 消息通知 ⑥ 生命周期挂钩 ⑦ 自定义方式 ⑧ 滚的升级 5、使用限制 第三章 主要定义 …...

Day131 | 灵神 | 回溯算法 | 子集型 子集

Day131 | 灵神 | 回溯算法 | 子集型 子集 78.子集 78. 子集 - 力扣&#xff08;LeetCode&#xff09; 思路&#xff1a; 笔者写过很多次这道题了&#xff0c;不想写题解了&#xff0c;大家看灵神讲解吧 回溯算法套路①子集型回溯【基础算法精讲 14】_哔哩哔哩_bilibili 完…...

Objective-C常用命名规范总结

【OC】常用命名规范总结 文章目录 【OC】常用命名规范总结1.类名&#xff08;Class Name)2.协议名&#xff08;Protocol Name)3.方法名&#xff08;Method Name)4.属性名&#xff08;Property Name&#xff09;5.局部变量/实例变量&#xff08;Local / Instance Variables&…...

工程地质软件市场:发展现状、趋势与策略建议

一、引言 在工程建设领域&#xff0c;准确把握地质条件是确保项目顺利推进和安全运营的关键。工程地质软件作为处理、分析、模拟和展示工程地质数据的重要工具&#xff0c;正发挥着日益重要的作用。它凭借强大的数据处理能力、三维建模功能、空间分析工具和可视化展示手段&…...

vue3 定时器-定义全局方法 vue+ts

1.创建ts文件 路径&#xff1a;src/utils/timer.ts 完整代码&#xff1a; import { onUnmounted } from vuetype TimerCallback (...args: any[]) > voidexport function useGlobalTimer() {const timers: Map<number, NodeJS.Timeout> new Map()// 创建定时器con…...

Ascend NPU上适配Step-Audio模型

1 概述 1.1 简述 Step-Audio 是业界首个集语音理解与生成控制一体化的产品级开源实时语音对话系统&#xff0c;支持多语言对话&#xff08;如 中文&#xff0c;英文&#xff0c;日语&#xff09;&#xff0c;语音情感&#xff08;如 开心&#xff0c;悲伤&#xff09;&#x…...

浅谈不同二分算法的查找情况

二分算法原理比较简单&#xff0c;但是实际的算法模板却有很多&#xff0c;这一切都源于二分查找问题中的复杂情况和二分算法的边界处理&#xff0c;以下是博主对一些二分算法查找的情况分析。 需要说明的是&#xff0c;以下二分算法都是基于有序序列为升序有序的情况&#xf…...