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

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

news 来源：原创 2025/5/16 13:40:53

有效括号序列

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

题目描述

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

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

数据范围：

字符串长度 $\leq n \leq 10000$

复杂度要求：

时间复杂度： $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)$ ，其中 $n$ 是字符串的长度。
空间复杂度: 由于需要使用一个栈来存储括号，栈的最大容量为字符串长度 $n$ ，因此空间复杂度是 $O (n)$ 。

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

有效括号序列题目描述数据范围：复杂度要求： 示例题解代码实现代码解析1. 定义栈和栈操作2. 栈的基本操作3. 主函数 isValid4. 返回值时间和空间复杂度分析题目描述给出一个仅包含字符 (, ), {, }, [, ] 的字符串，判断该字符串是否是一个…...

编程日记 2025/5/16 13:40:53

MQTT 术语表

Broker 有时我们也会直接将服务端称为 Broker，这两个术语可以互换使用。 Clean Start 客户端可以在连接时使用这个字段来指示是期望从已存在的会话中恢复通信，还是创建一个全新的会话。仅限 MQTT v5.0。 Client 使用 MQTT 协议连接到服务端的设备或…...

编程日记 2025/5/15 4:57:39

每天学点小知识之设计模式的艺术-策略模式

行为型模式的名称、定义、学习难度和使用频率如下表所示： 1.如何理解模板方法模式模板方法模式是结构最简单的行为型设计模式，在其结构中只存在父类与子类之间的继承关系。通过使用模板方法模式，可以将一些复杂流程的实现步骤封装在一系列基…...

编程日记 2025/5/13 12:09:19

ubuntuCUDA安装

系列文章目录移动硬盘制作Ubuntu系统盘前言根据前篇“移动硬盘制作Ubuntu系统盘”安装系统后，还不能够使用显卡。如果需要使用显卡，还需要进行相关驱动的安装（如使用的为Nvidia显卡，就需要安装相关的Nvidia显卡驱动&#xff…...

编程日记 2025/5/15 17:37:58

信息学奥赛一本通 2113：【24CSPJ普及组】小木棍（sticks） | 洛谷 P11229 [CSP-J 2024] 小木棍

【题目链接】 ybt 2113：【24CSPJ普及组】小木棍（sticks） 洛谷 P11229 [CSP-J 2024] 小木棍【题目考点】 1. 思维题，找规律【解题思路】解法1：找规律该题为：求n根木棍组成的无前导0的所有可能的数…...

编程日记 2025/5/16 6:47:45

【数据结构】(5) ArrayList 顺序表

一、使用 ArrayList ArrayList 就是数组的封装，但是数组只有 [] 操作存取值，和 .length 操作获取数组内存长度；而 ArrayList 有更多的功能： 1、创建对象 2、扩容机制 ArrayList 有自动扩容机制，在插入元素时不用担心数…...

编程日记 2025/5/12 22:32:19

Elasticsearch 指南 [8.17] | Search APIs

Search API 返回与请求中定义的查询匹配的搜索结果。 http GET /my-index-000001/_search Request GET /<target>/_search GET /_search POST /<target>/_search POST /_search Prerequisites 如果启用了 Elasticsearch 安全功能，针对目标数据流…...

编程日记 2025/5/15 23:51:39

【自开发工具介绍】SQLSERVER的ImpDp和ExpDp工具03

SQLSERVER的ImpDp和ExpDp工具 1、全部的表导出（仅表结构导出） 2、导出的表结构，导入到新的数据库导入前，test3数据没有任何表导入导入结果确认：表都被做成，但是没有数据 3、全部的表导出&#x…...

编程日记 2025/5/16 6:36:18

JVM-运行时数据区

JVM的组成运行时数据区-总览 Java虚拟机在运行Java程序过程中管理的内存区域，称之为运行时数据区。《Java虚拟机规范》中规定了每一部分的作用运行时数据区-应用场景 Java的内存分成哪几部分？ Java内存中哪些部分会内存溢出？ JDK7 和J…...

编程日记 2025/5/16 12:07:35

经典本地影音播放器MPC-BE.

