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

华为OD机试 - 括号匹配 - 栈(Python/JS/C/C++ 2024 E卷 100分)

在这里插入图片描述

华为OD机试 2024E卷题库疯狂收录中,刷题点这里

专栏导读

本专栏收录于《华为OD机试真题(Python/JS/C/C++)》。

刷的越多,抽中的概率越大,私信哪吒,备注华为OD,加入华为OD刷题交流群,每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景,发现新题目,随时更新,全天CSDN在线答疑。

一、题目描述

给定一个字符串,里边可能包含“()”, “[]”, “{}”三种括号,请编写程序检查该字符串中的括号是否成对出现,且嵌套关系正确。 若括号成对出现且嵌套关系正确,或该字符串中无括号字符,输出:true; 若未正确使用括号字符,输出:false。 实现时,无需考虑非法输入。

二、输入描述

三、输出描述

四、测试用例

测试用例1:

1、输入

(1+2)/(0.5+1)

2、输出

true

3、说明

测试用例2:

1、输入

([{}])

2、输出

true

3、说明

五、解题思路

1、栈

栈的先进后出(LIFO)特性非常适合用于括号匹配问题,因为每一个右括号都需要与最近的未匹配的左括号进行配对。

栈用于跟踪左括号的出现。当遇到一个左括号时,将其压入栈中;当遇到一个右括号时,从栈中弹出一个左括号并检查是否匹配。如果在弹出时栈为空,说明有多余的右括号,匹配错误。

