括号匹配问题:栈的巧妙应用与代码优化【栈、优化、哈希表】
当解决算法问题时,灵活使用数据结构是至关重要的。在这个问题中,我们需要判断一个只包含括号的字符串是否有效,即括号是否能够正确匹配和闭合。使用栈这一数据结构可以很好地解决这个问题。
题目链接:有效的括号
解题思路:为什么使用栈?
括号匹配问题需要判断输入的字符串中的括号是否正确闭合,而且要求括号的顺序也必须正确。这种情况下,我们可以使用堆栈来处理。
堆栈是一种后进先出(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 一.背景 由于定制化开发需要将原先的长按图标原生弹窗界面隐藏,然后显示自定义的弹窗界面,如下就是我们来实现自定义的弹窗界面...
基于算法竞赛的c++编程(28)结构体的进阶应用
结构体的嵌套与复杂数据组织 在C中,结构体可以嵌套使用,形成更复杂的数据结构。例如,可以通过嵌套结构体描述多层级数据关系: struct Address {string city;string street;int zipCode; };struct Employee {string name;int id;…...
深入浅出:JavaScript 中的 `window.crypto.getRandomValues()` 方法
深入浅出:JavaScript 中的 window.crypto.getRandomValues() 方法 在现代 Web 开发中,随机数的生成看似简单,却隐藏着许多玄机。无论是生成密码、加密密钥,还是创建安全令牌,随机数的质量直接关系到系统的安全性。Jav…...
汽车生产虚拟实训中的技能提升与生产优化
在制造业蓬勃发展的大背景下,虚拟教学实训宛如一颗璀璨的新星,正发挥着不可或缺且日益凸显的关键作用,源源不断地为企业的稳健前行与创新发展注入磅礴强大的动力。就以汽车制造企业这一极具代表性的行业主体为例,汽车生产线上各类…...
渲染学进阶内容——模型
最近在写模组的时候发现渲染器里面离不开模型的定义,在渲染的第二篇文章中简单的讲解了一下关于模型部分的内容,其实不管是方块还是方块实体,都离不开模型的内容 🧱 一、CubeListBuilder 功能解析 CubeListBuilder 是 Minecraft Java 版模型系统的核心构建器,用于动态创…...
华为OD机试-食堂供餐-二分法
import java.util.Arrays; import java.util.Scanner;public class DemoTest3 {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseint a in.nextIn…...
uniapp微信小程序视频实时流+pc端预览方案
方案类型技术实现是否免费优点缺点适用场景延迟范围开发复杂度WebSocket图片帧定时拍照Base64传输✅ 完全免费无需服务器 纯前端实现高延迟高流量 帧率极低个人demo测试 超低频监控500ms-2s⭐⭐RTMP推流TRTC/即构SDK推流❌ 付费方案 (部分有免费额度&#x…...
12.找到字符串中所有字母异位词
🧠 题目解析 题目描述: 给定两个字符串 s 和 p,找出 s 中所有 p 的字母异位词的起始索引。 返回的答案以数组形式表示。 字母异位词定义: 若两个字符串包含的字符种类和出现次数完全相同,顺序无所谓,则互为…...
python报错No module named ‘tensorflow.keras‘
是由于不同版本的tensorflow下的keras所在的路径不同,结合所安装的tensorflow的目录结构修改from语句即可。 原语句: from tensorflow.keras.layers import Conv1D, MaxPooling1D, LSTM, Dense 修改后: from tensorflow.python.keras.lay…...
【电力电子】基于STM32F103C8T6单片机双极性SPWM逆变(硬件篇)
本项目是基于 STM32F103C8T6 微控制器的 SPWM(正弦脉宽调制)电源模块,能够生成可调频率和幅值的正弦波交流电源输出。该项目适用于逆变器、UPS电源、变频器等应用场景。 供电电源 输入电压采集 上图为本设计的电源电路,图中 D1 为二极管, 其目的是防止正负极电源反接, …...
【无标题】路径问题的革命性重构:基于二维拓扑收缩色动力学模型的零点隧穿理论
路径问题的革命性重构:基于二维拓扑收缩色动力学模型的零点隧穿理论 一、传统路径模型的根本缺陷 在经典正方形路径问题中(图1): mermaid graph LR A((A)) --- B((B)) B --- C((C)) C --- D((D)) D --- A A -.- C[无直接路径] B -…...