经典本地影音播放器MPC-BE 链接：https://pan.xunlei.com/s/VOIAZbbIuBM1haFdMYCubsU-A1?pwd4iz3# MPC-BE（Media Player Classic Black Edition）是来自 MPC-HC（Media Player Classic Home Cinema）的俄罗斯开发者重新…...

编程日记 2025/5/14 11:43:55

暴力解法 #include<bits/stdc.h> using namespace std; int main() {int n,m;cin>>n>>m;if(n<3||n>7||m<0){cout<<"-1";return 0;}int powN[10];//记录0-9的n次方for(int i0;i<10;i){powN[i](int)pow(i,n);}int low(int) pow(1…...

编程日记 2025/5/16 10:40:16

后盾人JS -- 原型

没有原型的对象也有没有原型的对象 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-width, initial-scale1.0"><title>Document<…...

编程日记 2025/5/12 11:24:07

Deepseek-R1 和 OpenAI o1 这样的推理模型普遍存在“思考不足”的问题

每周跟踪AI热点新闻动向和震撼发展想要探索生成式人工智能的前沿进展吗？订阅我们的简报，深入解析最新的技术突破、实际应用案例和未来的趋势。与全球数同行一同，从行业内部的深度分析和实用指南中受益。不要错过这个机会，成为AI领…...

编程日记 2025/5/12 14:07:39

Nginx 命令行参数

文章来源：命令行参数 -- nginx中文文档|nginx中文教程 nginx 支持以下命令行参数： -?| — 打印帮助以获取命令行参数。-h-c file— 使用替代项 configuration 而不是 default 文件。file-e file— 使用替代项 error log 来存储日志而不是默认文件 &…...

编程日记 2025/5/11 14:39:36

YOLOV11-1：YoloV11-安装和CLI方式训练模型

YoloV11-安装和CLI方式训练模型 1.安装和运行1.1安装的基础环境1.2安装yolo相关组件1.3命令行方式使用1.3.1 训练1.3.2 预测本文介绍yoloV11的安装和命令行接口 1.安装和运行 1.1安装的基础环境 GPU环境，其中CUDA是12.4版本 1.2安装yolo相关组件 # 克隆github…...

编程日记 2025/5/14 14:40:17

Docker Hub 镜像 Pull 失败的解决方案

目录引言一、问题二、原因三、解决方法四、参考文献引言在云原生技术火热的当下，Docker可谓是其基础，由于其简单以及方便性，让开发人员不必再为环境配置问题而伤脑筋，因为可将其看作一个虚拟机程序去理解。所以掌握好它可谓是…...

编程日记 2025/5/15 5:37:30

重新思考绩效管理变革

Peter Cappelli 和 Anna Tavis 在绩效管理变革一文中，为我们带来了很多关于绩效管理变革的思考。企业为什么做绩效管理变革，为什么现在需要？让我们看看这些学者是如何思考的。摘要受到老板和下属的痛恨，传统的绩效考核已经被超…...

编程日记 2025/5/15 11:45:23

内核定时器2-高分辨率定时器

高分辨率定时器与低分辨率定时器高分辨率定时器与低分辨率定时器相比，有如下两个根本性的不同。 (1) 高分辨率定时器使用红黑树对定时器进行管理。 (2) 定时器独立于周期时钟。即不基于jiffies，精度可以达到纳秒级别。内核2.6.16版本开始&#xff…...

编程日记 2025/5/11 13:45:28

【自开发工具介绍】SQLSERVER的ImpDp和ExpDp工具02

工具运行前的环境准备 1、登录用户管理员权限确认工具使用的登录用户(-u后面的用户)，必须具有管理员的权限，因为需要读取系统表例：Export.bat -s 10.48.111.12 -d db1 -u test -p test -schema dbo 　　　　 2、Powershell的安全策略确认…...

编程日记 2025/5/7 14:52:39

数据结构【单链表操作大全详解】【c语言版】（只有输入输出为了方便用的c++）