2、具体步骤:

  1. 遍历字符串: 从左到右逐个字符遍历字符串。
  2. 处理左括号: 遇到左括号 (、[、{ 时,将其压入栈中。
  3. 处理右括号:
    • 如果栈不为空,弹出栈顶的左括号,检查是否与当前右括号匹配。
    • 如果栈为空,说明有多余的右括号,返回false。
      最终检查: 遍历结束后,检查栈是否为空。如果栈为空,说明所有括号都匹配正确,返回true;否则,说明有未匹配的左括号,返回false。

3、复杂度分析

时间复杂度: O(n),其中n是字符串的长度,遍历一次字符串即可完成匹配检查。

空间复杂度: O(n),最坏情况下,所有字符都是左括号,需要将它们全部压入栈中。

六、Python算法源码

# 导入所需的模块
import sysdef check_brackets(expr):# 使用列表模拟栈stack = []# 定义括号对应关系bracket_map = {')': '(', ']': '[', '}': '{'}# 遍历表达式中的每个字符for ch in expr:if ch in bracket_map.values():# 如果是左括号,压入栈中stack.append(ch)elif ch in bracket_map:# 如果是右括号if not stack:# 栈为空,说明没有对应的左括号return Falseif stack[-1] == bracket_map[ch]:# 栈顶的左括号与当前右括号匹配,弹出栈顶stack.pop()else:# 栈顶的左括号与当前右括号不匹配return False# 其他字符忽略# 最后检查栈是否为空return not stackdef main():# 读取输入字符串并去除前后空格expression = sys.stdin.readline().strip()# 调用检查函数is_valid = check_brackets(expression)# 输出结果print(str(is_valid).lower())if __name__ == "__main__":main()

七、JavaScript算法源码

// 定义一个函数来检查括号匹配
function checkBrackets(expr) {const stack = []; // 使用数组模拟栈// 定义括号对应关系const bracketMap = {')': '(',']': '[','}': '{'};// 遍历表达式中的每个字符for (let ch of expr) {if (['(', '[', '{'].includes(ch)) {// 如果是左括号,压入栈中stack.push(ch);} else if ([')', ']', '}'].includes(ch)) {// 如果是右括号if (stack.length === 0) {// 栈为空,说明没有对应的左括号return false;}if (stack[stack.length - 1] === bracketMap[ch]) {// 栈顶的左括号与当前右括号匹配,弹出栈顶stack.pop();} else {// 栈顶的左括号与当前右括号不匹配return false;}}// 其他字符忽略}// 最后检查栈是否为空return stack.length === 0;
}// 读取标准输入并处理
const readline = require('readline');// 创建接口以读取输入
const rl = readline.createInterface({input: process.stdin,output: process.stdout
});// 读取输入后处理
rl.on('line', (input) => {const expression = input.trim(); // 去除前后空格const isValid = checkBrackets(expression); // 调用检查函数console.log(isValid); // 输出结果(true 或 false)rl.close(); // 关闭输入流
});

八、C算法源码

#include <stdio.h>
#include <string.h>// 定义栈的最大容量
#define MAX 100// 定义一个栈结构
typedef struct {char data[MAX]; // 存储栈内字符int top;        // 栈顶指针
} Stack;// 初始化栈
void initStack(Stack *s) {s->top = -1; // 栈顶初始化为-1,表示栈为空
}// 判断栈是否为空
int isEmpty(Stack *s) {return s->top == -1;
}// 判断栈是否满
int isFull(Stack *s) {return s->top == MAX - 1;
}// 入栈操作
void push(Stack *s, char ch) {if (!isFull(s)) {s->data[++(s->top)] = ch; // 将字符压入栈中,并移动栈顶指针}
}// 出栈操作
char pop(Stack *s) {if (!isEmpty(s)) {return s->data[(s->top)--]; // 弹出栈顶字符,并移动栈顶指针}return '\0'; // 如果栈为空,返回空字符
}// 判断左右括号是否匹配
int isMatchingPair(char left, char right) {if (left == '(' && right == ')')return 1;if (left == '[' && right == ']')return 1;if (left == '{' && right == '}')return 1;return 0;
}// 检查括号匹配函数
int checkBrackets(char *expr) {Stack stack;initStack(&stack); // 初始化栈// 遍历表达式中的每个字符for (int i = 0; i < strlen(expr); i++) {char ch = expr[i];if (ch == '(' || ch == '[' || ch == '{') {push(&stack, ch); // 如果是左括号,压入栈中}else if (ch == ')' || ch == ']' || ch == '}') {if (isEmpty(&stack)) {// 栈为空,说明没有对应的左括号return 0; // false}char top = pop(&stack); // 弹出栈顶的左括号if (!isMatchingPair(top, ch)) {// 左右括号不匹配return 0; // false}}// 其他字符忽略}// 最后检查栈是否为空if (isEmpty(&stack)) {return 1; // true}else {return 0; // false}
}int main() {char expression[101]; // 定义表达式字符串,最多100字符// 读取输入表达式if (fgets(expression, sizeof(expression), stdin) != NULL) {// 移除末尾的换行符size_t len = strlen(expression);if (len > 0 && expression[len - 1] == '\n') {expression[len - 1] = '\0';}// 调用检查函数int isValid = checkBrackets(expression);// 输出结果if (isValid)printf("true\n");elseprintf("false\n");}return 0;
}

九、C++算法源码

#include <iostream>
#include <stack>
#include <string>
using namespace std;// 检查括号匹配函数
bool checkBrackets(const string &expr) {stack<char> s; // 使用标准库中的栈// 定义括号对应关系// 不需要显式定义,因为可以直接在判断中处理// 遍历表达式中的每个字符for (char ch : expr) {if (ch == '(' || ch == '[' || ch == '{') {// 如果是左括号,压入栈中s.push(ch);}else if (ch == ')' || ch == ']' || ch == '}') {if (s.empty()) {// 栈为空,说明没有对应的左括号return false;}char top = s.top(); // 获取栈顶的左括号// 判断是否匹配if ((ch == ')' && top == '(') ||(ch == ']' && top == '[') ||(ch == '}' && top == '{')) {s.pop(); // 匹配,弹出栈顶}else {// 不匹配return false;}}// 其他字符忽略}// 最后检查栈是否为空return s.empty();
}int main() {string expression;// 读取整行输入getline(cin, expression);// 调用检查函数bool isValid = checkBrackets(expression);// 输出结果(小写 true 或 false)if (isValid)cout << "true" << endl;elsecout << "false" << endl;return 0;
}

🏆下一篇:华为OD机试真题 - 简易内存池(Python/JS/C/C++ 2024 E卷 200分)

🏆本文收录于,华为OD机试真题(Python/JS/C/C++)

刷的越多,抽中的概率越大,私信哪吒,备注华为OD,加入华为OD刷题交流群,每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景,发现新题目,随时更新,全天CSDN在线答疑。

在这里插入图片描述

相关文章:

华为OD机试 - 括号匹配 - 栈(Python/JS/C/C++ 2024 E卷 100分)

华为OD机试 2024E卷题库疯狂收录中&#xff0c;刷题点这里 专栏导读 本专栏收录于《华为OD机试真题&#xff08;Python/JS/C/C&#xff09;》。 刷的越多&#xff0c;抽中的概率越大&#xff0c;私信哪吒&#xff0c;备注华为OD&#xff0c;加入华为OD刷题交流群&#xff0c;…...

打破欧美10年芯片垄断,杨振宁教授关门弟子,仅用三年创造奇迹

有这么一位超级厉害的中国人&#xff0c;硬是把欧美那边垄断了十年的芯片技术给“撬”开了&#xff01;说起来&#xff0c;这才是我们该追的真正明星啊&#xff01;那么&#xff0c;这位大神到底是谁&#xff1f;又是怎么让欧美芯片圈儿里的人听到她的名字就心里发怵的呢&#…...

OpenCV视频I/O(20)视频写入类VideoWriter之用于将图像帧写入视频文件函数write()的使用

操作系统&#xff1a;ubuntu22.04 OpenCV版本&#xff1a;OpenCV4.9 IDE:Visual Studio Code 编程语言&#xff1a;C11 算法描述 cv::VideoWriter::write() 函数用于将图像帧写入视频文件。 该函数/方法将指定的图像写入视频文件。图像的大小必须与打开视频编写器时指定的大…...

音视频入门基础:FLV专题(14)——FFmpeg源码中,解码Script Tag的实现

一、引言 在《音视频入门基础&#xff1a;FLV专题&#xff08;9&#xff09;——Script Tag简介》中对Script Tag进行了简介&#xff0c;本文讲述FFmpeg源码中是怎样解码FLV文件的Script Tag&#xff0c;拿到里面的信息。 二、flv_read_packet函数 从《音视频入门基础&#x…...

小猿口算APP脚本(协议版)

小猿口算是一款专注于数学学习的教育应用,主要面向小学阶段的学生。它提供多种数学练习和测试,包括口算、速算、应用题等。通过智能化的题目生成和实时批改功能,帮助学生提高数学计算能力。此外,它还提供详细的学习报告和分析,帮助家长和教师了解学生的学习进度和薄弱环节…...

【长文梳理webserver核心】核心类篇

前言 有三个核心组件支撑一个reactor实现 [持续] 的 [监听] 一组fd&#xff0c;并根据每个fd上发生的事件 [调用] 相应的处理函数。这三个组件就是 EventLoop 、Channel 以及 Poller 三个类&#xff0c;其中 EventLoop 可以看作是对业务线程的封装&#xff0c;而 Channel 可以看…...

[实用工具]Docker安装nextcloud实现私有云服务和onlyoffice

Nextcloud是一款开源的云存储和协作平台&#xff0c;允许用户在自己的服务器上存储和访问文件&#xff0c;同时提供强大的协作工具。它可以替代商业云存储服务&#xff0c;让用户拥有完全控制和自主管理自己的数据。 Nextcloud支持文件上传和下载&#xff0c;可以通过Web界面、…...

基于STM32设计的生猪健康检测管理系统(NBIOT+OneNet)(240)

文章目录 一、前言1.1 项目介绍【1】项目开发背景【2】设计实现的功能【3】项目硬件模块组成1.2 设计思路1.3 项目开发背景【1】选题的意义【2】可行性分析【3】参考文献【4】项目背景【5】摘要1.4 开发工具的选择【1】设备端开发【2】上位机开发1.5 系统功能总结1.6 系统框架图…...

springboot kafka多数据源,通过配置动态加载发送者和消费者

前言 最近做项目&#xff0c;需要支持kafka多数据源&#xff0c;实际上我们也可以通过代码固定写死多套kafka集群逻辑&#xff0c;但是如果需要不修改代码扩展呢&#xff0c;因为kafka本身不处理额外逻辑&#xff0c;只是起到削峰&#xff0c;和数据的传递&#xff0c;那么就需…...

【华为】基于华为交换机的VLAN配置与不同VLAN间通信实现

划分VLAN&#xff08;虚拟局域网&#xff09;主要作用&#xff1a; 一、提高网络安全性 广播域隔离访问控制增强 二、优化网络性能 减少网络拥塞提高网络可管理性 sysytem-view #进入系统视图配置参数 vlan batch 10 20 #批量创建vlan LSW3: int g0/0/1 port…...

力扣题11~20

题11&#xff08;中等&#xff09;&#xff1a; 思路&#xff1a; 这种题目第一眼就是双循环&#xff0c;但是肯定不行滴&#xff0c;o(n^2)这种肯定超时&#xff0c;很难接受。 所以要另辟蹊径&#xff0c;我们先用俩指针&#xff08;标志位&#xff09;在最左端和最右端&am…...

更美观的HTTP性能监测工具:httpstat

reorx/httpstat是一个旨在提供更美观和详细HTTP请求统计信息的cURL命令行工具&#xff0c;它能够帮助开发者和运维人员深入理解HTTP请求的性能和状态。 1. 基本概述 项目地址&#xff1a;https://github.com/reorx/httpstat语言&#xff1a;该工具主要是以Python编写&#xff…...

在2024 VDC,听一曲“蓝心智能”的江河协奏

作为科技从业者&#xff0c;我们每年参加的终端产品发布会和开发者大会&#xff0c;少则几十场。说每一场都别有新意&#xff0c;那自然是不可能的&#xff0c;但每次去vivo的活动现场&#xff0c;总能给我耳目一新的感觉。 雨果说过&#xff0c;音乐可以表达难以用语言描述&am…...

Python编写的数字光刻仿真程序,使用了Hopkins光刻模型和粒子群优化(PSO)算法来优化掩模设计

Python编写的数字光刻仿真程序,使用了Hopkins光刻模型和粒子群优化(PSO)算法来优化掩模设计,以减少光刻过程中的图形偏差。 4. 定义了几个函数来模拟光波通过光刻系统的变化: - `transfer_function`:计算光波的相位变化。 - `light_source_function`:描述光源在各…...

【AD那些事 11】绘制PCB板时“隔离” 的那些事(笔记摘抄)

在设计新板子时发现需要考虑隔离&#xff01;&#xff01;&#xff01;&#xff01;&#xff01;&#xff01;&#xff01;&#xff01;&#xff01;&#xff01;&#xff01;于是我在网上找了很多资料&#xff0c;摘抄了一些&#xff0c;整理了一下&#xff0c;作为笔记&#…...

sublime配置(竞赛向)

我也想要有jiangly一样的sublime 先决条件 首先&#xff0c;到官网上下载最新的sublime4&#xff0c;然后在mingw官网上下载最新的mingw64 mingw64官网&#xff1a;左边菜单栏点击dowloads,然后选择MinGW-W64-builds(可能会有点慢)——然后有时候会变成选LLVM-minGW,接着选择…...

双向数据库迁移工具:轻松实现 MySQL 与 SQLite 数据互导

项目概述与作用 该项目的核心是实现 MySQL 和 SQLite 两种数据库之间的数据迁移工具。它能够轻松地将 MySQL 数据库中的数据导出为 SQLite 数据库文件&#xff0c;反过来也可以将 SQLite 数据库中的数据上传到 MySQL 数据库中。这个双向迁移工具非常适用于&#xff1a; 数据库备…...

oracle查询表空间信息

方式一&#xff0c;通过SQLPLUS查看&#xff0c;适用于无PLSQL等工具 sqlplus / as sysdba set line 200 set lines 200 col tablespace_name for a20 col SUM_SPACE(M) for a15 col USED_SPACE(M) for a15 col USED_RATE(%) for a15 col FREE_SPACE(M) for a15 SELEC…...

使用Python编写你的第一个算法交易程序

背景 Background ​ 最近想学习一下量化金融&#xff0c;总算在盈透投资者教育&#xff08;IBKRCampus&#xff09;板块找到一篇比较好的算法交易入门教程。我在记录实践过程后&#xff0c;翻译成中文写成此csdn博客&#xff0c;分享给大家。 ​ 如果你的英语好可以直接看原文…...

点进HTML初步了解

写在前边 ##关于插件 ①简体中文 ②open-in-browser&#xff1a;自动在浏览器生成html页面&#xff1b; ③Auto Rename Tag&#xff1a;自动匹配标签&#xff1b; ④Live server&#xff1a;实现页面的实时刷新&#xff1b; ##关于快捷键&#xff1a; Ctrl / 用来注释…...

KubeSphere 容器平台高可用:环境搭建与可视化操作指南

Linux_k8s篇 欢迎来到Linux的世界&#xff0c;看笔记好好学多敲多打&#xff0c;每个人都是大神&#xff01; 题目&#xff1a;KubeSphere 容器平台高可用&#xff1a;环境搭建与可视化操作指南 版本号: 1.0,0 作者: 老王要学习 日期: 2025.06.05 适用环境: Ubuntu22 文档说…...

树莓派超全系列教程文档--(62)使用rpicam-app通过网络流式传输视频

使用rpicam-app通过网络流式传输视频 使用 rpicam-app 通过网络流式传输视频UDPTCPRTSPlibavGStreamerRTPlibcamerasrc GStreamer 元素 文章来源&#xff1a; http://raspberry.dns8844.cn/documentation 原文网址 使用 rpicam-app 通过网络流式传输视频 本节介绍来自 rpica…...

Golang 面试经典题:map 的 key 可以是什么类型?哪些不可以?

Golang 面试经典题&#xff1a;map 的 key 可以是什么类型&#xff1f;哪些不可以&#xff1f; 在 Golang 的面试中&#xff0c;map 类型的使用是一个常见的考点&#xff0c;其中对 key 类型的合法性 是一道常被提及的基础却很容易被忽视的问题。本文将带你深入理解 Golang 中…...

Redis相关知识总结(缓存雪崩,缓存穿透,缓存击穿,Redis实现分布式锁,如何保持数据库和缓存一致)

文章目录 1.什么是Redis&#xff1f;2.为什么要使用redis作为mysql的缓存&#xff1f;3.什么是缓存雪崩、缓存穿透、缓存击穿&#xff1f;3.1缓存雪崩3.1.1 大量缓存同时过期3.1.2 Redis宕机 3.2 缓存击穿3.3 缓存穿透3.4 总结 4. 数据库和缓存如何保持一致性5. Redis实现分布式…...

spring:实例工厂方法获取bean

spring处理使用静态工厂方法获取bean实例&#xff0c;也可以通过实例工厂方法获取bean实例。 实例工厂方法步骤如下&#xff1a; 定义实例工厂类&#xff08;Java代码&#xff09;&#xff0c;定义实例工厂&#xff08;xml&#xff09;&#xff0c;定义调用实例工厂&#xff…...

鸿蒙DevEco Studio HarmonyOS 5跑酷小游戏实现指南

1. 项目概述 本跑酷小游戏基于鸿蒙HarmonyOS 5开发&#xff0c;使用DevEco Studio作为开发工具&#xff0c;采用Java语言实现&#xff0c;包含角色控制、障碍物生成和分数计算系统。 2. 项目结构 /src/main/java/com/example/runner/├── MainAbilitySlice.java // 主界…...

Mobile ALOHA全身模仿学习

一、题目 Mobile ALOHA&#xff1a;通过低成本全身远程操作学习双手移动操作 传统模仿学习&#xff08;Imitation Learning&#xff09;缺点&#xff1a;聚焦与桌面操作&#xff0c;缺乏通用任务所需的移动性和灵活性 本论文优点&#xff1a;&#xff08;1&#xff09;在ALOHA…...

LINUX 69 FTP 客服管理系统 man 5 /etc/vsftpd/vsftpd.conf

FTP 客服管理系统 实现kefu123登录&#xff0c;不允许匿名访问&#xff0c;kefu只能访问/data/kefu目录&#xff0c;不能查看其他目录 创建账号密码 useradd kefu echo 123|passwd -stdin kefu [rootcode caozx26420]# echo 123|passwd --stdin kefu 更改用户 kefu 的密码…...

【Linux系统】Linux环境变量:系统配置的隐形指挥官

。# Linux系列 文章目录 前言一、环境变量的概念二、常见的环境变量三、环境变量特点及其相关指令3.1 环境变量的全局性3.2、环境变量的生命周期 四、环境变量的组织方式五、C语言对环境变量的操作5.1 设置环境变量&#xff1a;setenv5.2 删除环境变量:unsetenv5.3 遍历所有环境…...

微服务通信安全:深入解析mTLS的原理与实践

&#x1f525;「炎码工坊」技术弹药已装填&#xff01; 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 一、引言&#xff1a;微服务时代的通信安全挑战 随着云原生和微服务架构的普及&#xff0c;服务间的通信安全成为系统设计的核心议题。传统的单体架构中&…...