括号匹配问题:栈的巧妙应用与代码优化【栈、优化、哈希表】
当解决算法问题时,灵活使用数据结构是至关重要的。在这个问题中,我们需要判断一个只包含括号的字符串是否有效,即括号是否能够正确匹配和闭合。使用栈这一数据结构可以很好地解决这个问题。
题目链接:有效的括号
解题思路:为什么使用栈?
括号匹配问题需要判断输入的字符串中的括号是否正确闭合,而且要求括号的顺序也必须正确。这种情况下,我们可以使用堆栈来处理。
堆栈是一种后进先出(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 一.背景 由于定制化开发需要将原先的长按图标原生弹窗界面隐藏,然后显示自定义的弹窗界面,如下就是我们来实现自定义的弹窗界面...
后进先出(LIFO)详解
LIFO 是 Last In, First Out 的缩写,中文译为后进先出。这是一种数据结构的工作原则,类似于一摞盘子或一叠书本: 最后放进去的元素最先出来 -想象往筒状容器里放盘子: (1)你放进的最后一个盘子(…...
FastAPI 教程:从入门到实践
FastAPI 是一个现代、快速(高性能)的 Web 框架,用于构建 API,支持 Python 3.6。它基于标准 Python 类型提示,易于学习且功能强大。以下是一个完整的 FastAPI 入门教程,涵盖从环境搭建到创建并运行一个简单的…...
SiFli 52把Imagie图片,Font字体资源放在指定位置,编译成指定img.bin和font.bin的问题
分区配置 (ptab.json) img 属性介绍: img 属性指定分区存放的 image 名称,指定的 image 名称必须是当前工程生成的 binary 。 如果 binary 有多个文件,则以 proj_name:binary_name 格式指定文件名, proj_name 为工程 名&…...
【VLNs篇】07:NavRL—在动态环境中学习安全飞行
项目内容论文标题NavRL: 在动态环境中学习安全飞行 (NavRL: Learning Safe Flight in Dynamic Environments)核心问题解决无人机在包含静态和动态障碍物的复杂环境中进行安全、高效自主导航的挑战,克服传统方法和现有强化学习方法的局限性。核心算法基于近端策略优化…...
【C++特殊工具与技术】优化内存分配(一):C++中的内存分配
目录 一、C 内存的基本概念 1.1 内存的物理与逻辑结构 1.2 C 程序的内存区域划分 二、栈内存分配 2.1 栈内存的特点 2.2 栈内存分配示例 三、堆内存分配 3.1 new和delete操作符 4.2 内存泄漏与悬空指针问题 4.3 new和delete的重载 四、智能指针…...
华为OD机考-机房布局
import java.util.*;public class DemoTest5 {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseSystem.out.println(solve(in.nextLine()));}}priv…...
MyBatis中关于缓存的理解
MyBatis缓存 MyBatis系统当中默认定义两级缓存:一级缓存、二级缓存 默认情况下,只有一级缓存开启(sqlSession级别的缓存)二级缓存需要手动开启配置,需要局域namespace级别的缓存 一级缓存(本地缓存&#…...
医疗AI模型可解释性编程研究:基于SHAP、LIME与Anchor
1 医疗树模型与可解释人工智能基础 医疗领域的人工智能应用正迅速从理论研究转向临床实践,在这一过程中,模型可解释性已成为确保AI系统被医疗专业人员接受和信任的关键因素。基于树模型的集成算法(如RandomForest、XGBoost、LightGBM)因其卓越的预测性能和相对良好的解释性…...
PydanticAI快速入门示例
参考链接:https://ai.pydantic.dev/#why-use-pydanticai 示例代码 from pydantic_ai import Agent from pydantic_ai.models.openai import OpenAIModel from pydantic_ai.providers.openai import OpenAIProvider# 配置使用阿里云通义千问模型 model OpenAIMode…...
Linux入门(十五)安装java安装tomcat安装dotnet安装mysql
安装java yum install java-17-openjdk-devel查找安装地址 update-alternatives --config java设置环境变量 vi /etc/profile #在文档后面追加 JAVA_HOME"通过查找安装地址命令显示的路径" #注意一定要加$PATH不然路径就只剩下新加的路径了,系统很多命…...
