凯里网站建设哪家好,杭州首传网站建设公司怎么样,自己的网站是什么样子的,自己做装修效果的网站一、题目描述
题目连接#xff1a;有效的括号
给定一个只包括 (#xff0c;)#xff0c;{#xff0c;}#xff0c;[#xff0c;] 的字符串 s #xff0c;判断字符串是否有效。
有效字符串需满足#xff1a;
左括号必须用相同类型的右括号闭合。左括号必须以正确的顺…一、题目描述
题目连接有效的括号
给定一个只包括 (){}[] 的字符串 s 判断字符串是否有效。
有效字符串需满足
左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。每个右括号都有一个对应的相同类型的左括号。
输出需求
示例 1
输入s ()
输出true示例 2
输入s ()[]{}
输出true示例 3
输入s (]
输出false 二、题目思路 括号匹配是使用 栈 解决的经典问题 其思路如下 遍历字符串遇到左括号将左括号与之对应的右括号入栈将栈中的括号与右括号进行对比一样就出栈。遍历完之后若栈为空则字符有效 return ture . 在解决一些问题时我们首先要考虑这些问题的极端性 首先分析不匹配的情况一共有三种情况 1️⃣左括号多余 当遍历完字符串后栈不为空则说明有多余的左括号return flase. 2️⃣: 右括号多余 当遍历过程中遇到右括号时栈为空则说明右括号多余return false. 3️⃣: 括号没有多余但是括号的类型没有对应上。 当遍历过程中遇到右括号时栈顶元素与之不对应则说明括号的类型没有对应上return false. 三、问题实现 // 用栈解决
// 数组模拟栈
bool isValid(char * s)
{ // 计算 原数组长度int len strlen(s);// 先重新开辟一个动态数组来存储栈 在堆上开辟int* stack (int*)malloc(sizeof(int)*len);// 记录插入栈中的数据个数int count 0; // 此时count指向的是栈中有效数据的下一个位置 也就是栈顶指针// 开始遍历整个数据for(int i 0; i len; i){// 开始遍历 先遍历左括号在遍历右括号if(s[i](){stack[count] );}else if(s[i][){stack[count] ];}else if(s[i]{){stack[count] };}// count0 表示 右括号多余// stack[count-1]s[i] 表示 类型没对上else if(count0||stack[count-1]!s[i]){return false;}else{count--;}}// 当遍历完整个数组栈理应为空如果栈没空 表示左括号多余return count0; //栈中无任何元素说明全部匹配成功
}
