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

西安市建设网站,wordpress投资主题,网页设计工程师工资多少,站长如何做导航网站华为OD机试 2024E卷题库疯狂收录中#xff0c;刷题点这里 专栏导读 本专栏收录于《华为OD机试真题#xff08;Python/JS/C/C#xff09;》。 刷的越多#xff0c;抽中的概率越大#xff0c;私信哪吒#xff0c;备注华为OD#xff0c;加入华为OD刷题交流群#xff0c;… 华为OD机试 2024E卷题库疯狂收录中刷题点这里 专栏导读 本专栏收录于《华为OD机试真题Python/JS/C/C》。 刷的越多抽中的概率越大私信哪吒备注华为OD加入华为OD刷题交流群每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景发现新题目随时更新全天CSDN在线答疑。 一、题目描述 给定一个字符串里边可能包含“()” “[]” “{}”三种括号请编写程序检查该字符串中的括号是否成对出现且嵌套关系正确。 若括号成对出现且嵌套关系正确或该字符串中无括号字符输出true 若未正确使用括号字符输出false。 实现时无需考虑非法输入。 二、输入描述 无 三、输出描述 无 四、测试用例 测试用例1 1、输入 (12)/(0.51) 2、输出 true 3、说明 测试用例2 1、输入 ([{}]) 2、输出 true 3、说明 五、解题思路 1、栈 栈的先进后出LIFO特性非常适合用于括号匹配问题因为每一个右括号都需要与最近的未匹配的左括号进行配对。 栈用于跟踪左括号的出现。当遇到一个左括号时将其压入栈中当遇到一个右括号时从栈中弹出一个左括号并检查是否匹配。如果在弹出时栈为空说明有多余的右括号匹配错误。 2、具体步骤 遍历字符串 从左到右逐个字符遍历字符串。处理左括号 遇到左括号 (、[、{ 时将其压入栈中。处理右括号 如果栈不为空弹出栈顶的左括号检查是否与当前右括号匹配。如果栈为空说明有多余的右括号返回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 或 falserl.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) {stackchar 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 或 falseif (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在线答疑。