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

每日一题——有效括号序列

有效括号序列

    • 题目描述
      • 数据范围:
      • 复杂度要求:
    • 示例
    • 题解
    • 代码实现
    • 代码解析
      • 1. 定义栈和栈操作
      • 2. 栈的基本操作
      • 3. 主函数 `isValid`
      • 4. 返回值
    • 时间和空间复杂度分析

题目描述

给出一个仅包含字符 '(', ')', '{', '}', '[', ']' 的字符串,判断该字符串是否是一个合法的括号序列。

  • 括号必须以正确的顺序关闭。即 "()""()[]{}" 都是合法的括号序列,而 "(]""([)]" 是不合法的。

数据范围:

  • 字符串长度 0 ≤ n ≤ 10000 0 \leq n \leq 10000 0n10000

复杂度要求:

  • 时间复杂度: O ( n ) O(n) O(n)
  • 空间复杂度: O ( n ) O(n) O(n)

示例

示例 1:

输入:

"["

返回值:

false

示例 2:

输入:

"[]"

返回值:

true

题解

在这道题目中,我们可以使用栈来解决。具体思路如下:

  1. 栈的应用:

    • 使用栈来模拟括号的匹配。每次遇到左括号 '(', '{', '[' 时,将其压入栈中。遇到右括号 ')', '}', ']' 时,判断栈顶是否是对应的左括号。如果是,则弹出栈顶元素,如果不是,则说明序列不合法。
  2. 栈的空检查:

    • 如果在检查过程中栈为空且仍然遇到右括号,则说明没有匹配的左括号,返回 false
  3. 遍历字符串:

    • 遍历输入字符串,如果最后栈为空,则说明所有的括号都正确配对,返回 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中结构体…...

VB.net复制Ntag213卡写入UID

本示例使用的发卡器:https://item.taobao.com/item.htm?ftt&id615391857885 一、读取旧Ntag卡的UID和数据 Private Sub Button15_Click(sender As Object, e As EventArgs) Handles Button15.Click轻松读卡技术支持:网站:Dim i, j As IntegerDim cardidhex, …...

如何在看板中体现优先级变化

在看板中有效体现优先级变化的关键措施包括:采用颜色或标签标识优先级、设置任务排序规则、使用独立的优先级列或泳道、结合自动化规则同步优先级变化、建立定期的优先级审查流程。其中,设置任务排序规则尤其重要,因为它让看板视觉上直观地体…...

Leetcode 3577. Count the Number of Computer Unlocking Permutations

Leetcode 3577. Count the Number of Computer Unlocking Permutations 1. 解题思路2. 代码实现 题目链接:3577. Count the Number of Computer Unlocking Permutations 1. 解题思路 这一题其实就是一个脑筋急转弯,要想要能够将所有的电脑解锁&#x…...

五年级数学知识边界总结思考-下册

目录 一、背景二、过程1.观察物体小学五年级下册“观察物体”知识点详解:由来、作用与意义**一、知识点核心内容****二、知识点的由来:从生活实践到数学抽象****三、知识的作用:解决实际问题的工具****四、学习的意义:培养核心素养…...

苍穹外卖--缓存菜品

1.问题说明 用户端小程序展示的菜品数据都是通过查询数据库获得,如果用户端访问量比较大,数据库访问压力随之增大 2.实现思路 通过Redis来缓存菜品数据,减少数据库查询操作。 缓存逻辑分析: ①每个分类下的菜品保持一份缓存数据…...

【android bluetooth 框架分析 04】【bt-framework 层详解 1】【BluetoothProperties介绍】

1. BluetoothProperties介绍 libsysprop/srcs/android/sysprop/BluetoothProperties.sysprop BluetoothProperties.sysprop 是 Android AOSP 中的一种 系统属性定义文件(System Property Definition File),用于声明和管理 Bluetooth 模块相…...

【OSG学习笔记】Day 16: 骨骼动画与蒙皮(osgAnimation)

骨骼动画基础 骨骼动画是 3D 计算机图形中常用的技术,它通过以下两个主要组件实现角色动画。 骨骼系统 (Skeleton):由层级结构的骨头组成,类似于人体骨骼蒙皮 (Mesh Skinning):将模型网格顶点绑定到骨骼上,使骨骼移动…...

微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据

微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据 Power Query 具有大量专门帮助您清理和准备数据以供分析的功能。 您将了解如何简化复杂模型、更改数据类型、重命名对象和透视数据。 您还将了解如何分析列,以便知晓哪些列包含有价值的数据,…...

基于TurtleBot3在Gazebo地图实现机器人远程控制

1. TurtleBot3环境配置 # 下载TurtleBot3核心包 mkdir -p ~/catkin_ws/src cd ~/catkin_ws/src git clone -b noetic-devel https://github.com/ROBOTIS-GIT/turtlebot3.git git clone -b noetic https://github.com/ROBOTIS-GIT/turtlebot3_msgs.git git clone -b noetic-dev…...

莫兰迪高级灰总结计划简约商务通用PPT模版

莫兰迪高级灰总结计划简约商务通用PPT模版,莫兰迪调色板清新简约工作汇报PPT模版,莫兰迪时尚风极简设计PPT模版,大学生毕业论文答辩PPT模版,莫兰迪配色总结计划简约商务通用PPT模版,莫兰迪商务汇报PPT模版,…...