网站建设一般需经历确立,平台制作网站公司,承德网站制作人才招聘,wordpress微博#x1f525;个人主页#xff1a;艾莉丝努力练剑 ❄专栏传送门#xff1a;《C语言》、《数据结构与算法》、C语言刷题12天IO强训、LeetCode代码强化刷题 #x1f349;学习方向#xff1a;C/C方向 ⭐️人生格言#xff1a;为天地立心#xff0c;为生民立命#xff0c;为… 个人主页艾莉丝努力练剑 ❄专栏传送门《C语言》、《数据结构与算法》、C语言刷题12天IO强训、LeetCode代码强化刷题 学习方向C/C方向 ⭐️人生格言为天地立心为生民立命为往圣继绝学为万世开太平 前言牛客网和LeetCode的刷题都不可或缺我们都要做一做无论是参加竞赛还是笔试面试至少能提升你的代码能力洛谷的题目也可以去做一做。力扣的题目对提升代码能力很有帮助需要有一点基础几乎都是接口型的题目关于接口型和IO型的区别我们在本专栏的第一篇【LeetCode】力扣题——轮转数组、消失的数字、数组串联中就介绍过了这里不再赘述我们进入今天的力扣题目介绍—— 目录
正文
一、有效的括号
1、思路
2、解题过程
3、改进方案
4、其他思路——有局限性的一种思路
结尾 正文
一、有效的括号
链接20. 有效的括号
博主题解链接借助数据结构——栈——解决经典例题【有效的括号】 推荐大家可以直接去看博主在力扣上面写的题解博主介绍的还是比较详细的博主写题解尤其是数据结构算法题的题解都是画图加说明简单易懂。 题目描述 除了示例本题也给了这样一个提示—— 1、思路
我们的思路是
借助数据结构——栈遍历字符串左括号入栈是右括号就取栈顶元素比较看是否匹配。 我们先来看看题目描述—— 分析一下题目的意思—— 2、解题过程
像这种题目拿到手我们首先就是想到要画图一定要有这个意识数据结构的算法题一定要画图。 注意是取栈顶可不是出栈顶哦 接下来我们就可以写代码了—— 代码演示
//定义栈的结构
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-arr NULL;ps-top 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;
}//栈是否为空
bool STEmpty(ST* ps)
{assert(ps);return ps-top 0;
}//出栈——栈顶
void STPop(ST* ps)
{assert(!STEmpty(ps));ps-top--;
}//取栈顶元素
STDataType STTop(ST* ps)
{assert(!STEmpty(ps));return ps-arr[ps-top - 1];
}//获取栈中有效元素个数
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{//右括号——取栈顶比较匹配则出栈不匹配直接返回false//栈不为空才能取栈项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;}//判断栈是否为空为空有效非空无效if(STEmpty(st)){STDestory(st);return true;}STDestory(st);return false;STDestory(st);return ret;
}
复杂度时间复杂度O(N)空间复杂度O(1)。
3、改进方案 最后我们【判断栈是否为空为空有效非空无效】那里代码太长了我们用一个三目表达式就可以把它替换下来这就是改进方案。 代码演示
//定义栈的结构
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-arr NULL;ps-top 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;
}//栈是否为空
bool STEmpty(ST* ps)
{assert(ps);return ps-top 0;
}//出栈——栈顶
void STPop(ST* ps)
{assert(!STEmpty(ps));ps-top--;
}//取栈顶元素
STDataType STTop(ST* ps)
{assert(!STEmpty(ps));return ps-arr[ps-top - 1];
}//获取栈中有效元素个数
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{//右括号——取栈顶比较匹配则出栈不匹配直接返回false//栈不为空才能取栈项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;}//判断栈是否为空为空有效非空无效// if(STEmpty(st))// {// STDestory(st);// return true;// }// STDestory(st);// return false;//写成三目表达式bool ret STEmpty(st) ? true : false;STDestory(st);return ret;
}
复杂度时间复杂度O(N)空间复杂度O(1)。 代码只有一个循环遍历其它的都是条件判断时间复杂度O(N)也没有额外申请空间故空间复杂度O(1)复杂度较优。 4、其他思路——有局限性的一种思路 结尾
往期回顾
【LeetCode数据结构】单链表的应用——随机链表的复制问题、相交链表问题详解
【牛客LeetCode数据结构】单链表的应用——移除链表元素问题、链表分割问题详解
【牛客LeetCode数据结构】单链表的应用——合并两个有序链表问题、链表的回文结构问题详解
【LeetCode数据结构】单链表的应用——反转链表问题、链表的中间节点问题详解
【LeetCode】力扣题——轮转数组、消失的数字、数组串联
【LeetCode】力扣题——轮转数组、消失的数字、数组串联 结语本篇文章到这里就结束了本文讲述的两道代码题并不适合C语言初学者需要有一定的C语言基础最好要学过数据结构与算法的算法复杂度和链表的知识才能写出复杂度较优的代码来。大家一定要自己动手敲一敲不敲的话不仅容易忘记也不方便将来复习。
