每日一题——有效括号序列
有效括号序列
- 题目描述
- 数据范围:
- 复杂度要求:
- 示例
- 题解
- 代码实现
- 代码解析
- 1. 定义栈和栈操作
- 2. 栈的基本操作
- 3. 主函数 `isValid`
- 4. 返回值
- 时间和空间复杂度分析
题目描述
给出一个仅包含字符 '(', ')', '{', '}', '[', ']' 的字符串,判断该字符串是否是一个合法的括号序列。
- 括号必须以正确的顺序关闭。即
"()"和"()[]{}"都是合法的括号序列,而"(]"和"([)]"是不合法的。
数据范围:
- 字符串长度 0 ≤ n ≤ 10000 0 \leq n \leq 10000 0≤n≤10000
复杂度要求:
- 时间复杂度: O ( n ) O(n) O(n)
- 空间复杂度: O ( n ) O(n) O(n)
示例
示例 1:
输入:
"["
返回值:
false
示例 2:
输入:
"[]"
返回值:
true
题解
在这道题目中,我们可以使用栈来解决。具体思路如下:
-
栈的应用:
- 使用栈来模拟括号的匹配。每次遇到左括号
'(','{','['时,将其压入栈中。遇到右括号')','}',']'时,判断栈顶是否是对应的左括号。如果是,则弹出栈顶元素,如果不是,则说明序列不合法。
- 使用栈来模拟括号的匹配。每次遇到左括号
-
栈的空检查:
- 如果在检查过程中栈为空且仍然遇到右括号,则说明没有匹配的左括号,返回
false。
- 如果在检查过程中栈为空且仍然遇到右括号,则说明没有匹配的左括号,返回
-
遍历字符串:
- 遍历输入字符串,如果最后栈为空,则说明所有的括号都正确配对,返回
true。否则,返回false。
- 遍历输入字符串,如果最后栈为空,则说明所有的括号都正确配对,返回
代码实现
/*** 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可*** @param s string字符串* @return bool布尔型*/
#define MAX_SIZE 10000 // 假设栈最大容量// 用一个栈存储括号
char stack[MAX_SIZE];
int top = -1; // 栈顶指针,初始化时栈为空// 将字符s1压入栈
void push(char s1) {stack[++top] = s1;
}// 从栈中弹出一个字符
char pop() {return stack[top--];
}// 判断栈是否为空
bool isEmpty() {return top == -1;
}// 判断字符串是否是有效的括号序列
bool isValid(char* s) {// 遍历字符串中的每个字符for (int i = 0; s[i] != '\0'; i++) {// 如果栈为空且当前字符是右括号,则返回falseif (isEmpty()) {if (s[i] == '}' || s[i] == ']' || s[i] == ')') {return false;} else {push(s[i]); // 否则将当前左括号压入栈}} else { // 如果栈非空并且当前字符是右括号if (s[i] == '}' || s[i] == ']' || s[i] == ')') {char temp = pop(); // 弹出栈顶元素// 检查栈顶元素是否与当前右括号匹配if ((s[i] == '}' && temp != '{') || (s[i] == ']' && temp != '[') || (s[i] == ')' && temp != '(')) {return false; // 不匹配则返回false}} else {push(s[i]); // 否则将当前左括号压入栈}}}// 遍历完字符串后,栈应该为空return isEmpty();
}
代码解析
1. 定义栈和栈操作
#define MAX_SIZE 10000 // 假设栈最大容量
char stack[MAX_SIZE]; // 用于存储括号
int top = -1; // 栈顶指针,初始化时栈为空
- 定义了一个大小为
MAX_SIZE的栈数组stack,用于存储括号。 - 栈顶指针
top初始化为-1,表示栈为空。
2. 栈的基本操作
- push: 将一个字符压入栈。
void push(char s1) {stack[++top] = s1; // 将字符压入栈
}
- pop: 从栈中弹出一个字符。
char pop() {return stack[top--]; // 返回栈顶元素并将栈顶指针下移
}
- isEmpty: 判断栈是否为空。
bool isEmpty() {return top == -1; // 如果栈顶指针为-1,表示栈为空
}
3. 主函数 isValid
isValid 函数遍历字符串,对于每个字符,判断是左括号还是右括号,并进行相应的栈操作:
- 左括号处理: 遇到左括号时直接压入栈。
- 右括号处理: 遇到右括号时,弹出栈顶元素并进行匹配。如果匹配失败,则返回
false。 - 边界条件: 在遍历完成后,如果栈为空,则说明括号序列合法,否则不合法。
4. 返回值
- 如果栈为空,说明所有括号都匹配,返回
true;否则返回false。
时间和空间复杂度分析
-
时间复杂度: 每个字符仅遍历一次,栈操作(压栈和弹栈)都是常数时间操作,因此总的时间复杂度是 O ( n ) O(n) O(n),其中 n n n 是字符串的长度。
-
空间复杂度: 由于需要使用一个栈来存储括号,栈的最大容量为字符串长度 n n n,因此空间复杂度是 O ( n ) O(n) O(n)。
相关文章:
每日一题——有效括号序列
有效括号序列 题目描述数据范围:复杂度要求: 示例题解代码实现代码解析1. 定义栈和栈操作2. 栈的基本操作3. 主函数 isValid4. 返回值 时间和空间复杂度分析 题目描述 给出一个仅包含字符 (, ), {, }, [, ] 的字符串,判断该字符串是否是一个…...
PyTorch数据建模
回归分析 import torch import numpy as np import pandas as pd from torch.utils.data import DataLoader,TensorDataset import time strat = time.perf_counter()...
OpenAI 实战进阶教程 - 第二节:生成与解析结构化数据:从文本到表格
目标 学习如何使用 OpenAI API 生成结构化数据(如 JSON、CSV 格式)。掌握解析数据并导出表格文件的技巧,以便适用于不同实际场景。 场景背景 假设你是一名开发人员,需要快速生成一批产品信息列表(如名称、价格、描述…...
二叉树--链式存储
1我们之前学了二叉树的顺序存储(这种顺序存储的二叉树被称为堆),我们今天来学习一下二叉树的链式存储: 我们使用链表来表示一颗二叉树: ⽤链表来表⽰⼀棵⼆叉树,即⽤链来指⽰元素的逻辑关系。通常的⽅法是…...
Windows 中的 WSL:开启你的 Linux 之旅
今天在安装windows上安装Docker Desktop的时候,遇到了WSL。下面咱们就学习下。 欢迎来到涛涛聊AI 一、什么是 WSL? WSL,全称为 Windows Subsystem for Linux,是微软为 Windows 系统开发的一个兼容层,它允许用户在 Win…...
2.3学习总结
今天做了下上次测试没做出来的题目,作业中做了一题,看了下二叉树(一脸懵B) P2240:部分背包问题 先求每堆金币的性价比(价值除以重量),将这些金币由性价比从高到低排序。 对于排好…...
前端力扣刷题 | 6:hot100之 矩阵
73. 矩阵置零 给定一个 m x n 的矩阵,如果一个元素为 0 ,则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。 法一: var setZeroes function(matrix) {let setX new Set(); // 用于存储需要置零的行索引let setY new Set(); //…...
docker gitlab arm64 版本安装部署
前言: 使用RK3588 部署gitlab 平台作为个人或小型团队办公代码版本使用 1. docker 安装 sudo apt install docker* 2. 获取arm版本的gitlab GitHub - zengxs/gitlab-arm64: GitLab docker image (CE & EE) for arm64 git clone https://github.com/zengxs…...
路径规划之启发式算法之二十九:鸽群算法(Pigeon-inspired Optimization, PIO)
鸽群算法(Pigeon-inspired Optimization, PIO)是一种基于自然界中鸽子群体行为的智能优化算法,由Duan等人于2014年提出。该算法模拟了鸽子在飞行过程中利用地标、太阳和磁场等导航机制的行为,具有简单、高效和易于实现的特点,适用于解决连续优化问题。 更多的仿生群体算法…...
【AudioClassificationModelZoo-Pytorch】基于Pytorch的声音事件检测分类系统
源码:https://github.com/Shybert-AI/AudioClassificationModelZoo-Pytorch 模型测试表 模型网络结构batch_sizeFLOPs(G)Params(M)特征提取方式数据集类别数量模型验证集性能EcapaTdnn1280.486.1melUrbanSound8K10accuracy0.974, precision0.972 recall0.967, F1-s…...
一文讲解Java中的ArrayList和LinkedList
ArrayList和LinkedList有什么区别? ArrayList 是基于数组实现的,LinkedList 是基于链表实现的。 二者用途有什么不同? 多数情况下,ArrayList更利于查找,LinkedList更利于增删 由于 ArrayList 是基于数组实现的&#…...
CNN的各种知识点(五):平均精度均值(mean Average Precision, mAP)
平均精度均值(mean Average Precision, mAP) 1. 平均精度均值(mean Average Precision, mAP)概念:计算步骤:具体例子:重要说明:典型值范围: 总结: 1. 平均精度…...
【优先算法】专题——前缀和
目录 一、【模版】前缀和 参考代码: 二、【模版】 二维前缀和 参考代码: 三、寻找数组的中心下标 参考代码: 四、除自身以外数组的乘积 参考代码: 五、和为K的子数组 参考代码: 六、和可被K整除的子数组 参…...
gitea - fatal: Authentication failed
文章目录 gitea - fatal: Authentication failed概述run_gitea_on_my_pkm.bat 笔记删除windows凭证管理器中对应的url认证凭证启动gitea服务端的命令行正常用 TortoiseGit 提交代码备注END gitea - fatal: Authentication failed 概述 本地的git归档服务端使用gitea. 原来的用…...
基于Spring Security 6的OAuth2 系列之八 - 授权服务器--Spring Authrization Server的基本原理
之所以想写这一系列,是因为之前工作过程中使用Spring Security OAuth2搭建了网关和授权服务器,但当时基于spring-boot 2.3.x,其默认的Spring Security是5.3.x。之后新项目升级到了spring-boot 3.3.0,结果一看Spring Security也升级…...
蓝桥与力扣刷题(234 回文链表)
题目:给你一个单链表的头节点 head ,请你判断该链表是否为回文链表。如果是,返回 true ;否则,返回 false 。 示例 1: 输入:head [1,2,2,1] 输出:true示例 2: 输入&…...
Google C++ Style / 谷歌C++开源风格
文章目录 前言1. 头文件1.1 自给自足的头文件1.2 #define 防护符1.3 导入你的依赖1.4 前向声明1.5 内联函数1.6 #include 的路径及顺序 2. 作用域2.1 命名空间2.2 内部链接2.3 非成员函数、静态成员函数和全局函数2.4 局部变量2.5 静态和全局变量2.6 thread_local 变量 3. 类3.…...
Windows图形界面(GUI)-QT-C/C++ - QT Tab Widget
公开视频 -> 链接点击跳转公开课程博客首页 -> 链接点击跳转博客主页 目录 一、概述 1.1 什么是 QTabWidget? 1.2 使用场景 二、常见样式 2.1 选项卡式界面 2.2 动态添加和删除选项卡 2.3 自定义选项卡标题和图标 三、属性设置 3.1 添加页面&…...
【大数据技术】教程05:本机DataGrip远程连接虚拟机MySQL/Hive
本机DataGrip远程连接虚拟机MySQL/Hive datagrip-2024.3.4VMware Workstation Pro 16CentOS-Stream-10-latest-x86_64-dvd1.iso写在前面 本文主要介绍如何使用本机的DataGrip连接虚拟机的MySQL数据库和Hive数据库,提高编程效率。 安装DataGrip 请按照以下步骤安装DataGrip软…...
C++:结构体和类
在之前的博客中已经讲过了C语言中的结构体概念了,重复的内容在这儿就不赘述了。C中的结构体在C语言的基础上还有些补充,在这里说明一下,顺便简单地讲一下类的概念。 一、成员函数 结构体类型声明的关键字是 struct ,在C中结构体…...
MPNet:旋转机械轻量化故障诊断模型详解python代码复现
目录 一、问题背景与挑战 二、MPNet核心架构 2.1 多分支特征融合模块(MBFM) 2.2 残差注意力金字塔模块(RAPM) 2.2.1 空间金字塔注意力(SPA) 2.2.2 金字塔残差块(PRBlock) 2.3 分类器设计 三、关键技术突破 3.1 多尺度特征融合 3.2 轻量化设计策略 3.3 抗噪声…...
MongoDB学习和应用(高效的非关系型数据库)
一丶 MongoDB简介 对于社交类软件的功能,我们需要对它的功能特点进行分析: 数据量会随着用户数增大而增大读多写少价值较低非好友看不到其动态信息地理位置的查询… 针对以上特点进行分析各大存储工具: mysql:关系型数据库&am…...
dedecms 织梦自定义表单留言增加ajax验证码功能
增加ajax功能模块,用户不点击提交按钮,只要输入框失去焦点,就会提前提示验证码是否正确。 一,模板上增加验证码 <input name"vdcode"id"vdcode" placeholder"请输入验证码" type"text&quo…...
[ICLR 2022]How Much Can CLIP Benefit Vision-and-Language Tasks?
论文网址:pdf 英文是纯手打的!论文原文的summarizing and paraphrasing。可能会出现难以避免的拼写错误和语法错误,若有发现欢迎评论指正!文章偏向于笔记,谨慎食用 目录 1. 心得 2. 论文逐段精读 2.1. Abstract 2…...
Mac软件卸载指南,简单易懂!
刚和Adobe分手,它却总在Library里给你写"回忆录"?卸载的Final Cut Pro像电子幽灵般阴魂不散?总是会有残留文件,别慌!这份Mac软件卸载指南,将用最硬核的方式教你"数字分手术"࿰…...
工业自动化时代的精准装配革新:迁移科技3D视觉系统如何重塑机器人定位装配
AI3D视觉的工业赋能者 迁移科技成立于2017年,作为行业领先的3D工业相机及视觉系统供应商,累计完成数亿元融资。其核心技术覆盖硬件设计、算法优化及软件集成,通过稳定、易用、高回报的AI3D视觉系统,为汽车、新能源、金属制造等行…...
是否存在路径(FIFOBB算法)
题目描述 一个具有 n 个顶点e条边的无向图,该图顶点的编号依次为0到n-1且不存在顶点与自身相连的边。请使用FIFOBB算法编写程序,确定是否存在从顶点 source到顶点 destination的路径。 输入 第一行两个整数,分别表示n 和 e 的值(1…...
html css js网页制作成品——HTML+CSS榴莲商城网页设计(4页)附源码
目录 一、👨🎓网站题目 二、✍️网站描述 三、📚网站介绍 四、🌐网站效果 五、🪓 代码实现 🧱HTML 六、🥇 如何让学习不再盲目 七、🎁更多干货 一、👨…...
服务器--宝塔命令
一、宝塔面板安装命令 ⚠️ 必须使用 root 用户 或 sudo 权限执行! sudo su - 1. CentOS 系统: yum install -y wget && wget -O install.sh http://download.bt.cn/install/install_6.0.sh && sh install.sh2. Ubuntu / Debian 系统…...
Java求职者面试指南:Spring、Spring Boot、MyBatis框架与计算机基础问题解析
Java求职者面试指南:Spring、Spring Boot、MyBatis框架与计算机基础问题解析 一、第一轮提问(基础概念问题) 1. 请解释Spring框架的核心容器是什么?它在Spring中起到什么作用? Spring框架的核心容器是IoC容器&#…...
