网站导航
> 技术文档 > 【LeetCode刷题指南】--有效的括号

【LeetCode刷题指南】--有效的括号

网友: 技术文档 2025-07-26 20:30:43

🔥个人主页：@草莓熊Lotso

🎬作者简介：C++研发方向学习者

📖个人专栏： 《C语言》 《数据结构与算法》《C语言刷题集》《Leetcode刷题指南》

⭐️人生格言：生活是默默的坚持，毅力是永久的享受。  

前言：随着编程相关知识点的学习，我们LeetCode的刷题也不能落下。在前面我们也接触到了洛谷和牛客这两个刷题网站，但是博主一直都在推荐大家使用力扣，是因为力扣的判题严谨且大部分都是接口型题目，与面试中的笔试题也更加贴合。那么还是老样子，博主会为大家提供我自己的思路和代码，但是算法题的解法肯定不止一个，欢迎大家一起交流和讨论。

目录

有效的括号

解题过程：

代码演示： 

有效的括号

题目链接：20. 有效的括号 - 力扣（LeetCode）

题目描述：

题目示例： 

 思路：借助数据结构-栈，遍历字符串，左括号入栈，右括号取栈顶元素进行比较，看是否匹配

解题过程：

1.遍历字符串，左括号就入栈，右括号就取栈顶元素

2.前提是不为空才能取，如果为空证明前面没有左括号直接销毁返回false

3.如果不为空，取栈顶元素进行匹配，出现匹配不成功的销毁后返回false

4.如果本次匹配成功，出栈，继续遍历

5.遍历完后进行判空，如果栈为空证明全部匹配上了，返回true，如果不为空则返回false

复杂度：

  • 时间复杂度: O(n)
  • 空间复杂度: O(∗)

代码演示： 

typedef char STDataType;typedef struct Stack{STDataType* arr;int top;int capacity;}ST;//初始化void STInit(ST* ps){ps->arr = NULL;ps->top = ps->capacity = 0;}//销毁void STDestory(ST* ps){if (ps->arr)free(ps->arr);ps->top = 0;ps->capacity = 0;}//入栈void STPush(ST* ps, STDataType x){assert(ps);//检查空间//空间不够就增容if (ps->top == ps->capacity){int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;STDataType* tmp = (STDataType*)realloc(ps->arr, newcapacity * sizeof(STDataType));if (tmp == NULL){perror(\"realloc fail!\");exit(1);}ps->arr = tmp;ps->capacity = newcapacity;}//空间足够ps->arr[ps->top++] = x;}//出栈void STPop(ST*ps){//ps->top--;}//取栈顶元素STDataType STTop(ST* ps){return ps->arr[ps->top - 1];;}//判空bool STEmpty(ST* ps){assert(ps);return ps->top == 0;}//求栈中有效数据个数int STSize(ST* ps){assert(ps);return ps->top;}//----------------------以上是栈结构常用接口--------------------------------bool isValid(char* s) { ST st; STInit(&st); char*pi=s; while(*pi!=\'\\0\') { if(*pi==\'(\'||*pi==\'[\'||*pi==\'{\') { STPush(&st,*pi); } else{ //右括号取栈顶元素进行匹配 //栈不为空才能取 if(STEmpty(&st)) { STDestory(&st); return false; } char top=STTop(&st); if((top==\'(\'&&*pi!=\')\')  ||(top==\'[\'&&*pi!=\']\')  ||(top==\'{\'&&*pi!=\'}\')) { STDestory(&st); return false; } //本次匹配就出栈 STPop(&st); } pi++; } //为空有效，非空无效 bool ret=STEmpty(&st)?true:false; STDestory(&st); return ret;}

这里用到了栈的结构，大家如果使用C语言写的话可以把我们之前自己实现的栈直接拷贝上去   

 往期回顾：

【数据结构初阶】--双向链表(一)

​​​​​​【数据结构初阶】--双向链表(二)

【LeetCode刷题指南】--随机链表的复制

结语：本篇文章就到此结束了，《LetetCode刷题指南》中的题目比起之间的C语言刷题集中的题目，肯定会更加复杂一些。而且题目形式也不一样，大家需要注意一下。如果文章对你有帮助的话，欢迎评论，点赞，收藏加关注，感谢大家的支持

    网络标签：

    相关问题