当前位置: 首页 > 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 / 用来注释…...

Linux链表操作全解析

Linux C语言链表深度解析与实战技巧 一、链表基础概念与内核链表优势1.1 为什么使用链表&#xff1f;1.2 Linux 内核链表与用户态链表的区别 二、内核链表结构与宏解析常用宏/函数 三、内核链表的优点四、用户态链表示例五、双向循环链表在内核中的实现优势5.1 插入效率5.2 安全…...

家政维修平台实战20:权限设计

目录 1 获取工人信息2 搭建工人入口3 权限判断总结 目前我们已经搭建好了基础的用户体系&#xff0c;主要是分成几个表&#xff0c;用户表我们是记录用户的基础信息&#xff0c;包括手机、昵称、头像。而工人和员工各有各的表。那么就有一个问题&#xff0c;不同的角色&#xf…...

Qt Http Server模块功能及架构

Qt Http Server 是 Qt 6.0 中引入的一个新模块&#xff0c;它提供了一个轻量级的 HTTP 服务器实现&#xff0c;主要用于构建基于 HTTP 的应用程序和服务。 功能介绍&#xff1a; 主要功能 HTTP服务器功能&#xff1a; 支持 HTTP/1.1 协议 简单的请求/响应处理模型 支持 GET…...

【Java_EE】Spring MVC

目录 Spring Web MVC ​编辑注解 RestController RequestMapping RequestParam RequestParam RequestBody PathVariable RequestPart 参数传递 注意事项 ​编辑参数重命名 RequestParam ​编辑​编辑传递集合 RequestParam 传递JSON数据 ​编辑RequestBody ​…...

成都鼎讯硬核科技!雷达目标与干扰模拟器,以卓越性能制胜电磁频谱战

在现代战争中&#xff0c;电磁频谱已成为继陆、海、空、天之后的 “第五维战场”&#xff0c;雷达作为电磁频谱领域的关键装备&#xff0c;其干扰与抗干扰能力的较量&#xff0c;直接影响着战争的胜负走向。由成都鼎讯科技匠心打造的雷达目标与干扰模拟器&#xff0c;凭借数字射…...

Typeerror: cannot read properties of undefined (reading ‘XXX‘)

最近需要在离线机器上运行软件&#xff0c;所以得把软件用docker打包起来&#xff0c;大部分功能都没问题&#xff0c;出了一个奇怪的事情。同样的代码&#xff0c;在本机上用vscode可以运行起来&#xff0c;但是打包之后在docker里出现了问题。使用的是dialog组件&#xff0c;…...

10-Oracle 23 ai Vector Search 概述和参数

一、Oracle AI Vector Search 概述 企业和个人都在尝试各种AI&#xff0c;使用客户端或是内部自己搭建集成大模型的终端&#xff0c;加速与大型语言模型&#xff08;LLM&#xff09;的结合&#xff0c;同时使用检索增强生成&#xff08;Retrieval Augmented Generation &#…...

Docker 本地安装 mysql 数据库

Docker: Accelerated Container Application Development 下载对应操作系统版本的 docker &#xff1b;并安装。 基础操作不再赘述。 打开 macOS 终端&#xff0c;开始 docker 安装mysql之旅 第一步 docker search mysql 》〉docker search mysql NAME DE…...

并发编程 - go版

1.并发编程基础概念 进程和线程 A. 进程是程序在操作系统中的一次执行过程&#xff0c;系统进行资源分配和调度的一个独立单位。B. 线程是进程的一个执行实体,是CPU调度和分派的基本单位,它是比进程更小的能独立运行的基本单位。C.一个进程可以创建和撤销多个线程;同一个进程中…...

android RelativeLayout布局

<?xml version"1.0" encoding"utf-8"?> <RelativeLayout xmlns:android"http://schemas.android.com/apk/res/android"android:layout_width"match_parent"android:layout_height"match_parent"android:gravity&…...