建设官方网站需要那些人员,泰安网页设计招聘,利于优化的网站,望野古诗诵读有效括号序列 题目描述数据范围#xff1a;复杂度要求#xff1a; 示例题解代码实现代码解析1. 定义栈和栈操作2. 栈的基本操作3. 主函数 isValid4. 返回值 时间和空间复杂度分析 题目描述
给出一个仅包含字符 (, ), {, }, [, ] 的字符串#xff0c;判断该字符串是否是一个… 有效括号序列 题目描述数据范围复杂度要求 示例题解代码实现代码解析1. 定义栈和栈操作2. 栈的基本操作3. 主函数 isValid4. 返回值 时间和空间复杂度分析 题目描述
给出一个仅包含字符 (, ), {, }, [, ] 的字符串判断该字符串是否是一个合法的括号序列。
括号必须以正确的顺序关闭。即 () 和 ()[]{} 都是合法的括号序列而 (] 和 ([)] 是不合法的。
数据范围
字符串长度 0 ≤ n ≤ 10000 0 \leq n \leq 10000 0≤n≤10000
复杂度要求
时间复杂度 O ( n ) O(n) O(n)空间复杂度 O ( n ) 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 ) O(n) O(n)其中 n n n 是字符串的长度。 空间复杂度: 由于需要使用一个栈来存储括号栈的最大容量为字符串长度 n n n因此空间复杂度是 O ( n ) O(n) O(n)。