单链表操作的C/C实现详解在数据结构中，单链表是一种非常基础且重要的数据结构。它由一系列节点组成，每个节点包含数据和指向下一个节点的指针。今天我们就来深入探讨用C/C实现的单链表及其各种操作。一、单链表的定义 const int N 1e5; //单链表 t…...

编程日记 2025/5/15 5:37:29

【R语言】环境空间

一、环境空间种类 R语言中有5种环境： 全局环境：也叫用户环境，指在当前用户下R程序运行的环境空间。内部环境：通过“new.env()”命令创建的环境空间，也可以是匿名的环境空间。父环境：当前环境空间所处…...

编程日记 2025/5/15 17:49:46

Python处理数据库：MySQL与SQLite详解

Python处理数据库：MySQL与SQLite详解在数据处理和存储方面，数据库扮演着至关重要的角色。Python提供了多种与数据库交互的方式，其中pymysql库用于连接和操作MySQL数据库，而SQLite则是一种轻量级的嵌入式数据库，Pytho…...

编程日记 2025/5/16 1:38:24

软考高项笔记信息技术及其发展

信息技术及其发展 ❝ 信息系统项目管理师第二章第一节 1. 网络标准协议的定义网络协议是为计算机网络中进行数据交换而建立的规则、标准或约定的集合。网络协议由三个要素组成，分别是语义、语法和时序。语义：解释控制信息每个部分的含义，它…...

编程日记 2025/5/15 11:14:09

HAO的Graham学习笔记

前置知识：凸包摘录oiwiki 在平面上能包含所有给定点的最小凸多边形叫做凸包。其定义为：对于给定集合 X，所有包含 X 的凸集的交集 S 被称为 X 的凸包。说人话就是用一个橡皮筋包含住所有给定点的形态如图： 正题&#xff1a…...

编程日记 2025/5/16 13:35:38

C#基础知识

0 C#介绍定义与背景 C#（发音为C - sharp）是微软公司开发的一种高级编程语言。它是专门为构建在微软的.NET平台上运行的各种应用程序而设计的。在2000年左右推出，目的是结合当时编程语言的优点，如C的强大功能和Java的简单性与安全…...

编程日记 2025/5/13 0:12:39

Kafka中文文档

文章来源：https://kafka.cadn.net.cn 什么是事件流式处理？ 事件流是人体中枢神经系统的数字等价物。它是为“永远在线”的世界奠定技术基础，在这个世界里，企业越来越多地使用软件定义和 automated，而软件的用户更…...

编程日记 2025/5/14 22:40:30

Tyrant(暴君):反向Shell-后门注入与持久化控制的渗透测试工具

Tyrant Tyrant 是一款用于渗透测试和远程控制持久化的恶意工具，具备以下功能： 反向Shell：允许攻击者通过指定用户UID进行反弹对应权限的Shell会话。后门注入与持久化：在目标系统中注入后门并确保即使重启后依然能恢复控制。Tyran…...

编程日记 2025/5/15 4:00:39

leetcode刷题-贪心04

代码随想录贪心算法part04|452. 用最少数量的箭引爆气球、435. 无重叠区间、763.划分字母区间 452. 用最少数量的箭引爆气球435. 无重叠区间763.划分字母区间今天的三道题目，都算是重叠区间问题，大家可以好好感受一下。都属于那种看起来好复杂&#…...

编程日记 2025/5/15 17:37:59

系统学习算法：专题八二叉树中的深搜

深搜其实就是深度优先遍历（dfs），与此相对的还有宽度优先遍历（bfs） 如果学完数据结构有点忘记，如下图，左边是dfs，右边是bfs 而二叉树的前序，中序，后序遍历都可…...

编程日记 2025/5/16 13:26:14

2022年全国职业院校技能大赛网络系统管理赛项模块A：网络构建（样题2）-网络部分解析-附详细代码

目录附录1：拓扑图编辑附录2：地址规划表 1.SW1 2.SW2 3.SW3 4.SW4 5.SW5 6.SW6 7.SW7 8.R1 9.R2 10.R3 11.AC1 12.AC2 13.EG1 14.EG2 15.AP2 16.AP3 附录1：拓扑图附录2：地址规划表...

