手机网站建设价钱,wordpress主题基础,网站做中转,新浪云能用wordpress目录
题目要求
代码实现 题目要求
给定一个只包括 (#xff0c;)#xff0c;{#xff0c;}#xff0c;[#xff0c;] 的字符串 s #xff0c;判断字符串是否有效
有效字符串需满足#xff1a;
左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 每…目录
题目要求
代码实现 题目要求
给定一个只包括 (){}[] 的字符串 s 判断字符串是否有效
有效字符串需满足
左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 每个右括号都有一个对应的相同类型的左括号 示例 1 输入s () 输出true 示例 2 输入s ()[]{} 输出true 示例 3 输入s (] 输出false 代码实现
创建栈所需的结构以及函数
// 数据类型
typedef char STDataType;typedef struct Stack
{STDataType* a; //指向栈底的指针int top; //栈顶元素的下标int capaicty; //容量
}ST;// 初始化
void STInit(ST* pst)
{assert(pst);pst-a NULL;pst-top -1;pst-capaicty 0;
}// 入栈尾插
void STPush(ST* pst, STDataType x)
{// 数据入栈前判断是否需要扩容if (pst-capaicty (pst-top 1)){// 扩容int newCapaicty pst-capaicty 0 ? 4 : pst-capaicty * 2;STDataType* tmp (STDataType*)realloc(pst-a, sizeof(STDataType) * newCapaicty);// 判断是否扩容成功if (tmp NULL){perror(realloc fail);return;}pst-a tmp;pst-capaicty newCapaicty;}// 存放数据pst-a[pst-top] x;
}// 出栈尾删
void STPop(ST* pst)
{// 当栈内无数据时if (pst-top -1){printf(无数据可出栈\n);return;}pst-top--;
}// 访问栈顶元素
STDataType STTop(ST* pst)
{assert(pst);// 当栈内无数据时if (pst-top -1){printf(无数据可访问\n);return -1;}return pst-a[pst-top];
}// 判断栈是否为空
bool STEmpty(ST* pst)
{assert(pst);return pst-top -1;
}// 释放栈
void STDestroy(ST* pst)
{assert(pst);free(pst-a);pst-a NULL;pst-capaicty 0;pst-top -1;
}
代码演示
bool isValid(char* s)
{assert(s ! NULL);int len (int)strlen(s);// 当字符串长度为奇数个时肯定会有括号不匹配if (len % 2 1)return false;ST st;STInit(st);for (int i 0; i len; i){// 1. 遇到左括号就入栈if (s[i] ( || s[i] [ || s[i] {){STPush(st, s[i]);}else //2. 遇到右括号就和栈顶元素左括号进行匹配{// 3. 排除第一个字符就是右括号的情况if (STEmpty(st) true){STDestroy(st);return false;}// 取出当前栈顶元素char top STTop(st); // 4. 进行匹配if (top ( s[i] ! ) || top [ s[i] ! ] ||top { s[i] ! }){// 5. 优先判断匹配不成功的情况STDestroy(st);return false;}else{// 6. 表示匹配成功移除当前栈顶元素进行下一轮匹配STPop(st);}}}bool ret STEmpty(st);// 7. 释放栈STDestroy(st);return ret;
} 代码解析
遇到左括号就入栈遇到右括号就和栈顶元素进行匹配 需要注意的是当字符串的长度为奇数的情况肯定不为有效括号且当第一个括号就是右括号的情况肯定不为有效括号
代码验证
为有效括号时
为无效括号时
算法的时间和空间复杂度
for 循环执行了 N 次每次内部常数次且以最坏的情况来看额外开辟了 N 个空间
时间复杂度O(N)
空间复杂度O(N)
