括号匹配问题:栈的巧妙应用与代码优化【栈、优化、哈希表】
当解决算法问题时,灵活使用数据结构是至关重要的。在这个问题中,我们需要判断一个只包含括号的字符串是否有效,即括号是否能够正确匹配和闭合。使用栈这一数据结构可以很好地解决这个问题。
题目链接:有效的括号
解题思路:为什么使用栈?
括号匹配问题需要判断输入的字符串中的括号是否正确闭合,而且要求括号的顺序也必须正确。这种情况下,我们可以使用堆栈来处理。
堆栈是一种后进先出(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();}
};
栈的基础操作的使用技巧
在解决这个问题时,我们充分利用了栈的基础操作:
push:将左括号入栈。pop:遇到右括号时,出栈并与当前右括号比较是否匹配。top:检查栈顶元素是否与当前右括号匹配。
这些操作使得我们能够高效地检查括号是否匹配。
总结与反思
括号匹配问题是一个典型的使用堆栈解决的问题。通过将左括号压入堆栈,然后在遇到相应的右括号时进行出栈匹配,我们可以有效地判断括号是否正确闭合。
原始代码虽然已经完成了任务,但存在着冗长的 if-else 语句,不够优雅。通过使用哈希表存储括号对应关系,我们能够用更简洁的代码完成同样的功能,提高代码的可读性和维护性。
括号匹配问题只是栈在算法中的一个小应用,栈还有许多其他强大的用途,如逆波兰表达式求值、深度优先搜索等。掌握栈的基本操作和灵活应用,对于提升算法和数据结构的理解能力非常有帮助。
相关文章:
括号匹配问题:栈的巧妙应用与代码优化【栈、优化、哈希表】
当解决算法问题时,灵活使用数据结构是至关重要的。在这个问题中,我们需要判断一个只包含括号的字符串是否有效,即括号是否能够正确匹配和闭合。使用栈这一数据结构可以很好地解决这个问题。 题目链接:有效的括号 解题思路…...
vue项目正确使用样式deep穿透
经常开发前端的程序员应该都知道前端一般都是组件化开发,为了避免样式污染通常会使用scoped添加属性选择器,此时如果我们想在父组件中修改子组件的样式便成了难题。其实,我们可以通过以下几种方式修改子组件样式, 组件样式穿透 …...
Jenkins持续集成-快速上手
Jenkins持续集成-快速上手 注:Jenkins一般不单独使用,而是需要依赖代码仓库,构建工具等。 搭配组合:GitGitee(GitHub、GitLab)MavenJenkins 前置准备 常见安装方式: war包Docker容器实例&…...
查看linux 所有运行的应用和端口命令
要查看 Linux 中所有运行的应用程序及其对应的端口,可以使用以下命令: 1. 使用 netstat 命令(已被弃用,建议使用 ss 命令): netstat -tuln 这会显示当前系统上所有打开的网络连接和监听的端口。其中&#…...
Maven安装与配置,Eclipse配置Maven【图文并茂的保姆级教程】
🥳🥳Welcome Huihuis Code World ! !🥳🥳 接下来看看由辉辉所写的关于Maven的相关操作吧 目录 🥳🥳Welcome Huihuis Code World ! !🥳🥳 一.Maven是什么? 二.Maven的下…...
利用XLL文件投递Qbot银行木马的钓鱼活动分析
1概述 近期,安天CERT发现了一起利用恶意Microsoft Excel加载项(XLL)文件投递Qbot银行木马的恶意活动。攻击者通过发送垃圾邮件来诱导用户打开附件中的XLL文件,一旦用户安装并激活Microsoft Excel加载项,恶意代码将被执…...
2023CNSS——WEB题解(持续更新)
[Baby] SignIn 进来看到 按钮点击不了,想到去修改代码,要“检查“,但这里的右键和F12都不可用 还好还有其他方法 检查的各种方法 选用一种后进入检查页面 删掉这里的disabled即可 点击后得到flag [Baby] Backdoor 进入,…...
Unity之ShaderGraph 节点介绍 数学节点
数学 高级Absolute(绝对值)Exponential(幂)Length(长度)Log(对数)Modulo(余数)Negate(相反数)Normalize(标准化矢量&…...
springboot mongo 使用
nosql对我来说,就是用它的变动列,如果列是固定的,我为什么不用mysql这种关系型数据库呢? 所以,现在网上搜出来的大部分,用实体类去接的做法,并不适合我的需求。 所以,整理记录一下…...
如何使用appuploader制作apple证书
转载:如何使用appuploader制作apple证书 如何使用appuploader制作apple证书 一.证书管理 点击首页的证书管理 二.新建证书 点击“添加”,新建一个证书文件 免费账号制作证书只有7天有效期,没有推送消息功能,推送证书…...
Promise详细版
promise基础原理到难点分析 常见的Promise的方法解读 扩展async和await深入分析 逐步分析Promise底层逻辑代码 一、Promise基础 1.什么是promise 为了解决回调地狱: //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拆成两个部分,即Sping Data和JPA。 从这两个部分来解释。 Spring Data是什么? 摘自: https://spring.io/projects/spring-data Spring Data’s mission is to provide a familiar and cons…...
如何防止CSRF攻击
背景 随着互联网的高速发展,信息安全问题已经成为企业最为关注的焦点之一,而前端又是引发企业安全问题的高危据点。在移动互联网时代,前端人员除了传统的 XSS、CSRF 等安全问题之外,又时常遭遇网络劫持、非法调用 Hybrid API 等新…...
linuxARM裸机学习笔记(7)----RTC实时时钟实验
基础概念: I.MX6U 内部也有个RTC 模块,但是不叫作“ RTC ”,而是叫做“ SNVS ”。 SNVS 直译过来就是安全的非易性存储, SNVS 里面主要是一些低功耗的外设,包括一个 安全的实时计数器 (RTC) 、一个单调计数器 (mo…...
NSS [UUCTF 2022 新生赛]ez_upload
NSS [UUCTF 2022 新生赛]ez_upload 考点:Apache解析漏洞 开题就是标准的上传框 起手式就是传入一个php文件,非常正常的有过滤。 .txt、.user.ini、.txxx都被过滤了,应该是白名单或者黑名单加MIME过滤,只允许.jpg、.png。 猜测二…...
【操作系统】操作系统知识点总结(秋招篇)
文章目录 前言操作系统主要做了哪些工作?进程 线程 协程之间的区别进程的组成部分介绍一下进程的PCB讲一下进程的五态 以及它们的状态转移用户态和内核态是什么?进程在用户态和内核态之间是如何切换的讲一下进程之间的通信方式讲一下进程调度的三个层次介…...
篇十九:迭代器模式:遍历集合
篇十九:"迭代器模式:遍历集合" 开始本篇文章之前先推荐一个好用的学习工具,AIRIght,借助于AI助手工具,学习事半功倍。欢迎访问:http://airight.fun/。 另外有2本不错的关于设计模式的资料&…...
浅谈JVM中的即时编译器(Just-In-Time compiler, JIT)
Java虚拟机(JVM)中的即时编译器(Just-In-Time compiler, JIT)是一个非常重要的组件,它负责将字节码转换为本地机器代码。在不使用JIT的情况下,JVM通过解释字节码来执行程序,这意味着它会为每个字…...
Android 13 Launcher——长按图标弹窗内容修改以及小组件等隐藏起来
目录 一.背景 二.实现思路 三.布局文件修改 四.隐藏代码中原先的view 一.背景 由于定制化开发需要将原先的长按图标原生弹窗界面隐藏,然后显示自定义的弹窗界面,如下就是我们来实现自定义的弹窗界面...
TDengine 快速体验(Docker 镜像方式)
简介 TDengine 可以通过安装包、Docker 镜像 及云服务快速体验 TDengine 的功能,本节首先介绍如何通过 Docker 快速体验 TDengine,然后介绍如何在 Docker 环境下体验 TDengine 的写入和查询功能。如果你不熟悉 Docker,请使用 安装包的方式快…...
Admin.Net中的消息通信SignalR解释
定义集线器接口 IOnlineUserHub public interface IOnlineUserHub {/// 在线用户列表Task OnlineUserList(OnlineUserList context);/// 强制下线Task ForceOffline(object context);/// 发布站内消息Task PublicNotice(SysNotice context);/// 接收消息Task ReceiveMessage(…...
NLP学习路线图(二十三):长短期记忆网络(LSTM)
在自然语言处理(NLP)领域,我们时刻面临着处理序列数据的核心挑战。无论是理解句子的结构、分析文本的情感,还是实现语言的翻译,都需要模型能够捕捉词语之间依时序产生的复杂依赖关系。传统的神经网络结构在处理这种序列依赖时显得力不从心,而循环神经网络(RNN) 曾被视为…...
Spring数据访问模块设计
前面我们已经完成了IoC和web模块的设计,聪明的码友立马就知道了,该到数据访问模块了,要不就这俩玩个6啊,查库势在必行,至此,它来了。 一、核心设计理念 1、痛点在哪 应用离不开数据(数据库、No…...
C# 求圆面积的程序(Program to find area of a circle)
给定半径r,求圆的面积。圆的面积应精确到小数点后5位。 例子: 输入:r 5 输出:78.53982 解释:由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982,因为我们只保留小数点后 5 位数字。 输…...
GitFlow 工作模式(详解)
今天再学项目的过程中遇到使用gitflow模式管理代码,因此进行学习并且发布关于gitflow的一些思考 Git与GitFlow模式 我们在写代码的时候通常会进行网上保存,无论是github还是gittee,都是一种基于git去保存代码的形式,这样保存代码…...
wpf在image控件上快速显示内存图像
wpf在image控件上快速显示内存图像https://www.cnblogs.com/haodafeng/p/10431387.html 如果你在寻找能够快速在image控件刷新大图像(比如分辨率3000*3000的图像)的办法,尤其是想把内存中的裸数据(只有图像的数据,不包…...
Chrome 浏览器前端与客户端双向通信实战
Chrome 前端(即页面 JS / Web UI)与客户端(C 后端)的交互机制,是 Chromium 架构中非常核心的一环。下面我将按常见场景,从通道、流程、技术栈几个角度做一套完整的分析,特别适合你这种在分析和改…...
嵌入式常见 CPU 架构
架构类型架构厂商芯片厂商典型芯片特点与应用场景PICRISC (8/16 位)MicrochipMicrochipPIC16F877A、PIC18F4550简化指令集,单周期执行;低功耗、CIP 独立外设;用于家电、小电机控制、安防面板等嵌入式场景8051CISC (8 位)Intel(原始…...
k8s从入门到放弃之HPA控制器
k8s从入门到放弃之HPA控制器 Kubernetes中的Horizontal Pod Autoscaler (HPA)控制器是一种用于自动扩展部署、副本集或复制控制器中Pod数量的机制。它可以根据观察到的CPU利用率(或其他自定义指标)来调整这些对象的规模,从而帮助应用程序在负…...