编程日记 2025/5/13 3:16:45

笔试-业务逻辑4

应用小明在玩一个数字加减游戏，输入4个正整数：s、t、a、b，其中s>1，b<105，a!b。只使用加法或者减法，使得st。每回合，小明用当前的数字，加上或减去一个数字；目前有…...

编程日记 2025/5/14 20:11:23

冷启动+强化学习：DeepSeek-R1 的原理详解——无需监督数据的推理能力进化之路

本文基于 DeepSeek 官方论文进行分析，论文地址为：https://github.com/deepseek-ai/DeepSeek-R1/blob/main/DeepSeek_R1.pdf 有不足之处欢迎评论区交流原文翻译在阅读和理解一篇复杂的技术论文时，逐字翻译是一个重要的步骤。它不仅能帮助我们准确把握作者的原意，还能为后续…...

编程日记 2025/5/13 9:24:13

ubuntu22安装issac gym记录

整体参考：https://blog.csdn.net/Yakusha/article/details/144306858 安装完成后的整体版本信息 ubuntu：22.04内核：6.8.0-51-generic显卡：NVIDIA GeForce RTX 3050 OEM显卡驱动：535.216.03cuda：12.2cudnn&…...

编程日记 2025/5/12 10:30:15

Docker小游戏 | 使用Docker部署2048网页小游戏

Docker小游戏 | 使用Docker部署2048网页小游戏前言项目介绍项目简介项目预览二、系统要求环境要求环境检查Docker版本检查检查操作系统版本三、部署2048网页小游戏下载镜像创建容器检查容器状态检查服务端口安全设置四、访问2048网页小游戏五、总结前言在当今快速发展的技术世…...

编程日记 2025/5/15 6:08:12

C基础寒假练习(2)

一、输出3-100以内的完美数，(完美数：因子和(因子不包含自身)数本身 #include <stdio.h>// 函数声明 int isPerfectNumber(int num);int main() {printf("3-100以内的完美数有:\n");for (int i 3; i < 100; i){if (isPerfectNumber…...

编程日记 2025/5/12 6:30:44

传输层协议 UDP 与 TCP

🌈 个人主页：Zfox_ 🔥 系列专栏：Linux 目录一：🔥 前置复盘🦋 传输层🦋 再谈端口号🦋 端口号范围划分🦋 认识知名端口号 (Well-Know Port Number) 二&#xf…...

编程日记 2025/5/13 3:15:01

Vue06

目录一、声明式导航-导航链接 1.需求 2.解决方案 3.通过router-link自带的两个样式进行高亮二、声明式导航的两个类名 1.router-link-active 2.router-link-exact-active 三、声明式导航-自定义类名（了解） 1.问题 2.解决方案 3.代码演示四…...

编程日记 2025/5/13 17:02:56

AJAX笔记进阶篇

黑马程序员视频地址： AJAX-Day04-01.同步代码和异步代码https://www.bilibili.com/video/BV1MN411y7pw?vd_source0a2d366696f87e241adc64419bf12cab&spm_id_from333.788.videopod.episodes&p47 同步代码和异步代码回调函数地狱与解决方法回调函数地狱…...

编程日记 2025/5/13 23:06:01

Linux+Docer 容器化部署之 Shell 语法入门篇【Shell 循环类型】

文章目录一、Shell 循环类型二、Shell while 循环三、Shell for 循环四、Shell until 循环五、Shell select 循环六、总结一、Shell 循环类型循环是一个强大的编程工具，使您能够重复执行一组命令。在本教程中，您将学习以下类型的循环 Shell 程序&…...

编程日记 2025/5/16 4:57:41

【Redis】安装配置Redis超详细教程 / Linux版

Linux安装配置Redis超详细教程安装redis依赖安装redis启动redis停止redisredis.conf常见配置设置redis为后台启动修改redis监听地址设置工作目录修改密码监听的端口号数据库数量设置redis最大内存设置日志文件设置redis开机自动启动学习视频：黑马程序员Redis入门到…...

编程日记 2025/5/13 1:47:32

S4 HANA明确税金汇差科目(OBYY)

本文主要介绍在S4 HANA OP中明确税金汇差科目(OBYY)相关设置。具体请参照如下内容： 1. 明确税金汇差科目(OBYY) 以上配置点定义了在外币挂账时，当凭证抬头汇率和税金行项目汇率不一致时，造成的差异金额进入哪个科目。此类情况只发生在FB60/F…...

编程日记 2025/5/14 10:20:31

Nginx反向代理笔记250203

Nginx反向代理 Nginx 是一个高性能的 HTTP 服务器和反向代理服务器。反向代理是指客户端请求资源时，Nginx 作为中间层，将请求转发到后端服务器，并将后端服务器的响应返回给客户端。通过反向代理，可以实现负载均衡、缓存、SSL 终端…...

编程日记 2025/5/12 6:42:34

【ChatGPT：开启人工智能新纪元】

一、ChatGPT 是什么最近，ChatGPT 可是火得一塌糊涂，不管是在科技圈、媒体界，还是咱们普通人的日常聊天里，都能听到它的大名。好多人都在讨论，这 ChatGPT 到底是个啥 “神器”，能让大家这么着迷？今天咱就好好唠唠。 ChatGPT，全称是 Chat Generative Pre-trained Trans…...

编程日记 2025/5/14 1:19:39

OpenAI 实战进阶教程 - 第六节: OpenAI 与爬虫集成实现任务自动化

爬虫与 OpenAI 模型结合，不仅能高效地抓取并分析海量数据，还能通过 NLP 技术生成洞察、摘要，极大提高业务效率。以下是一些实际工作中具有较高价值的应用案例： 1. 电商价格监控与智能分析应用场景： 电商企业需要监控…...

编程日记 2025/5/14 9:28:40

49【服务器介绍】

服务器和你的电脑可以说是一模一样的，只不过用途不一样，叫法就不一样了物理服务器和云服务器的区别整台设备眼睛能够看得到的，我们一般称之为物理服务器。所以物理服务器是比较贵的，不是每一个开发者都能够消费得起的。 …...

编程日记 2025/5/12 10:25:56

docker pull Error response from daemon问题

里面填写里面解决方案就是挂代理。以虚拟机为例，将宿主机配置端口设置，https/http端口设为7899 配置虚拟机的http代理： vim /etc/systemd/system/docker.service.d/http-proxy.conf里面填写，wq保存 [Service] Environment…...

编程日记 2025/5/13 5:55:35

院校联合以项目驱动联合培养医工计算机AI人才路径探析

一、引言 1.1 研究背景与意义在科技飞速发展的当下，医疗人工智能作为一个极具潜力的新兴领域，正深刻地改变着传统医疗模式。从疾病的早期诊断、个性化治疗方案的制定，到药物研发的加速，人工智能技术的应用极大地提升了医疗服务…...

编程日记 2025/5/12 12:22:35

C++ Primer 标准库vector

欢迎阅读我的【CPrimer】专栏专栏简介：本专栏主要面向C初学者，解释C的一些基本概念和基础语言特性，涉及C标准库的用法，面向对象特性，泛型特性高级用法。通过使用标准库中定义的抽象设施，使你更加适应高级…...

编程日记 2025/5/12 16:09:36

Mac本地部署DeekSeek-R1下载太慢怎么办？

Ubuntu 24 本地安装DeekSeek-R1 在命令行先安装ollama curl -fsSL https://ollama.com/install.sh | sh 下载太慢，使用讯雷，mac版下载链接 https://ollama.com/download/Ollama-darwin.zip 进入网站 deepseek-r1:8b，看内存大小4G就8B模型 …...

编程日记 2025/5/12 8:48:19

kamailio-ACC_JSON模块详解【后端语言go】

要确认 ACC_JSON 模块是否已经成功将计费信息推送到消息队列（MQueue），以及如何从队列中取值，可以按照以下步骤进行操作： 1. 确认 ACC_JSON 已推送到队列 1.1 配置 ACC_JSON 确保 ACC_JSON 模块已正确配置并启用。以下…...

编程日记 2025/5/14 6:17:56